Chapter Two

Linear Programming

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene
Syed M.T. (2019)
Ahmed, Ph.D.
 Mathematical programming is used to find the
best or optimal solution to a problem that requires
a decision or set of decisions about how best to
use a set of limited resources to achieve a stated
goal of objectives.

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene
Syed M.T. (2019)
Ahmed, Ph.D.
 Model Assumptions
Proportionality

 The contribution to the objective function from each decision variable is

proportional to the value of the decision variable
 (E.g. The contribution to the objective function from making four soldiers
(4×$3=$12) is exactly four times the contribution to the objective function from
making one soldier ($3))

 The contribution of each decision variable to the LHS of

each constraint is proportional to the value of the decision variable
 (E.g. It takes exactly three times as many finishing hours (2hrs×3=6hrs) to
manufacture three soldiers as it takes to manufacture one soldier (2 hrs)

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene
Syed M.T. (2019)
Ahmed, Ph.D.
Model Assumptions

Additivity Assumption

 The contribution to the objective function for any decision variable is

independent of the values of the other decision variables.
 (E.g. No matter what the value of train (X2), the manufacture of soldier

(x1) will always contribute 3x1 dollars to the objective function)

 The contribution of a decision variable to LHS of each constraint is

independent of the values of other decision variables.
 (E.g. No matter what the value of X1, the manufacture of X2 uses X2 finishing hours

and X2 carpentry hours)

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene
Syed M.T. (2019)
Ahmed, Ph.D.
Model Assumptions

Additivity Assumption

 1st Implication:

 The value of objective function is the sum of the contributions from

each decision variables.

 2nd Implication: LHS of each constraint is the sum of the contributions

from each decision variables.

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene
Syed M.T. (2019)
Ahmed, Ph.D.
Model Assumptions

Divisibility Assumption:

 it is possible to take any fraction of any variable.

 Taking, for example, the Marketing problem, what does it mean to purchase
2.67 television ads?

 It may be that the divisibility assumption is violated in this example. Or,

 It may be that the units are such that 2.67 "ads" actually corresponds to
2666.7 minutes of ads, in which case we can "round off" our solution to
2667 minutes with little doubt that we are getting an optimal or nearly
optimal solution.
BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene
Syed M.T. (2019)
Ahmed, Ph.D.
Model Assumptions

Certainty Assumption

 The final assumption is the Certainty linear

Assumption: programming allows for no uncertainty about the
numbers.
 E.g. An ad will reach the given number of people; the number of assembly
hours we give will certainly be available.

 However,
 It is very rare that a problem will meet all of the assumptions exactly.
 That does not negate the usefulness of a model.
 A model can still give useful managerial insight even if reality
differs slightly from the rigorous requirements of the model.

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene
Syed M.T. (2019)
Ahmed, Ph.D.
 Construction of Mathematical Model
I. Objective function
II. Variables Quantitatively

III. Constraints- (equations, or inequalities)

o Resource, &
o Non-negativity constraints

 This process is often called =

– formulating the problem
– (or more strictly, formulating a mathematical representation
of the problem).

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene
Syed M.T. (2019)
Ahmed, Ph.D.
 Introduction
 Steps involved in mathematical programming
 Conversion of stated problem into a model that
mathematical abstracts all the essential elements of the
problem.
 Exploration of different solutions of the problem.

 Finding out the most suitable or optimum solution.

 Linear programming requires that all the
mathematical functions in the model be linear functions.

BCN67755
Decision and Risk Analysis Compiled by: DrSyed
Dejene T. Ph.D.
M. Ahmed,
 The Linear Programming Model (1)
Let: X1, X2, X3, ………, Xn = decision variables
Z = Objective function or linear function

Requirement: Maximization of the linear function Z.

Z = c1X1 + c2X2 + c3X3 + ………+ cnXn
…..Eq (1)
subject to the following constraints:

…..Eq (2)

where aij, bi, and cj are given constants.

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene
Syed M.T. (2019)
Ahmed, Ph.D.
 The Linear Programming Model (2)
 Thelinearprogramming model can be written in
more efficient notation as:

…..Eq (3)

The decision variables, xI, x2, ..., xn, represent levels of n

competing activities.
BCN67755
Decision and Risk Analysis Compiled by: DrSyed
Dejene T. Ph.D.
M. Ahmed,
 Examples of LP Problems (1)
1. A Product Mix Problem

 A manufacturer has fixed amounts of different resources

such as raw material, labor, and equipment.
 These resources can be combined to produce any one of
several different products.
 The quantity of the ith resource required to produce one unit
of the jth product is known.
 The decision maker wishes to produce the combination of
products that will maximize total income.

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene
Syed M.T. (2019)
Ahmed, Ph.D.
 Examples of LP Problems (2)
2. A Blending Problem

 Blending problems refer to situations in which a number of

components (or commodities) are mixed together to yield one
or more products.
 Typically, different commodities are to be purchased. Each
commodity has known characteristics and costs.
 The problem is to determine how much of each commodity
should be purchased and blended with the rest so that the
characteristics of the mixture lie within specified bounds and
the total cost is minimized.

BCN67755
Decision and Risk Analysis Compiled by: DrSyed
Dejene T. Ph.D.
M. Ahmed,
 Examples of LP Problems (3)
3. A Production Scheduling Problem

 A manufacturer knows that he must supply a given number of

items of a certain product each month for the next n months.
 They can be produced either in regular time, subject to a
maximum each month, or in overtime. The cost of producing
an item during overtime is greater than during regular time. A
storage cost is associated with each item not sold at the end
of the month.
 The problem is to determine the production schedule that
minimizes the sum of production and storage costs.

BCN67755
Decision and Risk Analysis Compiled by: DrSyed
Dejene T. Ph.D.
M. Ahmed,
 Examples of LP Problems (4)
4. A Transportation Problem

 A product is to be shipped in the amounts al, a2, ..., am from m

shipping origins and received in amounts bl, b2, ..., bn at each of
n shipping destinations.
 The cost of shipping a unit from the ith origin to the jth
destination is known for all combinations of origins and
destinations.
 The problem is to determine the amount to be shipped from each
origin to each destination such that the total cost of
transportation is a minimum.

BCN67755
Decision and Risk Analysis Compiled by: DrSyed
Dejene T. Ph.D.
M. Ahmed,
 Examples of LP Problems (5)
5. A Flow Capacity Problem

 One or more commodities (e.g., traffic, water, information, cash,

etc.) are flowing from one point to another through a network
whose branches have various constraints and flow capacities.
 The direction of flow in each branch and the capacity of
each branch are known.
 The problem is to determine the maximum flow, or capacity of
the network.

BCN67755
Decision and Risk Analysis Compiled by: DrSyed
Dejene T. Ph.D.
M. Ahmed,
 Developing LP Model (1)
 The variety of situations to which linear programming has
been applied ranges from agriculture to zinc smelting.

 Steps Involved:

 Determine the objective of the problem and describe it by a

criterion function in terms of the decision variables.
 Find out the constraints.
 Do the analysis which should lead to the selection of values for
the decision variables that optimize the criterion function while
satisfying all the constraints imposed on the problem.

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene
Syed M.T. (2019)
Ahmed, Ph.D.
 Developing LP Model (2)
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 in Table 1.

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.

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene
Syed M.T. (2019)
Ahmed, Ph.D.
 Developing LP Model (3)
Example Problem
All products manufactured are shipped out of the storage area at the end of the
day. Therefore, the two products must share the total raw material, storage
space, and production time. The company wants to determine how
many units of each product to produce per day to maximize its
total income.

Solution
• The company has decided that it wants to maximize its sale income,
which depends on the number of units of product I and II that it produces.
• Therefore, the decision variables, x1 and x2 can be the number of units of
products I and II, respectively, produced per day.

BCN67755
Decision and Risk Analysis Compiled by: DrSyed
Dejene T. Ph.D.
M. Ahmed,
 Developing LP Model (4)
• The objective is to maximize the equation:
Z = 13x1 + 11x2
subject to the constraints on storage space, raw materials, and
production time.

• Each unit of product I requires 4 ft2 of storage space and each unit of
product II requires 5 ft2. Thus a total of 4x1 + 5x2 ft2 of storage space is
needed each day. This space must be less than or equal to the available
storage space, which is 1500 ft2. Therefore,
4X1 + 5X2  1500
• Similarly, each unit of product I and II produced requires 5 and 3 1bs,
respectively, of raw material. Hence a total of 5xl + 3x2 Ib of raw material is
used.

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene
Syed M.T. (2019)
Ahmed, Ph.D.
 Developing LP Model (5)
• This must be less than or equal to the total amount of raw material
available, which is 1575 Ib. Therefore,
5x1 + 3x2  1575
• Prouct I can be produced at the rate of 60 units per hour. Therefore, it must
take I minute or 1/60 of an hour to produce I unit. Similarly, it requires 1/30
of an hour to produce 1 unit of product II. Hence a total of x1/60 + x2/30
hours is required for the daily production. This quantity must be less than or
equal to the total production time available each day. Therefore,

x1 / 60 + x2 / 30 
7 or x1 +2x2  420
• Finally, the company cannot produce a negative quantity of any product,
therefore x1 and x2 must each be greater than or equal to zero.

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene
Syed T. Ph.D.
M. Ahmed,
 Developing LP Model (6)
• The linear programming model for this example can be summarized as:

…..Eq (4)

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene
Syed T. Ph.D.
M. Ahmed,
 Examples


BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene
Syed T. Ph.D.
M. Ahmed,
The Galaxy Industries Production Problem
– A Prototype Example

• Galaxy manufactures two toy doll

models:
– Space Ray.
– Zapper.
• Resources are limited to
– 1000 pounds of special plastic.
– 40 hours of production time per week.
Compiled by: Dr. Dejene T
The Galaxy Industries Production Problem
– A Prototype Example
• Marketing requirement
– Total production cannot exceed 700 dozens.
– Number of dozens of Space Rays cannot exceed
number of dozens of Zappers by more than
350.
• Technological input
– Space Rays requires 2 pounds of plastic and
3 minutes of labor per dozen.
– Zappers requires 1 pound of
The Galaxy Industries Production Problem
– A Prototype Example
• The current production plan calls for:
– Producing as much as possible of the more profitable product,
Space Ray ($8 profit per dozen).
– Use resources left over to produce Zappers ($5 profit
per dozen), while remaining within the marketing
guidelines.
• The current production plan consists of:
8(450) +
Space Rays = 450 dozen
5(100)
Zapper = 100 dozen
Profit = $4100 per
week
Compiled by: Dr. Dejene T. (2019)
Management is seeking a
production schedule that will
increase the company’s profit.

Compiled by: Dr. Dejene T

A linear programming model
can provide an insight and an
intelligent solution to this
problem.

Compiled by: Dr Dejene T

 The Galaxy Linear Programming
Model
• Decisions variables:
– X1 = Weekly production level of Space Rays (in dozens)
– X2 = Weekly production level of Zappers (in dozens).

• Objective Function:
– Weekly profit, to be maximized

Compiled by: Dr Dejene T. (2019)

The Galaxy Linear Programming
Model
Max 8X1 + 5X2 (Weekly profit)
subject to
2X1 + 1X2  (Plastic)
1000 (Production Time)
3X1 + 4X2  (Total
2400 X1 + X2 production)
 700 X1 - (Mix)
X  350 X > (Nonnegativity)
Compiled by: Dr Dejene T
2 j
2.3 The Graphical Analysis of
Linear
Programming
The set of all points that satisfy all
the constraints of the model is
called
a
FEASIBLE
REGION

Compiled by: Dr Dejene T

Using a graphical presentation
we can represent all the constraints,
the objective function, and the three
types of feasible points.

Compiled by: Dr Dejene T

Graphical Analysis – the Feasible
Region
X2

The non-negativity
constraints

X1

Compiled by: Dr Dejene T

 Graphical Analysis – the Feasible
Region
X 2

1000 The Plastic constraint

2X1+X2  1000
700 Total production
constraint: X1+X2  700
500 (redundant)
Infeasible
Production Feasibl
Time e
3X1+4X2  X1
2400 500 700

Compiled by: Dr Dejene T. (2019)

 Graphical Analysis – the Feasible
Region
X 2

1000 The Plastic constraint

2X1+X2  1000
700 Total production
X1+X2  700
constraint:
500 (redundant)
Infeasible
Production mix
constraint:
Production Feasibl X1-X2  350
Time e
3X1+4X2
X1
2400 500 700
Interior points. Boundary points.Extreme
• Therepoints.
are three types of feasible Compiled by: Dr Dejene T
Compiled by: Dr Dejene T
Compiled by: Dr Dejene T
Solving Graphically for an
Optimal Solution

Compiled by: Dr Dejene T

 The search for an optimal
solution
X Start at some arbitrary profit, say profit = $2,000...
2

1000 Then increase the profit, if possible...

...and continue until it becomes infeasible

700 Profit =$4360

500

X1

500 Compiled by: Dr Dejene T

 Summary of the optimal
solution
Space Rays = 320
dozen Zappers = 360
dozen Profit = $4360
– This solution utilizes all the plastic and
all the production hours.
– Total production is only 680 (not 700).

– Space Rays production exceeds Zappers production by only 40

dozens.

Compiled by: Dr Dejene T

CORNER POINT
THEOREM
• If the feasible region is bounded, then the
objective function has both a maximum and a
minimum value, and each occurs at one or
more corner points.
• If the feasible region is unbounded, then the
objective function may not have a maximum
or minimum. But if a maximum or minimum
value exists, it will occur at one or more
corner points.
Compiled by: Dr Dejene T. (2019)
SOLVING LINEAR
PROGRAMMING PROBLEM
1. Write the objective function and all necessary
constraints.
2. Graph the feasible region.
3. Determine the cordinates of each corner
points.
4. If the feasible region is bounded, the solution is
given by the corner point producing the
optimum value of the objective function.
Compiled by: Dr Dejene T
SOLVING LINEAR
PROGRAMMING PROBLEM
5. If the feasible region is unbounded in the first quadrant and
both coefficients of the objective function are positive, then
the minimum value of the objective function occurs at a
corner point and there is no maximum value.

Compiled by: Dr Dejene T. (2019)

 Extreme points and optimal
solutions
– If a linear programming problem has an optimal
solution, an extreme point is optimal.

Compiled by: Dr Dejene T

 Multiple optimal
solutions
• For multiple optimal solutions to exist, the
objective function must be parallel to one of the
constraints

• Any weighted average of

optimal solutions is also
an optimal solution.

Compiled by: Dr Dejene T

 2.7 Models Without Unique
Optimal Solutions

• Infeasibility: Occurs when a model has no

feasible point.
• Unboundness: Occurs when the objective can
become infinitely large (max), or infinitely small
(min).
• Alternate solution: Occurs when more than one point
optimizes the objective function
Compiled by: Dr Dejene T. (2019)
 Infeasible
Model
No point,
simultaneously,
lies both above line1
and
below
2 and
2 lines
. 3

3 1
y: Dr Dejene T
Unbounded
solution 

Compiled by: Dr Dejene T

 The Simplex Method (2)
 Steps involved:
1. Locate an extreme point of the feasible region.
2. Examine each boundary edge intersecting at this point to see
whether movement along any edge increases the value of the
objective function.
3. If the value of the objective function increases along any edge,
move along this edge to the adjacent extreme point. If several
edges indicate improvement, the edge providing the greatest rate
of increase is selected.
4. Repeat steps 2 and 3 until movement along any edge no
longer increases the value of the objective function.

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene
Syed T. Ph.D.
M. Ahmed,
 Questions/Queries?

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene
Syed T. Ph.D.
M. Ahmed,
 Simplex method

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene
Syed T. Ph.D.
M. Ahmed,
 A firm, that assembles computers and computer
equipment, is about to start production of two new micro
computers.

Each type of microcomputer will require assembly time,

inspection time and storage space.
The amount of each of these resources that can be
devoted to the production of the micro computers is
limited.
The manager of the firm would like to determine the
quantity of each of the microcomputers to produce in
order to maximize the profit generated by sales of
these microcomputers.
The following additional information is provided.
BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene
Syed T. Ph.D.
M. Ahmed,
 Type 1 Type 2
Profit per unit 60 50
Assembly time/unit 4hrs 10hrs
Inspection time/unit 2hrs 1hrs
Storage space/ unit 3 3
feet cubi cubic
Resources available c
feet
Assembly time 100hrs
Inspection time 22 hrs
Storage space 39
cubic
feet

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene
Syed M.T.Ahmed,
(2019)Ph.D.
 Required
Formulate the problem as LPM
Solve using simplex method
Construct the range of optimality and feasibility for the
objective function coefficient and right hand side values.
Interpret the shadow prices.

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene
Syed T. Ph.D.
M. Ahmed,
 Management is seeking a
production schedule that
will increase the
company’s profit.

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene
Syed T. Ph.D.
M. Ahmed,
 Cont’d

Decisions variables:
◦ X1 = Weekly production level of type I computer (in dozens)
◦ X2 = Weekly production level of type II computer (in dozens).

Objective Function:
◦ Weekly profit, to be maximized

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene
Syed T. Ph.D.
M. Ahmed,
 Cont’d

Max 60X1 + 50X2 (Weekly profit)

subject to
4X1 + 10X2  100 (Assembly time)
2X1 + 4X2  2400 (Inspection Time)
3X1 + 3X2 39 (storage space)
Xj> = 0, j= (Nonnegativity)

1,2

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene
Syed T. Ph.D.
M. Ahmed,
  The simplex method is an iterative technique that begins with
a feasible solution
 Through algebraic manipulation, the solution is improved
until no further improvement is possible
 Each iteration moves one step closer to the optimal
solution.
 In each iteration, one variable that is not in the solution is
added to the solution and one variable that is in the solution is
removed from the solution in order to keep the number of
variables in the basis equal to the number of constraints.

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene
Syed M.T.Ahmed,
(2019)Ph.D.
 Cont’d

 The simplex procedure for a maximization problem with

all  constraints consists of the following steps
Step 1. Write the LPM in a standard form
 When all of the constraints are written as equalities
 We convert the LPM in to a standard form by applying the slack
variables, S, which carries a subscript that denotes which constraint
it applies to.
 For example, S1 refers to the amount of slack in the first constraint,
S2 to the amount of slack in the second constraint, and so on.

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene
Syed T. Ph.D.
M. Ahmed,
 Step1 cont’d

Taking the microcomputer problem its standard form is as

follows:
Zmax = 60X1 + 50X2 Zmax = 60X1 + 50X2 + 0S1 + 0S2 +
0S3 : 4X1 + 10X2  100 : 4X1 + 10X2 + S1 = 100
2X1 + X2  22 2X1 + X2 + S2 = 22
3X1 + 3X2  39 3X1 + 3X2 + S3 = 39
X1 , X2  0 X1, X2, S1, S2, S3  0

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene
Syed M.T.Ahmed,
(2019)Ph.D.
 Step 2. Develop the initial tableau:

The initial tableau always represents the “Do Nothing”

strategy, so that the decision variables are initially non-
basic.
o List the variables across the top of the table and write the objective
function coefficient of each variable jut above it.
o There should be one row in the body of the table for each constraint.
List the slack variables in the basis column, one per raw.
o In the Cj column, enter the objective function coefficient of zero for
each
slack variable. (Cj - coefficient of variable j in the objective function)
o Compute values for row Zj
o Computer values for Cj – Zj.

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene
Syed T. Ph.D.
M. Ahmed,
 Step 2 cont’d

Basic Cj 60 50 0 0 0
variable
X1 X2 S1 S2 S3 RHSV Ratio

S1 0 4 10 1 0 0 100 100/4 = 25

S2 0 2* 1 0 1 0 22 22/2 = 11

S3 0 3 3 0 0 1 39 39/3 = 13

Zj 0 0 0 0 0 0

Cj-Zj 60 50 0 0 0 0

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene
Syed T. Ph.D.
M. Ahmed,
 Step 3. Develop subsequent tableaus

1. Identify the entering variable - a variable that has a

largest positive value in the Cj – Zj raw.
2.Identify the leaving variable - Using the constraint
coefficients or substitution rates in the entering variable
column divide each one into the corresponding quantity
value. However do not divide by a zero or negative value.
The smallest non-negative ratio that results indicate
which variable will leave the solution.

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene
Syed T. Ph.D.
M. Ahmed,
 Step 4. Find unique vectors for the new
basic variable using row operations on the pivot
element.
Basic Cj 60 50 0 0 0
variable
X1 X2 S1 S2 S3 RHSV Ratio

S1 0 0 8 1 -2 0 56 56/8 = 7
X1 60 1 1/2 0 1/2 0 11 11/. 5 = 22

S3 0 0 3/2 0 -3/2 1 6 6/1.5 = 4

Zj 60 30 0 30 0 660
Cj-Zj 0 20 0 -30 0 0

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene
Syed M.T.Ahmed,
(2019)Ph.D.
 Optimal tableau

Basic
variable Cj 60 50 0 0 0 Ratio
X1 X2 S1 S2 S3 RHSV

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

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene
Syed T. Ph.D.
M. Ahmed,
 Cont’d

 Optimal solution: X1 = 9
 X2 = 4
 S1 = 24 hrs
 Z = Birr 740
 “A simplex solution is a maximization problem is optimal if
the Cj – Zj row consists entirely of zeros and negative numbers
(i.e., there are no positive values in the bottom row).”

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene
Syed M.T.Ahmed,
(2019)Ph.D.
 Cont’d

Note:
The variables in solution all have unit vectors in their
respective columns for the constraint equations.

Further, note that a zero appears in row c - z in every column

whose variable is in solution, indicating that its maximum
contribution to the objective function has been realized.

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene
Syed T. Ph.D.
M. Ahmed,
 The Simplex Method (3)
Example 2: 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.
BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene
Syed M.T.Ahmed,
(2019)Ph.D.
 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)

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene
Syed T. Ph.D.
M. Ahmed,
  Required:

Solve the above problem using simplex method

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene
Syed T. Ph.D.
M. Ahmed,
 Sensitivity Analysis
 Sensitivity analysis helps to test the sensitivity of the optimum
solution with respect to changes of the coefficients in the objective
function, coefficients in the constraints inequalities, or the constant
terms in the constraints.
 For Example in the case study discussed:
 The actual selling prices (or market values) of the two products may
vary from time to time. Over what ranges can these prices change
without affecting the optimality of the present solution?
 Will the present solution remain the optimum solution if the amount of
raw materials, production time, or storage space is suddenly changed
because of shortages, machine failures, or other events?
 The amount of each type of resources needed to produce one unit of
each type of product can be either increased or decreased slightly. Will
such changes affect the optimal solution ?
BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene
Syed T. Ph.D.
M. Ahmed,
 The Role of Sensitivity Analysis of the
Optimal Solution

 Is the optimal solution sensitive to changes in input

parameters?
 Possible reasons for asking this question:
 Parameter values used were only best estimates.
 Dynamic environment may cause changes.
 “What-if” analysis may provide economical and operational
information.

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene
Syed T. Ph.D.
M. Ahmed,
 Sensitivity Analysis of
Right-Hand Side Values
a change in the right-hand side for a constraint may
affect the feasible region and perhaps cause a change in
the optimal solution to the problem
In sensitivity analysis of right-hand sides of
constraints we are interested in the following
questions:
◦ Keeping all other factors the same, how much would the
optimal value of the objective function (for example, the
profit) change if the right-hand side of a constraint
changed by one unit?
◦ For how many additional or fewer units will this per
unit change be valid?
BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T. Ahmed,
Syed M. (2019)Ph.D.
 Shadow price

 Shadow prices are values in the Z row of the final (optimal)

