Transcript Introduction - UW Courses Web Server

IndE 310
Linear Programming
UW Industrial Engineering
Instructor: Prof. Zelda Zabinsky
Introduction-1
Operations Research
• “The Science of Better”:
The discipline of applying advanced analytical methods to help
make better decisions
• Operations – problems that concern how to conduct and coordinate
the operations within an organization
• Research – use of the scientific method to address these problems
• Interdisciplinary – brings together:
–
–
–
–
–
mathematics
statistics
industrial engineering
management (“management science”)
systems engineering...
• Highly application oriented
Introduction-2
Introduction-3
Applications of Operations Research
• Business
– Manufacturing
•
•
•
•
Project management
Scheduling
Facility layout and location
Many more
– Service
•
•
•
•
•
Project management
Transportation and logistics
Marketing
Queueing
Many more
• Economics & Finance
–
–
–
–
Auctions
Portfolio selection
Capital investment
Many more
• Health
–
–
–
–
Scheduling
Queueing
Biotechnology
And more
• Military
Introduction-4
Examples of O.R. Applications
• China
Select and schedule projects for future energy needs
• New Haven Health Department
Design an effective needle exchange program to combat HIV
• Continental Airlines
Optimize the reassignment of crews to flights
• IBM
Reengineer supply chain
• Proctor and Gamble
Redesign production and distribution system
• Many more
Introduction-5
Operations Research
(Understand and)
Model
(and verify)
(Strategize and)
Solve
(and make recommendations)
Structuring the real-life situation into a mathematical
model, abstracting the essential elements so that a
solution relevant to the decision maker's objectives can
be sought
This involves looking at the problem in the context of the
entire system
Exploring the structure of such solutions and developing
systematic procedures for obtaining them
Developing a solution, including the mathematical theory, if
necessary, that yields an optimal value of the system
measure of desirability (or possibly comparing alternative
courses of action by evaluating their measure of
desirability)
Introduction-6
Operations Research
Modeling Toolset
Queueing
Theory
Simulation
Inventory
Theory
Forecasting
Game
Theory
Markov
Chains
Markov
Decision
Processes
Decision
Analysis
Dynamic
Programming
PERT/
CPM
Network
Programming
Linear
Programming
Stochastic
Programming
Nonlinear
Programming
Integer
Programming
Introduction-7
Operations Research
Modeling Toolset
311
Queueing
Theory
Simulation
Inventory
Theory
Forecasting
Game
Theory
310
Markov
Chains
Markov
Decision
Processes
Decision
Analysis
Dynamic
Programming
312
Stochastic
Programming
PERT/
CPM
Network
Programming
Linear
Programming
Nonlinear
Programming
Integer
Programming
312
312
Introduction-8
IndE 310
• Linear Programming
– Modeling
– Solving
• Simplex method
• Foundations of the simplex method
• Duality and sensitivity
• Transportation and Assignment Problems
• Network Problems
–
–
–
–
Shortest path
Minimum spanning tree
Minimum cost, maximum flow
PERT/CPM
Introduction-9
Interesting Links
• “Operation Everything”, The Boston Globe, June 27, 2004
http://www.boston.com/globe/search/stories/reprints/
operationeverything062704.html
• Links available on the course web
Introduction-10
O.R. Modeling Approach
Introduction-11
O.R. Modeling Approach
• Define the problem and gather data
• Formulate a (mathematical) model to represent the problem
• Develop a computer-based procedure for deriving solutions
• Test model and refine it
• Prepare for the ongoing application of the model
• Implement
Introduction-12
Defining the problem and gathering data
• First order of business:
– Study the relevant system
– Develop a well-defined statement of the problem
•
•
•
•
Right answer for the wrong problem?
Defining objectives
What data are needed?
Collect them (easily said)
Introduction-13
Formulating a (mathematical) model
• We need to create a model that can be used for
– Abstracting the essence of the subject
– Showing interrelationships
– Facilitating analysis
• A model: E=mc2
• A mathematical model usually consists of:
–
–
–
–
Decision variables
Parameters
Objective function
Constraints
Introduction-14
Deriving solutions
• A common theme in O.R.:
Search for an optimal solution
• Develop a procedure for deriving solutions to the
mathematical model
– e.g. what is the best speed to obtain the highest possible energy?
• What kind of a procedure?
– Usually based on theoretical foundations
– Exact vs. heuristic (slow vs. fast?)
• Post-optimality and sensitivity analysis
Introduction-15
Testing, preparing and implementing
• Need to validate the model
– “Debugging”
– Plausible results?
• Prepare to apply as prescribed by management
– Operating procedures, supporting systems, managerial reports…
• Implementation
– Coordination, detailed indoctrination, new courses of action
Introduction-16
Peeking into Chapter 3
Wyndor Glass Co. Example
• Wyndor Glass produces glass windows and doors
• They have 3 plants:
– Plant 1: makes aluminum frames and hardware
– Plant 2: makes wood frames
– Plant 3: produces glass and makes assembly
• Two products proposed:
– Product 1: 8’ glass door with aluminum siding
– Product 2: 4’ x 6’ wood framed glass window
• Some production capacity in the three plants is available to produce
a combination of the two products
• Problem is to determine the best product mix to maximize profits
Introduction-17
Peeking into Chapter 3
Wyndor Glass Co. Data
• The O.R. team has gathered the following data:
– Number of hours of production time available per week in each plant
– Number of hours of production time needed in each plant for each batch
of new products
– Estimated profit per batch of each new product
Production time per batch (hr)
Product
Production time
available per
week (hr)
Plant
1
2
1
1
0
4
2
0
2
12
3
3
2
18
Profit per batch
$3,000
$5,000
Introduction-18
Peeking into Chapter 3
Formulate LP Model
• Identify the parameters
(activities/values you cannot control)
• Identify the decision variables
(activities/values that you can control and need to make a decision on)
• Identify the objective function
(function of the decision variables for minimization/maximization)
• Identify the constraints
(limitations you cannot control)
Introduction-19
Peeking into Chapter 3
Graphical Solution Setup
• The model:
Introduction-20
Prototype Example
Graphical Solution
• The model:
Introduction-21
LP Modeling
• Wyndor Glass Co. is only one of a vast number of
applications that LP can be used to address
• In general, the most common type of an LP addresses:
The allocation of limited resources to competing activities
for maximizing the value of these activities
Introduction-22
LP Terminology
•
•
•
•
•
The allocation of limited resources to competing
activities
for maximizing the value of these activities
Activities, n
Resources, m
Decision variables – or level of activities, x
Objective function – or value of activities, Z
Constraints
– functional
– non-negativity
Introduction-23
LP Terminology
•
•
•
•
•
Feasible region, feasible solution
Infeasible solution
Optimal solution
Extreme-point – or corner-point feasible solutions
Parameters
Introduction-24
Standard (Canonical) Form of an LP Model
c1x1
+ c2x2 + … + cnxn
Maximize
Z =
subject to
a11x1 + a12x2
a21x1 + a22x2
…
am1x1 + am2x2
+ … + a1nxn ≤ b1
+ … + a2nxn ≤ b2
+ … + amnxn ≤ bm
x1 ≥ 0, x2 ≥ 0, …, xn ≥ 0
Introduction-25
Matrix Form of an LP Model
Introduction-26
Other Forms that can be Converted into
Standard Form
• Objective function:
Minimize Z=cx
(instead of Maximize Z=cx)
• Functional constraints:
Ax ≥ b or Ax = b
(instead of Ax ≤ b)
• Non-negativity constraints:
x unrestricted in sign
(instead of x ≥ 0)
Introduction-27
Assumptions of Linear Programming
• Proportionality
• Additivity
• Divisibility
• Certainty
Introduction-28
LP Modeling Examples
Introduction-29
A Transportation Example
• A company has 2 plants and 3 warehouses
• Supply at plants
100 units in Plant 1, 200 units in Plant 2
• Sales potential at warehouses
150 units, 200 units, and 350 units at Warehouses 1, 2 and 3, respectively
• Revenue
12 $/unit, 14 $/unit and 15 $/unit at Warehouses 1, 2 and 3, respectively
• Cost of manufacturing
one unit at plant i
and shipping to w/h j:
Warehouse
Plant
1
2
3
1
8
10
12
2
7
9
11
• How many units to ship from each plant to each w/h to maximize
profits?
Introduction-30
Introduction-31
Personnel Scheduling (p.56)
• Union Airways is adding more flights and needs to hire
additional customer service agents
• Each agent works an eight-hour shift
• The five possible shifts are
–
–
–
–
–
Shift 1: 6:00 am – 2:00 pm
Shift 2: 8:00 am – 4:00 pm
Shift 3: Noon – 8:00 pm
Shift 4: 4:00 pm – Midnight
Shift 5: 10:00 pm – 6:00 am
Introduction-32
Personnel Scheduling
Minimum number of agents needed per two-hour time periods:
Time periods covered
Time period
Minimum number of
agents needed
Shift
1
2
3
4
5
6:00 am – 8:00 am

8:00 am – 10:00 am


79
10:00 am – noon


65
Noon – 2:00 pm



87


64
2:00 pm – 4:00 pm
48
4:00 pm – 6:00 pm


73
6:00 pm – 8:00 pm


82
8:00 pm – 10:00 pm

43
10:00 pm – midnight

Midnight – 6:00 am
Daily cost per agent
$170
$160
$175
$180

52

15
$195
Introduction-33
Introduction-34
Reclaiming Solid Wastes (p.52)
• A recycling center takes four types of material
–
–
–
–
Material 1: Newsprint
Material 2: White paper
Material 3: Mixed paper
Material 4: Cardboard
• Three products are reclaimed
– Grades A, B, C
• The SAVE-IT company wants to determine the amount of
each grade to produce and the mix of materials in each
grade to maximize profit
Introduction-35
Reclaiming Solid Wastes
• Products
Grade
Specification
Amalgamation
Cost per lb ($)
Selling Price
per lb ($)
A
Mat’l 1: Not more than 30% of total
Mat’l 2: Not less than 40% of total
Mat’l 3: Not more than 50% of total
Mat’l 4: Exactly 20% of total
3.00
8.50
B
Mat’l 1: Not more than 50% of total
Mat’l 2: Not less than 10% of total
Mat’l 4: Exactly 10% of total
2.50
7.00
C
Mat’l 1: Not more than 70% of total
2.00
5.50
• Solid waste materials
Mat’
l
lbs per week
available
Treatment cost per lb
($)
1
3,000
3.00
2
2,000
6.00
3
4,000
4.00
4
1,000
5.00
• Use at least half of each material collected
• Cannot use more than $30,000 per week for treatment of mat’ls
Introduction-36
Introduction-37