Lecture notes on

Decision Modelling
(ENEC531)

By Dr Gemechu Mulatu
Haramaya University
College of Business and economics
Department of Economics
E-mail: mulatugemech02@gmail.com
Course Description
•Quantitative approach is one of scientific methods in making business decisions. In this
method, such mathematics formulas, models, or heuristic/algorithm are used in
determining decision variables we want to solve.
•Quantitative approach presumably disregards emotional/ psychological content that may
affect decision maker in formulating problems, finding most fitted alternatives, gathering
appropriate/ relevant data, testing the result and in applying the decision. However, this
course will introduce some decision theory models that in some extents will quantify
psychological effect on the rationale of a decision.
•The models, formulas, and algorithms will not be used in operations research/ strategy
but also will be useful in making a good and rational decision in the area of economic
science like energy economics.
Course Objective.
•After completing this course, student is expected to be
able to demonstrate their ability in exposing, identifying
and analysing business problems, selecting appropriate
models, computing/ processing data into the model,
testing/ verifying the result, and translating the result
into energy business strategy.
•Students will be introduced to some computer
programs and therefore student is also expected
familiar with the soft wares.
Contents to be covered
•Introduction to decision Modeling

•Introduction to Linear Programming

•Linear Programming: Graphical Solutions

• Linear Programming: the Simplex Method

•Maximization With Mixed Constraints And Minimization

•Post-optimality analysis

•Transportation and Assignment Problems

•Network Model/ Optimization

•Non Linear Optimization

•Dynamic optimization
 Chapter 1:
Introduction to Decision Modeling
 What is Decision Modeling?

A scientific approach to managerial decision

making
• The development of a (mathematical) model of a
real-world scenario
• The model provides insight into the solution of the
managerial problem
Decisions often must be made in environments that are much more
fraught
with uncertainty. Here are a few examples.
1.A manufacturer introducing a new product into the marketplace.
 What will be the reaction of potential customers?
 How much should be produced?
 Should the product be test marketed in a small region before
deciding upon full distribution?
 How much advertising is needed to launch the product
successfully?
2. A financial firm investing in securities.
 Which are the market sectors and individual securities with the
best prospects?
Where is the economy headed?
How about interest rates?
How should these factors affect the investment decisions?
3. A government contractor bidding on a new contract.
What will be the actual costs of the project?
Which other companies might be bidding?
 What are their likely bids?
 Decision analysis provides a framework and methodology for rational
decision making when the outcomes are uncertain.
 Decision theory problems are characterized by the following:

1. A list of alternatives.

2. A list of possible future states of nature.

3. Payoffs associated with each alternative/state of nature

combination.
o The payoff is a quantitative measure of the value to the decision
maker of the consequences of the outcome

4.An assessment of the degree of certainty of possible future events.

5. A decision criterion.
 Types of Decision Models
• Deterministic Models
Where all the input data value are known
with complete certainty
• Probabilistic Models
Where some input data values are uncertain
 Quantitative vs. Qualitative Data
The modeling process begins with data
• Quantitative Data

Numerical factors such as costs and revenues

• Qualitative Data

Factors that effect the environment which are

difficult to quantify
 Spreadsheets in Decision Making
• Computers are used to create and solve models

• Spreadsheets are a convenient alternative to

specialized software
• Microsoft Excel has extensive modeling capability
via the use “add-ins”
 Steps in Decision Modeling
1. Formulation

Translating a problem scenario from words to a

mathematical model

2. Solution

Solving the model to obtain the optimal solution

3. Interpretation and Sensitivity Analysis

Analyzing results and implementing a solution

Steps in Decision
Modeling
 Possible Problems in
Developing Decision Models

Defining the Problem

• Conflicting viewpoints

• Impact on other departments

• Beginning assumptions

• Solution outdated
Possible Problems in Developing Decision
Models
Developing a Model
• Fitting the textbook models
• Understanding the model

Acquiring Input Data

• Using accounting data

• Validity of data
Possible Problems in Developing Decision
Models CTD..
 Developing a Solution
• Hard to understand mathematics

• Limitations of only one answer

 Testing the Solution

 Analyzing the Results

 Implementation
Chapter two: Introduction to Linear
Programming

19
 What is LP?
The word linear means the relationship which can be
represented by a straight line .i.e the relation is of the
form
ax +by=c
In other words it is used to describe the relationship
between two or more variables which are proportional
to each other.
The word “programming” is concerned with the optimal
allocation of limited resources.
20
 Definitions of LP

• LP is a mathematical modeling technique useful for the allocation

of “scarce or limited “ resources, such as labor, material,
machine ,time ,warehouse space ,etc…,to several competing
activities such as product , service , job, new equipments,
projects, etc...on the basis of a given criteria of optimality.
• The phrase scare resource means resource that are not available
in infinite quantity during the planning period.
• The criteria of optimality , generally is either performance , return
on investment , profit , cost , utility , distance etc.
21
• LP is a mathematical technique used to obtain
an optimum solution in resource allocation
problems, such as production planning.
• It is a mathematical model or technique for efficient
and effective utilization of limited recourses to
achieve organization objectives

• (Maximize profits or Minimize cost).

22
 General Structure of LP Model
• There are n variables in m constraints to be solved

Max / Min Z  c1x1  c2 x2 ... cn xn

S.t.
a11x1  a12 x2 ... a1n xn  /  /  b1
a21x1  a22 x2 ... a2n xn  /  /  b2
........................................................
am1x1  am2 x2 ... amn xn  /  /  bm
xi  0, i 1,2,..., n

23
• The maximization or minimization of some
quantity is the objective in LP problems.
• All LP problems have constraints that limit the
degree to which the objective can be pursued.
• A feasible solution satisfies all the constraints.
• An optimal solution is a feasible solution that
results in the largest possible objective function
value when maximizing (or smallest when
minimizing).

24
 Linear Programming - LP
• A function f (x1, x2, …, xn) is a linear function iff for
some set of constants c1, c2, …, cn, f(x1, x2, …, xn) = c1x1 +
c2x2 + … + cnxn
• For any linear function f (x1, x2, …, xn) and any number
b, the inequalities f (x1, x2, …, xn)  b and f (x1, x2, …, xn)
 b are linear inequalities
• Solving the problem means finding the values of the
decision variables that:
• satisfy the constraints
• optimize the objective function
25
• The objective function: The objective (goal) of each LPP is
expressed in terms of decision variables to optimize the
criterion of optimality (also called measure of performance)
such as profit, cost ,revenue etc..
• In its general form, it is represented as :
• Optimize (Max/ Min) Z = C1x1 + C2x2 + …….Cnxn
– where Z is the measure of performance variable, which is a
function of x1, x2,…..xn.
– Quantities c1,c2….cn are parameters that represent the
contribution of unit of respective variables.
26
• Decision variables: We need to evaluate various alternatives
(course of action) for arriving at the optimal value of objective
function. The evaluation of these alternatives is guided by the
nature of objective function and availability of resource. For this
we presume certain activities (decision variables) usually
denoted by x1,x2….xn.

– The value of these activities represents the extent to which

each of these is performed.

27
• The constraints: There are always certain limitations (or
constraints ) on the use of resources e.g. labour, m/c, raw
material, money etc.. that limit the degree to which an
objective can be achieved.
• Such constraints must be expressed as linear equalities or
inequalities in terms of decision variables.
– The solution of LP model must satisfy these constraints.

28
 LP Assumptions
• When we use LP as an approximate representation of a real-life
situation, the following assumptions are inherent:
1. Proportionality. - The contribution of each decision variable to the objective or
constraint is directly proportional to the value of the decision variable.

2. Additivity. - The contribution to the objective function or constraint for any variable is
independent of the values of the other decision variables, and the terms can be added
together sensibly.

3. Divisibility. - The decision variables are continuous and thus can take on fractional
values.

4. Deterministic. - All the parameters (objective function coefficients, right-hand side

coefficients, left-hand side, or technology, coefficients) are known with certainty.
29
 Optimization & Problem Solving
• Optimization attempts to express the goal of solving a problem in the best way.
– Running business to maximize profit, minimize loss and risk
– Design a bridge to maximize strength
– Selecting a flight plan to minimize time and fuel use
• To solve a problem:
– Define and formulate the problem
– Build a mathematical model of the problem
– Verify the model
– Identify and evaluate suitable feasible alternatives
– Select the best alternative
– Interpret and present your decision
30
 Advantages of LPP
• LP helps in attaining the optimum use of productive resources.
• LP improves the quality of decisions .
• The decision-making approach of the user of the technique becomes more
objective and less subjective.
• It also helps in providing better tools for adjustments to meet changing
conditions.
• Most business problems involve constraints like raw material availability, etc
which must be taken into consideration. Just coz we can produce so many units
does not mean that they can be sold. LP can handle such situation also since it
allows modification of its mathematical solutions.
• Highlighting the bottle neck in the production process is the most significant
advertizing of this process.
31
 Limitations of LPP
• LP treats all relationships among decision variables as linear.
However ,generally, neither the OF nor the constraints in real life
situations concerning business and industrial problems are linearly
related to the variables .It may yield fractional valued ans for
decision variables, round the same values may not yield an
optimal solution.
• LP model does not take into consideration the effect of time and
uncertainty.
• Parameters appearing in the model are assumed to be constant
but in real life situations, they are frequently neither known nor
constant.
• It deals only with single objectives, whereas in real-life situations
we may come across conflicting multi-objective problems.
• For large problems having many limitations and constraints, the
computational difficulties are enormous, even when the
assistance of computer is available. For it, the main problem can
be fragmented into several small problems and solving each one
separately.
32
 Problem Formulation

 Problem formulation or modeling is the

process of translating a verbal statement of a
problem into a mathematical statement.

33
 Guidelines for Model Formulation
 Understand the problem thoroughly.
 Describe the objective.
 Describe each constraint.
 Define the decision variables.
 Write the objective in terms of the decision
variables.
 Write the constraints in terms of the decision
variables.
34
 Example. A Nutrition Aid Problem
 A Nutrition Aid Program is considering two food
supplements S1 and S2 for distribution among a
population deficient in nutrients N1, N2, and N3. The
nutritional content and prices of the food supplements
and the minimum daily nutritional requirements per
person are given in Table 3.1
 For example, each unit of S1 provides 4 units of N1, 8
units of N2, 5 units of N3, and costs 6 pesos.
 The problem is to determine the daily quantities of the
food supplements for each person that meet the
minimum daily requirements and entail the least cost.
35
 Table 3.1. Dietary and Price Data
S1 S2 Minimum Daily
(Per Unit) (Per Unit) Requirement
(Per Person)
N1 4 12 96
N2 8 4 112
N3 5 5 100
Price P6 P4

36
To formulate this problem mathematically, let x i (i = 1,2)
denote the quantity of Si (i = 1,2) needed per person per day.
The cost C (assuming no discounts) is given by
C = 6x1 + 4x 2 .
To satisfy the.minimum.daily requirements, we must have
4x1 + 12x 2 > 96
8x1 + 4x 2 > 112
5x1 + 5x 2 > 100.
Finally, the quantities x i must not be negative, i.e.,
x1 >0, x 2  0.
The problem is expressed formally as follows:
Minimize 6x1 + 4x 2
subject to 4x1 + 12x 2 > 96
8x1 + 4x 2 > 112
5x1 + 5x 2 > 100
and x1 >0, x 2  0.
37
 Example. A Product Mix Problem
 A firm produces two different products P1 and P2. Every unit of P1 uses 3

units of resource 1 (R1) and 1 unit of resource 2 (R2) and earns a profit of
5 pesos. The firm wants to determine how many of the two products
must be manufactured each week in order to maximize profit subject
only to resource availability.

Product1 P1 Product2 P2 Available

(per unit) (per unit) Resource
R1 3 2 60
R2 1 2 40
Unit Profit P5 P4 38
 P1 P2 Available
(per unit) (per unit) Resource
R1 3 2 60
R2 1 2 40
Unit Profit P5 P4

39
 Methods of Solving Linear
Programming Problems (LPP)
There are Two important methods of solving L.P.P. They are:

(1) Graphical method

(2) Simplex method

40
chapter 3: Linear Programming:
Graphical Solutions

41
 Example 1: A Maximization Problem
 LP Formulation

Max profit = 5x1 + 7x2

s.t. x1 < 6
2x1 + 3x2 < 19
x1 + x 2 < 8
x1, x2 > 0
42
 Example 1: Graphical Solution
 Constraint #1 Graphed
x2

6 x1 < 6
5

2
(6, 0)
1

x1
1 2 3 4 5 6 7 8 9 10

43
 Constraint #2 Graphed
x2

8
(0, 6 1/3)
7

4 2x1 + 3x2 < 19

3

2 (9 1/2, 0)
1

x1
1 2 3 4 5 6 7 8 9 10

44
 Example 1: Graphical Solution
 Constraint #3 Graphed
x2
(0, 8)
8

7
x1 + x2 < 8
6

1
(8, 0)
x1
1 2 3 4 5 6 7 8 9 10

45
 Example 1: Graphical Solution
 Combined-Constraint Graph
x2
x1 + x2 < 8
8

6 x1 < 6
5

3
2x1 + 3x2 < 19
2

x1
1 2 3 4 5 6 7 8 9 10

46
 Example 1: Graphical Solution
x2
 Feasible Solution Region
8

3
Feasible
2
Region
1

x1
1 2 3 4 5 6 7 8 9 10

47
 Example 1: Graphical Solution
x2
 Objective Function Line
8

7
(0, 5)
6 Objective Function
5 5x11 + 7x22 = 35
4

2
(7, 0)
1

x1
1 2 3 4 5 6 7 8 9 10

48
 Example 1: Graphical Solution
x2
 Optimal Solution
Objective Function
8
5x11 + 7x22 = 46
7

6
Optimal Solution
(x11 = 5, x22 = 3)
5

x1
1 2 3 4 5 6 7 8 9 10

49
 Extreme Points and the Optimal Solution
 The corners or vertices of the feasible region are
referred to as the extreme points.
 An optimal solution to an LP problem can be found
at an extreme point of the feasible region.
 When looking for the optimal solution, you do not
have to evaluate all feasible solution points.
 You have to consider only the extreme points of
the feasible region.

50
 Summary of the Graphical Solution Procedure
for Maximization Problems

 Prepare a graph of the feasible solutions for each of

the constraints.
 Determine the feasible region that satisfies all the
constraints simultaneously.
 Draw an objective function line.
 Move parallel objective function lines toward larger
objective function values without entirely leaving the
feasible region.
 Any feasible solution on the objective function line
with the largest value is an optimal solution.

51
 Slack and Surplus Variables
 A linear program in which all the variables are non-
negative and all the constraints are equalities is said to
be in standard form.
 Standard form is attained by adding slack variables to
"less than or equal to" constraints, and by subtracting
surplus variables from "greater than or equal to"
constraints.
 Slack and surplus variables represent the difference
between the left and right sides of the constraints.
 Slack and surplus variables have objective function
coefficients equal to 0.
52
 Example 1: Graphical Solution
Point Z
x2
 The Five Extreme Points (0,0) 0
8
(6,0) 30
7
5 (6,2) 44
6
(5,3) 46
5
(0,19/3) 44.33
4

3
4

2 Feasible 3
1
Region
1 2
1 2 3 4 5 6 7 8 9 10
x1
53
 A Maximization Problem
 Optimal Solution
Point Z
x2
(0,0) 0
8
(6,0) 30
7
(6,2) 44
6
Optimal
Optimal Solution
Solution (5,3) 46
5
(0,19/3) 44.33
4

x1
1 2 3 4 5 6 7 8 9 10

54
 Extreme Points and the Optimal Solution
 The corners or vertices of the feasible region
are referred to as the extreme points.
 An optimal solution to an LP problem can be
found at an extreme point of the feasible
region.
 When looking for the optimal solution, you do
not have to evaluate all feasible solution points.
 You have to consider only the extreme points of
the feasible region.

55
 Feasible Region
 The feasible region for a two-variable linear
programming problem can be nonexistent, a single
point, a line, a polygon, or an unbounded area.
 Any linear program falls in one of three categories:
– is infeasible
– has a unique optimal solution or alternate optimal solutions
– has an objective function that can be increased without
bound
 A feasible region may be unbounded and yet there may
be optimal solutions. This is common in minimization
problems and is possible in maximization problems.
56
 Special Cases
 Alternative Optimal Solutions
In the graphical method, if the objective function line
is parallel to a boundary constraint in the direction of
optimization, there are alternate optimal solutions,
with all points on this line segment being optimal.
 Infeasibility
A linear program which is overconstrained so that no
point satisfies all the constraints is said to be
infeasible.
 Unbounded
For a max (min) problem, an unbounded LP occurs in it is
possible to find points in the feasible region with
arbitrarily large (small) Z
57
 Example with Multiple Optimal Solutions

x2
z1 z2 z3
Maximize z = 3x1 – x2
4

3 subject to 15x1 – 5x2  30

2
10x1 + 30x2  120
1
x1  0, x2  0
0
0 1 2 3 4 x1

58
 Example: Infeasible Problem
 Solve graphically for the optimal solution:

Max z = 2x1 + 6x2

s.t. 4x1 + 3x2 < 12

2x1 + x2 > 8
x1, x2 > 0

59
 Example: Infeasible Problem
 There are no points that satisfy both constraints, hence this
problem has no feasible region, and no optimal solution.

x2

8 2x1 + x2 > 8

4x1 + 3x2 < 12

4

x1
3 4
60
 Example: Unbounded Problem
 Solve graphically for the optimal solution:

Max z = 3x1 + 4x2

s.t. x1 + x2 > 5
3x1 + x2 > 8

x1, x2 > 0

61
 Example 2: A Minimization Problem
 LP Formulation

Min 5x1 + 2x2

s.t. 2x1 + 5x2 > 10
4x1 - x2 > 12
x1 + x2 > 4
x1, x2 > 0
62
 Example 2: Graphical Solution
 Graph the Constraints
Constraint 1: When x1 = 0, then x2 = 2; when x2 = 0,
then x1 = 5. Connect (5,0) and (0,2). The ">" side is
above this line.
Constraint 2: When x2 = 0, then x1 = 3. But setting x1
to 0 will yield x2 = -12, which is not on the graph.
Thus, to get a second point on this line, set x1 to any
number larger than 3 and solve for x2: when x1 = 5,
then x2 = 8. Connect (3,0) and (5,8). The ">" side is
to the right.
Constraint 3: When x1 = 0, then x2 = 4; when x2 = 0,
then x1 = 4. Connect (4,0) and (0,4). The ">" side is
above this line. 63
 Example 2: Graphical Solution
 Constraints
x22 Graphed Feasible Region

4x11 - x22 > 12

55

44 x11 + x22 > 4

33
2x11 + 5x22 > 10
22

11
x11
11 22 33 44 55 66

64
 Example 2: Graphical Solution
 Graph the Objective Function
Set the objective function equal to an arbitrary
constant (say 20) and graph it. For 5x1 + 2x2 = 20,
when x1 = 0, then x2 = 10; when x2= 0, then x1 = 4.
Connect (4,0) and (0,10).
 Move the Objective Function Line Toward Optimality
Move it in the direction which lowers its value
(down), since we are minimizing, until it touches the
last point of the feasible region, determined by the
last two constraints.
65
 Example 2: Graphical Solution
 Objective
x22 Function Graphed Min z = 5x11 + 2x22

4x11 - x22 > 12

5

4 x11 + x22 > 4

3
2x11 + 5x22 > 10
2

1
x11
1 2 3 4 5 6

66
 Example 2: Graphical Solution
 Solve for the Extreme Point at the Intersection of
the Two Binding Constraints
4x1 - x2 = 12
x1+ x2 = 4
Adding these two equations gives:
5x1 = 16 or x1 = 16/5.
Substituting this into x1 + x2 = 4 gives: x2 = 4/5

67
 Example 2: Graphical Solution
 Solve for the Optimal Value of the Objective
Function
Solve for z = 5x1 + 2x2 = 5(16/5) + 2(4/5) = 88/5.
Thus the optimal solution is
x1 = 16/5; x2 = 4/5; z = 88/5

68
 Example 2: Graphical Solution

 Optimal Solution
x22 Min z = 5x11 + 2x22

4x11 - x22 > 12

5

4 x11 + x22 > 4

3 2x11 + 5x22 > 10

2
Optimal: x11 = 16/5
1 x22 = 4/5
x11
1 2 3 4 5 6
 Feasible Region
 The feasible region for a two-variable linear
programming problem can be nonexistent, a single
point, a line, a polygon, or an unbounded area.
 Any linear program falls in one of three categories:
– is infeasible
– has a unique optimal solution or alternate optimal
solutions
– has an objective function that can be increased
without bound
 A feasible region may be unbounded and yet there may
be optimal solutions. This is common in minimization
problems and is possible in maximization problems. 70
 More examples on Special Cases
 Alternate Optimal Solutions
In the graphical method, if the objective function line
is parallel to a boundary constraint in the direction of
optimization, there are alternate optimal solutions,
with all points on this line segment being optimal.
 Infeasibility
A linear program which is overconstrained so that no
point satisfies all the constraints is said to be
infeasible.
 Unboundedness
(See example on upcoming slide.) 71
 Example: Infeasible Problem
 Solve graphically for the optimal solution:

Max 2x1 + 6x2

s.t. 4x1 + 3x2 < 12
2x1 + x2 > 8
x1, x2 > 0

72
 Example: Infeasible Problem
 There are no points that satisfy both constraints,
hence this problem has no feasible region, and no
optimal solution.
x2

8 2x1 + x2 > 8

4x1 + 3x2 < 12

4

x1
3 4
73
 Example: Unbounded Problem
 Solve graphically for the optimal solution:

Max 3x1 + 4x2

s.t. x1 + x 2 > 5
3x1 + x2 > 8
x1, x2 > 0

74
 Example: Unbounded Problem
 The feasible region is unbounded and the
