Chapter 3

Linear Programming:
Simplex Method
 The Simplex Method requires that all constraints be expressed as equations
Mathematically.
 It is easier to solve system of linear equations than system of inequalities.
 All inequalities shall be converted into equations or in the standard form of linear
programming problem.
 Simplex Method is an iterative technique that begins with a feasible solution that is not
optimal, but serves as a starting point with the use of algebraic manipulation.
 The solution is improve until no further improvement is possible.
 Step 4:
 Standard Form is the way of expressing the constraints of a Linear Programming
problem as equalities with all variables on the left side of the equation and a constant
on the right side.
 Slack variables are variables added to constraints to convert them into equations.
 Surplus variables are variables subtracted from constraints to convert them into
equations.
 Artificial variable is a computational device used in linear programming to achieve
an initial solution to the problem.
 Step 5:
 Iteration is a simplex method which consists of the sequence of steps (row operations) performed in
moving one basic feasible solution to another.
 Simplex Tableau is a table use to keep track of the calculations made when the simplex method is
employed.
 Right-Hand-side is the column in a simplex tableau indicating the quantities of the variables is in
solution.
 Basic Variables are the variable included in a basic solution.
 Step 6:
 Optimum Column is the column or entering by choosing the most positive entry in the 𝑪𝒋 − 𝒁𝒋 row or
which has largest negative value in a minimization problem.
 Intersectional Elements are elements common to both the optimum column and the row
representing variables in the solution.
 Pivot Row is the row in the simplex tableau corresponding to the basic variables that will leave the
solution.
 Pivot is the element of the simplex tableau that is in both the pivot row and the optimum column.
 Pivoting is the process of going from one simplex tableau to the next.
3.1 Maximization Problem
Example 3.1:
A tailor has the following materials available: 18 square meter cotton, 20 square meter
silk, 5 square meter wool. A gown requires the following: 3 square meters cotton. 2
square meters silk and 1 square meters wool. A suit requires the following: 2 square
meters cotton, 4 square meters silk. If a gown sells for P1,200 and a suit for P1,600,
how many of each garments should the tailor make to obtain the maximum amount of
money?
Solution:
In order to solve a linear programming using simplex method, it is necessary to follow
the following steps:
Step 1: Represent the unknown in the problem.
Let 𝑥1 be the number of gowns and
𝑥2 𝑏𝑒 𝑡ℎ𝑒 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑠𝑢𝑖𝑡𝑠
Step 2: Tabulate the data about the facts (if necessary)
 Materials Gown (x1) Suit (x2) Available
Cotton 3 2 18
Silk 2 4 20
Wool 1 0 5
Profit 1200 1600
Step 3: Formulate the objective function and constraints by restarting the information in
mathematical form.
The objective function is:
Maximize: Zj = 1200x1 + 1600x2
The constraints are:
Structural
3x1 + 2x2  18 Cotton
2x1 + 4x2  20 Silk
x1  5 Wool
Non-negativity
x1, x2  0
Step 4: Convert the inequality in structural constraints to equation by adding a stacks variable
in a “less-than-or-equal-to” constraints.
Rules fro preparing constraints in simplex method

Objective Function Coefficients

Constraints Adjustments
Maximization Minimization
 Add a slack variable 0 0
= Add a artificial variables -M M
Subtract a surplus variable and 0 0

add an artificial variable -M M

Note: M represents a very large number

Let Sn represents the stack variables
Maximize: Zj = 1200X1 + 1600X2 + 0S1 + 0S2 + 0S3
 Subject to:
3x1 + 2x2 + S1 = 18
2x1 + 4x2 + S2 = 20
x1+ S3 =5
x1, x2, S1, S2, S3  0
Step 5: Enter the constraints coefficients in the initial tableau and calculate Zj and Cj – Zj.
Tableau 1
Basic Right-Hand 1200 1600 0 0 0
𝑪𝒋
Variables Side 𝑿𝟏 𝑿𝟐 𝑺𝟏 𝑺𝟐 𝑺𝟑
0 𝑺𝟏 18 3 2 1 0 0
0 𝑺𝟐 20 2 4 0 1 0
0 𝑺𝟑 5 1 0 0 0 1
𝒁𝒋
𝑪𝒋 − 𝒁𝒋
The 𝑍𝑗 row is computed using the formula:
𝒁𝒋 = σ𝒏𝒋−𝟏 𝑪𝒋 𝑹𝒋
𝒁𝒋 = (0)(18,3,2,1,0,0) + (0)(20,2,4,0,1,0) + (0)(5,1,0,0,0,1)
= (0, 0, 0, 0, 0, 0) + (0, 0, 0, 0, 0, 0) + (0, 0, 0, 0, 0, 0)
= (0, 0, 0, 0, 0, 0)
𝑪𝒋 − 𝒁𝒋 = 𝟏𝟐𝟎𝟎, 𝟏𝟔𝟎𝟎, 𝟎, 𝟎, 𝟎 − 𝟎, 𝟎, 𝟎, 𝟎, 𝟎 = (𝟏𝟐𝟎𝟎, 𝟏𝟔𝟎𝟎, 𝟎, 𝟎, 𝟎)
Tableau 1

Basic Right-Hand 1200 1600 0 0 0

𝑪𝒋
Variables Side 𝑿𝟏 𝑿𝟐 𝑺𝟏 𝑺𝟐 𝑺𝟑
0 𝑺𝟏 18 3 2 1 0 0
0 𝑺𝟐 20 2 4 0 1 0
0 𝑺𝟑 5 1 0 0 0 1
𝒁𝒋 0 0 0 0 0 0
𝑪𝒋 − 𝒁𝒋 1200 1600 0 0 0
 Then initiate the following steps.

Step 6: Determine the optimum column or entering by choosing the most positive entry
in the 𝑪𝒋 − 𝒁𝒋 row, which is 1600.
Tableau 1

Optimum column
Tableau 1

Right-Hand Side (RHS) Intersectional Elements (IE)

Step 7: Identify the pivot row by dividing the right-hand side values by the non- zero and
non-negative entries in the optimum column.
Pivot row (PR) = Right-hand side (RHS)  Intersectional Elements (IE)
= 18  2 = 9
= 20  4 = 5 leaving basic variable
= 5  0 =  (undefined)
The second Row of the constraints coefficient has the smallest positive quotient, which is 5;
second row will be the pivot row
Tableau 1

Pivot Row
Other parts of the simplex table are: Entering Variable
Tableau 1

Contribution
to the Profit
Column

Leaving Constraints
Basic Coefficients
Variable
Step 8: Compute the values of the replacing row by dividing all the entries by the pivot 4.
Replacing Row (RR) = Pivot Row (PR)  Pivot(P)
= (20, 2, 4, 0, 1, 0)  4
= (5, ½, 1, 0, ¼, 0)
Step 9: Compute the new values for the remaining rows using the formula.
Remaining Row = Old Row – (Intersectional Element x Replacing Row)
First Row = (18, 3, 2, 1, 0, 0) – (2)(5, ½, 1, 0, ¼, 0)
= (18, 3, 2, 1, 0, 0) – (10, 1, 2, 0, ½, 0)
= (8, 2, 0, 1, - ½, 0)
Third Row = (5, 1, 0, 0, 0,1) – (0)(5, ½, 1, 0, ¼, 0)
= (5, 1, 0, 0, 0,1) – (0, 0, 0, 0, 0, 0)
= (5, 1, 0, 0, 0,1)
Enter the results in Tableau 2.
Tableau 2
Basic Right-Hand 1200 1600
𝑪𝒋
Variables Side 𝑿𝟏 𝑿𝟐 𝑺𝟏 𝑺𝟏 𝑺𝟏
0 𝑺𝟏 8 2 0 1 -½ 0
1600 𝑿𝟐 5 ½ 1 0 ¼ 0
0 𝑺𝟏 5 1 0 0 0 1
𝒁𝒋
𝑪𝒋 − 𝒁𝒋

Step 10: Calculate the 𝒁𝒋 and 𝑪𝒋 − 𝒁𝒋 values.

