3582319517

1

Badania operacyjne ZHP rok 2 ćwiczenia - zajęcia 3

Dualność w programowaniu liniowym

Z każdym zadaniem programowania linowego sprzężone jest pewne inne zadanie programowania liniowego, zwane zadaniem dualnym.

Tl «. i
max z = / c-x.,j = 1,	..., n
j=i 71
< i[y. p IA cr II	,,m

Jeżeli pierwotnym zadaniem (ZP) jest:

j=i

Vjf Xj > O.j — 1. ..„„w To zadaniem dualnym (ZD) jest:

min w =	£ II *5
m
	IA '■L,. II
i=i
V: w > 0,	i = 1,..., m

Relacje zachodzące między ZP i ZD:

1.    W każdym ZD jest tyle zmiennych, ile warunków w ZP (każdemu ograniczeniu w ZP odpowiada jedna zmienna w ZD).

2.    W ZD jest tyle warunków, ile zmiennych w ZP.

3.    Współczynniki w funkcji celu ZP są wyrazami wolnym (czyli prawymi stronami ograniczeń) w ZD.

4.    Prawe strony ograniczeń w ZP są współczynnikami funkcji celu w ZD.

5.    Macierz współczynników ZD jest transpozycją macierzy współczynników w ZP.

6.    Kryteria decyzyjne ZP i ZD są odwrotne.

Reguły budowy ZD:

1.    Jeżeli w ZP dany warunek jest równością, to odpowiadająca mu zmienna w ZD nie ma ograniczeń.

2.    Jeżeli w ZP dany warunek jest nietypową nierównością¹, to w ZD odpowiadająca mu zmienna jest mniejsza od zera (^¹ - ^lj).

3.    Jeżeli w ZP na zmienną ^X} nie nałożono ograniczeń, to w ZD ■ ~ ^r’“' warunek jest równością.

4.    Jeżeli w ZP zmienna ^A ~ ^fJ, to w ZD ^; ~ ^L’¹ warunek jest nietypową nierównością.

Zadanie dualne:

>T 2 0

y₂ - dowolna min w — lOyi. + 4y- + 2y-4y_t + 3y₂ + Zj-g = 6 6y₂ 4* 2y_; 4* 2Vg ^ S

Zadanie d ualne:

Zadanie pierwotne:

max z - iS.t; + S.v_:

+ ójfj i 10 3.t_ł ■+■ 2 .T- — 4

+ 2Xr > 2

x_t - dowolne x_z <0

Zadanie pierwotne:

1

Nierówności typowe:

Dla zadań, gdzie kryterium decyzyjnym jest maksymalizacja, są to nierówności typu „ 5”. Dla zadań, gdzie kryterium decyzyjnym jest minimalizacja, są to nierówności typu „ —