Elementy programowania liniowego i metod sieciowych
towar niedostępny
dodaj do przechowalni
Opis
Spis treści
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
Szczegóły
| ISBN | 9788374647731 |
| Autor | Wojda A.P. |
| Oprawa | br |
| Rok wydania | 2015 |
| Format | b5 |
| Stron | 153 |
Opinie o produkcie (0)
Newsletter