57348 img374 (3)

I /naltvc wekloi \ m.il.\\m.ili/il|;|t,V piodukcję, jc/rli kos/ly ilanc rów

ii.iiiinn

< I v I c¹ x.

pi /y c/ym

c =

mc powinny przekroczyć K = 6, a więc

2.v, + 3x₂ + 4x₃ ^ 6.

2. Jak zmieni się rozwiązanie, jeśli zostanie wprowadzone dodatkowe ograniczenie o postaci:

3-Cj + 2x₂ + 10.\'₃ ^15.

7. Elementy programowania dynamicznego

Programowanie dynamiczne jest jedną z technik matematycznych, którą można zastosować do rozwiązywania takich problemów, jak: zagadnienie dyliżansu, zagadnienie finansowania inwestycji, optymalizacja zapasów, alokacja zasobów, czy wymiana majątku trwałego¹. Warto przy tym podkreślić, że programowanie dynamiczne należy traktować bardziej jako sposób podejścia do rozwiązywania problemu niż jako pojedynczy uniwersalny algorytm. W dalszej części ograniczono się do bliższego scharakteryzowania zagadnienia finansowania inwestycji oraz zagadnienia dyliżansu (stagecoach problem).

Zagadnienie finansowania przedsięwzięcia inwestycyjnego można scharakteryzować jako problem alokacji określonego zasobu środków (w tym przypadku wyrażonego w jednostkach pieniężnych) pomiędzy poszczególne zadania (programy inwestycyjne), tak aby osiągnąć maksymalny efekt. Przyjmuje się przy tym następujące założenia:

1.    Efekt zastosowania każdego z programów inwestycyjnych nie zależy od tego, czy zostały zastosowane równocześnie inne programy inwestycyjne.

2.    Zwrot nakładów inwestycyjnych jest mierzony w tych samych jednostkach.

3.    Nakłady inwestycyjne są liczbami całkowitymi.

4.    Funkcje określające związki między nakładami inwestycyjnymi a wysokością zwrotu nakładów są niemałej ące.

Nieco inny problem niesie ze sobą tzw. zagadnienie dyliżansu, polegające na poszukiwaniu optymalnej drogi w sieci.

Nazwa zagadnienia pochodzi od pewnego kupca amerykańskiego, który transportował towary ze Wschodniego Wybrzeża USA na Wybrzeże Zachodnie, używając w tym celu różnych połączeń realizowanych za pomocą dyliżansu. Oczywiście, chodziło o dobór takich połączeń, aby transport odbywał się

205

1

Szeroki zakres zagadnień rozwiązywanych za pomocą algorytmów programowania dynamicznego można znaleźć np. w pracy H.M. Wagnera [68].