DSC00096 (8)

OCENA ROZWIĄZANIA OPTYMALNEGO PROBLEMU DECYZYJNEGO

•    Badan* reakcji optymalnej wartości funkcji edu na marginalne /-imany wybranego środka (limitu) prezentowanego przez określony wyraz wolny w ograniczeniach zadami PL zagadnieniu dualne PL, wyceny dualne

•    Ustałamc przedziałów dopuszczalnych zmian w zasobach środków (limitów), przedziałów dopuszczalnych zmian dla współczynników (unkgi edu, które nic powodują zmiany rozwiązania optymalnego - anaUza wratlłwości

•    Badane reakcji rozwiązania optymalnego na dołączenie lub usunięcie zmiennej decyzyjnej łub ogramczm z zadania PL - analiza wratlłwości na zmiany w strukturze modelu decyzyjnego

Zadanie dualne i jego własności

Zadanie dualne jest scule powiązane z rozwiązywanym zadaniem pierwotnym ipcynrnaym) PL Zadania te tworzą sprzężoną parę zadań dualnych względem siebie. Zadanie dualne względem zadania dualnego jest identyczne z zadaniem pierwotnym Zmiennymi decyzyjnymi zadania dualnego są tzw. wyceny dualne, zmienne pozwalające ocenić wielkość i kierunek zmian optymalnej wartości funkcji celu na zmiany w poziomach limitów (wyrazach wolnych ograiuttcń).

Zasady budowy zadania dualnego:

1.    Maksymalizacji wartości funkcji edu zadania pierwotnego odpowiada minimalizacja wartości funkcji edu zadania dualnego 1 odwrotnie.

2.    Współczynniki funkcji edu zadania pierwotnego [ty] stają się wyrazami wolnymi

dualnego

3    Wyrazy wolne [*_#] ograniczeń zadania pierwotnego stają się współczynnikami fimttyi cchl SjfllBBa ^nalrwgo

4    Macierz współczynników lewych stron ograniczeń zadania dualnego jest traospooowaną macierzą [ty] zadania pierwotnego. Wyruka stąd. te liczba zmiennych decyzyjnych zadania dualnego (wycen dualnych! jest równa liczbie ogromach w zadaniu pierwotnymi natomiast liczba ograniczeń w zadaniu dualnym jest równa iicbie zmiennych decyzyjnych w zagadnieniu pierwotnym.

5. Warunkowi pierwotnemu w postaci nierówności z relacją *<” odpowiada w ragadfWT>i» dualnym.

-    moijemna zmienna dualna ( w, > 0 j jczdi pierwotna funkcja edu jest

HakłymafenMiM

-    medodatnia zmienna dualna ( w, < 0 ) jeżeli pierwotna funkcja edu jest mmimafiTowana

6 Warnikowi pierwotnemu w postaci nierówności z relacją „2" odpowiada w zagadnieniu dualnym.

- medodatnia zmienna dualna { w, < 0 ') jeżeli pierwotna funkcja edu jest maksynalizowaBa

. maijemna zmienna dualna ( w, > 0 ) jezrii pierwotna funkcja edu jest nanimihzowaaa

7. Warunkowi pierwotnemu w postaci równania odpowiada nieokreślona co do znikli znaama dualna (w&R)

Niesymetryczne zadanie dualne

Zadanie pierwotne

min f(x ) - c^TX A X * b X> O

żądanie dualne

max g(w)-b^TX A^tW$c

brak wymagań aby w, > o

Symetryczne zadanie dualne

Zadanie

Zadanie pierwotne

min f(x) • c^TX AX > b X > 0

maxg(w)-b^TX A^T W Se W>0

Twierdzenie o dualizmie

Dla danej pny zadań dualnych prawdziwe jest wyłącznie jedno z poniższych twierdzeń

1. Jeżeli jedno z paty zadań dualnych posiada rozwiązanie opty malne A** (lub W ). to drugie również posiada rozwiązanie optymalne    (lub X/.

przy czym optymalne wartości funkcji celu są sobie równe, tj

to drugie z zadań jest sprzeczne (jeżeli jedno z zadań jest sprzeczne to drugie może być również sprzeczne lub me posiadać skończonego rozwiązania optymalnego).

Twierdzenie o rozwiązaniu zadania dualnego

Jeżeli istnieje skończone rozwiązanie optymalne X zadania pierwotnego względem bazy B, to rozwiązanie optymalne zadania dualnego to' dane jest wzorem:

gdzie: ( c* )^T-[ c*, c₂*, -™, c_m^B ] - wektor współczynników w aadagi cefal zadania pierwotnego stojących przy zmiennych bazowych w bazie M.

Interpretacja zmiennych dualnych

Optymalna wartość zmiennej dualnej ( wyceny dualnej) m,' qkxę& znunę optymalnej wartości funkcji celu zadania pierwotnego spowodowaną zmianą wmiata wyrazu wolnego (limitu ) b_; i-tego ograniczenia zadania pierwotnego o jednoukę. tj

jcash w i-tym ograniczeniu zadania PL wyraz wolny b, wzruooic {spodniej o jednostkę to optymalna wartość funkcji edu zadania pierwotnego f( X ) wzrośnie (spadnie) o w? jednostek tj. do pauorau /(x ) + uy (f( x"} - w< )

W interpretacji ekonomicznej najczęściej zmienna dualna traktowana jest jako mara efektywności wykorzystania ograniczonego zasobu danego środka produkcji.