The Simplex Method: Maximization: Simplex Method. The Simplex Method Was Developed by George Dantzig in 1946. It Provides

THE SIMPLEX METHOD: MAXIMIZATION
For linear programming problems involving two variables, the graphical solution method is
convenient to use. However, for problems involving more than two variables or problems
involving a large number of constraints, it is better to use the solution method that is called the
simplex method. The simplex method was developed by George Dantzig in 1946. It provides
us with a systematic way of examining the vertices of the feasible region to determine the
optimal value of the objective function.
We introduce this method with a suitable example as below:
Suppose we want to find the maximum value of where and subject to the following constraints.
Maximize Z= 300x1 +200x2 Subject to: 5x1 +2x2 ≤ 180; 3x1 +3x2 ≤ 135 and x1, x2 ≥ 0
Solution:
Since the left-hand side of each inequality is less than or equal to the right-hand side, there must
exist nonnegative slack variables s1 and s2 that can be added to the left side of each equation to
produce the following system of linear equations in standard form.
Maximize Z= 300x1 +200x2 + 0s1+ 0s2

Subject to: 5x1 + 2x2 + s1 + 0s2 =180;
3x1 +3x2 +0 s1 + s2 = 135
and x1, x2 , s1, s2 ≥ 0
The initial basic feasible solution is given by s1 = 180, s2 = 135 (x1= x2=0, non-basic)
Initial Iteration:
Table No.1
Cj 300 200 0 0
CB YB XB X1 X2 S1 S2 ϴ=Min
X Bi
aij
0 S1 180 (5)* 2 1 0 180/5=36*
0 S2 135 3 3 0 1 135/3=45
Zj–Cj 0 -300 -200 0 0
Work Done for Table No.1:

The values of (Z j – C j) = (CB aj – C j) are calculated as below:
(Z 1 – C 1) = (0 0)
(53) -300= (0 0)–300=-300
(Z 2 – C 2) = (0 0)
(23) -200= (0 0)–200=-200
1
(Z 1 – C 1) = (0 0)
( 0) -0= (0 0)–0=0
(Z 1 – C 1) = (0 0)
(01 )
-0= (0 0)–0=0
Since there are some (Z j – C j) <0, the current basic feasible solution is not optimal. Here (Z j –
C j) = -300 is the most negative, the corresponding non basic variable X 1 will enter the basis in
Table No.2, then the column corresponding to this variable X 1 is called the key column or pivot
column.
The ratio ϴ=Min {180/5, 135/3} = Min {36, 45} =36 that corresponding to the variable S 1, is
called the key row or pivot row. The intersection of the key column and the key row is 5 which is
key element or pivot element. Moreover S1 is the leaving variable.
First Iteration: Introduce X1 and drop S1
Table No.2
Cj 300 200 0 0 X Bi
CB YB XB X1 X2 S1 S2 ϴ=Min aij
300 X1 36 1 2/5 1/5 0 36×(5/2)=90
0 S2 27 0 (9/5)* -3/5 1 27×(5/9)=15*
Zj–Cj 10,800 0 -80 60 0

New pivot equation= Old pivot equation÷ pivot element
= (180 5 2 1 0) ÷ 5 = (36 1 2/5 1/5 0)
New S2 equation= Old S2 equation- (Corresponding column coefficient) ×New pivot equation
= (135 3 3 0 1) -3(36 1 2/5 1/5 0) = (27 0 9/5 -3/5 1)
New (Z j – C j) equation
= Old (Z j – C j) equation- (Corresponding column coefficient) ×New pivot equation
= (0 -300 -200 0 0) – (-300) (36 1 2/5 1/5 0) = (10800 0 9/5 -3/5 1)

Second Iteration: Introduce X2 and drop S2
Table No.3
Cj 300 200 0 0
CB YB XB X1 X2 S1 S2
300 X1 30 1 0 1/3 -2/9
200 X2 15 0 1 -1/3 5/9
Zj–Cj 12000 0 0 100/3 400/9
New pivot equation= Old pivot equation÷ pivot element
= (27 0 9/5 -3/5 1) ÷ 9/5 = (15 0 1 -1/3 5/9)
New X1 equation= Old X1equation- (Corresponding column coefficient) ×New pivot equation
= (36 1 2/5 1/5 0) – (2/5) (15 0 1 -1/3 5/9) = (30 1 0 1/3 -2/9)
New (Z j – C j) equation
= Old (Z j – C j) equation- (Corresponding column coefficient) ×New pivot equation
= (10800 0 -80 60 0) – (-80) (15 0 1 -1/3 5/9)

= (12000 0 0 0 100/3 400/9)
Since all (Z j – C j) ≥ 0, the current basic feasible solution is feasible. So that the optimal
solution is Max. Z= 12000 and X1=30, X2=15
Assignments (home works):

1. An automobile manufacturer makes automobiles and trucks in factory that divided into
two shops. Shop A, which performs the basic assembly operations must works 5 man-
days on each trucks but 2 man days on each automobile. Shop B, which performs
finishing operations must work 3 man days for each truck or mobile that it produces.
Because of men and machine limitations shop A has 180 man-days per week available
while shop B has 135 man-days per week. If the manufacturer desires to make a profit of
Tk.300 on each truck and Tk.200 on each automobile, how many of each should produce
to maximize the profit? Formulate the problem in L.P.P and solve it by simplex method.
2. Show the relationship between primal and dual problems.
3. How would you explain shadow price regarding primal and dual problems.

The Simplex Method: Maximization: Simplex Method. The Simplex Method Was Developed by George Dantzig in 1946. It Provides

Uploaded by

Copyright:

Available Formats

The Simplex Method: Maximization: Simplex Method. The Simplex Method Was Developed by George Dantzig in 1946. It Provides

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

The Simplex Method: Maximization: Simplex Method. The Simplex Method Was Developed by George Dantzig in 1946. It Provides

Uploaded by

Copyright:

Available Formats

THE SIMPLEX METHOD: MAXIMIZATION

Maximize Z= 300x1 +200x2 + 0s1+ 0s2

Work Done for Table No.1:

Work Done for Table No.2:

= Old (Z j – C j) equation- (Corresponding column coefficient) ×New pivot equation

= (0 -300 -200 0 0) – (-300) (36 1 2/5 1/5 0) = (10800 0 9/5 -3/5 1)

= Old (Z j – C j) equation- (Corresponding column coefficient) ×New pivot equation

= (10800 0 -80 60 0) – (-80) (15 0 1 -1/3 5/9)

Assignments (home works):

You might also like