1
$\begingroup$

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 $$

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – JimmyK4542 Jan 10 '16 at 8:50
  • $\begingroup$ 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. $\endgroup$ – Johan Löfberg Jan 10 '16 at 8:52
  • $\begingroup$ Sorry! I have edited my question. $x_1+x_2=1$ $\endgroup$ – MOP Jan 10 '16 at 10:40
0
$\begingroup$

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
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – MOP Jan 12 '16 at 3:03
  • $\begingroup$ No you should get fval = -2.6000 $\endgroup$ – Erwin Kalvelagen Jan 12 '16 at 3:18
  • $\begingroup$ 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) $\endgroup$ – MOP Jan 12 '16 at 3:31
  • $\begingroup$ You must have made a mistake. $\endgroup$ – Erwin Kalvelagen Jan 12 '16 at 3:36
  • $\begingroup$ I tried to find the mistake. But I couldn't $\endgroup$ – MOP Jan 12 '16 at 3:37
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Deleting questions after they have been answered is not very nice. $\endgroup$ – Erwin Kalvelagen Jan 12 '16 at 4:57
  • $\begingroup$ 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. $\endgroup$ – MOP Jan 12 '16 at 5:13
  • $\begingroup$ Thank you very much once again for clear explanations. $\endgroup$ – MOP Jan 12 '16 at 5:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.