objective function line can be moved parallel to
itself without bound
x2 so that z can be increased
infinitely. 3x + x > 8
1 2

8
Max 3x1 + 4x2

5
x1 + x2 > 5

x1
2.67 5
75
 Unit 4:
Linear Programming:
the Simplex Method
76
The most frequently used method to solve LP problems is the
Simplex Method. Before going into the method, we must get
familiarized with some important terminologies :
Standard Form- A linear program in which all the constraints are
written as equalities.
Slack Variable- A variable added to the LHS of “Less than or equal
to” constraint to convert it into an equality.
Surplus Variable- A variable subtracted from the LHS of
“More than or equal to” constraint to convert it into an equality.
Basic Solution- For a system of m linear equations in n variables
(n>m),a solution obtained by setting (n-m) variables equal to zero
and solving the system of equations for
remaining m variables.
Basic Feasible Solution(BFS)- If all the variables in basic solution
are more than or equal to zero.
77
Optimum Solution- Any BFS which optimizes(maximizes or
minimizes) the objective function.
Tableau Form- When a LPP is written in a tabular form prior to
setting up the Initial Simplex Tableau.
Simplex Tableau- A table which is used to keep track of the
calculations made at each iteration when the simplex method is
employed.
Net EvaluationRow(Cj-Zj )- The row containing net profit or loss.
The numbers in this row are also known as shadow prices.
Pivotal Column- The column having largest positive(or negative)
value in the Net Evaluation Row for a maximization(or
minimization) problem.
Pivotal Row- The row corresponding to variable that will leave
the table in order to make room for another variable.
Pivotal Element- Element at the intersection of pivotal row and
pivotal column.
78
 Simplex: a linear-programming algorithm that can solve

problems having more than two decision variables.

 The simplex technique involves generating a series of
solutions in tabular form, called tableaus. By inspecting
the bottom row of each tableau, one can immediately tell
if it represents the optimal solution.
 Each tableau corresponds to a corner point of the
feasible solution space.
 The first tableau corresponds to the origin. Subsequent
tableaus are developed by shifting to an adjacent corner
point in the direction that yields the highest (smallest)
rate of profit (cost). This process continues as long as a
positive (negative) rate of profit (cost) exists.
the simplex method is an iterative algorithm (a
systematic solution procedure that keeps
repeating a fixed series of steps, called, an
iteration, until a desired result has been
obtained) with the following structure:
 Simplex algorithm

Initialization: setup to start iterations, including

finding an initial CPF solution

Optimality test: is the current CPF solution

optimal?

if no if yes stop

Iteration: Perform an iteration to find a

better CFP solution
The simplex method in tabular form

 Steps:
1. Initialization:

a. transform all the constraints to equality by introducing

slack, surplus, and artificial variables as follows:

Constraint type Variable to be added

≥ + slack (s)

≤ - Surplus (s) + artificial (A)

= + Artificial (A)
Simplex method in tabular form

b. Construct the initial simplex tableau

Basic X1 … Xn S1 …... Sn A1 …. An RHS

variable
S b1
Coefficient of the constraints

A bm
Z Objective function coefficient Z value
In different signs
 Simplex method in tabular form

2. Test for optimality:

Case 1: Maximization problem
the current BF solution is optimal if every coefficient in the
objective function row is nonnegative
Case 2: Minimization problem
the current BF solution is optimal if every coefficient in the
objective function row is nonpositive
 Simplex method in tabular form

3. Iteration

Step 1: determine the entering basic variable by selecting the

variable (automatically a nonbasic variable) with the most
negative value (in case of maximization) or with the most positive
(in case of minimization) in the last row (Z-row). Put a box around
the column below this variable, and call it the “pivot column”
 Simplex method in tabular form

 Step 2: Determine the leaving basic variable by

applying the minimum ratio test as following:
1. Pick out each coefficient in the pivot column that is
strictly positive (>0)
2. Divide each of these coefficients into the right hand
side entry for the same row
3. Identify the row that has the smallest of these ratios
4. The basic variable for that row is the leaving variable,
so replace that variable by the entering variable in the
basic variable column of the next simplex tableau. Put a
box around this row and call it the “pivot row”
 Simplex method in tabular form

 Step 3: Solve for the new BF solution by using elementary

row operations (multiply or divide a row by a nonzero
constant; add or subtract a multiple of one row to another
row) to construct a new simplex tableau, and then return to
the optimality test. The specific elementary row operations
are:
1. Divide the pivot row by the “pivot number” (the number in
the intersection of the pivot row and pivot column)
2. For each other row that has a negative coefficient in the
pivot column, add to this row the product of the absolute
value of this coefficient and the new pivot row.
3. For each other row that has a positive coefficient in the pivot
column, subtract from this row the product of the absolute
value of this coefficient and the new pivot row.
 Simplex method

 Example (All constraints are )

Solve the following problem using the simplex method
 Maximize
Z = 3X1+ 5X2
Subject to
X1  4
2 X2  12
3X1 +2X2  18
X1 , X2  0
 Simplex method

 Solution
 Initialization
1. Standard form
Maximize Z,
Subject to Sometimes it is called the
augmented form of the
Z - 3X1- 5X2 =0
problem because the
original form has been
X1 + S1 = 4 augmented by some
supplementary variables
2 X2 + S2 = 12
needed to apply the
3X1 +2X2 + S3 = 18 simplex method
X1 , X2, S1, S2, S3  0
 Definitions
 A basic solution is an augmented corner point solution.
 A basic solution has the following properties:
1. Each variable is designated as either a nonbasic variable
or a basic variable.
2. The number of basic variables equals the number of
functional constraints. Therefore, the number of nonbasic
variables equals the total number of variables minus the
number of functional constraints.
3. The nonbasic variables are set equal to zero.
4. The values of the basic variables are obtained as
simultaneous solution of the system of equations
(functional constraints in augmented form). The set of
basic variables are called “basis”
5. If the basic variables satisfy the nonnegativity constraints,
the basic solution is a Basic Feasible (BF) solution.
Initial tableau
Entering
2. Initial tableau variable

Basic X1 X2 S1 S2 S3 RHS
variable
S1 1 0 1 0 0 4
S2 0 2 0 1 0 12
S3 3 2 0 0 1 18
Z -3 -5 0 0 0 0

Leaving Pivot row

Pivot column
variable Pivot
number
 Simplex tableau

Notes:

 The basic feasible solution at the initial tableau is (0, 0, 4, 12,

18) where:

X1 = 0, X2 = 0, S1 = 4, S2 = 12, S3 = 18, and Z = 0

Where S1, S2, and S3 are basic variables

X1 and X2 are nonbasic variables

 The solution at the initial tableau is associated to the origin point

at which all the decision variables are zero.
 Optimality test

By investigating the last row of the initial

tableau, we find that there are some
negative numbers.

Therefore, the current solution is not

optimal
 Iteration

 Step 1: Determine the entering variable by selecting

the variable with the most negative in the last row.

 From the initial tableau, in the last row (Z row), the

coefficient of X1 is -3 and the coefficient of X2 is -5;
therefore, the most negative is -5.

 consequently, X2 is the entering variable.

 X2 is surrounded by a box and it is called the pivot

column
Iteration

 Step 2: Determining the leaving variable by using the

minimum ratio test as following:

Basic Entering RHS Ratio

variable variable X2
(1) (2) (2)(1)
S1 0 4 None
S2 2 12 6
Leaving Smallest ratio
S3 2 18 9
Iteration

 Step 3: solving for the new BF solution by using the

eliminatory row operations as following:
1. New pivot row = old pivot row  pivot number
Basic X1 X2 S1 S2 S3 RHS
variable
S1
X2 0 1 0 1/2 0 6
S3
Z
Note that X2 becomes in the basic
variables list instead of S2
 iteration
2. For the other row apply this rule:
New row = old row – the coefficient of this row in the pivot column (new pivot row).
For S1

1 0 1 0 0 4
-
0 (0 1 0 1/2 0 6)
1 0 1 0 0 4
For S3

3 2 0 0 1 18
-
2 (0 1 0 1/2 0 6)
3 0 0 -1 1 6
for Z
-3 -5 0 0 0 0
- Substitute this
-5(0 1 0 1/2 0 6)
-3 0 0 5/2 0 30
values in the table
Iteration
This solution is not optimal, since there is a negative numbers in the last row

Basic X1 X2 S1 S2 S3 RHS
variable
S1 1 0 1 0 0 4
X2 0 1 0 1/2 0 6
S3 3 0 0 -1 1 6
Z -3 0 0 5/2 0 30

The smallest ratio is

The most negative
6/3 =2; therefore, S3 is
value; therefore, X1
the leaving variable
is the entering
variable
Iteration

 Apply the same rules we will obtain this solution:

Basic X1 X2 S1 S2 S3 RHS
variable
S1 0 0 1 1/3 -1/3 2
X2 0 1 0 1/2 0 6
X1 1 0 0 -1/3 1/3 2
Z 0 0 0 3/2 1 36
This solution is optimal; since there is no negative solution in the
last row: basic variables are X1 = 2, X2 = 6 and S1 = 2; the nonbasic
variables are S2 = S3 = 0
Z = 36
 The Simplex Method (3)
Example: Product Mix Problem
The N. Dustrious Company produces two products: I and II. The raw material
requirements, space needed for storage, production rates, and selling prices for
these products are given below:

The total amount of raw material available per day for both products is 15751b.
The total storage space for all products is 1500 ft2, and a maximum of 7 hours
per day can be used for production. The company wants to determine how
many units of each product to produce per day to maximize its total
income.
 The Simplex Method (4)
Solution
 Step 1: Convert all the inequality constraints into equalities by the
use of slack variables. Let:

As already developed, the LP model is:

…..Eq (4)
 The Simplex Method (5)
 Introducing these slack variables into the inequality constraints and
rewriting the objective function such that all variables are on the left-
hand side of the equation. Equation 4 can be expressed as:

…..Eq (5)
 The Simplex Method (6)

 Since the coefficients of x1 and x2 in Eq. (A1) are both negative, the
value of Z can be increased by giving either x1 or x2 some positive
value in the solution.
 In Eq. (B1), if x2 = S1 = 0, then x1 = 1500/4 = 375. That is, there is only
sufficient storage space to produce 375 units at product I.
 From Eq. (C1), there is only sufficient raw materials to produce 1575/5
= 315 units of product I.
 From Eq. (D1), there is only sufficient time to produce 420/1 = 420
units of product I.
 Therefore, considering all three constraints, there is sufficient resource
to produce only 315 units of x1. Thus the maximum value of x1 is
limited by Eq. (C1).
 The Simplex Method (7)

 Step 2: From Equation CI, which limits the maximum value of

x1 .

…..Eq (6)

Substituting this equation into Eq. (5) yields the following new formulation
of the model.

…..Eq (7)
 The Simplex Method (8)
 It is now obvious from these equations that the
new feasible solution is:

x1 = 315, x2 = 0, S1 = 240, S2 = 0, S3 = 105, and

Z = 4095

 It is also obvious from Eq.(A2) that it is also not