𝒁𝒋 = (0)(8, 2, 0, 1, - ½, 0) + (1600)(5,1/2, 1, 0, ¼, 0) + (0)(5, 1, 0, 0, 0, 1)
= (0, 0, 0 ,0, 0, 0) + (8000, 800, 1600, 0, 400, 0) + (0, 0, 0 ,0, 0, 0)
= (8000, 800, 1600, 0, 400,0)
𝑪𝒋 − 𝒁𝒋 = (1200, 1600, 0, 0, 0) - (8000, 800, 1600, 0, 400,0)
= (400, 0, 0, - 400, 0)
Enter the results to complete Tableau 2.
 Tableau 2

Return to Step 7, since the 𝑪𝒋 − 𝒁𝒋 row still contains a positive entry.

Step 7: Identify the pivot row by dividing the right-hand side values by the non-zer0 and non-negative entries or the
intersectional elements.

Pivot Row (PR) = Right-hand Side (RHS)  Intersection Elements (IE)

= 82=4 leaving basic variable
= 5  ½ = 5(2) = 10
=51=5
The first row of the constraint coefficient has the smallest positive quotient, which is 4; it will be he
pivot row.
. Step 8; Compute the values of the replacing row by dividing all the entries by the pivot 2
Replacing Row (RR) = Pivot Row (PR)  Pivot (P)
= (8, 2, 0, 1, - ½. 0)  2
= (4, 1, 0, ½, - ¼. 0)
Step 9: Compute the new values for the remaining rows using the formula.
Remaining Row = Old Row – (Intersectional Element x Replacing Row)
First Row = (5, 1/2, 1, 0, 1/4, 0) – (1/2) (4, 1, 0, ½, - ¼, 0)
= (5, 1/2, 1, 0, 1/4, 0) – (2, ½, 0, ¼, - 1/8, 0)
= (3, 0, 1, - ¼, 3/8, 0)
Third Row = (5, 1, 0, 0, 0, 1) – (1) )(4, 1, 0, 1/2, - ¼, 0)
= (5, 1, 0, 0, 0, 1) – )(4, 1, 0, 1/2, - ¼, 0)
= (1, 0, 0, - ½, ¼, 1)
Tableau 3
𝑪𝒋 Basic Right-Hand 1200 1600 0 0 0
Variables Side 𝑿𝟏 𝑿𝟐 𝑺𝟏 𝑺𝟐 𝑺𝟑
1200 𝑿𝟏 4 1 0 ½ -¼ 0
1600 𝑿𝟐 3 0 1 -¼ 3/8 0
0 𝑺𝟑 1 0 0 -½ ¼ 1
𝒁𝒋
300 𝑪𝒋 - 𝒁𝒋

Step 10. Calculate the 𝒁𝒋 and 𝑪𝒋 - 𝒁𝒋 values.

𝒁𝒋 = (1200)(4, 1, 0, ½, - ¼, 0) + (1600)(3, 0, 1, - ¼, 3/8, 0) + (0)(1, 0, 0, - ½, ¼, 1)
= (4800, 1200, 0, 600, - 300, 0) + (4800, 0, 1600, - 400, 600, 0) + (0, 0, 0, 0, 0, 0)
= (9600, 1200, 1600, 200, 300, 0)
𝑪𝒋 - 𝒁𝒋 = (1200, 1600, 0, 0, 0) – (1200, 1600, 200, 300, 0)
= (0, 0, - 200, - 300, 0)
Note: Identify if there is still a positive entry in 𝑪𝒋 - 𝒁𝒋 row. If so return to step 6. The final
solution has been obtained if there is no positive entry in the 𝑪𝒋 - 𝒁𝒋 row.
Tableau 3

Step 11 If the last 𝑪𝒋 - 𝒁𝒋 row do not contain a positive entry the tableau is
optimum. Our decision will be to make
Decision:
𝑿𝟏 = 4 gowns 𝑺𝟏 = 0
𝑿𝟐 = 𝟑 𝐬𝐮𝐢𝐭𝐬 𝑺𝟐 = 0
𝒁𝒋 = P 9,600 𝑺𝟑 = 1
 Sensitivity Analysis:
Changes in the Objective Function Coefficients
 Shadow Prices is the rate of change of the optimal objective function value per unit
increase in the right-hand-side (RHS)
 From Previous example;
A tailor has the following materials available: 18 square meter cotton, 20 square meter
silk, 5 square meter wool. A gown requires the following: 3 square meters cotton. 2 square
meters silk and 1 square meters wool. A suit requires the following: 2 square meters cotton, 4
square meters silk. If a gown sells for P1,200 and a suit for P1,600, how many of each
garments should the tailor make to obtain the maximum amount of money?
Maximize: Zj = 1200x1 + 1600x2
Subject to: 3x1 + 2x2  18
2x1 + 4x2  20
x1  5
x1 , x 2  0
Solution:
where x1 = number of gowns produced
x2 = number of suits produced
The final table in the simplex method:

Step : Change in C1 value from C1 = 1200 to C1 = 1200 + .

The new value is included only in the top Cj row, but also in the left-hand
column Cj
FINAL Simplex Tableau

Solving the delta changes () under the 𝑪𝒋 - 𝒁𝒋 row as long as it will remain negative.
- 200 - /2 < 0 and - 300 + /4 < 0
- /2 < 200 /4 < 300
 > (- 2)(200)  < (4)(300)
 > - 400  < 1200
Step 2: Substitute the values of the delta change into C1 = 1200 + .
Thus,
 > - 400 and  < 1200.
Note: C1 = 1200 + :
Therefore, ∆ = C1 - 1200
Then, substitute C1 - 1200 for  in the inequalities.
 > - 400  < 1200
𝑪𝟏 - 1200 > - 400 𝑪𝟏 - 1200 < 1200
𝑪𝟏 > - 400 + 1200 𝑪𝟏 < 1200 + 1200
𝑪𝟏 > 800 𝑪𝟏 < 2400
Therefore, the change of values for C1 over which the solution basis will
remain optimal is 800 < C1 < 2400.
Step 3: Determine the range of the succeeding Cj over which the current solution
basis will remain optimal.
Considering a delta change in C2.
Step 4: Change in C2 value from C2 = 1600 to C2 = 1600 + .
The new value is included not only in the top Cj row but also in the let-hand
Cj column.
Final Simplex Tableau with C2 = 1600 + 

𝑪𝒋 Basic Right-Hand 1200 1600 +  0 0 0

Variable Side 𝑿𝟏 𝑿𝟐 𝑺𝟏 𝑺𝟐 𝑺𝟑
1200 𝑿𝟏 4 1 0 1/2 -¼ 0
1600 +  𝑿𝟐 3 0 1 -¼ 3/8 0
0 𝑺𝟑 1 0 0 -½ ¼ 1
𝒁𝒋 9600 + 3 1200 1600 +  200 - /4 300 + 3/8 0
𝑪𝒋 − 𝒁𝒋 0 0 - 200 + /4 - 300 - 3/8 0
Solving the delta change () under the 𝑪𝒋 - 𝒁𝒋 row as long as it will remain negative.
- 200 + /4 < 0 and - 300 - 3/8 < 0
/4 < 200 - 3/8 < 300
 < (4)(200)  > (- 8/3)(300)
 < 800  > - 800
Step 5: Substitute the values of the delta change into C2 = 1600 + .
Thus,  < 800 and  > - 800.
Note that C2 = 1600 + ;
Therefore,
 = C2 – 1600.
Then substitute C2 – 1600 to  in the inequalities,
 < 800  > - 800
C2 – 1600 < 800 C2 – 1600 > - 800
C2 < 800 + 1600 C2 > - 800 + 1600
C2 < 2400 C2 > 800
Therefore, the change of values for C2 over which y=the
solution basis will remain optimal is 800 < C2 < 2400.
This demonstrates that a change in one of the ranges in the
coefficients of the objective function cannot change the optimal
solution.
 Changes in the Structural Constraint Coefficients
 Range of Feasibility is the range over which the right-hand side value
of a constraint can change without changing the optimal solution of a
problem.
 The sensitivity based on shadow prices and change vectors which
determines how the objective value and optimal solution change as
right-hand-side coefficients are changed.
 It also finds the validity ranges for the shadow prices and vector
