Lineární programování II. Ivan Nagy, Pavla Pecherková

Lineární programování II

Ivan Nagy, Pavla Pecherková

Obsah 1 Lineární programování

4

1.1

Formulace úlohy

1.2

Algebraický model

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.3

Pojmy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.3.1

Duální úloha

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.3.2

Duální cena (dual price) . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.3.3

Redukované náklady (reduced cost)

. . . . . . . . . . . . . . . . . . . . .

5

Simplexová metoda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

1.4.1

P°íklad - °e²ení standardní simplexové úlohy

6

1.4.2

P°íklad - °e²ení nestandardní simplexové úlohy

1.4

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 Modely lineárního programování

4

8

12

2.1

Obecný p°íklad lineárního programování . . . . . . . . . . . . . . . . . . . . . . .

12

2.2

Optimální produkce - 2 výrobky

14

2.3

Optimální produkce s omezenými zdroji

. . . . . . . . . . . . . . . . . . . . . . .

16

2.4

Optimální produkce s výb¥rem surovin . . . . . . . . . . . . . . . . . . . . . . . .

18

2.5

Optimální míchání

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

2.5.1

Úloha £. 1 (krmná sm¥s) . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

2.5.2

Úloha £. 2 (optimální strava v¥z¬·) . . . . . . . . . . . . . . . . . . . . . .

19

2.6

2.7

2.8

Minimální tok náklad· v síti

. . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

2.6.1

Úloha £. 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21

2.6.2

Úloha £. 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

P°i°azovací dopravní problém . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

2.7.1

PDP °e²ený pomocí lineárního programování

. . . . . . . . . . . . . . . .

23

2.7.2

PDP °e²ený pomocí MCNF (min. cost network ow) . . . . . . . . . . . .

24

Nejkrat²í cesta grafem (pomocí MCNF) 1

. . . . . . . . . . . . . . . . . . . . . . .

25

2

OBSAH

3 Celo£íselné programování

26

3.1

Formulace úlohy

3.2

Formulace celo£íselných program·

3.3

3.4

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

3.2.1

Binární veli£iny . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

3.2.2

Aktivace omezení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

3.2.3

Výb¥r z mnoºiny omezení . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

3.2.4

Implikované omezení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

3.2.5

Alespo¬ k omezení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

3.2.6

Omezení na oblasti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

Modelování nelineárních funkci

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

3.3.1

Fixní náklady . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

3.3.2

Po £ástech lineární reprezentace . . . . . . . . . . . . . . . . . . . . . . . .

30

3.3.3

Aproximace nelineárních funkcí . . . . . . . . . . . . . . . . . . . . . . . .

31

3.3.4

Sou£in v kritériu

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

Metody °e²ení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

3.4.1

Metoda v¥tví a mezí (branch and bound)

. . . . . . . . . . . . . . . . . .

33

3.4.2

Metoda °ez· (cutting planes)

. . . . . . . . . . . . . . . . . . . . . . . . .

35

4 Modely celo£íselného programování 4.1

4.2

26

39

Výb¥r projektu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39

4.1.1

Rozpo£et kapitálu (Capital budgeting)[Hlavni text] . . . . . . . . . . . . .

39

4.1.2

Problém batohu [Nas text, Knapsack]

. . . . . . . . . . . . . . . . . . . .

40

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

41

4.2.1

Velikost dávky - bez kapacity[Kniha] . . . . . . . . . . . . . . . . . . . . .

41

4.2.2

Velikost dávky - s kapacitou [Kniha]

. . . . . . . . . . . . . . . . . . . . .

41

4.2.3

Produkce na odbyt [Kniha]

. . . . . . . . . . . . . . . . . . . . . . . . . .

42

4.2.4

Objednávka léku [3 p°íklady]

Plánování produkce

. . . . . . . . . . . . . . . . . . . . . . . . .

43

4.3

P°eprava s pevnou cenou [Kniha] . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

4.4

Problém investi£ního rozhodování [Nas text] . . . . . . . . . . . . . . . . . . . . .

44

4.5

Problém po²tovních box· [Nas text]

. . . . . . . . . . . . . . . . . . . . . . . . .

45

4.6

Propuknutí infek£ního onemocn¥ní [Nas text, 3 p°íklady] . . . . . . . . . . . . . .

46

4.6.1

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

47

Pokrytí mnoºin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

48

4.7.1

48

4.7

P°íklad

Pokrytí mnoºin - set covering [Kniha]

. . . . . . . . . . . . . . . . . . . .

3

OBSAH

4.7.2

Rozd¥lení a zabalení mnoºin (partitioning, packing) [Kniha] . . . . . . . .

49

4.7.3

Rozmíst¥ní sklad· (Warehouse location) [Nas text, Hlavni text] . . . . . .

50

4.8

Problém p°i°azení [Kniha] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

51

4.9

Problém °ezání [Kniha] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

52

4.9.1

ezání ty£í

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

52

4.9.2

ezání papíru . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

52

4.10 TSP - Problém obchodního cestujícího [Nas text, Kniha] . . . . . . . . . . . . . .

53

4.10.1 Asymetrický TSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

53

4.10.2 Symetrický TSP

55

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.10.3 TSP jako nelineární problém

. . . . . . . . . . . . . . . . . . . . . . . . .

57

4.11 Zobecn¥ní TSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

58

4.11.1 Nejkrat²í cesta grafem [Kniha]

. . . . . . . . . . . . . . . . . . . . . . . .

58

4.11.2 Nejkrat²í cesta grafem z daného uzlu . . . . . . . . . . . . . . . . . . . . .

59

4.11.3 TSP s opakovanými náv²t¥vami m¥st [Kniha] . . . . . . . . . . . . . . . .

59

4.11.4 TSP s klastry [Kniha]

60

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.12 Optimální po°adí úloh (machine sequencing) [Sheduling]

. . . . . . . . . . . . .

60

. . . . . . . . . . . . . . . . . .

60

. . . . . . . . . . . . . . . . . . . .

62

4.12.1 Plánování sm¥n pro obsluhu (Scheduling) 4.12.2 Obsazování let· posádkami [Nas text]

5 Programové vybavení 5.1

5.2

65

Excel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

65

5.1.1

e²itel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

65

5.1.2

Model v se²it¥ Excel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

65

5.1.3

Triky p°i práci v Excelu . . . . . . . . . . . . . . . . . . . . . . . . . . . .

66

5.1.4

P°íklad v excelu

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

67

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

69

LIPS????

Kapitola 1

Lineární programování 1.1

Formulace úlohy

Nalezn¥te hodnoty vektoru

x,

které

(i)

c0 x = c1 x1 + c2 x2 + ai,1 x1 + ai,2 x2 + · · · + ai,n xn ≤ bi , pro

maximalizují lineární kriterium

· · · + cn xn , (ii) spl¬ují vedlej²í podmínky Ax ≤ b, tedy i = 1, 2, · · · , m (m podmínek pro n prom¥nných) a (iii)

jsou nezáporné.

Zápis standardní úlohy je následující:

c0 x → max1 Ax ≤ b2 x ≥ 03

Poznámka Omezení vytvá°í simplex, na kterém se hledá optimum. Lineární kriterium tvo°í nadrovinu v prostorux,

1.2

J , kde J

je kritérium.. Extrém je ve vrcholu nebo na hranici nebo ute£e do nekone£na.

Algebraický model

1. Denice neznámých (rozhodovacích) veli£in V prvé °ad¥ musíme denovat veli£iny (a) spojité

x≥0

(b) diskrétní

x

které budeme optimalizovat. Ty mohou být:

- nap°. po£et ks vyráb¥ného produktu (lze vyrobit i £ást produktu),

x ≥ 0, x ∈ N

1 hledáme maximum 2 nep°ekro£íme limitující 3 hodnota je nezáporná

x,

- nap°. po£et za°ízení s rychlým ob£erstvením,

omezení (nap°íklad nem·ºeme vyrobit víc výrobk· neº na které máme materiál)

4

KAPITOLA 1.

5

LINEÁRNÍ PROGRAMOVÁNÍ

(c) binární

x ∈ {0, 1} , které nazýváme rozhodovací (0 ne, 1 ano) - nap°. ozna£ení investic

z ur£ité mnoºiny, které budou realizovány. 2. Denice kritéria Kritérium v¥t²inou vyjad°uje n¥co, co chceme maximalizovat (zisk) nebo minimalizovat

x, v¥t²inou ve P c0 x, tedy jako sou£in vektor· nebo matic ( j,j cij xij ). Prom¥nné c se £asto nazývají

(náklady, ztráty atd.). Je vyjád°eno jako funkce optimalizovaných veli£in form¥ ceny. 3. Denice omezujících podmínek

Vyjad°ují podmínky, za kterých má optimalizace probíhat. Nejb¥ºn¥j²í jsou (a) nezápornost

x≥0

nebo nezápornost celo£íselných neznámých

(b) omezení ve tvaru nerovností

Ax ≤ b,

kde matice

A

x ∈ N,

má rozm¥ry po£et omezení

×

po£et neznámých (c) a p°ípadn¥ dal²í, se kterými se postupn¥ setkáme v textu.

1.3

Pojmy

1.3.1 Duální úloha Ke kaºdé primární úloze

c'x → max

s omezením

Ax≤b, x≥0

resp.

c'x → min

s omezením

Ax ≥ b, x≥0

A0 y≥c, y≥0

resp.

b0 y → min

s omezením

A0 y ≤ c, y≥0

existuje tzv. duální úloha

b0 y → min

s omezením

která má dále r·zné vyuºití.

1.3.2 Duální cena (dual price) Kaºdé omezení má svou duální cenu. Je to p°ír·stek v hodnot¥ kriteria, který dostaneme, kdyº k pravé stran¥ omezení typu

≤

p°i£teme jedni£ku - omezení uvolníme o jedna. Jsou nenulové,

jen kdyº je omezení aktivní.

1.3.3 Redukované náklady (reduced cost) Je to informace o tom, o kolik by se musel zm¥nit koecient

cj , aby se veli£ina xj

tj. aby se tato prom¥nná se stala sou£ástí optimálního °e²ení.

stala efektivní,

KAPITOLA 1.

1.4

6


Simplexová metoda

Pro °e²ení základní úlohy lze vyuºít

simplexovou metodu,

která prochází vrcholy simplexu

omezení (v kaºdém kroku pozm¥ní °e²ení) tak, aby stále nar·stala hodnota kritéria. To znamená, ºe v kaºdém kroku se pozm¥ní °e²ní tak, aby hodnota funkce byla v¥t²í. V p°ípad¥, ºe ani po zm¥n¥ v dal²ím kroku nedojde k zvý²ení hodnoty kritéria, nalezené °e²ení uvaºujeme jako optimální. Simplexová metoda m·ºe být pouºita za p°edpokladu, ºe jsou spln¥ny základní podmínky:

1. maximalizujeme kritérium (minimaliza£ní úloha lze p°evést na maximaliza£ní pomocí vzorce

min f (x) = − max (−f (x))),

2. pravé strany musí být nezáporné,

≤,

3. omezující podmínky jsou vymezeny nerovnostmi typu 4. prom¥nné

x

jsou nezáporné.

P°i °e²ení simplexové úlohy se postupuje v n¥kolika krocích. Nejd°íve si ov¥°íme, zda platí základní podmínky (viz vý²e). Poté sestavíme simplexovou tabulku a následuje vlastní °e²ení úlohy, p°i£emº úloha se °e²í r·zn¥ podle toho, zda se jedná o standardní nebo nestandardní úlohu, tedy úlohu, kde není spln¥na podmínka o nezápornosti pravé strany nebo typu nerovnosti. Postup je ukázán samostatn¥ pro standardní a nestandardní úlohu.

1.4.1 P°íklad - °e²ení standardní simplexové úlohy Zadání úlohy: Ur£ete hodnoty prom¥nné

x = [x1 , x2 ],

kde

x1 ≥ 0, x2 ≥ 0,

která maximalizuje kritérium

J

J = c1 x1 + c2 x2 = 2x1 + 3x2 a vyhovuje podmínkám

x1 + x2

≤ 5

x1 + 2x2

≤ 8

Ov¥°ení platnosti základních podmínek: 1. maximalizujeme kritérium -

X

(ano,

2. pravé strany musí být nezáporné -

X

2x1 + 3x2 → max), (ano, £íslo

5i8

jsou kladná £ísla),

3. omezující podmínky jsou vymezeny nerovnostmi typu mínky jsou uvedeny znaménka 4. prom¥nné

x

jsou nezáporné -

≤

-

X(ano,

v obou rovnicích pod-

≤),

X

(v zadání je denováno, ºe

x1 ≥ 0, x2 ≥ 0).

KAPITOLA 1.

7


Zbavíme se nerovnosti a maxima: 1. Nerovnosti se zbavíme tak, ºe p°idáme dal²í £len, který bude vºdy kladný, v na²em p°ípad¥ bude rovnice vypadat takto:

x1 + x2 + s1

=

5

x1 + 2x2 + s2

=

8

2. Do simplexové tabulky pot°ebujeme také pouºít kritérium. Pokus bychom pouºili základní tvar, tedy v tomto p°ípad¥ stranu dát

∞.

2x1 +3x2 → max bylo by nutné do simplexové tabulky na pravou

Z tohoto d·vodu se upraví tento °ádek rovnice do tvaru

−2x1 − 3x2

=

0

Sestavení simplexové tabulky: x1

x2

s1

s2

RHS

-2

-3

0

0

0

1

1

1

0

5

1

2

0

1

8

←°ádek kritéria ←1. omezení ←2. omezení

Úprava simplexové tabulky: 1. Najdeme nejmen²í záporný koecient v °ádku kritéria

→klí£ový

sloupec.

Nejmen²í záporný koecient je koecient na kterém hodnota závisí nejvíce. V tomto p°ípad¥ je to tedy hodnota

−3

a tedy prom¥nná

x2 .

2. Pro kladné prvky v klí£ovém sloupci najdeme nejmen²í podíl pravé strany a prvku v klí£ovém sloupci

→klí£ový °ádek. V p°ípad¥, ºe je více klí£ových °ádk·, lze vybrat libovolný

z nich.

5 8 1 = 5, pro druhé omezení je to podíl 2 v °ádku s druhým omezením, a to bude tedy klí£ový °ádek. Pro první omezení je to podíl

= 4.

Men²í podíl je

3. Na pr·se£íku klí£ového sloupce a klí£ového °ádku leºí klí£ový prvek. V na²em p°ípad¥ je tedy klí£ový prvek £íslo

2.

4. Klí£ový °ádek celý vyd¥líme klí£ovým prvkem a ur£íme hodnotu klí£ového prvku. V na²em p°ípad¥ bude nový klí£ový °ádek

x1

x2

s1

s2

RHS

0,5

1

0

0,5

4

a klí£ový prvek bude

x2

=

1 1 4 − x1 − s2 2 2

KAPITOLA 1.

8


5. Do v²ech prvk· klí£ového sloupce (mimo klí£ového prvku) dosadíme hodnotu klí£ového prvku, tzn. vynulujeme ostatní prvky v klí£ovém sloupci) a upravíme simplexovou tabulku.

x1

x2

s1

s2

RHS

-0,5

0

0

1,5

12

-0,5

0

1

-0,5

1

0,5

1

0

0,5

4

V nové simplexové tabulce se hodnota kritéria

J

←°ádek kritéria ←1. omezení ←2. omezení zvý²ila na hodnotu

12. P°esto není °e²ení

je²t¥ ideální, protoºe v °ádku kritéria se dále objevuje záporný koecient. Z tohoto d·vodu budeme znovu upravovat simplexovou tabulku. 6. V p°ípad¥, ºe se v °ádku kritérií objevuje záporný koecient, opakuje se postup od bodu 1 a to do doby, neº jsou v²echny prvky v °ádku kritéria nezáporné. V na²em p°ípad¥, se simplexová tabulka upraví do následujícího tvaru

Výsledek: a

x2 = 3.

x1

x2

s1

s2

RHS

0

0

1

1

13

1

0

2

-1

2

0

1

-1

1

3

←°ádek kritéria ←1. omezení ←2. omezení

Optimálním °e²ení nalezené simplexovou metodou v tomto p°ípad¥ je pro

Hodnota kritéria

x1 = 2

J = 13.

1.4.2 P°íklad - °e²ení nestandardní simplexové úlohy V n¥kterých zadáních dojde k tomu, ºe nejsou spln¥né v²echny základní podmínky, viz 1.4. Obvykle se jedná o omezení vyºadující nezáporné £íslo na pravé stran¥ nebo o obrácenou nerovnost. V takovém p°ípad¥ se postupuje podle následujícího postupu (hlavní princip je stejný jako u standardní simplexové úlohy).

Zadání úlohy: Ur£ete hodnoty prom¥nné

x = [x1 , x2 ],

kde

x1 ≥ 0, x2 ≥ 0,


J = c1 x1 + c2 x2 = 2x1 + 3x2 a vyhovuje podmínkám

x1 + x2

≤ 5

x1 + 2x2

≤ 8

−2x1 + x2

≤

−4

J

KAPITOLA 1.

9


Ov¥°ení platnosti základních podmínek: X

1. maximalizujeme kritérium -

(ano,

2. pravé strany musí být nezáporné -

×

2x1 + 3x2 → max), (NE, £íslo

−4

je záporné),

≤- X(ano,

3. omezující podmínky jsou vymezeny nerovnostmi typu mínky jsou uvedeny znaménka 4. prom¥nné

x

jsou nezáporné -

v obou rovnicích pod-

≤),

X

(v zadání je denováno, ºe

x1 ≥ 0, x2 ≥ 0).

Úprava nespln¥né podmínky: 1. ádek, kde je záporná hodnota vynásobíme £íslem

−2x1 + x2 2x1 − x2

≤

−1.

−4 / · (−1)

≥ 4

2. V tuto chvíli jsme splnili ze základních podmínek (1.4) druhou podmínku, ale zase není spln¥na podmínka t°etí, tedy levá strana je

≤neº

strana pravá. Nerovnici vyrovnáme p°i-

dáním dal²ích pomocných prom¥nných. 3. Nerovnosti se zbavíme tak, ºe p°idáme dal²í £len, který bude vºdy kladný, v na²em p°ípad¥ bude rovnice vypadat takto:

kde

xA

xA

x1 + x2 + s1 + xA

=

5

x1 + 2x2 + s2

=

8

2x1 − x2 + s3 − xA

=

4

je pomocná prom¥nná, která zajistí, ºe se vliv na °e²ení vynuluje. Prom¥nné

si

i

jsou nezáporné.

4. Do simplexové tabulky pot°ebujeme také pouºít kritérium. Pokus bychom pouºili základní tvar, tedy v tomto p°ípad¥ stranu dát

∞.

2x1 +3x2 → max bylo by nutné do simplexové tabulky na pravou

Z tohoto d·vodu se upraví tento °ádek rovnice do tvaru

−2x1 − 3x2

=

0

Sestavení simplexové tabulky: x1

x2

s1

s2

s3

xA

RHS

-2

-3

0

0

0

1

0

1

1

1

0

0

0

5

1

2

0

1

0

0

8

2

-1

0

0

-1

1

4

←°ádek kritéria ←1. omezení ←2. omezení ←3. omezení

KAPITOLA 1.

10


Úprava simplexové tabulky: 1. e²íme celý problém pro kritérium

z = xA → max xA = 1

(a) vynulujeme °ádek kritéria, necháme pouze

x1

x2

s1

s2

s3

xA

RHS

0

0

0

0

0

1

0

1

1

1

0

0

0

5

1

2

0

1

0

0

8

2

-1

0

0

-1

1

4

(°e²íme pro

c = 0,

tj.

min z = xA


(b) omezení, kde bylo opa£né znaménko (nespl¬ující základní podmínku) ode£teme od °ádku kritéria,

x1

x2

s1

s2

s3

xA

RHS

-2

1

0

0

1

0

0

1

1

1

0

0

0

5

1

2

0

1

0

0

8

2

-1

0

0

-1

1

4

(c) v míst¥, kde je v °ádku kritéria u prom¥nných


xi

záporná hodnota - tento sloupe£ek

je nutno vynulovat - klí£ový sloupec. Postupujeme jako p°i standardní úloze a pro omezení v klí£ovém sloupci najdeme nejmen²í podíl pravé strany a prvku v klí£ovém sloupci

→klí£ový

°ádek.

x1 kde je hodnota −2. Pro první omezení je to 5 8 = 5 , pro druhé omezení je to podíl 1 1 = 4 a pro t°etí omezení je to podíl 2. Men²í podíl je v °ádku s t°etím omezením, a to bude tedy klí£ový °ádek.

V na²em p°ípad¥ je klí£ový sloupec podíl

4 2 = V na²em p°ípad¥ bude nový klí£ový °ádek

x1

x2

s1

s2

s3

xA

RHS

2

-1

0

0

-1

1

4

a klí£ový prvek bude

x1

1 1 1 2 + x2 + s3 − xA 2 2 2

=

Výsledná tabulka pak bude

x1

x2

s1

s2

s3

xA

RHS

0

0

0

0

0

1

4

0

1,5

1

0

0,5

-0,5

3

0

2,5

0

1

0,5

-0,5

6

1

-0,5

0

0

-0,5

0,5

2


2. Ve výsledné tabulce nahradíme °ádek kritéria p·vodním a vynecháme sloupec s cal variable).

x1

x2

s1

s2

s3

RHS

-2

-3

0

0

0

0

0

1,5

1

0

0,5

3

0

2,5

0

1

0,5

6

1

-0,5

0

0

-0,5

2


xA

(arti-

KAPITOLA 1.

11


3. Pokra£ujeme jako u standardní úlohy, viz 1.4.1. V na²em p°ípad¥ bude °e²ení následující: (a) klí£ový °ádek

(b) klí£ový °ádek

Výsledek: x2 = 3

a

x2 ...

hledání minimálního podílu: 1. omezení

x1

x2

s1

s2

s3

RHS

-2

0

2

0

1

6

0

1

0

0

1

0

1 3 1 3 − 31

2

0

2 3 − 53 1 3

x1 ...

1 0

1 3


hledání minimálního podílu: 3. omezení

x1

x2

s1

s2

s3

RHS

0

0

0

1

0

0

1

0

1 3 1 3 1 3 − 13

12

0

2 3 2 3 − 53 1 3 2

0 1 0

2 1 3

=2

=3


Optimálním °e²ení nalezené simplexovou metodou v tomto p°ípad¥ je pro

s2 = 1.

Hodnota kritéria

J = 12.

x 1 = 2,

Kapitola 2

Modely lineárního programování Optimaliza£ní úlohy lineárního programování se li²í podle cíle, kterého chceme dosáhnout. Jinak bude vypadat úloha, kde se maximalizuje zisk a jinak úloha, kde se minimalizují náklady. Proto bychom si p°ed za£átkem práce m¥li odpov¥d¥t na základní otázky: 1. co je cílem optimalizace (£eho chceme dosáhnout)? 2. co jsou °ídící veli£iny (jak m·ºeme ovlivnit cíl)? 3. co nás omezuje (jaké jsou na²e limity)? Odpov¥dí je n¥kolik a dají se rozd¥lit do n¥kolika model·. Práv¥ t¥mto model·m se bude v¥novat následující kapitola, kdy zde budou uvedeny základní optimaliza£ní úlohy. Ke kaºdé úloze bude uvedeno zadání, stru£né vysv¥tlení a p°ipojen odkaz na °e²ení v jednom z níºe uvedených program·.

2.1

Obecný p°íklad lineárního programování

Zadání úlohy: Ur£ete hodnoty prom¥nné

x = [x1 , x2 ],


J = c1 x1 + c2 x2 a vyhovuje podmínkám

3x1 + 5x2

≤ 15

2x1 + x2

≤ 8

x2

≤ 2

x1 ≥ 0, x2 ≥ 0 Zvolte váhy podle následujích varianty a vysv¥tlete výsledky: 12

KAPITOLA 2.

13

MODELY LINEÁRNÍHO PROGRAMOVÁNÍ

1.

c = [5, 1],

2.

c = [1, 1] ,

3.

c = [1, 3] ,

4.

c = [−1, 1].

e²ení gracké: Geometrická interpretace úlohy je na následujícím obrázku

x2 [0, 8]

criterion 3

criterion 3

direction of maximization

criterion 2 criterion 1

[0, 3] [5/3, 2] [0, 2] [6/7, 25/7] admissible

[4, 0]

[5, 0]

solutions

e²ení varianta 1-3: 1. pro simplexovou tabulku (ru£ní výpo£et)

x1

KAPITOLA 2.

14


5x1 + x2

→ max

x1 + x2

→ max

x1 + 3x2

→ max

3x1 + 5x2 + s1

=

15

3x1 + 5x2 + s1

=

15

3x1 + 5x2 + s1

=

15

2x1 + x2 + s2

=

8

2x1 + x2 + s2

=

8

2x1 + x2 + s2

=

8

x2 + s3

=

2

x2 + s3

=

2

x2 + s3

=

2

x1

≥

0

x1

≥

0

x1

≥

0

x2

≥

0

x2

≥

0

x2

≥

0

varianta 1

varianta 2

varianta 3

2. pro Excel (UvodniPriklad.xlsx)

varianta 1

varianta 2

varianta 3

V programu Excel se m¥ní pouze váha ceny (oranºové pozadí) bez zm¥ny podmínek. Hodnota kritéria (zelené pozadí) a hodnoty parametr·

xi

se vypo£tou po pu²t¥ní e²itele.

Výsledek je zobrazen naho°e v bu¬kách s modrým pozadím.

2.2

Optimální produkce - 2 výrobky

Zadání úlohy (1): V jednom podniku se vyrábí výrobky A a B. K jejich výrob¥ jsou zapot°ebí dva drahé stroje, jejichº vyuºití je omezeno a doba k výrob¥ jednotlivých výrobk· se li²í. Jednotlivé £asy jsou uvedeny v tabulce

Cílem je navrhnout produkci výrobk· A a B tak, aby byla maximální.

KAPITOLA 2.

15


Stroj

as stroj· pot°ebný na 1000 výrobk·

as stroj·

[h]

k vyuºití

Produkt A

Produkt B

1

4

6

24

2

4

2

12

[h]

Tabulka 2.1: Optimální produkce - dva výrobky

e²ení (1): Maximalizujeme kritérium

J kde

x1

x2

a

=

c1 x1 + c2 x2

je produkce výrobk· A a B v tisících a

c1 = c2 .

Formulace úlohy je tedy následující

x1 + x2 → max Dále sestavíme podmínky pro lineární programování

4x1 + 6x2

≤ 24

4x1 + 2x2

≤ 12

x1 ≥ 0, x2 ≥ 0

Excel: Podmínky zadáme do Excelu (produkce2Vyrobky.xlsx) Zadání úlohy (2): P°edchozí zadání úlohy (1) je roz²í°eno o znalost cen. Ceny výrobk· jsou nastaveny následovn¥:

c1 = 10

pro výrobek A a

c2 = 20

pro výrobek B. V tomto p°ípad¥ se jiº cena obou výrobk·

neshoduje a my chceme docílit maximálního zisku.

e²ení (2): Nové kritérium bude

10x1 + 20x2 → max kde

x1

a

x2


c1 = 10

Podmínky jsou stejné jako v p°edchozím zadání.

Excel: Podmínky zadáme do Excelu (produkce2Vyrobky.xlsx)

resp.

c2 = 20

je cena výrobku.

KAPITOLA 2.

16


Zadání úlohy (3): P°edchozí zadání úlohy (1) je roz²í°eno o novou informaci. Podnik podepsal dohodu s dodavatelem, ºe minimální produkce výrobk· bude 1 tisíc (nezapome¬te, ºe p·vodní produkce byla také v tisících). Náklady na výrobu jednotlivých výrobk· jsou

n1 = 5

a

n2 = 10.

Cílem je

minimalizovat výdaje.

e²ení (3): Nové kritérium bude

5x1 + 10x2 → min kde

x1

a

x2


n1 = 5

resp.

n2 = 10

je cena výrobku.

x1 ≥ 1, x2 ≥ 1 Dále sestavíme podmínky pro lineární programování

4x1 + 6x2

≤ 24

4x1 + 2x2

≤ 12

x1 ≥ 1, x2 ≥ 1 Na rozdíl od p·vodního zadání (1) je zde zakomponováno, ºe min. produkce je 1 (x1

≥ 1, x ≥ 1).

Excel: Podmínky zadáme do Excelu (produkce2Vyrobky.xlsx) 2.3

Optimální produkce s omezenými zdroji

Zadání úlohy: Továrna s dv¥ma provozy produkuje výrobek A (hliníková trubka), který se prodává samostatn¥ a nebo jako sou£ást pro výrobek B (dopravní zna£ka). Oba výrobky pot°ebují ur£itou surovinu S (Al plech), jejíº zdroj je omezen. Kolik suroviny resp. výrobk· A je pot°eba k výrob¥ výrobk· B je specikováno v tabulce:

Spot°eba

K dispozici

na jednotku produkce

celkem

pouºitý materiál

výrobek A

výrobek B

Surovina

5

2

3000

výrobek A

0

1

Cena produktu (v tis. K£)

5

10

× ×

KAPITOLA 2.


17

Vysv¥tlení tabulky: pro vyrobení výrobku A je pot°eba 5 surovin (k výrob¥ 1 hliníkové trubky je pot°eba 5 Al plech·), ale ºádný dal²í výrobek A. Pro vyrobení výrobku B je pot°eba 2 surovin a 1 výrobek A (k vyrobení celé zna£ky je krom¥ 2 Al plech· pot°eba je²t¥ hliníková trubka). Na sklad¥ je k dispozici 3000 ks surovin (Al plech·). Výrobek A se prodává za 5 000, výrobek B za 10 000. Dále byla stanovena podmínka, ºe na konci musíme mít min. 250 ks výrobk· A. Po£et výrobk· B není omezen. Poºadujeme:

1. maximální produkci, 2. maximální zisk.

e²ení : Podmínky jsou spole£né pro ob¥ variaty, tedy jak pro maximální produkci tak pro maximální zisk

5x1 + 2x2 ≤ 3000

x1 − x2 ≥ 250

x1 ≥ 0, x2 ≥ 0

e²ení (1): Kritérium pro maximální produkci

x1 + x2 → max, x1

je po£et kus· A a

x2

pro B.

Excel: Podmínky zadáme do Excelu (produkceSeSurovinou.xlsx) e²ení (2): Kritérium pro maximální zisk

5x1 + 10x2 → max .

Excel: Podmínky zadáme do Excelu (produkceSeSurovinou.xlsx)

KAPITOLA 2.

2.4

18


Optimální produkce s výb¥rem surovin

Zadání úlohy: Továrna produkuje dva výrobky

B1

B2 . Na výrobu B1 pot°ebuje látku L1 , na B2 látku L2 . A1 , A2 , A3 a A4 , které je t°eba zakoupit. Kaºdá surovina

a

Tyto látky je moºno získat ze surovin

dá jiné mnoºství látek. a Specikace je v tabulce

Surovina

Látka

L1 L2

(pro (pro

B1 ) B2 )

Cena za surovinu

A1

A2

2

10

10 20

→ látka A3

Pot°ebné mnoºství

A4

látky

5

20

1000

1

1

×

2000

10

5

10

Vysv¥tlení tabulky: pro vyrobení látky L1 (resp. L2 ) pot°ebuje 2 (resp. 10) suroviny A2 nebo 10 (resp. 1) surovin A2 nebo 5 (resp. 1) surovin A3 nebo 20 surovin A4 . Víme, ºe pot°ebujeme nakoupit takové mnoºství surovin, abych vyrobili min. 1000 látky

A3 a

10 pro

L1 resp.

2000 látky

L2 .

Cena za surovinu je 20 pro

A1 ,

10 pro

A2 ,

5 pro

A4 .

Cílem je navrhnout koupi surovin tak, abychom minimalizovali výdaje.

e²ení: Kritérium pro minimální výdaje

20x1 + 10x2 + 5x3 + 10x4 → min kde

x1 , x2 , ...

jsou navrhovaná mnoºství zakoupených surovin.

Dále sestavíme podmínky pro lineární programování

2x1 + 10x2 + 5x3 + 20x4

≥ 1000

10x1 + 5x2 + x3

≥ 2000

Excel: Podmínky zadáme do Excelu (VyberSurovinNaVyrobu.xlsx) 2.5

Optimální míchání

2.5.1 Úloha £. 1 (krmná sm¥s) Zadání úlohy: Pro výkrm jednoho kusu dobytka je zapot°ebí 2.5 kg krmné sm¥si a 240 g protein· na den. Pro krmení se pouºívá píce a kuku°ice. Dal²í specikace jsou v tabulce

KAPITOLA 2.

19


Krmivo

krmná sm¥s/kg krmiva

proteiny/kg krmiva

cena K£/kg

Píce (x1 kg)

1

0.4

0.5

Kuku°ice (x2 kg)

1.25

0.08

0.4

Pot°ebné mnoºství

2.5

0.24

Vysv¥tlení tabulky: Z jednoho kg píce se získá 1 kg krmné sm¥si a 400 g protein·. Z jednoho kg píce se získá 1.25 kg krmné sm¥si a 80 g protein·. Cena jednoho kg píce je 0.50 K£ a kuku°ice 0.40 K£. Cílem je vytvo°it takovou krmnou sm¥s, která bude za spln¥ní poºadovaných podmínek nejlevn¥j²í.


0.5x1 + 0.4x2 → min kde

x1

zna£í mnoºství píce,

x2

mnoºství kuku°ice.


x1 + 1.25x2 0.4x1 + 0.08x2

≥ 2.5 ≥ 0.24

V p°ípad¥, ºe nechceme ºádné zbytky, budeme mít p°esné mnoºství, místo ménko

≥

pouºijeme zna-

=.

Excel: Podmínky zadáme do Excelu (KrmnaSmes.xlsx)

2.5.2 Úloha £. 2 (optimální strava v¥z¬·) Zadání úlohy: Ve v¥zení navrhují optimální stravu v¥z¬·. Cht¥jí ji kombinovat z mléka, fazolí a pomeran£·. P°i tom je t°eba dodrºet minimální poºadavky na obsah stravy podle zákona. Jedna se o vitaminy:

B3 , B1

a

C.

Obsah t¥chto vitamin· v jednotlivých sloºkách stravy je následující mléko

[l]

fazole

[100 g]

pomeran£e

[1 ks]

poºadavek

B3 B1 C

3.2

4.9

0.8

13

1.12

1.3

0.19

1.5

32

0

93

45

cena (v $)

2

0.2

0.25

Vysv¥tlení tabulky: Z jednoho mléka se získá 3.2 vitamínu B3 , 1.12 vitamínu B1 a 32 vitamínu C . Obdobn¥ je to pro 100g fazolí a pomeran£·. Cena za sklenici mléka je 2 $, za 100g fazolí je to 0.2 $ a za 1 ks pomeran£e je to 0.25 $. Aby byly spln¥ny zákonné poºadavky je nutné dodat 13 jednotek vitamínu B3 , 1.5 jednotek vitamínu B1 a 45 jednotek vitamínu C. Cílem je namíchat stravu tak, aby její cena byla co nejmen²í a zárove¬ byl spln¥n zákon?

1 hodnoty

vitamín· i cena je pouze orienta£ní a neodráºí skute£nost.

1

KAPITOLA 2.

20



2x1 + 0.2x2 + 0.25x3 → min kde

x1

zna£í mnoºství mléka,

x2

mnoºství fazolí a

x3 mnoºství

pomeran£·.


3.2x1 + 4.9x2 + 0.8x3 1.12x1 + 1.3x2 + 0.19x3 32x1 +

+ 93x3

≥ 13 ≥ 1.15 ≥ 45

V p°ípad¥, ºe chceme p°esné zákonné hodnoty, tak místo

≥

pouºijeme znaménko

=.

Excel: Podmínky zadáme do Excelu (?????.xlsx) 2.6

Minimální tok náklad· v síti

Minimum Cost Network Flow Problem (MCNF) Je dána sí´ (souvislý, orientovaný, acyklický graf s jedním vstupem a jedním výstupem) s uzly a

n

hranami. Písmenem

bi

i, tj. bi < 0

ozna£íme zásobu v uzlu

m

výstupní tok - vstupní tok.

bi > 0 jedná se o zásobovací uzel (zdroj), pro jde o uzel s poºadavkem (cíl) a bi = 0 máme uzel pr·jezdní. S kaºdou hranou je spojena dolní mez Lij a horní mez Uij toku touto hranou. Cílem je ur£it velikosti tok· xij v jednotlivých hranách grafu tak, aby náklady na p°epravu byly minimální, jestliºe jednotková cena transportu po hran¥ ij je cij . P P°edpokládáme, ºe platí i bi = 0 (vyrovnané zdroje a poºadavky).

Jestliºe je pro

e²ení Pomocí LP

X

cij xij → min

ij

X j

xkj −

X

xik = bk , ∀k

i

xij ≤ Uij , xij ≥ Lij , 0 ≤ Lij ≤ Uij , ∀i, j

Poznámka c

a

x

jsou £tvercové matice kde °ádky i sloupce jsou indexovány uzly. Prvky t¥chto matic odpo-

vídají hranám grafu. V¥t²inou ne v²echny hrany existují. Neexistující hrany vyplníme nulami. Jako m¥nící se bu¬ky v Excelu zadáme jen existující hrany - nejlépe vytaºené mimo do vektoru. Pro kriterium i podmínky pr·toku m·ºeme pouºít cele matice (i prvky odpovídajícími neexistujícím hranám - jsou to nuly). Podmínky pr·toku konstruujeme jakoby pro diagonálu matice

x

a d¥láme sum(°ádek)-sum(sloupec), kde v °ádcích xujeme (F4) písmenka a ve sloupcích £ísla adres. Pak lze kopírovat. V²e je vid¥t v Excelu.

KAPITOLA 2.

21


2.6.1 Úloha £. 1 Zadání úlohy: Ze skladu (1) pot°ebujeme dovést zboºí do výrobního závodu (7). K výrob¥ pot°ebujeme 150 výrobk· a m·ºeme je poslat pomocí vlaku nebo nákladního automobilu nebo kombinací t¥chto doprav.. Jedna cesta je kapacitn¥ omezena na 80 ks. Máme následující graf (vlevo), který doplníme zp¥tnou hranou s nulovým ohodnocením (vpravo)

4

4 2

2 zdroj

zdroj

cíl 5

1

cíl 5

1

7

7

3

3

6

6

Uzel 1 je zdrojový se zásobou 150 jednotek toku, uzel 7 je cílový, tj. poºadující 150 jednotek toku. Ostatní uzly jsou p°epravní. Ceny za p°epravu jednotky toku jsou dány v tabulce (matici)

startovní uzel

cílový uzel 1 2 3 4 5 6 7

1

2

3

4

5

6

7

0 0 0 0 0 0 x71

x12 0 0 0 0 0 0

x13 0 0 0 0 0 0

0 x24 x34 0 0 0 0

0 x25 x35 0 0 0 0

0 x26 x36 0 0 0 0

0 0 0 x47 x57 x67 0

Tabulka 2.2: Tabulka jednotek toku

cílový uzel

startovní uzel

1

4

5

6

2

14

18

32

3

9

7

12

1

2

3

5

21

7

4

31

5

29

6 7

35 0

Tabulka 2.3: Tabulka ceny p°epravy hrana

(7, 1)

je zp¥tná s cenou 0. Nepouºité hrany mají nulové ohodnocení (bez ohodnocení).

Maximální kapacita byla zadána jako 80, minimální jako 0.

KAPITOLA 2.

22


e²ení: Kritérium

7 X 7 X

cij xij → min

i=1 j=1 Podmínky konstruujeme pro kaºdý uzel. Jdeme po diagonále - to je a ode£teme

k -tý

°ádek. To se rovná

bk , k = 1, 2, · · · , 7.

k,

a se£teme

k -tý

sloupec

Protoºe jsme doplnili 0, m·ºeme d¥lat

sou£ty vºdy od 1 do 7.

X i

xki −

X

xjk = bk

j

k a °íká, ºe to co p°iteklo minus k -tém prvku diagonály matice x k -tém sloupci rovná se bk .

coº se týká uzlu

to co odteklo je to, co z·stalo (ve skladu). V

Excelu: jsme na

a d¥láme: sou£et prvk· v

sou£et prvku v

Dal²í podmínky jsou

xij ≥ L, xij ≤ U,

p°ípadn¥

k -tém

°ádku minus

xij ≥ 0, xij ≤ U 2 .

Excel: Podmínky zadáme do Excelu (minCostFlow1.xlsx)

2.6.2 Úloha £. 2 Zadání úlohy: Je dáno 9 uzl· podle obrázku

zdroj

cíl zdroj

zdroj

umely uzel

cíl zdroj zpetna hrana

jejichº ohodnocení (cena) je uvedeno v následující tabulce V tomto p°ípad¥ jsou zde 4 zdroje, tzn. 4 uzly jsou zdrojové. Jmenovit¥ se jedná o uzly 1 - 4. Poºadavky jsou 2, tzn. 2 uzly jsou cílové, jmenovit¥ se jedná o uzly 8 a 9. Zásoba ve zdrojových uzlech je

2 Pozor:

Bude-li zadána p°íli² malá maximální kapacita hran, bude problém ne°e²itelný.

KAPITOLA 2.

23


1 1

2

3

4

5

8

4

2

9 8

3

9

4

5

5

6

5

5

7

7

4

6

5

3

4

9

5 6 7

2

8

9

9

8

7

9

3

7

Tabulka 2.4: MCNF - více zdroj· a cíl·

£íslo uzlu

1

2

3

4

zásoba

50

30

20

50

a poºadavky v cílových uzlech jsou £íslo uzlu poºadavek

3

8

9

-100

-50

se £ty°mi zdroji a dv¥ma poºadavky.

e²ení: Graf sám nemá jeden výstupní uzel. Aby se mohla zavést zp¥tná hrana, je t°eba denovat pomocný uzel s

b=0

do n¥hoº vedou pomocné hrany s nulovým ohodnocením. V tomto p°í-

pad¥ uzel £. 10. Ten se pak propojí se vstupem 1 (protoºe ten vede dále do ostatních vstup·). Ohodnocení hran bude u t¥chto nov¥ vytvo°ených hran rovno 0.

Excel: Podmínky zadáme do Excelu (minCostFlow2.xlsx) 2.7

P°i°azovací dopravní problém

Je dáno

z, kde i ∈ {1 · · · m} = M , jednotkami zboºí, a n cílových dj , j ∈ {1 · · · n} = N jednotkami poºadavk·. cij , i ∈ M, j ∈ N je jednotková p°evoz zboºí po hran¥ i, j a xij je mnoºství zboºí p°epravené po této hran¥. Chceme m

zdrojových uzl·, kaºdý s

uzl·, kaºdý s cena za

dosáhnout minima náklad· za p°evoz.

2.7.1 PDP °e²ený pomocí lineárního programování e²ení (1): Kritérium pro minimální náklady za p°evoz

X ij

cij xij → min

KAPITOLA 2.

24



X

xij = zi , ∀i

j

X

xij = dj , ∀j

i

xij ≥ 0, ∀ij Lze °e²it p°ímo pomocí LP.

Excel: Podmínky zadáme do Excelu (assignmenProbl.xlsx)

2.7.2 PDP °e²ený pomocí MCNF (min. cost network ow) e²ení (2): Lze °e²it jako MCNF vhodnou úpravou grafu: 1. P°i°adíme

bi = zi , i ∈ M

a

bm+j = −dj , j ∈ N .

2. Vytvo°íme pomocné uzly 0 a

m+n+1 sP nulovými cenami, zdroji i poºadavky P b0 = i bi , i ∈ M a poºadavky bm+n+1 = j bj , j ∈

(tohle je v textu ale nechodí to: zdroji

N ). 3. Uzel 0 spojíme hranami s uzly 1 aº

m

a uzly

m+1

aº

m+n

spojíme s uzlem

m + n + 1.

Tyto hrany mají nulová ohodnocení. 4. Zavedeme zp¥tnou hranu

(m + n + 1, 0)

rovn¥º s nulovým ohodnocením.

5. Ignorujeme horní meze tok· (horní meze m·ºeme a nemusíme zadat). Na takto modikovaný graf aplikujeme MCNF. Modikovaný graf je na obrázku.

b>0 1

b<0 m+1

0

m+n+1

P

P

i bi

j bj

m

m+n

Excel: Podmínky zadáme do Excelu (assignmenProblAsMCNF.xlsx)

KAPITOLA 2.

2.8

25


Nejkrat²í cesta grafem (pomocí MCNF)

Je dána ohodnocená sí´, kde ohodnocení

cij

interpretujeme jako délky jednotlivých hran

Úkol je najít nejkrat²í cestu ze zdrojového uzlu 1 do cílového uzlu

e²íme pomocí MCNF, kde uvaºujeme o p°eprav¥ jednotky toku z uzlu 1 do uzlu

Uij = 1, ∀ij

a

(i, j) .

m. m.

Poloºíme

bi = 0, ∀i.

P°íklad Uvaºujeme graf z obrázku

2

5 8

1

3 10

6 9

4

Hledáme nejkrat²í cestu z uzlu 1 do uzlu 7 (nebo z uzlu s

7

bi = 1 do uzlu s bj = −1) a vyuºíváme

k tomu metodu MCNF.

e²ení: Údaje a °e²ení jsou v programu.

Excel: Podmínky zadáme do Excelu (assignmenProblMinPath.xlsx)

Kapitola 3

Celo£íselné programování 3.1

Formulace úlohy

x, které (i) maximalizují lineární kriterium c0 x = c1 x1 + c2 x2 + · · · + cn xn , (ii) spl¬ují vedlej²í podmínky Ax ≤ b, tedy ai,1 x1 + ai,2 x2 + · · · + ai,n xn ≤ bi , pro i = 1, 2, · · · , m (m podmínek pro n prom¥nných) a (iii) jsou celo£íselné1 .

Nalezn¥te hodnoty vektoru

Zápis standardní úlohy celo£íselného programování je následující:

c0 x → opt2 Ax ≤ b3 x ≥ 0, x ∈ N4

3.2

Formulace celo£íselných program·

3.2.1 Binární veli£iny Binární veli£iny mohou nabývat dvou hodnot 0 nebo 1. Souvisí s rozhodováním: n¥co bude 1, nebo nebude Pokud máme

•

alespo¬

•

práv¥

•

nejvý²e

1 Tato

k

→

n

takových veli£in, lze realizovat jednu z následujících podmínek:

k

bude spln¥no (k nebo více):

bude spln¥no:

k

→

0.

Pn

i=1

Pn

i=1

xi ≥ k ,

xi = k ,

bude spln¥no (k nebo mén¥):

Pn

i=1

xi ≤ k .

úloha je prakticky stejná jako úloha lineárního programování, navíc se ale poºaduje, aby °e²ení

x

bylo

celo£íselné.

2 hledáme optimum 3 nep°ekro£íme limitující omezení (nap°íklad 4 hodnota je z oboru p°irozených £ísel

nem·ºeme vyrobit víc výrobk· neº na které máme materiál)

26

KAPITOLA 3.

27

CELOÍSELNÉ PROGRAMOVÁNÍ

3.2.2 Aktivace omezení y∈ {0, 1} a podmínku a0 x ≤ b. Víme dále, podmínky je B . Zkonstruujeme dal²í podmínku

Uvaºujme binární prom¥nnou levé strany

0

ax

této

ºe maximální hodnota

a0 x − By ≤ b. Tato podmínka °íká

•

je-li

y = 1,

pak p·vodní podmínka je vºdy spln¥na (podmínka je vy°azena)

max(a0 x) = B

⇒

a0 x − B · |{z} 1 ≤0 ⇒ 0≤b y=1

•

je-li

y = 0,

pak p·vodní podmínka z·stává v platnosti

a0 x − B · |{z} 0 ≤b

⇒ a0 x ≤ b.

y=0

Hodnota binární prom¥nné

y

tedy aktivuje nebo deaktivuje p·vodní podmínku

a0 x ≤ b.

3.2.3 Výb¥r z mnoºiny omezení Uvaºujme dv¥ podmínky

0

a1 x ≤ b1

0

a2 x ≤ b2

a

s maximálními hodnotami levých stran

B1

a

B2 .

Poºadujeme, aby alespo¬ jedna podmínka byla vºdy platná. Modelujeme takto 0

a1 x − B1 y1 0

a2 x − B2 y2 y1 + y2

≤ b1 ≤ b2 ≥ 1

5 nebo zavedeme ekvivalentní podmínku

y1 = y 0

a

y2 = 1 − y

a1 x − B1 y

≤ b1

0

a2 x − B2 (1 − y) ≤ b2

3.2.4 Implikované omezení Máme dv¥ omezení

0

a1 x > b1

i druhé (kdyº první neplatí,

0

a2 x ≤ b2 . Chceme aby platilo: kdyº platí první omezení, pak platí 6 7 tak nic). Toto pravidlo lze popsat implikací (⇒) nebo disjunkcí

a

(∨). Pro tu platí

5 Podmínka y + y ≥ 1 1 2

y1 = 1

a

y2 = 1.

°íká, ºe p°ipou²tíme následující moºnosti:

Tedy alespo¬ jedna podmínka je vºdy spln¥na.

6 spojení jestliºe-pak 7 spojka nebo

y1 = 1

a

y2 = 0

nebo

y1 = 0

a

y2 = 1

nebo

KAPITOLA 3.

28


Odtud vidíme, ºe

(a ⇒ b)

a

b

a⇒b

a0

b

a0 ∨ b

0

0

1

1

0

1

0

1

1

1

1

1

1

0

0

0

0

0

1

1

1

0

1

1

je stejné jako

(a0 ∨ b),

p°i£emº alternativu umíme - viz p°edchozí

odstavec. Nebo lze pouºít následující postup

Zadání úlohy: Vy°e²te implikaci

x≤4⇒y≤6

0 ≤ x ≤ 10 ⇒ 0 ≤ y ≤ 10

za podmínek

P1 : x ≥ 4 + 6z P2 : y ≤ 10 − 4 (1 − z) z ∈ {0, 1}

e²ení: Je-li x ≤ 4 pak z první P2 y ≤ 6 je aktivována. nastat

8.

podmínky Pro

x≤4

P1

plyne, ºe

m·ºe být

z

z = 1

a tedy

(1 − z) = 0.

Potom podmínka

0 nebo 1 a tedy druhá podmínka m·ºe a nemusí

3.2.5 Alespo¬ k omezení 0

ai x ≤ bi , i = 1, 2, · · · , n. Chceme, aby alespo¬ k z nich bylo spln¥no, tzn. ºe m·ºe být spln¥no k a více neº k . Postupujeme podle p°edchozích dvou odstavc·. Denujeme binární prom¥nné y1 , y2 , · · · , yn . P°i konstrukci omezení lze pouºít dv¥ varianty:

Máme

1.

n

omezení

0

ai x − Bi (1 − yi ) ≤ bi . Omezení

i

je v platnosti, jestliºe

yi = 0.

Pro alespo¬

n X

k

omezení v platnosti musí platit

k

omezení v platnosti musí platit

yi ≥ k,

i=1 2.

0

ai x − Bi yi ≤ bi Omezení

i

je v platnosti, jestliºe

yi = 0. n X

Pro alespo¬

yi

≤ n − k.

i=1

8 Místo

6 a -4 u prom¥nné

z

m·ºeme zvolit libovolné (v absolutní hodnot¥) v¥t²í £ísla. Tato zvolená £ísla

jsou p°esn¥ na hranici tak, abychom dosáhli poºadovaného efektu. P°íli² velká £ísla se ale nedoporu£ují, mohou zp·sobit potíºe p°i °e²ení.

KAPITOLA 3.

29


3.2.6 Omezení na oblasti Nech´ omezení tvo°í n¥kolik r·zných oblastí (disjunktních nebo i p°ekrývajících se). Jednotlivé oblasti jsou popsány pomocí lineárních omezení. Ukaºme si toto omezení na následujícím p°íklad¥, kdy platí:

0

0

0

0

0

a1 x ≤ b1 , a2 x ≤ b2 , a3 x ≤ b3

první oblast

a4 x ≤ b4 , a5 x ≤ b5

druhá oblast

... Chceme zaru£it, ºe optimální bod °e²ení bude leºet alespo¬ v jedné z oblastí. Modelujeme takto

1. oblast 0

a1 x − B1 y1 ≤ b1 , 0

a2 x − B2 y1 ≤ b2 , 0

a3 x − B3 y1 ≤ b3 2. oblast 0

a4 x − B4 y2 ≤ b4 , 0

a5 x − B5 y2 ≤ b5 3. oblast ....

Zárove¬ musí platit, ºe

k X

yj ≥ 1

j=1 kde

k

je celkový po£et oblastí. Napravo v poslední podmínce je po£et oblastí z výroku aspo¬ v

jedné oblasti a

y1 , y2 ∈ {0, 1} . Kaºdá yj , j = 1, 2, · · · , k .

rovnice má svoje

Bi

(maximální hodnota levé strany) a

spole£nou veli£inu

3.3

Modelování nelineárních funkci

3.3.1 Fixní náklady V n¥kterých p°ípadech pot°ebujeme modelovat nelineární funkci (nap°. skok v po£átku). Pokud výrobu budeme realizovat, náklady na výrobu ur£itého výrobku se sestává z po£áte£ní investice a dále z investice do kaºdého výrobku. Pokud se výroba nerealizuje, jsou v²echny náklady nula.

KAPITOLA 3.

30


Za p°edpokladu, ºe

K

je po£áte£ní skok.

( 0 K + c0 x

pro pro

x=0 . x≥0

Zápis takové úlohy je následující

Ky + c0 x → min9 a podmínky

x ≤ By 10 x ≥ 011

y ∈ {0, 1}

3.3.2 Po £ástech lineární reprezentace M¥jme po £ástech lineární funkce - nap°. tu, co je na obrázku

f(x) 3

1

4

x

První úse£ka je na intervalu se sklonem 3. Prom¥nnou

x

9 hledáme minimální náklady 10 Pro y = 0 dostáváme x = 0

0

4

10

15

(0, 4) a

má sklon 4, druhá na

(4, 10) se sklonem 1 a t°etí na (10, 15) x = δ1 + δ2 + δ3 tak, ºe platí

vyjád°íme jako sou£et t°í £len·

0 ≤ δ1 ≤ 4

délka 1. úseku

0 ≤ δ2 ≤ 6

délka 2. úseku

0 ≤ δ3 ≤ 5

délka 3. úseku

a kriterium je také 0; pro

y=1

je

x≤B

a kriterium je

K + c 0 x.

jsme namodelovali je binárn¥ lineární a kopíruje na²i formulaci úlohy (nelineární funkci náklad·).

11 hodnota

je nezáporná

Tedy to, co

KAPITOLA 3.

31


w1 = w2 = 0 0 ≤ δ1 ≤ 4 δ2 = 0 δ3 = 0

w1 = 1 a w2 = 0 δ1 = 4 0 ≤ δ2 ≤ 6 δ3 = 0

w1 = w2 = 1 δ1 = 4 δ2 = 6 0 ≤ δ3 ≤ 5

Tabulka 3.1: Po £ástech lineární funkce

Funkci

f (x)

vyjád°íme takto

f (x) = 4δ1 + δ2 + 3δ3 . Musíme ale zajistit, aby se

δi

zapínala postupn¥ a aby niº²í

Tedy, aby p°i pr·chodu hodnot

x

δi

drºely svou maximální hodnotu.

od 0 do 15 bylo

x≤4 x ∈ (4, 10) x > 10

δ1 x−0

δ2 0

δ3 0

4

x−4

0

4

6

x − 10

To zaru£í následující podmínky s dv¥ma novými binárními prom¥nnými

4w1 ≤ δ1

≤4

6w2 ≤ δ2

≤ 6w1

0 ≤ δ3

≤ 5w2

w1

a

w2

w1 , w2 ∈ {0, 1} D·kaz, ºe p°edpis platí je ukázán v následující tabulce Poslední varianta

w1 = 0

a

w2 = 1

je nep°ípustná a podmínka

6w2 ≤ δ2 ≤ 6w1 → 6 ≤ 0

ji

vylu£uje. Stejnou konstrukci lze provést i pro více interval·, pomocí podmínek

Lj wj ≤ δj ≤ Lj wj−1 , kde

Lj

je délka

j -tého

segmentu.

3.3.3 Aproximace nelineárních funkcí Nelineární funkci m·ºeme vhodn¥ rozd¥lit na intervaly a na nich pouºít lineární aproximace. Po£et takových interval· je závislý na nelineární funkci a musí být zvolen vhodn¥ tak, aby platilo, ºe v intervalu je funkce lineární. Pokud platí toto pravidlo, lze pouºít techniku z p°edchozího odstavce.

KAPITOLA 3.

32


3.3.4 Sou£in v kritériu Máme

x1 , x2 , x3 ,

- binární veli£iny,

y ∈ (0, u)

je spojitá nebo diskrétní veli£ina.

Kriterium:

x1 · x2 · x3 · y Zavedeme

w = x1 · x2 · x3 · y

max

a podmínky

w ≤ uxj

w≥u

→

X

→ w − uxj ≤ 0

w ≤y → w−y ≤0 X xi − k + y → u xi − k + y − w ≤ 0

Zadání úlohy: Nalezn¥te hodnoty binárních veli£in

KAPITOLA 3.


33

e²ení:

3.4

Metody °e²ení

3.4.1 Metoda v¥tví a mezí (branch and bound) Je to metoda pro °e²ení celo£íselného programování, zaloºená na opakovaném °e²ení pomocí simplexové metody s postupným p°idáváním omezení. Metoda konverguje v kone£ném po£tu krok·, i kdyº doba konvergence m·ºe být dlouhá. Jestliºe úlohu °e²íme tak, ºe jednou simplexovou tabulkou dostaneme °e²ení a to zaokrouhlíme, nemusíme dostat optimální °e²ení. Lze dokázat, ºe optimální °e²ení m·ºe leºet libovoln¥ daleko,

KAPITOLA 3.

34


omezení

vrstevnice kritéria optimální LP ?e?ení optimální IP ?e?ení zaokrouhlené LP ?e?ení

Obrázek 3.4.1: Porovnání výsledku LP a IP

viz následující p°íklad.

Zadání úlohy: Podle následujícího zadání, chceme dosáhnout maximálního zisku

x + 5y → max

Dále musíme splnit následující podmínky

x + 5y ≤ 50 x−y ≤5 x + y ≤ 30

e²ení: Úlohu nejd°íve vy°e²íme metodou lineárního programování, kde získáme °e²ení ²ení celo£íselného programování dá °e²ení

[10, 8].

[12.5, 7.5].

e-

Výsledek celo£íselného programování není za-

okrouhlení lineárního programování. Z obrázku 3.4.1 je vid¥t, ºe zaokrouhlené °e²ení leºí od optimální vrstevnice kritéria dále, neº optimální IP °e²ení.

Algoritmus Metody v¥tví a mezí (Branch and Bound - B&B) je: 1. Vezmeme optimální LP °e²ení - nap°.

bu¤ na ose

x

nebo

y

(p·jdeme p°es

x).

[12.5, 7.5]

a tento bod vyjmeme z p°ípustné oblasti

Tj. p°idá dv¥ nová omezení

x ≤ 12

a

x ≥ 13.

KAPITOLA 3.

35


Tím vzniknou dv¥ nové p°ípustné oblasti - podoblasti p·vodní, kde jiº optimální bod LP neleºí, ale ºádné celo£íselné °e²ení není vyjmuto. 2. Znovu °e²íme LP úlohu (simplexovou metodou) pro p·vodní úlohu s dal²íma dv¥ma omezeními. 3. Dostaneme optimální °e²ení. Pokud je °e²ení celo£íselné, je konec. Pokud není, pokra£ujeme op¥t od bodu 1. 4. Takhle stále p°idáváme nová omezení, dokud nedostaneme integer °e²ení. e²ení budeme demonstrovat na p°edchozím p°íklad¥.

Ob¥ °e²ení pro

y

LP °e²ení

[12.5, 7.5]

°e²ení

omez

x ≤ 12

x(dolní)

[12, 7, 6]

krit=42.4

x >= 13

krit=42.5

°e²eni

omez

x(horní)

X

°e²ení

omez

y≤7

y (dolní)

[12, 7]

krit=40

°e²ení

omez

x≥8

y (horní)

[10, 8]

krit=42

omez vyhodíme pamatujeme a vyhodíme

vyhovují celo£íselnosti. Druhé má ale vy²²í hodnotu kritéria, proto ho volíme.

Vidíme také, ºe toto °e²ení souhlasí s IP °e²ením.

Lips: Podmínky zadáme do programu Lips (BaB_demo.lpx).

3.4.2 Metoda °ez· (cutting planes) Tato metoda vychází z optimální simplexové tabulky pro LP. Tuto tabulku p°epí²eme do rovnic, v kterých eliminujeme zlomkové koecienty na pravou stranu. Vzniklé rovnice se zlomkovými koecienty znovu °e²íme simplexovou tabulkou. Kon£íme, kdyº jako výsledek obdrºíme celá £ísla.

K soustav¥ omezení p°idáváme dal²í lineární omezení, která vylou£í optimální (zlomkové) LP °e²ení ale zachovají v²echna p°ípustná celo£íselná °e²ení.

Zadání úlohy: Podle následujícho zadání, chceme dosáhnout maximálního zisku

J = 5x + 8y → max Dále musíme splnit následující podmínky

x + y + s1 = 6 5x + 9y + s2 =45 x, y, s1 , s2 > ≥0

KAPITOLA 3.

36


e²ení: LP °e²ení tohoto problému dá simplexovou tabulku

(−z) x y

− 54 s1 + 94 s1 − 54 s1

− 43 s2 − 41 s2 + 41 s2

−41 41

=

9 4 15 4

= =

Tu p°epí²eme následujícím zp·sobem

(−z) x y

−2s1 +2s1 −2s1

−s2 −s2

+42 −2 −3

= = =

3 4 1 4 3 4

− 34 s1 − 14 s2 − 14 s1 − 34 s2 − 34 s1 − 14 s2

a to tak, ºe

1. vlevo jsou jen celo£íselné koecienty, 2. vpravo jdou zlomky (a) absolutní hodnoty jsou kladné, (b) koecienty u prom¥nných jsou záporné.

Dále platí: 1. Pro celo£íselné °e²ení je jsou levé strany celá £ísla. 2. Pro

s1 , s2 ≥ 0

jsou pravé strany men²í nebo rovny konstantám.

3. Protoºe konstanty jsou kladné zlomky, musí platit ºe pravé strany jsou

≤ 0 (a tedy i levé).

M·ºeme proto psát

1 3 3 1 3 3 − s1 − s2 ≤ 0 → − s1 − s2 + s3 = 0 4 4 4 4 4 4 1 1 3 1 1 3 − s1 − s2 ≤ 0 → − s1 − s2 + s4 = 0 4 4 4 4 4 4 posledn´ı rovnice je stejn´ a jako prvn´ı To jsou podmínky, které p°idáme k p·vodní úloze a op¥t °e²íme pomocí simplexové tabulky. Celo£íselné °e²ení kon£í výpo£et, pro necelo£íselné vyjdeme z nové simplexové tabulky a pokra£ujeme stejn¥. První °e²ení

KAPITOLA 3.

37


z tabulky sestavíme nová omezení pro

s1

a

s2

a p°epo£ítáme na

2x + 3y ≤ 15 4x + 7y ≤ 35. První omezení dá rovnou výsledek

[0, 5]

Kdyº zkusíme druhé omezení, dostaneme

7

11 3, 3

xa y .

Ta jsou

KAPITOLA 3.


a museli bychom v hledání dál pokra£ovat.

Lips: Podmínky zadáme do programu Lips (cuts.lpx).

38

Kapitola 4

Modely celo£íselného programování 4.1

Výb¥r projektu

4.1.1 Rozpo£et kapitálu (Capital budgeting)[Hlavni text] Pro tyto úlohy lze denovat úlohu dv¥ma zp·soby:

1. Varianta:

Zadání úlohy: Máme moºnost n¥kolika investic. Z kaºdé investice máme o£ekávaný zisk a kaºdá vyºaduje ur£ité zdroje (prac. síly, suroviny atd.), které jsou omezené. Investici bu¤ realizujeme nebo ne. Jak vybrat investice aby p°inesly maximální zisk a nebyly p°ekro£ené omezené zdroje? Zápis standardní úlohy je následující:

c0 x → min1 ax ≤ b

2

x ∈ {0, 1}3

e²ení: Zavedeme binární prom¥nnou zdroje,

aij

xj .

Dále ozna£íme

- jsou poºadavky investice

j

i-tý

na

cj

- výnosy investice

j , bi

- omezení na

zdroj.

2. Varianta:

1 Jestliºe a ij

se týká dodate£ných investic a je

aij > 0,

pak investice pot°ebují dal²í nance; je-li

investice jiº nance produkuje.

2 nep°ekro£íme limitující omezení (nap°íklad nem·ºeme 3 x = 1 realizovat investici, 0 = nerealizovat investici. 39

do investice vloºit víc neº máme zdroj·)

aij < 0,

pak

KAPITOLA 4.

40

MODELY CELOÍSELNÉHO PROGRAMOVÁNÍ

Zadání úlohy: Máme

n

projekt·, které bychom rádi realizovali, ale nemáme najednou tolik pen¥z. Proto

je budeme realizovat po etapách. Z projektu náklady

at,j .

Pro etapu

t

j

o£ekáváme výnos

máme k dispozici nan£ní £ástku

bt .

cj

a v etap¥

t

vyºaduje

Cílem je dosáhnout maxi-

málního zisku v první etap¥, s ohledem na nan£ní omezení v dal²ích etapách. Zápis standardní úlohy je následující:

J= P

P

j cj yj

→ max4

at,j yj ≤ bt , ∀t5

yt ∈ {0, 1} , ∀j 6

4.1.2 Problém batohu [Nas text, Knapsack] (Knapsack problem) Jedná se o nejjednodu²²í úlohu z t°ídy investi£ního rozhodování.

Zadání úlohy : Jedeme na výlet stopem a balíme si s sebou v¥ci do batohu. Objem (nosnost) batohu je omezený hodnotou M . Jednotlivé v¥ci mají sv·j i = 1, 2, · · · , n. Chceme s sebou vzít

objem (váhu)

mi

a d·leºitost

di

a celkem jich je

n,

tedy

co nejvíce d·leºitých v¥cí tak, aby nebyla p°ekro£ena

kapacita batohu.

Matematická formulace je následující: max x

n X

n X

di xi

i=1

m i xi ≤ M

i=1

xi ∈ {0, 1} , ∀i

LIPS: Podmínky zadáme do programu LIPS (Kapsack0.lpx) nebo pro více v¥cí najednou (Kapsack1.lpx) 4 Hledáme °e²ení, kde získáme maximum z n projekt·, které nelze realizovat najednou 5 nep°ekro£íme limitující omezení (nap°íklad nem·ºeme do investice vloºit víc neº máme 6 x = 1 realizovat investici, 0 = nerealizovat investici.

pen¥z)

KAPITOLA 4.

4.2

41


Plánování produkce

4.2.1 Velikost dávky - bez kapacity[Kniha] Pro budoucí £asová období máme navrhnout objem produkce tak, aby celkové náklady a produkci a skladování byly minimální a aby poºadavky na produkci v jednotlivých etapách byly spln¥ny. P°edpokládáme neomezenou kapacitu produkce v kaºdém období. P°edpokládáme dále, ºe

•

náklady na produkci jsou úm¥rné její velikosti,

•

celkové náklady v kaºdém období jsou úm¥rné úrovni zásob z p°ede²lého období.

Rozhodujeme, zda

yt

vyráb¥t a pokud ano, kolik vyráb¥t

xt .


P

t

(ct xt + ft yt + ht st ) → min7 st−1 + xt − st = dt 8 xt ≤ M y t 9

xt ≥ 0, st ≥ 0, y ∈ {0, 1} kde

t

je po£et period;

dt

je poºadavek v period¥

jednotka náklad· na produkci,

ht

t ; ft

je po£áte£ní náklad v period¥

je jednotka náklad· na p°echování výrobk·.

Poznámka: P°i objednávkách je

st−1 + xt − st − bt−1 + bt = dt

Excel: Podmínky zadáme do Excelu (VelikostDavkyBezK.xlsx)

4.2.2 Velikost dávky - s kapacitou [Kniha] Stejné jako v p°edchozím p°ípad¥, jen navíc je ýroba v jednotlivých etapách omezena. Z tohoto d·vodu zavedeme novou prom¥nnou

ut ,

tedy omezení výroby v období


P

t

(ct xt + ft yt + ht st ) → min10

7 kriterium: minimalizace náklad· na produkci a skladování 8 s - úrove¬ zásob v kaºdém období (s = 0). t 0 9 je pot°eba naplnit poºadavky v kaºdém období a M (kapacita) 10 kriterium: minimalizace náklad· na produkci a skladování

je velké £íslo

→∞

t.

t ; ct

je

KAPITOLA 4.

42


st−1 + xt − st = dt 11 xt ≤ ut yt 12 xt ≥ 0, st ≥ 0, y ∈ {0, 1} kde

t

je po£et period;

dt

t ; ft

je poºadavek v period¥

jednotka náklad· na produkci,

ht

je po£áte£ní náklad v period¥

t ; ct

je

je jednotka náklad· na p°echování výrobk·.

Excel: Podmínky zadáme do Excelu (VelikostDavkyBezK.xlsx) (jen místo M

se dá ta kapacita)

4.2.3 Produkce na odbyt [Kniha] Máme ur£it velikost produkce n¥kolika výrobk· pro kaºdé období ve správném mnoºství a daném £ase. Snaºíme se mít pokud moºno ºádné nebo malé zásoby. V praxi ale p°ipustíme bu¤ malé zásoby nebo p°echodný nedostatek zboºí. (Jestliºe nedostatek nep°ipustíme, pouºijeme velikou penalizaci

→ ∞).

Cíl je platit co nejmén¥ na pokutách za p°ebytek nebo nedostatek zboºí.

Rozhodujeme, zda

yt

vyráb¥t a pokud ano, kolik vyráb¥t

xt .


P

pj

j

P

t

d+ j,t + qj

P

t

13 d− j,t → min

sj,t−1 + xj,t − dj,t = sj,t , ∀j, t − 14 sj,t = d+ j,t − dj,t , ∀j, t

xj,t = lj,t yj,t , ∀j, t = 1 · · · T − 1 (x = lj,T ) yj,T , ∀j yj,t ≥ 0, kden je po£et r·zných výrobk·; mnoºství výroby;

pj

T

int

je po£et období;

je jednotková pokuta za p°ebytek;

dj,t jsou poºadavky; lj,t je p°edepsané qj je jednotková pokuta za nedostatek.

Excel: Podmínky zadáme do Excelu (produkceNaSpotrebu.xlsx) 11 s - úrove¬ zásob v kaºdém období (s = 0). t 0 12 je pot°eba naplnit poºadavky v kaºdém období s ohledem na omezení 13 kritérium: minimalizovat platby za p°ebytek nebo nedostatek zboºí 14 Stav: d− a d+ mnoºství nedostatku a p°ebytku; s mnoºství zásob. j,t

j,t

j

kapacitou

KAPITOLA 4.

43


4.2.4 Objednávka léku [3 p°íklady] Zadání úlohy : m potenciálních dodavatel·. iv m¥síci t je cit . Kaºdý dodavatel i má ur£itou minimální dávku odb¥ru li . Nespot°ebovaná balení léku je moºno schovat do dal²ího období jako zásobu zt , která je v²ak omezena velikostí Z . Zbylá Léka°ské st°edisko má rozhodnout o tom, jak objednat ur£itý lék od St°edisko má pro jednotlivé m¥síce poºadavky

dt , t = 1, 2, · · · , T

a cena léku od dodavatele

balení lék· (které nebyly spot°ebovány a uº se nevejdou do zásoby) se musí vyhodit. Cílem je minimalizovat náklady na po°ízení léku v daném £asovém úseku.

e²ení : Zavedeme prom¥nné:

cit

cena za jedno balení léku od dodavatele

dt

poºadavek na m¥síc

li

kolik balení léku bereme od dodavatele

yit

jestli v·bec bereme (0 ne, 1 ano)

t

gt

kolik toho v m¥síci

t

i

xit

zásoba v m¥síci

v m¥síci

t

minimální odb¥r od dodavatele

zt

i

i

v m¥síc

t

(z minulého m¥síce)

t

vyhodíme

První, co je t°eba ud¥lat, je vypo£ítat zásoby

zt .

Vyjdeme z rovnice vyjad°ující zákon zachováni

hmoty (lék·)

zt−1 +

X

xit = dt + zt + gt

i tedy: co zbylo z minula + co jsme odebrali od dodavatel· se musí rovnat tomu, co jsme spot°ebovali + nechali v zásob¥ + co jsme p°ípadn¥ vyhodili. Odtud je

zz = zt−1 +

X

xit − dt − gt .

i To zadáme do Excelu jako po£ítané bu¬ky. Omezení:

xit ≥ li yit ···

kdyº se nebere, tak se nebere; kdyº ano, tak minimum od dodavatele

xit ≤ 1000yit ···

kdyº se nebere, tak

xit

musí být nula, jinak libovolné

xit ∈ {0, 1} , 0 ≤ zt ≤ Z, gt ≥ 0 Kriterium:

X

cit xit → min

Excel: Podmínky zadáme do Excelu (NakupLeku.xlsx)

i

je li

KAPITOLA 4.

4.3

P°eprava s pevnou cenou [Kniha]

Uvaºujeme

ik

44


m

odb¥rateli

n

zdroj· a

j

odb¥ratel· jednoho druhu zboºí. Náklady na p°epravu zboºí ze zdroje

zahrnují jednotkovou cenu p°epravy

cij

a pevné náklady

fij ,

nezávislé ne mnoº-

ství p°eváºeného zboºí. Máme nalézt minimální náklady na p°epravu tak, aby byly spln¥ny poºadavky odb¥ratel·

dj .

e²ení xij

- mnoºství zboºí z

i

do

j

yij

- jestli se p°evoz z

i

do

j

bude realizovat nebo ne

Úloha

XX

(cij xij + fij yij ) → min X

xij = dj

i

xij ≤ M yij xij ≥ 0, yij ∈ {0, 1} kde

xij

je mnoºství zboºí z

i

do

j , yij

zna£í, jestli se p°evoz z

i

do

j

bude realizovat (1) nebo ne

(0).

Excel: Podmínky zadáme do Excelu (TranspPevnaCena4.xlsx) 4.4

Problém investi£ního rozhodování [Nas text]

Cílem je rozhodnout o ur£itém mnoºství investi£ních akcí. Akce se bu¤ podpo°í celá, nebo se nepodpo°í v·bec. Akcím p°i°adíme stavový vektor

x = [x1 , x2 , · · · , xn ] , xj ∈ {0, 1} ∀j = 1, 2, · · · , n tak, ºe

xi = 1

znamená podporu akce

i, xj = 0

Zisk plynoucí z jednotlivých akcí ozna£íme

znamená, ºe akce

j

nebude podpo°ena.

cj , j = 1, 2, · · · , n. Akce vyºadují m r·zných zdroj· i-tý zdroj pro akci j ozna£íme ai,j a mnoºství bi (omezení jsou psány pro jednotlivé zdroje).

(nance, lidské síly, suroviny atd.). Náklady na jednotlivých zdroj·, které jsou k dispozici Zápis standardní úlohy je následující:

n X

cj xj → max

j=1 n X j=1 Modikace základní úlohy:

ai,j xj ≤ bi , xj ∈ {0, 1} , i = 1, 2, · · · , m

KAPITOLA 4.

•

45


Modelování závislostí projekt· - realizace projektu

i

je závislá na realizaci projektu

j.

Lze

modelovat jako

xj ≥ xi . •

Výb¥r nejvý²e jednoho ze skupiny

x1 + x2 + x3 + x4 ≤ 1

Excel: Podmínky zadáme do Excelu (InvesticniRozhodnuti.xlsx) 4.5

Problém po²tovních box· [Nas text]

Zadání úlohy : Firma dostává platby od zákazník·. Tyto platby jdou ze 4 míst: západu - 70tis., st°edozápadu - 50tis., východu - 60tis. a jihu - 40tis. v pr·m¥ru za den. Pro výb¥r t¥chto plateb chce otev°ít pobo£ky (po²tovní boxy). Pro tyto boxy p°ichází v úvahu následující místa: Los Angeles, Chicago, New York a Atlanta. Za otev°ení boxu v kaºdém z t¥chto míst zaplatí stejnou £ástku 50tis. Po£et dní, ve kterých budou platby realizovány, je dán v tabulce

z / do

L.A.

Chicago

New York

Atlanta

západ

2

6

8

8

st°edo západ

6

2

5

5

východ

8

5

2

5

jih

8

5

5

2

Po dobu, kdy je platba uskute£n¥na ale není proplacena jsou peníze pro rmu nedostupné a rma ztrácí úrok 20% z jejich p°ípadné investice. Které z pobo£ek má rma otev°ít, aby co nejvíce u²et°ila?

e²ení : Ztráty z nerealizovaných investic jsou dány v tabulce (v tis.)

kde nap°. západ

z / do

L.A.

Chicago

New York

Atlanta

západ

28

84

112

112

st°edo západ

60

20

50

50

východ

96

60

24

60

jih

64

40

40

16

→

New York je

Zavedeme binární veli£iny na pobo£ku

8 · 70 · 0.2 = 112

yj = 1

- pobo£ka

j.


j

(dny, platba, procenta).

bude otev°ena, a

xij = 1

- oblast

i

posílá platby

KAPITOLA 4.

46


28x11 + 84x12 + 112x13 + 112x14 + 60x21 + · · · + 16x44 ++50y1 + 50y2 + 50y3 + 50y4 → min15 xij = 1 ∀i16

P

j

P

i

xij ≤ 4yj ∀j 17

xij , yj ∈ {0, 1} ∀i, j

Excel: Podmínky zadáme do Excelu (LockBoxes.xlsx) 4.6

Propuknutí infek£ního onemocn¥ní [Nas text, 3 p°íklady]

Zadání úlohy: V

n

m léka°ských tým·, které mohou j ∈ {1, 2, · · · , n} vy²et°ovat tij hodin.

místech se vyskytlo infek£ní onemocn¥ní. K dispozici je

onemocn¥ní pro²et°it. Tým

i∈ {1, 2, · · · , m}

bude místo

Kaºdý tým m·ºe obslouºit 0, 1 nebo 2 místa. Jestliºe má tým obslouºit je²t¥ druhé místo (z místa

k do místa l), musí se po£ítat s dobou p°ejezdu dkl . Jakmile jsou v²echna místa pro²et°ena,

m·ºe se s infekcí za£ít bojovat. Cílem je navrhnout plán vy²et°ování tak, aby cela akce byla co nejkrat²í.

e²ení: Denujeme veli£inu

xij ∈ {0, 1}

s hodnotou 1 jestliºe tým

i

bude vy²et°ovat místo

j

a 0, kdyº

nebude. 1. Kriterium

P

j tij xij ,

P

k,l; k6=l

∀i18

dkl xik xil , ∀i19

2. Optimalizace:

min maxi

nP

j tij xij

+

P

k,l; k6=l

dkl xik xil

o

3. Omezení

P

i

xij = 1, ∀j 20

15 kritérium 16 kaºdá oblast musí být p°i°azena jedné pobo£ce 17 neotev°ené pobo£ce se nesmí nic posílat (4 je tam 18 musí se vy²et°it v²echna místa 19 na kaºdé místo se musí cestovat 20 kaºdé místo bude nav²tíveno práv¥ jednou

proto, aby pro

y=1

podmínka vypadla - velké £íslo)

KAPITOLA 4.

47


P

j

xij ≤ 2, ∀ii21

xij ∈ {0, 1} , ∀i, j Pro kaºdou konstelaci je jeden tým nejdel²í a tohle maximum chceme minimalizovat. Tohle ale neumíme

(i)

nelinearita v sou£inu,

(ii)

minimax.

S nelinearitu lze vy°e²it tak, ºe zavedeme novou prom¥nnou

wikl = xik xil s podmínkami

wikl ≤ xik , wikl ≥ 0, wikl ≤ xil , wikl ≥ xik + xil − 1.

4.6.1 P°íklad 2 týmy (i=1,2),

3 místa (j=1,2,3)

stav

x=

x11 x21

x12 x22

x13 x23

binární

£asy

t= veli£ina

w

t11 t21

t12 t22

t13 t23

(cesta tam a zp¥t je stejn¥ dlouhá)

w=

w1;12 w2;12

w1;13 w2;13

w1;21 w2;21

w1;23 w2;23

w1;31 w2;31

w1;32 w2;32

délky p°ejezdu

d=

8, 12, 8, 14, 12, 14

Podmínky 1.

wi;kl ≥ 0, ∀i, k, l

2.

wi;kl − xik ≤ 0,

3.

wi;kl − xik − xil + 1 ≥ 0 P P j tij xij + kl; k6=l dkl wi;kl − q ≤ 0, ∀i

4. kde

q

wi;kl − xil ≤ 0, ∀i, k, l

je nová veli£ina s významem doba trvání nejdel²í akce.

Úloha

q → min

Excel: Podmínky zadáme do Excelu (infection_small.xlsx, 21 ºádný

tým nenav²tíví více neº dv¥ místa

infection_bigger.xlsx)

KAPITOLA 4.

4.7 Existuje


48

Pokrytí mnoºin m

poºadavk·

Ri

a

n

aktivit

Aj

takových, ºe v celkovém sjednocení pokrývají v²echny

poºadavky, nikoliv ale jednotliv¥. Cílem je najít takovou podmnoºinu aktivit, která ve sjednocení pokryje v²echny poºadavky a minimalizuje ur£ité kriterium (nap°. náklady na vyuºité aktivity). Existují 3 varianty tohoto problému: (1) Set covering, (2) Set partitioning a (3) Set packing. Jejich formulace jsou následující (li²í se v nerovnítku podmínek): 1. Covering

c0 x → min Ax ≥ 1 x ∈ (0, 1) 2. Partitioning

c0 x → min Ax = 1 x ∈ (0, 1) 3. Packing

c0 x → max Ax ≤ 1 x ∈ (0, 1)

4.7.1 Pokrytí mnoºin - set covering [Kniha] Zadání úlohy : (poºární stanice) Uvaºujme m¥sto, které se skládá z n¥kolika oblastí. Ty jsou zachyceny na obrázku

7 2

6 4

1

5 3

Kaºdé oblasti je p°i°azeno £íslo. Ve m¥st¥ chceme vybudovat poºární stanice. Jedna stanice je schopna pokrýt oblast, ve které je postavena a v²echny sousední oblasti (tj. takové, co sousedí hranou). Jak postavit stanice, aby jich bylo co nejmén¥?

KAPITOLA 4.

49


e²ení : (poºární stanice) Oblastem p°i°adíme binární prom¥nné

x1 , x 2 , · · · , x 7 .

Tyto prom¥nné budou mít hodnotu 1,

kdyº stanice bude, jinak 0. Kriterium: minimální sou£et

x

Podmínky: oblast 1 a její sousedi musí mít alespo¬ jednu stanici; a dále pro 2,

··· ,

7. Sousední

oblasti jsou

1,2,3 2,1,3,4,6,7 3,1,2,4 4,2,3,5 5,4,6 6,2,5,7 7,2,6

Úloha tedy bude

X

xi → min

i

x1 + x2 + x3 ≥ 1 x1 + x2 + x3 + x4 + x6 + x7 ≥ 1 x1 + x2 + x3 + x4 ≥ 1 x2 + x3 + x4 + x5 ≥ 1 x4 + x5 + x6 ≥ 1 x2 + x5 + x6 + x7 ≥ 1 x2 + x6 + x7 ≥ 1

x1 · · · x7 ∈ {0, 1}

Excel: Podmínky zadáme do Excelu (pozarniStanice.xlsx)

4.7.2 Rozd¥lení a zabalení mnoºin (partitioning, packing) [Kniha] Zadání úlohy

: (výb¥r jídel z kucha°ky)

ekáme neohlá²enou náv²t¥vu a chceme ji pohostit. Ve spíºi máme 7 ingrediencí do jídla a dal²í uº nesta£íme po°ídit. Nevíme ale, jaké chut¥ náv²t¥va má, a proto chceme p°ipravit co nejv¥t²í po£et jídel. Máme kucha°ku a z ní jsme vybrali jídla, která obsahují ty ingredience, které máme k dispozici. Ingredience ale nelze d¥lit; kaºdou lze pouºít jen jednou. O£íslujeme-li ingredience 1,2,· · · ,7, pak vybraná jídla podle kucha°ky pot°ebují

KAPITOLA 4.

50


jídlo

ingredience

A

1,2

B

1

C

2,5,6

D

3,7

E

2,7

F

3,5

G

4,5,6

Která z jídel m·ºeme p°ipravit, aby jich bylo co nejvíce?

e²ení : (výb¥r jídel z kucha°ky) B, C, D.

Excel: Podmínky zadáme do Excelu (recepty.xlsx)

4.7.3 Rozmíst¥ní sklad· (Warehouse location) [Nas text, Hlavni text] Máme

m sklad· a n zákazník·. Máme obstarat a dovézt zboºí, které poºadují zákazníci. Jde o to,

rozhodnout, ze kterého skladu a kolik daného zboºí nakoupit a p°evézt jednotlivým zákazník·m tak, aby cena za nákup a p°evoz byla minimální. Ty sklady, pro které se rozhodneme, musíme pronajmout, a to n¥co stojí.

yi

ozna£uje, zda sklad

fi

je cena pronájmu

i

je pronajatý (yi

i-tého

= 1)

je mnoºství zboºí, zakoupeného ve skladu

ci,j

je cena za nákup jednotky zboºí

poºadavek

j -tého

= 0).

skladu.

xi,j

dj

nebo není (yi

i

a p°evezeného zákazníkovi

xi,j .

zákazníka.


Pm Pn i=1

j=1 ci,j xi,j

Pm

i=1

Pn

+

Pm

i=1

fi yi → min22

xi,j = dj , j = 1 · · · n23

j=1 xi,j − yi

P

n j=1

dj ≤ 0 , i = 1 · · · m24

xi,j ≥ 0 , ∀i, ∀j 22 celková cena za zboºí a dovoz + 23 spln¥ní poºadavk· zákazník·; 24 odb¥r jen z pronajatých sklad·

poplatky za pronájem sklad·

j.

KAPITOLA 4.


51

yi ∈ {0, 1} , ∀i kde

yi

i je pronajatý (yi = 1) nebo není (yi = 0), fi je cena pronájmu i-tého i a p°evezeného zákazníkovi j , ci,j je cena xi,j , dj poºadavek j -tého zákazníka.

ozna£uje, zda sklad

skladu,

xi,j

je mnoºství zboºí, zakoupeného ve skladu

za nákup jednotky zboºí

D·kaz, ºe platí, ºe zboºí lze odebrat jen z pronajatých sklad· je následující

n X

xi,j

  n X ≤ yi  dj  , ∀i

j=1 tedy, pro

i

takové, ºe

yi = 0

j=1

dostaneme

n X

xi,j ≤ 0

j=1 a protoºe pro

xi,j

yi = 1

jsou nezáporné, znamená to, ºe k ºádnému odb¥ru z t¥chto sklad· nedo²lo,

máme

n X

xi,j ≤

j=1

n X

dj

j=1

tedy celkové mnoºství zboºí, odebrané ze skladu

i

je men²í nebo rovno celkovému poºadavku

25

v²ech zákazník· (rovno, kdyby se bralo v²echno z jednoho skladu).

Excel: Podmínky zadáme do Excelu (pozarniStanice.xlsx) 4.8

Problém p°i°azení [Kniha]

Zadání úlohy : Uvaºujeme neorientovaný graf. Hledáme podvýb¥r jeho hran tak, ºe kaºdý uzel má nejvý²e jednu hranu (hrany spojují odd¥lené dvojice uzl·) a hran je maximální po£et.

e²ení : Zavedeme uzlo-hranovou inciden£ní matici

a

(svisle uzly, vodorovn¥ hrany) a binární vektor

dimenzí po£et hran kde 1 znamená hrana je vybrána, 0 hrany není vybrána. Zápis standardní úlohy je následující:

X

yj → max

X

aij yj ≤ 1

yj ∈ {0, 1}

Excel: Podmínky zadáme do Excelu (matchingProblem1.xlsx) 25 P d

j je z°ejm¥ to nejmen²í velké £íslo, aby se podmínka vºdy splnila.

y

s

KAPITOLA 4.

52


Poznámka Varianta této úlohy je, kdyº poºadujeme, aby kaºdý uzel mel nejvý²e

m

hran. Potom podmínka

je

X

4.9

aij yj ≤ m.

Problém °ezání [Kniha]

4.9.1 ezání ty£í Zadání úlohy : Máme ty£e dlouhé 7.4 m a chceme z nich na°ezat kusy dlouhé 150, 210 a 290 cm. Jednotlivé délky pot°ebujeme v mnoºství 1000 ks. Jak máme postupovat, kdyº chceme mít minimální odpad?

e²ení : Nejprve stanovíme tzv. °ezné plány Délka

Ozna£íme

x1 · · · x6

Plán °ezání 1

2

3

4

5

290

1

2

-

1

-

6 1

210

-

-

2

2

1

1

150

3

1

2

-

3

1

Odpad

0

10

20

30

80

90

jsou mnoºství °ezání podle jednotlivých plán·. Úloha je:

10x2 + 20x3 + 30x4 + 80x5 + 90x6 → min x1 + 2x2 + x4 + x6 = 1000 2x2 + 2x4 + x5 + x6 = 1000 3x1 + x2 + 2x3 + 3x5 + x6 = 1000.

Excel: Podmínky zadáme do Excelu (RezaniTyci.xlsx)

4.9.2 ezání papíru Zadání úlohy : W . Pro dal²í prodej se °eºe na pásy o p°edepsaných w1 , w2 , · · · , wm . Jednotliví odb¥ratelé si si p°edepisují po£et rolí bj na°ezaných na ur£itý

Papír se p°i výrob¥ balí do rolí o vý²ce ²í°kách

rozm¥r. Jak role °ezat, aby byl co nejmen²í odpad?

KAPITOLA 4.

53


e²ení : Kriterium je minimální odpad - tedy výroby

P

yj

P

j

Tj → min

nebo, coº je totéº, minimální po£et rolí z

coº je vlastn¥ po£et °ezání (podle r·zných plán·).

Poznámka Zbytky po °ezání mohou být po£ítány takto

Tj = W −

X

wi aij

i

4.10

TSP - Problém obchodního cestujícího [Nas text, Kniha]

4.10.1 Asymetrický TSP Uvaºujeme

n

m¥st spojených navzájem cestami. Kaºdou cestu uvaºujeme jako jednosm¥rnou,

obousm¥rné jsou dv¥ jednosm¥rky tam a zp¥t. Kaºdá z jednosm¥rek má svou délku (obecn¥ se délka cesty tam nerovná délce zp¥t). Cílem je najít cestu, kterou má projít obchodní cestující tak, aby kaºdé m¥sto nav²tívil práv¥ jednou a vrátil se do stejného m¥sta, ze kterého vy²el. Celá cesta má být nejkrat²í moºná.

Zadání úlohy : Úlohu budeme demonstrovat pro 5 m¥st.

2

d12

4

d21 1

x31 5

x13 3

dij ≥ 0

zna£í délky cest,

xij ∈ {0, 1}

znamená

xij = 1

cestující p·jde z m¥sta

i

do m¥sta

j

;

xij = 0

nep·jde.

KAPITOLA 4.

54


e²ení : Pro nejkrat²í cestu musí platit

J=

X

dij xij → min

ij Omezení 1: m¥sta se nesmí opakovat

→

kaºdé m¥sto má jen jednu vstupní cestu a jednu

výstupní, tj.

X

xij = 1, ∀j

výstupní

i

X

xij = 1, ∀i

vstupní

j Omezení 2: cesta se nesmí skládat z odd¥lených cykl· - to je problematický a °e²í se r·zn¥. My budeme postupovat následovn¥: Sestavíme v²echny Pro

n=5

bude

k -krokové

k = 2, 3

cykly,

k = 2, 3, 4, · · · , n − 226

a sou£et

xij

v nich musí být

≤k − 1.

a tedy

2-krokové: 12, 13, 14, 15, 23, 24, 25, 34, 35, 45 (a vºdy návrat do prvního, tedy 121, 131, · · · ) 3-krokové: (dohromady jich bude 2 × 53 = 2 × 10 = 20) z uzlu 1: 123, 124, 125, 134, 135, 145, z uzlu 2: 234, 235, 245, z uzlu 3: 345 (a návrat do po£. uzlu - na konci bude je²t¥ £íslo z po£átku); A odzadu: z uzlu 1: 1321, 1421, 1521, 1431, 1531, 1541 z uzlu 2: 2432, 2532, 2542 z uzlu 3: 3543 Návod

•

Za£ínáme od 1 a postupn¥ zvy²ujeme 123

•

Pak zv¥t²ujeme poslední aº do

•

Pak zvý²íme p°edposlední, následuje o jedna v¥t²í 134

•

A zase zvy²ujeme poslední.

•

A tak dál

n

123, 124, 125

Excel: Podmínky zadáme do Excelu (TSP_asym5.xlsx) 26 Ve

skute£nosti sta£í kontrolovat cykly od 2 do

n 2

,

kde

[·]

zna£í celou £ást £ísla. Je to proto, ºe kdyº se

v grafu vytvo°í cyklus, musí být zbylé uzly také v cyklu - pro kaºdý uzel poºadujeme jednu vstupní a jednu výstupní hranu. Pro cyklus s

k

kroky, kde

jsme jiº kontrolovali mezi cykly 2,3· · ·

,

n 2

n k> n tedy bude v grafu je²t¥ jeden cyklus s délkou l ≤ , který 2 2 n . Vedle cyklu s délkou v¥t²í neº 2 m·ºe být také více dal²ích cykl·,

ty ale budou také pat°it mezi jiº kontrolované.

KAPITOLA 4.

55


Obchodní cestující - 5 měst podmínka na "každé město jednou" x 1 2 3 4 1 0 0 1 0 2 1 0 0 0 3 0 0 0 1 4 0 0 0 0 5 0 1 0 0 1

1

kritérium J= 12

5

0 0 0 1 0

1

1

1

1 1 1 1 1

pro sestavení kritéria

tady je možno zadat apriorní hodnoty x (i když to prakticky nemá význam)

12

13

14

15

21

23

24

25

31

32

34

35

41

42

43

45

51

52

53

54

0 5

1 1

0 8

0 4

1 2

0 9

0 1

0 1

0 1

0 8

1 7

0 6

0 4

0 9

0 6

1 1

0 3

1 1

0 6

0 5

x d

Tady se zadávají délky cest

2 2

1 1

9 5

8

1

4

9 4 6

4 1

1 8

1 3 6

7 6

1

5 5

3

podmínka na cykly II III nemusí se hlídat vůbec 1 protože mohou být jen v kombinacích 1 s dvoukrokovými - a ty už se hlídají 0 0 0 0 1 1 0 1 dvou-krokové

Hlídáme 2 a 3-krokové cykly. 2-krokové jsou OK ihned. 3-krokové bychom museli hlídat tam i zpět, ale v kombinaci s 3-krokovým by musel být 2-krokový a ty se hlídají. Takže zpět nemusíme! Dokonce 3-krokové nemusíme vůbec!!!

Poznámka V podmínkách na cykly musíme hlídat, aby nenastala situace, ºe se v grafu utvo°í dva odd¥lené cykly. 1-krokové cykly nemohou nastat nikdy, protoºe smy£ky v grafu jsou vylou£eny (prvky na diagonále inciden£ní matice se neuvaºují). 2-krokové cykly jsou tam a zp¥t - obsahují tedy oba cykly (po sm¥ru i proti sm¥ru). 3-krokové cykly bychom museli hlídat v obou sm¥rech - tedy po sm¥ru i proti sm¥ru - tj. to, co jsme vý²e uvedli nap°. 1231 a je²t¥ zp¥t 1321. Protoºe ale 3-krokový cyklus muºe být v kombinaci jedin¥ s 2-krokovým (a ty jsou jiº hlídány) nemusíme je jiº v na²em p°ípad¥ (5 m¥st) v·bec hlídat! Sta£í kontrolovat cykly od 2 do

n 2

, kde [·] zna£í celou £ást £ísla. Je to proto, ºe kdyº se v grafu

vytvo°í cyklus, musí být zbylé uzly také v cyklu - pro kaºdý uzel poºadujeme jednu vstupní a jednu výstupní hranu. Pro cyklus s

neº

2

kroky, kde

k>

n 2

tedy bude v grafu je²t¥ jeden cyklus

, n2 . Vedle cyklu s délkou v¥t²í 2 m·ºe být také více dal²ích cykl·, ty ale budou také pat°it mezi jiº kontrolované.

n l ≤

s délkou

k

n

, který jsme jiº kontrolovali mezi cykly 2,3· · ·

4.10.2 Symetrický TSP Na rozdíl od p°edchozího jsou v²echny cesty obousm¥rné. Inciden£ní matice je horní trojúhelník. Kontrola na kaºdé m¥sto jednou se provádí takto:

KAPITOLA 4.

•

56


Pro kaºdý prvek inciden£ní matice na diagonále (to je to m¥sto) se se£tou prvky nad ním a vpravo od n¥ho.

•

Tento sou£et (po£et cest ve trase, které jím prochází) musí být

≤

2.

Kontrola cykl·:

•

2-krokové cykly se nemusí kontrolovat, protoºe

x

je zadáno jako binární (cyklus by dal 2,

protoºe jdeme tam a zp¥t po stejné cest¥),

• k -krokové

cykly sta£í kontrolovat jen po sm¥ru - proti sm¥ru jsou stejné.

Program: TSP_sym5.xlsx

x 1 2 3 4 5

c

1

2

3

4

5

0 0 0 0 0

0 0 0 0 0

1 0 0 0 0

0 1 1 0 0

1 1 0 0 0

1 1

2

3

4

5

5

6 9

8 8 3

3 5 7 6

2

2

2 3 4

J 25

na diag. a pod nejsou přípustné stavy (hrany nejsou orientované - trojúhelníky)

5

Podmínka 1: každý uzel 2 hrany 2 2 2

každý uzel má právě dvě hrany (vezmu pole (i,i) a sčítám nad ním a vpravo od něj)

Podmínka 2: cykly - je dána tím, že x je binární Tady se zadávají délky cest

2 8 5

5

4

8 1

9

6

3 6

3

5 7

3

KAPITOLA 4.

57


4.10.3 TSP jako nelineární problém 1.

Varianta s hranami Zadání úlohy : n

Obchodní cestující má nav²tívit

m¥st, kaºdé z nich práv¥ jednou a vrátit se do stejného

m¥sta, ze kterého vy²el. Cena ca cestování má být co nejmen²í. Ceny tras z m¥sta m¥sta

j

jsou dány jako prvky

ci,j

matice

i

do

c.

e²ení : Zavedeme stavovou matici s prvky

xi,j ∈ {0, 1} (nep·jde, p·jde z i

do

j ) a úloha je zadána

následovn¥

n n X X

ci,j xi,j → min

i=1 j=1 n X

xi,j = 1, ∀j

(tj. sloupce)

i=1 m X

xi,j = 1, ∀i,

(tj. °ádky)

j=1

X X

diag (X)

=0

X2 = 0

diag

··· X

kde

n

je po£et m¥st (uzl·) a

X

diag

X n−1 = 0

je £tvercová matice stavových prom¥nných

xi,j .

Poznámka Místo podmínky

P

diag (X)

=0

by také m¥la jít veliká penalizace na diagonále matice

c.

S hodnotou 1000 to ale numericky selhávalo.

2.

Excel: Podmínky zadáme do Excelu (ObchodniCestujiciOK_b.xlsx) Varianta s uzly Zadání úlohy : Jiné moºné °e²ení tohoto problému je uvaºovat místo hran uzly a hrany, které k nim pat°í. Podmínka je, ºe ke kaºdému uzlu pat°í práv¥ dv¥ hrany.

KAPITOLA 4.

58


e²ení : xk,k matice X. Hrany vstupující do tohoto uzlu xi,k , i = 1, 2, · · · , k − 1 nad tímto uzlem a hrany vystupující z tohoto xk,j , j = k + 1, k + 2, · · · , n - pro v²echny uzly k = 1, 2, · · · , n. Kaºdý uzel má

Uzly vztáhneme k diagonálním prvk·m budou ve sloupci uzlu budou

mít práv¥ dv¥ hrany a tedy podmínky budou

n X

xi,k +

i=1

xi,j ∈ {0, 1}

n X

xk,j = 2, k = 1, 2, · · · , n

j=1

xi,j

pro

Podmínky na sub-trasy jsou stejné - zákaz cykl· o délce men²í neº

n

0

a uvaºujeme jen prvky nad diagonálou

není nutno uvaºovat - hrany

k−k

X,

tedy

i < j.

2 . Podmínku

P

diag (X)

neexistují.

Excel: Podmínky zadáme do Excelu (ObchodniCestujiciOK_b.xlsx) 4.11

Zobecn¥ní TSP

4.11.1 Nejkrat²í cesta grafem [Kniha] Zadání úlohy : V·bec nejkrat²í cesta v²emi uzly bez ohledu na to, kde za£íná a kde kon£í.

e²ení : Vezmeme graf a p°idáme jeden uzel. Z n¥j vedeme cesty tam a zp¥t do v²ech uzl· grafu s nulovou délkou. Na tento roz²í°ený graf aplikujeme TSP a to, co vznikne v p·vodním grafu je nejkrat²í cesta. puvodni graf

0

0

0

0

novy uzel

Excel: Podmínky zadáme do Excelu (TSP_asym6Ham1.xlsx)

=

KAPITOLA 4.


59

4.11.2 Nejkrat²í cesta grafem z daného uzlu Zadání úlohy : Po£áte£ní uzel cesty je dán. Hledáme nejkrat²í cestu z tohoto uzlu.

e²ení : Vezmeme po£áte£ní uzel, a hranám, které do n¥j vedou dáme nulová ohodnocení. Na tento upravený graf aplikujeme TSP.

0 0 0 0

pocatecni uzel

0 carkovane hrany jsou pridany

Excel: Podmínky zadáme do Excelu (TSP_asym6Ham2.xlsx)

4.11.3 TSP s opakovanými náv²t¥vami m¥st [Kniha] Zadání úlohy : Úloha je dána jako asymetrický TSP, ale p°ipou²tíme více náv²t¥v jednotlivých m¥st. Typická aplika£ní úloha je rozvoz zboºí.

e²ení : Místo matice vzdáleností jednotlivých dvojic uzl· (ohodnoceni hran grafu) zadáme matici nejkrat²ích vzdáleností mezi jednotlivými dvojicemi uzl·. M·ºe být: bu¤ je vzdálenost spojovací hrany nejmen²í, pak ji necháme. Nebo existuje krat²í cesta, pak ji p°epí²eme. Nebo hrana neexistuje, pak ji p°idáme s ohodnocením nejkrat²í vzdálenosti mezi t¥mito uzly.

Poznámka minimální s£ítání matic . Tato operace funguje podobn¥ jako sou£in matic, ale místo násobení prvk· a s£ítání se Matice nejkrat²ích vzdáleností se velice jednodu²e spo£te pomocí operace provádí sou£et prvk· a vezme se minimum, tedy

(A ⊕ B)i,j = min {ai,k + bk,j }∀k

KAPITOLA 4.

60


Pro výpo£et nejkrat²ích vzdáleností napí²eme matici ohodnocení grafu

D,

kde na diagonále jsou

nuly a mimodiagonální prvky ozna£ují orientovanou vzdálenost mezi uzly. Kde hrana nevede, dáme velké £íslo. A provedeme

D2 = D ⊕ D D3 = D ⊕ D2 ··· Dn−1 = D ⊕ Dn−2 D2 spo£te v²echny nejkrat²í dvou-krokové cesty, D3 t°í-krokové atd. aº n−1-krokové, kde n je po£et uzl· (m¥st). Protoºe nejdel²í cesta grafem má n − 1 hran, obsahuje matice Dn−1 nejkrat²í kde

cesty mezi jednotlivými uzly grafu. Na upravenou matici (nyní minimálních vzdáleností mezi uzly grafu) aplikujeme TSP. Dostaneme navazující dvojice uzl·, které v p·vodním grafu vyzna£íme. Kaºdou hranu ale musíme prozkoumat. Pokud je délka hrany minimální délkou, pak ji na cest¥ ponecháme. Pokud není minimální, musíme hledat, po kterých hranách minimální cesta mezi aktuální dvojicí bod· vede a místo aktuální hrany vyzna£íme tuto minimální cestu. Tím se m·ºe stát, ºe n¥kterým uzlem projdeme vícekrát, ale m·ºeme dostat krat²í cestu neº kdyº trváme na podmínce jediného pr·chodu kaºdým m¥stem.

Excel: Podmínky zadáme do Excelu (TSP_asym5vice.xlsx)

4.11.4 TSP s klastry [Kniha] Zadání úlohy : Uvaºujeme graf jehoº vrcholy jsou pokryty

k klastry tak, ze klastry jsou disjunktní a ºádný vrchol

není nepokryt. Uzly jsou spojeny orientovanými hranami s ohodnocením, reprezentujícím délku hrany. Úkol je projít v²emi uzly tak, ºe po vstupu do uzlu se musí projít v²emi uzly tohoto grafu a cesta je nejkrat²í moºná.

e²ení : Vyjdeme z existujícího grafu a hranám uvnit° klastru p°idáme velké ohodnoceni

M → ∞.

Dále

aplikujeme TSP.

Excel: Podmínky zadáme do Excelu (TSP_asym6klast.xlsx) 4.12

Optimální po°adí úloh (machine sequencing) [Sheduling]

4.12.1 Plánování sm¥n pro obsluhu (Scheduling) 1.

Zam¥stnanci na plný úvazek

KAPITOLA 4.

61


Zadání úlohy : Plánujeme obsazení 4 sm¥n obsluhy v restauraci s rychlým ob£erstvením. Aby jednotlivé sm¥ny na sebe dob°e navázaly, musí se na za£átku a na konci p°ekrývat. Proto celý den (24 hodin) rozd¥líme na okna po 3 hodinách a sm¥ny sestavujeme podle následující tabulky (X ozna£uje jedno okno) Okno

Sm¥na 1

6-9

X

9-12

X

12-15

X

Sm¥na 2

Sm¥na 3

Sm¥na 4

Poºadavek prac.

X

55 46

X

15-18

X

18-21

X

59 23 X

21-24

X

0-3

X

60 38

3-6 Plat

135

140

190

X

20

X

30

188

Cílem je sestavit sm¥ny tak, aby celková vyplacená odm¥na byla co nejmen²í.

e²ení : Zavedeme

dt

- pot°ební pracovníci pro v okn¥

t; wj

- plat pro sm¥nu

j

(na kaºdé okno je

pot°eba ur£itý po£et pracovník·, sm¥na je obsazena stejnými pracovníky sm¥nu),

yj

- po£et pracovník· ve sm¥n¥

→

platba je za

j , (y1 , y2 , y3 , y4 )


J=

P

j

P

j

wj yj → min

at,j yj ≥ dt

yj ≥ 0, kde



1

 at,j =   1

1

1 1

int

 1

1 1

1

1 1 1

  

y = [y1 , y2 , y3 , y4 ] , t = 1, 2, · · · , 8

Excel: Podmínky zadáme do Excelu (FullTimeWorkers.xlsx) 2.

Brigádníci

[Kniha]

Zadání úlohy : Zase jako p°ed tím, ale najímáme i brigádníky. Ty p°ijímáme na divoko (do jednotlivých £asových oken) platíme mzdou

ct .

Jejich po£et ozna£íme

xt .

KAPITOLA 4.

62


e²ení : P

j

P

j

M

wj yj +

P

t ct xt

at,j yj + xt ≥ dt 27

P

j

at,j yj − xt ≥ 028

xt , yj ≥ 0,

int

Excel: Podmínky zadáme do Excelu (FullPartTimeWorkers.xlsx)

4.12.2 Obsazování let· posádkami [Nas text] Zadání úlohy : Letecká doprava zaji²´uje spojení mezi vybranými m¥sty. Tyto spoje nazveme etapy letu. Jeden let (s jednou posádkou letadla) letí po ur£itá trase a na ní m·ºe realizovat n¥kolik etap (pokud se mezi n¥ vejde povinný odpo£inek posádky a údrºba letadla). Tak nap°íklad let 10.00 z New Yorku do Chicaga a let 18.00 z Chicaga do Los Angeles je p°íkladem takových etap, které mohou tvo°it jednu trasu s jednou posádkou.

e²ení : Máme

n

etap a

m

posádek.

Nejd°íve sestavíme matici

a, která bude svými sloupci odpovídat jednotlivým etapám. V °ádcích

bude obsahovat v²echny moºné trasy, sestavené z etap, které lze realizovat v jedné trase - etapy budou vyzna£eny jedni£kou ve sloupci p°íslu²né etapy. Cílem je ze v²ech moºných tras vybrat ty, které obsadíme posádkou (budou realizovány) tak, aby 1. ºádná etapa nez·staly neobsazena, 2. náklady na realizaci tras byly minimální. Ozna£íme

xj ∈ {0, 1}, cj

je cena za pronajatí posádky na trase

ai,j ∈ {0, 1}

j

ozna£uje (jedni£kou), ºe etapa

(realizaci trasy

i

j ),

je za°azena do trasy

j

Úloha je formulována takto

Pn

j=1 cj xj

Pn

j=1

→ min29

ai,j xj = 1, i = 1, 2, · · · , m30

27 pro okno t, kde je P a y = 0 musí být x taky 0. Jinak podmínka neplatí. t j t,j j 28 omezení s M °íká, ºe brigádníci se mohou brát jen kdyº je tam uº n¥kdo na plný 29 c je cena za pronajatí posádky na trase j (realizaci trasy j ) j 30 a ∈ {0, 1} ozna£uje (jedni£kou), ºe etapa i je za°azena do trasy j i,j

úvazek

KAPITOLA 4.

63


xj ∈ {0, 1} , j = 1, 2, · · · , n31 kde kritérium vyjad°uje minimalizaci náklad·, a první podmínka vyjad°uje skute£nost, ºe kaºdá etapa má práv¥ jednu posádku.

Poznámka Jestliºe p°ipustíme, ºe £lenové n¥které posádky mohou ur£itou trasu let¥t jako pasaºé°i (p°eváºí se na místo svého letu na dal²í etap¥), bude mít tato podmínka tvar n X

ai,j xj ≥ 1, ∀i

j=1 1.

P°íklad Uvaºujeme 4 m¥sta:

A, B, C, D

a lety mezi t¥mito m¥sty podle následujícího obrázku

B

1

6

4 2

A

D 5 3

7

C Jednotlivé ²ipky na obrázku zna£í etapy. Jde o to, jak z nich sestavit trasy (obsazené posádkou) tak, aby pronájem posádek by minimální a v²echny etapy byly obslouºeny. Trasy jsou p°edem denovány bu¤ jako samostatné lety nebo jsou sestaveny z navazujících etap a jsou denovány maticí

     a=    

1 0 0 0 0 0 0

a. 0 1 0 0 0 0 0

Zde vybereme trasy takto

0 0 1 0 0 0 0

0 0 0 1 0 0 0

0 0 0 0 1 0 0

0 0 0 0 0 1 0

0 0 0 0 0 0 1

1 0 0 0 0 1 0

1 0 0 1 0 0 1

1 0 0 0 0 0 1

0 0 1 0 1 1 0

0 0 1 0 0 0 1

         

Nejd°íve uvaºujeme v²echny etapy jako samostatné lety, potom n¥které trasy sestavené z vhodných etap.

31

indikuje, zda trasa

j

bude realizována (tj. obsazena posádkou)

KAPITOLA 4.


64

Ceny posádek vezmeme p°ibliºn¥ rovny po£tu etap v p°íslu²né trase a trochu p°ihodíme na samostatné lety, protoºe tam musí posádka dojet z domova. Ceny tedy budou

c = [15, 12, 16, 14, 18, 12, 16, 22, 25, 24, 27, 26] Stavový vektor bude mít 12 prvk·, které budou bu¤ 0 nebo 1. Úloha má tvar

n X

cj xj → min

j=1 n X

aj xj = 1

j=1

xj ∈ {0, 1} e²ení úlohy je

x = [0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0] tedy budou realizovány lety (podle matice

a)

trasa 1

etapa 2

trasa 2

etapa 1,

etapa 4,

etapa 7

trasa 3

etapa 3,

etapa 5,

etapa 6

Tedy, v²echny etapy jsou obsazeny, poletí 3 posádky a doufejme, ºe cena za posádky je minimální. 2.

P°íklad Jiný p°íklad je realizován v programu: planovaniLetu.xlsx

Excel: Podmínky zadáme do Excelu (planovaniLetu.xlsx)

Kapitola 5

Programové vybavení 5.1

Excel

5.1.1 e²itel Pro °e²ení úloh lineárního programování je moºné pouºít aplikaci e²itel, tedy aplikaci, která souºí k vyhledávání extrém· funkce. e²itel je sou£ástí MS Excel Výhoda této aplice je v tom, ºe je p°ehledná a Excel je b¥ºn¥ vyuºívaný a roz²í°ený tabulkový procesor. Nevýhoda je, ºe je omezený prostorem a pro sloºité úlohy se msí pouºít jiný program. V²echny úlohy byly naprogramovány ve verzi MS Excel 2013 a i na tuto verzi optimalizovány. Z toho d·vodu neru£íme za nefunk£nost ve star²ích verzích. Tato verze je zdarma ke staºení na

http://download.cvut.cz/. e²itele naleznete po spu²tení v záloºce DATA, viz obrázek 5.1.1.

Obrázek 5.1.1: Excel - Data - e²itel Pokud tam není, je nutné ho aktivovat. Lze aktivovat následujícím zp·sobem: 1. otev°ete Soubor - Moºnosti - Dopl¬ky a otev°e se vám nové okno, viz obrázek (a), 2. v otev°eném okn¥ dole klikneme na Spravovat: Dopl¬ky aplikace Excel a otev°e se dal²í okno, viz obrázek (b). Za²krtneme e²itel a potvrdíme pomocí tla£ítka OK. Pokud v²e prob¥hlo v po°ádku, v záloºce DATA se objeví e²itel (v anglické verzi Solver).

5.1.2 Model v se²it¥ Excel 1. Nejd°íve vymezíme blok bun¥k pro neznámé 65

x

(p°ípadn¥ dal²í neznámé)

KAPITOLA 5.

66

PROGRAMOVÉ VYBAVENÍ

(a)

(b)

Obrázek 5.1.2: Aktivace e²itele

2. Dále zapí²eme v²echny zadané veli£iny - v¥t²inou to jsou ceny omezení

A

a poºadované pravé strany

c

a koecienty lineárních

b.

3. Spo£teme v²echno, co je pot°eba spo£ítat (do e²itele se dávají jen odkazy na bu¬ky nebo bloky bun¥k). V¥t²inou to je: (a) kriterium

c0 x =

P

i ci xi

(b) vypo£tené pravé strany omezení

Ax =

P

aij xj ∀i

4. Zavoláme e²itele a zadáme v²echny odkazy (a) zvolíme Min nebo Max pro kriterium (b) zadáme blok nebo bloky pro neznáme (optimalizované) veli£iny (c) p°idáme omezení ve tvaru

≤, ≥

nebo bin (volí se na stejném míst¥)

(d) v¥t²inou necháme zatrºenou volbu neomezené veli£iny jsou nezáporné (nemusí se to jiº deklarovat v podmínkách) (e) a v okénku dole vybereme volbu Simplex LP - lineární programování.

5.1.3 Triky p°i práci v Excelu Blok bun¥k - taºení my²í nebo Shift+²ipka P°emíst¥ní bloku (s Ctrl kopie) -uchopení za okraj (bu¬ky nebo bloku) a taºení. Vkopírování hodnoty do celého bloku - vytvo°íme blok, zadáme hodnotu a Ctrl+Enter. Maticové vzorce - provád¥jí operace (nej£ast¥ji násobení) prvek po prvku. Zadávají se pomocí

Ctrl+Shift+Enter. Výsledek m·ºe být v jedné bu¬ce, nebo v bloku bun¥k. Blok je moºno zadat

p°edem (pak se objeví výsledky v celém bloku). Vzorec je moºno kopírovat se v²emi pravidly o posunu adres.

Fixace adres (absolutní adresy) - zaxované adresy se p°i kopírování neposouvají. Adresu xuje dolar p°ed písmenem, £íslem nebo obojím. Dolar p°ed písmenem xuje adresu p°i vodorovném pohybu, p°ed £íslem p°i svislém pohybu a p°ed obojím i ve vodorovném i svislém sm¥ru.

KAPITOLA 5.

Zadání dolar·

67


- automaticky zadáme dolary klávesou F4 ihned po vloºení adresy (jinak se

musí adresa dát do bloku). Opakované stisknutí F4 provede: oba dolary, jen p°ed £íslem, jen p°ed písmenem, ºádný dolar (atd.)

Skalární sou£in - pokud pot°ebujeme maticový výpo£et =

P

i

tak, ºe vytvo°íme sumu sou£inu dvou sloupc· a poté zmá£kneme

=suma(A1:A10*B1:B10) + Ctrl+Shift+Enter

ai bi lze ho jednodu²e vytvo°it Ctrl+Shift+Enter. Nap°íklad

Sou£in matice a vektoru - matice je B1:D10 a vektor A1:A10. Sou£in je =suma(B1:D1*$A$1:$A$10) + Ctrl+Shift+Enter

a rozkopírovat svisle. (Druhá adresa je absolutní - viz xace adres.)

5.1.4 P°íklad v excelu e²íme obecný p°íklad lineárního programování, viz 2.1. Pro p°ehlednost, je hned na za£átku uvedeno °e²ení, které je ozna£eno modrým pozadím (obrázek 5.1.3). Dále jsou uvedeny váhy v kritériu (pro variantu (a) v obecném p°íkladu), tedy váhy

c = [5, 1].

Následují podmínky

3x1 + 5x2

≤ 15

2x1 + x2

≤ 8

x2

≤ 2

které jsou také ve £tvere£ku s oranºovým pozadím, stejn¥ jako váhy v kritériu. Kritérium, které je ozna£eno zeleným pozadím v ráme£ku, je základní parametr, kde se hledá maximum nebo minimim. Ani tento parametr nem¥níme. P°i práci se obvykle m¥ní pouze polí£ka s oranºovým pozadím, tedy zadání.

Obrázek 5.1.3: P°íklad v excelu

KAPITOLA 5.

68


V p°ípad¥, ºe jiº máme nastavené základní hodnoty, p°echázíme k e²iteli (Solver). Spustíme DATA-e²itel (Solver) a objeví se nám tabulka znázorn¥na na obrázku 5.1.4 (a). Pro správnou funkci je pot°eba nastavit následující: 1. 2.

Ú£elová funkce - odkaz na bu¬ku s kritériem (zelené pozadí). Hledat - hledá se minimum, maximum nebo ur£itá hodnota. Pro zadávajícího je d·leºité si uv¥domit co hledá (u zisku nebude hledat minimum a u náklad· maximim).

3.

Prom¥nné modelu - výsledek (modré pozadí). Zde bude optimální hodnota pro zadané veli£iny (nap°íklad kolik kus· výrobku A a B vyrobit).

4.

Omezující podmínky

- zde musí být v²echny podmínky, které je potreba splnit, tzn.

vytvo°í se sloupcový vektor, do kterého se vypo£ítá sou£in výsledku (nap°íklad kolik kus· vyrobit) s hodnotou °ádku tak, aby se dal výsledek porovnat s omezením. Tedy

ax

porovnáme s pravou strannou omezení. Pokud bude je²t¥ jiný poºadavek, nap°íklad minimální vyrobené mnoºství, musí se zapsat také do Omezujících podmínek, kde se klikne na ikonku P°idat a nadenuje se nová podmínka. 5.

Nastavit podmínky nezápornosti - u v¥t²iny problém· se o£ekává, ºe výsledek nem·ºe být záporný (nem·ºeme vyrobit -5 výrobk·). Tato podmínka se m·ºe zadat p°ímo do omezujících podmínek nebo se za²krtne polí£ko s podmínkou nezápornosti.

6.

Vyberte metou °e²ení - na výb¥r je Gradientní metoda, Simplexová metoda a Evolu£ní algoritmust. Zvolení vhodné metody je na zadavateli a ur£í se podle typu úlohy. (a) Simplexová metoda - lineární optimaliza£ní úlohy, (b) Gradientní metoda - hladké nelineární optimaliza£ní úlohy, (c) Evolu£ní algoritmus - nehladké nelineární optimaliza£ní úlohy.

(a)

(b) Obrázek 5.1.4: e²itel

Poté se jiº jen zadá funkce °e²it a objeví se následující tabulka 5.1.4 (b). Tam necháme za²krtnutou moºnost

Uchovat °e²ení e²itele a potvrdit tla£ítkem OK.

KAPITOLA 5.

5.2


LIPS????

69

Literatura [Kniha]

Chen, Batson, Dang: Applied Integer Programming

[Nas text]

U£ební text - LecText_IntPrg.lyx

[Formulating] Formulating Linear Programming Models [Hlavni text]

Hlavní text - Integer programming

[Lockbox]

Lockbox, set coverinc, salesman

[Knapsack]

The knapsack problem

[3 p°íklady]

Infek£ní onemocn¥ní a dal²í

[Sheduling]

Scheduling, sequencing

70

Lineární programování II. Ivan Nagy, Pavla Pecherková

Recommend Documents