Dualita v úlohách LP Ekonomická interpretace duální úlohy. Jiří Neubauer. Katedra ekonometrie FEM UO Brno

Dualita v úlohách LP Ekonomická interpretace duální úlohy

Základy operačního výzkumu Přednáška č. 6 Jiří Neubauer Katedra ekonometrie FEM UO Brno

Jiří Neubauer

Základy operačního výzkumu


Dualita v úlohách LP Uvažujme obecnou úlohu lineárního programování, tj. úlohu nalezení takového řešení vlastních omezujících podmínek a11 x1 + a12 x2 + . . . + a1n xn a21 x1 + a22 x2 + . . . + a2n xn .. .. . . am1 x1 + am2 x2 + . . . + amn xn

= b1 = b2 .. . = bm

aby současně byly splněny podmínky nezápornosti, tj. xi ≥ 0, i = 1, . . . , n. a aby účelová funkce z = c1 x1 + c2 x2 + · · · + cn xn nabývala svého maxima, resp. minima. Jiří Neubauer



Dualita v úlohách LP

V úloze se vyskytují 3 druhy koeficientů: aij . . . strukturální koeficienty bi . . . celkové úrovně činitelů (pravé strany) cj . . . cenové koeficienty Tyto koeficienty jsou v matematických modelech propojeny pomocí proměnných xj . Koeficienty aij , bi se vyskytují ve vlastních omezeních, koeficienty cj se vyskytují v účelové funkci. Takto zformulovaný matematický model budeme nazývat primární matematický model.

Jiří Neubauer




Ke každé úloze lineárního programování lze formulovat úlohu duální. Dualita je matematický vztah mezi dvěma úlohami lineárního programování – primární a duální, které tvoří dvojici duálně sdružených úloh. Věta o reflexivnosti duality Duální úloha k duální úloze je původní primární úloha. Reflexivnost duality umožňuje z vlastností a řešení primární úlohy určit vlastnosti a řešení úlohy duální a naopak.

Jiří Neubauer




Říkáme, že maximalizační úloha je ve standardním tvaru, jestliže všechny vlastní omezující podmínky jsou typu „≤ÿ nebo „=ÿ, tzn. např. z = c1 x1 + c2 x2 a11 x1 + a12 x2 a21 x1 + a22 x2 .. .. . . am1 x1 + am2 x2

Jiří Neubauer

+ . . . + cn xn → max + . . . + a1n xn ≤ b1 + . . . + a2n xn ≤ b2 .. . + . . . + amn xn ≤ bm



Dualita v úlohách LP Říkáme, že minimalizační úloha je ve standardním tvaru, jestliže všechny vlastní omezující podmínky jsou typu „≥ÿ nebo „=ÿ, tzn. např. z = c1 x1 + c2 x2 a11 x1 + a12 x2 a21 x1 + a22 x2 .. .. . . am1 x1 + am2 x2

+ . . . + cn xn → min + . . . + a1n xn ≥ b1 + . . . + a2n xn ≥ b2 .. . + . . . + amn xn ≥ bm

Poznámka: Pokud typy nerovností nejsou v souladu s extrémem účelové funkce, je třeba příslušné vlastní omezující podmínky násobit číslem (−1), a to i za cenu záporné pravé strany.

Jiří Neubauer



Dualita v úlohách LP Ke každé úloze lineárního programování ve standardním tvaru lze jednoznačně přiřadit duální úlohu následovně: Maximalizační primární úloze ve standardním tvaru přísluší minimalizační duální úloha ve standardním tvaru, a naopak. Každému vlastnímu omezení primární úlohy odpovídá jedna strukturní proměnná úlohy duální, a naopak. Matice strukturních koeficientů primární úlohy a matice strukturních koeficientů duální úlohy jsou navzájem transponované. Vektor pravých stran primární úlohy je vektorem cen úlohy duální, a naopak.

Jiří Neubauer



Dualita v úlohách LP Primární mat. model

Duální mat. model

Účelová funkce → max (resp. min) Vlastní omezení primární úlohy (počet m) Podmínky nezápornosti primárních proměnných (počet n)

