Assignment # 02
Operation Research Lab
Course Code: IE-356L
Semester:5th
Fall 2024
Submitted by: Asif Ali
Reg No: 22pwind0741
Submitted to: Dr.Sikandar Bilal Khattak
Department of Industrial Engineering
University of Engineering and Technology
Peshawar
Question No. 1
Considering the LP Model below. Find the optimum solution by applying the two-phase method.
Minimize z = 4x 1 + x 2
3x 1 + x 2 = 3
4x 1 +3x 2 ≥6
x 1 +2x 2 ≤ 4
x1,x2≥0
SOLUTION:
To solve the given Linear Programming (LP) problem using the Two-Phase Method, follow
these steps:
Problem Formulation:
The LP problem is:
Minimize z=4x1+x2
Subject to:
1. 3x1+x2=3
2. 4x1+3x2≥6
3. x1+2x2≤4
4. x1,x2≥0
Step 1: Convert Constraints into Standard Form
1. For 3x1+x2=3 it is already an equality, no modification needed.
2. For 4x1+3x2≥6, introduce a surplus variable (s1s_1s1) and an artificial variable (A1):
4x1+3x2−s1+A1=6
3. For x1+2x2≤4, introduce a slack variable (s2): x1+2x2+s2=4
Thus, the standard form is:
Minimize z=4x1+x2
Subject to:
1. 3x1+x2=3
2. 4x1+3x2−s1+A1=6
3. x1+2x2+s2=4
4. x1,x2,s1,s2,A1≥0
Step 2: Formulate the Phase 1 Objective Function
The Phase 1 objective is to minimize the sum of artificial variables (A1A_1A1). Thus, the Phase
1 objective function is:
Minimize W=A1
The system of equations for Phase 1 is:
Minimize W=A1
Subject to:
1. 3x1+x2=3
2. 4x1+3x2−s1+A1=6
3. x1+2x2+s2=4
Step 3: Solve Phase 1
Set up the initial simplex tableau for Phase 1 and iterate to minimize W. Once the artificial
variable (A1) is removed from the basis (i.e., W=0), proceed to Phase 2.
Step 4: Solve Phase 2
Replace the Phase 1 objective function with the original objective function:
Minimize z=4x1+x2
Proceed with solving the problem using the two-phase method, including the simplex tableau
iterations. We'll break it into steps.
Phase 1: Minimize W=A1W = A_1W=A1
We start by setting up the initial simplex tableau for the Phase 1 problem:
Problem Recap (Standard Form for Phase 1):
Objective function:
Minimize W=A1
Constraints:
3x1+x2+0s1+0s2+0A1=3
4x1+3x2−s1+A1=6
x1+2x2+s2+0A1=4
Add the coefficients into the simplex tableau.
Initial Tableau (Phase 1)
Basic Variable x1 x2 s1 s2 A1 RHS
A1 4 3 −1 0 1 6
s2 1 2 0 1 0 4
x2 3 1 0 0 0 3
Row 0 (W) -4 -3 1 0 -1 -6
Iteration 1 (Phase 1)
Step 1: Choose Entering Variable
The most negative value in the objective row (W) is −4, corresponding to x1. So, x1 enters the
basis.
Step 2: Choose Leaving Variable
Compute the ratio of the RHS to the pivot column (x1):
Ratios: 6/4=1.5, 4/1=4, 3/3=1
The smallest ratio is 1, so the third row (x2) leaves the basis.
Step 3: Perform Row Operations
Perform row operations to make x1 the new basic variable. Use the pivot element (3 in the third
row, first column).
Tableau After Iteration 1 (Phase 1)
Basic Variable x1 x2 s1 s2 A1 RHS
A1 0 1 -1 0 1 4
s2 0 2 0 1 0 3
x1 1 1/3 0 0 0 1
Row 0 (W) 0 -2/3 1 0 -1 -2
Iteration 2 (Phase 1)
Step 1: Choose Entering Variable
The most negative value in the objective row (W) is −2/3 corresponding to x2. So, x2 enters the
basis.
Step 2: Choose Leaving Variable
Compute the ratio of the RHS to the pivot column (x2):
Ratios: 4/1=4, 3/2=1.5, 1/1/3=3
The smallest ratio is 1.5, so the second row (s2) leaves the basis.
Step 3: Perform Row Operations
Perform row operations to make x2 the new basic variable. Use the pivot element (2 in the
second row, second column).
Tableau After Iteration 2 (Phase 1)
Basic Variable x1 x2 s1 s2 A1 RHS
A1 0 0 -1 -1/2 1 3
x2 0 1 0 1/2 0 1.5
x1 1 0 0 -1/6 0 0.5
Row 0 (W) 0 0 1 1/3 -1 -1.5
Check for Phase 1 Completion
The objective row (W) contains no negative values, so Phase 1 is complete. The artificial
variable (A1) is removed, and W=0.
Phase 2: Minimize z=4x1+x2z
Replace the objective function with the original:
Minimize z=4x1+x2
The initial tableau for Phase 2 is:
Basic Variable x1 x2 s1 s2 RHS
s1 0 0 -1 -1/2 3
x2 0 1 0 1/2 1.5
x1 1 0 0 -1/6 0.5
Row 0 (z) -4 -1 0 0 0
Continue with Phase 2 of the simplex method to minimize z=4x1+x2
Initial Tableau (Phase 2)
Basic Variable x1 x2 s1 s2 RHS
s1 0 0 -1 -1/2 3
x2 0 1 0 1/2 1.5
x1 1 0 0 -1/6 0.5
Row 0 (z) -4 -1 0 0 0
Iteration 1 (Phase 2)
Step 1: Choose Entering Variable
The most negative coefficient in the objective row (z) is −4, corresponding to x1 So, x1 enters
the basis.
Step 2: Choose Leaving Variable
Compute the ratio of the RHS to the pivot column (x1):
Ratios: 3/0=∞ (not considered) , 1.5/0=∞ (not considered)
The smallest ratio is 0.5, so the third row (x1) leaves the basis.
Step 3: Perform Row Operations
Make x1 the new basic variable by pivoting on the element at the intersection of the third row
and the first column (pivot = 1). Normalize the pivot row and adjust the other rows.
Tableau After Iteration 1 (Phase 2)
Basic Variable x1 x2 s1 s2 RHS
s1 0 0 -1 -1/2 3
x2 0 1 0 1/2 1.5
x1 1 0 0 -1/6 0.5
Row 0 (z) 0 0 ...
Continuing Iteration 1 (Phase 2)
We will now perform the necessary row operations after making x1 the pivot.
Tableau After Iteration 1 (Phase 2)
Basic Variable x1 x2 s1 s2 RHS
s1 0 0 -1 -1/2 3
x2 0 1 0 1/2 1.5
x1 1 0 0 -1/6 0.5
Row 0 (z) 0 0 **...
Apologies for the abrupt response earlier. Let’s carefully continue from Phase 2, iteration 1,
ensuring the correct simplex row operations.
Initial Tableau (Phase 2)
Basic Variable x1 x2 s1 s2 RHS
s1 0 0 -1 -1/2 3
x2 0 1 0 1/2 1.5
x1 1 0 0 -1/6 0.5
Row 0 (z) -4 -1 0 0 0
Iteration 1 (Phase 2)
Step 1: Choose Entering Variable
The most negative coefficient in the objective row (z) is −4, corresponding to x1Thus, x1 enters
the basis.
Step 2: Choose Leaving Variable
Compute the ratio of the RHS to the pivot column (x1):
Ratios: 3/0=∞ (not considered),1.5/0=∞ (not considered),
The smallest ratio is 0.50.50.5, so the third row (x1) leaves the basis.
Step 3: Perform Row Operations
The pivot element is 1 (in the x1 column, third row). Normalize the pivot row and eliminate x1
from the other rows.
Row Operations for Tableau Update:
1. Normalize the pivot row (row 3):
Divide row 3 by 1.
2. Eliminate x1 from Row 1 (s1s_1s1) and Row 2 (x2), as well as the objective row (z).
Tableau After Iteration 1 (Phase 2)
Basic Variable x1 x2 s1 s2 RHS
s1 0 0 -1 -1/2 3
x2 0 1 0 1/2 1.5
x1 1 0 0 -1/6 0.5
Row 0 (z) 0 0 **...
Complete the row operations for Iteration 1 of Phase 2.
Row Operations to Update the Tableau
1. Normalize the Pivot Row (Row 3): The pivot element is 1 in the x1 column (Row 3).
Divide the entire row by 1 (no changes needed since it is already normalized).
2. Eliminate x1 from the Other Rows: Subtract the pivot row multiplied by the
corresponding coefficient of x1 from each row.
o For s1 (Row 1):
Subtract 0×(Pivot Row) No change to Row 1.
o For x2 (Row 2):
Subtract 0×(Pivot Row)No change to Row 2.
o For the Objective Function (z) (Row 0):
Subtract (−4)×(Pivot Row).
Tableau After Row Operations
Basic Variable x1 x2 s1 s2 RHS
s1 0 0 -1 −1/2 3
x2 0 1 0 1/2 1.5
x1 1 0 0 −1/6 0.5
Row 0 (z) 0 -1 0 −2/3 2
Check for Optimality
In the objective row (z), the most negative coefficient is −1, corresponding to x2. Thus, x2 will
enter the basis for the next iteration.
Iteration 2 (Phase 2)
Step 1: Choose Entering Variable
x2 enters the basis as it has the most negative coefficient (−1) in Row 0.
Step 2: Choose Leaving Variable
Compute the ratio of the RHS to the pivot column (x2):
Ratios: 30=∞ (not considered),1.51=1.5,0.50=∞ (not considered)
The smallest ratio is 1.5, so x2 replaces x2 in the basis (Row 2).
Step 3: Perform Row Operations
Use 1 (in Row 2, x2) as the pivot element. Normalize Row 2 and eliminate x2 from the other
rows.
Final Tableau After Iteration 2
Basic Variable x1 x2 s1 s2 RHS
s1 0 0 -1 -1/2 3
x2 0 1 0 1/2 1.5
x1 1 0 0 −1/6 0.5
Row 0 (z) 0 0
Continuing Iteration 2: Finalizing Phase 2
We’ll complete the necessary row operations to fully update the tableau after x2 enters the basis.
Updated Tableau After Iteration 2 (Final Form)
Basic Variable x1 x2 s1 s2 RHS
s1 0 0 -1 -1/2 3
x2 0 1 0 1/2 1.5
x1 1 0 0 −1/6 0.5
Row 0 (z) 0 0 0 −1/3 2.5
Check for Optimality
The objective row (z) contains no negative coefficients. Therefore, the current solution is
optimal.
Optimal Solution
From the final tableau:
x1=0.5
x2=1.5
z=4x1+x2=4(0.5)+1.5=2.5
Slack variables:
s1=3 (non-binding constraint, surplus exists)
s2=0 (binding constraint)
Final Answer
x1=0.5
x2=1.5
z=2.5
