Z niniejszej książki mogą korzystać studenci różnych kierunków, szczególnie ekonomicznych i technicznych. Pisana jest jednak głównie z myślą o studentach Wydziału Matematyki Stosowanej AGH, dla których autor prowadzi semestralny wykład z programowania liniowego. Książka zawiera zatem szczegółowy zapis wykładów autora, które obok głównego zagadnienia programowania liniowego obejmują również wybrane problemy z zakresu optymalizacji kombinatorycznej: metody sieciowe i ich zastosowania w teorii grafów.
- Contents
-
Wstęp 4
1 Problem programowania liniowego 9
1.1 Definicje 12
1.2 Ćwiczenia 13
2 Opis algorytmu sympleksowego 15
2.1 Wprowadzenie 15
2.2 Tabele sympleksowe 20
2.3 Szczegóły metody sympleksowej 23
2.3.1 Badanie niesprzeczności i szukanie pierwszego rozwiązania dopuszczalnego 23
2.3.2 Czy metoda sympleks jest zawsze skuteczna? 25
2.3.3 Cykliczność. Reguła Blanda 27
2.4 Ile może być rozwiązań optymalnych PPL? 32
2.5 Złożoność obliczeniowa algorytmu sympleksowego 33
2.6 Wyjaśnienie nazwy algorytmu sympleksowego 38
2.7 Ćwiczenia 38
3 Dualizm 41
3.1 Problem dualny programowania liniowego 41
3.2 Zastosowanie zasady dualności 44
3.3 Interpretacja ekonomiczna zmiennych dualnych 48
3.4 O dualności ogólniej 50
3.5 Ćwiczenia 52
4 Zrewidowana metoda sympleksowa 55
4.1 Macierzowy opis słownika 55
4.2 Podsumowanie 61
4.3 Programowanie całkowite 62
4.4 Ćwiczenia 67
5 Zadanie ograniczone 69
5.1 Algorytm sympleksowy dla zadania ograniczonego 70
5.2 Inicjalizacja 75
5.3 Ćwiczenia 76
6 Interpretacje i zastosowania 77
6.1 Interpretacja geometryczna 77
6.2 Powłoki wypukłe zbiorów 81
6.3 Układy nierówności i równań liniowych 84
6.4 Wielościany i półprzestrzenie 86
6.5 Metoda Fouriera–Motzkina 88
6.6 Ćwiczenia 90
7 Grafy i metody sieciowe 93
7.1 Grafy skierowane 93
7.1.1 Macierz sąsiedztw grafu skierowanego 94
7.1.2 Macierz incydencji grafu skierowanego 95
7.1.3 Ścieżki i cykle 95
7.2 Sieci 96
7.3 Przepływy w sieciach 96
7.4 Maksymalny przepływ a dualność 101
7.5 Algorytm Forda–Fulkersona 102
7.6 Przepływ całkowity. Zbieżność algorytmu F–F 104
7.7 Wnioski i zastosowania 108
7.7.1 Twierdzenie Halla 108
7.7.2 Zbiór różnych reprezentantów 111
7.7.3 Przepustowość wierzchołków i twierdzenie Mengera 112
7.8 Twierdzenie Chvátala–Erdősa 115
7.9 Ćwiczenia 118
8 Problem transportowy 121
8.1 Drzewa nieskierowane 121
8.2 Drzewa skierowane 124
8.3 Problem transportowy – sieciowy algorytm sympleksowy 125
8.4 Iteracje 127
8.5 Inicjalizacja 136
8.6 Dekompozycja problemu transportowego 138
8.7 Skończoność algorytmu sympleksu sieciowego 140
8.8 Modyfikacja uczciwych cen w wierzchołkach 141
8.9 Procedura unikania zapętlania – reguła Cunninghama 142
8.10 Zapotrzebowanie mniejsze od zasobów 147
8.11 Ćwiczenia 147
Bibliografia 149
Index 151
