Badania Operacyjne GB w1 (PDF)

Badania operacyjne i teoria optymalizacji
Grzegorz Bocewicz

Literatura

Badania operacyjne i teoria optymalizacji
G. Bocewicz

2

Literatura

Badania operacyjne i teoria optymalizacji
G. Bocewicz

3

Literatura

Badania operacyjne i teoria optymalizacji
G. Bocewicz

4

Sytuacja decyzyjna
Blackett's OR group Convoy Problem
How to organize and protect convoys in the most effective way?
1.
2.
3.
4.

How many escort ships should be provided to a convoy?
How big should a convoy be?
How fast should a convoy travel?
How much air cover should b e given to each convoy and how should it be
deployed?
ryzyko zatonięcia
r=2,5%

ryzyko zatonięcia
r=1,1%

Badania operacyjne i teoria optymalizacji
G. Bocewicz

5

Rys historyczny
II Wojna Światowa

Bawdsey Research Station (Anglia, 1939)
Pierwszy na świecie ośrodek zajmujący się badaniami operacyjnymi w związku z wprowadzeniem na
uzbrojenie wojsk angielskich pierwszych stacji radiolokacyjnych.
„Cyrk Blacketta” (Anglia, 1940)
Grupa składająca się z 3 fizjologów, 3 fizyków, 2 matematyków, astronoma i oficera powstała przy
dowództwie obrony przeciwlotniczej Anglii.
1937 Brytyjczycy po raz pierwszy używają określenia badania operacyjne w kontekście planowania
operacji wojskowych
1939 “Mathematical Methods of Organization and Production,” L. Kantorovich
1941 Model przepływów międzygałęziowych, W. W. Leontief
1941 Problem transportowy, F. Hitchcock
1942 Badania operacyjne w Bitwie o Anglie, P. Blackett
1943 Sieci neuronowe, W. McCulloch, W. Pitts
1944 Teoria gier, J. von Neumann, O. Morgenstern
….

Badania operacyjne i teoria optymalizacji
G. Bocewicz

6

Rys historyczny
Po II Wojnie Światowej
1947 Model programowania liniowego i metoda sympleks, G. B. Dantzig
1949 Metoda Monte Carlo, S. M. Ulam, J. von Neumann
1950 Równowaga Nasha, J. Nash
1950 Komputer rozwiązuje problem transportowy (SEAC)
1950 Programowanie dynamiczne, R. Bellman
1954 Szeregowanie żądań, S. Johnson
1955 Problem komiwojażera, M. Flood
1955 Metoda Węgierska, H. Kuhn, E. Egerv´ary
1956 PERT/CPM/MPM, J. Kelley, Jr., W. Walker/D. Malcolm, J. Roseboom, C. Clark, W. Fazar/B. Roy
1957 Programowanie dynamiczne, R. Bellman
1962 Przepływy w sieciach, L. Ford, Jr., D. Fulkerson
1965 Teoria złożoności obliczeniowej; pojecie NP-zupełnosci, J. Edmonds, R. Karp
1971 Złożoność obliczeniowa, S. A. Cook, R. Karp
1972 Dowód, że sympleks nie jest algorytmem wielomianowym, V.Klee and G. J. Minty
1975 Wielokryterialne podejmowanie decyzji, M. Zeleny, S. Zionts, J. Wallenius, W. Edwards, B. Roy
1979 Metoda elipsoid, L. Khachian
1980 Constraint Programming
1982 Symulowane wyżarzanie, W. Metropolis
1989 Przeszukiwanie tabu, F. Glover
1990 Algorytmy ewolucyjne
1995 Eksploracja danych
…
Badania operacyjne i teoria optymalizacji
G. Bocewicz

7

Dziedziny zastosowań
• ekonomia
• logistyka

• produkcja
• medycyna
• informatyka

• sport
• polityka
• ...

Badania operacyjne i teoria optymalizacji
G. Bocewicz

8

Badania operacyjne + teoria optymalizacji

Badania operacyjne (operations research) to nazwa
dyscypliny, zajmującej się teorią podejmowania decyzji. Jest to
zbiór metod matematycznych i statystycznych, pozwalających
wyznaczyć metodę i rozwiązanie określonych problemów
związanych z podjęciem optymalnych decyzji.

Teoria optymalizacji zajmuje sie badaniem metod
optymalizacji rozumianej jako wyznaczenie spośród rozwiązań
dopuszczalnych danego problemu rozwiązania najlepszego ze
względu na przyjęte kryterium.
Dyskretna
MAX

Badania operacyjne (operations research)
są nauką
systemową, czyli nauką o sterowaniu złożonymi systemami,
które mogą być fragmentami rzeczywistości fizycznej i/lub ich
modelami. Badania operacyjne, jako naukę systemowa
definiuję się przez określenie klasy systemów, którymi się ona
zajmuje. Są to systemy typu kompleks operacji. [J. Józefowska]

MIN
Ciągła

Badania operacyjne są to zastosowania matematyki do
rozwiązywania problemów.

Badania operacyjne i teoria optymalizacji
G. Bocewicz

9