010 011 2

10 Spis treści

8.2.1.    Reguły postępowania przy poszukiwaniu minimalnego drzewa rozpinającego ....................................... 368

8.2.2.    Kolejne iteracje ................................... 368

8.3.    Najkrótsze drogi w sieci .................................. 372

8.3.1.    Reguły postępowania przy poszukiwaniu    najkrótszych dróg w sieci 373

8.3.2.    Kolejne iteracje ................................... 374

8.4.    Maksymalny przepływ w sieci ............................. 379

8.4.1.    Reguły postępowania przy poszukiwaniu maksymalnego przepływu

w sieci ......................................... 380

8.4.2.    Kolejne iteracje ................................... 381

8.5.    Przykłady wykorzystania programowania sieciowego .............. 388

8.5.1.    Dynamiczny problem wielkości    zamówienia ............... 388

8.5.2.    Optymalizacja transportu gorącej wody z ciepłowni do terminala

wysyłkowego ..................................... 390

8.5.3.    Optymalizacja przebiegu linii    światłowodowej .............. 393

9. Programowanie dynamiczne ............................ 395

9.1    Wprowadzenie ......................................... 395

9.2.    Metoda programowania dynamicznego ........................ 397

9.2.1.    Składowe wieloetapowego procesu decyzyjnego ............ 398

9.2.2.    Stany i decyzje dopuszczalne ......................... 400

9.2.3.    Wartości funkcji kosztów etapowych .................... 405

9.2.4.    Zasada optymalności Bellmana i równania optymalności ...... 406

9.2.5.    Reguły postępowania przy rozwiązywaniu zadań programowania

dynamicznego .................................... 410

9.3.    Przykłady wykorzystania programowania dynamicznego ........... 412

9.3.1.    Zagadnienie rozdziału środka .......................... 412

9.3.2.    Zagadnienie alokacji ................................ 415

9.3.3.    Dwukryterialne zagadnienie alokacji ..................... 421

Bibliografia ............................................. 427

Wstęp

Badania operacyjne i decyzje

Słowo decyzja występuje w wielu sytuacjach i niesie ze sobą różne treści, stanowiąc nieodłączny element naszego życia. Bardzo wiele uwagi poświęcono i poświęca się procesowi podejmowania decyzji.

Zacznijmy od dwóch przykładów:

1.    Inwestor zainteresowany jest takim portfelem papierów wartościowych, który przyniesie mu w przyszłości największy zysk przy minimalnym ryzyku. Podejmuje on decyzję o zakupie akcji i obligacji, które znajdą się w jego portfelu inwestycyjnym.

2.    Przyjmijmy, że przedmiotem decyzji jest program inwestycyjny dla pew'-nego regionu. Można ogólnie powiedzieć, że celem programu jest rozwój społeczno-ekonomiczny regionu. Mamy więc w gruncie rzeczy dwa podstawowe cele, obejmujące sferę społeczną i gospodarczą. Dalej konkretyzując, możemy przyjąć, że cel rozwój gospodarczy zostanie osiągnięty, jeżeli nastąpi rozwój przemysłu, rolnictwa, budownictwa, rzemiosła. Podobnie, celowi rozwój społeczny, rozumianemu jako poprawa warunków życia mieszkańców', odpowiada rozwój budownictwa mieszkaniowego, sieci komunikacyjnej, oświaty, służby zdrowia, poprawa stanu środowiska naturalnego. Zamiast jednego celu ogólnego mamy więc całą wiązkę celów cząstkowych, opisujących poszczególne aspekty rozwoju regionu¹.

Podejmując decyzję, możemy poprzestać na zadowoleniu się pierwszym rozwiązaniem, które nam przyjdzie do głowy, a częściej — które w pewien sposób wypracujemy. Pojawia się jednak pytanie: czy otrzymana decyzja jest jedyną możliwą, czy nie istnieją decyzje lepsze? Poszukując decyzji najlepszej, możemy iść drogą bardziej skomplikowaną. Najpierw tworzymy wiele wariantów decyzji,

1

Przykład ten został zaczerpnięty z książki: Z. Galas, I. Nykowski, /.. Żółkiewski, Programowaniu wielokryierialne. PWE, Warszawa 1987.