1
$\begingroup$

I was given the following linear program with the supposed answers to be $x_1 = 45/103$, $x_2 = 27/103$, $x_3 = 31/103$. Howerver, I tried to solve it using the Simplex Algorithm with no success, online LP solvers also couldn't seem to find the solutions, but checking the answers work with the LP. Could someone please show me how to solve this?

$min$ $z,$ $subject$ $to$
$-2x_1 + x_2 + 3x_3 \leq z$
$x_1 - 4x_2 + 3x_3 \leq z$
$3x_1 + 3x_2 - 6x_3 \leq z$
$x_1 + x_2 + x_3 = 1$
$x_1,x_2,x_3 \geq 0$

I converted the above to

$Minimize$ $p = z$ $subject$ $to$
$z + 2x_1 - x_2 - 3x_3 \geq 0$
$z - x_1 + 4x_2 - 3x_3 \geq 0$
$z - 3x_1 - 3x_2 + 6x_3 \geq 0$
$x_1 + x_2 + x_3 = 1$

$\endgroup$
  • $\begingroup$ Where does "$x \geq 0$" come from? $\endgroup$ – Symeof Nov 9 '15 at 8:49
  • $\begingroup$ it basically says x1, x2, x3 are all greater than 0 $\endgroup$ – gametheorybeginner Nov 9 '15 at 8:50
  • $\begingroup$ then try to add these 3 equations to the system $\endgroup$ – Michael Medvinsky Nov 9 '15 at 9:00
  • $\begingroup$ I edited the equations to make them looking a little better (Ii hope). Is this OK for you ? $\endgroup$ – Claude Leibovici Nov 9 '15 at 9:03
  • $\begingroup$ sure, I added in the constraints but it still didnt work for me. $\endgroup$ – gametheorybeginner Nov 9 '15 at 9:03
0
$\begingroup$

Multiply the first equation by $45$, second by $27$, third by $31$ and add them up:

$103z\geq 30x_1+30x_2+30x_3=30$

Hence $z_{min}={30\over103}$

After that just solve the system of equations letting each of the three equations equal to $z_{min}$.

$\endgroup$
  • $\begingroup$ this is not valid because you are basically solving it with the answer given. I want to get the answers from scratch... $\endgroup$ – gametheorybeginner Nov 9 '15 at 9:03
  • $\begingroup$ No. I did not solve from answer given. What you want is three multipliers $a,b,c$ such that the linear combination of the equations gives the same ratio over $x_1,x_2,x_3$. Note that the third equation has first two term equal, so you know the first two equation must have multipliers of ratio $5:3$ as $-2+x=1-4x$ gives $x={3\over5}$. After that you add $5(-2,1,3)+3(1,-4,3)$ to get $(-7,-7,24)$. Then you are finding $-7+3x=24-6x$ giving you $x={31\over9}$. So you know the ratio of the multipliers are $45:27:31$ $\endgroup$ – cr001 Nov 9 '15 at 9:08
  • $\begingroup$ thanks for the explanation, but do you know if it is possible to use the simplex method on this problem? $\endgroup$ – gametheorybeginner Nov 9 '15 at 9:12
  • $\begingroup$ Yes it is but you would still need to find the linear combination to make a multiple of $(x_1+x_2+x_3)$. $\endgroup$ – cr001 Nov 9 '15 at 9:17
0
$\begingroup$

I know this is old, but you could only add Z as a new variable inside your simplex formulation and let:

X1 = Z

and just change all the other variables you had as: Xn = Xn+1 So you would have this system of equations:

Min P = X1

S.T:

X1 +2X2 -X3 -3X4 >= 0

X1 -X2 +4X3 -3X4 >= 0

X1 -3X2 -3X3 +6X4 >= 0

X2 + X3 +X4 = 1

Solve using Two Phase method or Big M method (You could multiply all >= 0 constraints by -1 to simplify the problem) and then you just change back your variables:

Z = X1

Xn = Xn-1

Solving this problem gets you Z = 2/7 if I recall.

$\endgroup$

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.