System Engineering

LESSON 3. Big M Method- Special Case

Example:

Maximize z = 2x₁ + 3x₂

Subject to

-x₁ + 2x₂≤  4
 x₁ + x₂  ≤ 6
  x₁ + 3x₂ ≤ 9

x₁, x₂ are unrestricted in sign

Solution:

Since x₁ and x₂ are unrestricted in sign, we can replace them by non-negative variables x₁^' , x₁'', x₂^' , x₂^'' .

Put x₁ = x₁^' - x₁''
      x₂ = x₂^' - x₂''

The given problem can be written as

Max. z = 2(x₁^' - x₁'') + 3(x₂^' - x₂'')

Subject to

-(x₁^' - x₁'') + 2(x₂^' - x₂'') ≤  4
 (x₁^' - x₁'') + (x₂^' - x₂'') ≤ 6
   (x₁^' - x₁'') + 3(x₂^' - x₂'') ≤ 9

Introducing slack variables

Max. z = 2x₁^' - 2x₁'' + 3x₂^' - 3x₂''

Subject to

  -x₁^' + x₁'' + 2x₂^' - 2x₂'' + x₃ = 4
     x₁^{’ -} x₁'' + x₂^'- x₂'' + x₄ = 6
   x₁^' - x₁'' + 3x₂^' - 3x₂'' + x₅ = 9

where x₃, x₄ and x₅ are slack variables

Iteration 1:

	cj	2	-2	3	-3	0	0	0
cB	Basic variables B	x1'	x1''	x2'	x2''	x3	x4	x5	Solution values b (=XB)
0	x3	-1	1	2	-2	1	0	0	4
0	x4	1	-1	1	-1	0	1	0	6
0	x5	1	-1	3	-3	0	0	1	9
zj-cj		-2	2	-3	3	0	0	0

 Key column = x₂^' column.
Minimum (4/2, 6/1, 9/3) = 2
Key row = x₃ row.
Pivot element = 2
x₃ departs and x₂^' enters.

Iteration 2:

	cj	2	-2	3	-3	0	0	0
cB	Basic variables B	x1'	x1''	x2'	x2''	x3	x4	x5	Solution values b (=XB)
3	x2'	-1/2	1/2	1	-1	1/2	0	0	2
0	x4	3/2	-3/2	0	0	-1/2	1	0	4
0	x5	5/2	-5/2	0	0	-3/2	0	1	3
zj-cj		-7/2	7/2	0	0	3/2	0	0

Iteration 3:

	cj	2	-2	3	-3	0	0	0
cB	Basic variables B	x1'	x1''	x2'	x2''	x3	x4	x5	Solution values b (=XB)
3	x2'	0	0	1	-1	1/5	0	1/5	13/5
0	x4	0	0	0	0	2/5	1	-3/5	11/5
2	x1'	1	-1	0	0	-3/5	0	2/5	6/5
zj-cj		0	0	0	0	-3/5	0	7/5

 

Iteration 4:

	cj	2	-2	3	-3	0	0	0
cB	Basic variables B	x1'	x1''	x2'	x2''	x3	x4	x5	Solution values b (=XB)
3	x2'	0	0	1	-1	0	-1/2	1/2	3/2
0	x3	0	0	0	0	1	5/2	-3/2	11/2
2	x1'	1	-1	0	0	0	3/2	-1/2	9/2
zj-cj		0	0	0	0	0	3/2	1/2

Result:

      The optimal solution is x₁^' = 9/2, x₁'' = 0, x₂^' = 3/2, x₂'' = 0.

Solution of the original problem is
                               x₁ = x₁^' - x₁'' = 9/2 - 0 = 9/2
                                x₂ = x₂^' - x₂'' = 3/2 - 0 = 3/2
                               Max z = 2 x 9/2 + 3 x 3/2 = 27/2.