the optimum solution. The coefficient of x1 in the
objective function represented by A2 is
negative ( -16/5), which means that the value of
Z can be further increased by giving x2 some
positive value.
 The Simplex Method (9)

 Following the same analysis procedure used in step 1,

it is clear that:

 In Eq. (B2), if S1 = S1 = 0, then x2 = (5/13)(240) = 92.3.

 From Eq. (C2), x2 can take on the value (5/3 )(315) =

525 if x1 = S2 = 0

 From Eq. (D2), x2 can take on the value (5/7)(105) =

75 if S2 = S3 = 0

 Therefore, constraint D2 limits the maximum value of x2

to 75. Thus a new feasible solution includes x 2 = 75,
S2 = S3 = 0.
 The Simplex Method (10)
 Step 3: From Equation D2:
…..Eq (8)

Substituting this equation into Eq. (7) yield:

…..Eq (9)

From these equations, the new feasible solution is readily found to be: x1
= 270, x2 = 75, S1 = 45, S2 = 0, S3 = 0, Z = 4335.
 The Simplex Method (11)

Because the coefficients in the objective

function represented by Eq. (A3) are all positive,
this new solution is also the optimum solution.
 Simplex Tableau for Maximization (1)

 Step I: Set up the initial tableau using Eq. (5).

…..Eq (5)

In any
iteration, a
variable that
has a nonzero
value in the
solution is
called a basic
variable.
 Simplex Tableau for Maximization (2)

 Step II: . Identify the variable that will be assigned a nonzero value in
the next iteration so as to increase the value of the objective function.
This variable is called the entering variable.
 It is that nonbasic variable which is associated with the smallest
negative coefficient in the objective function.
 If two or more nonbasic variables are tied with the smallest
coefficients, select one of these arbitrarily and continue.

 Step III: Identify the variable, called the leaving variable, which will be
changed from a nonzero to a zero value in the next solution.
 Simplex Tableau for Maximization (3)
 Step IV: . Enter the basic variables for the second tableau. The row
sequence of the previous tableau should be maintained, with the
leaving variable being replaced by the entering variable.
 Simplex Tableau for Maximization (4)
 Step V: Compute the coefficients for the second tableau. A sequence
of operations will be performed so that at the end the x1 column in the
second tableau will have the following coefficients:

The second tableau yields the following feasible solution:

x1 = 315, x2 = 0, SI = 240, S2 = 0, S3 = 105, and Z = 4095
 Simplex Tableau for Maximization (5)
 The row operations proceed as fo1lows:

 The coefficients in row C2 are obtained by dividing the corresponding

coefficients in row C1 by 5.

 The coefficients in row A2 are obtained by multiplying the coefficients of

row C2 by 13 and adding the products to the corresponding coefficients in
row Al.

 The coefficients in row B2 are obtained by multiplying the coefficients of

row C2 by -4 and adding the products to the corresponding coefficients in
row Bl.

 The coefficients in row D2 are obtained by multiplying the coefficients of

row C2 by -1 and adding the products to the corresponding coefficients in
row Dl.
 Simplex Tableau for Maximization (6)

 Step VI: Check for optimality. The second feasible solution is also not
optimal, because the objective function (row A2) contains a negative
coefficient. Another iteration beginning with step 2 is necessary.

 In the third tableau (next slide), all the coefficients in the objective
function (row A3) are positive. Thus an optimal solution has been
reached and it is as follows:

x1 = 270, x2 = 75, SI = 45, S2 = 0, S3 = 0, and Z = 4335

Unit 5: Simplex: Maximization With Mixed
Constraints And Minimization
 Simplex method incase of Artificial variables
“Big M method”
 Solve the following linear programming problem by using the
simplex method:
 Min Z =2 X1 + 3 X2
S.t.
½ X1 + ¼ X2 ≤ 4
X1 + 3X2  20
X1 + X2 = 10
X1, X2  0
 Big M method

 Solution
Step 1: standard form
Min Z,
s.t.
Z – 2 X1 – 3 X2 - M A1 -M A2 =0
½ X1 + ¼ X2 + S1 =4
X1 + 3X2 - S 2 + A1 = 20
X1 + X2 + A 2 = 10
X1, X2 ,S1, S2, A1, A2  0
Where: M is a very large number
 Big M method

 Notes
M, a very large number, is used to ensure that the values of A1 and A2, …, and An will
be zero in the final (optimal) tableau as follows:
1. If the objective function is Minimization, then A1, A2, …, and An must be added to
the RHS of the objective function multiplied by a very large number (M).
Example: if the objective function is Min Z = X1+2X2, then the obj. function should be
Min Z = X1 + X2+ MA1 + MA2+ …+ MAn
OR
Z – X1 - X2- MA1 - MA2- …- MAn = 0

2. If the objective function is Maximization, then A1, A2, …, and An must be subtracted
from the RHS of the objective function multiplied by a very large number (M).
Example: if the objective function is Max Z = X1+2X2, then the obj. function should be
Max Z = X1 + X2- MA1 - MA2- …- MAn
OR
Z - X1 - X2+ MA1 + MA2+ …+ MAn = 0

N.B.: When the Z is transformed to a zero equation, the signs are changed
Big M method

 Step 2: Initial tableau

Basic X1 X2 S1 S2 A1 A2 RHS
variables
2 3 0 0 M M

S1 ½ ¼ 1 0 0 0 4
A1 1 3 0 -1 1 0 20
A2 1 1 0 0 0 1 10
Z -2 -3 0 0 -M -M 0

Note that one of the simplex rules is violated, which is the basic variables A1, and A2
have a non zero value in the z row; therefore, this violation must be corrected before
proceeding in the simplex algorithm as follows.
 Big M method

 To correct this violation before starting the simplex algorithm, the

elementary row operations are used as follows:
New (Z row) = old (z row) ± M (A1 row) ± M (A2 row)
In our case, it will be positive since M is negative in the Z
row, as following:
Old (Z row): -2 -3 0 0 -M -M 0
M (A1 row): M 3M 0 -M M o 20M
M (A2 row): M M 0 0 0 M 10M
New (Z row):2M-2 4M-3 0 -M 0 0 30M

It becomes zero
Big M method

 The initial tableau will be:

Basic X1 X2 S1 S2 A1 A2 RHS
variables
2 3 0 0 M M

S1 1/2 1/4 1 0 0 0 4
A1 1 3 0 -1 1 0 20
A2 1 1 0 0 0 1 10
Z 2M-2 4M-3 0 -M 0 0 30M

• Since there is a positive value in the last row, this solution is not optimal
• The entering variable is X2 (it has the most positive value in the last row)
• The leaving variable is A1 (it has the smallest ratio)
Big M method

 First iteration

Basic X1 X2 S1 S2 A1 A2 RHS
variables
2 3 0 0 M M

S1 5/12 0 1 1/12 -1/12 0 7/3

X2 1/3 1 0 -1/3 1/3 0 20/3

A2 2/3 0 0 1/3 -1/3 1 10/3

Z 2/3M-1 0 0 1/3M-1 1-4/3M 0 20+10/3M

• Since there is a positive value in the last row, this solution is not optimal
• The entering variable is X1 (it has the most positive value in the last row)
• The leaving variable is A2 (it has the smallest ratio)
Big M method

 Second iteration
Basic X1 X2 S1 S2 A1 A2 RHS
variables
S1 0 0 1 -1/8 1/8 -5/8 1/4

X2 0 1 0 -1/2 1/2 -1/2 5

X1 1 0 0 1/2 -1/2 3/2 5

Z 0 0 0 -1/2 ½-M 3/2-M 25

This solution is optimal, since there is no positive value in the last row. The optimal
solution is:
X1 = 5, X2 = 5, S1 = ¼
A1 = A2 = 0 and Z = 25
 Note for the Big M method

 In the final tableau, if one or more artificial variables (A1, A2, …)

still basic and has a nonzero value, then the problem has an
infeasible solution.
 All other notes are still valid in the Big M method.
 Special cases

 In the final tableau, if one or more artificial variables (A1, A2, …)

still basic and has a nonzero value, then the problem has an
infeasible solution
 If there is a zero under one or more nonbasic variables in the last
tableau (optimal solution tableau), then there is a multiple optimal
solution.
 When determining the leaving variable of any tableau, if there is
no positive ratio (all the entries in the pivot column are negative
and zeroes), then the solution is unbounded.
 Simplex method when some constraints
are not “≤” constraints (cont.)
Example:

Max 16x1+15x2+20x3-18x4
ST
2x1 + x2 + 3x3 ≤ 3000 [1]
3x1 + 4x2 + 5x3 – 60x4 ≤ 2400 [2]
x4 ≤ 32 [3]
X2 ≥ 200 [4]
X1 + x2 + x3 ≥ 800 [5]
X1 – x2 –x3 =0 [6]
Xj ≥ 0 for all J

126
 Simplex method when some constraints
are not “≤” constraints (cont.)
Example:
We assign a very large negative
Max 16x1+15x2+20x3-18x4 objective function coefficient , -M ,
( +M for minimization problem) to
ST each artificial variable
2x1 + x2 + 3x3 ≤ 3000 [1]
3x1 + 4x2 + 5x3 – 60x4 ≤ 2400 [2]
x4 ≤ 32 [3]
X2 ≥ 200 [4] We add artificial :
X1 + x2 + x3 ≥ 800 [5] R4, R5, R6, respectively
X1 – x2 –x3 =0 [6] to the fourth, fifth, and
Xj ≥ 0 for all J sixth equations.

127
 Simplex method when some constraints
are not “≤” constraints (cont.)
The solution
Max 16x1+15x2+20x3-18x4
–MR4 –MR5 –MR6
ST
2x1 + x2 + 3x3 + s1= 3000 [1]
3x1 + 4x2 + 5x3 – 60x4 + s2 = 2400 [2]
x4 + s3 = 32 [3]
X2 – s4 + R4 = 200 [4]
X1 + x2 + x3 – s5 + R5 = 800 [5]
X1 – x2 –x3 + R6= 0 [6]
Xj ≥ 0 , Sj ≥ 0, Rj ≥ 0 for all J
The simplex algorithm can then be used to solve this problem
128
 Solving For the optimal solution of [Maximization]
when there are artificial variables
Example # 1:

MAX 2x1+ 5x2

ST
X1 ≥ 4
x1 + 4x2≤ 32
3x1+ 2x2 = 24

129
 Solving For the optimal solution of [Maximization]
when there are artificial variables (cont.)
The Solution
• By adding the appropriate slack, surplus, and artificial
variables, we obtain the following:

MAX 2x1 + 5x2 –MR1 – MR3

ST
X1 – s1 + R1 =4
X1 + 4x2 + s2 = 32
3x1 + 2x2 + R3= 24

X1,x2,s1,s2,R1,R3 ≥ 0

130
 Solving For the optimal solution of [Maximization]
when there are artificial variables (cont.)

The initial table :

Basis X1 X2 S1 S2 R1 R3 RHS
R1 1 0 -1 0 1 0 4
R1, S2, R3 are
S2 1 4 0 1 0 0 32 basic
variables.
R3 3 2 0 0 0 1 24
Z -2 -5 0 0 +M +M 0
• Make z consistent; (R1, R3) in z-row coefficient (+M,+M) it must be zero; By apply:

New z-row = old z-row + ( -M * R1 row – M * R3 row)

MAX objective function
New z-row = old z-row + ( M * R1 row +M * R3 row)
MIN objective function
131
 Solving For the optimal solution of [Maximization]
when there are artificial variables (cont.)
• Starting table:

Basis X1 X2 S1 S2 R1 R3 RHS
R1 1 0 -1 0 1 0 4
S2 1 4 0 1 0 0 32
R3 3 2 0 0 0 1 24
Z -2-4M -5-2M +M 0 -M -M -28M

132
 Solving For the optimal solution of [Maximization]
when there are artificial variables (cont.)
• To determine Entering Variable; We should look to the largest negative
number in z-row.

Entering Variable

Basis X1 X2 S1 S2 R1 R3 RHS
R1 1 0 -1 0 1 0 4
S2 1 4 0 1 0 0 32
R3 3 2 0 0 0 1 24
Z -2-4M -5-2M +M 0 -M -M -28M

Largest negative number

133
 Solving For the optimal solution of [Maximization]
when there are artificial variables (cont.)

• Calculate the ratio; then, determine the smallest positive

number as Leaving Variable
Leaving Variable

Basis X1 X2 S1 S2 R1 R3 RHS Ratio

R1 1 0 -1 0 1 0 4 4
S2 1 4 0 1 0 0 32 32
R3 3 2 0 0 0 1 24 8
Z -2-4M -5-2M +M 0 -M -M -28M

• Pivot element = ( 1, 0, -1, 0, 1, 0, 4)/ (1)

( 1, 0, -1, 0, 1, 0, 4)
134
 Solving For the optimal solution of [Maximization]
when there are artificial variables (cont.)
• First iteration

Entering Variable Leaving Variable

Basis X1 X2 S1 S2 R1 R3 RHS Ratio

X1 1 0 -1 0 1 0 4 ….
S2 0 4 1 1 -1 0 28 28
R3 0 2 3 0 -3 1 12 4
Z 0 -5-2M -2-3M 0 2+3M -M 8-12M

135
 Solving For the optimal solution of [Maximization]
when there are artificial variables (cont.)
• Second iteration

Entering Variable Leaving Variable

Basis X1 X2 S1 S2 R1 R3 RHS Ratio

X1 1 2/3 0 0 0 1/3 8 12
S2 0 10/3 0 1 0 -1/3 24 7.2
S1 0 2/3 1 0 -1 1/3 4 6
Z 0 -11/3 0 0 0 2/3 +16

136
 Solving For the optimal solution of [Maximization]
when there are artificial variables (cont.)
• Third iteration

Basis X1 X2 S1 S2 R1 R3 RHS Ratio

X1 1 0 -1 0 1 0 4
S2 0 0 -5 1 5 -2 4
X2 0 1 3/2 0 -3/2 1/2 6
Z 0 0 11/3 0 -11/2 5/2 38

137
 Solving For the optimal solution of [Maximization] when
there are artificial variables (cont.)

points Classification Reason

X1=0, X2=0 Not Feasible R1, R3 both Positive (4, 24)
X1=4, X2=0 Not Feasible R3 positive= 12
X1=8, X2=0 Feasible but not optimal X2 is negative
X1=4, X2=6 Feasible and optimal All x1,X2 ≥0

138
 Solving For the optimal solution of [Minimization]
when there are artificial variables
Example # 2:

Min 4x1 + x2
ST
3x1+ x2 = 3
4x1 + 3x2 ≥ 6
X1+ 2x2 ≤ 4
X1, x2 ≥ 0

139
 Solving For the optimal solution of [Minimization]
when there are artificial variables (cont.)
The Solution
• By adding the appropriate slack, surplus, and artificial
variables, we obtain the following:

Min 4x1 + x2 + MR1 + MR2

ST
3x1+ x2 + R1= 3
4x1 + 3x2 –s1 + R2 = 6
X1+ 2x2 + s2 = 4
X1, x2 , s1, s2, R1, R2≥ 0

140
 Solving For the optimal solution of [Minimization]
when there are artificial variables (cont.)
• The initial table:

Basis X1 X2 S1 R1 R2 S2 RHS
R1 3 1 0 1 0 0 3
R2 4 3 -1 0 1 0 6
S2 1 2 0 0 0 1 4
Z -4 -1 0 -M -M 0 0

• New z-row = old z-row +( M * R1 row +M * R3

row)

141
 Solving For the optimal solution of [Minimization]
when there are artificial variables (cont.)
• Starting table: Leaving Variable

Entering Variable

Basis X1 X2 S1 R1 R2 S2 RHS
R1 3 1 0 1 0 0 3
R2 4 3 -1 0 1 0 6
S2 1 2 0 0 0 1 4
Z -4+7M -1+4M -M 0 0 0 9M

142
 Solving For the optimal solution of [Minimization]
when there are artificial variables (cont.)
• First iteration
Leaving Variable
Entering Variable

Basis X1 X2 S1 R1 R2 S2 RHS
X1 1 1/3 0 1/3 0 0 1
R2 0 5/3 -1 -4/3 1 0 2
S2 0 5/3 0 -1/3 0 1 3
Z 0 (1+5M)/3 -M (4-7M)/3 0 0 4+2M

143
 Solving For the optimal solution of [Minimization]
when there are artificial variables (cont.)
• Second iteration
Entering Variable
Leaving Variable
Basis X1 X2 S1 R1 R2 S2 RHS
X1 1 0 1/5 3/5 -1/5 0 3/5
X2 0 1 -3/5 -4/5 3/5 0 6/5
S2 0 0 1 1 -1 1 1
Z 0 0 1/5 8/5 - M -1/5 -M 0 18/5

144
 Solving For the optimal solution of [Minimization]
when there are artificial variables (cont.)
• Third iteration

Basis X1 X2 S1 R1 R2 S2 RHS
X1 1 0 0 2/5 0 -1/5 2/5
X2 0 1 0 -1/5 0 3/5 9/5
s1 0 0 1 1 -1 1 1
Z 0 0 0 7/5 – M -M -1/5 17/5

• Optimal solution : x1= 2/5, x2= 9/5, z= 17/5

145
 Simplex Algorithm – Special cases
(review)
• There are four special cases arise in the use of the
simplex method.

1. Degeneracy
2. Alternative optima
3. Unbounded solution
4. Nonexisting ( infeasible ) solution

146
 Simplex Algorithm – Special cases (cont.)
1. Degeneracy ( no improve in objective)

• It typically occurs in a simplex iteration when in the

minimum ratio test more than one basic variable
determine 0, hence two or more variables go to 0, whereas
only one of them will be leaving the basis.

• This is in itself not a problem, but making simplex

iterations from a degenerate solution may give rise to
cycling, meaning that after a certain number of iterations
without improvement in objective value the method may
turn back to the point where it started.
147
Simplex Algorithm – Special cases (cont.)
Example:
Max 3x1 + 9x2
ST
X1 + 4x2 ≤ 8
X1 + 2x2 ≤ 4
X1, x2 ≥ 0

148
 Simplex Algorithm – Special cases (cont.)
The solution:
• The constraints:
X1 + 4x2 + s1= 8
X1 + 2x2 + s2= 4
X1, x2 ,s1,s2≥ 0

149
Simplex Algorithm – Special cases (cont.)

Entering Variable Leaving Variable

Basis X1 X2 S1 S2 RHS
s1 1 4 1 0 8
s2 1 2 0 1 4
Z -3 -9 0 0 0

150
Simplex Algorithm – Special cases (cont.)

Entering Variable Leaving Variable

Basis X1 X2 S1 S2 RHS
X2 1/4 1 1/4 0 2
s2 ½ 0 -1/2 1 0
Z -3/4 0 2/4 0 18

151
 Simplex Algorithm – Special cases (cont.)

Basis X1 X2 S1 S2 RHS
X2 0 1 ½ -1/2 2
X1 1 0 -1 2 0
Z 0 0 3/2 3/2 18

• Same objective no change and improve ( cycle)

• It is possible to have no improve and no termination
for computation.
152
 Simplex Algorithm – Special cases (cont.)
2. Alternative optima

• If the z-row value for one or more nonbasic

variables is 0 in the optimal tubule, alternate
optimal solution is exist.

153
Simplex Algorithm – Special cases (cont.)
Example:

Max 2x1+ 4x2

ST
X1 + 2x2 ≤ 5
X1 + x2 ≤ 4
X1, x2 ≥0

154
 Simplex Algorithm – Special cases (cont.)
The solution

Max 2x1+ 4x2

ST
X1 + 2x2 + s1= 5
X1 + x2 + s2 = 4
X1, x2, s1, s2 ≥0

155
Simplex Algorithm – Special cases (cont.)

Entering Variable Leaving Variable

Basis X1 X2 S1 S2 RHS
s1 1 2 1 0 4
s2 1 1 0 1 5
Z -2 -4 0 0 0

156
 Simplex Algorithm – Special cases (cont.)
• Optimal solution is 10 when x2=5/2, x1=0.

Basis X1 X2 S1 S2 RHS
x2 1/2 1 1/2 0 5/2
s2 1/2 0 -1/2 1 3/2
Z 0 0 2 0 10

• How do we know from this tubule that alternative

optima exist ?
157
 Simplex Algorithm – Special cases (cont.)
• By looking at z-row coefficient of the nonbasic
variable.
Entering Variable
Leaving Variable

Basis X1 X2 S1 S2 RHS
x2 1/2 1 1/2 0 5/2
s2 1/2 0 -1/2 1 3/2
Z 0 0 2 0 10
• The coefficient for x1 is 0, which indicates that x1 can
enter the basic solution without changing the value of
z.

158
 Simplex Algorithm – Special cases (cont.)
• The second alternative optima is:

Basis X1 X2 S1 S2 RHS
x2 0 1 1 -1 1
x1 1 0 -1 2 3
Z 0 0 2 0 10

• The new optimal solution is 10 when x1=3, x2=1

159
Simplex Algorithm – Special cases (cont.)
3. Unbounded solution

• It occurs when nonbasic variables are

zero or negative in all constraints
coefficient (max) and variable
coefficient in objective is negative

160
Simplex Algorithm – Special cases (cont.)
Example

Max 2x1+ x2
ST
X1 – x2 ≤10
2x1 ≤ 40
X1, x2≥0

161
 Simplex Algorithm – Special cases (cont.)
The solution

Max 2x1+ x2
ST
X1 – x2 +s1= 10
2x1 +s2= 40
X1, x2,s1,s2≥0

162
 Simplex Algorithm – Special cases (cont.)

Basis X1 X2 S1 S2 RHS
x2 1 -1 1 0 10
x1 2 0 0 1 40
Z -2 -1 0 0 0

• All value if x2( nonbasic variable) either zero or

negative.
• So, solution space is unbounded

163
 Simplex Algorithm – Special cases (cont.)
4. Infeasible solution
• R coefficient at end ≠ 0
• This situation can never occur if all the
constraints are of the type “≤” with
nonnegative RHS

164
Unit 6: Post-optimality analysis

165
Usefulness of Sensitivity Analysis

When solving an LP model we assume

that all relevant factors are known with
certainty.
However, such certainty rarely exists, so
sensitivity analysis helps assess the
robustness of a solution

166
 Usefulness of Sensitivity Analysis (cont.)

Sensitivity analysis helps answer

questions about how the optimal solution
changes given various changes of inputs
• Objective function coefficients
• Right hand side constants
• Addition or deletion of decision variables

167
 Approaches to Sensitivity Analysis

1. Change the data and re-solve the model

(sometimes this is the only practical approach)
2. Perform ad-hoc “one-way” sensitivity analyses (by
hand or using LINDO)
 Ranges of Optimality (for objective function coefficients
and dual prices )
 Dual Prices
 Reduced Costs

168
 Sensitivity Analysis Areas

Objective function coefficients (shifting

slope of objective function)
RHS constants (enlarging, shrinking
feasible region)
Changing the optimal solution by adding a
“non-basic” variable (reduced costs)

169
 Blue Ridge Hot Tubs

MAX Z = 350X1 + 300X2 } profit

S.T.:
1X1 + 1X2 <= 200 } pumps
9X1 + 6X2 <= 1566 } labor
12X1 + 16X2 <= 2880 } tubing
X1, X2 >= 0 } non-negativity
170
 Sensitivity of Objective Function Coefficients

Re: MAX Z = 350X1 + 300X2

What if the profit of the Hydro-luxe (X2) is really $360 instead of $300? Does this
change the optimal solution?
One approach: resolve using
MAX = 350X1 + 360X2

Another approach: look at the Z line shift

Re: MAX Z = 350X1 + 300X2
in slope-intercept form:
X2 = (-350/300)*X1 + (Z/300)
X2 = -7/6 X1 + Z/300
For MAX Z = 350X1 + 360X2, the slope-intercept form is:
X2 = -35/36X1 + Z/360

171
 Changing the Slope of the Obj. Fn.
(change in Obj. Fn. coefficients)
X2
orig MAX Z = 350X1 + 300X2
250
new MAX Z = 350X1 + 360X2
original Z, slope = -350/300

200
new optimal solution
(80, 120, Z =71,200)
150
original optimal solution
100 (80, 120) (122, 78, Z=66,100)

(122, 78) new Z, slope = -35/36

50

0
0 50 100 150 200 250 X1
172
 Recall the Feasible Region
X2
(0, 261)
boundary line of pump constraint
250
X1 + X2 = 200, slope is -1

(0, 200)
200 boundary line of labor constraint
(0, 180) 9X1 + 6X2 = 1566, slope is -3/2
150
boundary line of tubing constraint
12X1 + 16X2 = 2880, slope is -3/4
100 (80, 120)

50 (122, 78)

0
0 50 100 150 200 250 X1
(174, 0) (200, 0) (240, 0)173
Changes in Objective Function
Coefficients

“Allowable Increase” and “Allowable Decrease” columns

for the decision variables/changing cells indicate the
amounts by which an objective function coefficient can
change without changing the optimal solution, assuming
all other coefficients remain constant.

174
Sensitivity of Objective Function Coefficients
Goal: Find the boundary slopes of the objective
function beyond which another corner point becomes
optimal.
They are defined by the slopes of the binding constraints!

Here, they are -3/2 and -1.

Putting these slopes in a boundary format yields:

-3/2 < slope of Z < -1  -3/2 < -c1/c2 < -1

To solve for the boundaries of c1 and c2:

-3/2 < -350/c2 < -1  -3/2 < -c1/300 < -1
 233.3 < c2 < 350 & 300 < c1< 450 175
 Check for
Alternate Optimal Solutions

The signal: values of zero (0) in the “Allowable Increase”

or “Allowable Decrease” columns for the decision variables

176
 Blue Ridge Hot Tubs

MAX Z = 350X1 + 300X2 } profit

S.T.:
1X1 + 1X2 <= 200} pumps
9X1 + 6X2 <= 1566 } labor
12X1 + 16X2 <= 2880 } tubing
X1, X2 >= 0 } nonnegativity

177
 How Changing the RHS Value of a Constraint Can Change the Feasible
Region and Optimal Solution
X2

250 Suppose available labor hours increase from 1,566

to 1,728

200

150 old optimal solution (122,78)

Z=66,100
old labor constraint (1566 hrs.)
100
new optimal solution
(176,24) z=68,800
50
new labor constraint
(1728 hrs.)
0
0 50 100 150 200 250 X1
(174,0) (192, 0) 178
 Sensitivity of RHS Constants
What is the dual price of a labor hour?
We know if labor hours increase from 1566 to 1728, the
objective function value increases from $66,100 to
$68,800

Change In The Obj Fn

Yi = =
Change In The RHSi

$(68,800 - 66,100)
= = 2700/162 = $16.67/hr
(1728 - 1566) hrs
179
Changes in Constraint RHS Values
The dual price of a constraint indicates the amount by which the objective function
value changes (improves or worsens) given a unit change (loosening or tightening)
in the RHS value of the constraint, assuming all other coefficients remain constant.

Loosen Tighten
< increase RHS decrease RHS
> decrease RHS increase RHS

MAX MIN
Improves increases Z decreases Z
Worsens decreases Z increases Z

Tightening a constraint worsens the objective function

Loosening a constraint improves the objective function
180
Changes in RHS Values

 Dual prices are valid only within RHS changes falling within the
values in “Allowable Increase” and “Allowable Decrease” columns

181
Key Points About Dual Prices

 The dual prices of resources equate the marginal

value of the resources consumed with the marginal
benefit of the entities being produced
 Resources in excess supply have a dual price (or
marginal value) of zero

182
 Another Use of
Dual Prices

 Suppose a new Hot Tub (the Typhoon-Lagoon) is being

considered. It generates a marginal profit of $320 and
requires:
 1 pump (dual price = $200)
 8 hours of labor (dual price = $16.67)
 13 feet of tubing (dual price = $0)
 Q: Would it be profitable to produce any?
A: $320 - $200*1 - $16.67*8 - $0*13
= -$13.33
No!

183
 Blue Ridge Hot Tubs, Revisited

MAX z = 350X1 + 300X2 + 320X3 } profit

S.T.:
1X1 + 1X2 + 1X3 <= 200 } no. of pumps
9X1 + 6X2 + 8X3 <= 1566 } labor hrs.
12X1 + 16X2 + 13X3 <= 2880 } ft. of tubing
X1, X2, X3 >= 0 } nonnegativity

184
Reduced Costs
 The reduced cost for each product equals its per-unit
marginal profit minus the per-unit value of the resources it
consumes (priced at their dual prices)

OR

 the amount by which the objective function is worsened by a

one unit inclusion of a (currently) non-basic variable into the
basis

185
Reduced Costs (cont.)

OR

 the amount by which the objective function coefficient must be changed by in order to allow
that decision variable to become non-zero

186
 Reduced Costs (cont.)

 Basically, products whose marginal profits are less than the

marginal value of the goods required for their production will not
be produced in an optimal solution

187
Review

 Understand the usefulness of sensitivity analysis

 Perform “one-way” sensitivity analyses for changes in
objective function coefficients and right-hand-side
constants
 Interpret dual prices and reduced costs
 Interpret LINDO sensitivity analysis tables

188
 Solve the following LLP
Maximize Z = 3X1 + 2X2 + 5X3
Subjective to:
X1 + 2X2 + X3 430
3X1 + 2X3  460
X1 + 4X2  420
 Xi  0

189
 The primary task is to convert the LPP into SLPP, let Si be the slack
variables, then
 Maximize Z – 3X1 – 2X2 – 5X3 = 0
Subject to:
X1 + 2X2 + X3 + S1 = 430
3X1 + 2X3 + S2 = 460
X1 + 4X2 + S3 = 420
Xi, Si  0

190
191
 Thus the IFBS is:
X1 = X2 = X3 = 0,
S1 = 430,
S2 = 460,
S3 = 420,
Z=0

192
 Is the IFBS optimal? No, it is not optimal because there are negative
numbers into the net evaluations row (NER), these are –3, -2 and –5.
  

 Now, we choose the column with the most negative number as the pivot
(entering) column. –5 is, of course, the most negative number and therefore
X3 is the entering variable, we mark the column. Now the X3 column is the
pivot column.
  

193
 To determine the pivot (leaving) row we compare the ratios of the CV and
coefficient of pivot column. . We then choose the least ratio, which is 230.
We mark the row as the pivot row; S2 is the leaving variable. The element
at the intersection between the pivot row and the pivot column, 2 in our
example, is the pivot element, and we mark it. Now we are ready of the
second iteration.

194
195
 S2 is replaced by X3 and the whole row is multiplied by 1/2 to get the
pivot element equal to 1. All other elements of the pivot column are
reduced to zero by elementary operation, which involves the pivot
element. Thus, the old S1 minus the X3 gives the new S1. Row S3
remains as it was because its value was zero in the pivot column. To
make the value of NER in the pivot column equal to zero multiply the
new X3 by 5 and add to the old NER to get the new NER.
 Now, the second iteration is done. The current solution is X1 = X2 = S2
= 0. X3 = 230, S1 = 200 and S3 = 420; and Z = 1150.

196
 Is the current solution optimal?
 No because there is –2 in NER X2 column.
 Mark the column.
 Compare the ratios = 100 and = 105, S1 is the pivot row, mark it.
 The intersecting element 2 is the pivot element and mark it.
 Now we are ready for the third iteration.

197
198
Example:
Leather limited manufactures two types of belts: the deluxe model
and the regular model.
Each type requires 1 sq yd of leather. A regular belt requires 1 hour
of skilled labor, and a deluxe belt requires 2 hours.
 Each week, 40 sq yd of leather and 60 hours of skilled labor are
available. Each regular belt contributes $3 to profit and each deluxe
belt, $4.

199
 Define,
X1=number of deluxe belts produced weekly
X2=number of regular belts produced weekly
 The LP is,
Max z=4x1+3x2 (LP1)
s.t. x1+ x2≤40 (Leather constraint)
2x1+ x2≤60 (Labor constraint)
x1,x2≥0

200
 Convert inequality constraints to
equality constraints
 Define for each ≤ constraint a slack variable si
(si=slack variable for ith constraint).
We define,
s1=40- x1-x2 or x1+ x2+ s1=40
s2=60-2x1-x2 or 2x1+ x2 + s2=60

Note: a point satisfies the ith constraint if and only if si≥0.

201
LP1 in standard form
\

Max z=4x1+3x2 (LP1’)

s.t. x1+ x2 +S1 =40
2x1+ x2 +S2 = 60
x1,x2,S1,S2≥0

Note: if constraint i of an LP is a ≤ constraint, we convert it to an

equality constraint by adding a slack variable si to the ith
constraint and adding the sign restriction si ≥0.

202
 60
D

50

B
40

30
x2

E
20

10

C A
0
0 10 20 30 40 50 60
x1

Basic Nonbasic Basic feasible solution Corresponds to

