Answer to Question #256030 in Algorithms for Jitendra Solanki

Question

Solve the Integer LP problem using the GOMORY'S cutting plane method. Maximize Z = 2Y1+ 20Y2-10Y3 subject to the constraints (0) 2Y1+20Y2+4Y3 ≤ 15, (ii) 6Y1+ 20Y2+4Y3=201 and Y1, Y2, Y3 20 and are integers.

Answer 1

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 S1

2.As the constraint-2 is of type '≤' we should add slack variable S2

After introducing slack variables

Max Z=2x1+20x2-10x3+0S1+0S2

subject to

2x1+20x2+4x3+S1=15

6x1+20x2+4x3+S2=20

and x1,x2,x3,S1,S2≥0

after iteration 1:

Negative minimum Zj-Cj is -20 and its column index is 2. So, the entering variable is x2.

Minimum ratio is 0.75 and its row index is 1. So, the leaving basis variable is S1.

∴ The pivot element is 20.

Entering =x2, Departing =S1, Key Element =20

after iteration 2:

Since all Zj-Cj≥0

Hence, non-integer optimal solution is arrived with value of variables as :

x1=0,x2=0.75,x3=0

Max Z=15

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

0.75=0.1x1+1x2+0.2x3+0.05S1

(0+0.75)=(0+0.1)x1+(1+0)x2+(0+0.2)x3+(0+0.05)S1

The fractional cut will become

-0.75=Sg1-0.1x1-0.2x3-0.05S1→ (Cut-1)

Adding this additional constraint at the bottom of optimal simplex table.

Minimum negative XB is -0.75 and its row index is 3. So, the leaving basis variable is Sg1.

Maximum negative ratio is 0 and its column index is 1. So, the entering variable is x1.

∴ The pivot element is -0.1.

Entering =x1, Departing =Sg1, Key Element =-0.1

Minimum negative XB is -25 and its row index is 2. So, the leaving basis variable is S2.

Maximum negative ratio is -0.3333 and its column index is 4. So, the entering variable is S1.

∴ The pivot element is -3.

Entering =S1, Departing =S2, Key Element =-3

after iteration 3:

Since all Zj-Cj≥0

Hence, non-integer optimal solution is arrived with value of variables as :

x1=3.3333,x2=0,x3=0

Max Z=6.6667

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

3.3333=1x1+0.6667x3+0.1667S2-3.3333Sg1

(3+0.3333)=(1+0)x1+(0+0.6667)x3+(0+0.1667)S2+(-4+0.6667)Sg1

The fractional cut will become

-0.3333=Sg2-0.6667x3-0.1667S2-0.6667Sg1→ (Cut-2)

Adding this additional constraint at the bottom of optimal simplex table.

Minimum negative XB is -0.3333 and its row index is 4. So, the leaving basis variable is Sg2.

Maximum negative ratio is -2 and its column index is 5. So, the entering variable is S2.

∴ The pivot element is -0.1667.

Entering =S2, Departing =Sg2, Key Element =-0.1667

Since all Zj-Cj≥0

Hence, integer optimal solution is arrived with value of variables as :

x1=3,x2=0,x3=0

Max Z=6

The integer optimal solution found after 2-cuts.