Question

Find the solution to the following problem MAXZ=2x1 +20x2 –10x3

subject to

2x1 +20x2 +4x3 ≤15

6x1 +15x2 +6x3 ≤20

5x1 +3x3 ≤13

and x1, x2, x3 ≥ 0 x1, x2, x3 = integer

Answer 1

Answer: As no specific information is mentioned in the question, we will solve the given Integer LP model by applying the following steps of Integer Simplex (Gomory's cutting plane method):

We are given:

Step 1: The problem is converted to canonical form by adding slack, surplus and artificial variables as applicable

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
3. As the constraint-3 is of type '≤' we should add slack variable S3

After introducing surplus, artificial variables:

:

Step 2: Prepare the first Iteration table as mentioned below:

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

Step 3: Prepare the second Iteration table as mentioned below:

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= 2 (0) + 20 (0.75) - 10 (0) = 15

Here, as well the values of decision variables are non-integer.. Hence, move to the next step.

Step 4: Prepare the first iteration table for integer solution:

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. The new table so obtained is:

Minimum negative XB is -0.75 and its row index is 4. 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

Step 5: Prepare the second iteration table for integer solution:

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

Step 6: Prepare the third iteration table for integer solution:

Minimum negative XB is -3.6667 and its row index is 3. So, the leaving basis variable is S3.
Maximum negative ratio is -0.4 and its column index is 5. So, the entering variable is S2.
∴ The pivot element is -0.8333.
Entering =S2, Departing =S3, Key Element =-0.8333

Step 7: Prepare the fourth iteration table for integer solution:

Since all Zj-Cj≥0

Hence, non-integer optimal solution is arrived with value of variables as :
x1=2.6, x2=0, x3=0

Max Z= 2 (2.6) + 20 (0) - 10 (0) = 5.2

Here, as well the values of decision variables are non-integer.. Hence, move to the next step.

Step 8: Again, prepare the first iteration table for integer solution:

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

2.6=1x1+0.6x3+0.2S3
(2+0.6)=(1+0)x1+(0+0.6)x3+(0+0.2)S3
The fractional cut will become
-0.6=Sg2-0.6x3-0.2S3→ (Cut-2)
Adding this additional constraint at the bottom of optimal simplex table. The new table so obtained is:

Minimum negative XB is -0.6 and its row index is 5. So, the leaving basis variable is Sg2.
Maximum negative ratio is -2 and its column index is 6. So, the entering variable is S3.
∴ The pivot element is -0.2.
Entering =S3, Departing =Sg2, Key Element =-0.2

Step 9: Again, prepare the second iteration table for integer solution:

Since all Zj-Cj≥0

Hence, an integer optimal solution arrives with the value of variables as :
x1=2, x2=0, x3=0

Max Z= 2 (2) + 20 (0) - 10(0) = 4

(Note: The integer optimal solution found after 2-cuts.)