Transcript Module 2 (ppt file)

Computational Methods for
Management and Economics
Carla Gomes
Module 2
Introduction to LP
(Textbook – Hillier and Lieberman)
Mathematical Models
Need to formulate problems in a way that is convenient for analysis –
typically using a mathematical model.
Mathematical models – idealized representations expressed in
terms of mathematical symbols and expressions. Famous
mathematical models
F = ma (Newton’s second law of motion) and
E=mc² (Einstein’s famous equation of conservation of
energy into mass).
Optimization Problems
In an optimization problem we want to
maximize or minimize a specific quantity
(called the objective), which depends on a
finite number of decision variables and
parameters. The variables may be independent
of one another or may be related through one
or more constraints.
Mathematical model of a business problem:
•Decision variables - they represent quantifiable decisions to be
made, under our control, say x1, x2, …, xn. The respective values are to
be determined.
•Objective function – expresses the appropriate measure of
performance as a mathematical function of the decision variables. E.g.,
P = 2 x1 + 5 x2 + …+ xn
•Constraints – any restriction on the values of the variables are also
expressed mathematically, typically by means of equations (e.g. 2 x1 +
3 x2 <= 10)
•Parameters of the model – constants (namely coefficients and rightend-sides) in the constraints and objective function.
Typical OR model
Choose the decision variables so as to maximize (or minimize) the
objective function, subject to the specified constraints.
Example of Optimization
Problem
Minimize: Z = x12 + x22
Subject to:
2x1 – 2x2 = 6
x2  2
Z – objective;
x 1, x 2
- decision variables; two constraints;
Mathematical Program
• Optimization problem in which the objective and
constraints are given as mathematical functions
and functional relationships.
• Optimize: Z = f(x1, x2, …, xn)
• Subject to:
g1(x1, x2, …, xn) = ,  ,  b1
g2(x1, x2, …, xn) = ,  ,  b2
…
gm(x1, x2, …, xn) = ,  , 
bm
Linear Programming (LP)
• One of the most important scientific advances of the 20th
century
• A variety of applications:
Financial planning, Marketing, E-business, Telecommunications,
Manufacturing, Transportation Planning, System Design, Health Care
• Remarkably efficient solution procedures to solve LP
models – simplex method and interior point methods --• Very fast LP solvers (CPLEX – from 1981-2001
2,000,000X faster!)
Linear Programming (LP)
• Linear – all the functions are linear (f and g functions are linear.
Ex: f (x1, x2, …, xn)= c1x1 + c2 x2 + … cn xn
• Programming – does not refer to computer programming but
rather “planning” - planning of activities to obtain an optimal result
i.e., it reaches the specified goal best (according to the mathematical
model) among all feasible alternatives.
Prototype Example –
Wyndor Glass (Hillier and Liebermnan)
Wyndor Glass Co. Product Mix Problem
• Wyndor has developed the following new
products:
– An 8-foot glass door with aluminum framing.
– A 4-foot by 6-foot double-hung, wood-framed window.
• The company has three plants
– Plant 1 produces aluminum frames and hardware.
– Plant 2 produces wood frames.
– Plant 3 produces glass and assembles the windows and
doors.
Questions:
1. Should they go ahead with launching these two new
products?
2. If so, what should be the product mix?
Steps in setting up a LP
1.
2.
3.
Determine and label the decision variables.
Determine the objective and use the decision variables to
write an expression for the objective function.
Determine the constraints - feasible region.
1.
2.
Determine the explicit constraints and write a functional
expression for each of them.
Determine the implicit constraints (e.g., nonnegativity
constraints).
The LP Mathematical model
Problem of determining the optimal product mix
(maximizing profit) for Wyndor as an LP.
Step 1: Determine the decision variables (write a
statement per variable).
– Specify the unknowns that determine the profit; each variable has
to be well defined in English; careful with units!!!
– Put yourself in the shoes of the decision maker and then ask the
question “What are the unknowns in this particular problem that
impact the overall performance measure?”
(Often, the most difficult part of any modeling problem.
Once the decision variables are correctly identified then the remainder
of the modeling process usually goes smoothly.)
Objective Function
Step 2 Specify the problem objective (write an
expression for the objective function)
Feasible Region
Step 3 Express the feasible region as the solution set of a
finite collection of linear inequality and equality
constraints.
3.1. Determine the functional constraints
3.1. Determine the non-negativity constraints
Algebraic Model for Wyndor
Glass Co.
Let D = the number of doors to produce
W = the number of windows to produce
Maximize P = 3 D + 5 W
subject to
D≤4
2W ≤ 12
3D + 2W ≤ 18
and
D ≥ 0, W ≥ 0.
A graphical solution
Since this problem is two dimensional it is possible to
provide a graphical solution. To graphically find the
feasible region, we will follow these steps:
1.
2.
Graph the line associated with each of the linear
inequality constraints.
Determine on which side of each of these lines the
feasible region must lie.
Graphing the Product Mix
W
Production rate (units per week) for windows
8
A product mix of
D = 4 and W = 6
7
(4, 6)
6
5
4
A product mix of
D = 2 and W = 3
3
(2, 3)
2
1
Origin
-2
-1
0
-1
-2
1
2
3
4
5
6
7
Production rate (units per week) for doors
8
D
Graph Showing Non-Negativity
Constraints:
D ≥ 0 and W ≥ 0
W
Production rate for windows
8
6
4
2
0
2
4
Production rate for doors
6
8
D
Nonnegative Solutions Permitted by
D≤4
W
8
Production rate for windows
D= 4
6
4
2
0
2
6
4
Production rate for doors
8
D
Nonnegative Solutions Permitted by
2W ≤ 12
Production rate for windows
W
8
2 W = 12
6
4
2
0
2
4
Production rate for doors
6
8
D
Boundary Line for Constraint
3D + 2W ≤ 18
Production rate for windows
W
10
(0, 9)
8
1
(1, 7 _)
2
(2, 6)
6
3 D + 2 W = 18
1
(3, 4 _)
2
4
(4, 3)
2
1
(5, 1 _)
2
(6, 0)
0
2
4
Production rate for doors
6
8
D
Changing Right-Hand Side Creates
Parallel Constraint Boundary Lines
Production rate for windows
W
12
10
3D + 2W = 24
8
6
3D + 2W = 18
4
2
0
3D + 2W = 12
2
4
6
Production rate for doors
8
10
D
Nonnegative Solutions Permitted by
3D + 2W ≤ 18
Production rate for windows
W
10
8
6
3D + 2W = 18
4
2
0
2
4
Production rate for doors
6
8
D
Graph of Feasible Region
Production rate for windows
W
10
3 D + 2 W = 18
8
D= 4
6
2 W =12
4
Feasible
2
0
region
2
4
Production rate for doors
6
8
D
Graph of Feasible Region
Production rate for windows
W
10
3 D + 2 W = 18
8
D= 4
6
2 W =12
4
Feasible
2
0
region
2
4
Production rate for doors
6
8
D
Objective Function (P = 1,500)
Production rate
W
for windows
8
6
4
P = 1500 = 300D + 500W
Feasible
region
2
isoprofit line
0
2
4
Production rate for doors
6
8
D
Finding the Optimal Solution
Production rate
W
for windows
Our objective function is:
maximize 3D+5W
8
P = 3600 = 300D + 500W
P = 3000 = 300D + 500W
The vector representing the
gradient of the objective
function is:
3
Optimal solution
(2, 6)
6
5
 
Feasible
4
P = 1500 = 300D + 500W
region
The line through the origin that
contains this vector is:
2
0
5
W  D
3
isoprofit line
2
4
Production rate for doors
6
8
10
D
Summary of the Graphical Method
• Draw the constraint boundary line for each constraint. Use the origin (or any point
not on the line) to determine which side of the line is permitted by the constraint.
• Find the feasible region by determining where all constraints are satisfied
simultaneously.
• Determine the slope of one objective function line (perpendicular to its gradient
vector). All other objective function lines will have the same slope.
• Move a straight edge with this slope through the feasible region in the direction of
improving values of the objective function (direction of the gradient). Stop at the last
instant that the straight edge still passes through a point in the feasible region. This
line given by the straight edge is the optimal objective function line.
• A feasible point on the optimal objective function line is an optimal solution.
Terminology and Notation
• Resources – m (plants)
• Activities – n (2 products)
• Wyndor Glass problem optimal product mix --allocation of resources to activities i.e., choose the levels
of the activities that achieve best overall measure of
performance
Terminology and notation (cont.)
• Z – value of the overall measure of performance; value of the objective
function,
• xj – level of activity j (for j = 1, 2, …, n)
 decision variables
• cj – increase in Z for each unit increase in the level of activity j;
coefficient of objective function associated with activity j
• bi – amount of resource i that is available (for i=1,2,…, m). Right-handside of constraint associated with resource i.
• aij – amount of resource i consumed by each unit of
activity
j. Technological coefficient.
(The values of cj, bi, and aij are the input constants for the model
 the parameters of the model. )
Standard form of the LP model
xi >= 0 , (i =1,2,…,n)
Other forms:
Minimize Z (instead of maximizing Z)
Some functional constraints have signs >= (rather than <=)
Some functional constraints are equalities
Some variables have unrestricted sign, i.e., they are not
subject to the non-negativity constraints
Terminology of solutions in LP model
• Solution – not necessarily the final answer to the problem!!!
• Feasible solution – solution that satisfies all the constraints
• Infeasible solution – solution for which at least one of the
constraints is violated
• Feasible region – set of all points that satisfies all the constraints
(possible to have a problem without any feasible solutions)
• Binding constraint – the left-hand side and the right-hand side of the
constraint are equal, I.e., constraint is satisfied in equality.
Otherwise the constraint is nonbinding.
• Optimal solution – feasible solution that has the best value of the
objective function.
Largest value  maximization problems
Smallest value  minimization problems
• Multiple optimal solutions
• No optimal solutions
• Unbounded Z
Corner Point Solutions
• Corner-point feasible solution – special solution that plays a key
role when the simplex method searches for an optimal solution.
Relationship between optimal solutions and CPF solutions:
– Any LP with feasible solutions and bounded feasible region 
• (1) the problem must possess CPF solutions and at least one optimal
solution
• (2) the best CPF solution must be an optimal solution
If the problem has exactly one optimal solution it must be a CFP
solution
If the problem has multiple optimal solutions, at least two must be
CPF solutions
No Feasible Solutions – Why?
Maximize P = 3 D + 5 W
Production rate for windows
W
10
subject to
D≤4
2W ≤ 12
3D + 2W ≤ 18
3 D + 2 W = 18
8
D= 4
3 D + 5 W 50
6
2 W =12
and
D ≥ 0, W ≥ 0.
4
Feasible
2
0
Previous
region
Feasible
Region
2
4
Production rate for doors
6
8
D
Multiple Optimal Solutions.
Why?
Maximize P = 3 D + 2 W
Production rate for windows
W
10
subject to
D≤4
2W ≤ 12
3D + 2W ≤ 18
3 D + 2 W = 18
8
D= 4
6
and
2 W =12
D ≥ 0, W ≥ 0.
4
Every point on this line is
An optimal solution
with P=18
Feasible
2
0
region
2
4
Production rate for doors
6
8
D
Unbounded Objective Function. Why?
(4, ) P=
W
Maximize P = 3 D + 2 W
subject to
D≤4
(4,8) P=28
8
Production rate for windows
D= 4
and
6
D ≥ 0, W ≥ 0.
4
(4,4) P=20
2
(4,2) P=16
0
2
6
4
Production rate for doors
8
D
LP Assumptions
Proportionality –
The contribution of each activity to the value of the objective function Z is
proportional to the level of the activity xj as represented by the cjxj term;
The contribution of each activity to the left-hand side of each functional
constraint is proportional to the level of the activity xj as represented by
the term aij.
This assumption implies that all the x terms of the linear equations cannot
have exponents greater than 1.
Note: if there is a term that is a product of different variables,
even though the proportionality assumption is satisfied,
the additivity assumption is violated.
Examples of violation of proportionality
assumption
Case 1 - violation occurs
as a result of e.g., startup costs,
associated with product 1.
E.g., costs of setting up
the production, or distribution
of product 1.
Examples of violation of proportionality
assumption
Case 2 - slope of the objective function for product 1 keeps increasing as x1 is increased –
there is an increasing marginal return. Economies of scale that sometimes
can be achieved at higher levels of production (e.g., more efficient machinery,
discounts for large purchases,etc).
Case 3 – opposite of case 2; the slope of the objective function for product 1 keeps
decreasing as x1 is increased – there is a decreasing marginal return.
E.g., in order to sell higher volumes of product 1 require a major marketing campaign.
Case 2
Case 3
What to do when proportionality
is violated?
Non linear programming;
To deal with case 1 (fixed charge problem) –
mixed integer programming.
3 x1 – 1 for x1 > 0;
3 x1
for x1 = 0;
LP Assumptions
Additivity
The contribution of all variables to the objective
function and to the left-hand side of the functional
constraints has to be additive, i.e., it has to be the
sum of the individual contributions of the
respective activities – therefore crossproducts of
variables are ruled out.
Case 3 – the two products are complementary in some way that increases the
profit! E.g., a major marketing campaign required for product 2
will help product 1.
Case 4 – the two products are competitive in some way that decreases the profit!
E.g., two products use the same equipment and that requires setting up costs
for going from one product to the other.
What to do when additivity assumption violated:
realm of non-linear programming!!!
LP Assumptions
Divisibility
Decision variables in an LP model are allowed to
have any values, including noninteger values, that
satisfy the functional and nonnegativity
constraints. i.e., activities can be run at fractional
levels.
What to do when divisibility assumption violated:
realm of integer programming!!!
LP Assumptions
Certainty
The parameters of the model, (coefficients of the objective
function and of the functional constraints, and the righ-hand
sides of the functional constraints) are assumed to be known
constants.
T Rarely the case – sometimes we use approximations 
important to perform sensitivity analysis to identify sensitive
parameters (the parameters that cannot be changed without
changing the value of the objective function).
What to do when certainty assumption violated:
treat parameters as random variables
LP Assumptions - Comments
Quite often the assumptions are not 100%
applicable!
Except for the divisibility assumption, minor
disparities are to be expected. This is especially true
for the certainty assumption, so sensitivity analysis
normally is a must to compensate for the violation of
this assumption!
LP Assumptions - Comments
Mathematical model --- abstractions of the real world
problem.
Approximations and simplifying assumptions
generally are required in order for the model to be
tractable.
Adding too much detail and precision can make the
model too complex for useful analysis of the
problem.
Main issues  a correlation between the prediction
of the model and what would actually happen in the
real problem.
Additional Examples
• Giapetto’s Woodcarving (from Winston and
Venkataramanan)
• Dorian Auto (from Winston and Venkataramanan)
• Radiation Therapy (from Hillier and Lieberman)
Giapetto’s Woodcarving, Inc.
(from Winston)
Giapetto’s Woodcarving, Inc. manufactures two types of wooden
toys: soldiers and trains. A soldier sells for $27 and uses $10 worth
of raw materials. Each soldier that is manufactured increases
Giapetto’s variable labor and overhead costs by $14. A train sells
for $21 and uses $9 worth of raw materials. Each train built
increases Giapetto’s variable labor and overhead costs by $10. The
manufacture of wooden soldiers and trains requires two types of
skilled labor: carpentry and finishing. A soldier requires 2 hours of
finishing labor and 1 hour of carpentry labor. A train requires 1
hour of finishing and 1 hour of carpentry labor. Each week,
Giapetto can obtain all the needed raw material but only 100
finishing hours and 80 carpentry hours. Demand for trains is
unlimited, but at most 40 soldiers are bought each week. Giapetto
wants to maximize weekly profit (revenues – costs). Formulate a
mathematical model of Giapetto’s situation that can be used to
maximize Giapetto’s weekly profit.
3.2 – Graphical Solution to a 2-Variable LP
Binding and Nonbinding constraints
Once the optimal solution to an LP is found, it is
useful to classify each constraint as being a
binding or nonbinding constraint.
A constraint is binding if the left-hand and righthand side of the constraint are equal when the
optimal values of the decision variables are
substituted into the constraint. In the Giapetto
LP, the finishing and carpentry constraints are
binding.
3.2 – Graphical Solution to a 2-Variable LP
A constraint is nonbinding if the lefthand side and the right-hand side of the
constraint are unequal when the optimal
values of the decision variables are
substituted into the constraint. In the
Giapetto LP, the demand constraint for
wooden soldiers is nonbinding since at
the optimal solution (x1 = 20), x1 < 40.
3.2 – Graphical Solution to a 2-Variable LP
Convex sets, Extreme Points, and LP
A set of points S is a convex set if the line segment jointing
any two pairs of points in S is wholly contained in S.
For any convex set S, a point p in S is an extreme point if
each line segment that lines completely in S and contains the
point P has P as an endpoint of the line segment.
Consider the figures (a) – (d) below:
A
E
B
A
B
B
A
D
C
(a)
(b)
(c)
(d)
3.2 – Graphical Solution to a 2-Variable LP
For example, in figures (a) and (b) below, each
line segment joining points in S contains only
points in S. Thus is convex for (a) and (b). In
both figures (c) and (d), there are points in the
line segment AB that are not in S. S in not
convex for (c) and (d).
A
E
B
A
B
B
A
D
C
(a)
(b)
(c)
(d)
3.2 – Graphical Solution to a 2-Variable LP
In figure (a), each point on the circumference of
the circle is an extreme point of the circle. In
figure (b), A, B, C, and D are extreme points of
S. Point E is not an extreme point since E is not
an end point of the line segment AB.
A
E
B
A
B
B
A
D
C
(a)
(b)
(c)
(d)
3.2 – Graphical Solution to a 2-Variable LP
Extreme points are sometimes called
corner points, because if the set S is a
polygon, the extreme points will be the
vertices, or corners, of the polygon.
The feasible region for the Giapetto LP
will be a convex set.
3.2 – Graphical Solution to a 2-Variable LP
It can be shown that:
• The feasible region for any LP will be a
convex set.
• The feasible region for any LP has only
a finite number of extreme points.
1. Any LP that has an optimal solution
has an extreme point that is optimal.
Dorian Auto
(from Winston)
Dorian Auto manufactures luxury cars and trucks. The company
believes that its most likely customers are high-income men and
women. To reach these groups, Dorian Auto has embarked on an
ambitious TV advertising campaign and has decided to purchase 1minute commercial spots on two types of programs: comedy shows
and football games. Each comedy commercial is seen by 7 million
high-income women and 2 million high-income men. Each football
commercial is seen by 2 million high-income women and 12 million
high-income men. A 1-minute comedy ad costs $50,000, and a 1minute football ad costs $100,000. Dorian would like the commercials
to be seen by at least 28 million high-income women and 24 million
high-income men. Use LP to determine how Dorian Auto can meet its
advertising requirements at minimum cost.
- underlined text was modified