Daniela Felisa B. Jacinto 2. Statistical analysis and forecasting (e.g.

regression
Econ 162 2nd Semester 2017-2018 (1st Exam) analysis)
3. Optimization (mathematical programming): Finding the
Economic Decisions and Mathematical Optimization optimal (most efficient) way of using limited resources
Problems
4. Game theory

Scope of Managerial Economics

Theory of the Firm
- Douglas: Managerial Economics is the application of
- Goal: Maximize the long-term value of the firm
economic principles and methodologies to decision-
(sustainability)
making process within the firm or organization.
- Salvatore: Managerial Economics refers to the application 𝑁 𝑁
𝑃𝑟𝑜𝑓𝑖𝑡 𝑡𝑜𝑡𝑎𝑙 𝑟𝑒𝑣𝑒𝑛𝑢𝑒 − 𝑡𝑜𝑡𝑎𝑙 𝑐𝑜𝑠𝑡
of economic theory and the tools of analysis of decision 𝑉𝑎𝑙𝑢𝑒 = ∑ = ∑
(1 + 𝑖)𝑡 (1 + 𝑖)𝑡
𝑖=𝑡 𝑖=𝑡
science to examine how an organization can achieve its
objectives most effectively.
- Discount rate increases over time.
- Profit: Business or accounting profit vs. economic profit
Management Decision Problems
o Accounting Cost: What comes out in your
1. Product price and output
balance sheet
2. Production technique (in an economic sense, the
o Economic Cost: Opportunity cost (value resource
proportion of input to output, such as the mix of labor
would’ve earned in an alternative activity)
and capital)
o Example: A secretary being paid Php10,000
3. Make or buy
(accounting cost) should really be paid
4. Inventory level
Php15,000 (economic cost).
5. Advertising medium and intensity
o Normal rate of return: If you are paying all your
6. Labor hiring and training
resources the value they would’ve earned
7. Investment and financing
elsewhere, economic profit = 0. (value of

Economic Concepts: Framework for Decisions revenue = value of cost)

- Theory of Consumer Behavior - Economic profits or losses exist when:
o How consumers choose o Barriers to entry: Monopoly Profit (above normal
o Consumers have preferences and choose based rate of return)
on those preferences.  Positive economic profit
o Consumers try to maximize their utility but are  Product sells higher than opportunity
constrained by their budget. cost used in producing it
- Theory of the Firm  Happens when someone has market
o Technology of a firm (vs. preference of power or monopoly power, restricting
consumer) potential competitors
o Try to maximize profit o Unexpected changes in demand and supply:
- Theory of Market Structure and Pricing Frictional Profit
o Pricing depends on kind of market  Example: After a storm, producers take
o Market can go from perfect competition to advantage of the high demand.
monopoly o Successful invention of innovation:
Schumpeterian Profit (reward for innovation)
Decision Science: Tools and Techniques of Analysis
1. Numerical analysis
 o Extraordinary success in meeting customer needs 𝜋 = 𝑅𝑒𝑣𝑒𝑛𝑢𝑒 − 𝐶𝑜𝑠𝑡

and maintaining efficient operations:

𝜋 = 31.8𝑞 − 0.05𝑞2 − (1,000 + 9𝑞 + 0.064𝑞2 )
Compensatory Profit (reward for good business
foresight) 𝑑𝜋
= 31.8 − 0.1𝑞 − 9 − 0.128𝑞 = 0
𝑑𝑞
Do firms maximize profit?
- Optimize vs. satisfice 𝑀𝑅 = 𝑀𝐶

- Separation of management and ownership

31.8 − 0.1𝑞 = 9 + 0.128𝑞
o Managers who don’t own the firm are more risk-

averse because they are answerable to the actual 𝑑2 𝜋

= −0.1 − 0.128 = −0.228
owners. 𝑑𝑞2

o Internal market discipline: Managers still end up

𝑞 = 100
thinking like owners because if they don’t
maximize the firm’s profits, their income will also
 1st Condition: When you make marginal profit = 0 and
be affected.
solve for q, what you come up with is the quantity where
o Optimal contract (compensation scheme): Fixed
the additional revenue from producing any more would
wage + profit-contingent compensation
add an equal amount to your cost.
o Labor market discipline: Poor performance
 2nd Condition: At q = 100, MR = MC.
creates bad reputation for managers
 3rd Condition: Profit you make by producing more (e.g.
o Product market discipline: Firms are likely to go
200) can only be lower than profit made at optimal q (100)
under if profit is not maximized
or else you were never at the maximum profit in the first
o Capital market discipline: Vulnerability to
place.
corporate raid or takeover (when value of firm is
lower than its potential)
Profit Maximization Example 2

Profit Maximization Example 1

Suppose a firm’s inverse demand function is given by 𝑝 = 120 −
0.5𝑞 and its cost function is 𝐶 = 420 + 60𝑄 + 𝑄 2 .
Profit = Revenue – Cost
a. Find the firm’s optimal quantity, price, and profit.

𝑝 = 31.8 − 0.05𝑞
𝐶 = 1,000 + 9𝑞 + 0.064𝑞2 𝜋 = (120 − 0.5𝑄)𝑄 − (420 + 60𝑄 + 𝑄 2 )

𝑑𝜋
Note = 120 − 𝑄 − 60 − 2𝑄 = 0
𝑑𝑄
 Demand equation in given is an inverse demand function
because, here, p is determined by q. In reality, it’s price 𝜕2𝜋
= −1 − 2 = −3 < 0
𝜕𝑄 2
that determines demand. Not the other way around. (q
should be dependent variable_
𝑄 = 20, 𝑃 = 110, 𝜋 = 180
 2 types of cost: fixed (1,000) and variable

 At maximum profit, 3 conditions are fulfilled: b. Suppose instead that the firm can sell any and all of its
𝜕𝜋
a.) Marginal profit = 0 ( = 0) output at the fixed market price of 120. Find the firm’s
𝜕𝑞

b.) Marginal revenue = Marginal cost optimal output.

𝜕2 𝜋
c.) Marginal profit is declining ( < 0)
𝑑𝑞 2
𝜋 = 120𝑄 − (420 + 60𝑄 + 𝑄 2 )
 Profit Maximization Example 3
𝑑𝜋
= 120 − 60 − 2𝑄 = 0
𝑑𝑄 Leda Co. is developing a new product. An early introduction

(beating rivals to the market) would greatly enhance the company’s

𝑄 = 30, 𝑃 = 120, 𝜋 = 480
revenues. However, the ____ development effort needed to
expedite the introduction can be very expensive. Suppose the total
Note
revenues and costs associated with the new product’s introduction
 Profit in B is higher because every additional unit sold
are given by 𝑅 = 720 − 8𝑡 and 𝐶 = 600 − 20𝑡 + 0.25𝑡 2 , where t is
earns him an additional 120. (MR=120)
the introduction date (months from now). Some executives agreed
 In A, the firm is prevented from selling more than 20
for an expedited introduction date 12 months from now (t=12). Do
because at any Q > 20, MC will be greater than MR and
you agree?
marginal profit will be negative.

 Example: If A made Q = 30, MC > MR.  Negative profit

𝜋 = 720 − 8𝑡 − (600 − 20𝑡 + 0.25𝑡 2 )

𝑑𝑅
𝑀𝑅 = = 120 − 𝑄 = 120 − 30 = 90 You want to find time, t where profit, 𝜋 is stationary.
𝑑𝑄

𝑑𝐶 𝜋
𝑀𝐶 = = 60 + 2𝑄 = 60 + 60 = 120
𝑑𝑄

 Example: If A made Q = 20, MR = MC.  Optimal

𝑑𝑅
𝑀𝑅 = = 120 − 𝑄 = 120 − 20 = 100
𝑑𝑄 t

𝑑𝐶 𝑑𝜋
𝑀𝐶 = = 60 + 2𝑄 = 60 + 40 = 100 = −8 + 20 − 0.5𝑡 = 0
𝑑𝑄 𝑑𝑡

 Firm sells more in B because the price is fixed. Selling 𝑡 = 24

disagree
more in A would lower the price per unit.

Profit Maximization Example 4

Firm A Firm B Multivariate Optimization

Suppose a firm’s profit function is given by 𝜋 = 20 + 2𝑃 − 2𝑃 2 +

4𝐴 − 𝐴2 + 2𝑃𝐴 where P is price and A is advertising. Find the values

of P and A that will maximize profit.

1st Step: Get partial derivatives.

 Imperfectly competitive market: Downward sloping
demand curve for individual firm
𝜕𝜋
(𝑎) = 2 − 4𝑃 + 2𝐴 = 0
 Perfectly competitive market: Horizontal demand curve 𝜕𝑃
for individual firm
𝜕𝜋
a.) No matter how much output an individual firm (𝑏) = 4 − 2𝐴 + 2𝑃 = 0
𝜕𝐴
provides, it will be unable to affect the market
price. 2nd Step: Solve both equations together.
 (𝑎) 2 − 4𝑃 + 2𝐴 = 0 In this example, you are maximizing Q, which has 2 types: medical
2𝐴 = 4𝑃 − 2
𝐴 = 2𝑃 − 1 and social service.

(𝑏) 4 − 2(2𝑃 − 1) + 2𝑃 = 0 𝑀𝑎𝑥 𝑄 = 𝑀 + 0.5𝑆 + 0.5𝑀𝑆 − 𝑆 2

4 − 4𝑃 + 2 + 2𝑃 = 0 such that 30,000𝑆 + 60,000𝑀 = 1,200,000
6 − 2𝑃 = 0
𝑃=3
You equate your expenses to your budget because you want to
𝐴 = 2𝑃 − 1 maximize the service by using up all resources available.
𝐴 = 2(3) − 1 = 5

ℒ = 𝑀 + 0.5𝑆 + 0.5𝑀𝑆 − 𝑆 2 + 𝜆(1,200,000 − 30,000𝑆 − 60,000𝑀)

Profit Maximization Example 5
Constrained Optimization
𝜕ℒ
𝑎) = 1 + 0.5𝑆 − 60,000𝜆 = 0
𝜕𝑀
Suppose the firm’s profit is estimated to be 𝜋 = −10,000 + 400𝑄 −
2𝑄 2 . The firm faces a constraint in production in that 4 hours of
skilled labor are required to produce a unit, and only 300 hours of 𝜕ℒ
𝑏) = 0.5 + 0.5𝑀 − 2𝑆 − 30,000𝜆 = 0
𝜕𝑆
labor are available. Calculate the profit-maximizing profit and value

of 𝜆. 𝜕ℒ
𝑐) = 1,200,00 − 30,000𝑆 − 60,000𝑀 = 0
𝜕𝜆
𝑀𝑎𝑥 𝜋 = −10,000 + 400𝑄 − 2𝑄 2
such that 4𝑄 ≤ 300 Solve all 3 equations together.

Logically, to maximize profit, you would use all 300 hours available 𝑎) 1 + 0.5𝑆 − 60,000𝜆 = 0

so you make constraint 400 = 300.

1 + 0.5𝑆 = 60,000𝜆

ℒ = −10,000 + 400𝑄 − 2𝑄 2 + 𝜆(300 − 4𝑄) 1 + 0.5𝑆

𝜆=
60,000
𝜕ℒ
= 400 − 4𝑄 − 4𝜆 = 0
𝜕𝑄
𝑏) 0.5 + 0.5𝑀 − 2𝑆 − 30,000𝜆 = 0

𝜕ℒ
= 300 − 4𝑄 = 0 1 + 0.5𝑆
𝜕𝜆 0.5 + 0.5𝑀 − 2𝑆 − 30,000 ( )=0
60,000

𝑄 = 75, 𝜆 = 25
1 + 0.5𝑆
0.5 + 0.5𝑀 − 2𝑆 − ( )=0
2
Maximization Example 6
Constrained Optimization 1 + 𝑀 − 4𝑆 − 1 − 0.5𝑆 = 0

AHC is considering hiring medical (M) and social service (S) staff. 𝑀 = 4.5𝑆
It’s determined that service (Q) can be described as follows: 𝑄 =
𝑀 + 0.5𝑆 + 0.5𝑀𝑆 − 𝑆 2 . AHC has a budget of 1.2 million/month. 𝑐) 1,200,000 − 30,000𝑆 − 60,000𝑀 = 0

Monthly employment costs are 30,000 per social service member

1,200,000 − 30,000𝑆 − 60,000(4.5𝑆) = 0
and 60,000 per medical member.
a. Construct the Lagrangian function that would determine 1,200,000 − 30,000𝑆 − 270,000𝑆 = 0
the service-maximizing employment combination.
𝑆=4
 1 + 0.5𝑆 1 + 0.5(4) 𝑔2 (𝑥) = 𝑔2 (𝑥1 , … , 𝑥𝑛 ) ≤ 𝑏2
𝜆= = = 0.00005
60,000 60,000 ⋮
𝑔𝑚 (𝑥) = 𝑔𝑠 (𝑥1 , … , 𝑥𝑛 ) ≤ 𝑏𝑚
𝑥1 ≥ 0, 𝑥2 ≥ 0, … , 𝑥𝑛 ≥ 0
𝑀 = 4.5𝑆 = 4.5(4) = 18

𝑆 = 4, 𝑀 = 18, 𝜆 = 0.00005 - Example: Maximize sales subject to a profit constraint.

Mathematical Optimization Problems 𝑀𝑎𝑥 𝑓(𝑥, 𝑦) = 𝑥 2 + 2𝑦 2 − 𝑥𝑦

- Involves choosing values of certain variables to optimize a subject to 𝑥 + 𝑦 ≤ 8
function subject to constraints

- Could be for maximizing or minimizing a function Linear Programming

- Objective function is linear and the constraints are linear
- Variables (that the function is dependent on) are called
inequality constraints and non-negativity constraints
instruments
- The function to be optimized is the objective function
𝑓 (𝑥) = 𝑐1 𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐𝑛 𝑥𝑛
- Example: 𝑦 = 𝑓(𝑥)
o y  objective function
subject to
o x  instrument
o you want to maximize or minimize y 𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 ≤ 𝑏1
- The instrument x is feasible if it satisfies all the constraints 𝑎21 𝑥1 + 𝑎22 𝑥2 + ⋯ + 𝑎2𝑛 𝑥𝑛 ≤ 𝑏2
⋮
of the problem.
𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥2 + ⋯ + 𝑎𝑚𝑛 𝑥𝑛 ≤ 𝑏𝑚
- The set of all feasible x is the opportunity set of x, which 𝑥1 ≥ 0, 𝑥2 ≥ 0, … , 𝑥𝑛 ≥ 0

consists of the values of x allowed by the given

Geometrical Solution to Mathematical Optimization Problems
limits/constraints.

- Contour: (of the objective function) is the set of points for

𝑀𝑎𝑥 𝑓(𝑥) subject to 𝑥 𝜖 𝑋
which the value of the objective function is constant
- Contour Map: Set of contours
Mathematical Programming Problems
- Preference Direction: Direction in which the value of the
Classical Programming
objective function is increasing (if maximizing) or
- Equality constraints
decreasing (if minimizing)

𝑔1 (𝑥) = 𝑔𝑠 (𝑥1 , … , 𝑥𝑛 ) = 𝑏1 - Mathematical Optimization Problems: Choosing a point or

𝑔2 (𝑥) = 𝑔2 (𝑥1 , … , 𝑥𝑛 ) = 𝑏2
set of points in the opportunity set at the highest possible
⋮
𝑔𝑚 (𝑥) = 𝑔𝑠 (𝑥1 , … , 𝑥𝑛 ) = 𝑏𝑚 contour (if you’re maximizing) or lowest possible contour
(if you’re minimizing)
where 𝑔1 (𝑥), 𝑔2 (𝑥),…,𝑔𝑚 (𝑥) are called constraint functions, and 𝑏1 ,

𝑏2 ,…,𝑏𝑚 are called constants. Possible Solutions to Programming Problems

- Example: Minimize cost subject to output constraint. Classical Programming

Consumer Problem
𝑀𝑖𝑛 𝐶 = 3𝑥 2 + 6𝑦 2 − 𝑥𝑦
subject to 𝑥 + 𝑦 = 20 𝑀𝑎𝑥 𝑈 = 𝑥𝑦 subject to 𝑀 = 𝑃𝑥 𝑋 + 𝑃𝑦 𝑌

Nonlinear Programming
- Non-negativity constraints and inequality constraints

𝑔1 (𝑥) = 𝑔𝑠 (𝑥1 , … , 𝑥𝑛 ) ≤ 𝑏1
 y

𝑀 Linear Programming
𝑃𝑦
𝑀𝑎𝑥 𝐹 = 3𝑥1 + 2𝑥2
subject to 2𝑥1 + 𝑥2 ≤ 6
𝑥1 + 2𝑥2 ≤ 8
x 𝑥1 , 𝑥2 ≥ 0
𝑀 x2
𝑃𝑥

Tangency Solution

- Objective function here is non-linear because you take xy

x1
as one term.

- Constraint is linear because 𝑃𝑥 and 𝑃𝑦 are parameters

(constants). Vertex Solution at (4/3,10/3)

- Vertical Intercept:
𝑀 (unique solution)
𝑃𝑦
𝑀
- Horizontal Intercept:
𝑃𝑥
Note: Along a contour, the value of the objective function is
- Income can only buy combinations of x and y that are
constant.
within the triangle or on the diagonal.
- Because you are maximizing, get the point on the
diagonal that is tangent to a utility curve. x2

- Preference Direction: Northeast

Non-linear Programming

𝑀𝑎𝑥 𝐹(𝑥1 , 𝑥2 ) = −8𝑥 2 − 10𝑥22 + 12𝑥1 𝑥2 − 50𝑥1 + 80𝑥2

subject to 𝑥1 + 𝑥2 ≤ 1 x1

8𝑥12 + 𝑥22 ≤ 2 Bounding Face Solution

𝑥1 , 𝑥2 ≥ 0
All points on the line segment (thick, red line) are solutions so you
x2
have an infinite number of points/solutions.

Linear Programming

Leontief Production Function

𝐿 𝐾
x1 𝑞 = 𝑚𝑖𝑛 { , }
𝑎 𝑏
Boundary Solution at (0,1)
x2 where q is output, L is labor, K is capital, a is the amount of labor
needed to produce 1 unit of output, and b is the amount of capital
needed to produce 1 unit of output.

Note: Look at what you have less of then match it with the

x1 appropriate amount of the other input.

Interior Solution
Example 1
Only 1 production technique

L = 100
K = 200
a=2
b=1
100 200
𝑞 = 𝑚𝑖𝑛 { , }
2 1
Note: Midpoint of the line segment (thick black line) is where 50%
𝑞 = 50 of production technique 1 is used and 50% of production
technique 2 is used.
At q = 50, you use up all of your available labor and end up with
excess capital. Example 3
3 production techniques

K 𝐾 = 2𝐿
𝑞1 = min{𝐿, 0.5𝐾}

𝐾 =L
𝑞3 = min{0.8𝐿, 0.8𝐾}

𝐾 = 0.5L
𝑞3 = min{0.5𝐿, 𝐾}

- Isoquant: L-shaped figure

- x, y, z produce the same output but using different inputs Note: The more production techniques you have, the smoother the

o x: more L used isoquant (curve).

o y: more K used
o z: minimum labor and capital used Suppose a firm can choose among the following linear processes:
𝑞1 = 𝑚𝑖𝑛{𝐿, 0.5𝐾}
- Only produce at point Z because producing at any other
𝑞2 = min{0.5𝐿, 𝐾}
point is inefficient. 𝑞3 = 𝑚𝑖𝑛{0.8𝐿, 0.8𝐾}
𝐿 𝐾 𝑏
- At point z, = so 𝐾 = ( ) 𝐿
𝑎 𝑏 𝑎
The total input requirements are:
Example 2 𝐿 = 𝑞1 + 2𝑞2 + 1.25𝑞3
𝐾 = 2𝑞1 + 𝑞2 + 1.25𝑞3
2 production techniques

𝐿 𝐾 Problem:
𝑞1 = 𝑚𝑖𝑛 { , } 𝑀𝑎𝑥 𝑅 = 𝑝𝑞1 + 𝑝𝑞2 + 𝑝𝑞3
𝑎 𝑏
𝐿 𝐾 subject to
𝑞2 = 𝑚𝑖𝑛 { , }
𝑐 𝑑
𝑞1 + 2𝑞2 + 1.25𝑞3 ≤ 𝐿0
2𝑞1 + 𝑞2 + 1.25𝑞3 ≤ 𝐾0
𝑞1 , 𝑞2 , 𝑞3 ≥ 0

Linear Programming Problems

Example 1
A company produces 2 commodities, 𝑥1 and 𝑥2 . These 2 products
are processed through 2 machines. Maximum hours available are
120 and 180 for machines 1 and 2, respectively. Profit is Php45 for A (0,18) 990
𝑥1 and Php55 for 𝑥2 . Determine the optimal 𝑥1 and 𝑥2 that should B (10,15) 1,275
be manufactured in order to maximize profit. C (20,0) 900

D (0,0) 0
𝑥1 𝑥2 Hours
Machine 1 6 4 120
The solution is point B, where 𝑥1 = 10 and 𝑥2 = 15.
Machine 2 3 10 180

Profit / unit 45 55 Example 2

A small company manufactures different kinds of computers: a
𝑀𝑎𝑥 𝜋 = 45𝑥1 + 55𝑥2
basic model, x and an upscale model with several added
such that 6𝑥1 + 4𝑥2 ≤ 120
3𝑥1 + 10𝑥2 ≤ 180 components, y. The basic model yields the firm 100 per unit in
𝑥1 , 𝑥2 ≥ 0 profit, whereas the upscale model yields 250 per unit in profit. The
𝑥2 firm employs 5 workers who assemble the computers and 2
workers who run diagnostic tests on the computers before they are
6𝑥1 + 4𝑥2 ≤ 120
sold. Each employee works 40 hours per week. It takes 1 hour to

A assemble the basic model and 3 hours to assemble the upscale

B
3𝑥1 + 10𝑥2 ≤ 180 model. It takes 1 hour to run diagnostic tests on the upscale

𝑥1 models, but only 0.5 hour to run diagnostic tests on the basic
D
C model. At what quantities of x and y should the company produce
to maximize profit?
Notes
 The shaded area is the feasible region.
y
 Vertex solution is found along the bounding face solution.
 Whether the solution is a vertex solution or a bounding 0.5𝑥 + 𝑦 ≤ 80
face solution, the solution is always a vertex.

 Intuitively, point D cannot be a solution because not a

b
producing anything will not give you any revenues. 𝑥 + 3𝑦 ≤ 200
 Contour must intersect with the vertex. x
d
c
𝑀𝑎𝑥 𝜋 = 100𝑥 + 250𝑦
Point A  (0,18) such that 𝑥 + 3𝑦 ≤ 200

Point B  Intersection of first 2 constraints 0.5𝑥 + 𝑦 ≤ 80

𝑥, 𝑦 ≥ 0
Point C  (20,0)

Notes
Point B
 Automatically eliminate point d because not producing
6𝑥1 + 4𝑥2 = 120
3𝑥1 + 10𝑥2 = 180 anything will not maximize your profits.
 Solve for point b:

Note: Use equal signs instead of inequality signs because the point

is on the boundary of the constraint. 𝑥 + 3𝑦 = 200

0.5𝑥 + 𝑦 = 80

𝑥1 = 10, 𝑥2 = 15
𝑥 = 80, 𝑦 = 40

Point (𝑥1 , 𝑥2 ) VOF

Point (𝑥1 , 𝑥2 ) VOF
 𝑥2
A (0,181/3) 16,667 a
B (80,40) 18,000

C (160,0) 16,000 b
c
D (0,0) 0

𝑥1
The solution is point B, where 𝑥 = 80 and 𝑦 = 40.

Point (𝑥1 , 𝑥2 ) VOF

Would adding more assembly workers and more testers add to
A (0,6) 60
more profits?
B (0,5) 50
Answer: Yes, because by doing so, you will have more time to
C (4/3,10/3) 36
produce more computers. (Constraints will change)

Example 3 General Form of LPP

A company produces 2 commodities, 𝑥1 and 𝑥2 , and wishes to

 n variables (instruments), m constraints
minimize cost, 𝐶 = 2𝑥1 + 10𝑥2 subject to the constraints:
 Maximization Program
2𝑥1 + 𝑥2 ≤ 6
5𝑥1 + 4𝑥2 ≥ 20
𝑥1 , 𝑥2 ≥ 0 𝑀𝑎𝑥 𝑐𝑜 = 𝑐1 𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐𝑛 𝑥𝑛
Determine the optimal quantities of each commodity to be
produced and its associated cost. subject to

𝑀𝑖𝑛 𝐶 = 2𝑥1 + 10𝑥2 𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 ≤ 𝑏1

subject to 𝑎21 𝑥1 + 𝑎22 𝑥2 + ⋯ + 𝑎2𝑛 𝑥𝑛 ≤ 𝑏2
2𝑥1 + 𝑥2 ≤ 6 ⋮
5𝑥1 + 4𝑥2 ≥ 20 𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥2 + ⋯ + 𝑎𝑚𝑛 𝑥𝑛 ≤ 𝑏𝑚
𝑥1 , 𝑥2 ≥ 0 𝑥𝑖 ≥ 0 (𝑖 = 1, … , 𝑛)

Steps  Minimization Program

1. Get the vertical and horizontal intercepts of each

𝑀𝑖𝑛 𝑐𝑜 = 𝑐1 𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐𝑛 𝑥𝑛
constraint.

2. Connect the intercepts to get the curve of the constraint.

subject to
3. Determine the area to be considered by looking at the
inequality signs of the constraints.
𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 ≥ 𝑏1
4. Determine the vertices. 𝑎21 𝑥1 + 𝑎22 𝑥2 + ⋯ + 𝑎2𝑛 𝑥𝑛 ≥ 𝑏2
⋮
5. Calculate the VOF for each vertex.
𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥2 + ⋯ + 𝑎𝑚𝑛 𝑥𝑛 ≥ 𝑏𝑚
𝑥𝑖 ≥ 0 (𝑖 = 1, … , 𝑛)

 You can convert inequality constraints into equality

constraints by adding slack/surplus variables.

In a maximization program,
𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 ≤ 𝑏1

is replaced by
𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 + 𝑠1 = 𝑏1
 where 𝑠1 is the slack variable.
3. Bounding Face Solution: Degenerate problem
In a minimization program,
𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 ≥ 𝑏1 𝑀𝑖𝑛 𝐶 = 5𝑤 + 5𝑟

subject to
is replaced by
𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 − 𝑡1 = 𝑏1 𝑤 + 2𝑟 ≥ 1
where 𝑡1 is the surplus variable. 2𝑤 + 𝑟 ≥ 1
1.25𝑤 + 1.25𝑟 ≥ 1
𝑤, 𝑟 ≥ 0
Theorem (Dantzig). If the linear programming problem has an
optimal solution, then the optimal solution is an extreme point in a. 𝑤 + 2𝑟 = 1 → 𝑟 = 0.5 − 0.5𝑤
the feasible region. b. 2𝑤 + 𝑟 = 1 → 𝑟 = 1 − 2𝑤
c. 1.25𝑤 + 1.25𝑟 = 1 → 𝑟 = 0.8 − 𝑤
d. from objective function: 𝐶 = 5𝑤 + 5𝑟 → 𝑟 = 0.2𝐶 − 𝑤
Possible Outcomes

𝑟
1. No feasible solution

2𝑥1 + 𝑥2 ≤ 6
5𝑥1 + 4𝑥2 ≥ 40
𝑥2

Solution is the line segment (thick black line)

Notes
𝑥1  (c) and (d) have the same slop so they are parallel.

No intersection so no solution.  If C = 4, (c) and (d) will coincide, and the intersection of
the 2 lines is the solution.

2. If the feasible region is not bounded from above, LP

Linear Programming Example 3
problem has a solution if it involves minimization, but not
Consider the problem of James Bond, Inc., a small manufacturer of
if it involves maximization.
tennis bags. Each bag requires the following operations: cutting

and dyeing the material, sewing, finishing and inspection, and

2𝑥1 + 𝑥2 ≤ 6
5𝑥1 + 4𝑥2 ≥ 40 packaging.

𝑥2
James, the manager, determined that if the company produces a
low-priced standard model, each bag will require 7/10 hour in the

cutting and dyeing department, ½ hour in the sewing department,

1 hour for finishing, and 1/10 hour for inspection and packaging.

𝑥1
The more expensive deluxe model will require 1 hour for cutting
and dyeing, 5/6 hour for sewing, 2/3 hour for finishing, and ¼ hour
No solution if problem involves maximization because feasible for inspection and packaging.
region goes into infinity (unbounded).
James’ production is constrained by a limited number of hours (1) 𝑀𝑖𝑛 𝑐1 𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐𝑛 𝑥𝑛 subject to
available in each department. After studying the workload 𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 ≥ 𝑏1
𝑎21 𝑥1 + 𝑎22 𝑥2 + ⋯ + 𝑎2𝑛 𝑥𝑛 ≥ 𝑏2
projections in each department, James reckons that 630 hours for ⋮
cutting and dyeing, 600 hours for sewing, 708 hours for finishing 𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥2 + ⋯ + 𝑎𝑚𝑛 𝑥𝑛 ≥ 𝑏𝑚
𝑥1 , 𝑥2 , … , 𝑥𝑛 ≥ 0
and 135 hours for inspection and packaging will be available for the

production of tennis bags during the next 3 months.

(2) 𝑀𝑎𝑥 𝑏1 𝑦1 + 𝑏2 𝑦2 + ⋯ + 𝑏𝑚 𝑦𝑚 subject to
𝑎11 𝑦1 + 𝑎12 𝑦2 + ⋯ + 𝑎𝑚1 𝑦𝑚 ≥ 𝑐1
The accountant of the company calculates that the profit 𝑎12 𝑦1 + 𝑎22 𝑦2 + ⋯ + 𝑎𝑚2 𝑦𝑚 ≥ 𝑐2
⋮
contributions of each standard and deluxe bag are Php10 and
𝑎1𝑚 𝑦1 + 𝑎2𝑚 𝑦2 + ⋯ + 𝑎𝑛𝑚 𝑦𝑚 ≥ 𝑐𝑛
Php9, respectively. 𝑦, 𝑦, … , 𝑦𝑚 ≥ 0

𝑦1 = standard, 𝑦2 = deluxe
… where (1) is the primal problem and (2) is the dual problem,
𝑀𝑎𝑥 𝜋 = 10𝑦1 + 9𝑦2
 Coefficients of the objective function in the primal
problem are the constraint constants of the dual problem.
such that
 Coefficients of the objective function in the dual problem
are the constraint constants of the primal problem.
7
𝑦 + 𝑦2 ≤ 630
10 1
The original problem, called the primal problem, is transformed
1 5
𝑦1 + 𝑦2 ≤ 600 into a dual problem through the following procedures:
2 6
1. Change “maximize” to “minimize” (or vice versa)
2 2. Except for the non-negativity restrictions, the inequality
𝑦1 + 𝑦2 ≤ 708
3
signs in the primal constraints are reversed in the dual

1 1 constraints.*
𝑦 + 𝑦 ≤ 135
10 1 4 2
3. The coefficient matrix of the dual constraints is the
transpose of the coefficient matrix of the primal
𝑦1 , 𝑦2 ≥ 0
constraints.

Answers: 4. The row vector of coefficients in the primal objective

𝑦1 = 540, 𝑦2 = 252, 𝜋 = 7,668 function is the column vector of constants in the dual

constraints.
Notes
 When you plug the values you got into the constraint * Inequality signs must adhere to the general forms:
functions, you find that you don’t use up all your available Maximize  ≤
hours. You end up with unused hours of sewing and Minimize  ≥
inspection and packaging, i.e. slack hours.
 Even if you don’t use up all available hours, you are still
maximizing profits because you’ve used up all the time
you have for some parts of the process. Example 1
Primal Problem:
Duality in Linear Programming
𝑀𝑎𝑥 45𝑥1 + 55𝑥2

Given a pair of LPPs,

 subject to −2𝑦1 + 5𝑦2 ≤ 2
−𝑦1 + 4𝑦2 ≤ 10
𝑦1 , 𝑦2 ≥ 0
6𝑥1 + 4𝑥2 ≤ 120
3𝑥1 + 10𝑥2 ≤ 180
𝑥1 , 𝑥2 ≥ 0 Theorem. If x is primal feasible and y is dual feasible, then
𝑉𝑂𝐹(𝑥) ≥ 𝑉𝑂𝐹(𝑦), i.e., the minimand can never fall below the
6 4 maximand.
[ ]
3 10
 If the problem has a solution, then the solution to the

Dual Problem: objective function of the primal problem will always be

greater than the solution to the objective function of the
𝑀𝑖𝑛 120𝑦1 + 180𝑦2 dual problem.

subject to Theorem. If x* is primal feasible and y* is dual feasible, and

𝑉𝑂𝐹(𝑥 ∗ ) = 𝑉𝑂𝐹(𝑦 ∗ ), then x* and y* are optimal solutions.

6𝑦1 + 3𝑦2 ≥ 45
4𝑦1 + 10𝑦2 ≥ 55
𝑦1 , 𝑦2 ≥ 0 From Example 1
Primal Problem:
6 3
[ ] 𝑀𝑎𝑥 45𝑥1 + 55𝑥2
4 10

subject to

Example 2
6𝑥1 + 4𝑥2 ≤ 120
3𝑥1 + 10𝑥2 ≤ 180
Primal Problem:
𝑥1 , 𝑥2 ≥ 0
𝑀𝑖𝑛 2𝑥1 + 10𝑥2

Answer:
subject to
(10,15) where VOF = 1,275 (profit)

2𝑥1 + 𝑥2 ≤ 6
5𝑥1 + 4𝑥2 ≥ 20 Dual Problem:
𝑥1 , 𝑥2 ≥ 0

𝑀𝑖𝑛 120𝑦1 + 180𝑦2

Primal problem needs to be written in general form.

subject to
𝑀𝑖𝑛 2𝑥1 + 10𝑥2

6𝑦1 + 3𝑦2 ≥ 45
subject to 4𝑦1 + 10𝑦2 ≥ 55
𝑦1 , 𝑦2 ≥ 0

−2𝑥1 − 𝑥2 ≥ −6
5𝑥1 + 4𝑥2 ≥ 20 Answer:
𝑥1 , 𝑥2 ≥ 0
(95/16, 25/8) where VOF = 1,275 (cost)

Dual Problem:
Theorem. If the primal is unbounded (feasible region goes to
𝑀𝑎𝑥 − 6𝑦1 + 20𝑦2
infinity), then the dual is infeasible.

subject to
Theorem (Complementary Slackness). If x* and y* are primal
and dual optimal, respectively, then Min VOF(x) Max VOF(y)
Dual problem: Max Dual problem: Min
(i) if 𝑦𝑖∗ > 0, then 𝑡𝑖∗ = 0 and if 𝑥𝑗∗ > 0, then 𝑠𝑗∗ = 0
(ii) if 𝑡𝑖∗ > 0, then 𝑦𝑖∗ = 0 and if 𝑠𝑗∗ > 0, then 𝑥𝑗∗ = 0 Subtract a surplus (ti) in primal Add a slack (si) in primal

where t* and s* are vectors of surplus and slack variables, problem problem

respectively. If constraint in primal problem If there is a slack in the dual

has a surplus, then yi* = 0 in problem, then xi* = 0 in primal

𝑀𝑖𝑛 𝑐1 𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐𝑛 𝑥𝑛 dual problem. problem.

subject to If yi* > 0 in the dual problem, If xi* > 0 in the primal problem,
𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 ≥ 𝑏1
then there is no surplus in the then there is no slack in the
𝑎21 𝑥1 + 𝑎22 𝑥2 + ⋯ + 𝑎2𝑛 𝑥𝑛 ≥ 𝑏2
⋮ partner constraint in the primal partner constraint in the dual
𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥2 + ⋯ + 𝑎𝑚𝑛 𝑥𝑛 ≥ 𝑏𝑚
problem. problem.
𝑥1 , 𝑥2 , … , 𝑥𝑛 ≥ 0

𝑀𝑎𝑥 𝑏1 𝑦1 + 𝑏2 𝑦2 + ⋯ + 𝑏𝑚 𝑦𝑚 Example 3

subject to JRB manufactures tables (𝑥1 ), chairs (𝑥2 ), and benches (𝑥3 ) and

𝑎11 𝑦1 + 𝑎21 𝑦2 + ⋯ + 𝑎𝑛1 𝑦𝑚 ≤ 𝑐1 derives a per-unit profit of Php6, Php8 and Php7, respectively. Only
𝑎12 𝑦1 + 𝑎22 𝑦2 + ⋯ + 𝑎𝑛2 𝑦𝑚 ≤ 𝑐2 two resources are consumed in manufacturing: wood (300 board
⋮
𝑎1𝑚 𝑦1 + 𝑎2𝑚 𝑦2 + ⋯ + 𝑎𝑛𝑚 𝑦𝑚 ≤ 𝑐𝑛 feet in inventory) and labor (110 hours available). JRB uses 30 board
𝑦1 , 𝑦2 , … , 𝑦𝑚 ≥ 0 feet to produce a table, 20 board feet for a chair and 25 board feet
for a bench. He also uses 5 hours of labor to produce a table, 10
Determining the dual solution from the primal solutions:
hours for a chair, and 7 hours for a bench.

𝑀𝑎𝑥 45𝑥1 + 55𝑥2

Primal Problem:

subject to
𝑀𝑎𝑥 𝜋 = 6𝑥1 + 8𝑥2 + 7𝑥3
such that
6𝑥1 + 4𝑥2 ≤ 120
30𝑥1 + 20𝑥2 + 25𝑥3 ≤ 300
3𝑥1 + 10𝑥2 ≤ 180
5𝑥1 + 10𝑥2 + 7𝑥3 ≤ 110
𝑥1 , 𝑥2 ≥ 0
𝑥1 , 𝑥2 , 𝑥3 ≥ 0

Answer:
Note: Because you have 3 unknowns but only 2 constraints, try to
(10,15) where VOF = 1,275 (profit)
solve the problem by getting the dual problem.

vs.
Dual Problem:

𝑀𝑖𝑛 120𝑦1 + 180𝑦2

𝑀𝑖𝑛 𝐶 = 300𝑦1 + 110𝑦2
subject to
subject to 30𝑦1 + 5𝑦2 ≥ 6
20𝑦1 + 10𝑦2 ≥ 8
25𝑦1 + 7𝑦2 ≥ 7
6𝑦1 + 3𝑦2 ≥ 45
𝑦1 , 𝑦2 ≥ 0
4𝑦1 + 10𝑦2 ≥ 55
𝑦1 , 𝑦2 ≥ 0
𝑦1 = 7/55
𝑦2 = 6/11
Answer: 𝐶 = 98.18
(95/16, 25/8) where VOF = 1,275 (cost)
Application of Complementary Slackness: 30(0) + 20𝑥2 + 25𝑥3 ≤ 300
5(0) + 10𝑥2 + 7𝑥3 ≤ 110
 Plug in the values you got (from solving the dual
problem) into the constraints of the dual problem. 20𝑥2 + 25𝑥3 ≤ 300
 Compare the resulting value on left-hand side to the set 10𝑥2 + 7𝑥3 ≤ 110

value on the right-hand side.

4
20𝑥2 + 25𝑥3 = 300 → 𝑥3 = 12 − 5𝑥2
 If left-hand side is greater than right-hand side, this
4
10𝑥2 + 7 (12 − 5𝑥2 ) = 110
means that the slack/surplus variable is positive. This
65
means the corresponding variable in the primal problem 𝑥2 =
11
4 65 80
is equal to 0. 𝑥3 = 12 − 5 (11) =
11
 If left-hand side is equal to the right-hand side, this means
that the value of the slack/surplus variable is 0. This means 65 80
𝑥1 = 0, 𝑥2 = ,𝑥 =
11 3 11
the corresponding variable in the primal problem has a

positive value. 𝜋 = 6𝑥1 + 8𝑥2 + 7𝑥3

65 80
𝜋 = 6(0) + 8 ( ) + 7 ( )
11 11
Constraint 1 𝜋 = 98.18
30𝑦1 + 5𝑦2 ≥ 6
7 6
30 ( ) + 5 ( ) = 6.54 Interpretation of the Dual Variables
55 11
Because the LHS is strictly greater than the RHS (6.54 > 6), the The coefficients in the dual objective function are the shadow

surplus variable is positive, which allows you to assume that 𝑥1 = 0. prices / opportunity costs / accounting or imputed prices of the

constraints in the primal problem.

Constraint 2
20𝑦1 + 10𝑦2 ≥ 8
𝑀𝑎𝑥 𝜋 = 45𝑦1 + 55𝑦2
7 6
20 ( ) + 10 ( ) = 8 subject to
55 11
Because the LHS is strictly equal to the RHS (8 = 8), the surplus 6𝑦1 + 4𝑦2 ≤ 120
3𝑦1 + 10𝑦2 ≤ 180
variable is 0, which allows you to assume that 𝑥2 > 0.
𝑦1 , 𝑦2 ≥ 0

Constraint 3 𝑀𝑖𝑛 𝐶 = 120𝑥1 + 180𝑥2

25𝑦1 + 7𝑦2 ≥ 7
subject to
7 6
25 ( ) + 7 ( ) = 7 6𝑥1 + 3𝑥2 ≤ 45
55 11
4𝑥1 + 10𝑥2 ≤ 55
Because the LHS is strictly equal to the RHS (7 = 7), the surplus
𝑥1 , 𝑥2 ≥ 0
variable is 0, which allows you to assume that 𝑥3 > 0.

Notes:
Solving for 𝑥1 , 𝑥2 , 𝑥3 :  6 and 3 are resource requirements of 𝑦1 .
 Because you assume that 𝑥1 = 0, you can now solve for 𝑥2  𝑥1 and 𝑥2 are valuation of resources (i.e., opportunity cost
and 𝑥3 . of using machine 1 and machine 2, respectively)
 Use the 2 constraint equations in the primal problem to  Total opportunity cost of producing 𝑦1 should at least be
solve for the values of 𝑥2 and 𝑥3 . as large as the gross profit of the product.
 Plug in values of 𝑥1 , 𝑥2 , 𝑥3 in objective function of primal  𝑦𝑖 > 0 implies 𝑡𝑖 = 0 ; 𝑡𝑖 > 0 implies 𝑦𝑖 = 0
problem (profit) and make sure it equates to the value of  If 6𝑥1 + 3𝑥2 were greater than 45, 𝑦1 would be greater
the objective function of the dual problem (cost), 98.18. than 0, and opportunity cost would be greater than profit.
Therefore, you wouldn’t produce at that value of 𝑦1 .
30𝑥1 + 20𝑥2 + 25𝑥3 ≤ 300
5𝑥1 + 10𝑥2 + 7𝑥3 ≤ 110
𝑡𝑜𝑡𝑎𝑙 𝑔𝑟𝑜𝑠𝑠 𝑝𝑟𝑜𝑓𝑖𝑡 = 𝑡𝑜𝑡𝑎𝑙 𝑜𝑝𝑝𝑜𝑟𝑡𝑢𝑛𝑖𝑡𝑦 𝑐𝑜𝑠𝑡 𝑜𝑓 𝑟𝑒𝑠𝑜𝑢𝑟𝑐𝑒𝑠
 Optimal solution becomes:
If an addition unit of resource 1 is made available, the optimal
solution becomes: 𝑥1∗∗∗ = 5.73
𝑥2∗∗∗ = 3.21
𝑉𝑂𝐹(𝑥 ∗ ) = 1,265
𝑦1∗∗ = 10.21
𝑦2∗∗ = 14.94
𝑉𝑂𝐹(𝑥 ∗∗∗ ) − 𝑉𝑂𝐹(𝑥 ∗ ) = −10 = −𝑦1∗
𝑉𝑂𝐹(𝑦 ∗∗ ) = 1,280.94
95
𝑉𝑂𝐹(𝑦 ∗∗ ) − 𝑉𝑂𝐹(𝑦 ∗ ) = 1,280.94 − 1,275 = 5.94 = = 𝑥1
16

Example 1
Similarly, if 1 unit of resource 1 is lost, the optimal solution Solve the following linear programming problem by solving the
becomes: dual problem:

𝑦1∗∗∗ = 9.79 𝑀𝑖𝑛 𝐺 = 6𝑦1 + 20𝑦2 + 3𝑦3 + 20𝑦4

𝑦2∗∗∗ = 15.06
subject to
𝑉𝑂𝐹(𝑦 ∗∗∗ ) = 1,269.06
95 3𝑦1 + 6𝑦2 − 𝑦3 + 2𝑦4 ≥ 4
𝑉𝑂𝐹(𝑦 ∗∗∗ ) − 𝑉𝑂𝐹(𝑦 ∗ ) = 1,269.06 − 1,275 = −5.94 = − = −𝑥1 −4𝑦1 + 2𝑦2 + 𝑦3 + 5𝑦4 ≥ 2
16
𝑦𝑖 ≥ 0, 𝑖 = 1, 2, … , 4

𝑥1 is the effect of an addition or reduction of 1 unit of resource 1 on

Dual Problem:
gross profit.

𝑀𝑎𝑥 𝐹 = 4𝑥1 + 2𝑥2

Dual Problem
subject to
Consider the dual problem:
3𝑥1 − 4𝑥2 ≤ 6
6𝑥1 + 2𝑥2 ≤ 20
𝑀𝑖𝑛 𝐶 = 120𝑥1 + 180𝑥2 −𝑥1 + 𝑥2 ≤ 3
subject to 2𝑥1 + 5𝑥2 ≤ 20
𝑥1 , 𝑥2 ≥ 0
6𝑥1 + 3𝑥2 ≤ 45
4𝑥1 + 10𝑥2 ≤ 55
𝑥1 , 𝑥2 ≥ 0 Example 2
Given the problem:

Optimal Solutions:
95 𝑀𝑎𝑥 𝑐0 = 𝑥1 + 2𝑥2
𝑥1∗ =
16 subject to
25
𝑥2∗ = 𝑥1 + 𝑥2 ≤ 10
8
𝑉𝑂𝐹(𝑥 ∗ ) = 1,275 −2𝑥1 + 2𝑥2 ≤ 4
𝑥1 , 𝑥2 ≥ 0

𝑦1∗ = 10
𝑦2∗ = 15 a.) Solve the problem and its dual.
b.) How will the value of the objective function in the primal
Consider a 1 peso increase in the price of 𝑦1∗ . change when the first constraint is changed to 𝑥1 + 𝑥2 ≤
Optimal solution becomes: 11?

𝑥1∗∗ = 6.15 Simplex Algorithm

𝑥2∗∗ = 3.04
𝑉𝑂𝐹(𝑥 ∗ ) = 1,285
Definition. Given 𝐴𝑥 = 𝑏, where A is an 𝑚 𝑥 𝑛 matrix and B is an
𝑉𝑂𝐹(𝑥 ∗∗ ) − 𝑉𝑂𝐹(𝑥 ∗ ) = 10 = 𝑦1∗ 𝑚 𝑥 𝑚 non-singular submatrix of A, B is called a basis of A. The rest
of the matrix A is submatrix N, and 𝐴 = [𝐵|𝑁]. Variables associated
Consider a 1 peso decrease in the price of 𝑦1∗ . with columns of B are called basic, and others, non-basic.
Definition. Let B be a basis for A. Set 𝑥𝑗 = 0 if 𝑗 ∈ 𝑁. For 𝑥𝑗 ∈ 𝐵, Lemma 1. If the set {𝑥 | 𝐴𝑥 = 𝑏, 𝑥 ≥ 0} is feasible, then it has a
choose them so as to solve 𝐵𝑥 𝐵 = 𝑏. The resulting solution is a basic feasible solution.
basic solution.
Lemma 2. If 𝑥 ∗ is a basic feasible solution of the set {𝑥 | 𝐴𝑥 =
Definition. If a basic solution associated with the basis B, 𝑥 = 𝑏, 𝑥 ≥ 0}, then 𝑥 ∗ is an extreme point of the set.
[𝑥 𝐵 |0] is nonnegative, then x is a basic feasible solution to the

linear programming problem. Lemma 3. Every extreme point of the set {𝑥 | 𝐴𝑥 = 𝑏, 𝑥 ≥ 0} is a

basic feasible solution.
Example 1
Computation Form of LPP
𝑥1 + 𝑥2 + 𝑥3 = 1
2𝑥1 + 3𝑥2 = 1 𝑀𝑖𝑛 − 𝑐′𝑥
𝑥1 , 𝑥2 , 𝑥3 ≥ 0 subject to
𝐴𝑥 = 𝑏
1 1 1 𝑥≥0
𝐴=[ ]
2 3 0

Example
One basis of A is: General Form:
𝑀𝑎𝑥 45𝑥1 + 55𝑥2
1 1 subject to
𝐵=[ ]
2 0
6𝑥1 + 4𝑥2 ≤ 120
3𝑥1 + 10𝑥2 ≤ 180
The basic solution associated with this basis is: 𝑥1 , 𝑥2 ≥ 0
𝑥1 + 𝑥3 = 1
2𝑥1 = 1
Standard Form:
𝑀𝑎𝑥 45𝑥1 + 55𝑥2
1
𝑥1 = subject to
2
𝑥2 = 0 6𝑥1 + 4𝑥2 + 𝑥3 + 0𝑥4 = 120
1 3𝑥1 + 10𝑥2 + 0𝑥3 + 𝑥4 = 180
𝑥3 =
2 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ≥ 0

1 1
where ( , 0, ) is a basic feasible solution. Computational Form:
2 2
𝑀𝑖𝑛 − 45𝑥1 − 55𝑥2
subject to
Another basis associated with A:
6𝑥1 + 4𝑥2 + 𝑥3 + 0𝑥4 = 120
3𝑥1 + 10𝑥2 + 0𝑥3 + 𝑥4 = 180
1 1 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ≥ 0
𝐵=[ ]
2 3

Notes:
The basic solution associated with this basis is:
𝑥1 + 𝑥2 = 1  Standard Form is always Max
2𝑥1 + 3𝑥2 = 1  Computational Form is always Min
 If General Form is Max
𝑥1 = 2
𝑥2 = −1 a.) Retain objective function for Standard Form
𝑥3 = 0 b.) Negate equation for Computational Form to
make it Min –(OF)
where (2, −1, 0) is NOT a basic feasible solution because the value
 If General Form is Min
of 𝑥2 is negative.
 a.) Negate equation for Standard Form to make it (ii) Choose the pivot row r such that 𝑏𝑟 ÷ 𝐴𝑟𝑘 =
Max –(OF) 𝑚𝑖𝑛{𝑏𝑖 /𝐴𝑖 } > 0 . If there is no such r, stop. The linear
b.) Retain objective function for Computational problem is unbounded. Otherwise, continue.
Form (iii) Pivot on 𝐴𝑟𝑘 . Go to step (i).

Definition. If the linear programming problem is in computational Example 1

form, there exists a basis B such that 𝐵 = 𝐼, 𝑐 𝐵 = 0, and the linear

𝑀𝑎𝑥 45𝑥1 + 55𝑥2
programming problem is said to be in canonical form with respect
subject to
to the basis of A. 6𝑥1 + 4𝑥2 ≤ 120
3𝑥1 + 10𝑥2 ≤ 180
𝑥1 , 𝑥2 ≥ 0
𝑀𝑖𝑛 − 𝑐 ′ 𝑥 = −𝑐0
subject to
𝐴𝑥 = 𝑏 Standard Form:
𝑥≥0 𝑀𝑎𝑥 45𝑥1 + 55𝑥2
subject to
Example 6𝑥1 + 4𝑥2 + 𝑥3 = 120
3𝑥1 + 10𝑥2 + 𝑥4 = 180
𝑐 = [−45 −55 0 0] 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ≥ 0

6 4 1 0
𝐴=[ ] Computational Form:
3 10 0 1
𝑀𝑖𝑛 − 45𝑥1 − 55𝑥2

𝑥 𝐵 = [𝑥3 𝑥4 ] subject to
6𝑥1 + 4𝑥2 + 𝑥3 = 120
3𝑥1 + 10𝑥2 + 𝑥4 = 180
𝑥 𝑁 = [𝑥1 𝑥2 ]
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ≥ 0

[−𝑐 𝐵 𝑥 𝐵 ] = −𝑐
−𝑐 𝑁 ] [ 0 Tableau 1:
𝑥𝑁
𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 RHS
𝑥𝐵 𝑏
[𝐵 𝑁] [ 𝑁 ] = [ ]
0 Ax-c’x -45 -55 0 0 0 c0
𝑥
6 4 1 0 120
𝐵𝑥 𝐵 = 𝑏 b
3 10 0 1 180
𝐼𝑥 𝐵 = 𝑏
𝑥𝐵 = 𝑏
 Tableau 1 is canonical with respect to 𝑥 𝐵 = (𝑥3 , 𝑥4 )
𝑥1 = 0, 𝑥2 = 0, 𝑥3 = 120, 𝑥4 = 180  Pivot on a22 = 10
basic solution

Goal:
Steps in Simplex Algorithm
1. All values in the first row are positive.
The linear programming problem is canonical with respect to some
2. Intersection of pivot row and pivot column is equal to 1,
basis and the basic solution associated with this basis is feasible
while all other values in that column are 0.
(𝑏 ≥ 0).
(i) Choose the pivot column k such that 𝑐𝑘 < 0 and
Tableau 2:
|𝑐𝑘 | > |𝑐𝑗 | ∀ 𝑗 ≠ 𝑘. If there is no 𝑐𝑘 < 0 and 𝑏 ≥ 0,
𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 RHS
𝑐𝑘 ≥ 0, the basic solution associated with the basis, is
-57/2 0 0 11/2 990
optimal. Otherwise, continue to the next step.
24/5 0 1 -2/5 48

3/10 1 0 1/10 18
 1/2 1 7/10 0 1/10 11
 Tableau 2 is canonical with respect to 𝑥 = (𝑥2 , 𝑥3 )
𝐵

 Pivot on a11 = 24/5 Tableau 3

𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓 RHS
Tableau 3 0 0 -3/10 1/10 3/5 96
𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 RHS 1 0 11/20 1/20 -1/10 4
0 0 95/16 25/8 1275 0 1 17/40 -1/40 3/20 9
1 0 5/24 -1/12 10

0 1 -1/16 11/10 15 Tableau 4

𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓 RHS
 Tableau 3 is canonical with respect to 𝑥𝐵 = (𝑥1 , 𝑥2 ) 6/11 0 0 7/55 6/11 1080/11
 𝑥1 = 10; 𝑥2 = 15; 𝑥𝑥 = 0; 𝑥4 = 0
20/11 0 1 1/11 -2/11 80/11

-17/22 1 0 7/110 5/22 65/11

Example 2

General Form: Interpretation:

𝑀𝑎𝑥 𝜋 = 6𝑥1 + 8𝑥2 + 7𝑥3 * x3* = 80/11

subject to * x2* = 65/11
30𝑥1 + 20𝑥2 + 25𝑥3 ≤ 300
* 7/5 and 6/11 are y1* and y2*, respectively
5𝑥1 + 10𝑥2 + 7𝑥3 ≤ 110
𝑥1 , 𝑥2 , 𝑥3 ≥ 0
Use of Artificial Variables

Standard Form:
𝑀𝑎𝑥 𝜋 = 6𝑥1 + 8𝑥2 + 7𝑥3  When the computational form of the LPP is not canonical
subject to with respect to some basic sequence, artificial variables
30𝑥1 + 20𝑥2 + 25𝑥3 + 𝑥4 = 300 are used. This happens in 2 cases:
5𝑥1 + 10𝑥2 + 7𝑥3 + 𝑥5 = 110 a.) The original problem is a minimization problem;
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 ≥ 0
and
b.) One of the constraints in the original
Computational Form: maximization problem is a strict equality.
𝑀𝑖𝑛 𝐶 = −6𝑥1 − 8𝑥2 − 7𝑥3
 The artificial variables are assigned large coefficients
subject to
relative to the coefficients in the objective function.
30𝑥1 + 20𝑥2 + 25𝑥3 + 𝑥4 = 300
 For (a), choose a large positive number. For (b), choose a
5𝑥1 + 10𝑥2 + 7𝑥3 + 𝑥5 = 110
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 ≥ 0 large negative number. This ensures that the optimal
solution doesn’t include any artificial variable.

Tableau 1

𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓 RHS Example

-6 -8 -7 0 0 0 𝑀𝑖𝑛 𝑐0 = 2𝑥1 + 10𝑥2

30 20 25 1 0 300 subject to
2𝑥1 + 𝑥2 ≤ 6
5 10 7 0 1 110
5𝑥1 + 4𝑥2 ≥ 20
𝑥1 , 𝑥2 ≥ 0
Tableau 2
Standard Form:
𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓 RHS
𝑀𝑎𝑥 − 2𝑥1 − 10𝑥2
-2 0 -7/5 0 4/5 88
subject to
20 0 11 1 -2 80 2𝑥1 + 𝑥2 + 𝑥3 = 6
 5𝑥1 + 4𝑥2 − 𝑥4 = 20 0 0 14 6 94 -36
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ≥ 0
1 0 4/3 1/3 1/3 4/3

Computational Form: 0 1 -5/3 2/3 2/3 10/3

𝑀𝑖𝑛 2𝑥1 + 10𝑥2 + 𝛼𝑦1
subject to  Tableau 3 is canonical with respect to to 𝑥 𝐵 = (𝑥1 , 𝑥2 )
2𝑥1 + 𝑥2 + 𝑥3 = 6  Optimal solution:
5𝑥1 + 4𝑥2 − 𝑥4 + 𝑦1 = 20
a.) 𝑥1 = 4/3
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ≥ 0
b.) 𝑥2 = 10/3
c.) 𝑥3 = 𝑥4 = 𝑦1 = 0
Let 𝛼 = 100.
Degenerate Problem Example (Bounding Face Solution)
Tableau 1
𝑀𝑖𝑛 𝐶 = 𝑤𝐿 + 𝑟𝐾
𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒚𝟏 RHS
subject to
2 10 0 0 100 0
𝑤 + 2𝑟 ≥ 1
2 1 1 0 0 6 2𝑤 + 𝑟 ≥ 1
1.25𝑤 + 1.25𝑟 ≥ 1
5 4 0 -1 1 20
𝑤, 𝑟 ≥ 0

 Tableau 1 is not canonical in form with respect to any

variable because no identity matrix can be found 𝑟
 Tableau 1 can be made can be made canonical by
multiplying the 2nd row by -100 and adding it to the 0th
row.

Tableau 2
𝑤
𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒚𝟏 RHS

-498 -390 0 100 0 -2000

Difficulties encountered in employing the simplex method when
2 1 1 0 0 6
the problem is degenerate:
5 4 0 -1 1 20
a.) Two or more quotients share the distinction of being the
smallest, so you end up having two or more rows eligible
 Tableau 2 is canonical with respect to 𝑥 𝐵 = (𝑥3 , 𝑦1 ) to be pivot rows.
 Pivot on a11 = 2 b.) Each pivot step fails to improve the value of the objective
function. (E.g. If you’re given a maximization problem and
the VOF goes down as you move from tableau 1 to
tableau 2)
Tableau 3

𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒚𝟏 RHS Example

0 -141 249 100 0 -506

𝑀𝑎𝑥 3𝑥1 + 2𝑥2
1 1/2 1/2 0 0 3 subject to
𝑥1 ≤ 4
0 3/2 -5/2 -1 1 5
𝑥2 ≤ 6
3𝑥1 + 2𝑥2 ≤ 18
𝑥1 , 𝑥2 ≥ 0
 Tableau 3 is canonical with respect to to 𝑥 𝐵 = (𝑥1 , 𝑦1 )
 Pivot on a22 = 3/2

𝑀𝑖𝑛 − 3𝑥1 − 2𝑥2

Tableau 4 subject to
𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒚𝟏 RHS 𝑥1 + 𝑥3 = 4
𝑥2 + 𝑥4 = 6
 3𝑥1 + 2𝑥2 + 𝑥5 = 18  Changes in the constraint constant
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 ≥ 0
a.) Shadow price
x2 b.) Reduced cost
 Changes in the objective function coefficients
(2,6) a.) Single decision variable
(4,3) b.) Simultaneous changes
 Changes in the constraint coefficient

x1
JRB manufactures tables (𝑥1 ) and chairs (𝑥2 ) and derives a per unit
Tableau 1 profit of Php6 and Php8, respectively. Only 2 resources are
𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓 RHS consumed in manufacturing: wood (300 board feet in inventory)
and labor (110 hours available). JRB uses 30 board feet to produce a
-3 -2 0 0 0 0
table and 20 board feet to produce a chair. He also uses 5 hours of
1 0 1 0 0 4
labor to produce a table and 10 hours to produce a chair.
0 1 0 1 0 6

3 2 0 0 1 18 𝑀𝑎𝑥 𝜋 = 6𝑥1 + 8𝑥2

Subject to
30𝑥1 + 20𝑥2 ≤ 300 (wood)
Tableau 2
5𝑥1 + 10𝑥2 ≤ 110 (labor)
𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓 RHS 𝑥1 , 𝑥2 ≥ 0
0 -2 3 0 0 12

1 0 1 0 0 4 𝑥2
0 1 0 1 0 6 15

0 2 -3 0 1 6
11
(4,9)
Tableau 3

𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓 RHS 𝑥1
0 0 0 0 0 18 10 22

1 0 1 0 0 4
Notes:
0 0 3/2 1 -1/2 3
 Instruments: x1 and x2
0 1 -3/2 0 1/2 3  Constraint Constants: 300 and 100
 Coefficients of Objective Function: 6 and 8
 Coefficients of Constraints: 30, 20, 5 and 10

Tableau 1

𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 RHS
Tableau 4
-6 -8 0 0 0
𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓 RHS
30 20 1 0 300
0 0 0 0 1 18
5 10 0 1 110
1 0 0 -2/3 1/3 2

0 0 1 2/3 -1/3 2 Tableau 2

0 1 0 1 0 6 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 RHS

-2 0 0 4/5 88

20 0 1 -2 80
Sensitivity Analysis
1/2 1 0 1/10 11
 Change in Constraint Constant: Labor
𝑥2

Tableau 3

𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 RHS

0 0 1/10 3/5 96 𝑒

1 0 1/20 -1/10 4
𝑑

0 1 -1/40 3/20 9 𝑥1

 Point D: Same as point A. Wood and labor are fully

 1/10 and 3/5 are the shadow prices of wood and labor, utilized.
respectively.  Point E: Labor constraint is increased to 130. More chairs
 1/10 and 3/5 are the solutions of the dual problem (y1 = and less tables are produced.
1/10, y2 = 3/5)  Point F: Labor constraint is decreased to 80. More tables
 1/20, -1/10, -1/40, 3/20 are the exchange coefficients and less chairs are produced.
 96 is the VOF of the dual problem (minimum)
Exchange Coefficient
Change in Constraint Constant: Wood Units of one variable that must be given up to accommodate an
𝑥2 increase in another

30𝑥1 + 20𝑥2 ≤ 300 (wood)

5𝑥1 + 10𝑥2 ≤ 110 (labor)

𝑐
𝑎
𝑏
Example
Finding the Wood Exchange Coefficient using Matrices
𝑥1

𝐴𝑥 = 𝑏
𝐴−1 𝐴𝑥 = 𝐴−1 𝑏
 Point A: No slack. Wood and labor are fully utilized. 𝑥 = 𝐴−1 𝑏
 Point B: Wood constraint increased to 500. More tables
(x1) and less chairs (x2) are produced. 30 20 𝑥1 1
[ ][ ] = [ ]
5 10 𝑥2 0
 Point C: Wood constraint decreased to 240. More chairs
and less tables are produced. det(𝐴) = (30)(10) − (20)(5) = 200

1 10 −5
𝐴−1 = [ ]
200 −20 30

10⁄
𝐴−1 𝑏 = [ 200 −20/200] [1]
−5/200 30/200 0

1/20 −1/10
[ ] and [ ]
−1/40 3/20
are the shadow prices of wood and labor, respectively.

You can also find the exchange coefficients from your final tableau:
Slack Slack
(wood) (labor)
𝑥1 (tables) 1/20 -1/10
𝑥2 (chairs) -1/40 3/20

𝑅𝑒𝑣𝑖𝑠𝑒𝑑 𝑣𝑎𝑙𝑢𝑒 = 𝑂𝑟𝑖𝑔𝑖𝑛𝑎𝑙 𝑣𝑎𝑙𝑢𝑒 + (𝑒𝑥𝑐ℎ𝑎𝑛𝑔𝑒 𝑐𝑜𝑒𝑓𝑓𝑖𝑐𝑖𝑒𝑛𝑡

× 𝑐ℎ𝑎𝑛𝑔𝑒 𝑖𝑛 𝑐𝑜𝑛𝑠𝑡𝑟𝑎𝑖𝑛𝑡 𝑐𝑜𝑛𝑠𝑡𝑎𝑛𝑡)

Increase in wood constraint from 300 to 310:

 1 𝐿𝐶𝐶𝑆𝐿 = 110 − 60 = 50
 New 𝑥1 = 4 + [( ) (310 − 300)] = 4.5 tables
20 𝑈𝐶𝐶𝑆𝐿 = 110 + 40 = 150
1
 New 𝑥2 = 9 + [(− ) (310 − 300)] = 8.75 chairs
40
 𝑉𝑂𝐹(𝑥 ∗ ) = 97 Sensitivity Limits: Exchange Ratio (Surplus)

Reduction in labor constraint from 110 to 80: 𝑠𝑜𝑙𝑢𝑡𝑖𝑜𝑛 𝑣𝑎𝑙𝑢𝑒

𝐸𝑅 =
1 𝑒𝑥𝑐ℎ𝑎𝑛𝑔𝑒 𝑐𝑜𝑒𝑓𝑓𝑖𝑐𝑖𝑒𝑛𝑡 𝑖𝑛 𝑠𝑢𝑟𝑝𝑙𝑢𝑠 𝑐𝑜𝑙𝑢𝑚𝑛
 New 𝑥1 = 4 + [(− ) (80 − 110)] = 7 tables
10
3
 New 𝑥2 = 9 + [( ) (80 − 110)] = 4.5 chairs No Surplus in the Original Solution
20
 𝑉𝑂𝐹(𝑥 ∗∗ ) = 78  Lower constraint constant sensitivity limit (LCCSL)
 Upper constraint constant sensitivity limit (UCCSL)
Comparing VOFs:
 𝑉𝑂𝐹(𝑥 ∗ ) − 𝑉𝑂𝐹(𝑥) = 97 − 96 = 1 = 10(𝑦1 ) 𝐿𝐶𝐶𝑆𝐿 = 𝑜𝑟𝑖𝑔𝑖𝑛𝑎𝑙 𝑙𝑒𝑣𝑒𝑙
 𝑉𝑂𝐹(𝑥 ∗∗ ) − 𝑉𝑂𝐹(𝑥) = 78 − 96 = −18 = −30(𝑦2 )
− 𝑠𝑚𝑎𝑙𝑙𝑒𝑠𝑡 𝑎𝑏𝑠𝑜𝑙𝑢𝑡𝑒 𝑣𝑎𝑙𝑢𝑒 𝑜𝑓 𝑛𝑒𝑔𝑎𝑡𝑖𝑣𝑒 𝑟𝑎𝑡𝑖𝑜 (𝑜𝑟
− ∞ 𝑖𝑓 𝑛𝑜 𝑟𝑎𝑡𝑖𝑜 𝑖𝑠 𝑛𝑒𝑔𝑎𝑡𝑖𝑣𝑒)
Sensitivity Limits: Exchange Ratio (Slack)
 Exchange ratio helps you determine allowable increase 𝑈𝐶𝐶𝑆𝐿
and allowable decrease = 𝑜𝑟𝑖𝑔𝑖𝑛𝑎𝑙 𝑙𝑒𝑣𝑒𝑙
+ 𝑠𝑚𝑎𝑙𝑙𝑒𝑠𝑡 𝑝𝑜𝑠𝑖𝑡𝑖𝑣𝑒 𝑟𝑎𝑡𝑖𝑜 (𝑜𝑟 ∞ 𝑖𝑓 𝑛𝑜 𝑟𝑎𝑡𝑖𝑜 𝑖𝑠 𝑝𝑜𝑠𝑖𝑡𝑖𝑣𝑒)
𝑠𝑜𝑙𝑢𝑡𝑖𝑜𝑛 𝑣𝑎𝑙𝑢𝑒
𝐸𝑅 = Surplus in the Original Solution
𝑒𝑥𝑐ℎ𝑎𝑛𝑔𝑒 𝑐𝑜𝑒𝑓𝑓𝑖𝑐𝑖𝑒𝑛𝑡 𝑖𝑛 𝑠𝑙𝑎𝑐𝑘 𝑐𝑜𝑙𝑢𝑚𝑛
𝐿𝐶𝐶𝑆𝐿 = −∞
No Slack in the Original Solution
 Lower constraint constant sensitivity limit (LCCSL) 𝑈𝐶𝐶𝑆𝐿 = 𝑜𝑟𝑖𝑔𝑖𝑛𝑎𝑙 𝑙𝑒𝑣𝑒𝑙 + 𝑠𝑜𝑙𝑢𝑡𝑖𝑜𝑛 𝑣𝑎𝑙𝑢𝑒 𝑜𝑓 𝑠𝑢𝑟𝑝𝑙𝑢𝑠
 Upper constraint constant sensitivity limit (UCCSL)
Change in Coefficient of Objective Variable (or Constraints
of Dual Problem)
𝐿𝐶𝐶𝑆𝐿 = 𝑜𝑟𝑖𝑔𝑖𝑛𝑎𝑙 𝑙𝑒𝑣𝑒𝑙 − 𝑠𝑚𝑎𝑙𝑙𝑒𝑠𝑡 𝑝𝑜𝑠𝑖𝑡𝑖𝑣𝑒 𝑟𝑎𝑡𝑖𝑜 (𝑜𝑟
− ∞ 𝑖𝑓 𝑛𝑜 𝑟𝑎𝑡𝑖𝑜 𝑖𝑠 𝑝𝑜𝑠𝑖𝑡𝑖𝑣𝑒) Improvement Ratio

𝑈𝐶𝐶𝑆𝐿 = 𝑜𝑟𝑖𝑔𝑖𝑛𝑎𝑙 𝑙𝑒𝑣𝑒𝑙 𝑠ℎ𝑎𝑑𝑜𝑤 𝑝𝑟𝑖𝑐𝑒 𝑜𝑓 𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒

𝐼𝑅 =
+ 𝑠𝑚𝑎𝑙𝑙𝑒𝑠𝑡 𝑎𝑏𝑠𝑜𝑙𝑢𝑡𝑒 𝑣𝑎𝑙𝑢𝑒 𝑜𝑓 𝑛𝑒𝑔𝑎𝑡𝑖𝑣𝑒 𝑟𝑎𝑡𝑖𝑜 𝑒𝑥𝑐ℎ𝑎𝑛𝑔𝑒 𝑐𝑜𝑒𝑓𝑓𝑖𝑐𝑖𝑒𝑛𝑡 𝑖𝑛 𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒 𝑟𝑜𝑤
(𝑜𝑟 ∞ 𝑖𝑓 𝑛𝑜 𝑟𝑎𝑡𝑖𝑜 𝑖𝑠 𝑛𝑒𝑔𝑎𝑡𝑖𝑣𝑒)
Variable in the Original Solution
Slack in the Original Solution
 Lower objective coefficient sensitivity limit (LOCSL)
𝐿𝐶𝐶𝑆𝐿 = 𝑜𝑟𝑖𝑔𝑖𝑛𝑎𝑙 𝑙𝑒𝑣𝑒𝑙 − 𝑠𝑜𝑙𝑢𝑡𝑖𝑜𝑛 𝑣𝑎𝑙𝑢𝑒 𝑜𝑓 𝑠𝑙𝑎𝑐𝑘
 Upper objective coefficient sensitivity limit (UOCSL)

𝑈𝐶𝐶𝑆𝐿 = ∞
𝐿𝑂𝐶𝑆𝐿 = 𝑜𝑟𝑖𝑔𝑖𝑛𝑎𝑙 𝑙𝑒𝑣𝑒𝑙 − 𝑠𝑚𝑎𝑙𝑙𝑒𝑠𝑡 𝑝𝑜𝑠𝑖𝑡𝑖𝑣𝑒 𝑟𝑎𝑡𝑖𝑜 (𝑜𝑟
− ∞ 𝑖𝑓 𝑛𝑜 𝑟𝑎𝑡𝑖𝑜 𝑖𝑠 𝑝𝑜𝑠𝑖𝑡𝑖𝑣𝑒)
Slack Slack
(wood) (labor)
𝑥1 (tables) 1/20 -1/10 𝑈𝑂𝐶𝑆𝐿 = 𝑜𝑟𝑖𝑔𝑖𝑛𝑎𝑙 𝑙𝑒𝑣𝑒𝑙
𝑥2 (chairs) + 𝑠𝑚𝑎𝑙𝑙𝑒𝑠𝑡 𝑎𝑏𝑠𝑜𝑙𝑢𝑡𝑒 𝑣𝑎𝑙𝑢𝑒 𝑜𝑓 𝑛𝑒𝑔𝑎𝑡𝑖𝑣𝑒 𝑟𝑎𝑡𝑖𝑜
-1/40 3/20 (𝑜𝑟 ∞ 𝑖𝑓 𝑛𝑜 𝑟𝑎𝑡𝑖𝑜 𝑖𝑠 𝑛𝑒𝑔𝑎𝑡𝑖𝑣𝑒)

Sensitivity Limits for Wood Constraint

Exchange Solution Exchange Variable Not in the Original Solution
Coefficient Value Ratio  Lower objective coefficient (max) sensitivity limit
𝑥1 (tables) 1/20 4 80 (LOCMSL)
𝑥2 (chairs) -1/40 9 -360  Upper objective coefficient (max) sensitivity limit
(UOCMSL)
𝐿𝐶𝐶𝑆𝐿 = 300 − 80 = 220
𝑈𝐶𝐶𝑆𝐿 = 300 + 360 = 660
𝐿𝑂𝐶𝑀𝑆𝐿 = −∞

Sensitivity Limits for Labor Constraint 𝑈𝑂𝐶𝑀𝑆𝐿

Exchange Solution Exchange = 𝑜𝑟𝑖𝑔𝑖𝑛𝑎𝑙 𝑙𝑒𝑣𝑒𝑙
coefficient value ratio + 𝑎𝑏𝑠𝑜𝑙𝑢𝑡𝑒 𝑠𝑖𝑧𝑒 𝑜𝑓 𝑡ℎ𝑒 𝑠ℎ𝑎𝑑𝑜𝑤 𝑝𝑟𝑖𝑐𝑒 𝑜𝑓 𝑡ℎ𝑒 𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒
𝑥1 (tables) -1/10 4 -40
𝑥2 (chairs) 3/20 9 60 Example 1
 Slack Slack a.) What is the maximum premium that Andre would pay for
(wood) (labor)
𝑥1 (tables) one additional silicon sheet? For one additional minute of
1/20 -1/10
𝑥2 (chairs) labor?
-1/40 3/20

Willing to pay a maximum of 3.33 for an additional silicon

Sensitivity limits for objective function of 𝑥1 :
sheet and a maximum of 1.17 for an additional minute of
 Improvement ratios for 𝑥1
labor.
1⁄
10 = 2
1⁄ Notes:
20
 Check shadow price of each input.
6⁄  Shadow price of A = Additional profit if you introduce an
10 = −6
−1⁄ additional 1 unit of A
10
 Shadow price of A = The maximum price you would be
willing to pay for an additional unit of A
 Lower objective variable (max) sensitivity limit

6−2 = 4 b.) Determine the optimal solution to the primal problem.

 Upper objective variable (max) sensitivity limit C = 666,666.67

I=0
6 + 6 = 12 M = 666,666.67

Sensitivity limits for objective function of 𝑥2 :

c.) Suppose that Andre can manufacture an all-purpose
 Improvement ratios for 𝑥2
game chip at a profit of 1 per chip. If each game chip
requires 0.01 silicon sheet and 0.4 minute of labor, should
1⁄
10 = −4 any game chips be made?
−1⁄
40

6⁄
Yes, because total cost is less than the profit you make.
10 = 4
3⁄
20 Notes:
 Check shadow prices of each input. Determine the total
 Lower objective variable (max) sensitivity limit
cost of the inputs of new product.
 Compare that total cost to the profit.
8−4 = 4
 If profit > cost, produce. If profit < cost, don’t produce.

 Upper objective variable (max) sensitivity limit

