We are given the following linear problem: $\max\left\{5x_1-2x_2\mid3x_1+x_2\leq7,4x_1-2x_2\leq3,x_1\geq0,x_2\geq0\right\}$. If there exists an optimal point where at least one of its coordinates is not zero, then $x_1$ and $x_2$ shall differ by at least $1$ whereby the second coordinate mustn't be lower than the first coordinate.

I don't know how this should all be possible.

First I tried to solve the problem without respecting the conditions, just by using the Simplex algorithm:

enter image description here

Thus optimal point is $x= \begin{pmatrix} x_1\\ x_2 \end{pmatrix}= \begin{pmatrix} \frac{17}{10}\\ \frac{19}{10} \end{pmatrix}$ , clearly not satisfying the conditions above...

How is it possible to determine an optimal point satisfying these conditions? I don't know but I believe I somehow need to apply these conditions while doing the Simplex algorithm? Maybe in the middle table, increase $\frac{19}{4}$ by $1$ and continue with that? Or a complete different attempt? :o


1 Answer 1


The optimal solution is at $x = [1.7,1.9]^T$, so your answer is correct. Also, the second coordinate (I believe this is $x_2$) is greater than the first one.

Maybe "they shall differ at least 1" should be 0.1. But the answer is correct.

There is also no alternative optima since the slope of your objective function is not the same with one of the edges of your set.

  • $\begingroup$ "Differ by $1$" is clearly $1$ and not $0.1$. I'm not sure if that is really correct your answer because it seems too easy and then I also wonder why there is a condition at all in the given example. $\endgroup$
    – cnmesr
    Dec 3, 2018 at 18:57
  • $\begingroup$ To convince you, I am sharing the solver output (by Yalmip): >>x = sdpvar(2,1) >>optimize([3*x(1)+x(2) <= 7, 4*x(1)-2*x(2)<= 3, x>= 0], -5*x(1)+2*x(2) ) Solved in 1 iterations and 0.04 seconds Optimal objective -4.700000000e+00 >> value(x) ans = 1.7000 1.9000 $\endgroup$ Dec 3, 2018 at 18:59
  • $\begingroup$ Also, in the feasible region, you have 4 vertices. They are (0,7), (1.7,1.9), (0,0),(0.75,0). The optimal point has to be for sure at a vertex. Compare the values. $\endgroup$ Dec 3, 2018 at 19:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .