Optimização E Decisão: Program

OPTIMIZAO E DECISO
Joo Miguel da Costa Sousa

Technical University of Lisbon, Instituto Superior Tcnico
Dep. of Mechanical Engineering, Center of Intelligent Systems/IDMEC
1049-001 Lisboa, Portugal, E- mail: jmsousa@ist.utl.pt,
http://www.dem.ist.utl.pt/~jsousa
Program
Introduction to optimization. Operations Research
Linear Programming: Simplex. Sensitivity Analysis.
Transportation and Assignment Problems
Dynamic Programming
Integer Programming
Nonlinear Programming. Quadratic Programming.
Convex Programming.
7. Metaheuristics. Tabu search, Simulated Annealing,
Genetic Algorithms, Ant Colony Optimization.
8. Game Theory
9. Decision Analysis. Decision Trees. Utility Theory.
1.
2.
3.
4.
5.
6.
Bibliography
F. Hillier and G. Lieberman. Introduction to Operations
Research, 8th Edition. McGrawHill, 2005.
http://highered.mcgraw-hill.com/sites/0073017795/information_center_view0/
J. Kennedy, R. C. Eberhart and Y. Shi. Swarm Intelligence.

Morgan Kaufmann Publishers, 2002.
Marco Dorigo and Thomas Sttzle. Ant Colony
Optimization. The MIT Press. July 2004.
R. Fletcher. Practical Methods of Optimization, 2nd Edition,
John Wiley, 2000.
J. Nocedal and S.Wright. Numerical Optimization. Springer,
1999.
Michael Pinedo. Scheduling. Theory, Algorithms and
Systems, 2nd Edition, Prentice Hall, 2002.
3
Evaluation method
Exam (minimum grade: 9.5/20)
Project (minimum grade: 9.5/20)
project assignment: November
project deadline: December
oral presentation: between last week of lectures
Final Grade = 0.7*Exam + 0.3*Project
INTRODUCTION
Origins of Operations Research

As the complexity and specialization in an organization
increase, it becomes more and more difficult to
allocate available resources to the various activities in
a way that is most effective for the organization as a
whole.
This kind of problems and the need to find a why to
solve them provided the environment for the
emergence of operations research (OR).
Roots of operations research

Military services early in World War II.
Urgent need to allocate scarce resources to operations
and activities in an effective manner.
Scientists were asked to do research on (military)
operations.
Examples:
Effective methods of using radars to win the Air Battle of
Britain.
Better management of convoy and antisubmarine
operations to win the Battle of North Atlantic.
After WW II, it became apparent that problems caused

by increasing complexity and specialization in
organizations required the same tools.
7
Roots of operations research

Two main factors for rapid growth of OR:
1. Large progress in improving the OR techniques during
the war.
An example is the development of the simplex method (G.
Dantzig, 1947) for solving linear programming problems.
Many standard OR tools were developed before the 50s.
2. The computer revolution: a large amount of
computation is required to deal with OR problems.

During the 80s, the PC and related OR software
brought the use of OR to a much larger number of
people. Today
8
Nature of operations research

OR is applied to conduct and coordinate operations
(i.e., the activities) within an organization.
Applied to many areas: manufacturing, transportation,
construction, telecommunications, financial planning,
health care, military, public services, etc, etc.
OR uses techniques resembling the way research is

conducted in many scientific fields.
Formulate the problem, including gathering data;
construct model; conduct experiments; validate model.
OR is also concerned with management and decision
making.
9
Nature of operations research

OR attempts to find a best (optimal) solution; search
for optimality is an important theme in OR.
As OR requires many and broad aspects, it is usually
necessary to use a team approach, including areas
such as:
mathematics, statistics and probability theory,
economics, business administration, computer science,
engineering and physical sciences, behavioral sciences
and the special techniques of OR.
10
Impact of operations research

Improvement of efficiency in numerous organizations
around the world, and improving economy.
IFORS (International Federation of Operations
Research Societies) and INFORMS (Institute for
Operations Research and the Management Sciences).
INFORMS has many journals, including Interfaces.
Next table present some examples of award-winning
applications reported in Interfaces (to see more details
see page 4 of Hilliers book).
11
Impact of operations research