Example 3
A farmer in Georgia has a 100-acre farm on which to plant
8 + 4 = 12
watermelons and cantaloupes. Every acre planted with
Example 2 watermelons requires 50 gallons of water per day and must be
Andre manufactures 3 types of silicon chips for computers: central prepared for planting with 20 pounds of fertilizer. Every acre
processing units (C), integrated circuits (I) and core memories (M). planted with cantaloupes requires 75 gallons of water per day and
The following linear program applies: must be prepared for planting with 15 pounds of fertilizer. The
farmer estimates that it will take 2 hours of labor to harvest each
𝑀𝑎𝑥 𝜋 = 0.25𝐶 + 0.4𝐼 + 0.15𝑀
acre planted with watermelons and 2.5 hours to harvest each acre
subject to
planted with cantaloupes.
0.005𝐶 + 0.02𝐼 + 0.01𝑀 ≤ 10,000 (silicon sheets)
0.2𝐶 + 0.5𝐼 + 0.1𝑀 ≤ 200,000 (labor in minutes)
He believes that watermelons will sell for about $3 each, and
cantaloupes will sell for about $1 each. Every acre planted with
watermelons is expected to yield 90 salable units. Every acre
planted with cantaloupes is expected to yield 300 salable units. The
farmer can pump about 6,000 gallons of water per day for Notes:
irrigation purposes from a well. He can buy as much fertilizer as he  Watermelons: $270/acre  $210/acre ($2.33/unit)
needs at a cost of $10 per 50-pound bag.  Cantaloupes: $300/acre  $350/acre ($1.17/unit)
 Set up new objective function with new prices.
Finally, the farmer can hire laborers to harvest the fields at a rate of
$5 per hour. If the farmer sells all the watermelons and cantaloupes d.) Suppose the farmer can lease up to 20 acres of land from
he produces, how many acres of each crop should the farmer plant a neighboring farm to plant additional crops. How many
in order to maximize profits? acres should the farmer lease, and what is the maximum
amount he should pay to lease each acre?
𝑀𝑎𝑥 𝜋 = 270𝑊 + 300𝐶
(20𝑊 + 15𝐶)
− [(10 ×
50
) + (5 × (2𝑊 + 2.5𝐶))] He should lease all 20 acres for $199/acre.
Subject to
50𝑊 + 75𝐶 ≤ 6,000 Notes:
𝑊 + 𝐶 ≤ 100
 Look at shadow price of land (199)
 Maximum
Rewrite objective function:
𝑀𝑎𝑥 𝜋 = 270𝑊 + 300𝐶 − [(4𝑊 + 3𝐶) + (10𝑊 + 12.5𝐶)]
𝑀𝑎𝑥 𝜋 = 270𝑊 + 300𝐶 − 14𝑊 − 15.5𝐶 Example 4
𝑀𝑎𝑥 𝜋 = 256𝑊 + 284.5𝐶 Ethan Resources (ER) has 2 mines with different production
capabilities for producing the same type of ore. After mining and
Acres of Watermelons = 60 crushing, the ore is graded into 3 classes: high, medium and low.
Acres of Cantaloupes = 40

The company has contracted to provide local smelters with 24 tons

a.) How much can the price of watermelons drop before it is of high-grade ore, 16 tons of medium-grade ore and 48 tons of
no longer optimal to plant any watermelons? low-grade ore each week. It costs 10,000 per day to operate Mine
A and 5,000 per day to run Mine B. In a day’s time, Mine A
270 − 66.33 = 203.67
produces 6 tons of high-grade ore, 2 tons of medium-grade ore,

203.67 and 4 tons of low-grade ore. Mine B produces 2, 2, and 12 tons per
= 2.26
90 day of each grade, respectively.

3 − 2.26 = 0.74
Management’s problem is to determine how many days per week
to operate each mine under current conditions.
Notes:
 Look at allowable decrease of revenue of watermelon.
a.) How much, if any, excess production would result if the
 Subtract 66.33 from 270 then divide answer by 90 to get
operating decision is based on minimizing costs?
the lowest possible price.
b.) What would be the cost effect of increasing low-grade ore
sales by 50%?
b.) How much does the price of cantaloupes have to increase
c.) What is ER’s minimum acceptable price per ton if it is to
before it is optimal to only grow cantaloupes?
renew a current contract to provide one of its customers

300 + 99.5 = 399.5 with 6 tons of high-grade ore per week?

d.) With current output requirements, how much would the
399.5
= 1.33 cost of operating Mine A have to rise before ER changes
300
its operating decision?

1.33 − 1 = 0.33 e.) What increase in the cost of operating Mine B would
cause ER to change its current operating decision?
c.) Suppose the price of watermelons drops by $60 per acre,
and the price of cantaloupes increases by $50 per acre. Is Degeneracy

the current solution still optimal? No.

Difficulties encountered in employing the simplex method when a.) Add a constraint that holds the objective
the problem is degenerate: function at the current optimal solution
a. Two or more quotients share the distinction of being the b.) Maximize or minimize the value of one of the
smallest, so that two or more rows are eligible as pivot decision variables with an allowable increase or
rows. decrease of zero
b. Each pivot step fails to improve the value of the objective
function. 𝑀𝑎𝑥 𝑥1 + 2𝑥2
Subject to
Degeneracy I 2𝑥1 + 4𝑥2 ≤ 12
 Tie in minimum coefficient or minimum ratio 4𝑥1 + 3𝑥2 ≤ 24
𝑥1 , 𝑥2 ≥ 0
 Allowable increase or decrease of constraint constant is
zero
Example 1
 May cause circling phenomenon The CitruSun Corporation ships frozen orange juice concentrate for
 Consequences: processing plants in Eustis and Clermont to distributors in Miami,
a.) Reduced costs for the variable cells may not be Orlando and Tallahassee. Each plant can produce 20 tons of
unique concentrate each week. The company has just received orders of 10
b.) Allowable increases and decreases for the tons from Miami for the coming week, 15 tons for Orlando, and 10
objective function coefficients still hold, and in tons for Tallahassee. The cost per ton for supplying each of the
fact, the coefficients may have to changed distributors from each of the processing plants is shown in the
substantially beyond the allowable increase and following table.
decrease limits before the optimal solution
changes Miami Orlando Tallahassee
c.) Shadow prices and their ranges may not be
Eustis 260 220 290
unique
Clermont 230 240 310

𝑀𝑎𝑥 3𝑥1 + 9𝑥2

The company wants to determine the least costly plan for filling
Subject to
their orders for the coming week.
𝑥1 + 4𝑥2 ≤ 8
𝑥1 + 2𝑥2 ≤ 4
𝑥1 , 𝑥2 ≥ 0 1. What is the optimal solution?
2. Is the optimal solution degenerate?
Notes: 3. Is the optimal solution unique? If not, identify an alternate

 If slope of objective function and slope of at least 1 optimal solution to the problem.
4. How would the solution change if the plant in Clermont is
constraint are not the same, then you have a Degenrate I
forced to shut for one day resulting in a loss of 4 tons of
problem.
production capacity?
 Problem above:
5. What would the optimal objective function value be if the
a.) Slope of OF: -1/3 processing capacity in Eustis was reduced by 5 tons?
b.) Slope of constraint 1: -1/4 6. Interpret the reduced cost for shipping from Eustis to
c.) Slope of constraint 2: -1/2 Miami.

 Complementary slackness does not apply because surplus

Example 2
of dual problem is 0, but value of solutions in primal Incline Electronics produces 3 different products in a plant that is
problem is also 0. open 40 hours per week. Each product requires the following
processing times (in hours) on each of 3 machines.
Degeneracy II: Infinite Number of Solutions
 Allowable increase or allowable decrease in one of the
Product 1 Product 2 Product 3
coefficients of the objective function is zero
Machine 1 2 2 1
 Alternative solution can be generated:
Machine 2 3 4 6
 Machine 3 4 6 5 Transportation Problem
James Bond operates a distribution system that must meet the

Each machine must be run by one of 19 cross-trained workers who following requirements.
are each available 34 hours per week. The plant has 10 type 1 Plant Capacity Warehouse Demand

machines available, 6 type 2 machines available, and 8 type 3 A 100 U 150

machines available. Products 1, 2 and 3 contribute $90, $120 and B 150 V 200
$150, respectively, in marginal profit per unit produced. C 300 W 200

1. Is the solution degenerate?

Unit shipping costs are
2. Explain the value of the shadow price associated with
Machine 1. Shipping Cost to Destination
Source U V W
3. If the plant could hire another cross-trained worker, would
you recommend the company do so? Why?
A 10 7 8

4. Suppose that the marginal profit for each product was B 15 12 9

computed using estimated costs. If you could get more C 7 8 12
accurate profit estimates for these products, which one(s)
would be of greatest interest to you? Why?
Variables:

Application of Linear Programming Problem 𝑥𝐴𝑈  shipping from A to U

𝑥𝐴𝑉  shipping from A to V
Production and Cost Analysis
𝑥𝐴𝑊  shipping from A to W
Bond Company is trying to determine the amount of each of two
𝑥𝐵𝑈  shipping from B to U
products to produce. The following information concerns labor
availability, labor utilization and product profitability. 𝑥𝐵𝑉  shipping from A to V
𝑥𝐵𝑊  shipping from A to W
Labor hours
Product (hours/unit) 𝑥𝐶𝑈  shipping from C to U
available
Department 1 2 𝑥𝐶𝑉  shipping from C to V
A 1.00 0.35 100 𝑥𝐶𝑊  shipping from C to W
B 0.30 0.20 36
C 0.20 0.50 50 𝑀𝑖𝑛 𝐶 = 10𝑥𝐴𝑈 + 7𝑥𝐴𝑉 + 8𝑥𝐴𝑊 + 15𝑥𝐵𝑈 + 12𝑥𝐵𝑉 + 9𝑥𝐵𝑊 + 7𝑥𝐶𝑈 +
Profit per 8𝑥𝐶𝑉 + 12𝑥𝐶𝑊
30 15
unit subject to
𝑥𝐴𝑈 + 𝑥𝐴𝑉 + 𝑥𝐴𝑊 ≤ 100
a. Develop a LPP to determine optimal production. 𝑥𝐵𝑈 + 𝑥𝐵𝑉 + 𝑥𝐵𝑊 ≤ 150
b. In computing profit per unit, Bond doesn’t deduct labor 𝑥𝐶𝑈 + 𝑥𝐶𝑉 + 𝑥𝐶𝑊 ≤ 300
𝑥𝐴𝑈 + 𝑥𝐵𝑈 + 𝑥𝐶𝑈 ≥ 150
costs because they are considered fixed for the period.
𝑥𝐴𝑉 + 𝑥𝐵𝑉 + 𝑥𝐶𝑉 ≥ 200
However, suppose that overtime can be scheduled in 𝑥𝐴𝑊 + 𝑥𝐵𝑊 + 𝑥𝐶𝑊 ≥ 200
some of the departments. Which department would you 𝑥𝑖𝑗 ≥ 0, 𝑖 = 𝐴, 𝐵, 𝐶 𝑗 = 𝑈, 𝑉, 𝑊
recommend scheduling for overtime? How much would
you be willing to pay per hour of overtime in each James is preparing a shipment schedule to meet the demands at
department?
the least cost possible.
c. Suppose that 10, 6 and 8 hours of overtime may be
a.) How much will be shipped from C to warehouse W?
scheduled in departments A, B, and C, respectively. The
b.) What is the minimum transportation counts?
cost per hour of overtime is 18, 22.50 and 12 in
departments A, B, and C, respectively. Formulate a LPP to
determine the optimal production. How much overtime James is contemplating of opening a new plant D that would have
do you recommend using in each department? a capacity of 200 units. It would cost Php8 per unit for this plant to
service each warehouse.
 c.) How much will be shipped from plant D to warehouse U if 𝑥23 + 𝑥43 ≥ 10
𝑥34 + 𝑥44 ≥ 7
the plan pushes through? 𝑥35 + 𝑥55 ≥ 4
d.) Should James push through with the plan? Explain why or 𝑥56 + 𝑥66 ≥ 6

why not.
Blending Problem
Jason Bourne manufactures a coffee product by blending 3 types
Employee Scheduling
of coffee beans. The cost per pound and the available pounds of
UP police schedules officers for 8-hour shifts. The beginning times
each bean are as follows:
for shifts are 8am, 12nn, 4pm, 8pm, 12mn and 4am. An officer
beginning a shift at one of these times work for the next 8 hours.
Bean Cost per Pound Available Pounds
During normal weekday operations, the number of officers needed
1 0.50 500
varies depending on the time of day. The staffing guidelines
2 0.70 600
require the following minimum umber of officers on duty:
3 0.45 400

Time of Day Minimum officers on duty

Consumer tests with coffee products were used to provide ratings
(1) 8am – 12nn 5
on a scale of 0 to 100, with higher ratings indicating higher quality.
(2) 12nn – 4pm 6
Product quality standards for the blended coffee require a
(3) 4pm – 8pm 10
consumer rating for aroma to be at least 75 and a consumer rating
(4) 8pm – 12mn 7
for taste to be at least 80. The individual ratings of the aroma and
(5) 12nn – 4am 4
taste for coffee made from 100% of each bean are as follows:
(6) 4am – 8pm 6
Bean Aroma Taste

Time 1 73 86
Start End 1 2 3 4 5 6 2 85 88
8am 4pm 𝑥11 𝑥12
3 60 75
12nn 8pm 𝑥22 𝑥23

4pm 12mn 𝑥34 𝑥35 Assume that the aroma and taste attributes of the coffee blend will

8pm 4am 𝑥43 𝑥44 be weighted average of the attributes of the beans used in the

12nn 8pm 𝑥55 𝑥56 blend.

4am 12nn 𝑥61 𝑥66 1. What is the minimum-cost blend that will meet the quality

5 6 10 7 4 6 standards and provide 1,000 pounds of the blended

coffee product?

i = shifts = 1, 2, …, 6
j = time of shifts = 1, 2, …, 6 Variables:

(e.g. x11 is the first shift, first period of the day)  𝑥1  Percentage of bean 1
 𝑥2  Percentage of bean 2

Determine the number of police officers that should be scheduled  𝑥3  Percentage of bean 3

to begin the 8-hour shifts at each of the six times (8am, 12nn, 4pm,
8pm, 12mn, 4pm) to minimize the total number of officers required.
𝑀𝑖𝑛 𝐶 = 0.50(1,000)𝑥1 + 0.70(1,000)𝑥2 + 0.45(1,000)𝑥3
Subject to
𝑀𝑖𝑛 𝑥11 + 𝑥12 + ⋯ , + 𝑥66
73𝑥1 + 85𝑥2 + 60𝑥3 ≥ 75
86𝑥1 + 88𝑥2 + 75𝑥3 ≥ 80
subject to 1,000𝑥1 ≤ 500
𝑥11 + 𝑥61 ≥ 5 1,000𝑥2 ≤ 600
𝑥12 + 𝑥22 ≥ 6 1,000𝑥3 ≤ 400
 𝑥1 + 𝑥2 + 𝑥3 = 1 Acme has 120 units in inventory on hand for this product. To
maintain a level workforce, the company wants to produce at least
𝑥1 = 0.5 𝑜𝑟 50%  500 pounds
400 units per month. It also wants to maintain a safety stock of at
𝑥2 = 0.34 𝑜𝑟 34%  340 pounds
least 50 units per month. Acme wants to determine how many
𝑥3 = 0.16 𝑜𝑟 16%  160 pounds
appliances to manufacture during each of the next 4 months to
meet the expected demand at the lowest possible total cost.
2. What is the cost per pound for the coffee blend?

Cash Flow Problem

500(0.50) + 340(0.70) + 160(0.45) = 560 JR wants to establish a construction fund (or sinking fund) to pay

for a new bowling alley he is having built. Construction of the

560
1000
= 0.56 bowling alley is expected to take 6 months and cost $300,000. JR’s
contract with the construction company requires him to make
3. Determine the aroma and taste ratings for the coffee payments of $50,000 at the end of the second and fourth months,
blend. and a final payment of $200,000 at the end of the sixth month
Aroma Rating = 75 when the bowling alley is completed. JR has identified 4
Taste Rating = 84.92 investments he can use to establish the construction fund; these
4. If additional coffee were to be produced, what would be investments are summarized in the following table:
the expected cost per pound? 0.56
5. If the minimum required aroma rating is increased to 80, Available in Months to Yield at
Investment
month maturity maturity
what is the minimum-cost blend that will meet the new
A 1, 2, 3, 4, 5, 6 1 1.2%
quality standards?
B 1, 3, 5 2 3.5%

C 1, 4 3 5.8%
𝑥1 = 0.4166 𝑜𝑟 41.67%  416.70 pounds
D 1 6 11.0%
𝑥2 = 0.5833 𝑜𝑟 58.33%  583.30 pounds
𝑥3 = 0 𝑜𝑟 0%  0 pounds
JR wants to minimize the amount of money he must invest in

Production and Inventory Problem month 1 to meet the required payments for this project.

Acme Manufacturing makes a variety of household appliances at a

single manufacturing facility. The expected demand for one of Notes:

these appliances during the next 4 months is shown in the  What you have at the beginning of the month, you use to

following table along with the expected production costs and the pay or invest.

expected capacity for producing these items.  What is available to me at the beginning of the month is
the money I have invested in previous periods that have

Month become mature.

1 2 3 4  At the beginning of month 1, you have not invested

Demand 420 580 310 540 anything yet so nothing has matured.

Production  At the beginning of month 2, you’ll have money maturing

$49 $45 $46 $47
Cost
from some investment (A).
Production
500 520 450 550
Capacity  1.012A1  What is available to me at the beginning of the
2nd month and can be used to invest in A again (A2)
Acme estimates that it costs $1.50 per month for each unit of this

appliance carried in inventory (estimated by averaging the Beginning of 2nd Month:

beginning and ending inventory levels each month). Currently, 1.012𝐴1 = 𝐴2 + 0
 1.012𝐴1 − 𝐴2 ≥ 0
1.012𝐴2 + 1.035𝐵1 − 𝐴3 − 𝐵3 ≥ 50,000
Beginning of 3rd Month: 1.012𝐴3 + 1.058𝐶1 − 𝐴4 − 𝐶4 ≥ 0
1.012𝐴2 + 1.035𝐵1 = 𝐴3 + 𝐵3 + 50,000 1.012𝐴4 + 1.035𝐵3 − 𝐴5 − 𝐵5 ≥ 50,000
1.012𝐴5 − 𝐴6 ≥ 0
1.012𝐴6 + 1.035𝐵5 + 1.058𝐶4 + 1.11𝐷1 ≥ 200,000
Beginning of 4th Month:
1.012𝐴3 + 1.058𝐶1 = 𝐴4 + 𝐶4

Make vs. Buy Problem

Beginning of 5th Month
The Weedmacker Company manufactures 2 types of lawn
1.012𝐴4 + 1.035𝐵3 = 𝐴5 + 𝐵5 + 50,000
trimmers: an electric model and a gas model. The company has
contracted to supply a national discount retail chain with a total of
Beginning of 6th Month:
1.012𝐴5 = 𝐴6 30,000 electric trimmers and 15,000 gas trimmers. However,
Weedmacker’s production capability is limited in 3 departments:
Beginning of 7th Month production, assembly, and packaging. The following table
1.012𝐴6 + 1.035𝐵5 + 1.058𝐶4 + 1.11𝐷1 = 200,000 summarizes the hours of processing time available and the

processing time required by each department, for both types of

Notes:
trimmers:
 All equations above are your constraints.
 Objective Function: 𝑀𝑖𝑛 𝐴1 + 𝐵1 + 𝐶1 + 𝐷1
Hours Required per Trimmer
 A4 is a function of A1 so you can express all constraints in
Electric Gas Hours Available
terms of A1 (same goes for B, C, D)
Production 0.20 0.40 10,000
 Only decision JR has to make is how much to invest in A,
Assembly 0.30 0.50 15,000
B, C, D at the beginning of the period (beginning of first
Packaging 0.10 0.10 5,000
month)

The company makes its electric trimmer in-house for $55 and its
Questions
gas trimmer for $85. Alternatively, it can buy electric gas trimmers
1. How much investment in A will JR make in month 2?
from another source for $67 and $95, respectively.
2. How much investment in B will JR make in month 3?
3. How much investment in C will JR make in month 4?
1. How many gas and electric trimmers should Weedmacker
4. How much investment in D will JR make in month 1?
make and buy?
5. Use the dual price to determine how much more JR
2. How much would electric trimmers have to cost in order
should be willing to pay to delay the payment due at the
for the company to consider purchasing these items
end of the second month to the end of the third month.
rather than making them?

3. If the cost to make gas trimmers increased to $90 per

For #5:
unit, how would the optimal solution change?
 (Dual price of Php50,000) x Php50,000
4. How much should the company be willing to pay to
 If you reduce Php50,000 in the 2nd constraint, it will
acquire additional capacity in the assembly area? Explain.
reduce the value of the objective function. But you’re also
5. How much should the company be willing to pay to
going to increase 0 in the 3rd constraint. This will increase
acquire additional capacity in the production area?
the objective function. What you need to do is get the net
Explain.
of the changes in the objective function.
6. Suppose the hours of production capacity available are
uncertain and could vary from 9,500 to 10,500. How does
𝑀𝑖𝑛 𝐴1 + 𝐵1 + 𝐶1 + 𝐷1
Subject to
 the optimal solution change for every 100-hour change in
production capacity within this range? The efficiency of unit i:

Data Envelopment Analysis 𝑤𝑒𝑖𝑔ℎ𝑡𝑒𝑑 𝑠𝑢𝑚 𝑜𝑓 𝑢𝑛𝑖𝑡 𝑖 ′ 𝑠 𝑜𝑢𝑡𝑝𝑢𝑡𝑠

𝐸𝑖 =
Fidelity Savings & Loss operates several banking facilities 𝑤𝑒𝑖𝑔ℎ𝑡𝑒𝑑 𝑠𝑢𝑚 𝑜𝑓 𝑢𝑛𝑖𝑡 𝑖 ′ 𝑠 𝑖𝑛𝑝𝑢𝑡𝑠

throughout the Southeastern United States. The officers of FS&L

∑𝑛𝑗=1
𝑜
𝑂𝑖𝑗 𝑤𝑗
want to analyze the efficiency of the various branch offices using 𝐸𝑖 =
∑𝑛𝑗=1
𝐼
𝐼𝑖𝑗 𝑣𝑗
DEA. The data below has been selected to represent appropriate
input and output measures of each banking facility. Compute the 𝑛

𝑀𝑎𝑥 ∑ 𝑂𝑖𝑗 𝑤𝑗
DEA efficiency for each branch office.
𝑗=1

Subject to
New Satisfaction Labor Operation 𝑛0 𝑛1
Branch R.O.A.
Loans Rating Hours Costs ∑ 𝑂𝑖𝑗 𝑤𝑗 − ∑ 𝐼𝑖𝑗 𝑣𝑗 ≤ 0
1 5.32 770 92 3.73 6.34 𝑗=1 𝑗=1
𝑛𝐼

2 5.39 780 94 3.49 4.43 ∑ 𝐼𝑖𝑗 𝑣𝑗

𝑗=1
3 4.95 790 93 5.98 6.31
𝑘 = 1, … , 𝑛
4 6.01 730 82 6.49 7.28

5 6.40 910 98 7.09 8.69 𝑀𝑎𝑥 𝑂1 𝑤1 + 𝑂2 𝑤2 + 𝑂3 𝑤3

6 2.89 860 90 3.46 3.23 subject to

𝑂11 𝑤1 + 𝑂12 𝑤2 + 𝑂13 𝑤3 − 𝐼11 𝑣1 − 𝐼12 𝑣2 ≤ 0
7 6.94 880 89 7.36 9.07 𝑂21 𝑤1 + 𝑂22 𝑤2 + 𝑂23 𝑤3 − 𝐼21 𝑣1 − 𝐼22 𝑣2 ≤ 0
8 7.18 970 99 6.38 7.42 ⋮
𝐼11 𝑣1 − 𝐼12 𝑣2 = 1
9 5.98 770 94 4.74 6.75

10 4.97 930 91 5.04 6.35

Notes:

 If efficiency ratio < 1, that branch is inefficient.

 Cost of operations: Labor hours and operation costs
 If difference between weighted output and weighted
 Income sources (not necessarily in monetary terms): New
input is negative, that branch is inefficient.
loans, return on assets, satisfaction rating
 Results of each solver equation only pertains to 1 branch.
(E.g. you solved for branch 2 and got values for branch 1
Notes:
also. Disregard values for branch 1 and all other values
 You can only say branch 1 does better than branch 2 if
that don’t pertain to branch 2.)
both branches were given the same input and branch 1
 A branch is inefficient if it is using more inputs than
produced more; However, inputs and outputs both differ.
expected or producing less output than is expected.
 You can compare costs and income if all variables were
 If you want to make a branch efficient, you think about
expressed in the same unit, but because that’s not the
how to increase the amount of output using the same
case, you need to use DEA.
amount of inputs.
 Production Possibility Frontier:
 When you look at Solver results, you find branches with
a.) Producing on the frontier is efficient.
almost 0 difference (negative number with many decimal
b.) Producing inside frontier is inefficient.
points, e.g. 3E-15, 2E-15). These also have positive shadow
c.) Producing outside frontier is not possible.
prices.
 Compare the different branches in terms of where they
 Use results in sensitivity report to determine how to make
are in relation to their production possibility frontier.
branches efficient.
 Our concern is which units are inefficient, rather than
 Paste column of shadow prices beside difference column.
which units are efficient.
  Get the sumproduct of ROA column and shadow price
column. Do the same for the other columns. (e.g. new
loans and shadow price, rating and shadow price, etc.)
 From the sumproduct, you get the combined inputs and
outputs of branches 6 and 8. You’ll find that combined
inputs will be lower than that of branch 3, and that output

would be higher.
 Branches 6 and 8 serve as models for branch 3, because
the combined operations/characteristics, if emulated by
branch 3, would make branch 3 efficient because it will
allow branch 3 to produce more output with less input.
 Sometimes, reference branch and composite branch will

have the same inputs, but composite will have more

output.
 Sometimes, reference branch and composite branch will
have the same output, but composite branch will use less
inputs.
 Inefficient branches: Branch 3, branch 10

 For branch 10, it should emulate branches 1, 6, 8

DOSS
1. Do the thing 5 times.
2. Weights * output of composite
3. Shadow * input