Recap on LP through Graphics

• Let’s start with a basic problem. An organization has

two products with selling prices of Birr 25 and Birr 20
and are called product A and B respectively. Every
day, they have 1800 units of resources to produce
these products. Product A requires 20 resources units
and B requires 12 resources units. The production
time for Each of these products is four minutes and
the organization gets a total of eight working hours
every day. The problem is, what should be the
production quantity for each of these products to
maximize the company’s profits?
 B. Simplex Method

• Step 1 Formulate LPP Model 

• Step 2 Standardize the problem
• i.e. Convert constraint inequality into equality form by introducing a
variable called Slack variable.
• Slack Variables:
• A slack variable(s) is added to the left hand side of a < constraint to
covert the constraint inequality in to equality. The value of the slack
variable shows unused resource. 
• A slake variable emerges when the LPP is a maximization problem.
•  Slack variables represent unused resource or idle capacity.
• Thus, they don’t produce any product and their contribution to profit is zero.
• Slack variables are added to the objective function with zero coefficients.
•  Let that s1, s2, and s3 are unused labor, machine and marketing hrs
respectively.
 The Simplex Method

• The graphical approach for LPPs is restricted

solving with only two decision variables.
problems to
– When the number of variables to deal with increase
another method is required to be used.
• An efficient method for solving LPPs with more than two
variables is called the simplex method, or iterative or step by
step method.
• It was developed by George B. Datzing in 1947.
• It is an algebraic procedure which starts with a feasible
solution that is not optimal and systematically moves from
one feasible solution to another until an optimal solution is
found.
 Basic Terms Involved in Simplex
Procedure
1. Standard Form: when all constraints are written as
equalities it is called standard form
2. Utilization of Resources
I. Slack Variable: A Variable added to the LHS of a ‘less-
than or equal to’ constraint to convert the constraint into
an equality is called a slack variable.
II. Surplus variable: A variable subtracted from the LHS of
the “greater than or equal to” constraints to convert the
constraints into equality is called a surplus variable.
3. Basic variable: for m simultaneous linear
equations in n variables(n>m), a solution obtained by
setting (n-m) variables equal to zero and solving for
the remaining m variables is called a basic variables
4. Basic feasible solution: a basic feasible solution
is a basic solution for which the variables have a
value of greater than or equal zero.
5. Simplex Tableau: is a table used to keep track of
the calculation that made at each of the iteration
when the simplex solution method is employed.
7. Zj Row: the numbers in this row under each
variable represents the total contribution of outgoing
profit when one unit of a non-basic variable is
introduced into this in place of a basic variable.
8. Cj – Zj Row: the row containing the net profit that will result
from introducing one unit of the variable indicated in that
column in the solution numbers in index rows are also known
as shadow prices.
9. Pivot column: the column with the largest positive number
in the net evaluation row of maximization problem, or the
largest negative number in the net evaluation row in the cost
minimization problem(Cj-Zj)
Incoming variables
 An incoming variable is currently a non-basic variable (the current
value is zero) and will be changed to a basic variable (introduced
into the solution).

01/17/2023
10. Pivot row: the row corresponding to the variable
that will leave the basis in order to make room for the
entering variable.
Outgoing Variable
 To determine the outgoing variable, compute the ratio
of the Quantity to the coefficient of the incoming
variable for each basis row.
 For both the maximization and minimization
problems, the outgoing variable is the basic variable
with the smallest ratio.
 The coefficient of the incoming variable in the
outgoing row is called the pivot element/number.
11. Pivot number: the element at the
intersection of the pivot row and pivot column

12. Iteration: an iteration of the simplex

method consists of the sequence of steps
performed in moving from one basic feasible
solution to another.

01/17/2023
 The procedures of Simplex Method

I. Standardize the problem.

II. Generate an initial Solution.
III.Test for optimality if in case the solution is
optimal Otherwise, go to Step 4.
IV.Identify the incoming and outgoing
variables.
V. Generate an improved solution. Go to Step
3.
VI.Check
01/17/2023 for other optimal solutions.
• To convert a ≤ constraint to an equality, define for each
constraint a slack variable [si] (si = the slack variable for
the ith constraint).
– A slack variable is the amount of the resource unused
in the ith constraint.
• To convert a ≥ constraint to an equality constraint, define
a surplus variable [ei] (si = the excess variable for the ith
≥ constraint.
• Since, slack and surplus variables are insignificant with
no contribution, they are represented with coefficient of
zero in the objective function.
Example: Constraints with ≤ sign
• Non Standard form Standard form
X1+2X2 ≤ 6 X1+2X2+S1= 6
• where X1 and X2 are decision variables and S1 is a slack
variable, added to the smaller side of the inequality.
Example: Constraints with ≥ sign
• Non Standard form Standard form
X1+2X2 ≥ 6 X1+2X2-s1= 6
• where X1 and X2 are decision variables and s1 is a surplus
variable, added to the smaller side of the inequality.
• To find a unique solution, the number of variables should
not exceed the number of equations.
• When the number of variables is more than the number of
equations, the number of solutions is unlimited.
• So as to get a unique solution, we have to set at least (n-
m) variables to zero, where:
n = the number of variables and
m = the number of equalities.
• Those variables that are set to zero are called non basic
variables indicating they are not in the solution.
• The variables that are in solution are called basic variable.
• For a set of m simultaneous equations in n variables (
n>m), a solution obtained by setting ( n-m) variables
equal to zero and solving for remaining m equations
in m variables is called a basic solution
• Any basic solution which all variables are a
in nonnegative basic feasible solution
is called (or BFS).
 Example:
Maximization
• A Problem
microcomputer manufacturing firm about to start
production
is of two new microcomputers, Model-I and
Model-II. Each requires limited resources of assembly time,
inspection time, and storage space. Currently, 100 hours of
assembly time, 22 hours of inspection time and 39 cubic feet
of storage space are available. A unit of Model-I and Model-
II microcomputers contribute $60 and $50 to the profit of the
firm respectively. The amount of each resource needed to
make each type of microcomputer is given in the following
table. The manager wants to determine how much of each
computer to produce in order to maximize the profit
generated by selling them.
 Cont
…
• Table 3.1: The amount of each resource needed
to make each type of microcomputer

Resources Model-I MC Model-II MC

Assembly time/unit 4 hrs 10 hrs

Inspection time/unit 2 hrs 1 hr

Storage space/unit 3 cubic feet 3 cubic feet

Soluti
on:
Let:
o x1 = number of Model-I microcomputers manufactured
o x2 = number of Model-II microcomputers manufactured
• The LP is
Max z = 60x1 + 50x2
s.t. 4x1 + 10x2 ≤ 100 (Assembly time constraint)
2x1 + x2 ≤ 22 (Inspection time constraint)
3x1 + 3x2 ≤ 39 (Storage space constraint)
x1, x2 ≥ 0
Solving the Problem using the Simplex method (Step by step)

 Step 1: Convert the model in to a standard form: It can be by

introducing slack variables to the constraints and adding the
slack variables to the objective function with zero coefficients
• Standard Form of the LP:
Max Z = 60X1+50X2+0S1+0S2+0S3
Subject to 4X1+10X2+S1 = 100
2X1+ X2+S2 = 22
3X1+ 3X2+S3 = 39
X1, X2, S1, S2, S3 ≥ 0
 Cont
…
 Step 2: Design the initial feasible solution: An initial basic
feasible solution is obtained by setting the decision variables
to zero.
• In our example (at the origin):
X1 = 0
X2 = 0
• Thus, we get:
S1 = 100
S2 = 22
S3 = 39
 Cont
…
 Step 3: Set up the initial simplex tableau: it can be developed
as follows. (Table 1)
Basic Cj 60 50 0 0 0 RHS RR
Variables X1 X2 S1 S2 S3
100/4= 25
S1 0 4 10 1 0 0 100
22/2 = 11
S2 0 2 1 0 1 0 22
39/3 = 13
S3 0 3 3 0 0 1 39
Zj 0 0 0 0 0 0
Cj-Zj 60 50 0 0 0

Leaving Variable Entering Variable Pivot Element

 Cont
…
 Interpretation of the data in the above tableau:
– In the first row labeled "Cj” are stated the coefficients of the
variables in the objective function.
• These values will remain the same in
subsequent
tableaus.
– To find an entry in the Zj row under a column, we multiply
the entries of that column by the corresponding entries of
‘CB’ column and add the results, i.e., Zj= ∑CBiXj.
– The Zj row entries will all be equal to zero in the initial
simplex tableau.
– The Zj entry under the “Quantity Column" gives the current
value of the objective function.
 Cont
…
– The last row labeled "Cj-Zj“ is called the index row or net
evaluation row.
– It is used to determine whether or not the current solution
is optimal or not.
– The calculation of Cj-Zj row simply involves subtracting each Zj
value from the corresponding Cj value for that column.
– The entries in the Cj - Zj, row represent the net contribution
to the objective function that results by introducing one unit
of each of the respective column variables.
– A plus value indicates that a greater contribution can be
made by bringing the variable for that column into the
solution. [Negative values indicate a decrease in contribution]
 Cont
…
– Index row elements are also known as the shadow prices.
 Step 4: Test if the current solution is optimum or not:
– If all the elements or entries in the Cj- Zj row are negative or
zero, then the current solution is optimum.
– If there exists some positive number, the current solution can
be further improved by removing one basic variable from the
basis and replacing it by some non-basic one.
 Step 5: Identify the Entering and Leaving Variables
 The variable with the largest positive value in the Cj - Zj row is
the entering variable.
 Cont
…
• The column associated with the entering variable is
called
Key/pivot Column.
• We need to compute the replacement ratio to identify
the leaving variable:
Replacement Ratio (RR) = Solution Quantity (Q)
Corresponding values in pivot column

• The row with the minimum ratio is the key/pivot row.

• The corresponding variable in the key row (the
departing variable) will leave the basis.
• The number that lies at the intersection of the key column and
key row is called a pivot element.
 Cont
…
 Step 7. Evaluate the new solution by constructing a second
simplex tableau.
 Use Elementary Row Operations (EROs) to find a new BFS
with a better objective function value.
 Step 8. Do the Iteration and Complete it.
 If any of the numbers in Cj - Zj row are positive, repeat
the steps (6-7) again until an optimum solution is
obtained.
 Step 9. Interpret the result
 Cont
…
 Simplex Tableau 2
• ERO: 1/2R2→R2 -4R2+R1→R1 -3R2+R3→R3
Basic Cj 60 50 0 0 0 RHS RR
Variables X1 X2 S1 S2 S3
56/8= 7
S1 0 0 8 1 -2 0 56
11/1/2 =22
X1 60 1 1/2 0 1/2 0 11
6/3/2 =4
S3 0 0 3/2 0 -3/2 1 6
Zj 60 30 0 30 0 660
Cj-Zj 0 20 0 -30 0
 Cont
…
 Simplex Tableau 3
• ERO: 2/3R3→R3 -1/2R3+R2→R2 -8R3+R1→R1
Basic Cj 60 50 0 0 0 RHS
Variables X1 X2 S1 S2 S3

S1 0 0 0 1 6 -16/3 24
X1 60 1 0 0 1 -1/3 9
X2 50 0 1 0 -1 2/3 4
Zj 60 50 0 10 40/3 740
Cj-Zj 0 0 0 -10 -40/3
All elements in the Cj-Zj row are ≥0. So, the optimal solution is found.
 Cont
…
• Allthe values in the Cj-Zj row are zero and
negative
indicating that there can no be additional improvement.
• This makes the third tableau to contain the
optimal solution with the following basic variables:
S1 = 24,
X1 = 9, and
X2 = 4, producing a maximum profit of $740.
 Interpretation: In order to achieve the maximum profit of
$740, the company should produce 9 units of Model-I and 4
units of Model-II micro computers leaving 24 hours of
unused resource of the assembly time constraint.
 Example 2: Simplex Method for the Maximization
Problem
Example1: Max z= 40x1 +30x2
S.T x1 + 2x2 ≤ 40 hour of labour
4x1 + 3x2 ≤ 120 Ib of clay
X1, x2 ≥ 0
Required:
 Standardize the model
 Generate an initial solution and the initial simplex
tableau
 Determine the value of x1 and x2 at the optimal
simplex tableau
 What is the z-value at the optimal solution?
 Does the problem have a multiple solution? Why?
01/17/2023
 Solution:
A.
Convert the model into standard form by adding slack
variables to each constraint as follows.
N.B: slack variables are added to ≤ constraints and represent
unused resources.
Max Z = Max z= 40x1 +30x2+0s1 + 0s2
S.T x1 + 2x2 +s1 +0s2 = 40
4x1 + 3x2 + 0s1+ s2 =120
X1, x2,s1, s2 ≥ 0

01/17/2023
 Cont…
B.
At the origin where nothing is being produced, the values of all
the decision variables are zero which implies the value of the
slack variable equals to the RHS value.
1(0) + 2(0) +s1+ 0S2 = 40
S1= 40 -------------------------------------------------- 1
4(0) + 3(0) + 0S1 + s2 = 120
S2 = 120------------------------------------------------ 2
N.B: at the origin all decision variables are non-basic whereas all
slack are basic.

01/17/2023
 Cont… Pivot Pivot
column number

Pivot Row

01/17/2023
The objective is to maximize profit with a
 Cont…
•  

01/17/2023
 Cont…
•  

01/17/2023
 Cont …

01/17/2023
 Cont…

01/17/2023
 Cont…
The optimal solution has been reached because all
values of Cj-zj row are less than and equal to zero.

01/17/2023
E.
Con t…
 Multiple optimal solutions on a simplex tableau can be
determined from Cj- Zj or Zi-Cj row value. An alternative
optimal solutions have the same z value but different
variable values.
 The answer for the question is yes because optimal simplex
tableau is said to be multiple if at least one non-basic
variable has zero value in the Cj-Zi or Zj-Cj row.
 Now you can see the above table, x2 is non-basic variable
but its value corresponds to Cj-zj row is zero.
 Alternative optimal solution is determined by selecting the
non-basic variable with Cj-zj = 0 as entering or incoming
variable.
01/17/2023
 Cont…

01/17/2023
Example 3:
A farmer owns a 100-hectare farm and plans to
plant at most three crops. The seed for crops A,
B, and C costs $40, $20, and $30 per hectare,
respectively. A maximum of $3,200 can be
spent on seed. Crops A, B, and C require 1, 2,
and 1 work days per hectare, respectively, and
there is a maximum of 160 work days available.
If the farmer can make a profit of $100 per
hectare on crop A, $300 per hectare on crop B,
and $200 per hectare on crop C, how many
hectare of each crop should be planted to
maximize profit? What is the maximum profit?
40
 solution
• Number of hectare of crop A = 0
• Number of hectares of crop B = 60
• Number of hectares of crop C = 40
• Maximum profit = $26,000
 The Big M-method
/Charnes Penalty Method/
• The Big-M Method is a method which is used in removing artificial
variables from the basis .In this method; we assign coefficients to
artificial variables, undesirable from the objective function point of
view.
• If objective function Z is to be minimized, then a very large positive
price (called penalty) is assigned to each artificial variable.
• Similarly, if Z is to be maximized, then a very large negative price
(also called penalty) is assigned to each of these variables.
• Following are the characteristics of Big-M Method:
• High penalty cost (or profit) is assumed as M
• M is assigned to artificial variable A in the objective function Z.
• Big-M method can be applied to minimization as well as
maximization problems with the following distinctions:
 1.

• - Minimization problems
• : Assign +M as coefficient of artificial variable A in the objective function Z
• Maximization problems:
• -Here –M is assigned as coefficient of artificial variable A in the objective
function Z
• Coefficient of S (slack/surplus) takes zero values in the objective function Z
• For minimization problem, the incoming variable corresponds to the highest
negative value of Cj-Zj.
• Solution is optimal when there is no negative value of Cj-Zj.(For minimization
case)
• Example:
• 1. Minimize Z=25x1 +30x2
• Subject to:
• 20x1+15x2 > 100
• 2x1+ 3x2 > 15
• x1, x2 >0
• Solution
• Step 1
• Standardize the problem
• Minimize Z=25x1 +30x2 +0s1+0s2 +MA1+MA2
• Subject to:
• 20x1+15x2- s1+A1 = 100
• 2x1+ 3x2 –s2+A2 = 15
• x1, x2 , s1, s2 ,A1 ,A2 > 0  
• Step 2
• Initial simplex tableau
• The initial basic feasible solution is obtained by setting x 1= x2= s1= s2=0
• No production, x1= x2= s1=0==>20(0) +15(0) - 0+A1 = 100 ==> A1 = 100
• x1= x2= s2=0==>0(0)+3(0) - 0+A2 =15==> A2 = 15
Contd…..
Contd…..
Contd….
Special Issues in the Simplex Method
1. Non-feasible Solution/ Infeasibility
– Whenever the optimality criteria is satisfied but still
there exist an artificial variable in the basis or solution
mix, this is the indication of infeasibility.
2. Unbounded Solution
– It is detected when trying to decide which variable to
leave [while computing replacement ratio for all
variables]
– If the entire ratios turn out to be negative or undefined,
it indicates that the problem is unbounded.
3. Degeneracy
– Tie for leaving basic variable (key row)
– If there is a tie for the smallest ratio, this is a signal that
degeneracy exists.
– Such problems can be overcome by trial and
error method.
5. Multiple Optimum Solutions
– A situation when there can be infinite number of
solutions possible for a given problem.
– This can be recognized when one of the non-basic
variables in the Cj-Zj, row have a value of zero.
– To obtain the other solution, we will make a non-
basic variable with a zero Cj-Zj value to enter in to the
basis and solve.
 Transportation
Chapter Three and
Assignment