Konvexní množiny Formulace úloh lineárního programování. Jiří Neubauer. Katedra ekonometrie FEM UO Brno

Konvexní množiny Formulace úloh lineárního programování

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

Jiří Neubauer

Základy operačního výzkumu


Euklidovský prostor En

Pod pojmem n-rozměrný euklidovský prostor budeme rozumnět prostor, jehož prvky jsou uspořádané n-tice reálných čísel X = (x1 , x2 , . . . , xn ), které budeme nazývat body.

Jiří Neubauer



Nadrovina

Nadrovinou nazveme množinu bodů X = (x1 , x2 , . . . , xn ) ∈ En , které vyhovují rovnici a1 x1 + a2 x2 + · · · + an xn = a0 .

Jiří Neubauer



Nadrovina Nadrovina N dělí prostor En na 3 disjunktní části: množina bodů P1 , pro něž platí a1 x1 + a2 x2 + · · · + an xn < a0

Jiří Neubauer

−→

otevřený poloprostor




−→


množina bodů N, pro něž platí a1 x1 + a2 x2 + · · · + an xn = a0

Jiří Neubauer

−→

nadrovina




−→


množina bodů N, pro něž platí a1 x1 + a2 x2 + · · · + an xn = a0

−→

nadrovina

množina bodů P2 , pro něž platí a1 x1 + a2 x2 + · · · + an xn > a0

Jiří Neubauer

−→




Příklad

Prostor E1 . . . nadrovinou je bod P1

A=5 N

P2

5

P1

x <5

polopřímka

N

x =5

nadrovina

P2

x >5

polopřímka

Jiří Neubauer



Příklad 3x1 − 2x2 = 12

Prostor E2 . . . nadrovinou je přímka x2 P2 4

x1

0 -6

P1 N P2

P1

3x1 − 2x2 > 12 polopřímka 3x1 − 2x2 = 12 přímka 3x1 − 2x2 < 12 polopřímka Jiří Neubauer



Příklad

Znázorněte v rovině množinu bodů splňující x1 + x2 ≤ 5 −2x1 + 4x2 ≤ 8 x1 ≥0

Jiří Neubauer



Přímka

Množina bodů X , pro které platí X = (1 − λ)A + λB, kde λ ∈ R, A, B ∈ En se nazývá přímka procházející body A, B.

Jiří Neubauer



Příklad Napište rovnici přímky procházející body A[1, 2] a B[0, −1]. X = (1 − λ)[1, 2] + λ[0, −1]

Jiří Neubauer



Příklad Napište rovnici přímky procházející body A[1, 2] a B[0, −1]. X = (1 − λ)[1, 2] + λ[0, −1] x2 Volbou λ = 12 dostaneme bod S = (1 − 12 )[1, 2] + 21 [0, −1] = 1 1 1 1 2 [1, 2] + 2 [0, −1] = [ 2 , 2 ]

A S 0

B

x1 Volbou λ = 2 dostaneme bod T = (1 − 2)[1, 2] + 2[0, −1] = −[1, 2] + 2[0, −1] = [−1, −4]

T Jiří Neubauer



Úsečka

Množina bodů X splňující X = (1 − λ)A + λB, kde λ ∈ h0, 1i, A, B ∈ En se nazývá úsečka spojující body A, B.

Jiří Neubauer



Konvexní množina Řekneme, že množina K ⊂ En je konvexní, obsahuje-li s každými 2 body A, B i úsečku spojující tyto body.

Jiří Neubauer



Konvexní množina Řekneme, že množina K ⊂ En je konvexní, obsahuje-li s každými 2 body A, B i úsečku spojující tyto body.

B A

konvexní množina Jiří Neubauer

nekonvexní množina Základy operačního výzkumu


Krajní bod

Bod X ∈ K ⊂ En se nazývá krajním bodem konvexní množiny K , neexistují-li 2 různé body A, B (přičemž X 6= A, X 6= B) takové, že bod X leží na úsečce AB.

Jiří Neubauer



Krajní bod

Bod X ∈ K ⊂ En se nazývá krajním bodem konvexní množiny K , neexistují-li 2 různé body A, B (přičemž X 6= A, X 6= B) takové, že bod X leží na úsečce AB. množina trojúhelník kruh kružnice

konvexnost ano ano ne

Jiří Neubauer

krajní body vrcholy kružnice –



Ohraničená a neohraničená množina

Konvexní množina K se nazývá ohraničená, neobsahuje-li žádnou polopřímku. Obsahuje-li alespoň 1 polopřímku, nazývá se neohraničená.

Jiří Neubauer



Věta o průniku

Průnik konvexních množin je opět konvexní množina.

Jiří Neubauer



Úloha výrobního plánování Podnik vyrábí 2 druhy výrobků V1 a V2 . Tabulka udává spotřebu surovin S1 a S2 v kg potřebných na výrobu 1 kusu výrobku. Zisk z 1 výrobku V1 je 18 Kč a z 1 výrobku V2 je 8 Kč. Dále je v tabulce uvedeno množství surovin, kterým podnik disponuje. Stanovte optimální výrobní plán, aby podnik dosáhl maximálního zisku. Ekonomický model S1 [kg/ks] S2 [kg/ks] zisk [Kč/ks]