simplex table.
 It is a marginal value.
 It shows the impact that a one unit change in the amount of
constraint would have on the value of the objective function

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T. Ahmed,
Syed M. (2019)Ph.D.
 60 50 0 0 0 RHS
Basis c X1 X2 S1 S2 S3
S1 0 0 0 1 6 -5.3333 24
X1 60 1 0 0 1 -0.3333 9
X2 50 0 1 0 -1 002/3 4
z 60 50 0 10 40/3 740
C-Z 0 0 -10 -13.333

Negative of
Shadow Shadow
prices prices
BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T. Ahmed,
Syed M. (2019)Ph.D.
  From the above table one can clearly see that:
 If resource one is increased by one unit, there would be no
effect on the profit.
 If the second resource is increased by one unit, profit will
increase by ten birr and
 If the third resource is increased by one unit, profit will
increase by 40/3 birr.
 shadow prices do not tell us by how much the level of
scarce resources can be increased and still have the same
impact per unit

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T. Ahmed,
Syed M. (2019)Ph.D.
  resources with positive shadow prices as scarce goods
(binding constraints) and resources with zero shadow prices
as free goods (surplus resource).
 At some point, the ability to use additional resources will
disappear because of the fixed amounts of the other
constraints.
 We need to determine the range over which we can change