change which is called right-hand-side ranging.
Step1:
Maximize: Zj = 1200x1 + 1600x2
Subject to: 3x1 + 2x2  18
2x1 + 4x2  20
x1  5
x 1 , x2  0
Step 2: Determine the  changes in Qi from the optimal tableau. We will first solve for
the  change in first constraint.
3x1 + 2x2  18 + 1
2x1 + 4x2  20 + 0
x1  5 + 0
Notice in the initial simplex tableau for our example in the following table that the
changes in the right-hand side (RHS) column are the same coefficient in the S1 columns.
Initial Simplex Tableau
𝑪𝒋 Basic Right-Hand 1200 1600 0 0 0
Variables Side 𝑿𝟏 𝑿𝟐 𝑺𝟏 𝑺𝟐 𝑺𝟑
0 𝑺𝟏 18 + 1 3 2 1 0 0
0 𝑺𝟐 20 + 0 2 4 0 1 0
0 𝑺𝟑 5 + 0 1 0 0 0 1
𝒁𝒋 0 0 0 0 0 0
𝑪𝒋 - 𝒁𝒋 1200 1600 0 0 0
Step 3: We will also duplicate through each subsequent tableau, so the S1 column
values will duplicate the  changes in the right-hand side (RHS) column in
the final tableau.
Final Simplex Tableau
𝑪𝒋 Basic Right-Hand 1200 1600 0 0 0
Variables Side 𝑿𝟏 𝑿𝟐 𝑺𝟏 𝑺𝟐 𝑺𝟑
1200 𝑿𝟏 4 + /2 1 0 ½ -¼ 0
1600 𝑿𝟐 3 - /4 0 1 -¼ 3/8 0
0 𝑺𝟑 1 - /2 0 0 -½ ¼ 1
𝒁𝒋 9600 + 200 1200 1600 200 300 0
𝑪𝒋 - 𝒁𝒋 0 0 - 200 - 300 0
Step 4: Solve the  inequalities: 4 + /2
3 - /4
1 - /2
Solving the  values in each inequality
4 + /2  0 3 - /4  0 1 - /2  0
/2  0 – 4 - /4  0 – 3 - /2  0 – 1
  (- 4)(2)   (- 3)(- 4)   (- 1)(- 2)
-8   12 2
Since constraint 1 is:
Q1 = 18 + , then  = Q1 – 18
These values are substituted into the inequalities   - 8,   12, and   2 as follows,
-8   12 2
Q1 – 18  - 8 Q1 – 18  12 Q1 – 18  2
Q1  - 8 + 18 Q1  12 + 18 Q1  2 + 18
Q1  10 Q1  30 Q1  20
That is, 10  Q1  20  30.
The value 30 can be eliminated since Q1 cannot exceed 20.
Thus the range over which the basic solution variables will remain feasible is : 10  Q1  20.
Step 5. We will now solve the  change in the second constraint.
3x1 + 2x2  18 + 0
2x1 + 4x2  20 + 1
x1  5 + 0
Observe that in the initial simplex tableau for our example in the following table that the
changes in the right-hand side (RHS) column are the same coefficients in the S2 column.
Initial Simplex Tableau

𝑪𝒋 Basic Right-Hand 1200 1600 0 0 0

Variables Side 𝑿𝟏 𝑿𝟐 𝑺𝟏 𝑺𝟐 𝑺𝟑
0 𝑺𝟏 18 + 0 3 2 1 0 0
0 𝑺𝟐 20 + 1 2 4 0 1 0
0 𝑺𝟑 5 + 0 1 0 0 0 1
𝒁𝒋 0 0 0 0 0 0
𝑪𝒋 - 𝒁𝒋 1200 1600 0 0 0
Step 6. We will also copy through each subsequent tableau, so the S2 column values
will copy the  changes in the RHS column in the final tableau.
Final Simplex Tableau
𝑪𝒋 Basic Right-Hand 1200 1600 0 0 0
Variables Side 𝑿𝟏 𝑿𝟐 𝑺𝟏 𝑺𝟐 𝑺𝟑
1200 𝑿𝟏 4 - /4 3 2 ½ -¼ 0
1600 𝑿𝟐 3 + 3/8 2 4 -¼ 3/8 0
0 𝑺𝟑 1 + /4 1 0 -½ ¼ 1
𝒁𝒋 9600 + 300 0 0 200 300 0
𝑪𝒋 - 𝒁𝒋 1200 1600 - 200 - 300 0

