Home > Operation Research calculators > Simplex method example

6. Integer simplex method (gomory's cutting plane method) example ( Enter your problem )
 Algorithm & Example-1 (Pure integer)Example-2 (Mixed integer) Other related methods

2. Example-2 (Mixed integer)

This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then Submit Here

Find solution using integer simplex method (Gomory's cutting plane method)
MAX Z = x1 + x2
subject to
3x1 + 2x2 <= 5
x2 <= 2
and x2 >= 0 and x1 non-negative integers

Solution:
Problem is
 Max Z =   x_1  +   x_2
subject to
  3 x_1  +  2 x_2 ≤ 5   x_2 ≤ 2
and x_1,x_2 >= 0; x_1 non-negative integers

The problem is converted to canonical form by adding slack, surplus and artificial variables as appropiate

1. As the constraint-1 is of type '<=' we should add slack variable S_1

2. As the constraint-2 is of type '<=' we should add slack variable S_2

After introducing slack variables
 Max Z =   x_1  +   x_2  +  0 S_1  +  0 S_2
subject to
  3 x_1  +  2 x_2  +   S_1 = 5   x_2  +   S_2 = 2
and x_1,x_2,S_1,S_2 >= 0

 Iteration-1 C_j 1 1 0 0 B C_B X_B x_1 Entering variable x_2 S_1 S_2 MinRatio (X_B)/(x_1) S_1 Leaving variable 0 5 (3)  (pivot element) 2 1 0 (5)/(3)=1.6667-> S_2 0 2 0 1 0 1 --- Z=0 0=Z_j=sum C_B X_B Z_j Z_j=sum C_B x_j 0 0=0xx3+0xx0Z_j=sum C_B x_1 0 0=0xx2+0xx1Z_j=sum C_B x_2 0 0=0xx1+0xx0Z_j=sum C_B S_1 0 0=0xx0+0xx1Z_j=sum C_B S_2 C_j-Z_j 1 1=1-0uarr 1 1=1-0 0 0=0-0 0 0=0-0

Positive maximum C_j-Z_j is 1 and its column index is 1. So, the entering variable is x_1.

Minimum ratio is 1.6667 and its row index is 1. So, the leaving basis variable is S_1.

:. The pivot element is 3.

Entering =x_1, Departing =S_1, Key Element =3

R_1(new)= R_1(old)-: 3

R_2(new)= R_2(old)

 Iteration-2 C_j 1 1 0 0 B C_B X_B x_1 x_2 Entering variable S_1 S_2 MinRatio (X_B)/(x_2) x_1 1 5/3 5/3=5-:3R_1(new)= R_1(old)-: 3 1 1=3-:3R_1(new)= R_1(old)-: 3 2/3 2/3=2-:3R_1(new)= R_1(old)-: 3 1/3 1/3=1-:3R_1(new)= R_1(old)-: 3 0 0=0-:3R_1(new)= R_1(old)-: 3 (5/3)/(2/3)=2.5 S_2 Leaving variable 0 2 2=2R_2(new)= R_2(old) 0 0=0R_2(new)= R_2(old) (1) 1=1 (pivot element)R_2(new)= R_2(old) 0 0=0R_2(new)= R_2(old) 1 1=1R_2(new)= R_2(old) (2)/(1)=2-> Z=5/3 5/3=1xx5/3Z_j=sum C_B X_B Z_j Z_j=sum C_B x_j 1 1=1xx1+0xx0Z_j=sum C_B x_1 2/3 2/3=1xx2/3+0xx1Z_j=sum C_B x_2 1/3 1/3=1xx1/3+0xx0Z_j=sum C_B S_1 0 0=1xx0+0xx1Z_j=sum C_B S_2 C_j-Z_j 0 0=1-1 1/3 1/3=1-(2/3)uarr -1/3 -1/3=0-(1/3) 0 0=0-0

Positive maximum C_j-Z_j is 1/3 and its column index is 2. So, the entering variable is x_2.

Minimum ratio is 2 and its row index is 2. So, the leaving basis variable is S_2.

:. The pivot element is 1.

Entering =x_2, Departing =S_2, Key Element =1

R_2(new)= R_2(old)

R_1(new)= R_1(old)- 2/3 R_2(new)

 Iteration-3 C_j 1 1 0 0 B C_B X_B x_1 x_2 S_1 S_2 MinRatio x_1 1 1/3 1/3=5/3-2/3xx2R_1(new)= R_1(old)- 2/3 R_2(new) 1 1=1-2/3xx0R_1(new)= R_1(old)- 2/3 R_2(new) 0 0=2/3-2/3xx1R_1(new)= R_1(old)- 2/3 R_2(new) 1/3 1/3=1/3-2/3xx0R_1(new)= R_1(old)- 2/3 R_2(new) -2/3 -2/3=0-2/3xx1R_1(new)= R_1(old)- 2/3 R_2(new) x_2 1 2 2=2R_2(new)= R_2(old) 0 0=0R_2(new)= R_2(old) 1 1=1R_2(new)= R_2(old) 0 0=0R_2(new)= R_2(old) 1 1=1R_2(new)= R_2(old) Z=7/3 7/3=1xx1/3+1xx2Z_j=sum C_B X_B Z_j Z_j=sum C_B x_j 1 1=1xx1+1xx0Z_j=sum C_B x_1 1 1=1xx0+1xx1Z_j=sum C_B x_2 1/3 1/3=1xx1/3+1xx0Z_j=sum C_B S_1 1/3 1/3=1xx(-2/3)+1xx1Z_j=sum C_B S_2 C_j-Z_j 0 0=1-1 0 0=1-1 -1/3 -1/3=0-(1/3) -1/3 -1/3=0-(1/3)

Since all C_j-Z_j <= 0

Hence, non-integer optimal solution is arrived with value of variables as :
x_1=1/3,x_2=2

Max Z = 7/3

To obtain the integer valued solution, we proceed to construct Gomory's fractional cut, with the help of x_1-row as follows:

1/3= 1 x_1+1/3 S_1 -2/3 S_2

(0+1/3)=(1+0) x_1+(0+1/3) S_1+(-1+1/3) S_2

The fractional cut will become
-1/3 = Sg1 -1/3 S_1 -1/3 S_2 -> (Cut-1)

Adding this additional constraint at the bottom of optimal simplex table. The new table so obtained is

 Iteration-1 C_j 1 1 0 0 0 B C_B X_B x_1 x_2 S_1 Entering variable S_2 Sg1 x_1 1 1/3 1 0 1/3 -2/3 0 x_2 1 2 0 1 0 1 0 Sg1 Leaving variable 0 -1/3 0 0 (-1/3)  (pivot element) -1/3 1 Z=7/3 7/3=1xx1/3+1xx2Z_j=sum C_B X_B Z_j Z_j=sum C_B x_j 1 1=1xx1+1xx0+0xx0Z_j=sum C_B x_1 1 1=1xx0+1xx1+0xx0Z_j=sum C_B x_2 1/3 1/3=1xx1/3+1xx0+0xx(-1/3)Z_j=sum C_B S_1 1/3 1/3=1xx(-2/3)+1xx1+0xx(-1/3)Z_j=sum C_B S_2 0 0=1xx0+1xx0+0xx1Z_j=sum C_B Sg1 C_j-Z_j 0 0=1-1 0 0=1-1 -1/3 -1/3=0-(1/3) -1/3 -1/3=0-(1/3) 0 0=0-0 "Ratio"=(C_j-Z_j)/(Sg1,j)and Sg1,j<0 --- Sg1,j=0; which is not <0 --- Sg1,j=0; which is not <0 1 1=(-1/3)/(-1/3)"Ratio"=(C_j-Z_j)/(Sg1,j)uarr 1 1=(-1/3)/(-1/3)"Ratio"=(C_j-Z_j)/(Sg1,j) --- Sg1,j=1; which is not <0

Minimum negative X_B is -1/3 and its row index is 3. So, the leaving basis variable is Sg1.

Minimum positive ratio is 1 and its column index is 3. So, the entering variable is S_1.

:. The pivot element is -1/3.

Entering =S_1, Departing =Sg1, Key Element =-1/3

R_3(new)= R_3(old)xx-3

R_1(new)= R_1(old)- 1/3 R_3(new)

R_2(new)= R_2(old)

 Iteration-2 C_j 1 1 0 0 0 B C_B X_B x_1 x_2 S_1 S_2 Sg1 x_1 1 0 0=1/3-1/3xx1R_1(new)= R_1(old)- 1/3 R_3(new) 1 1=1-1/3xx0R_1(new)= R_1(old)- 1/3 R_3(new) 0 0=0-1/3xx0R_1(new)= R_1(old)- 1/3 R_3(new) 0 0=1/3-1/3xx1R_1(new)= R_1(old)- 1/3 R_3(new) -1 -1=(-2/3)-1/3xx1R_1(new)= R_1(old)- 1/3 R_3(new) 1 1=0-1/3xx(-3)R_1(new)= R_1(old)- 1/3 R_3(new) x_2 1 2 2=2R_2(new)= R_2(old) 0 0=0R_2(new)= R_2(old) 1 1=1R_2(new)= R_2(old) 0 0=0R_2(new)= R_2(old) 1 1=1R_2(new)= R_2(old) 0 0=0R_2(new)= R_2(old) S_1 0 1 1=(-1/3)xx(-3)R_3(new)= R_3(old)xx-3 0 0=0xx(-3)R_3(new)= R_3(old)xx-3 0 0=0xx(-3)R_3(new)= R_3(old)xx-3 1 1=(-1/3)xx(-3)R_3(new)= R_3(old)xx-3 1 1=(-1/3)xx(-3)R_3(new)= R_3(old)xx-3 -3 -3=1xx(-3)R_3(new)= R_3(old)xx-3 Z=2 2=1xx0+1xx2Z_j=sum C_B X_B Z_j Z_j=sum C_B x_j 1 1=1xx1+1xx0+0xx0Z_j=sum C_B x_1 1 1=1xx0+1xx1+0xx0Z_j=sum C_B x_2 0 0=1xx0+1xx0+0xx1Z_j=sum C_B S_1 0 0=1xx(-1)+1xx1+0xx1Z_j=sum C_B S_2 1 1=1xx1+1xx0+0xx(-3)Z_j=sum C_B Sg1 C_j-Z_j 0 0=1-1 0 0=1-1 0 0=0-0 0 0=0-0 -1 -1=0-1 Ratio --- --- --- --- ---

Since all C_j-Z_j <= 0

Hence, integer optimal solution is arrived with value of variables as :
x_1=0,x_2=2

Max Z = 2

The integer optimal solution found after 1-cuts.