the right hand side quantities and still have the same shadow
prices.
 This is called range of feasibility/ right hand range

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T. Ahmed,
Syed M. (2019)Ph.D.
 Sensitivity Analysis of
Right-Hand Side Values
 Any change to the right hand side of a binding
constraint will change the optimal solution.

 Any change to the right-hand side of a non-binding

constraint that is less than its slack or surplus, will
cause no change in the optimal solution.

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T. Ahmed,
Syed M. (2019)Ph.D.
 Cont’d

 To find range of feasibility for the right hand side, divide the
entries in the quantity column by associated slack column
values.
 The smallest positive ratio indicates the allowable decrease and
negative ratio closest to zero indicates allowable increase

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T. Ahmed,
Syed M. (2019)Ph.D.
 Cont’d

For the previous example:

For the first variable
Allowab
4/ (1/3) =
le
12
decrease
7/ (-2/3)
There are only two ratios one positive and the other
negative. = -21/2 Allowabl
Increas
e
Hence, the first resource can be reduced by 12 and
e
increased by 21/2.

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T. Ahmed,
Syed M. (2019)Ph.D.
 Cont’d

Hence, range of feasibility for resource one is:

0 ≤ b1≤ 45/2 Construct
the range of feasibility for resource two.

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T. Ahmed,
Syed M. (2019)Ph.D.
 For second constraint

4/0=undefined
7/1=7
Hence, 15-7≤b2≤∞
8 ≤b2≤∞
Allowable
decrease

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T. Ahmed,
Syed M. (2019)Ph.D.
 Sensitivity Analysis of
Objective Function Coefficients.

Range of Optimality
The range of optimality for each objective function
coefficient provides the range of values over which the
current solution will remain optimal.
◦ The optimal solution will remain unchanged as long as
🞄 An objective function coefficient lies within its range of
optimality
🞄 There are no changes in any other input parameters.

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T. Ahmed,
Syed M. (2019)Ph.D.
 Cont’d

 Managerial attention should be focused on those objective

function coefficients that have a narrow range of optimality and
coefficients near the end points of the range.
 With these coefficients, a small change can necessitate
modifying the optimal solution

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T. Ahmed,
Syed M. (2019)Ph.D.
 Example

Consider:
Max! X1+ 2X2
Subject to: 2X1 + 3X2≤ 12
5X1 + 2X2 ≤ 15
X1, X2 ≥ 0
Solve using simplex method.

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T. Ahmed,
Syed M. (2019)Ph.D.
 Optimal solution

1 2 0 0
BV CB X1 X2 S1 S2 RHS
V
X2 2 2/3 1 1/3 0 4
S2 0 11/3 0 -2/3 1 7
Z 4/3 2 2/3 0 8
C-Z -1/3 0 -2/3 0

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T. Ahmed,
Syed M. (2019)Ph.D.
 Cont’d

 For all non-basic variables range of insignificance will be