Organization
Application
Year of pub.
Annual savings
The Netherlands
Rijkwaterstaat
Develop national water management

policy, including mix facilities,
operating procedures and pricing.
1985
$15 million
Citgo Petroleum
Corporation
Optimize refinery operations, supply,

distribution and marketing of
products.
1987
$70 million
San Francisco
Police Dept.
Optimally schedule and deploy police

patrol officers.
1989
$11 million
China
Optimally select and schedule

massive projects for meeting the
countrys future energy needs.
1995
$425 million
Samsung
Electronics
Develop methods of reducing manufacturing times and inventory levels.
2001
$200 million
more revenue
Continental
Airlines
Optimize reassignment of crews to

flights when a disruption occurs.
2003
$40 million
12
Algorithms and Courseware

Algorithm a systematic solution procedure for
solving a particular type of problem.
OR Courseware of Hilliers book and CD-ROM.
OR Tutor teach the algorithms
IOR Tutorial (implemented in Java)
Excel Solver or Premium Solver for Education
LINDO and modeling language LINGO
CPLEX and modeling system MPL elite state-of-the-art
software package for large and challenging OR
problems.
Later, we will use MATLAB with GA, ACO, etc.

13
OPERATIONS RESEARCH
MODELING APPROACH
Phases of an OR study
1. Define the problem and gather relevant data.
2. Formulate a mathematical model for the problem.
3. Develop a computer algorithm for deriving solutions
to the problem from the model.

4. Test the model and refine it as needed.
5. Prepare the ongoing application of the model as
prescribed by management.
6. Implement.
Usually some cycles are necessary.
15
1. Defining the problem

Practical problems are initially described in a vague,
imprecise way.
OR teams work in an advisory capacity: they dont
only solve the problem, they also advise management.
Be completely sure about the appropriate objectives
(together with the management) is an important
aspect.
Objectives should be as specific as possible, but
consistent with high-level objectives of the
organization.
16
Defining the problem

For profit making organizations, objective can be the
long-run profit maximization (including R&D).
In practice, this is not enough, and must be combined
with other objectives, such as: improve worker morale
or increase company prestige.
Five parties affected by a firm: owners, employees,
customers, suppliers and government (nation).
Besides making profit, a company has broader social
responsibilities that must also be recognized.
17
Gathering relevant data

Data is needed to understand the problem and as
input for the mathematical model.
Often it is necessary to install a management
information system to deal with the necessary data.
Much of the data is quite soft (rough estimates).
Biggest data problem: too many data is available
(gigabytes or terabytes).
Data mining is often required to deal with the data.
18
Example: Police Department

Recall the San Francisco PD problem.
New system provided annual savings of $11 million,
annual increase of $3 million in traffic citation
revenues, and 20% improvement of response times.
Appropriate objectives found for this study:
1. Maintain a high level of citizen safety (establish
desired level of protection).

2. Maintain a high level of officer morale (balance
workload equitable amongst officers).
3. Maintain the cost of operation (minimizing number of
officers to satisfy objectives 1 and 2).
19
2. Formulating a model
Mathematical models are idealized representations.
Decision variables: x1, x2,, xn.
Objective (cost) function: J = f (x1, x2,, xn).
Constraints: example; x1 + 3x2 x1 x5 20
Constants in the objective function and constraints are
called parameters.
Determining values for the parameters is crucial. These
values are based on data and can be uncertain.
Thus, a sensitivity analysis is necessary.
20
10
Formulating a model
Linear programming model is often used. It can be
applied to very different problems.
Models are an abstract idealization of the problem.
Models must be tractable (capable of being solved).
To assure high correlation between predictions of the
model and real world data, testing and model
validation must be performed.
Measure of performance combining the multiple
objectives is needed.
21
3. Deriving solutions from the model

Develop a (computer-based) procedure for deriving
solutions to the problem from the model.
Sometimes, one of the standard algorithms is applied
using readily available software packages.
Search for an optimal (best) solution for the model.
Herbert Simon (Nobel Laureate) points out that
satisficing (= satisfactory and optimizing) is much
more prevalent than optimizing in practice.
22
11
Deriving solutions
OR seeks for optimal solutions, but time or cost
restrictions may demand for heuristic procedures to
find good suboptimal solutions.
Recently, efficient and effective metaheuristics have
been developed for designing heuristics for particular
types of problems.
One solution is commonly not enough, so postoptimal
analysis is needed to find alternative solutions.
Postoptimal analysis demands for sensitivity analysis.
23
Sensitivity analysis
Sensitive parameter:
For a mathematical model with specified values for all
its parameters, the models sensitive parameters are
the parameters whose value cannot be changed
without changing the optimal solution.
Postoptimality analysis involves obtaining several

solutions that contain improved approximations.
This cycle is repeated until the improvements in the
succeeding solutions become too small to warrant
continuation.
24
12
4. Testing the model

Developing a large mathematical model is analogous to
developing a large computer program:
First version of computer program contain many bugs
that are corrected by thoroughly testing the program.
First version of mathematical program contain many
flaws and some parameters have not been estimated
correctly.
Small bugs can remain in the program or model.
This process of testing and improving a model is known

as model validation.
Revision of a complete model must include an outsider.
25
Examples
In the Netherlands Rijkwaterstaat study model
validation had three main parts:
Checking results of the 50 models for changes in
parameters.
Retrospective tests (use of historical data to
reconstruct the past) were done.
Careful technical review of model, methodology and
results by experts unaffiliated with the project.
In the Citgo Petroleum Corporation study, model of

refinery operations was tested using input and output
data for a series of months to fix the model inputs.
26
13
5. Preparing to apply the model

When model is ready, install a well documented
system for applying it as prescribed by management.
Inputs for the model can be obtained from databases
or information systems.
If interactivity is needed, a decision support system is
installed to help managers in their decision making.
DSS can take months (or longer) to be implemented.
Example: Continental Airlines developed the decision
support system CrewSolver, (it was running on
September 11, 2001).
27
6. Implementation
Phases:
OR team gives management an explanation of the system.
These two parties share the responsibility for developing
procedures to put the system in operation.
Personal involved is indoctrinated, and system is initiated.
Feedback when system is in use is essential to evaluate

model.
Documentation is crucial to ensure reproducibility.
Crucial for studies of controversial public policies.
Example: studies for localization of future Lisbon
airport.
28
14
Discussion
This discipline focuses on constructing and solving
mathematical models, but these are only part of the
overall process of an optimization study.
Optimization is deeply intertwined with the use of
computers.
There are many exceptions to the rules prescribed:
OR requires considerable ingenuity and innovation.
29
15

Optimização E Decisão: Program

Uploaded by

Copyright:

Available Formats

Optimização E Decisão: Program

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Optimização E Decisão: Program

Uploaded by

Copyright:

Available Formats

OPTIMIZAO E DECISO

Joo Miguel da Costa Sousa

J. Kennedy, R. C. Eberhart and Y. Shi. Swarm Intelligence.

Final Grade = 0.7*Exam + 0.3*Project

Origins of Operations Research

Roots of operations research

After WW II, it became apparent that problems caused

Roots of operations research

2. The computer revolution: a large amount of

computation is required to deal with OR problems.

Nature of operations research

OR uses techniques resembling the way research is

Nature of operations research

Impact of operations research

Impact of operations research

Develop national water management

Optimize refinery operations, supply,

Optimally schedule and deploy police

Optimally select and schedule

Develop methods of reducing manufacturing times and inventory levels.

Optimize reassignment of crews to

Algorithms and Courseware

Later, we will use MATLAB with GA, ACO, etc.

to the problem from the model.

1. Defining the problem

Defining the problem

Gathering relevant data

Example: Police Department

desired level of protection).

3. Deriving solutions from the model

Postoptimality analysis involves obtaining several

4. Testing the model

This process of testing and improving a model is known

In the Citgo Petroleum Corporation study, model of

5. Preparing to apply the model

Feedback when system is in use is essential to evaluate

You might also like

Final Grade = 0.7Exam + 0.3Project