Výrobky V1 V2 4 2 4 1 18 8

Jiří Neubauer

Disponibilní množství 2000 1600 max



Úloha výrobního plánování Matematický model: proměnné

x1 x2

... ...

počet výrobků V1 počet výrobků V2

výrobní plán ~x = (x1 , x2 )0 , kde x1 ≥ 0, x2 ≥ 0

Jiří Neubauer




x1 x2

... ...


výrobní plán ~x = (x1 , x2 )0 , kde x1 ≥ 0, x2 ≥ 0 např. ~x = (300, 100)0 Spotřeba surovin při tomto výrobním plánu bude S1 :

300 · 4 + 100 · 2 = 1400 kg < 2000

S2 :

300 · 4 + 100 · 1 = 1300 kg < 1600

Jiří Neubauer




x1 x2

... ...


výrobní plán ~x = (x1 , x2 )0 , kde x1 ≥ 0, x2 ≥ 0 např. ~x = (300, 100)0 Spotřeba surovin při tomto výrobním plánu bude S1 :

300 · 4 + 100 · 2 = 1400 kg < 2000

S2 :

300 · 4 + 100 · 1 = 1300 kg < 1600

Jedná se tedy o přípustné řešení úlohy LP. Zisk je 300 · 18 + 100 · 8 = 6200 Kč.

Jiří Neubauer



Úloha výrobního plánování

např. ~x = (250, 700)0 Spotřeba surovin při tomto výrobním plánu bude S1 :

250 · 4 + 700 · 2 = 2400 kg > 2000

S2 :

250 · 4 + 700 · 1 = 1700 kg > 1600

Jiří Neubauer




např. ~x = (250, 700)0 Spotřeba surovin při tomto výrobním plánu bude S1 :

250 · 4 + 700 · 2 = 2400 kg > 2000

S2 :

250 · 4 + 700 · 1 = 1700 kg > 1600

Jedná se tedy o nepřípustné řešení úlohy LP.

Jiří Neubauer




obecně ~x = (x1 , x2 )0 4x1 + 2x2 ≤ 2000 4x1 + x2 ≤ 1600

Jiří Neubauer




obecně ~x = (x1 , x2 )0 4x1 + 2x2 ≤ 2000 4x1 + x2 ≤ 1600 účelová funkce má tvar z(x1 , x2 ) = 18x1 + 8x2

−→ max

Taková úloha se označuje za maximalizační úlohu.

Jiří Neubauer



Úloha výrobního plánování Postup při řešení: soustavu lin. nerovnic přepíšeme na soustavu lin. rovnic 4x1 + 2x2 + x10 = 2000 4x1 + x2 + x20 = 1600 x1 ≥ 0, x2 ≥ 0, x10 ≥ 0, x20 ≥ 0

Jiří Neubauer



Úloha výrobního plánování Postup při řešení: soustavu lin. nerovnic přepíšeme na soustavu lin. rovnic 4x1 + 2x2 + x10 = 2000 4x1 + x2 + x20 = 1600 x1 ≥ 0, x2 ≥ 0, x10 ≥ 0, x20 ≥ 0 řešíme simplexovou případně grafickou metodou

Jiří Neubauer



Úloha výrobního plánování Postup při řešení: soustavu lin. nerovnic přepíšeme na soustavu lin. rovnic 4x1 + 2x2 + x10 = 2000 4x1 + x2 + x20 = 1600 x1 ≥ 0, x2 ≥ 0, x10 ≥ 0, x20 ≥ 0 řešíme simplexovou případně grafickou metodou optimální řešení je ~x = (300, 400, 0, 0)0 , což znamená, že z hlediska maximalizace zisku je třeba vyrobit 300 ks výrobků V1 a 400 ks výrobků V2 , přičemž se spotřebuje veškerá surovina S1 a S2 (x10 = 0, x20 = 0). Dosáhne se zisku z = 300 · 18 + 400 · 8 = 8600 Kč.

Jiří Neubauer



Směšovací úloha Podnik má vytvořit krmnou směs, která by obsahovala alespoň 308 mg vápníku a 214 mg hořčíku. Používají přitom 2 typů krmiv: 1 kg krmiva K1 obsahuje 10 mg Ca a 8 mg Mg a stojí 1500 Kč

Jiří Neubauer



Směšovací úloha Podnik má vytvořit krmnou směs, která by obsahovala alespoň 308 mg vápníku a 214 mg hořčíku. Používají přitom 2 typů krmiv: 1 kg krmiva K1 obsahuje 10 mg Ca a 8 mg Mg a stojí 1500 Kč 1 kg krmiva K2 obsahuje 8 mg Ca a 1 mg Mg a stojí 240 Kč

Jiří Neubauer



Směšovací úloha Podnik má vytvořit krmnou směs, která by obsahovala alespoň 308 mg vápníku a 214 mg hořčíku. Používají přitom 2 typů krmiv: 1 kg krmiva K1 obsahuje 10 mg Ca a 8 mg Mg a stojí 1500 Kč 1 kg krmiva K2 obsahuje 8 mg Ca a 1 mg Mg a stojí 240 Kč Úkolem je připravit co možná nejlevnější krmnou směs.

Ca [mg/kg] Mg [mg/kg] cena [Kč/kg]

Krmivo K1 K2 10 8 8 1 1500 240

Jiří Neubauer

Požadované množství 308 214 min



Směšovací úloha

Matematický model: proměnné

x1 x2

... ...

množství krmiva K1 ve výsledné směsi množství krmiva K2 ve výsledné směsi

výrobní plán ~x = (x1 , x2 )0 , kde x1 ≥ 0, x2 ≥ 0

Jiří Neubauer



Směšovací úloha

Matematický model: proměnné

x1 x2

... ...

množství krmiva K1 ve výsledné směsi množství krmiva K2 ve výsledné směsi

výrobní plán ~x = (x1 , x2 )0 , kde x1 ≥ 0, x2 ≥ 0 Použijeme-li x1 kg krmiva K1 a x2 krmiva K2 , bude ve výsledné směsi Ca : 10x1 + 8x2 Mg : 8x1 + x2

Jiří Neubauer



Směšovací úloha

Vlastní omezení mají tvar 10x1 + 8x2 ≥ 308 8x1 + x2 ≥ 214

Jiří Neubauer



Směšovací úloha

Vlastní omezení mají tvar 10x1 + 8x2 ≥ 308 8x1 + x2 ≥ 214 Celková cena směsi je dána účelovou funkcí z = 1500x1 + 240x2 −→ min Jedná se o minimalizační úlohu.

Jiří Neubauer



Rozdělovací úloha Máme dostatečné množství základních lan o délce 32 m. K dalšímu použití potřebujeme alespoň 12 kusů 20 m lan, 20 kusů 11 m lan a 26 kusů 6 m lan. Určete optimální skladbu řezných plánů vzhledem k minimálnímu odpadu.

Jiří Neubauer



Rozdělovací úloha Máme dostatečné množství základních lan o délce 32 m. K dalšímu použití potřebujeme alespoň 12 kusů 20 m lan, 20 kusů 11 m lan a 26 kusů 6 m lan. Určete optimální skladbu řezných plánů vzhledem k minimálnímu odpadu.

20 m 11 m 6m odpad [m]

I. 1 1 0 1

Řezný plán II. III. IV. 1 0 0 0 2 1 2 1 3 0 4 3

Jiří Neubauer

V. 0 0 5 2

Požadované množství 12 20 26 min



Rozdělovací úloha

Proměnné x1 , . . . , x5 Proměnná xj , j = 1, 2, 3, 4, 5 udává počet základních lan rozřezaných podle řezného plánu j, xj ≥ 0.

Jiří Neubauer




Proměnné x1 , . . . , x5 Proměnná xj , j = 1, 2, 3, 4, 5 udává počet základních lan rozřezaných podle řezného plánu j, xj ≥ 0. Rozřežeme-li x1 lan podle řezného plánu I., . . . , x5 lan podle řezného plánu V., nařežeme x1 + x2

ks 20 m lan

Jiří Neubauer




Proměnné x1 , . . . , x5 Proměnná xj , j = 1, 2, 3, 4, 5 udává počet základních lan rozřezaných podle řezného plánu j, xj ≥ 0. Rozřežeme-li x1 lan podle řezného plánu I., . . . , x5 lan podle řezného plánu V., nařežeme x1 + x2 x1 + 2x3 + x4

Jiří Neubauer

ks 20 m lan ks 11 m lan




Proměnné x1 , . . . , x5 Proměnná xj , j = 1, 2, 3, 4, 5 udává počet základních lan rozřezaných podle řezného plánu j, xj ≥ 0. Rozřežeme-li x1 lan podle řezného plánu I., . . . , x5 lan podle řezného plánu V., nařežeme x1 + x2 ks 20 m lan x1 + 2x3 + x4 ks 11 m lan 2x2 + x3 + 3x4 + 5x5 ks 6 m lan

Jiří Neubauer




x1 + x2 ≥ 12 x1 + 2x3 + x4 ≥ 20 2x2 + x3 + 3x4 + 5x5 ≥ 26 x1 ≥ 0, . . . , x5 ≥ 0

Jiří Neubauer




x1 + x2 ≥ 12 x1 + 2x3 + x4 ≥ 20 2x2 + x3 + 3x4 + 5x5 ≥ 26 x1 ≥ 0, . . . , x5 ≥ 0 Celkový odpad určuje účelová funkce z = x1 + 4x3 + 3x4 + 2x5 −→ min

Jiří Neubauer


Konvexní množiny Formulace úloh lineárního programování. Jiří Neubauer. Katedra ekonometrie FEM UO Brno

Recommend Documents