Program dualny - teoria i przyklad.pdf - programowanie liniowe - przedmioty_ekonomiczne

Ilustracja zagadnienia dualności w programowaniu liniowym

Grzegorz Ginda

Zakład Badań Operacyjnych

Wydział Zarządzania i Inżynierii Produkcji

ul. Waryńskiego 4, 45-057 Opole

ging@po.opole.pl

Przykładowe zagadnienie

Dane do zadania przyjęto z książki [1].

Zakład produkcyjny może wytwarzyć trzy rodzaje dóbr. Ich liczby wynoszą odpowiednio (w

tysiącach sztuk): x 1 , x 2 , x 3 . Do wyprodukowania tysiąca sztuk wyrobu pierwszego rodzaju

potrzebna jest ilość podstawowego surowca, wynosząca 2 tony. W przypadku produktu drugiego

rodzaju potrzeba 1 tysiąca ton, a trzeciego – 4 tysięcy ton tego samego surowca. Poza tym, do

wytworzenia 1 tysiąca sztuk wyrobów poszczególnych rodzajów niezbędny jest surowiec drugiego

rodzaju, którego zużycie wynosi odpowiednio: 2 tysięcy ton na 1 tys. sztuk wyrobu pierwszego

rodzaju oraz 2 tysiące ton na 1 tys. sztuk wyrobu drugiego rodzaju. Zużycie surowców nie powinno

być niższe niż odpowiednio: 2 tysiące ton i 3 tysiące ton. Koszty wyprodukowania 1 tys. sztuk

wyrobów poszczególnych rodzajów wynoszą odpowiednio: 14 tys. zł, 8 tys. zł i 16 tys. zł.

Należy określić program produkcji, wyrażony liczbą produkowanych wyrobów, który spełni

powyższe ograniczenia przy jak najniższym koszcie.

Model PL (prymalny)

Zmiennymi decyzyjnymi są wielkości produkcji wyrobów poszczególnych rodzajów tj.: x 1 , x 2 oraz

x 3 . Z warunków zadania wynika, że funkcja celu ma postać:

f =14 x 1 8 x 2 16 x 3 min .

(1)

Ponadto rozwiązanie powinno spełniać ograniczenia:

2⋅ x 1 1⋅ x 2 4⋅ x 3 ≥2 ;

2⋅ x 1 2⋅ x 2 ≥3 ;

(2)

a także ograniczenia nieujemności liczby produkowanych wyrobów:

x 1, x 2, x 3 ≥0 .

(3)

Powyższe zagadnienie przyjmuje następującą postać w ujęciu macierzowym:

f = c T ⋅ X min ;

(4)

A ⋅ x ≥ b ;

(5)

∀ i x i ≥0 ;i =1,2,3

(6)

1/3

Macierze i wektory, które wystepują w formułach (4-6) mają następujące postacie:

c T =[14 8 16] ;

(7)

A =

[ 2 1 4

2 2 0 ] ;

(8)

x =[ x 1 x 2 x 3 ] T

;

(9)

b =

[ 3 ] .

(10)

Ponieważ w powyższym zadaniu występują trzy zmienne decyzyjne, trudno znaleźćjego

rozwiązanie metodą graficzną. Z uwagi na liczbę ograniczeń wynoszącą 2, można jednak

sformułować analizowane zagadnienie w innej postaci, umożliwiającej zastosowanie metody

graficznej do jego rozwiązania. W tym celu konstruuje się tzw. dualną postać zagadnienia

(zagadnienie dualne). W tej postaci liczba zmiennych decyzyjnych odpowiada liczbie ograniczeń

zagadnienia prymalnego (2), a liczba ograniczeń – liczbie zmiennych decyzyjnych zagadnienia

prymalnego (3). Zagadnienie dualne w postaci macierzowej wygląda następująco:

g = yb T max ;

(11)

y ⋅ A ≥ c ;

(12)

∀ j y j ≥0 ;j =1,2

(13)

Zmienne decyzyjne y 1 , y 2 nazywane są komplementarnymi w stosunku do poszczególnych

warunków ograniczających zagadnienia prymalnego (5) i odwrotnie tzn. zmienne x 1 , x 2 , x 3

zagadnienia prymalnego pełnią rolę zmiennnych komplementarnych względem ograniczeń (12)

zagadnienia dualnego. Natomiast z postaci funkcji celu (11) widać, że wektor współczynników przy

funkcji celu w zadaniu prymalnym (7) staje się wektorem prawej strony ograniczeń (tzn. wyrazów

wolnych) w zadaniu dualnym i odwrotnie, tj. wektor wyrazów wolnych w zadaniu dualnym staje się

wektorem współczynników funkcji celu w zadaniu prymalnym. Ponadto, kierunki optymalizacji

(minimalizacja, maksymalizacja) oraz ograniczeń nierównościowych w obu zadaniach są

przeciwne.

Jak widać, zagadnienie dualne charakteryzuje obecność tylko 2 zmiennych decyzyjnych. Dlatego

też, można je rozwiązać wykorzystując metodę graficzną. Pomimo przeciwstawnych kierunków

optymalizacji, w przypadku obu zagadnień otrzymuje się tę samą optymalną wartość funkcji celu.

f min = g max = 14 tys. zł 1 .

(14)

Rozwiązanie optymalne dla zadania dualnego otrzymano przy wartościach zmiennych decyzyjnych

wynoszących:

1 Rozwiązania dla obydwu problemów – prymalnego i dualnego można także otrzymać metodami analitycznymi. Na

przykład można zastosować w tym celu arkusz kalkulacyjny MS Excel i jego narzędzie Solver – por. zawartość

pliku “dualizmPL.xls”.

2/3

y =

[ 2 ] .

(15)

Tak więc, y 1 = 4 tys. zł / tys. t surowca pierwszego i y 2 = 2 tys. zł / tys. t surowca drugiego rodzaju.

Otrzymane wartości zmiennych decyzyjnych stanowią tzw. ceny dualne, będące w istocie

wskaźnikami największej zmiany funkcji celu zagadnienia prymalnego wraz ze zmianą podaży

rozpatrywanych dwóch rodzajów surowców.

W celu otrzymania wartości zmiennych decyzyjnych zagadnienia prymalnego, odpowiadających

rozwiązaniu optymalnemu można wykorzystać twierdzenie o komplementarności zagadnień

prymalnego i dualnego:

 yA − c  x =0 .

(16)

Z pierwszej zależności (16) można otrzymać, że:

y 1 ⋅  2−2⋅ x 1 −1⋅ x 2 −4⋅ x 3  =0 ;

y 2 ⋅  3−2⋅ x 1 −2⋅ x 2 −0⋅ x 3  =0 .

(17)

Ponieważ obie wartości zmiennych decyzyjnych zadania dualnego są dodatnie to składniki obu

wyrażeń (17) zawarte w nawiasach muszą być równe zeru. Stąd, po uwzględnieniu optymalnej

wartości funkcji celu (14) oraz przyrównując składowe wyrażeń w nawiasach do zera, można

zbudować następujący układ równań, z którego wyznacza się wartości zmiennych decyzyjnych

zagadnienia prymalnego (4-10):

14⋅ x 1 8⋅ x 2 16⋅ x 3 =16 ;

2⋅ x 1  x 2 4⋅ x 3 =2 ;

2⋅ x 1 2⋅ x 2 =3 .

(18)

Z powyższego układu równań otrzymuje się rozwiązanie w postaci:

x =

[

1,5

0,125

] .

(19)

Tak więc, aby osiągnąć maksymalny zysk należało by wyprodukować 1,5 tys. produktu drugiego

rodzaju i 125 szt. produktu trzeciego rodzaju.

Literatura

[1] Tadeusz Trzaskalik “Wprowadzenie do badań operacyjnych z komputerem”.

PWE, Warszawa 2003.

[2] Ireneusz Nykowski “Programowanie liniowe”. PWN, Warszawa 1984.

3/3

y  b − Ax  =0

Program dualny - teoria i przyklad.pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: