Department of Business Administration
SPRING 2019
Linear Programming
Source (Managerial economics in global economy by Dominick
Salvatore)
Linear Programming
Mathematical Technique for Solving Constrained
Maximization and Minimization Problems
Assumes that the Objective Function is Linear
Assumes that All Constraints Are Linear
Applications of Linear Programming
Optimal Process Selection
Optimal Product Mix
Satisfying Minimum Product Requirements
Long-Run Capacity Planning
Least Cost Shipping Route
(Transportation Problems)
Applications of Linear Programming
Airline Operations Planning
Output Planning with Resource and Process
Capacity Constraints
Distribution of Advertising Budget
Routing of Long-Distance Phone Calls
Investment Portfolio Selection
Allocation of Personnel Among Activities
Production Processes
Feasible Region Optimal Solution (S)
Formulating and Solving Linear
Programming Problems
Express Objective Function as an Equation
and Constraints as Inequalities
Graph the Inequality Constraints and
Define the Feasible Region
Graph the Objective Function as a Series of
Isoprofit or Isocost Lines
Identify the Optimal Solution
PowerPoint
Slides by Robert
F. Brooker
Copyright (c)
2001 by
Harcourt, Inc. All
rights reserved.
Profit Maximization
Quantities of Inputs Quantities of Inputs
Required per Available per
Unit of Output Time Period
Input Product X Product Y Total
A 1 1 7
B 0.5 1 5
C 0 0.5 2
Maximiz = $30QX + (objective function)
e $40QY (input A constraint)
Subject
1QX + 1QY 7 (input B constraint)
to
0.5QX + 1QY 5 (input C constraint)
0.5QY 2 (nonnegativity constraint)
QX , Q Y 0
Profit Maximization
Multiple Optimal Solutions
New objective function has the same slope as the feasible region
at the optimum
Profit Maximization
Algebraic Solution
Points of Intersection Between Constraints are Calculated to
Determine the Feasible Region
Profit Maximization
Algebraic Solution
Profit at each point of intersection between
constraints
is calculated to determine the optimal point (E)
Corner Point QX QY Profit
0 0 0 $0
D 7 0 210
*E 4 3 240
F 2 4 220
G 0 4 160
Cost Minimization
Meat (Food X) Fish (Food Y)
Price per pound $2 $3
Units of Nutrients Minimum Daily
Per Pound of Requirements
Nutrient Meat (Food X) Fish (Food Y) Total
Protein 1 1 7
Minerals 0.5 1 5
Vitamins 0 0.5 2
Minimize C = $2QX + $3QY (objective function)
Subject 1QX + 2QY 14 (protein constraint)
to
1QX + 1QY 10 (minerals constraint)
1QX + 0.5QY 6 (vitamins constraint)
(nonnegativity constraint)
QX , Q Y 0
Cost Minimization
Feasible Region Optimal Solution (E)
Cost Minimization
Algebraic Solution
Cost at each point of intersection between constraints is
calculated to determine the optimal point (E)
Corner Point QX QY Cost
D 14 0 $28
*E 6 4 24
F 2 8 28
G 0 12 36
Dual of the Profit
Maximization Problem
Maximiz = $30QX + (objective function)
e $40QY (input A constraint)
Subject 1QX + 1QY 7 (input B constraint)
to
0.5QX + 1QY 5 (input C constraint)
0.5QY 2 (nonnegativity constraint)
QX , Q Y 0
Minimize C = 7VA + 5VB + 2VC
Subject 1VA + 0.5VB $30
to
1VA + 1VB + 0.5VC $40
VA , V B , V C 0
Dual of the Cost
Minimization Problem
Minimize C = $2QX + $3QY (objective function)
Subject 1QX + 2QY 14 (protein constraint)
to
1QX + 1QY 10 (minerals constraint)
1QX + 0.5QY 6 (vitamins constraint)
(nonnegativity constraint)
QX , Q Y 0
Maximiz = 14VP + 10VM + 6VV
e
1VP + 1VM + 1VV $30
Subject
to 2VP + 1VM + 0.5VV $40
VP, VM, VV 0
Example : 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.
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:
Space Rays = 450 dozen 8(450) + 5(100)
Zapper = 100 dozen
Profit = $4100 per week
Management is seeking a
production schedule that
will increase the company’s
profit.
A linear programming model
can provide an insight and an
intelligent solution to this problem.
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
The Galaxy Linear Programming
Model
Max 8X1 + 5X2 (Weekly profit)
subject to
2X1 + 1X2 £ 1000 (Plastic)
3X1 + 4X2 £ 2400 (Production Time)
X1 + X2 £ 700 (Total production)
X1 - X2 £ 350 (Mix)
Xj> = 0, j = 1,2 (Nonnegativity)
The Graphical Analysis of Linear
Programming
The set of all points that satisfy all the
constraints of the model is called
a
FEASIBLE REGION
Using a graphical presentation
we can represent all the
constraints,
the objective function, and the
three
types of feasible points.
Graphical Analysis – the Feasible
Region
X2
The non-negativity constraints
X1
Graphical Analysis – the Feasible
Region
X2
1000 The Plastic constraint
2X1+X2 £ 1000
700 Total production constraint:
X1+X2 £ 700 (redundant)
500
Infeasible
Production Feasible
Time
3X1+4X2 £ 2400 X1
500 700
Graphical Analysis – the Feasible
Region
X2
1000 The Plastic constraint
2X1+X2 £ 1000
700 Total production constraint:
X1+X2 £ 700 (redundant)
500
Infeasible
Production mix
constraint:
Production Feasible X1-X2 £ 350
Time
3X1+4X2£ 2400
X1
500 700
Boundary points.
Interior points. Extreme points.
• There are three types of feasible points
Solving Graphically for an Optimal Solution
The search for an optimal solution
Start
X2 at some arbitrary profit, say profit = $2,000...
1000 Then increase the profit, if possible...
...and continue until it becomes infeasible
700 Profit
500
=$4360
X1
500
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.
31
The End
Thanks
