Linear programming

Quote:

Originally Posted by ULB

hi,
can you help me solve this probleme or how to begin

thk

min − 2x1 − x2 − x3
scq x1 +x2 + x4 ≤ 6
− 2x1 +x3 ≥ 8
4x1 − 2x2 − x3 ≥ 4
xj≥ 0 ∀j= 1,...,4

As a special favour to you, here is a link to my foolproof instructions for solving linear programming problems by the simplex method. You can find them at http://www.maths.leeds.ac.uk/~pmt6ecl/simplex.pdf. Download that pdf file and follow the instructions there.

To get you started, notice that your problem here is in what I call nonstandard form. So you need to start by following the procedure on page 2 of the pdf file. For a start, the objective function $-2x_1 - x_2 - x_3$ is to be minimised. So you should replace it by its negative, $M = 2x_1 + x_2 + x_3$ , which you maximise (and the answer to the problem will then be the negative of that).

Next, some of the inequalities have a $\geqslant$ instead of a $\leqslant$ . Change the sign of everything in them so as to flip the inequality sign. That gives you the set of inequalities

$\begin{aligned}x_1+\phantom{2}x_2\phantom{{}+x_3}+ x_4 &\leqslant 6,\\ 2x_1\phantom{{}+2x_2}-x_3\phantom{{}+x_4} &\leqslant -8,\\ -4x_1 +2x_2 + x_3\phantom{{}+x_4}&\leqslant -4,\end{aligned}$

together with the objective equation

$-2x_1 - x_2 - x_3 + M = 0.$

The matrix for the initial simplex tableau is then

$\begin{bmatrix}1&1&0&1&1&0&0&0&6\\ 2&0&-1&0&0&1&0&0&-8\\ -4&2&1&0&0&0&1&0&-4\\ -2&-1&-1&0&0&0&0&1&0\end{bmatrix}.$

(Some people leave out the last-but-one column in the tableau, which does not play an essential part in the reduction process.)

You now have to follow the reduction process described in Steps B2, B3 and B4 on the second page of the pdf file, and then you can read off the solution to the problem.

If you are unsure about how to operate the pivoting procedure, there are some good worked examples here.