Solve the  inequalities,

4 - /4  0
3 + 3/8  0
1 + /4  0
Solving the  values in each inequality,
4 - /4  0 3 + 3/8  0 1 + /4  0
- /4  - 4 3/8  - 3 /4  - 1
  (- 4)(- 4)   (- 3)(8/3)   (- 1)(4)
  16 -8 -4
Since the constraint 1 is : Q2 = 20 + , then  = Q2 – 20.
These values are substituted into the inequalities   16,   - 8, and   - 4 as follows.
  16 -8 -4
Q2 – 20  16 Q2 – 20  - 8 Q2 – 20  -4
Q2  16 + 20 Q2  - 8 + 20 Q2  -4 + 20
Q2  36 Q2  12 Q2  16
That is, 12  16  Q2  36.
The value 12 can be eliminated, since Q2 must be greater than or equal to 16.
Thus the range over which the basic solution variables will remain feasible is: 16  Q2  36.
 Sensitivity analysis of constraint quantity values can be used in combination with the
dual solution to make decision regarding the model resources.
Recall the analysis of the dual solution of the Tailor problem example that
𝒚𝟏 = 𝑷 𝟐𝟎𝟎 marginal value of cotton
𝒚𝟐 = 𝑷 𝟑𝟎𝟎 marginal value of silk
𝒚𝟑 = 𝑷 𝟎 marginal value of wool
Since the resources with the greatest marginal value is silk, the decision is to secure
same additional square meter of silk. Given that the range for Q2 is 16  Q2  36, the
decision is to secure up to an additional 16 square meter of silk (36 total square meter)
before the solution became infeasible.
Step 8. Solve the new feasible solution by  = 16 using the RHS of the final tableau in the 
change in the second constraint.
𝑿𝟏 = 4 - /4
𝑿𝟐 = 3 + 3/8
𝑺𝟑 = 1 + /4
Since  = 16,
𝑿𝟏 = 4 - 16/4 𝑿𝟐 = 3 + 3(16)/8 𝑺𝟑 = 1 + 16/4
𝑿𝟏 = 4 – 4 𝑿𝟐 = 3 + 6 𝑺𝟑 = 1 + 4
𝑿𝟏 = 0 𝑿𝟐 = 9 𝑺𝟑 = 5
The tailor must produce 0 gown and 9 suits in order to have an increase of P300
for each square meter of silk.
𝒁𝒋 = 9600 + 300
= 9600 + 300(16)
= 9600 + 4800
= P14,400
Assignment:
Solve the maximization problem using simplex method.
Maximize: 𝒁𝒋 = 𝟐𝑿𝟏 + 𝑿𝟐
Subject to;
𝑿𝟐 ≤ 𝟏𝟎
𝟐𝑿𝟏 + 𝟓𝑿𝟐 ≤ 𝟔𝟎
𝑿𝟏 + 𝑿𝟐 ≤ 𝟏𝟖
𝟑𝑿𝟏 + 𝑿𝟐 ≤ 𝟒𝟒
𝑿𝟏, , 𝑿𝟐 ≥ 𝟎
Minimization Problem
Example 3.2 A Dug Company produces a drug from two ingredients. Each ingredient
contains the same three antibiotics in different proportions. Each ingredient 1 produced
results in P80 in cost; each ingredient 2 results in P50 in cost. The production of the
antibiotics is dependent on the availability of limited resources. The resource
requirements for the production are as follows:

The company wants to determine the number of grams of each ingredient 1 and 2 that
must go in to drug in order to meet the antibiotic minimum requirements at the minimum cost.
Solution:
Reference:
1. Sirug, Dr. Winston S. , “Quantitative Techniques for Business”, Copyright 2006,
ISBN 978-971-04445-00-4