Transcript Linear Programming Intro

Linear Programming
Intro
HSPM J716
Linear Programming
• Optimization under constraint
• Linear constraints and objective function
Elements of a Linear Programming
Manufacturing Problem
• Things you can make or do in different
amounts.
• Constraints
– Tell you how much you get from different
combinations of resources
– Tell you how much you have of each resource.
• Objective function
– Assigns a value to what you make
– Your objective is to maximize this value
What Linear Implies
• No increasing or diminishing returns in the use
of the resources.
• Everything just multiplies and adds.
• The profit or revenue is linear, too. How much
you make is price times quantity. No declining
demand curve.
Translate the words into math
• Profit is $3 per desk and $4 per table.
• Objective function Profit = 3d + 4t
• A desk takes 2½ hours to assemble; a table takes 1.
• 20 hours of assembly time are available.
• Constraint A: 2.5d + 1t <= 20
• A desk takes 3 hours to buff; a table takes 3.
• 30 hours of buffing time are available.
• Constraint B: 3d + 3t <= 30
• A desk takes 1 hour to crate; a table takes 2.
• 16 hours of crating time are available.
• Constraint C: 1d + 2t <= 16
Graph method
• Each product is assigned to an axis.
• Plot the constraints as equalities.
– Draw a line for each constraint.
• The feasible area is the polygon formed by the
axes and the lowest constraints.
– The axes are constraints – You are not allowed to
make a negative amount of any product.
Graph method:
Using the profit function
• Pick an arbitrary profit number and set the
profit equal to it.
• E.g. 3d + 4t = 12
• Plot this on the graph
• Move this parallel to itself up or down until
the line just touches a corner of the feasible
area.
Graph method drawbacks
• How good a draftsman are you?
• Can’t work in three or more dimensions
Enumeration method
• Find all the intersections
– Of the constraints
– And the axes
• Test each for feasibility
• Choose the feasible intersection with the
highest profit.
Enumeration method good and bad
•
You can do problems with more than two
dimensions.
•
The math grows rapidly as the number
of activities and constraints grows.
Constraints
Products Intersections Calculations
3
2
10
53
6
4
210
8,960
6
6
924
133,056
12
8
125,970 42,997,760
Simplex Method
• A closed shape with flat sides is a “simplex.”
• The simplex method starts with a corner of
the feasible area that is easy to find.
• Then it crawls along an edge to another
corner. It picks the direction that makes profit
go up the fastest.
• It keeps going until it finds a corner where any
move lowers profit.
• Shortcuts the enumeration method. A local
maximum is a global maximum.
George B. Dantzig (1914-2005)
“The Father of Linear Programming”
Shadow price
• How much more money you could make if you
had one more unit of a resource
– That’s the shadow price for that resource
• If you could buy one more unit of a resource,
the most you’d be willing to pay would be the
shadow price.