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 \begin{equation} 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 ...