10962067�59140220949130871164 n

I nitowe zadanie decy zyjne (Ia) (lc) mo/na zapisać w /wartej postaci

ca -»mat.    ca -+ min,

(2p^ A\ I*    albo Op) A\ • b.

xiO    aŁO

. .•ulania (2p>.(«p) będą nazywane zadaniami pierwotnymi

Zadaniami dualo>utl do tych zadań nazywane si\ zadania:

Od)

yb -ł min.    yh-* mut.

albo (3d)    \ ,

\ A h    yA S b.

w których > -(>•, i_:    y_m | jest wektorem zmiennych decyzyjnych za

dania dualnego. krOtko: wektorem zmiennych dualnych

Zadanie (2d) jest zadaniem dualnym do zadania (2p>. a zadanie (Jd) jed zadaniem dualnym do zadania (3p)

Jak 10 ahlktMff

Cech) „konstrukcyjne" zadań dualnych względem siebie:

•    Jr>eli w zadaniu pierwotnym chodzi o nuiksymalUacjf wurtoici funkcji celu. to w zadaniu dualnym chodzi o minimalizację watio-ici funkcji celu. i na odwrót: Jcłcłi ss zadaniu pierwotny m chodzi o minimalizację funkcji celu. tu w zadaniu dualnym chodzi o maksymalizację funkcji celu.

•    I iczba zmiennych w zadaniu dualnym jest równa liczbie równań w zadaniu pierwotnym.

•    Zmienne decyzyjne zadania dualnegosą przyporządkowane warunkom ograniczającym zadania pierwotnego i na odwrót; zmienne decyzyjne zadania pierwotnego są przyporządkowane warunkom ogninic/nji|cym zadania dualnego.

•    W agi fuukcji celu zadania pierwotnego %e wy razami wolnymi zadania dualnrgo.

•    Wyrazy wolne zadania pierwotnego %e wagami funkcji celu zadu-nia dualnrgo.

•    Współczynniki poszczególnych równań zadania pierwotnego

znajduje się w wierszach macierzy \. natomiast współczynniki po\/cz» gol im h nierówności zadania dualnego znajduje się « kolumnach macierzy A._

;<M

Podatkowi- H-łasnoicI zadań dualnych:

1.    Jeżeli warunek ograniczający w zadaniu pierwotnym jc*t nicrów nością (do której „wprowadzana" jest zmienna swobodna celem przejęcia do postaci kanonicznej zadania), to zmienna dualna odpowiadająca tej nierówności Jest nicujemna. jeżeli natomiast warunek ograniczający zadania pierwotnego jest równaniem, to zmienna dualna odpowiadająca temu rów-naniu może przyjąć dowolne (dodatnie lub ujemne) wartości.

2.    Jeżeli zadanie pierwotne jest zadaniem o postaci standardowej, to zadanie dualne do niego jest rów nieź /aduniem o postaci standardowej.

J. /.udanie dualne do zadania dualnrgo jest zadaniem pierwotnym.

W szczególnym przypadku zadaniami dualnymi do zadań o postaci standardowej:

cx — > min.

(6p) Ax i b , xiO.

yb -♦ max . (6d)    > A £ b.

y*0

c\ > max,

($p) Ax i b.

\Z0.

są zadania o postaci standardowej: yb —» min,

(5d) yA i b, yJtO.

Zadanie (>d) jest zadaniem dualnym do ($p). a zadanie (6d) jest zadaniem dualnym do (óp).

Przykład

W przykładzie 1. z paragrafu 9.3 rozważaliśmy zadanie o postaci standardowej.

I S.\| ♦ 15.t2 8x, -f 4x2 i $2.

(7s)    6.t| + 9x2 ^s

x,.    x₂* 0

Sformułować zadanie dualne do tego zadania

Aby skonstruować zadanie dualne, zadanie (?s) trzeba najpierw przedstawić w postaci kanonicznej:

205