1
$\begingroup$

I've given the following LP problem:

P(x) = 4x1 + 5x2 -> max;
  x1 - 2x2 <= 15;
 4x1 + 3x2 <= 24;
-2x1 + 5x2 >= 20;
x1 >= 0; x2 >= 0;

I have to perform 3 tasks:

  1. Convert this problem to Normal form and check how many variables and constraints there are
  2. Convert the normal form to a Big M problem and perform a Big M simplex for the first iteration
  3. Create a dual problem for the above LP problem

I can do the 1st task and maybe the 3rd, but I've no clue how the Big M method works. I tried to search, but I couldn't find an actual example. I cannot understand the usual mathematical formulas, but I can instantly lear from even one step-by-step guide. Any link where I can find a step-by-step solution with actual numbers would be fine.

The normal form I got for task 1 is as follows:

P(x) = 4x1 + 5x2 -> max;
  x1 - 2x2 + x3 = 15;
 4x1 + 3x2 + x4 = 24;
-2x1 + 5x2 - x5 = 20;
x1 >= 0; x2 >= 0; x3 >= 0; x4 >= 0; x5 >= 0;

Is the above Normal form correct? It has 5 variables and 3 constraints, am I correct?

$\endgroup$
  • $\begingroup$ In the last equation you need to add one more variable (an artificial variable), because the simplex method does not admit negative variable as basic variables. This link show an example of the Big M method: faculty.smcm.edu/acjamieson/f12/480BigMExample.pdf $\endgroup$ – AES Dec 10 '16 at 17:16
  • $\begingroup$ Do I need the extra artificial variable for Big M method only or even for the normal form? $\endgroup$ – Moha Dec 10 '16 at 19:02
  • $\begingroup$ When you have a "$\geq$" restriction fist add a "surplus" variable (the restriction now is an equation) and then you Will need an artificial variable (this variable Will be the basic variable of that restriction) $\endgroup$ – AES Dec 11 '16 at 22:36
  • $\begingroup$ Can you help me how to write up the tabelau for this Big M? $\endgroup$ – Moha Dec 14 '16 at 9:10
  • $\begingroup$ $$P(x) = 4x_1 + 5x_2 - M x_6 \to max \\ -2x_1 + 5x_2 - x_5 + x_6 = 20 \\ x_i \ge 0 \,\forall i \in \{1,\dots,6\}$$ $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Dec 14 '16 at 23:19
1
$\begingroup$

First, write the constraints as equations:

(1) $x_1 - 2x_2 \leq 15$ we need to add a slack variable: (1)* $x_1 - 2x_2+x_3 = 15$

(2) $4x_1 + 3x_2 \leq 24$ here we need a slack variable: (2)* $4x_1 + 3x_2 + x_4= 24$

(3)$-2x1 + 5x2 \geq 20$ here we need a surplus variable: (3)*$-2x_1 + 5x_2 -x_5 = 20$

Note that we use a slack variable($+x_i $) for "$\leq$" restrictions and a surplus variable($-x_i$) for "$\geq$ " restrictions. Now we need to add an artificial variable in the constraint (3)* because we can't use surplus variables as basic variables and we need a basic variable for each contraint. The problem given is equivalent to:

max $P = 4x_1 + 5x_2-Mx_6$;

subjecto to

(1)* $x_1 - 2x_2+x_3 = 15$

(2)* $4x_1 + 3x_2 + x_4= 24$

(3)*$-2x_1 + 5x_2 -x_5+x_6 = 20$

so tht initial simplex table: enter image description here

From here you only need to sum M times the line of $X_6$ in the line of Z and apply the simplex method.

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