variables variables corner point

x1,x2 s1,s2 s1=s2=0, x1=x2=20 E

x1,s1 x2,s2 x2=s2=0,x1=30,s1=10 C
x1,s2 x2,s1 x2=s1=0,x1=40,s2=-20 Not a bfs
x2,s1 x1,s2 x1=s2=0,s1=-20,x2=60 Not a bfs
x2,s2 x1,s1 x1=s1=0,x2=40,s2=20 B
s1,s2 x1,x2 x1=x2=0,s1=40,s2=60 F203
Unit 7: Transportation and Assignment
Problems

204
 Transportation Model
• Transportation problem deals with the distribution of goods from several points of
supplies (sources) to a number of points of demands (destinations).
• Cost of product = production cost + distribution cost

• Distribution cost consists of mainly the transportation cost of items from its
production (manufacturing) center to the warehouses.
• Transportation techniques are designed to minimize the distribution costs.

• The production capacity of each product in each factory is not fixed.

• The holding capacity of a warehouse or potential sales in each marketing center is

again a fixed quality which cannot be exceeded.

08/16/21 205
 The Characteristics of Transportation Problem
1. A limited supply of one commodity is available at certain
sources or origins.
2. There is a demand for the commodity at several destinations
3. The quantities of supply at each source and the demand at each
destination are constant.
4. The shipping or transportation costs per unit from each source
to each destination are assumed to be constant.
5. No shipments are allowed between sources or between
destinations. All supply and demand quantities are given in
whole number or integers.
6. The problem is to determine how many units shipped from each source to
each destination so that all demands are satisfied at the minimum total
shipping costs.

08/16/21 206
 Uses of Transportation Techniques
1. Reduce distribution or transportation cost
2. Improve competitiveness of product
3. Assist proper location of warehouses
3. Assist proper location of new factories or plants
being planned.
4. Close down warehouses which are found costly and
uneconomical

08/16/21 207
1. Transportation Problem (TP)

Distributing any commodity from

any group of supply centers, called
sources, to any group of receiving
centers, called destinations, in such
a way as to minimize the total
distribution cost (shipping cost).
Total supply must equal total demand.
If total supply exceeds total demand, a dummy
destination, whose demand equals the difference
between the total supply and total demand is
created. Similarly if total supply is less than total
demand, a dummy source is created, whose
supply equals the difference.
All unit shipping costs into a dummy destination
or out of a dummy source are 0.
Example 2:
Example 2:

Destination Supply
D1 D2 D3 D4
S1 50 75 35 75 12
Source S2 65 80 60 65 17
S3 40 70 45 55 11
(D) 0 0 0 0 10
Demand 15 10 15 10
Transportation Tableau:
Initial Solution Procedure:
1. Northwest Corner Starting Procedure
1. Select the remaining variable in the upper left (northwest) corner
and note the supply remaining in the row, s, and the demand
remaining in the column, d.
2. Allocate the minimum of s or d to this variable. If this minimum is
s, eliminate all variables in its row from future consideration and
reduce the demand in its column by s; if the minimum is d, eliminate
all variables in the column from future consideration and reduce the
supply in its row by d.
REPEAT THESE STEPS UNTIL ALL SUPPLIES HAVE BEEN
ALLOCATED.
Total sipping cost = 2250
2. Least Cost Starting Procedure
1. For the remaining variable with the lowest unit cost,
determine the remaining supply left in its row, s, and the
remaining demand left in its column, d (break ties arbitrarily).
2. Allocate the minimum of s or d to this variable. If this
minimum is s, eliminate all variables in its row from future
consideration and reduce the demand in its column by s; if the
minimum is d, eliminate all variables in the column from future
consideration and reduce the supply in its row by d.
REPEAT THESE STEPS UNTIL ALL SUPPLIES HAVE
BEEN ALLOCATED.
Total shipping cost = 2065
3. Vogel’s Approximation Method Starting Procedure
1. For each remaining row and column, determine the difference
between the lowest two remaining costs; these are called the row
and column penalties.
2. Select the row or column with the largest penalty found in step 1
and note the supply remaining for its row, s, and the demand
remaining in its column, d.
3. Allocate the minimum of s or d to the variable in the selected
row or column with the lowest remaining unit cost. If this
minimum is s, eliminate all variables in its row from future
consideration and reduce the demand in its column by s; if the
minimum is d, eliminate all variables in the column from future
consideration and reduce the supply in its row by d.
REPEAT THESE STEPS UNTIL ALL SUPPLIES HAVE BEEN
ALLOCATED.
Total sipping cost = 2030
Example 2:. Shipping costs, Supply, and Demand for
Powerco Example

From To
City 1 City 2 City 3 City 4 Supply
(Million kwh)
Plant 1 $8 $6 $10 $9 35
Plant 2 $9 $12 $13 $7 50
Plant 3 $14 $9 $16 $5 40
Demand 45 20 30 30
(Million kwh)
Transportation Tableau
 Solution
1. Decision Variable:
Since we have to determine how much electricity is
sent from each plant to each city;

Xij = Amount of electricity produced at plant i and

sent to city j

X14 = Amount of electricity produced at plant 1 and

sent to city 4
 2. Objective function

Since we want to minimize the total cost of shipping

from plants to cities;

Minimize Z = 8X11+6X12+10X13+9X14
+9X21+12X22+13X23+7X24
+14X31+9X32+16X33+5X34
 3. Supply Constraints
Since each supply point has a limited production capacity;

X11+X12+X13+X14 <= 35
X21+X22+X23+X24 <= 50
X31+X32+X33+X34 <= 40
 4. Demand Constraints
Since each supply point has a limited production capacity;

X11+X21+X31 >= 45
X12+X22+X32 >= 20
X13+X23+X33 >= 30
X14+X24+X34 >= 30
 5. Sign Constraints
Since a negative amount of electricity can not be shipped
all Xij’s must be non negative;

Xij >= 0 (i= 1,2,3; j= 1,2,3,4)

 LP Formulation of Powerco’s Problem
Min Z = 8X11+6X12+10X13+9X14+9X21+12X22+13X23+7X24
+14X31+9X32+16X33+5X34

S.T.: X11+X12+X13+X14 <= 35 (Supply Constraints)

X21+X22+X23+X24 <= 50
X31+X32+X33+X34 <= 40
X11+X21+X31 >= 45 (Demand Constraints)
X12+X22+X32 >= 20
X13+X23+X33 >= 30
X14+X24+X34 >= 30
Xij >= 0 (i= 1,2,3; j= 1,2,3,4)
General Description of a Transportation Problem

1. A set of m supply points from which a good is

shipped. Supply point i can supply at most si units.
2. A set of n demand points to which the good is
shipped. Demand point j must receive at least di
units of the shipped good.
3. Each unit produced at supply point i and shipped to
demand point j incurs a variable cost of cij.
Xij = number of units shipped from supply point i to demand
point j
i m j n
min  cijXij
i 1 j 1
j n
s.t. Xij  si (i  1,2,..., m)
j 1
i m

X
i 1
ij  dj ( j  1,2,..., n)

Xij  0(i  1,2,..., m; j  1,2,..., n)

 Balanced Transportation Problem
If Total supply equals to total demand, the
problem is said to be a balanced
transportation problem:

i m j n

s  d
i 1
i
j 1
j
Balancing a TP if total supply exceeds total
demand

If total supply exceeds total demand, we can

balance the problem by adding dummy
demand point. Since shipments to the dummy
demand point are not real, they are assigned a
cost of zero.
Balancing a transportation problem if total supply
is less than total demand

If a transportation problem has a total supply

that is strictly less than total demand the
problem has no feasible solution. There is no
doubt that in such a case one or more of the
demand will be left unmet. Generally in such
situations a penalty cost is often associated
with unmet demand and as one can guess this
time the total penalty cost is desired to be
minimum
7.2 Finding Basic Feasible Solution
for TP
Unlike other Linear Programming problems, a
balanced TP with m supply points and n
demand points is easier to solve, although it
has m + n equality constraints. The reason for
that is, if a set of decision variables (xij’s)
satisfy all but one constraint, the values for xij’s
will satisfy that remaining constraint
automatically.
Methods to find the bfs for a balanced TP

There are three basic methods:

1. Northwest Corner Method

2. Minimum Cost Method

3. Vogel’s Method
Example 3

Suppose that a firm has three factories /sources of supply/

& four warehouses
/point of demand/. The firm's production capacity at the
three factories, the demand for the four distribution
centers located at various regions & the cost of shipping
each unit from the factories to the warehouses through
each route is given as follows:
 Destinations
(dd) =j
Factory
Origin
W1 W2 W3 W4 Capacity =i
(Supply)
$3 2 7 6
F1 5000
7 5 2 3
F2 6000

2 5 4 5
F3 2500

Requirements of the
Warehouses
( Units of demand) 6000 4000 2000 1500 13500
LPP

Solution

Let xij =The amount of commodity to be transported form

source i (i =1,2,3 ) to destination j( j= 1,2,3,4).
Then the objective function of the problem (minimization of
the total transportation cost) can be formulated as:
Min Z = 3x11 +2x12 + 7x13 +6 x14 +
7x21 +5x22 +2x23 + 3x24 +
2x31+5x32 +4x33+5x34
Subject to the constraints
a. Supply constraints:
x11 +x12 +x13 +x 14 =5000 F1 supply constraint
x21 + x22 + x23 +x24 =6000 F2 supply constraint
x31 +x32 +x33+x34 = 2500 F3 supply constraint
b. Demand constraints:
x11 + x21 + x31 = 6000 W1 demand constraint
x12 + x22 + x32 = 4000 W2 demand constraint
x13 + x23 +x33 = 2000 W3 demand constraint
x14 +x24 + x34 = 1500 W4 demand constraint
x ij > 0 for all i& j
In the above LPP, there are m x n = 3x4 =12 decision variables & m + n = 3+4
=7 constraints. Thus, if this problem is solved by the simplex method, then it
may take considerable computational time.
The network representation of the transportation LPP is
called Net work flow

Origin Destination centers

(Sources of Supply) (Point of demand centers)
3
F1 50000 W1 6000

2
6
7

F2 6000 5
W2 4000
2
3
W3 2000

2 5
4
F3 2500
5 W4 1500

This LPP has 12 shipping routes. The objective is to identify the minimum cost
route (Least cost route).
 Methods Of Finding Initial Feasible Solution

A. North- West Corner Method (NWCM)

• This method does not take into account the cost of
transportation on any route of transportation.
• The NWCM gets its name because the starting point for the
allocation process is the Upper Left-hand (Northwest) corner of
the transportation table.
• Therefore, allocate to the Northwest corner as many units as
possible. 
Northwest corner rule
The following set of principles guides the allocation:
 
1.Begin with the upper left hand cell (Left, upper most in the
table), & allocate as many units as possible to that cell. This
will be the smaller amount of either the row supply or the
column demand. Adjust the row & column quantities to
reflect the allocation.
2. Subtract from the row supply & from the column demand
the amount allocated
3. If the column demand is now zero, move to the cell next to
the right, if the row supply is zero, move down to the cell
in the next row. 
If both are zero, move first to the next cell on the right
then down one cell.
4. Once a cell is identified as per step (3), it becomes a
northwest cell. Allocate to it an amount as per step (1)
5. Repeat, the above steps (1) - (4) until all the remaining
supply and demand is gone.
 
