Operations Research Simplified produced by www.universalteacher.com

Simplex Method

The Big M Method

Example 2

Maximize z = -4x₁ - 2x₂

subject to

3x₁ + x₂ ³ 27
x₁ + x₂ ³ 21
x₁ + 2x₂ ³ 30

x₁, x₂ ³ 0

Solution.

By introducing surplus and artificial variables, the standard form of LPP becomes

Maximize z = -4x₁ - 2x₂ + 0x₃+ 0x₄+ 0x₅– MA₁ – MA₂ – MA₃

3x₁ + x₂ - x₃+ A₁ = 27
x₁ + x₂ - x₄+ A₂ = 21
x₁ + 2x₂ - x₅+ A₃ = 30

x₁ ,x₂, x₃, x₄, x₅, A₁, A₂ ³ 0

Where:
x₄ and x₅ are surplus variables
A₁ and A₂ are artificial variables.

Table 1

	c_j	-4	-2	0	0	0	–M	–M	–M
c_B	Basic variables B	x₁	x₂	x₃	x₄	x₅	A₁	A₂	A₃	Solution values b (= X_B)
–M	A₁	3	1	-1	0	0	1	0	0	27
-M	A₂	1	1	0	-1	0	0	1	0	21
–M	A₃	1	2	0	0	-1	0	0	1	30
z_j–c_j		-5M + 4	-4M + 2	M	M	M	0	0	0

As -5M < -4M, x₁ becomes a basic variable in the next iteration
Key column = x₁ column.
Minimum (27/3, 21/1, 30/1) = 9
Key row = A₁ row
Pivot element = 3.
A1 departs and x₁enters.

Table 2

	c_j	-4	-2	0	0	0	–M	–M
c_B	Basic variables B	x₁	x₂	x₃	x₄	x₅	A₂	A₃	Solution values b (= X_B)
–4	x₁	1	1/3	-1/3	0	0	0	0	9
-M	A₂	0	2/3	1/3	-1	0	1	0	12
–M	A₃	0	5/3	1/3	0	-1	0	1	21
z_j–c_j		0	-7M/3 + 2/3	-2M/3 - 4/3	M	M	0	0

Table 3

	c_j	-4	-2	0	0	0	–M
c_B	Basic variables B	x₁	x₂	x₃	x₄	x₅	A₂	Solution values b (= X_B)
–4	x₁	1	0	-2/5	0	1/5	0	24/5
–M	A₂	0	0	1/5	-1	2/5	1	18/5
-2	x₂	0	1	1/5	0	-3/5	0	63/5
z_j–c_j		0	0	-M/5 + 6/5	M	-2M/5 + 2/5	0

Table 4

	c_j	-4	-2	0	0	0
c_B	Basic variables B	x₁	x₂	x₃	x₄	x₅	Solution values b (= X_B)
–4	x₁	1	0	-1/2	1/2	0	3
0	x₅	0	0	1/2	-5/2	1	9
-2	x₂	0	1	1/2	-3/2	0	18
z_j–c_j		0	0	1	1	0

The optimal solution is

x₁ = 3, x₂= 18
z = -4 X 3 - 2 X 18 = -48

Operations Research Contents