396 397

396 Programowanie dynamiczne

decyzje w taki sposób, aby zmaksymalizować (w przypadku korzyści) lub zminimalizować (w przypadku strat) wartość funkcji kryterium, opisującej proces w całym rozpatrywanym odcinku czasu.

Strategią nazwiemy funkcję, która każdemu stanowi dopuszczalnemu, w jakim może znaleźć się proces, przyporządkowuje pewną decyzję dopuszczalną. Strategią optymalną nazwiemy taką strategię, która każdemu stanowi dopuszczalnemu przyporządkowuje decyzję optymalną. Strategia optymalna pozwala na wygenerowanie optymalnej realizacji procesu, czyli takiego ciągu stanów i decyzji, który optymalizuje wartość funkcji kryterium.

Rozwiązując zadanie programowania dynamicznego, możemy wykorzystać jego strukturę etapową. Podział rozpatrywanego odcinka czasu na etapy powoduje, że zamiast rozwiązywać jedno duże i zazwyczaj trudne zadanie optymalizacyjne, w pierwszym stadium rozwiązywania zadania dekomponujemy (czyli dzielimy) je w odpowiedni sposób na ciąg mniejszych i łatwiejszych do rozwiązania, powiązanych ze sobą zadań. Wzajemną zależność między rozwiązaniami optymalnymi tych zadań a rozwiązaniem optymalnym całego problemu określa zasada optymalności Bellmana. Korzystając z niej, tworzymy dla wszystkich stanów procesu równania optymalności. Drugie stadium rozwiązywania zadań programowania dynamicznego polega na odpowiednim połączeniu ze sobą rozwiązań zadań cząstkowych i określeniu optymalnej realizacji procesu.

Zadania programowania dynamicznego — podobnie jak zadania statyczne — można rozpatrywać jako problemy jedno- i wielokryterialne. W tym drugim przypadku aktualne są uwagi sformułowane w rozdziale 4, dotyczące określenia rozwiązań optymalnych wektorowo. Nie należy również oczekiwać, że w rozpatrywanych zadaniach często będzie możliwe uzyskanie rozwiązania dominującego, stąd jako rozwiązanie optymalne wektorowo przyjmiemy rozwiązanie niezdomino-wane. Porównując ze sobą dwa dowolne rozwiązania, będziemy się posługiwać ocenami wieloetapowymi, dotyczącymi całego rozpatrywanego odcinka czasu. Można poszukiwać pełnego zbioru ocen niezdominowanych w przestrzeni kryte-rialnej oraz rozwiązań sprawnych w przestrzeni decyzyjnej, wykorzystując wektorowe ujęcie zasady optymalności Bellmana. Ze względu na to, że zazwyczaj (podobnie jak w przypadku wielokryterialnego programowania liniowego) trudno znaleźć pełne rozwiązanie wektorowe, często wykorzystuje się skalaryzację tego zadania, stosując takie same metody, jakie zostały opisane w rozdziale 4.

Rozpatrywane uprzednio zadania statyczne miały zazwyczaj jednoznacznie określoną strukturę. Przykładowo, każde zadanie programowania liniowego z kryterium maksymalizacji można zapisać w postaci:

cx —» max,

Ax = b,

x>0,

gdzie:

c — wektor funkcji celu,

A — macierz warunków ograniczających, b — wektor prawych stron ograniczeń, x — wektor decyzyjny.

Różnorodność problemów, które można rozwiązać za pomocą programowania dynamicznego, powoduje, że nie istnieje możliwość jednolitego zapisu zadania programowania dynamicznego, tak jak to występuje dla dowolnego zadania programowania liniowego. Każdy problem należy zapisać oddzielnie, wyróżniając zbiór stanów dopuszczalnych, decyzji dopuszczalnych, funkcje przejścia, funkcje korzyści (lub strat) etapowych oraz globalną funkcję korzyści (lub strat) dla całego procesu.

W rozdziale tym przedstawimy metodę programowania dynamicznego oraz cztery przykłady jej wykorzystania. Omawiane zagadnienia dotyczą sterowania zapasami oraz optymalnego rozdziału środków. Do rozwiązania zadań metodą programowania dynamicznego można wykorzystać programy DYNAM1.EXE i DYNAM2.EXE.

9.2. Metoda programowania dynamicznego

Rozpoczniemy od sformułowania przykładowego zadania sterowania zapasami. Następnie wyznaczymy dla niego zbiory stanów i decyzji dopuszczalnych, wartości funkcji kosztów etapowych, przedstawimy zasadę optymalności Bellmana i pokażemy, w jaki sposób możemy ją wykorzystać w rozpatrywanym przypadku do sformułowania równań optymalności.

Przykład 9.1¹

Rozważamy trzyetapowe zadanie sterowania zapasami. Na początku pierwszego etapu w magazynie znajduje się jedna jednostka określonego produktu. Wiemy, że maksymalna wielkość możliwego uzupełnienia zapasów w jednym etapie, taka sama dla wszystkich rozpatrywanych etapów, wynosi 4 jednostki. Maksymalne możliwości magazynowania w każdym etapie to 4 jednostki. Popyt na dany produkt kształtuje się na poziomie 3 jednostek w ciągu jednego okresu. Z uzupełnieniem zapasów związane są koszty stałe w wysokości 8 jednostek, niezależne od wielkości zamówienia i ponoszone jedynie w przypadku, gdy decydujemy się na złożenie w danym okresie zamówienia, oraz koszty zmienne, proporcjonalne do wielkości zakupu.

' Zadanie opisane w tym przykładzie można rozwiązać zarówno przy użyciu programu DYNAM 1.EXE, jak i programu DYNAM2.EXE.