0000136

DOOATEK A

ZASADA DUALNOŚCI

Wełny pod uwagę zodonle programowanie liniowego (pi t r-w o t n o); Należy wyznoczyć *° • (Xj,...,x°^ teki, łe

(0.4.1)

Cc₄x° > nnx c-x

H J J X ł-» ^{J J}

przy ograniczeniach

11 ^x» * ••• ^{4 Q}u ^xt ^{f a}i,t+t ^X|ai ⁺‘'“ ^{+ Q}i_n *n “ ^bi

CD.4.2)

a_M X_t ♦ ... 4-Q_wx_l + Q_|t^₁ X_M 4. •••ta_knX_n -b_k ^Qk*l,1 ** * **' ^+akM,l^xi ^+ak*1,U1 *U1 * '* ' ^+CW^Xn ⁴

^Qm *1 * -Omi^ ♦Om,Ul *|_H ♦ * * * + ^Xn * !>_r

przy czym niech zmienne x_1#...,x₁ nie maję ogronlczonia no znok, natomiast zmienno ^xx*l^<<*^a#Xn    nieujemne.

Dualne zadania prograaowanla liniowego tworzy alę następująco: Każdemu ograniczeniu przyporzydkowujomy zmienny y_J,

przy czym równościom odpowiodojg zmienne yj.....y^ bez ograni -

czenio no znak, a nierównościom zmienne y^_4l.....y_Q, które majo

być nieujemne.

Należy wyznaczyć taki wektor y° • <y°,...,y®> , aby

2—^bi^yl ’ ^,ln IZ^bi^yi    (0.4.3)

»«i y i-i

przy ograniczeniach.

Q„ y, + ••• ^łQki«k ♦ Q_kł|,l y_k.i ^f ’^aml«m - ^cl

(D.4.4)

Zadanie dualne zndonlo dualnego Joot zadaniem pierwotnym. Wek -tor X nazywamy woktorom dopuszczalnym , gdy Opoł-nla on ogranlczonla zadania pierwotnego, doleli ponadto makey -

y i wektory optymalne dla zadanio dualnogo.

Zadanie programowania llnlowogo ma zatem będż

o/ wektory optymalne (o więc dopuszczalne),

b/ woktory dopuszczalne, lecz nie ma wektora optyaelnogo,

c/ nlo mo wektorów dopuezczalnych.

Geóli yryetępuje przypadek a/ w zodaniu plerwotnye, to mamy równio! przypadek a/ w zodaniu dualnya 1

n    m

(0.4.5)

Gęśli w zadaniu pierwotnym występuje przypadek b/, to w zadaniu dualnym mamy przypadek c/.

Gęśli natomiast w zadaniu pierwotnym mamy przypadek c/, to w zo-donlu dualnya mamy przypodek b/ lub c/.

Gęśli zarówno zadonio piorwotne. Jak 1 dualne, maję wektory dopuszczalne, to łatwo sprowdzlć, la

(0.4.6)

271