Optimization Technique LAB
ASSIGNMENT 5
First, follow the steps of the simplex method of this example and solve one
problem manually. Then modify Assignment 4 code for the general simplex
method and upload it in Moodle.
Example. Max. z = 3x1 + 2x2 + 5x3 , subject to the constraints:
x1 + 2x2 + x3 ≤ 430, 3x1 + 2x3 ≤ 460, x1 + 4x2 ≤ 420, and x1 , x2 , x3 ≥ 0.
This problem is suitable for the Simplex method since all variables are posi-
tive, constraints are less than equal to type and all bj are positive.
Convert this to standard form:
Standard form;
M aximize 3x1 + 2x2 + 5x3
subject to
x1 + 2x2 + x3 + x4 = 430
3x1 + 2x3 + x5 = 460
x1 + 4x2 x6 = 420
x1 , x2 , x3 , x4 , x5 , x6 ≥ 0 Write the initial table as in Assignment 4. Calculate
all ∆j and objective value z = CBT XB
Initial table:
∆1 = −3, ∆2 = −2, ∆3 = −5, ∆4 = 0, ∆5 = 0, ∆6 = 0
The basic feasible solution at this stage is (x1 , x2 , x3 , x4 , x5 , x6 ) = (0, 0, 0, 430, 460, 420)
The objective value is:z = XBT CB = 0
Basis=(x4 , x5 , x6 )
All ∆j are not positive.
Hence optimal solution is not reached. We have to move to the next iteration
as follows.
Select the column corresponding to the most negative ∆j . Let the most neg-
ative value occur corresponding to Xk column. Here, most negative ∆j = −5
1
3 2 5 0 0 0
Basic V ar CB XB X1 X2 X3 X4 X5 X6 XB /Xk
x4 0 430 1 2 1 1 0 0 430/1
x5 0 460 3 0 2 0 1 0 460/2
x6 0 420 1 4 0 0 0 1 xxxx
x1 = x2 = x3 = 0 z = XBT CB = 0 −3 −2 −5 0 0 0
Table 1: Simplex Table
occurs corresponding to X3 column. This column is known as the pivot col-
umn.
Divide the column XB by the pivot column componentwise corresponding to
those components of the pivot column which has a strictly positive quantity.
Then consider it’s minimum. This is known as the minimum ratio rule. Here
we have:
min{430/1, 460/2} = 460/2. The minimum ratio occurs at 2nd row. This
row is known as the pivot row.
Pivot row corresponds to x5 variable and Pivot column corresponds to x3
variable.
Decision: x5 will be removed from the basis and x3 will enter into the basis.
Their intersecting element is known as the pivot element. Here the pivot
element is 2.
Using the pivot element and pivot row, modify the table using row operation
so that new basis can be accommodated. In general, this can be done as
follows:
Consider
all the columns X B , X 1 , X2 , ...Xn+m
xB1 p1j
xB2 p2j
XB = .. and Xj = .. , j = 1, 2, ..., m + n.
.. ..
xBm pmj
If s row is the pivot row and k th column is the pivot column then psk is the
th
pivot element. In the new table,
pij /psk f or i = s, j = 1, 2, ..., n + m
pij →
pij − (psj /psk )pik f or i 6= s, j = 1, 2, ..., n + m
and
xBi /psk f or i = s
xB i →
xBi − (xBs /psk )pik f or i =
6 s
As a result of this transformation, xs will be removed from the basis and xk
will enter into the basis.
1 1 − (3/2).1 −1/2
In our example, X1 = 3 → 3/2 = 3/2
1 1 − (3/2).0 1
2 2 − (0/2).1 2
X2 = 0 → 0/2 = 0
4 4 − (0/2).0 4
2
1 1 − (2/2).1 0
X3 = 2 →
2/2 = 1 ( this is the new basis vector)
0 0 − (2/2).0 0
1 1 − (0/2).1 1
X4 = 0 → 0/2 = 0
0 0 − (0/2).0 0
0 0 − (1/2).1 −1/2
X5 = 1 →
1/2 = 1/2 (this is no more a basis vector)
0 0 − (1/2).0 0
0 0 − (0/2).0 0
X6 = 0 →
0/2 = 0
1 1 − (0/2).1 1
430 430 − (460/2).1 200
XB = 460 → 460/2 = 230
420 420 − (0/2).0 420
These can be summarized in a table as follows: Modified table(Iteration 2):
All ∆j are not positive.
3 2 5 0 0 0
Basic V ar CB XB X1 X2 X3 X4 X5 X6 XB /Xk
x4 0 200 −1/2 2 0 1 -1/2 0
x3 5 230 3/2 0 1 0 1/2 0
x6 0 420 1 4 0 0 0 1
T
x1 = x2 = x5 = 0 z = XB CB = 1150 9/2 −2 0 0 5/2 0
Table 2: Iteration 2
Hence optimal solution is not reached. We have to move to the next iteration
The basic feasible solution at this stage is (x1 , x2 , x3 , x4 , x5 , x6 ) = (0, 0, 230, 200, 0, 420)
The objective value is:z = XBT CB = 1150
Basis=(x4 , x3 , x6 )
Similarly do other iterations. The complete simplex table is :
3
cj → 3 2 5 0 0 0
Basic Variables CB XB X1 X2 X3 X4 X5 X6 Min Ratio
(XB /Xk )
x4 0 430 1 2 1 1 0 0 430/1
← x5 0 460 3 0 2 0 1 0 460/2 ←
x6 0 420 1 4 0 0 0 1 −
x1 = x2 = x3 = 0 z=0 −3 −2 −5∗ 0 0 0 ← ∆j
↑ ↓
← x4 0 200 −1/2 2 0 1 −1/2 0 200/2 ←
→ x3 5 230 3/2 0 1 0 1/2 0 −
x6 0 420 1 4 0 0 0 1 420/4
x1 = x2 = x5 = 0 z = 1150 9/2 −2∗ 0 0 5/2 0 ← ∆j
↑ ↓
→ x2 2 100 −1/4 1 0 1/2 −1/4 0
x3 5 230 3/2 0 1 0 1/2 0
x6 0 20 2 0 0 −2 1 1
x1 = s 4 = x5 = 0 z = 1350 4 0 0 1 2 0 ← ∆j ≥ 0
Since all ∆j ≥ 0, the solution is: x1 = 0, x2 = 100, x3 = 230, max z=1350.
ASSIGNMENT 5(SIMPLEX METHOD CONTINUED)
Q1. Solve the following LPP by the simplex method manually. Show the
results in tabular form. At every iteration find the basic feasible solution,
basic variables, nonbasic variables, objective value, pivot row, pivot column,
and pivot element with its value.
Maximize x1 + 2x2 + x3
subject to
2x1 + x2 − x3 ≤ 2,
−2x1 + x2 − 5x3 ≥ −6,
4x1 + x2 + x3 ≤ 6, xj ≥ 0
Ans: Maximum value:10
Optimal solution: (x1 , x2 , x3 ) = (0, 4, 2)
Q2 . Modify your code for Assignment 4 and develop code for the gen-
eral simplex method to solve a linear programming problem.
The following are the key points of the simplex method code.
• Check if the problem is suitable for the simplex method or not.(unrestricted
variables should be taken care )
• Convert the problem to standard form.
• Write the initial table,CB , xB , cj and ∆j for all j.This is Iteration 1.
4
• Declare the basic feasible solution and objective value at Iteration 1.
• If all ∆j ≥ 0 then this basic feasible solution is the optimal solution
and the corresponding objective value is the optimal value. Otherwise,
change the table as explained in the example.
• Continue the process until all ∆j are positive.
OUTPUT:
• Total number of iterations=–
• at every iteration
1. Basic feasible solution—
2. Basic variables—
3. Nonbasic variables—
4. ∆j for all j
5. Pivot element and it’s value—–
6. Incoming variable—-
7. outgoing variable—–
8. Minimum ratio—–
9. objective value—-
• Optimal solution—
• Optimal value—–
• Values of ∆j
NOTE: Try to complete it by 5 PM today and upload it in Moodle. If you
are not able to complete then you will upload it in the next lab class. Moodle
will be closed at 5 PM and will be opened in the next class.
