Elementy programowania liniowego i metod sieciowych

szkoła wyższa
16
PLN
Elementy programowania liniowego i metod sieciowych
in_stock
Dostępność:
jest
Wysyłka w:
24 godziny
Cena: 16,00 zł
Cena netto: 15,24 zł
egz.
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.

 

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 broszura
Rok wydania 2015
Format B-5
Stron 153

Opinie o produkcie (0)

Koszyk

produktów: 0

wartość: 0,00 zł

przejdź do koszyka »

Zaloguj się

123

W Y D A W C Y

Sklep jest w trybie podglądu
Sklep internetowy Shoper.pl