Transcript Linear Programming (Optimization)

Operations Research - 1
Spring 2010
OR-1 2010
Origins of OR
 Contributions of scientists and engineers during world war II.
Air war in France, Battle of Britain (radar site selection and control),
Submarine warfare, Design of B-29, ..
 Air war in France(1939): requests for 10 fighter squadron (120),
losses 3 squadrons/2 days.  retreat of fighters from France.
 Battle of Britain: integration of radar(hardware) and warning and
control system. Addition of radar sites causes problems.
(the name operational research (research in (military) operations)
 Maintenance of aircraft: For 350 flying hours, need 7 minor
inspections( 2-5 days each) and a major inspection (14 days). Each
aircraft had a devoted aircrew and a ground crew
 change to central garage system.
: Flying hour increased by 61% over previous best record.
OR-1 2010
2
 Submarine warfare:
Needed 170 man-hours by maintenance and ground staff to
produce one hour of operational flying.
More than 200 hours of flying to produce one attack on a surfaced
U-boat. (34,000 man-hours for an attack)
In 1941, attack kill probability was 2% - 3%
 1.1M  1.7M man-hours needed to destroy one U-boat.
(needed improvements)
 Important decision variables:
1.
2.
3.
4.
5.
6.
Depth (time) setting for depth charge explosion
Lethal radius
Aiming errors in dropping the stick
Orientation of the stick with respect to the U-boat
Spacing between successive depth charges in the stick
Low level bombsights
OR-1 2010
3
1. Originally set 30/45 meters. Pilot reports showed, at time of
attack, the U-boat still visible or submerged less than 15 seconds
in 40% of attacks. Lethal radius of depth charge was around 5-6
meters.
: Use shallower setting. 15m -> 10m (new fuses) ->
8m
2. 250lb(110Kg) depth charges used: change to 600lb(270 Kg)(Air
staff) or 100lb(45Kg)(ORS) charges?
3. “aiming off” (aiming ahead): analysis showed 50% more kills
without aiming off.
4. Attack along U-boat track.
5. Initially set 12m. ORS calculated 33m would increase kills by
35%.
6. Pilot acted also as bomb aimer/release. -> recommended low
level bombsight. 1943, increase kills per attack by 35%
 Overall effect: By 1945, the attack kill probability had risen to over
40%.
OR-1 2010
4
 After the war, methodologies used by the scientists adopted by
government, industry.
Called Operations Research (US), Operational Research(UK, Europe) (운용
과학), Management Science (경영과학)
 Characteristics: Use of mathematical models to solve decision problems
arising in management of industry, government, military, ….
E=mC2, F=ma, …
OR-1 2010
5
Nature of OR
 “research on operations”
Applied mathematics + computer science + management
 Models : Deterministic models (확정적 모형, OR-I)
Stochastic models (확률적 모형, OR-II)
 Needed background: Algebra, calculus, discrete mathematics,
probability, statistics, data structure, algorithm, data base, programming
skills, …)
 Important thrusts in early stages
1. Technical progress (Simplex method for linear programming, Dantzig,
1947)
2. Invention of computer and PC
OR-1 2010
6
Study areas
 Deterministic models
Linear programming(선형계획법, linear optimization):1975, Nobel prize,
Kantorovich, Koopmans (efficient allocation of resources)
min x1  2 x2
3x1  2 x2  10
x1  2 x2  3
x1  0, x2  0
Nonlinear programming(비선형계획법):1990 Nobel prize, Markowitz
(portfolio selection)
max x1x2 x3
2 x1x2  2 x2 x3  2 x1x3  a
x1  0, x2  0, x3  0
OR-1 2010
7
Integer Programming(정수계획법), Combinatorial optimization (조합최적화)
• Knapsack problem
max x1  2 x2  5x3  3x4
2 x1  6 x2  3x3  2 x4  6
xi {0,1} for all i
• Traveling Salesman Problem (외판원문제)
Given n cities, and distances cij between city i and j. What is the shortest
sequence to visit each city exactly once and return to the starting city?
( Applications: PCB assembly, Off-shore drilling, vehicle routing
(delivery/pick-up problem), bio, …)
web site: http://www.tsp.gatech.edu/
OR-1 2010
8
Networks and graphs
Inchon
Seoul
Kangnung
Daejeon
Daegu
Kwangju
Pusan
• Shortest path to move from Inchon to Kangnung? (Shortest path
problem)
– Logistics, Telecommunication routing, …
• Connect the cities with roads (or communication lines) in a cheapest
way. (Minimum spanning tree problem)
• How much commodities (or packets) can we send from Kangju to Daegu
if edges have limited capacities? (maximum flow problem)
OR-1 2010
9
Dynamic programming
• If a system changes in time and the status of the system in the next
period depends on the current status and decisions made, what is the
best decision in each stage to optimize our goal in the end?
• Not the formalized problems, but refer the structured steps used to
solve problems involving many stages.
Game theory
• Investigate the best strategy when the outcome of cooperation and/or
competition between people or groups depends on the collective
decisions made by individual person/group.
• Economics, Marketing (1994, Nobel prize, Nash, Harsanyi, Selten)
OR-1 2010
10
 Computational complexity: Theory that investigate the inherent difficulty of
problems. Turing machine model of computation.
NP-completeness.
• NP-complete (NP-hard) problems: Knapsack problem, Traveling salesman
problem, …
• Easily solvable problems: shortest path problem, minimum spanning tree
problem, …
– Problems for which polynomial running time algorithms exist.
• A little bit of changes in the problem structure may make the problem hard.
– Minimum spanning tree problem vs. Steiner tree problem
• Useful tool when we try to solve some new problems.
 Note that the basic models may appear as subproblems in a big problem. Also
the models may be hidden in the real problem in some unexpected way.
Identifying the hidden model may be crucial.
OR-1 2010
11
 Stochastic models (OR-II)
Markov chain
Queueing theory
Decision analysis
Simulation
Reliability
OR-1 2010
12
Steps of OR approaches
1. Identifying the problem (problem may be vague, find appropriate
objective (there frequently exist multiple objectives))
2. Construct a (math) model and data acquisition.
Find model appropriate for objective.
3. Deriving a solution (optimal or good enough solution)
(Note that finding a good enough solution can be a serious challenge.
e.g. air line crew scheduling problem, steel company, ship building, …)
4. Test the model and the solution.
5. Establishing control over the solution (documentation, maintenance)
6. Implementation
OR-1 2010
13
Some Application areas of optimization
Manufacturing, production
• Scheduling, production • Circuit design
• Facility layout
• Refinery, Energy
• Process control
…
Logistics
• Distribution network
• Center location
• Transportation plan
• Vehicle routing
• Worker Sched
…
Telecommunication
• Network design
• Traffic routing
• Base station location
• Power control
…
Service, Engineering
• Plane scheduling
• Water resource
• Crew scheduling
• Engineering optimiz
• Medical, Bioinformatics • Financial Eng.
…
OR-1 2010
14