Transcript Graphical Solution 1-2004

BM 4808
Linear Programming Models:
Graphical Solution
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.
Introduction
Management decisions in many organizations
involve trying to make most effective use of
resources.
– Machinery, labor, money, time, warehouse
space, and raw materials.
– Produce products - such as computers,
automobiles, or clothing or
– Provide services - such as package delivery,
health services, or investment decisions.
To solve problems of resource allocation one may
use mathematical programming.
Mathematical Programming
Mathematical programming used for
resource allocation problems.
Linear programming (LP) is most common
type of mathematical programming.
One assumes all relevant input data and
parameters are known with certainty in
models (deterministic models).
Development of a LP Model
LP applied extensively to problems areas – medical, transportation, operations,
– financial, marketing, accounting,
– human resources, and agriculture.
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).
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
$7 T + $5 C
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)
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.
Allows one to provide an intuitive
explanation of how more complex
solution procedures work for larger LP
models.
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-negativityconstraint 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
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 .
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)
Subject to:
5A + 10B  90
4A + 3B  48
½A
 1½
A  0, B  0
constraint)
= 2A + 3B
(protein constraint)
(vitamin constraint)
(iron constraint)
(nonnegativity
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
Summary of Graphical Solution Methods
1. Graph each constraint equation.
2. Identify feasible solution region, that is, area
that satisfies all constraints simultaneously.
3. Use Corner Point Method and proceed to solve
problem.
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).
Special Situations in Solving LP Problems
1. 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
Special Situations in Solving LP Problems
2. 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
Special Situations in Solving LP Problems
3. 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
Special Situations in Solving LP Problems
4. Alternate Optimal Solutions
An LP problem may have more than one
optimal solution.
– In other words, when they have same slope.
Example: Alternate Optimal Solutions
Maximize profit =
$3x + $2y
Subject to:
6X + 4Y  24
X  3
X, Y  0