given by -∞≤ Cj ≤ Z.
 The non-basic variable will remain non-basic so long as Cj
≤ Zj.
 Hence, the range of insignicance for X1 is
 -∞≤ Cj ≤ 4/3

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T. Ahmed,
Syed M. (2019)Ph.D.
 For basic variable

For variables which are in the solution, the determination

of range of optimality requires different approach.
The value in C-Z row must be divided by the
corresponding row values of the variable in question.
The smallest positive ratio will indicate the allowable
increase and the smallest negative ratio (absolute value)
indicates the allowable decrease.
If there is no positive ratio there is no upper limit in
variables objective function coefficient

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T. Ahmed,
Syed M. (2019)Ph.D.
 Cont’d

Therefore ratios calculated for the row are:

-1/2 Allowable
decrease
0
-2 No positive ratio; hence there
is no upper limit
0/0

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T. Ahmed,
Syed M. (2019)Ph.D.
 Cont’d

 As you can see, the smallest negative ration (in terms of

absolute value) is -1/2 and there is no positive ratio.
 Hence, the coefficient of X2 can be reduced by 0.5 and
increased indefinitely without making it non basic.

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T. Ahmed,
Syed M. (2019)Ph.D.
 Cont’d

Therefore, the range of optimality for X2 is:

(2-0.5) ≤ C2 ≤∞ = 1.5 ≤ C2 ≤ ∞

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T. Ahmed,
Syed M. (2019)Ph.D.
 Complications in Simplex Method

 An objective function to be minimized instead of maximized.

 Greater-than-or-equal-to constraints.
 Equalities instead of inequalities for constraints.
 Decision variables unrestricted in signs.
 Zero constants on the right-hand side of one or more
constraints.
 Some or all decision variables must be integers.
 Non-positive constants on the right-hand side of the constraints.
 More than one optimal solution, that is, multiple solutions such
that there is no unique optimal solution.

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T. Ahmed,
Syed M. (2019)Ph.D.
 Minimization problems

 Manual solution of minimization problems using simplex

method are handled in the same fashion as maximization
problem with mixed constraints.
 The two key exceptions are:
 M coefficients in the objective function must be assigned a large
positive number.
 Selection of variables to enter the solution is based on the largest
negative value in row C-Z

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T. Ahmed,
Syed M. (2019)Ph.D.
 Example

Minimize Z= 7X + 9Y
Subject to: 3X + 6Y ≥ 36
8X + 4Y ≥ 64
X, Y ≥ 0

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T. Ahmed,
Syed M. (2019)Ph.D.
 In standard form

Minimize Z= 7X + 9Y + 0S1 + 0S2+MA1+MA2

Subject to: 3X + 6Y –S1 +A1 = 36
8X + 4Y –S2 + A2 = 64
All variables ≥ 0

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T. Ahmed,
Syed M. (2019)Ph.D.
 Initial table

BV CBV X S1 S2 A1 A2
9 0 0 M M
Y
7
A1 M 3 6 -1 0 1 0 36
A2 M 8 4 0 -1 0 1 64

Z 11M 10M -M -M M M 100M

C-Z 7-11M 9-10M M 0 0
M
To be optimal C-Z>=0

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T. Ahmed,
Syed M. (2019)Ph.D.
 2nd table

BV CBV X Y S1 S2 A2
A1
7 9 0 0 M M

A1 M 0 9/2 -1 3/8 1 0 12
X 7 1 1/2 0 -1/8 0 1/8 8
Z 7 7/2+9M/2 - M 3M/8 -7/8 M 7/8 56 + 12M
C-Z 0 11/2- 9M/2 M -3M/8 + 7/8 0 M-7/8

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T. Ahmed,
Syed M. (2019)Ph.D.
 3rd Table

BV CBV X Y S1 S2
7 9 0 0

Y 9 0 1 -2/9 1/12 8/3

X 7 1 0 1/9 -1/6 20/3

Z 7 9 -11/9 -5/12 212/3

C-Z 0 0 11/9 5/12

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T. Ahmed,
Syed M. (2019)Ph.D.
 Maximization with mixed constraints

 The simplex method requires that all the constraints be in

standard form.
 Constraints that are ≤ can be put in to standard form by
adding a slack variable in the constraint.
 Constraints with ≥or = sign are handled a bit differently.

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T. Ahmed,
Syed M. (2019)Ph.D.
 Cont’d

 To change equality constraints to standard form add

artificial variables
 To covert this inequality to standard form subtract surplus
variable first and add artificial variable

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T. Ahmed,
Syed M. (2019)Ph.D.
 Solve using simplex method

Max! 6X + 8Y
Subject to: Y≤4
X+Y=9
6X+
2Y ≥
24
X, Y ≥
0

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T. Ahmed,
Syed M. (2019)Ph.D.
 In standard form

Max! 6X + 8Y + 0S1 + 0S3 - MA1 – MA3

Subject to: Y+ S1 = 4
X+Y + A2 = 9
6X+ 2Y –S3 +
A3 = 24
All variables ≥
0

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T. Ahmed,
Syed M. (2019)Ph.D.
 Initial table

BV CBV X Y S1 S3 A2 A3 Quantity
6 8 0 0 -M -M

S1 0 0 1 1 0 0 0 4
A2 -M 1 1 0 0 1 0 9
A3 -M 6 2 0 -1 0 1 24

Z -7M -3M 0 M -M -M -33M

C-Z 6+ 7M 8+3M 0 -M 0 0

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T. Ahmed,
Syed M. (2019)Ph.D.
 Second table

BV CBV X Y S1 S3 A2 A3 Quantity
6 8 0 0 -M -M

S1 0 0 1 1 0 0 0 4
A2 -M 0 2/3 0 1/6 1 -1/6 5
X 6 1 1/3 0 -1/6 0 1/6 4

Z 6 2-2M/3 0 -1M/6 -1 -M 1+M/6 24 - 5M

C-Z 0 6+2M/3 0 1+ M/6 0 -1-m/6

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T. Ahmed,
Syed M. (2019)Ph.D.
 Third table

BV CBV X Y S1 S3 A2 Quantity
6 8 0 0 -M

Y 0 0 1 1 0 0 4
A2 -M 0 0 -2/3 1/6 1 7/3
X 6 1 0 -1/3 -1/6 0 8/3

Z 6 8 6 + 2M/3 -M/6 -1 -M 48 -7M/3

C-Z 0 0 -6-2M/3 1+ M/6 0

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T. Ahmed,
Syed M. (2019)Ph.D.
 Fourth table

BV CBV X Y S1 Quantity
S3
6 8 0
0
Y 0 1 1 4
8 0
14
S3 0 0 -4
5
0 1
X 1 0 -1
6 0

Z
BCN67755
6 8 2 62
0 Compiled by: Dr. Dejene T. Ahmed,
(2019)Ph.D.
C-Z
Decision and Risk Analysis Syed M.
 Complications in Simplex Method (2)
 The constraints are such that no feasible solution exists.
 The constraints are such that one or more of the variables can
increase without limit and never violate a constraint (i.e., the
solution is unbounded).

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T. Ahmed,
Syed M. (2019)Ph.D.
 Duality (1)

 With every linear programming problem, there is associated another

linear programming problem which is called the dual of the original
(or the primal) problem.

Formulating the Dual problem

 Consider again the production mix problem of N. Dustrious
Company.
 Suppose that the company is considering leasing out the entire
production facility to another company, and it must decide on the
minimum daily rental price that will be acceptable.
 This decision problem can also be formulated as a linear
programming problem.

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T. Ahmed,
Syed M. (2019)Ph.D.
 Duality (2)

 Let y1, y2 and y3 represent the unit price of each unit of storage
space, raw materials, and production time, respectively.
 The unit prices are in fact the income values of each unit of
resource to the N. Dustrious Company.
 There are available 500 ft2 of storage space, 1575 lb of raw
materials, and 420 minutes of production time per day.
 Thus the total income value (P) of all the available resources
may be expressed as follows :
P = 1500y1 + 1575y2 + 420y3
 The objective of the problem is to minimize P subject to the
condition that the N. Dustrious Company will earn at least as much
income as when it operates the production facility itself.
BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T.(2019)
Syed M. Ahmed, Ph.D.
 Duality (3)

 Since the market value (or selling price) of 1 unit of product I is

$13 and it requires 4 ft2 of storage space, 5 lbs of raw materials, and 1
minute of production time, the following constraint must be satisfied:
4y1 + 5y2 + 5y3  13

 Similarly, for Product II:

5y1 + 3y2 + 2y3  11

 In addition, the unit prices y1, y2 and y3 must all be greater than or
equal to zero.

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T.(2019)
Syed M. Ahmed, Ph.D.
 Duality (4)

 The new linear programming problem may now be summarized

as follows :

…….Eq. (1)

 The following interesting observations can now be made: o P

= Z = $4335
o y1 = $0; y2 = $15/7 and y3 = $16/7
 This problem is the same as maximization problem in the
previous example and can now be solved accordingly.
BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T.(2019)
Syed M. Ahmed, Ph.D.
 Duality (5)

The primal-Dual Relationship

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T.(2019)
Syed M. Ahmed, Ph.D.
 WORKED –OUT PROBLEM 2

Example

Form the dual problem:

Minimize C = 16 x1 + 9x2 + 21x3

subject to x1 + x2 + 3x3 ≥ 12
2x1 + x2 +x3 ≥ 16
x1, x2, x3 ≥ 0

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T.(2019)
Syed M. Ahmed, Ph.D.
 Solution of Minimization Problems

ORIGINAL PROBLEM (1) DUAL PROBLEM (2)

Minimize C = 16x1 + 45x2 Maximize P = 50y1 + 27y2

subject to 2x1 + 5x2 ≥ 50 subject to 2y1 + y2  16

x1 + 3x2 ≥ 5y1 + 3y2  45
y1,y2 ≥ 0
27
x 1, x 2 ≥ 0

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T.(2019)
Syed M. Ahmed, Ph.D.
 Questions/Queries?

BCN67755
Decision and Risk Analysis Compiled by: Dr. Dejene T.(2019)
Syed M. Ahmed, Ph.D.