The steps of the northwest corner method are summarized
here:

1.Allocate as much as possible to the cell in the upper left-

hand corner, subject to the supply and demand constraints.

2. Allocate as much as possible to the next adjacent feasible

cell.

3. Repeat step 2 until all rim requirements have been met.

Example:
Consider the following transportation problem:

To Store 1 Store 2 Store 3 Store 4

From Supply
Plant 1
19 30 50 10 7

Plant 2 70 30 40 60 9

Plant 3 40 8 70 20 18

Demand 5 8 7 14 34

a. Develop an initial feasible solution using the NWCM

b. Compute the total cost for this solution.
Solution
A. Table: Initial feasible solution

To
Store 1 Store 2 Store 3 Store 4 Supply
From
19 30 50 10
Plant 1 5 2 7
70 30 40 60
Plant 2 6 3 9

40 8 70 20
Plant 3 4 14 18

Demand 8 7 14 34
5

Check that the solution is feasible or not:

==>m + n-1; m=3 and n=4  3+4-1= 6 cells occupied (Feasible solution)
The total transportation cost of the initial feasible solution
derived by the NWCM is:

Route Unit Per unit Total

From To Shipped X cost ( $) = Cost ( $)

Plant 1 Store 1 5 19 95
plant 1 Store 2 2 30 60
Plant 2 Store 3 6 30 180
Plant 2 Store 4 3 40 120
Plant 3 Store 4 4 70 280
Plant 3 Store 4 14 20 280
Total Cost= $ 1015

Note: NWCM does not consider the cost factor for allocation.
Exercise:
1. Determine an initial basic feasible solution to the following
transportation problem using NWCM. Compute the total cost
for this solution

A B C Supply
S1 2 7 14 5
S2 3 3 1 8

S3 5 4 7 7
S4 1 6 2 14
Demand 7 9 18 34

Answer: X11=5, X21=2, X22=6, X32=3, X33=4, X43=14, and

Total cost =$102
Note:
1. Total Supply= Total demand ===> Balanced TP
2. Total Supply ≠ total demand ===> Unbalanced TP
3. Convert the unbalanced TP into a balanced TP by using dum
my destination/dummy source.
* If total Supply > Total demand, then create a fictitious or
artificial destination called dummy destination
i.e: total Supply > Total demand===>
Add dummy column  
* Excess demand (Supply < demand)
- Add a dummy source
- Add a dummy row

Note: the cost of “shipments” to the dummy is usually set at zero ==> No real
cost
Example
Develop an initial feasible solution using NWCM
Table: Unbalanced transportation table

R S T Supply
A 1 2 3 100

B 4 1 5 110

80 120 60 210
Demand
260
 Solution:

R S T Supply
1 2 3
A 100
80 20
4 1 5
B 110
100 10
0 0 0
Dummy 50
50
Demand 80 120 60 260

Answer:X11=80, X12=20, X22=100, X23=10, X33=50 Total cost =$270

. The Least- Cost Method (LCM) Or
(Largest- Profit) Method
 LCM is the method used a minimum cost in the allocation.
 It begins a solution by sequentially assigning to the ratios or
cells with the minimum cost as many units as possible.
 The first allocation be made to the cell with the lowest cost
(the highest profit in a maximization case)
 The Least- Cost Method yields not only an initial feasible
solution but also one that is close to optimal in small problems.
The specific steps of the minimum cell cost method are
summarized next:

1. Allocate as much as possible to the feasible cell with the

minimum transportation
cost, and adjust the rim requirements.
2. Repeat step 1 until all rim requirements have been met.
Example
1.Suppose that a firm has three factories / sources of supply /& four
warehouses/point of demand/ .The firm's production capacity at the three factories,
the demand for the four destination centers located at various regions & the cost of
shipping each unit from the factories to the warehouses through each route is given
as follows:
Destinations

Factory
W1 W2 W3 W4 Capacity
F1 3 2 7 6 5000
F2 7 5 2 3 6000
F3 2 5 4 5 2500
Demand 6000 4000 2000 1500 13500

Required:
a. Develop an initial feasible solution using NWCM & Compute the total cost
b. Develop an initial feasible solution using least-cost method & compute the total cost.
 Solution:

a. Initial feasible solution

Factory
W1 W2 W3 W4 Capacity
Factory 3 2 7 6
F1 5000 5000

7 5 2 3
F2 6000
1000 4000 1000
2 5 4 5
F3 2500
1000 1500
Demand 6000 4000 2000 1500 13500

m= 3, n =4 ==> 3+4 -1 =6 occupied cells (Feasible)

 Total transportation cost

Routes Units Unit Total

From To Shipped X Cost =Cost
F1 W1 5000 3 $ 15000
F2 W1 1000 7 7000
F2 W2 4000 5 20000
F2 W3 1000 2 2000
F3 W3 1000 4 4000
F3 W4 1500 5 7500
Total =$55,500
transportation
cost
 W1 W2 W3 W4 Factory Capacity
3 2 7 6
F1 5000
1000 4000
7 5 2 3
F2 6000
2500 2000 1500
2 5 4 5
F3 2500
2500
Demand 6000 4000 2000 1500 13500
 Total transportation cost

Routes Units Unit Total

From To Shipped Cost =Cost
F1 W1 1000 3 $ 3000
F1 W2 4000 2 8000
F2 W1 2500 7 17500
F2 W3 2000 2 4000
F2 W4 1500 3 45000
F3 W1 2500 2 5000
Total transportation cost =$42,000
 C. vogel's Approximation Method (VAM) or Penalty
Method
 
• VAM is preferred to the other two methods described above. In this
method each allocation is made on the basis of the opportunity (or
penalty or extra) cost that would have incurred if allocation in certain
cells with minimum unit transportation cost were missed. 
• In this method allocation are made so that the penalty cost is minimized.
• The advantage of this method is that it gives an initial solution which is
nearer to an optimal solution or is the optimal solution itself. 
• VAM determines the penalty for not using the minimum cost routes,
where the objective is to avoid large penalties so that the penalty from
not using the routes is minimized.
 Steps in VAM method

• 1. Calculate penalties for each row (column) by taking the smallest & the next smallest unit
transportation cost in the same row (column)

• This difference indicates the penalty or extra cost which has to be paid if one fails to allocate
to the cell with the minimum unit transportation cost
• 2. Select the row or column with the largest penalty & allocate as much unit as possible in
the cell having the least cost in the selected row or column satisfying the conditions.
• If there is a tie in the values of penalties, then it can be broken by selecting the cell where
maximum allocation can be made.
• 3. Adjust the supply & demand & cross out the satisfied row or column
• If a row or column is satisfied simultaneously, only one of them is crossed out & the
remaining row (column) is assigned a zero supply (demand) .Any row or column with zero
supply or demand should not be used in computing future penalties.
• Repeat step 1 to 3 until the entire available supply at various sources & demand at various
destinations are satisfied.
The steps of Vogel’s approximation model can be summarized in the
following list:

1. Determine the penalty cost for each row and column by

subtracting the lowest cell
cost in the row or column from the next lowest cell cost in the same
row or column.
2. Select the row or column with the highest penalty cost (breaking
ties arbitrarily or
choosing the lowest-cost cell).
3. Allocate as much as possible to the feasible cell with the lowest
transportation cost in
the row or column with the highest penalty cost.
4. Repeat steps 1, 2, and 3 until all rim requirements have been met.
Example: 1
a.Determine an initial basic feasible solution to the following
transportation problem using VAM.
Row difference or Row penalty

or opportunity cost
A B C D Supply
2 2 0 4 2 0 - - -
Factory 5 20 25
F1
F2 5 9 8 3 2 2 2 2 5
25
15 5 5
F3 6 4 3 2
10 1 2 2 - -
10
Demand 20 15 20 5 60

Column difference 3 2 3 1

or Column penalty

or opportunity cost 3 2 - 1

1 5 - 1

5 9 - -

5 - - -
Example: 2
The Assignment Problem (AP)
a special case of TP with m=n and si=dj for all i,
and j.

The Hungarian Algorithm

=> solving the assignment problem of a least
cost assignment of m workers to m jobs
 The Hungarian Method

• Provides a simple heuristic that can be used to find the optimal set
of assignments.
• It is based on minimization of opportunity costs that would result
from potential pairings. These are additional costs that would be
incurred if the lowest-cost assignment is not made
 Requirements for Use of the Hungarian Method

• Situations in which the Hungarian method can be used are

characterized by the following:
 There needs to be a one-for-one matching of two sets of items.
 The goal is to minimize costs (or to maximize profits) or a similar
objective
 The costs or profits are known or can be closely estimated.
 The Hungarian Method
• Step 1: Locate the smallest cost element in each row of the cost table. Now
subtract this smallest from each element in that row.
• Step 2: Consider each column and locate the smallest element in it.
Subtract the smallest value from every other entry in the column.
• Step 3: Draw the minimum number of horizontal and vertical lines required
to cover the entire ‘zero’ elements. If the number of lines drawn is equal to
n (the number of rows/columns) the solution is optimal
• Step 4: Select the smallest uncovered cost element. Subtract this element
from all uncovered elements including itself and add this element to each
value located at the intersection of any lines.
• Step 5: Repeat steps 3 and 4 until an optimal solution is obtained.
• Step 6: Given the optimal solution, make the job assignments as indicated
by the ‘zero’ elements.
Example
contd
Determine the Minimum Number of Lines Needed to Cover
the Zeros

Further
FurtherRevision
Revisionof
ofthe
theCost
CostTable
Table
Optimal Assignments
 Example 2
• A production supervisor is considering how he should assign the four jobs that
are performed, to four of the workers working under him. He want to assign
the jobs to the workers such that the aggregate time to perform the job in the
least. Based on the previous experience, he has the information on the time
taken by the four workers in performing these jobs, as given in below
The final assignments is 1-B, 2-D, 3-C, and
Example 3:
Minimum uncovered
number
Minimum uncovered
number
CONVERSION OF A MAXIMIZATION
PROBLEM TO A MINIMIZATION PROBLEM

The Hungarian algorithm works only if the matrix is a

cost matrix. A maximization assignment problem can be
converted to a minimization problem by creating a lost
opportunity matrix. The problem then is to minimize the
total lost opportunity.
Profit Matrix:
J1 J2 J3 J4
W1 67 58 90 55
W2 58 88 89 56
W3 74 99 80 22
(D) 0 0 0 0
The lost opportunity matrix given below is derived by
subtracting each number in the J1 column from 74, each
number in the J2 column from 99, each number in the J3
column from 90, and each number in the J4 from 56.

J1 J2 J3 J4
W1 7 41 0 1
W2 16 11 1 0
W3 0 0 10 34
(D) 74 99 90 56

The Hungarian algorithm can now be applied to this lost

opportunity matrix to determine the maximum profit set of
assignments.