Cutting Plane Method

Example 2

Maximize z = x1 + 4x2

subject to
2x1 + 4x2 £ 7
5x1 + 3x2 £ 15

x1, x2 are integers ³ 0

Solution.

First, solve the above problem by applying the simplex method (try it yourself).The final simplex table is presented below.

Final Simplex Table

  
 cj 1 4 0 0
  
cB Basic variables
B		 x1 x2 x3 x4 Solution values
b (=XB)
4 x2 1/2 1 1/4 0 7/4 (1 + 3/4)
0 x4 7/2 0 -3/4 1 39/4 (9 + 3/4)
zj–cj
  
 1 0 1 0   

Taking first row as the source row, the corresponding equation is
1/2x1 + 1x2 + 1/4x3 + 0x4 = 1 + 3/4
1/2x1 + (1 + 0)x2 + (1 - 3/4)x3 = 1 + 3/4

Gomory's constraint
- (1/2x1 - 3/4x3) £ -3/4
-1/2x1 + 3/4x3 + x5 = -3/4

Table

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

Table

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

Taking second row as the source row, the corresponding equation is:
0x1 + 0x2 + 9/2x3 + 1x4 + 7x5 = 4 + 1/2
or  (4 + 1/2)x3 + (1 + 0)x4 + (7 + 0)x5 = 4 + 1/2

Gomory's constraint
-1/2x3 £ -1/2
-1/2x3 + x6 = -1/2

Table

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

In the above table, there is a negative value under XB column; therefore, apply the dual simplex method.

Final Table

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

The optimal solution is
x1 = 3, x2 = 0
z = 3 + 4 X 0 = 3

 

Operations Research Contents
   
Copyright © www.universalteacher.com