# Questions tagged [linear-programming]

Questions on linear programming, the optimization of a linear function subject to linear constraints.

3,293 questions
23 views

### Using the primal solution solve the dual sloution

For: $$\text{Max } z=2x_1+2x_2$$ $$\text{ s.t } 2x_1+x_2\leq 16$$ $$3x_1+2x_2\leq 25$$ $$2x_1+3x_2\leq 25$$ $$x_1+x_2\leq 16$$ $$x_1,x_2\geq 0$$ Solve the primal, and solve ...
43 views

### Differential of partial minimization

Let $\mu_1 \in \mathbb{R}^n$ and $\mu_2 \in \mathbb{R}$, $h(\mu_1, \mu_2)$ be a concave function in $\mu_1, \mu_2$, and let G(\mu_2) = \underset{\mu_1 \geq 0}{max} \,\, h(\mu_1, \...
27 views

### Reducing the Eulerian cycle problem in a mixed graph to a maximum flow problem

I'm completely stuck on this one. The obvious resemblance between the two that I see is that every vertex needs to have the same amounts going in and out, in the Eulerian cycle problem the amount is ...
27 views

### Reformulate an optimization problem with absolute values as a linear program

Reformulate the following optimization problem as a linear program. $$\begin{array}{ll} \text{minimize} & 2 x_1 + 3 |x_2-10|\\ \text{subject to} & |x_1+2|+|x_2|\leq 5\end{array}$$ First, ...
34 views

### Show that a set $\mathcal U$ is convex

Consider the set $$\mathcal{U}\equiv \{U\in \mathbb{R}^K: T(U)< T'(U)\}$$ where $T$ and $T'$ are linear functionals of the vector $U$. I want to show that $\mathcal{U}$ is convex using the ...
30 views

### Subgradient procedure for lagrangian relaxation of GAP

I'm trying to solve the general assignment problem by relaxing the capacity constraint and applying the subgradient procedure. GAP (from here): Relaxation (same source as above): Subgradient method ...
26 views

### Proving equivalence with Farkas lemma

The problem I am trying to solve: trying to show that the two systems are equivalent. $$\exists x : Ax=a$$ $$Bx \leq b$$ second system: $$\nexists y,z: y^TA+z^TB=0$$ $$y^Ta+z^Tb<0$$ $$z\geq 0$$...
46 views

### Optimise allocation to minimise variance

Background I am trying to allocate customers $C_i$ to financial advisers $P_j$. Each customer has a policy value $x_i$. I'm assuming that the number of customers ($n$) allocated to each adviser is ...
22 views

28 views

### What does it mean when we can't put a particular variable as a basic variable in a LPP?

Consider the LPP of minimizing $z = -2x_1 + x_2$ subject to $$\begin{cases} x_1 + 2x_2 \le 6, \\ 3x_1 + 2x_2 \le 12, \\ x_1, x_2 \ge 0 \end{cases}$$ First I add slack variables $x_3, x_4$ which ...
30 views

### Convex Conjugate of sum-of-max terms

Let $f: \mathbb{R}^n \mapsto \mathbb{R}$ be a sum-of-max linear terms function: $$f(x) = \sum_{k=1}^K \max_i\{a_{k,i}^\top x\}$$ where $a$ are the linear coefficients. I am interested in the convex ...
14 views

### Simplify a triple cycle

I'm writing an algorithm which computes the solution for a pretty complex (for me) problem which I found online. I couldn't find a smart solution, so I decided to use the brute force. BUT as ...
25 views

### How to specify a constraint for an LP when it needs to be related to ONE of two other variables depending on smallest?

So I have a problem where I need to model a LP, but the question specifies a constraint such that x_1 must be at least 40% more than x_2 or x_3 I thought of defining it as x_1 >= 1.4 (min(x_2, x_3)) ...
32 views

### Setting up a linear equation of three variables with two equations

For the following question that has appeared in one of my homework questions, I have: A fisheries laboratory needs to prepare $300$ litres of salt solution to replenish their tropical tank with salt ...
30 views

### Problems with solving the dual problem graphically

I have the following problem minimize $21x_1-15x_2-16x_3$ subject to $2x_1-5x_2+7x_3\ge2$ $3x_1+3x_2-2x_3\ge-5$ $x_1,x_2,x_3\ge0$ So, I transformed the second constraint to make sure that the ...
58 views

### Proof in regression model

Im studying for an exam, i don't have the solution, so I hope some of you guys can help me. I have tried a lot but i can't do this proof. Here is the task: Suoppose we have the linear regression ...
42 views

### Should Mister Hungerman eat Thai or Mexican?

Mr. Hungerman’s preferences on Thai (T) and Mexican (M) food are given by $$U(x_T,x_M) = a x_T + b x_M$$ Let $p_T$ and $p_M$ denotes the prices of a Thai dinner and a Mexican dinner,...
23 views

### Optimize for a parameter in a function with constraints on other 2 more parameters

I am an applied statistics student trying to solve a problem where constrained optimization is required. I have a function $f(x, p_1, p_2)$ in which $p_1 \epsilon [0,1]$, $p_2 \epsilon [0,1]$ are ...
73 views

### Infeasible solution in Duality and Dual simplex method

Currently I am preparing the Linear Programming exam and I've got some issue to solve these problems. Shortly, suppose some linear program: max $C^{T}X$ s.t. $AX \leq b$, where $A$ is $2 \times 3$ ...
24 views

31 views

### Prove optimality of the output of the algorithm

Problem: Given $c \in \mathbb { R } _ { + } ^ { n } , a \in \mathbb { R } _ { + } ^ { n }$ and $\gamma \in \mathbb { R } _ { + } ,$ design an algorithm which, in $O ( n \log n )$ operations, computes ...