Účelová funkce → min (resp. max) Podmínky nezápornosti duálních proměnných (počet m) Vlastní omezení duální úlohy (počet n)

z=

n X

cj xj → max

j=1

f =

m X

bi ui → min

i=1

A~x ≤ ~b

AT ~u ≥ ~c

xj ≥ 0, j = 1, . . . n

ui ≥ 0, i = 1, . . . m

Jiří Neubauer




Dualita v lineárním programování je jednoznačné přiřazení matematických modelů vycházejících ze stejných koeficientů aij , bi , cj , které jsou v modelech jinak umístěny. Jestliže se v primární úloze objevují vlastní omezující podmínky pouze ve tvaru nerovnic (nikoli rovnic) a podmínky nezápornosti na všechny proměnné, tvoří primární úloha spolu s duální úlohou dvojici tzv. symetrických duálně sdružených úloh. Když se mezi vlastními omezujícími podmínkami primární úlohy vyskytuje nějaká rovnice, či pokud se nepožaduje nezápornost některé primární proměnné, nazýváme primární úlohu spolu s duální úlohou dvojicí tzv. nesymetrických duálně sdružených úloh.

Jiří Neubauer



Schéma konstrukce duální úlohy f q ≤ b1 u1 + ≤ b2 u2 + .. .

Jiří Neubauer

≥

≥

≥

a11 x1 + a12 x2 + . . . + a1n xn u1 u1 u1 + + + a21 x1 + a22 x2 + . . . + a2n xn u2 u2 u2 + + + .. .. . . + + + + am1 x1 + am2 x2 + . . . + amn xn ≤ bm um um um um ↓ z = c1 x1 + c2 x2 + . . . + cn xn → max min Základy operačního výzkumu


Příklad Podnik vyrábí dva druhy výrobku V1 a V2 . Tabulka udává spotřebu surovin S1 a S2 v kg na výrobu 1 ks výrobku V1 , resp. V2 , a disponibilní množství těchto surovin. Zisk z každého výrobku V1 je 3 Kč a z 1 ks V2 je 2 Kč. Stanovte optimální výrobní plán podniku tak, aby dosáhl maximálního zisku. Sestavte matematický model duální úlohy a naleznete řešení duální úlohy.

S1 S2 zisk

Výrobky V1 V2 2 5 4 1 3 2

Jiří Neubauer

Disponibilní množství 1000 1100 max



Příklad Nejprve sestavíme (primární) matematický model úlohy. 2x1 + 5x2 ≤ 1000 4x1 + x2 ≤ 1100 z = 3x1 + 2x2 → max x1 ≥ 0, x2 ≥ 0, kde x1 , resp. x2 značí počet kusu výrobku V1 , resp. V2 . Primární úloha je maximalizační a všechny vlastní omezující podmínky jsou nerovnosti (konkrétně typu „≤ÿ), tzn. matematický model je ve standardním tvaru. Současně obě proměnné musí být nezáporné, proto tato úloha a k ní úloha duálně sdružená budou tvořit dvojici symetrických úloh. Jiří Neubauer



Příklad

Primární úloha má dvě vlastní omezení, proto duální úloha bude mít dvě duální proměnné. Označíme je u1 a u2 . Uplatněním výše uvedených pravidel sestavíme matematický model duální úlohy ve tvaru 2u1 + 4u2 ≥ 3 5u1 + u2 ≥ 2 f = 1000u1 + 1100u2 → min u1 ≥ 0, u2 ≥ 0 Vyřešme nejprve simplexovou metodou primární úlohu, poté vyřešíme úlohu duální (metoda umělé báze).

Jiří Neubauer



Příklad

báze x10 x20 z

x1 2 4 −3

x2 5 1 −2

Jiří Neubauer

x10 1 0 0

x20 0 1 0

bi 1000 1100 0

βi αik

max



Příklad

báze x10 x20 z

x1 2 4 −3

x2 5 1 −2

Jiří Neubauer

x10 1 0 0

x20 0 1 0

bi 1000 1100 0

βi αik

max



Příklad

báze x10 x20 z

x1 2 4 −3

x2 5 1 −2

Jiří Neubauer

x10 1 0 0

x20 0 1 0

bi 1000 1100 0

βi αik

500 275 max



Příklad

báze x10 x20 z

x1 2 4 −3

x2 5 1 −2

Jiří Neubauer

x10 1 0 0

x20 0 1 0

bi 1000 1100 0

βi αik

500 275 max



Příklad

báze x10 x20 z x10 x1 z

x1 2 4 −3 0 1 0

x2 5 1 −2 18 4 1 4 − 45

Jiří Neubauer

x10 1 0 0 1 0 0

x20 0 1 0 − 12 1 4 3 4

bi 1000 1100 0 450 275 825

βi αik

500 275 max

max



Příklad


x1 2 4 −3 0 1 0

x2 5 1 −2 18 4 1 4 − 45

Jiří Neubauer

x10 1 0 0 1 0 0

x20 0 1 0 − 12 1 4 3 4

bi 1000 1100 0 450 275 825

βi αik

500 275 max

max



Příklad


x1 2 4 −3 0 1 0

x2 5 1 −2 18 4 1 4 − 54

Jiří Neubauer

x10 1 0 0 1 0 0

x20 0 1 0 − 12 1 4 3 4

bi 1000 1100 0 450 275 825

βi αik

500 275 max 100 1100 max



Příklad


x1 2 4 −3 0 1 0

x2 5 1 −2 18 4 1 4 − 54

Jiří Neubauer

x10 1 0 0 1 0 0

x20 0 1 0 − 12 1 4 3 4

bi 1000 1100 0 450 275 825

βi αik

500 275 max 100 1100 max



Příklad PRIMÁRNÍ ÚLOHA báze x10 x20 z x10 x1 z x2 x1 z

x1 2 4 −3 0 1 0 0 1 0

18 4 1 4 − 54

x10 1 0 0 1 0 0

x20 0 1 0 − 12

1 0 0

2 9

1 − 18 5 18

− 91

x2 5 1 −2

Jiří Neubauer

1 4 3 4

5 18 11 18

bi 1000 1100 0 450 275 825 100 250 950

βi αik

500 275 max 100 1100 max

max



Příklad PRIMÁRNÍ ÚLOHA báze x10 x20 z x10 x1 z x2 x1 z

x1 2 4 −3 0 1 0 0 1 0

18 4 1 4 − 54

x10 1 0 0 1 0 0

x20 0 1 0 − 12

1 0 0

2 9

1 − 18 5 18

− 91

x2 5 1 −2

1 4 3 4

5 18 11 18

bi 1000 1100 0 450 275 825 100 250 950

βi αik

500 275 max 100 1100 max

max

Optimální řešení je ~x = (250, 100, 0, 0), zmax = 950. Jiří Neubauer



Příklad

DUÁLNÍ ÚLOHA báze u100 u200 f f0

u1 2 5 −1000 7

u2 4 1 −1100 5

Jiří Neubauer

u10 −1 0 0 −1

u20 0 −1 0 −1

u100 1 0 0 0

u200 0 1 0 0


bi 3 2 0 5

βi αik

min min


Příklad


u1 2 5 −1000 7

u2 4 1 −1100 5

Jiří Neubauer

u10 −1 0 0 −1

u20 0 −1 0 −1

u100 1 0 0 0

u200 0 1 0 0


bi 3 2 0 5

βi αik

min min


Příklad


u1 2 5 −1000 7

u2 4 1 −1100 5

Jiří Neubauer

u10 −1 0 0 −1

u20 0 −1 0 −1

u100 1 0 0 0

u200 0 1 0 0


bi 3 2 0 5

βi αik 3 2 2 5

min min


Příklad


u1 2 5 −1000 7

u2 4 1 −1100 5

Jiří Neubauer

u10 −1 0 0 −1

u20 0 −1 0 −1

u100 1 0 0 0

u200 0 1 0 0


bi 3 2 0 5

βi αik 3 2 2 5

min min


Příklad DUÁLNÍ ÚLOHA báze u100 u200 f f0 u100 u1 f f0

u1 2 5 −1000 7 0 1 0 0

u2 4 1 −1100 5 18 5 1 5

−900 18 5

u10 −1 0 0 −1 −1 0 0 −1

Jiří Neubauer

u20 0 −1 0 −1 2 5

− 51 −200 2 5

u100 1 0 0 0 1 0 0 0

u200 0 1 0 0 − 25

bi 3 2 0 5

200 − 75

400

1 5


βi αik 3 2 2 5

min min

11 5 2 5 11 5

min min



u1 2 5 −1000 7 0 1 0 0

u2 4 1 −1100 5 18 5 1 5

−900 18 5

u10 −1 0 0 −1 −1 0 0 −1

Jiří Neubauer

u20 0 −1 0 −1 2 5

− 51 −200 2 5

u100 1 0 0 0 1 0 0 0

u200 0 1 0 0 − 25

bi 3 2 0 5

200 − 75

400

1 5


βi αik 3 2 2 5

min min

11 5 2 5 11 5

min min



u1 2 5 −1000 7 0 1 0 0

u2 4 1 −1100 5 18 5 1 5

−900 18 5

u10 −1 0 0 −1 −1 0 0 −1

Jiří Neubauer

u20 0 −1 0 −1 2 5

− 51 −200 2 5

u100 1 0 0 0 1 0 0 0

u200 0 1 0 0 − 25

bi 3 2 0 5

200 − 75

400

1 5


11 5 2 5 11 5

βi αik 3 2 2 5

min min 11 18

2 min min



u1 2 5 −1000 7 0 1 0 0

u2 4 1 −1100 5 18 5 1 5

−900 18 5

u10 −1 0 0 −1 −1 0 0 −1

Jiří Neubauer

u20 0 −1 0 −1 2 5

− 51 −200 2 5

u100 1 0 0 0 1 0 0 0

u200 0 1 0 0 − 25

bi 3 2 0 5

200 − 75

400

1 5


11 5 2 5 11 5

βi αik 3 2 2 5

min min 11 18

2 min min


Příklad DUÁLNÍ ÚLOHA báze u100 u200 f f0 u100 u1 f f0 u2 u1 f f0

u1 2 5 −1000 7 0 1 0 0 0 1 0 0

u2 4 1 −1100 5 18 5 1 5

−900 18 5

1 0 0 0

Optimální řešení je ~u =

u10 −1 0 0 −1 −1 0 0 −1 5 − 18

u20 0 −1 0 −1 2 5

− 15 −200

u100 1 0 0 0 1 0 0 0

1 18

2 5 2 18 4 − 18

5 18 1 − 18

−250 0

−100 0

250 −1

5 11 18 , 18 , 0, 0

Jiří Neubauer

u200 0 1 0 0 − 25

bi 3 2 0 5

200 − 75 2 − 18

400

4 18

11 5 11 18 5 18

100 −1

950 0

1 5

, fmin = 950.


11 5 2 5

βi αik 3 2 2 5

min min 11 18

2 min min

min min



Věta o dualitě Má-li jedna z dvojice duálně sdružených úloh lineárního programování optimální řešení, pak má i druhá úloha optimální řešení a hodnoty účelových funkcí (pro tato optimální řešení) jsou stejné. Řešení duální úlohy lze vyvodit i z posledního kroku simplexové tabulky primární úlohy. Podobně, na základě reflexivity duality platí, že optimální řešení primární úlohy lze určit z posledního kroku simplexové tabulky duální úlohy (obsahuje-li optimální řešení duální úlohy).

Jiří Neubauer




0 báze x1 . . . xn x10 . . . xm .. .. .. . . .

z

bi .. .

u10 . . . un0 u1 . . . um z = f

Tabulka: Řešení duální úlohy v řešení primární úlohy

báze u1 . . . um u10 . . . un0 .. .. .. . . . f

bi .. .

0 x ...x x10 . . . xm 1 n f =y

Tabulka: Řešení primární úlohy v řešení duální úlohy

