Transcript X - Angelfire

Managerial Decision Modeling
with Spreadsheets
Chapter 2
Linear Programming Models:
Graphical and Computer Methods
Learning Objectives
• Understand basic assumptions and
properties of linear programming (LP).
• Use graphical solution procedures for LP
problems with only two variables to
understand how LP problems are solved.
• Understand special situations such as
redundancy, infeasibility, unboundedness,
and alternate optimal solutions in LP
problems.
2.1. Introduction
• Management decisions in many organizations
involve trying to make most effective use of
resources.
– Machinery, labor, money, time, warehouse space,
and raw materials.
• To solve problems of resource allocation one
may use mathematical programming (LP).
Mathematical Programming
• One assumes all relevant input data and
parameters are known with certainty in
models (deterministic models).
2.2 Development of a LP Model
• Development of all LP models can be
examined in three step process:
– (1) formulation.
– (2) solution.
– (3) interpretation.
Three Steps of Developing LP Problem
Formulation
– Process of translating problem scenario into simple LP
model framework with set of mathematical relationships.
Solution
– Mathematical relationships resulting from formulation
process are solved to identify optimal solution.
Interpretation and What-if Analysis
– Problem solver or analyst works with manager to
• Interpret results and implications of problem solution.
• Investigate changes in input parameters and model
variables and impact on problem solution results.
Properties of a LP Model
1. All problems seek to maximize or minimize
some quantity, usually profit or cost (called
objective function).
2. LP models usually include restrictions, or
constraints, limit degree to which one can
pursue objective.
3. Must be alternative courses of action from
which to choose.
4. Objective and constraints in LP problems must
be expressed in terms of linear equations or
inequalities.
Linear Equations and Inequalities
• This is a linear equation:
2A + 5B = 10
• This equation is not linear:
2A2 + 5B3 + 3AB = 10
• LP uses, in many cases, inequalities like:
A+BC
or A + B  C
Basic Assumptions of a LP Model
1. Conditions of certainty exist.
2. Proportionality in objective function and
constraints (1 unit – 3 hours, 3 units 9 hours).
3. Additivity (total of all activities equals sum of
individual activities).
4. Divisibility assumption that solutions need not
necessarily be in whole numbers (integers).
2.3 Formulating a LP Problem
• A common LP application is product mix problem.
– Two or more products are usually produced using limited
resources - such as personnel, machines, raw materials,
and so on.
• Profit firm seeks to maximize is based on profit
contribution per unit of each product.
• Firm would like to determine – How many units of each product it should produce
– Maximize overall profit given its limited resources.
LP Example: Flair Furniture Company
Company Data and Constraints • Flair Furniture Company produces tables and chairs.
• Each table requires: 4 hours of carpentry and 2 hours of painting.
• Each chair requires: 3 hours of carpentry and 1 hour of painting.
• Available production capacity: 240 hours of carpentry time and 100
hours of painting time.
• Due to existing inventory of chairs, Flair is to make no more than
60 new chairs.
• Each table sold results in $7 profit, while each chair produced
yields $5 profit.
Flair Furniture’s problem:
• Determine best possible combination of tables and chairs to
manufacture in order to attain maximum profit.
Decision Variables
• Problem facing Flair is to determine how many
chairs and tables to produce to yield maximum
profit?
• In Flair Furniture problem, there are two
unknown entities:
T - number of tables to be produced.
C - number of chairs to be produced.
Objective Function
• Objective function states goal of problem.
– What major objective is to be solved?
– Maximize profit!
• An LP model must have a single objective function.
In Flair’s problem, total profit may be expressed as:
Using decision variables T and C Maximize
$7T + $5C
($7 profit per table) x (number of tables produced) +
($5 profit per chair) x (number of chairs produced)
Constraints
• Denote conditions that prevent one from
selecting any specific subjective value for
decision variables.
• In Flair Furniture’s problem, there are
three restrictions on solution.
– Restrictions 1 and 2 have to do with available
carpentry and painting times, respectively.
– Restriction 3 is concerned with upper limit on
number of chairs.
Constraints
• There are 240 carpentry hours available.
4T + 3C < 240
• There are 100 painting hours available.
2T + 1C  100
• The marketing specified chairs limit constraint.
C  60
• The non-negativity constraints.
T  0
(number of tables produced is  0)
C  0 (number of chairs produced is  0)
2.4 Graphical Solution of a LP
With Two Variables
• Primary advantage of two-variable LP
models (such as flair furniture’s problem)
is their solution can be graphically
illustrated using two-dimensional graph.
Graphical Representation of Constraints
Complete LP model for flair’s case:
Maximize profit = $7T + $5C
(objective function)
Subject to constraints 4T + 3C  240
(carpentry constraint)
2T + 1C  100
(painting constraint)
C  60
(chairs limit constraint)
T  0
(non-negativity constraint on tables)
C  0
(non-negativity constraint on chairs)
Graphical Representation of Constraints
Carpentry Time Constraint
4T + 3C  240
Graphical Representation of Constraints
Carpentry Time Constraint
Any point
below line
satisfies
constraint.
Graphical Representation of Constraints
Painting Time Constraint
2T + 1C  100
Any point on line
satisfies equation:
2T + 1C = 100
(30,40) yields 100.
Any point below line
satisfies constraint.
Graphical Representation of Constraints
Chair Limit Constraint and Feasible Solution Area
Feasible solution
area is contained
by three limiting
lines
Graphical Solution
• Isoprofit Line Solution Method
• Corner Point Solution Method
Corner Point Property
Property states optimal solution to LP
problem will always occur at a corner
point.
Corner Point Solution Method
From figure one knows
feasible region for Flair’s
problem has five corner
points, namely, 1, 2, 3, 4,
and 5, respectively.
To find point yielding
maximum profit, one finds
coordinates of each corner
point and computes profit
level at each point.
Corner Point Solution Method
• Point 1 (T = 0, C = 0)
profit = $7(0) + $5(0) = $0
• Point 2 (T = 0, C = 60)
profit = $7(0) + $5(60) = $300
• Point 3 (T = 15, C = 60)
profit = $7(15) + $5(60) = $405
• Point 4 (T = 30, C = 40)
profit = $7(30) + $5(40) = $410
• Point 5 (T = 50, C = 0)
profit = $7(50) + $5(0) = $350 .
2.5 A Minimization LP Problem
Many LP problems involve minimizing objective such
as cost instead of maximizing profit function.
Examples:
– Restaurant may wish to develop work schedule to meet
staffing needs while minimizing total number of employees.
– Manufacturer may seek to distribute its products from
several factories to its many regional warehouses in such a
way as to minimize total shipping costs.
– Hospital may want to provide its patients with a daily meal
plan that meets certain nutritional standards while
minimizing food purchase costs.
Example of a Two Variable Minimization
LP Problem
Holiday Meal Turkey Ranch
• Buy two brands of feed for good, low-cost diet for
turkeys.
• Each feed may contain three nutritional ingredients
(protein, vitamin, and iron).
• One pound of Brand A contains:
– 5 units of protein,
– 4 units of vitamin, and
– 0.5 units of iron.
• One pound of Brand B contains:
– 10 units of protein,
– 3 units of vitamins, and
– 0 units of iron.
Example of Two Variable Minimization
Linear Programming Problem
Holiday Meal Turkey Ranch
• Brand A feed costs ranch $0.02 per pound, while
Brand B feed costs $0.03 per pound.
• Ranch owner would like lowest-cost diet that meets
minimum monthly intake requirements for each
nutritional ingredient.
Summary of Holiday Meal Turkey
Ranch Data
Formulation of LP Problem:
Minimize cost (in cents) = 2A + 3B
Subject to:
5A + 10B  90
(protein constraint)
4A + 3B  48
(vitamin constraint)
½A
 1½
(iron constraint)
A  0, B  0
(nonnegativity constraint)
Where:
A denotes number of pounds of Brand A feed, and B
denote number of pounds of Brand B feed.
Graphical Solution of Holiday
Meal Turkey Ranch Problem
Drawing Constraints:
½A  1½
4A + 3B  48
5A + 10B  90
Nonnegativity Constraint
A  0, B  0
Corner Point Solution Method
• Point 1 - coordinates (A = 3, B = 12)
– cost of 2(3) + 3(12) = 42 cents.
• Point 2 - coordinates (A = 8.4, b = 4.8)
– cost of 2(8.4) + 3(4.8) = 31.2 cents
• Point 3 - coordinates (A = 18, B = 0)
– cost of (2)(18) + (3)(0) = 36 cents.
• Optimal minimal cost solution:
Corner Point 2, cost = 31.2 cents
2.6
Summary of Graphical Solution Methods
1. Graph each constraint equation.
2. Identify feasible solution region, that is, area
that satisfies all constraints simultaneously.
3. Select one of two following graphical solution
techniques and proceed to solve problem.
1. Corner Point Method.
2. Isoprofit or Isocost Method.
2.6
Summary of Graphical Solution Methods
(Continued)
Corner Point Method
• Determine coordinates of each of corner
points of feasible region by visual inspection
or solving equations.
• Compute profit or cost at each point by
substitution of values of coordinates into
objective function and solving for result.
• Identify an optimal solution as a corner point
with highest profit (maximization problem),
or lowest cost (minimization).
2.7 Special Situations in Solving LP Problems
Redundancy: A redundant constraint is constraint that
does not affect feasible region in any way.
Maximize
Profit
= 2X + 3Y
subject to:
X + Y  20
2X + Y  30
X  25
X, Y  0
2.7 Special Situations in Solving LP Problems
Infeasibility: A condition that arises when an LP problem
has no solution that satisfies all of its constraints.
X + 2Y  6
2X + Y  8
X  7
2.7 Special Situations in Solving LP Problems
Unboundedness: Sometimes an LP model will
not have a finite solution
Maximize profit
= $3X + $5Y
subject to:
X  5
Y  10
X + 2Y  10
X, Y  0
Alternate Optimal Solutions
• An LP problem may have more than one
optimal solution.
Example: Alternate Optimal Solutions
Maximize profit =
$3x + $2y
Subject to:
6X + 4Y  24
X  3
X, Y  0
LP Exercises
• P.67: Q.2-14, 15, 18
• P.68: Q.2-19, 22, 23, 25
• P.69: Q.2-30
© 2002 Prentice-Hall, Inc
Ch 2-40