# How can I solve the following linear program?

I want to find the answer for the following linear program.

Max $v$

subject to $$v-5x_1-x_2 \le 0$$ $$v-x_1-4x_2 \le 0$$ $$v-2x_1-3x_2 \le 0$$ $$x_1+x_2 = 1$$ $$x_1, x_2 \ge 0$$ $$v \in R$$

I know how to solve following linear program by using MATLAB $$C^T x$$ $$s.t. Ax \le b$$ $$x \ge 0$$

We can solve this by the following MATLAB code

[x, fval]=linprog(C, A, b)


How can I solve the above linear program by using MATLAB? I cannot identify C, A, b matrices and their dimentions in the above problem.

The answers should be $$x_1=0.4, x_2=0.6, v=2.6$$

My second problem is

$$3x_1-7x_2 \le y$$ $$-3x_2-5x_3 \le y$$ $$-x_1-7x_2 \le y$$ $$x_1+x_2+x_3 =1$$ $$x_1,x_2,x_3 \ge 0$$

• If you are imposing the constraints $x_1+x_2 = 0$ and $x_1,x_2 \ge 0$, then that forces $x_1 = x_2 = 0$. Then all of the other inequalities become $v \le 0$, so the maximum of $v$ subject to all of those constraints is simply $0$. Are you sure you wrote down the constraints correctly? – JimmyK4542 Jan 10 '16 at 8:50
• First, let $x_3=v$, and then notice that linprogs syntax is more general with many more inputs as it allows for equality constraints and general lower and upper variable bounds. – Johan Löfberg Jan 10 '16 at 8:52
• Sorry! I have edited my question. $x_1+x_2=1$ – MOP Jan 10 '16 at 10:40

The equality constraint can be passed on in the Aeq,beq parameters. I.e.

>> f=[-1,0,0]; A=[1,-5,-1;1,-1,-4;1,-2,-3]; b=[0;0;0]; A2=[0,1,1]; b2=1; lo=[-inf,0,0]; up=[inf,inf,inf];
>> [x,fval]=linprog(f,A,b,A2,b2,lo,up);
Optimization terminated.
>> x

x =

2.6000
0.4000
0.6000

>> fval

fval =

-2.6000

• According to your MATLAB code, fval=6.0822e-12. But, since I want to maximize v (v=2.6), the value of the objective function(fval) and the value of v should have the same value, right? I'm little bit confused. Could you please explain this to me? – MOP Jan 12 '16 at 3:03
• No you should get fval = -2.6000 – Erwin Kalvelagen Jan 12 '16 at 3:18
• I'm sorry. It gives the right answer. But I have another matlab code. It doesn't give the right answer. It is similar to the above. It gives a wrong value for fval. Could you please help me with this? Here is the code. >>f=[1;0;0;0]; A=[-1,0,3,-7;-1,-3,0,5;-1,7,-5,0]; b=[0;0;0]; A2=[0,1,1,1]; b2=1; lo=[-inf,0,0,0]; up=[inf,inf,inf,inf]; >>[x,fval]=linprog(f,A,b,A2,b2,lo,up) – MOP Jan 12 '16 at 3:31
• You must have made a mistake. – Erwin Kalvelagen Jan 12 '16 at 3:36
• I tried to find the mistake. But I couldn't – MOP Jan 12 '16 at 3:37

Second answer for extra bonus points.

First note that you first equation looks very suspicious: $−u+3x_2−7x_2≤0$ and does not correspond to the first row in $A$.

Second 1e-12 vs 0 is very close. Within the tolerances. I would be happy with such a result. If you really care about this minuscule differences, solve with dual simplex method:

>> options = optimoptions(@linprog,'Algorithm','dual-simplex');
>> [x, fval]=linprog(f, A, b, A2, b2, lo, up, [], options)

Optimal solution found.

x =

0
0.3333
0.4667
0.2000

fval =

0


The second question has been removed by the poster so this answer is now a bit hanging in the air. Not sure what is happening with these bonus points.

• Deleting questions after they have been answered is not very nice. – Erwin Kalvelagen Jan 12 '16 at 4:57
• I'm sorry! I deleted that question because it is not a good question. You have answered it correctly. Since you have answered my all questions very nicely, I will add that question again. – MOP Jan 12 '16 at 5:13
• Thank you very much once again for clear explanations. – MOP Jan 12 '16 at 5:19