Find the Maximum value using Big M method (algorithm)

linear programmingsimplexstatistics

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.

enter image description here

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

  1. Row #2 = $-3 \cdot$ Row #1+ Row #2
  2. Row #3 = $-3 \cdot$ Row #1+ Row #3
  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.

enter image description here

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

  1. Row #1 = $-\frac{1}{2} \cdot$ Row #3 + Row #1
  2. Row #2 = $-2.5 \cdot$ Row #3 + Row #2
  3. 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.

enter image description here

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:

enter image description here

$A_1, A_2, A_3$ - basic variables.

Related Question