Poznámka. Pokud je úloha minimalizační, je třeba koeficienty v anulované účelové rovnici vynásobit číslem (−1) a teprve pak je považovat za duální proměnné.

Jiří Neubauer



Příklad PRIMÁRNÍ ÚLOHA

báze x2 x1 z

x1 0 1 0

x20 − 19

bi 100 250 950

u20

bi

1 18

2 18 4 − 18

11 18 5 18

−250

−100

950

x2 1 0 0

x10 2 9

1 − 18

5 18 11 18

5 18

Optimální řešení je ~x = (250, 100, 0, 0), zmax = 950. DUÁLNÍ ÚLOHA

Optimální řešení je ~u =

báze u2 u1 f

u1 0 1 0

u2 1 0 0

5 11 18 , 18 , 0, 0

Jiří Neubauer

u10 5 − 18

, fmin = 950.



Dualita v úlohách LP Uveďme na tomto místě, jaké kombinace optimálních řešení (a jejich vlastností) duálně sdružených úloh jsou přípustné. Má-li primární úloha jediné optimální řešení, pak i duální úloha má jediné optimální řešení, a naopak. Má-li primární úloha alternativní řešení, pak optimální řešení duální úlohy je degenerované, a naopak. Nemá-li primární úloha konečné optimální řešení (tj. má přípustná řešení, ale účelová funkce může neomezeně růst, resp. klesat, podle toho, zda jde o maximalizační, resp. minimalizační, úlohu), pak duální úloha nemá žádné přípustné řešení, a naopak.

Jiří Neubauer



Příklad Podnik vyrábí dva druhy výrobku V1 a V2 . Tabulka udává spotřebu surovin S1 a S2 v kg na výrobu 1 ks výrobku V1 , resp. V2 , i disponibilní množství těchto surovin. Zisk z každého výrobku V1 je 3 Kč a z 1 ks V2 je 2 Kč.

S1 S2 zisk

Výrobky V1 V2 2 5 4 1 3 2

Disponibilní množství 1000 1100 max

Optimální výrobní plán podniku tak, aby dosáhl maximálního zisku, jsme již stanovili dříve. V tom případě se suroviny transformují na výrobky a ty se (se ziskem) prodávají. Zde ale uvažujme zcela jinak. Úkolem je sestavit úlohu (její matematický model), kdy nebudeme ze surovin vyrábět výrobky a ty prodávat, ale budeme prodávat přímo suroviny, které má podnik k dispozici. Jiří Neubauer



Ekonomická interpretace duální úlohy Uvažujme tedy přímý prodej surovin. Otázkou, která nás zajímá, je, jaké by musely být ceny surovin (a jakého nejmenšího možného zisku přitom dosáhneme), aby se jejich přímý prodej vyplatil. Označme tedy neznámou cenu jednotkového množství suroviny S1 symbolem u1 a neznámou cenu jednotkového množství suroviny S2 symbolem u2 . Prodejní cena celkového množství surovin je potom dána funkcí f = 1000u1 + 1100u2 . Aby se přímý prodej surovin vyplatil (proti transformaci surovin na výrobky), je třeba zajistit, aby se přímým prodejem surovin, potřebných pro výrobu 1 ks výrobku V1 , dosáhlo alespoň stejného zisku jako v případě jeho výroby a prodeje, tj. alespoň 3 Kč. Dostáváme podmínku 2u1 + 4u2 ≥ 3. Jiří Neubauer



Ekonomická interpretace duální úlohy Analogickou úvahou vzhledem k surovinám potřebných k výrobě výrobku V2 dospějeme k podmínce 5u1 + u2 ≥ 2. Ceny surovin uvažujeme nezáporné, tj. u1 ≥ 0, u2 ≥ 0. Dostáváme tedy model 2u1 + 4u2 ≥ 3 5u1 + u2 ≥ 2 f = 1000u1 + 1100u2 → min u1 ≥ 0, u2 ≥ 0 což je již řešená duální úloha LP. Jiří Neubauer


Dualita v úlohách LP Ekonomická interpretace duální úlohy. Jiří Neubauer. Katedra ekonometrie FEM UO Brno

Recommend Documents