Task: I need to write a program, which should calculate the maximum value of the function using Big M method.
Here is the problem:
$Z(x_1,x_2)=4x_1+3x_2 \rightarrow max$
Subject to:
$
\begin{cases}
2x_1+x_2 \ge 10 \\
3x_1+4x_2 \ge 30 \\
3x_1+8x_2 \ge 42
\end{cases}
$
Here is what I've done:
$Z=4x_1+3x_2+0S_1+0S_2+0S_3-MA_1-MA_2-MA_3$
$-4x_1-3x_2-0S_1-0S_2-0S_3+MA_1+MA_2+MA_3+Z=0$
Iteration #1
$S_1, S_2, S_3$ – base variables.
$S_1$ is now leaving base variables and $X_1$ is entering them.
Pivot is $[2]$, dividing row #1 by 2
New Row #1 = $|5|1|0.5|0.5|0.5|0|0|0|0|0|$
Performing following row operations:
- Row #2 = $-3 \cdot$ Row #1+ Row #2
- Row #3 = $-3 \cdot$ Row #1+ Row #3
- Row #4 = $4 \cdot$ Row #1+ Row #4
The table after this operations looks like this:
Iteration #2
$X_1, S_2, S_3$ – base variables.
$S_3$ is now leaving base variables and $X_2$ is entering them.
Pivot is $[6.5]$, dividing row #1 by $6.5$
New Row #3 = $|4.15|0|1|-0.23|-0.23|0|0|0.15|0.15|0|$
Performing following row operations:
- Row #1 = $-\frac{1}{2} \cdot$ Row #3 + Row #1
- Row #2 = $-2.5 \cdot$ Row #3 + Row #2
- Row #4 = $1 \cdot$ Row #3 + Row #4
The table after this operations looks like this:
Iteration #3
$X_1, S_2, X_2$ – base variables.
Question:
Since the last row's numbers are all positive we have a solution… which is wrong. By the way this function does not even have a maximum value, but my task is to understand the algorithm of Big M method for finding the maximum value.
Am I constructing the tables correctly? If not, what am i doing wrong here?
Best Answer
The correct way to create initial table:
$Z(x_1,x_2)=4x_1+3x_2 \rightarrow max$
$ \begin{cases} 2x_1+x_2 \ge 10 \\ 3x_1+4x_2 \ge 30 \\ 3x_1+8x_2 \ge 42 \end{cases} $
$(1): 2x_1+x_2-s_1+a_1=10$
$(2): 3x_1+4x_2-s_2+a_2=30$
$(3): 3x_1+8x_2-s_3+a_3=42$
$z=4x_1+3x_2+0S_1+0S_2+0S_3-MA_1-MA_2-MA_3$
$z-4x_1-3x_2+MA_1+MA_2+MA_3=0$
We need to multiply each of the $1,2,3$ equations by $-M$ and sum them with $z$:
$(1)\cdot -M = 2x_1+x_2-s_1+a_1=10$
$(2)\cdot -M = 3x_1+4x_2-s_2+a_2=30$
$(3)\cdot -M = 3x_1+8x_2-s_3+a_3=42$
After sum with $z$:
$z-8Mx_1-4x_1-13Mx_2-3x_2+Ms_1+Ms_2+Ms_3=-82M$
$z+x_1(-8M-4)+x_2(-13M-3)+Ms_1+Ms_2+Ms_3=-82M$
Let's create first table:
$A_1, A_2, A_3$ - basic variables.