Linear Programming:
Model Formulation and
Solution
MBA 8104: Quantative
Analysis
2-
1
Chapter
Topics
Model Formulation
A Maximization Model Example
Graphical Solutions of Linear Programming
Models
A Minimization Model Example
Characteristics of Linear Programming Problems
Solving Linear Programming Problems with TORA
presentation
notes
Introduction
Objectives of business decisions frequently involve
maximizing profit or minimizing costs.
Linear programming uses linear algebraic
relationships to represent a firm’s decisions, given a
business objective, and resource constraints.
Steps in application:
1. Identify problem as solvable by
linear programming.
2. Formulate a mathematical model of
the unstructured problem.
3. Solve the model.
4. Implementation presentation
notes
Model
• Components
Decision variables - mathematical symbols representing
levels of activity of a firm.
• Objective function - a linear mathematical relationship
describing an objective of the firm, in terms of decision
variables - this function is to be maximized or
minimized.
• Constraints – requirements or restrictions placed on the firm
by the operating environment, stated in linear relationships
of the decision variables.
• Parameters - numerical coefficients and constants used in
the objective function and constraints.
presentation
notes
Summary of Model Formulation
Steps
Step 1 : Clearly define the decision
variables
Step 2 : Construct the objective function
Step 3 : Formulate the constraints
presentation
notes
LP Model
Formulation
Illustration 1: A Maximization Example (1 of
4)
• Product mix problem - Beaver Creek Pottery Company
• How many bowls and mugs should be produced to
maximize profits given labor and materials constraints?
• Product resource requirements and unit profit:
Labor Clay
Resource Requirements Profit
Produ
(Hr./Unit (Lb./Unit ($/Unit
ct
Bow ) 1 ) 4 ) 4
l 2 3 0
Mug 5
presentation 0
notes
LP Model Formulation
A Maximization Example (2 of
4)
presentation
notes
LP Model
Formulation
A Maximization Example (3 of
4)
Resource 40 hrs of labor per
Availabilit day 120 lbs of clay
y:
x1 = number of bowls to produce per
Decision day x2 = number of mugs to produce
Variable per day
s:
Maximize Z = $40x1 +
Objecti $50x2 Where Z = profit per
ve
day
Functio
n: 1x1 + 2x2 40 hours of labor
4x1 + 3x2 120 pounds of
Resource
Constraint clay
presentation
s: notes
x1 0; x2 0
Non-
LP Model
Formulation
A Maximization Example (4 of
4)
Complete Linear Programming
Model:
Maximiz Z = $40x1 +
e $50x2
subject
to: 1x1 + 2x2 40
4x2 + 3x2 120
x1, x2 presentation
0
notes
Feasible
Solutions
A feasible solution does not violate any of the
constraints:
Exampl x1 = 5 bowls
e: x2 = 10
mugs
Z = $40x1 +
Labor constraint
$50x2 = 1(5) + 2(10) = 25 < 40 hours
check: Clay constraint
$700 4(5) + 3(10) = 70 < 120
check: pounds
presentation
notes
Infeasible
Solutions
An infeasible solution violates at least one of
the constraints:
Exampl x1 = 10 bowls
e: x2 = 20
mugs
Z = $40x1 +
Labor constraint
$50xcheck:
2= 1(10) + 2(20) = 50 > 40
hours $1400
presentation
notes
Graphical Solution of LP
Models
• Graphical solution is limited to linear programming
models containing only two decision variables (can be
used with three variables but only with great difficulty).
• Graphical methods provide visualization of how a solution
for a linear programming problem is obtained.
presentation
notes
Coordinate Axes
Graphical Solution of Maximization
Model
(1 of 12)
X2 is mugs
Maximize Z = $40x1 + $50x2
subject to: 1x1 + 2x2
40
4x2 + 3x2
120
x1, x2 0
X1 is bowls
presentation
Fig notes
ure
Labor
Constraint
Graphical Solution of Maximization Model (2 of
12)
Maximize Z = $40x1 + $50x2
subject to: 1x1 + 2x2
40
4x2 + 3x2
120
x1, x2 0
Figure 2.3 Graph of Labor
Constraint
presentation
notes
Labor Constraint Area
Graphical Solution of Maximization Model (3 of
12)
Maximize Z = $40x1 + $50x2
subject to: 1x1 + 2x2
40
4x2 + 3x2
120
x1, x2 0
Figure 2.4 Labor Constraint
Area
presentation
notes
Clay Constraint Area
Graphical Solution of Maximization Model (4 of
12)
Maximize Z = $40x1 + $50x2
subject to: 1x1 + 2x2
40
4x2 + 3x2
120
x1, x2 0
Figure 2.5 Clay Constraint
presentation
notes Area
Both Constraints
Graphical Solution of Maximization Model (5 of
12)
Maximize Z = $40x1 + $50x2
subject to: 1x1 + 2x2
40
4x2 + 3x2
120
x1, x2 0
Figure 2.6 Graph of Both Model
presentation
Constraints
notes
Feasible Solution
Graphical
Area Solution of Maximization Model (6 of
12)
Maximize Z = $40x1 + $50x2
subject to: 1x1 + 2x2
40
4x2 + 3x2
120
x1, x2 0
Figure 2.7 Feasible Solution
Area
presentation
notes
Objective Function Solution =
Graphical
$800 Solution of Maximization Model (7 of
12)
Maximize Z = $40x1 + $50x2
subject to: 1x1 + 2x2
40
4x2 + 3x2
120
x1, x2 0
Figure 2.8 Objection Function Line for Z =
$800
presentation
notes
Alternative Objective Function Solution
Graphical
Lines Solution of Maximization Model (8 of
12)
Maximize Z = $40x1 + $50x2
subject to: 1x1 + 2x2
40
4x2 + 3x2
120
x1, x2 0
Figure 2.9 Alternative Objective Function
Lines
presentation
notes
Optimal Solution
Graphical Solution of Maximization Model (9 of
12)
Maximize Z = $40x1 + $50x2
subject to: 1x1 + 2x2
40
4x2 + 3x2
120
x1, x2 0
Figure Identification of Optimal Solution
2.10 Point
presentation
notes
Optimal Solution
Coordinates
Graphical Solution of Maximization Model (10 of
12)
Maximize Z = $40x1 + $50x2
subject to: 1x1 + 2x2
40
4x2 + 3x2
120
x1, x2 0
Figure 2.11 Optimal Solution
Coordinates
presentation
notes
Extreme (Corner) Point Solutions
Graphical Solution of Maximization Model (11 of
12)
Maximize Z = $40x1 + $50x2
subject to: 1x1 + 2x2
40
4x2 + 3x2
120
x1, x2 0
Figure 2.12 Solutions at All Corner
Points
presentation
notes
Optimal Solution for New Objective Function
Graphical Solution of Maximization Model (12 of 12)
Maximize Z = $70x1 + $20x2
subject to: 1x1 + 2x2
40
4x2 + 3x2
120
x1, x2 0
Figure 2.13 Optimal Solution with Z = 70x 1 +
20x2
presentation
notes
Slack
Variables
Standard form requires that all constraints be in
the form of equations (equalities).
A slack variable is added to a constraint
(weak inequality) to convert it to an
equation (=).
A slack variable typically represents an
unused resource.
A slack variable contributes nothing to the
objective function value.
presentation
notes
Linear Programming Model: Standard
Form
Max Z = 40x1 + 50x2 + s1 +
s2 subject to:1x1 + 2x2 + s1 =
40
4x2 + 3x2 + s2 = 120
x1, x2, s1, s2 0
Where:
x1 = number of bowls
x2 = number of mugs
s1, s2 are slack
variables
presentation
notes
Figure
Illustration 2: LP Model Formulation – Minimization (1 of
8)
Two brands of fertilizer available - Super-gro, Crop-quick.
Field requires at least 16 pounds of nitrogen and 24 pounds
of phosphate.
Super-gro costs $6 per bag, Crop-quick $3 per bag.
Problem: How much of each brand to purchase to minimize total
cost of fertilizer given following data ?
Chemical Contribution
N itroge Phosphat
Brand
n (lb/ e (lb/
Super-gro bag)2 bag)4
Crop-quick 4 3
presentation
notes
LP Model Formulation – Minimization (2 of
8)
Figure 2.15
Fertilizing farmer’s
field
presentation
notes
LP Model Formulation – Minimization (3 of
8)
Decision Variables:
x1 = bags of Super-gro
x2 = bags of Crop-
quick
The Objective Function:
Minimize Z = $6x1 +
3x2
Where:
$6x1 = cost of bags of
Super-Gro
$3x2 = cost of
bags of
Crop-Quick
presentation
notes
Model Constraints:
2x + 4x 16 lb (nitrogen constraint)
Constraint Graph – Minimization (4 of
8)
Minimize Z = $6x1 + $3x2
subject to: 2x1 + 4x2
16
4x2 + 3x2
24 x1, x2 0
Figure 2.16 Graph of Both Model
Constraints
presentation
notes
Feasible Region– Minimization (5 of
8)
Minimize Z = $6x1 + $3x2
subject to: 2x1 + 4x2
16
4x2 + 3x2
24 x1, x2 0
Figure 2.17 Feasible Solution
Area
presentation
notes
Optimal Solution Point – Minimization (6 of
8)
Minimize Z = $6x1 + $3x2
subject to: 2x1 + 4x2
16
4x2 + 3x2
24 x1, x2 0
Figure 2.18 Optimum Solution
Point
presentation
notes
Surplus Variables – Minimization (7 of
8)
A surplus variable is subtracted from a constraint
to convert it to an equation (=).
A surplus variable represents an excess above
a constraint requirement level.
A surplus variable contributes nothing to the
calculated value of the objective function.
Subtracting surplus variables in the farmer
problem constraints:
2x1 + 4x2 - s1 = 16 (nitrogen)
4x1 + 3x2 - s2 = 24 (phosphate)
presentation
notes
Graphical Solutions – Minimization (8 of
8)
Minimize Z = $6x1 + $3x2 + 0s1 +
subject
0s2 2x1 + 4x2 – s1 =
to: 16
4x2 + 3x2 – s2 =
24
x1, x2, s1, s2 0
Figure 2.19 Graph of Fertilizer
Example
presentation
notes
Irregular Types of Linear Programming
Problems
For some linear programming models, the
general rules do not apply.
• Special types of problems include those with:
Multiple optimal solutions
Infeasible solutions
Unbounded solutions
presentation
notes
Multiple Optimal Solutions Beaver Creek
Pottery
The objective function is
parallel to a constraint
line.
Maximize Z=$40x
subject 1x11++ 2x2
30x 2 40
to: 4x2 + 3x2
120
Where: x1, x2 0
x1 = number of
bowls x2 = number
of mugs
Fig presentation
ure notes
2.2
An Infeasible
Problem
Every possible solution
violates at least one
constraint:
Maximize
subject Z = 5x 3x22
4x1 + 2x
to: 8 x1 4
x2 6
x1, x2 0
Figure 2.21 Graph of an Infeasible
Problem
presentation
notes
An Unbounded
Problem
Value of the objective
function increases
indefinitely:
Maximize Z = 4x1 +
2x2 subject to: x1 4
x2 2
x1, x2 0
Figure 2.22 Graph of an Unbounded
Problem
presentation
notes
Characteristics of Linear Programming
Problems
• A decision amongst alternative courses of action is
required.
• The decision is represented in the model by
decision variables.
• The problem encompasses a goal, expressed as an
objective function, that the decision maker wants
to achieve.
• Restrictions (represented by constraints) exist that limit
the extent of achievement of the objective.
• The objective and constraints must be definable by linear
mathematical functional relationships.
presentation
notes
Properties of Linear Programming
Models
• Proportionality - The rate of change (slope) of the
objective function and constraint equations is constant.
• Additivity - Terms in the objective function and
constraint equations must be additive.
• Divisibility -Decision variables can take on any fractional
value and are therefore continuous as opposed to integer in
nature.
• Certainty - Values of all the model parameters are assumed
to be known with certainty (non-probabilistic).
presentation
notes
Problem Statement: Example (1 of
3)
■ Hot dog mixture in 1000-pound batches.
■ Two ingredients, chicken ($3/g) and beef ($5/g).
■ Recipe requirements:
at least 500 pounds of
“chicken” at least 200 pounds
of “beef”
■ Ratio of chicken to beef must be at least 2 to
1.
■ Determine optimal mixture of ingredients that will
minimize costs.
presentation
notes
Solution: Example Problem No. 1 (2 of
3)
Step 1:
Identify decision variables.
x1 = Quantity in grams of chicken in
mixture x2 = Quantity in grams of beef in
mixture
Step 2:
Formulate the objective function.
Minimize Z = $3x1 + $5x2
where Z = cost per 1,000-lb batch
$3x1 = cost of chicken
$5x2 = cost of beef
presentation
notes
Solution: Example Problem No. 1 (3 of
Step 3: 3)
Establish Model Constraints
x1 + x2 = 1,000 lb
x1 500 g of
chicken x2 200 g
of beef
x1/x2 2/1 or x1 - 2x2
0 x1, x2 0
The Model: Minimize Z = $3x1 +
5x2
subject to: x1
+ x2 = 1,000 g x1
50
x2 200 presentation
notes
x1 - 2x2 0 x1,x2 0
Example Problem No. 2 (1 of
3)
Solve the following
model graphically:
Maximize Z = 4x1 + 5x2
subject to: x1 + 2x2
10
6x1 + 6x2
36 x1 4
x1, x2 0
Step 1: Plot the
constraints as
equations
presentation
F notes
i
Example Problem No. 2 (2 of
3)
Maximize Z = 4x1 + 5x2
subject to: x1 + 2x2
10
6x1 + 6x2
36 x1 4
x1, x2 0
Step 2: Determine the
feasible solution space
Figure 2.24 Feasible Solution Space and Extreme
Points
presentation
notes
Example Problem No. 2 (3 of
3)
Maximize Z = 4x1 + 5x2
subject to: x1 + 2x2
10
6x1 + 6x2
36 x1 4
x1, x2 0
Step 3 and 4: Determine
the solution points and
optimal solution
Figure 2.25 Optimal Solution
Point
presentation
notes
Group work No. 1: Super Grain Corp. Advertising-Mix
Problem
Goal: Design the promotional campaign for Crunchy Start.
The three most effective advertising media for this product are
Television commercials on Saturday morning programs
for children.
Advertisements in food and family-oriented magazines.
Advertisements in Sunday supplements of major
newspapers.
The limited resources in the
problem are
Advertising budget ($4 million) .
Planning budget ($1 million) .
TV commercial spots available (5).
The objective will be measured in terms of
the expected number of exposures.
Question: At what level should they presentation
notes
advertise Crunchy Start in each of the
three media?
Cost and Exposure
Data Costs
Each
TV Each Each
Cost Category Com Magazine Ad Sunday Ad
merc
Ad Budget
ial
$300,000 $150,000 $100,000
($4 million)
Planning
budget 90,000 30,000 40,000
($1
million)
Expected
number of 1,300,000 600,000 500,000
exposures
presentation
notes
Group work No. 2 Think-Big Capital Budgeting
Problem
Think-Big Development Co. is a major investor in commercial real-
estate development projects.
They are considering three large construction projects
Construct a high-rise office building.
Construct a hotel.
Construct a shopping center.
Each project requires each partner to make four investments: a down
payment now, and additional capital after one, two, and three years.
Given the following table determine at what fraction should Think-
Big invest in each of the three projects.
presentation
notes
Financial Data for the
Projects Office
Investment Capital Requirements
Shopping
Year Hotel
Building Center
0 $40 million $80 million $90 million
1 60 million 80 million 50 million
2 90 million 80 million 20 million
3 10 million 70 million 60 million
Net present
$45 million $70 million $50 million
value
Assume for years 0 through 3 the firm has: $25MM, $45MM, $65MM, and $80MM available.
(cumulative)
presentation
notes
Diet Mix
A prison is tryingProblem
to decide what to feed its prisoners. They would like to offer
some combination of milk, beans, and oranges. Their goal is to minimize
cost, subject to meeting the minimum nutritional requirements imposed by
law. The cost and nutritional content of each food, along with the minimum
nutritional requirements are shown below.
Na vy Orang es M inimum
M ilk B ( larg e Ca . Da ily
(g s) eans lif Va len c R equ i remen t
allon (cup ia )
s)
Niacin ( m g) 3.2 4 .9 0 .8 13 .0
Thiam in (mg ) 1.12 1 .3 0. 19 1 .5
V it amin C (mg ) 32 .0 0 .0 93 . 0 45 .0
Cost ($ ) 2.00 0.20 0. 25
presentation
notes