Wydawca
Nowości
Łamigłówki debiutowe/Penelopa/
Łamigłówki debiutowe/Penelopa/
21,00 zł 20,00 zł
egz.
Magnus Carlsen. Mocart szachów
Magnus Carlsen. Mocart szachów
37,80 zł 36,00 zł
EGZ.
Bezpieczeństwo pożarowe dachów. DAFA  PPOŻ.1.01
Bezpieczeństwo pożarowe dachów. DAFA PPOŻ.1.01
73,50 zł 70,00 zł
EGZ.
Newsletter
Podaj swój adres e-mail, jeżeli chcesz otrzymywać informacje o nowościach i promocjach.
Submit

Elementy programowania liniowego i metod sieciowych

Dostępność: średnia ilość
Wysyłka w: 24 godziny
Dostawa: Cena nie zawiera ewentualnych kosztów płatności sprawdź formy dostawy
Cena: 16,00 zł 16.00
zawiera 5% VAT, bez kosztów dostawy
Cena netto: 15,24 zł
bez 5% VAT i kosztów dostawy
ilość egz.
dodaj do przechowalni

Opis

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
Oprawa broszura
Rok wydania 2015
Format b5
Stron 153

Koszty dostawy Cena nie zawiera ewentualnych kosztów płatności

Kraj wysyłki:

Opinie o produkcie (0)

do góry
Sklep jest w trybie podglądu
Pokaż pełną wersję strony
Sklep internetowy Shoper.pl