pbo.pdf

(3130 KB) Pobierz
88121071 UNPDF
Przewodnik po Badaniach Operacyjnych
dla ekipy z LZK
jawnych członków i tajnych agentów
Strona 1 z 153
Przewodnik po Badaniach Operacyjnych
Jacek Małyszko: Przewodnik po Badaniach Operacyjnych
Opracowanie materiału z zajęć z doktorem Piotrem Maćkowiakiem
na Wydziale Informatyki i Gospodarki Elektronicznej na Akademii Ekonomicznej w Poznaniu.
Spis treści
Przedmowy słów kilka, których nie da się uniknąć na początku żadnej książki i których strasznie
nie chce mi się pisać, dobrze jednak będzie jeśli je przeczytasz..........................................................4
1. Podstawy i trochę teorii ...................................................................................................................6
1.1. Czym będziemy się właściwie zajmować?...............................................................................6
1.2. Zmatematyzujmy sobie sytuację...............................................................................................6
1.3. Układ równań liniowych tudzież zbiór warunków ograniczających........................................9
1.4. Jak wyznaczyć wartość zmiennych bazowych?.....................................................................11
1.5. Funkcja celu- druga z przyczyn naszych przyszłych problemów...........................................13
1.6. Sprawdzamy optymalność!.....................................................................................................14
1.7. Zwiększamy zmienne niebazowe- jak to robić? ....................................................................15
1.8. Długość kroku- jak daleko możemy pójść, żeby nie wdepnąć w G?..................................... 16
2. Ruszamy z zadaniami!....................................................................................................................18
2.1. Normalizacja. .........................................................................................................................18
2.2. Interpretacja geometryczna.....................................................................................................19
2.3. Tablica sympleksowa..............................................................................................................20
2.4. Mam nadzieję, że umiesz obsługiwać Excela...? - sympleks w arkuszu kalkulacyjnym.......27
2.5. Metoda operacji elementarnych, czyli to, co prawdopodobnie będziesz mieć na kolokwium.
.......................................................................................................................................................32
2.6. Dwa słowa o dwóch wymiarach- metoda graficzna (czyli na koniec ta najprostsza)............37
2.7. Metoda dwufazowa, czyli czemu, do cholery, nie mogę wziąć pierwszych zmiennych z
brzegu?!?........................................................................................................................................39
2.8. Na czym więc polega ta metoda?........................................................................................... 40
3. Modele, niestety............................................................................................................................. 44
Brakujące rozdziały:...........................................................................................................................54
4. Dualność.........................................................................................................................................54
5. Analiza wrażliwości.......................................................................................................................54
6. Algorytm sympleks z ograniczeniami na zmienne.........................................................................54
7. Programowanie binarne..................................................................................................................55
7.1. Przegląd pośredni....................................................................................................................55
7.1.2. Normalizacja........................................................................................................................55
7.1.4.Rozwiązanie..........................................................................................................................56
7.1.5. Komentarze..........................................................................................................................63
8. Programowanie całkowitoliczbowe................................................................................................67
8.1. Metoda podziału i ograniczeń.................................................................................................67
8.2. Metoda płaszczyzn tnących Gomory'ego...............................................................................72
8.2.1. Liczba= podłoga plus mantysa............................................................................................72
8.2.2. Wyprowadzenie metody......................................................................................................74
8.2.3. Jak to się liczy- przykład z Gomory'ego..............................................................................77
9. Zagadnienia transportowe.............................................................................................................. 82
9.1. Pierwszy rzut oka....................................................................................................................82
9.2. Budujemy model.....................................................................................................................83
Strona 2 z 153
Przewodnik po Badaniach Operacyjnych
9.3. Wyznaczanie dopuszczalnego rozwiązania bazowego- metoda kąta północno-zachodniego.
.......................................................................................................................................................84
9.4. xroot, czyli nie może być za łatwo i zbyt zrozumiale bo by było nudno. Tylko się nie
zniechęcaj!.....................................................................................................................................85
9.5. Teraz będzie bardziej zrozumiałe- jak to zapisywać, czyli tablica algorytmu transportowego
.......................................................................................................................................................87
9.6. Zadanie niezbilansowane........................................................................................................93
9.7. Inne metody wyznaczania bazowego dopuszczalnego..........................................................94
9.8. Trasy niedopuszczalne..........................................................................................................100
10. Zagadnienie przydziału.............................................................................................................. 102
10.1. Znowu nas męczą................................................................................................................102
10.2. Model zadania na optymalny przydział, czyli podpunkty a) - c)........................................103
10.3. Algorytm węgierski............................................................................................................105
11. Programowanie sieciowe............................................................................................................112
11.1.Wstęp do teorii grafów. ...................................................................................................... 112
11.2. Graf i sieć- podstawowe pojęcia i objaśnienia....................................................................113
11.3. No to weźmy się wreszcie do cholery za jakiś przykład!!!................................................113
11.3.1. Zacznijmy od analizy treści zadania................................................................................114
11.3.2. Spróbujmy zapisać to matematycznym językiem, czyli sformułowanie zadania............115
11.3.3. No to może na początek jakieś rozwiązanie dopuszczalne czy coś?...............................115
11.3.4. ... 3,14. Dokładniej p. Czyli liczymy potencjały!............................................................117
11.3.5. Cezdaszkiem....................................................................................................................118
11.3.6. Trasa wycieczki...............................................................................................................120
11.3.7. No i mamy nowe drzewo rozpinające!!! Kończmy więc z tym...................................... 121
12. Programowanie sieciowe część 2...............................................................................................123
Wstęp ...............................................................................................................................................123
12.1. Zadanie niezbilansowane....................................................................................................123
12.2. Znajdowanie początkowego dopuszczalnego drzewa rozpinającego.................................125
12.3. Problem sieciowy z ograniczoną przepustowością tras......................................................127
12.4. Metoda dwufazowa w zadaniu z ograniczeniami na zmienne............................................135
13. Wstęp do programowania nieliniowego cz. 1............................................................................136
13.1. Programowanie nieliniowe- что это?.................................................................................136
13.2. Na dobry początek- prosty przykład z podstawowymi definicjami................................... 137
13.3. Jeszcze jeden przykład........................................................................................................141
13.4. Wypływamy na głęboką wodę............................................................................................141
Wstawka epistolarna:...................................................................................................................143
14. Wstęp do programowania nieliniowego część 2........................................................................144
14.1. Optymalizacja warunkowa................................................................................................. 144
14.3. Zabierzmy się teraz za konkretny już przykład znajdowania ekstremum warunkowego...146
14.4. Zadanie ostatnieeee!!! Jessssssssssssssss!!!!!.....................................................................153
Strona 3 z 153
Przewodnik po Badaniach Operacyjnych
Przedmowy słów kilka, których nie da się uniknąć na początku żadnej
książki i których strasznie nie chce mi się pisać, dobrze jednak będzie
jeśli je przeczytasz.
Oto masz przed sobą Coś zatytułowane „Przewodnik po Badaniach Operacyjnych”.
Znalazłeś to Coś prawdopodobnie w internecie, szukając materiałów na Twój Niekoniecznie
Ulubiony Przedmiot, i teraz zastanawiasz się pewnie, skąd też w sieci znalazł się za darmo 150
stronicowy podręcznik.
No więc historia powstania tego Czegoś jest taka: w roku akademickim 2006/07 na
drugim roku na wydziale Informatyki i Gospodarki Elektronicznej Akademii Ekonomicznej w
Poznaniu pewien student usiadł sobie pewnego jesiennego wieczoru i stwierdził, że trzeba się brać
do roboty. Zrobił sobie herbaty, włączył komputer i całą noc siedział nad badaniami operacyjnymi,
z których właśnie zbliżało się pierwsze kolokwium (zajęcia prowadzone były przez doktora Piotra
Maćkowiaka), starając się zapisać strzępki wiedzy jakie posiadał jakimś zrozumiałym językiem i
ułożyć sobie to wszystko w głowie. Ponieważ jesienne noce do krótkich nie należą, przez ten czas
zrozumiał i plus minus zrozumiale opisał podstawy algorytmu sympleks, a to opracowanie
zamieścił na forum internetowym swojej grupy dziekańskiej.
Dobra, koniec pisania o sobie w trzeciej osobie. Tym studentem był oczywiście nikt
inny jak tylko ja. Tak czy siak, ponieważ stwierdziłem, że kurde całkiem fajnie jest tak sobie pisać,
a na dodatek sporo osób stwierdziło, że na prawdę im to opracowanie pomogło, postanowiłem
przygotować materiał na całe kolokwium. Kolokwium poszło zarówno mi, jak i osobom uczącym
się z tych opracowań całkiem nieźle, więc postanowiłem pisać dalej.
I tak pisząc powolutku z pewnymi przerwami opracowałem prawie cały materiał.
Zamieszczałem go na własnej stronie WWW, a liczniki wejść przed trzecim i czwartym kolokwium
przez trzy dni nabijały w sumie po 500 wejść. Gdy drugi rok się więc skończył, a ja nie miałem
żadnych poprawek i morze czasu w wakacje, zachęcony takim zainteresowaniem postanowiłem
przez dwa miesiące popracować nad tym materiałem i zrobić z niego coś w stylu jednolitego
podręcznika. Efekt tej mojej pracy masz właśnie przed sobą.
Historię powstania tego Czegoś już więc znasz, a teraz druga sprawa- jakie wyciągnąć z
tej historii wnioski? Teraz trochę Cię postraszę.
Po pierwsze, wszystko to jest napisane przez studenta, a jedynymi tego recenzentami
byli inni studenci. Choć nie, chwila- doktor Maćkowiak, po odwiedzeniu mojej strony i obejrzeniu
opracowań stwierdził coś w stylu, że jest to „obrazoburcze” czy „niemoralne”, ale „skoro to jest
pomocne dla studentów, to wszystko w porządku”. Choć od tego czasu podręcznik zdecydowanie
zmienił swoją postać, to słowa te ciągle dobrze go charakteryzują- podstawowym celem, który
przyświecał mi przy pisaniu tego Czegoś, było przedstawienie materiału w sposób
bezstresowy, przyjemny do czytania, i łatwy do zrozumienia , i obawiam się, że osoby
oczekujące pozycji pisanej naukowym językiem nie mają, niestety, za bardzo czego tu szukać. Z
podanych powyżej powodów wynika kolejna cecha tego podręcznika: pisałem go jako jedynie
jedno z kilku źródeł, z którego czytelnik będzie się uczył. Nie ma w nim zawartej wiedzy od A do
Z. Co więcej, nie gwarantuję w 100% poprawności zawartego w nim materiału (choć dołożyłem
wszelkich starań, aby nie było żadnych błędów ani nieścisłości), i nie odpowiadam za ewentualne
błędy na kolokwiach spowodowane nauczeniem się materiału z tego przewodnika, który z jakiegoś
Strona 4 z 153
Przewodnik po Badaniach Operacyjnych
powodu okazałby się błędny. W kilku miejscach pozostawiłem również kwestie niewyjaśnione,
których sam nie jestem pewien. Nie uważam tego za wadę tego podręcznika- odnalezienie bowiem
miejsca, którego możesz nie rozumieć, i postawienie odpowiedniego pytania może również okazać
się pomocne podczas nauki. Na koniec najpoważniejszy problem- brak trzech rozdziałów... W
czasie opracowywania podręcznika miałem też inne obowiązki (jak na przykład leżenie i nic
nierobienie) i po prostu pewnego dnia skończyły się wakacje.
W porządku, dość już straszenia, bo już pewnie masz ochotę wyjść i więcej tu nie
wrócić. Pomimo tych wszystkich rzeczy, na które zwróciłem uwagę, głęboko wierzę, że jest to
spory kawałek porządnego materiału, który w znacznym stopniu może pomóc Ci w nauce- inaczej
po prostu bym tego nie publikował w sieci. Zachęcam więc gorąco do czytania i czekam na maile z
uwagami i znalezionymi nieścisłościami. I powodzenia!
Strona 5 z 153

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin