priklady

t ebí palivová sm s o výh evnosti v rozmezí 10,5 – 12,0 MJ/kg.
Nejvyšší p ípustný obsah vody ve sm si je 24%, popelovin 30% a síry 5,4%. Ur ete podíl
jednotlivých druh paliva ve sm si tak, aby celkové náklady na po ízení paliva byly
minimální.
P íklad 19
Firma vyrábí dva druhy nát rových hmot (barev) pro interiéry a exteriéry z vodné disperze
epoxidové prysky ice obsahující aditiva, pigmenty a plniva (složka A) a polyamidového
tvrdidla (složka B). Mísící pom ry pro jednotlivé nát rové hmoty jsou v tabulce:
barva pro exteriéry barva pro interiéry
složka A (díly) 100 100
složka B (díly) 26 14
zisk (K /t) 5000 4000
Denn je k dispozici maximáln 20 t složky A a 14 t složky B. Minimální denní požadavek na
množství barvy pro interiér jsou dv tuny, navíc toto množství nemá p ekro it množství barvy
pro exteriér o více jak jednu tunu. Firma chce naplánovat denní výrobu tak, aby byl
maximalizován denní zisk.
P íklad 20
V keramické díln se vyrábí vázy, misky a talí e. Za jednu sm nu je možné vyrobit nejvýše
10 ks váz nebo 16 ks misek nebo 20 ks talí a malbou ozdobit nejvýše 8 ks váz nebo 10 ks
28


misek nebo 12 ks talí . Zisk z prodeje jedné vázy je 500 K , z jedné misky 300 K a jednoho
talí e 200 K . Stanovte výrobní program dílny maximalizující zisk za sm nu.

3.3. ešení p íklad
P íklad 1
x1 ... náhrdelník (ks)
x2 ...prsteny (ks)
x1 + x2 24 (ks)
x1 + 1,5x2 16 (hod.)
x1 10 (ks)
z = 1 500x1 + 2 000x2 MAX (K )
x1, x2 0
P íklad 2
x1 ... kalkula ka standardní (ks)
x2 ... kalkula ka v decká (ks)
x3 ... kalkula ka programovatelná (ks)
5x1 + 7x2 + 10x3 90 000 (ks sou ástek)
x1 + 3x2 + 4x3 30 000 (prac. hod.)
x1 + x2 + x3 9 000 (ks pouzder)
z = 60x1 + 150x2 + 350x3 MAX (K )
x1, x2, x3 0
P íklad 3
x1 ... vým ra pšenice (ha)
x2 ... vým ra je mene (ha)
x3 ... vým ra žita (ha)
x1 + x2 + x3 200 (ha)
260x1 + 250x2 + 280x3 4 800 (kg)
x1 120 (ha)
z = 1 600x1 + 2 600x2 + 1 800x3 MIN (K )
x1, x2, x3 0
P íklad 4
x1 ... lesní sm s (1000 ks balení)
29


x2 ... ovocný aj (1000 ks balení)
30x1 + 35x2 4000 (kg)
7x1 + 4x2 600 (kg)
2x1 + x2 350 (kg)
x1 200 (kg)
z = 2 000x1 + 1 000x2 MAX (K )
x1, x2 0
P íklad 5
x1 ... obal jednoduchý lisovaný (ks)
x2 ... obal lisovaný ozdobný (ks)
x3 ... obal potišt ný ozdobn lisovaný (ks)
x1 + x2 + x3 400 (ks)
x2 + x3 250 (ks)
x3 200 (ks)
z = 9x1 + 6,5x2 + 15x3 MAX (K )
x1, x2, x3 0
P íklad 6
x1 ... vým ra paprik (ha)
x2 ... vým ra raj at (ha)
x1 + x2 10 (ha)
x1 3 (ha)
x2 3 (ha)
z = 6x1 + 4,5x2 MAX (tis. K )
x1, x2 0
P íklad 7
x1 ... lupínky (kg)
x2 ... hranolky (kg)
2x1 + 1,5x2 100 (kg brambor)
0,4x1 + 0,2x2 16 (kg oleje)
z = 64x1 + 50x2 MAX (K )
x1, x2 0
30


P íklad 8
x1 ... objem pen z investovaných do akcií (mil. K )
x2 ... objem pen z investovaných do podílových fond (mil. K )
x3 ... objem pen z investovaných do termínovaných vklad (mil. K )
x4 ... objem pen z investovaných do hypote ních zástavních list (mil. K )
5x1 + 4x2 + x3 + 3x4 30 (mil. bod )
1,06x1 + 1,04x2 + 1,01x3 + 1,05x4 10,03 (mil. K )
x1 + x2 + x3 + x4 = 10 (mil. K )
z = 10x1 + 8x2 + 3x3 + 4x4 MIN (mil. bod )
x1, x2, x3, x4 0
P íklad 9
x1 ... ezný plán . 1 (ks polotovar )
x2 ... ezný plán . 2 (ks polotovar )
x3 ... ezný plán . 3 (ks polotovar )
x4 ... ezný plán . 4 (ks polotovar )
x1 + x3 600 (ks ty í 90 cm)
x1 + x2 + 2x4 600 (ks ty í 70 cm)
x2 + x4 200 (ks ty í 50 cm)
x1 + 2x2 + 3x3 400 (ks ty í 35 cm)
z = 5x1 + 10x2 + 5x3 + 10x4 MIN (cm)
x1, x2, x3, x4 0
P íklad 10
x1 ... výroba v Most (dny)
x2 ... výroba v Klatovech (dny)
100x1 + 200x2 20 000 (ks luxusních tri ek)
200x1 + 500x2 42 000 (ks standardních tri ek)
130x1 + 60x2 12 000 (ks levných tri ek)
z = 5 000x1 + 8 000x2 MIN (K )
x1, x2 0
P íklad 11
x1 ... sm s „soft“ (balí ek)
x2 ...sm s „hard“ (balí ek)
31


2x1 + 5x2 40 (g)
7x2 28 (g)
12x1 + 5x2 65 (g)
z = 2x1 + 6x2 MIN (K )
x1, x2 0
P íklad 12
x1 ... sm s KSC1 (m3)
x2 ... sm s B5 (m3)
0,2x1 + 0,4x2 80 (t cementu)
0,5x1 + 0,3x2 50 (t kameniva)
z = 300x1 + 400x2 MAX (K )
x1, x2 0
P íklad 13
x1 ... kuku ice (kg)
x2 ... sojové boby (kg)
x1 + x2 800 (kg)
0,08x1 + 0,6x2 0,3(x1 + x2) (kg)
0,06x1 + 0,03x2 0,05(x1 + x2) (kg)
z = 3x1 + 9x2 MIN (K )
x1, x2 0
P íklad 14
x1 ... hn dý cukr (t)
x2 ... bílý cukr (t)
x3 ... mou kový cukr (t)
3x1 4 200 (t)
-x1 + 1,25x2 0 (t)
-x2 + 1,05x3 0 (t)
z = 1 500x1 + 2 000x2 + 2 300x3 MAX (K )
x1, x2, x3 0
P íklad 15
x1 ... stoly (ks)
x2 ...židle (ks)
32


x3 ... psací stoly (ks)
x4 ... knihovny (ks)
5x1 + x2 + 9x3 + 12x4 1 500 (m2)
2x1 + 3x2 + 4x3 + x4 1 000 (m2)
3x1 + 2x2 + 5x3 + 10x4 800 (hod.)
z = 1 200x1 + 500x2 + 1 500x3 + 1 000x4 MAX (K )
x1, x2, x3, x4 0
P íklad 16
x1 ... bonboniéra „Karamélie“ (ks)
x2 ... bonboniéra „Šakalád“ (ks)
2x1 + 10x2 60 (ks okoládových bonbón )
6x1 + 6x2 60 (ks o íškových bonbón )
10x1 + 5x2 85 (ks karamelových bonbón )
z = 30x1 + 45x2 MAX (K )
x1, x2 0
P íklad 17
x1 ...chléb (kg)
x2 ...sýr (kg)
2x1 + 4x2 3 (tis. kalorií)
50x1 + 200x2 100 (g bílkovin)
z = 20x1 + 60x2 MIN (K )
x1, x2 0
P íklad 18
x1 ... palivo HUL1 (kg)
x2 ... palivo HUL2 (kg)
x3 ...palivo CUL1 (kg)
x4 ... palivo CUL2 (kg)
10x1 + 11,7x2 + 11,3x3 + 14,2x4 10,5(x1 + x2 + x3 + x4)
10x1 + 11,7x2 + 11,3x3 + 14,2x4 12,0(x1 + x2 + x3 + x4)
0,3x1 + 0,25x2 + 0,2x3 + 0,12x4 0,24(x1 + x2 + x3 + x4)
0,35x1 + 0,22x2 + 0,17x3 + 0,09x4 0,3(x1 + x2 + x3 + x4)
0,042x1 + 0,047x2 + 0,056x3 + 0,08x4 0,054(x1 + x2 + x3 + x4)
33


z = 30,5x1 + 35x2 + 32,5x3 + 43x4 MIN (K )
x1, x2, x3, x4 0
P íklad 19
x1 ... barva pro exteriéry (t)
x2 ... barva pro interiéry (t)
1 2
1 2
100 100 20 (t složky A)
126 114
26 14 14 (t složky B)
126 114


x x
x x

x2 2 (t)
-x1 + x2 1 (t)
z = 5 000x1 + 4 000x2 MAX (K )
x1, x2 0
P íklad 20
x1 ... vázy (ks)
x2 ... misky (ks)
x3 ... talí e (ks)
1 2 3
1 2 3
1 1 1 1 (sm n)
10 16 20
1 1 1 1 (sm n)
8 10 12


x x x
x x x

z = 500x1 + 300x2 + 200x3 MAX (K )
x1, x2, x3 0



34


4. Grafické ešení modelu lineárního programování
Malé modely lineárního programování je možno ešit graficky. Pro grafické
znázorn ní modelu používáme rovinu, m žeme tedy pracovat s nejvýše dv ma rozm ry.
Proto m žeme graficky ešit pouze modely LP, které mají nejvýše dv rozhodovací
prom nné (po et omezujících podmínek m že být libovolný) nebo které mají nejvýše dv
omezující podmínky (po et prom nných m že být libovolný).
V prvním p ípad hovo íme o ešení modelu LP v tzv. „prostoru ešení“, kdy osy
reprezentují p ímo hodnoty rozhodovacích prom nných, ve druhém o ešení v tzv.
„prostoru požadavk “, kdy na osy vynášíme míru uspokojení požadavk omezujících
podmínek pomocí p íslušné rozhodovací prom nné.
Cílem kapitoly je poskytnout tená i návod, jak postupovat p i grafickém ešení
model LP obou typ .

4.1. ešené p íklady
P íklad 1
Pomocí vhodného zobrazení ešte graficky model lineárního programování:
x1 + 2x2 20
3x1 + 4x2 12
x1 8
z = 2x1 + x2 MAX
x1, x2 0
Model obsahuje dv rozhodovací prom nné a t i omezující podmínky, proto je nutné pro
zobrazení zvolit prostor ešení.
Nejprve musíme vymezit prostor p ípustných ešení. Ten tvo í geometrický útvar, který
vznikne jako pr nik grafického znázorn ní omezujících podmínek.
Omezující podmínka ve tvaru nerovnice je reprezentována polorovinou. Pokud ji
chcete zakreslit, musíte ur it její hrani ní p ímku a vymezit správnou polorovinu.
Hrani ní p ímka je spojnice dvou bod , pro které je omezující p ímka spln na jako
rovnice.
Pro konstrukci hrani ní p ímky m žeme použít dva libovolné body, které spl ují výše
uvedenou podmínku. Nej ast ji se používají pr se íky hledané hrani ní p ímky s ob ma
osami sou adnic.
Když chcete spo ítat pr se íky hrani ní p ímky s osami sou adnic, zvolte nejprve
x1 = 0 a z dané podmínky vypo t te hodnotu sou adnice x2. Poté položte x2 = 0 a
vypo t te p íslušnou hodnotu prom nné x1. Dostanete tak dva body [0,x2] a [x1,0].
Jejich spojením obdržíte hledanou hrani ní p ímku omezující podmínky.
35


Zakreslíme hrani ní p ímku omezující podmínky
x1 + 2x2 20
Pokud položíme x1 = 0, z rovnice 2x2 = 20 zjistíme, že první pr se ík má sou adnice [0, 10].
Pokud položíme x2 = 0, z rovnice x1 = 20 zjistíme, že druhý pr se ík má sou adnice [20, 0].
Hrani ní p ímku zakreslíme takto:
0
5
10
15
0 5 10 15 20 25 x1
x2

Nyní musíme ur it, která z polorovin vymezených hrani ní p ímkou obsahuje p ípustná ešení
úlohy.
Když chcete zjistit, která polorovina obsahuje p ípustná ešení, dosa te do dané
omezující podmínky libovolný bod, který neleží na hrani ní p ímce. Pokud je pro
tento bod omezující podmínka spln na, je tato podmínka spln na také pro všechny
body dané poloroviny.
Obvykle je výhodné dosadit do omezující podmínky po átek sou adnic, bod [0,0]. Pro naši
podmínku dostaneme výraz
0 20,
což platí. Proto všechny body, které leží v polorovin po átku sou adnic, dané omezující
podmínce vyhovují. P ípustnou polorovinu si ozna íme takto:
36


0
5
10
15
0 5 10 15 20 25 x1
x2

Stejným zp sobem postupujeme p i zakreslení druhé omezující podmínky
3x1 + 4x2 12
Pr se íky s osami jsou [0, 3] a [4, 0], p ípustná je polorovina, která po átek sou adnic
neobsahuje:
0
5
10
15
0 5 10 15 20 25 x1
x2

T etí omezující podmínka je specifická, nebo obsahuje pouze jednu prom nnou. V takovém
p ípad je hrani ní p ímka rovnob žná s jednou z os sou adnic.
Pokud omezující podmínka obsahuje pouze prom nnou x1, je rovnob žná s osou
x2. Pokud omezující podmínka obsahuje pouze prom nnou x2, je rovnob žná
s osou x1. Hrani ní p ímka vždy protíná druhou osu v bod , jehož hodnota je rovná
hodnot pravé strany omezující podmínky.
T etí omezující podmínka
37


x1 8
je tedy rovnob žná s osou x2 a osu x1 protíná v bod x1 = 8. P ípustná polorovina je
polorovina po átku sou adnic. Celou množinu p ípustných ešení tvo í konvexní polyedr,
který je zachycen na následujícím obrázku:
0
5
10
15
0 5 10 15 20 25 x1
x2

Nyní je už pouze pot eba ur it, který bod z množiny p ípustných ešení s nejlepší hodnotu
ú elové funkce
z = 2x1 + x2 MAX
K tomu jsou pot eba dva kroky. Nejprve zakreslíme libovolnou p ímku ú elové funkce, což
je spojnice všech bod [x1, x2] (kombinací prom nných), které vykazují stejnou hodnotu
ú elové funkce. Potom nalezneme takovou její rovnob žku, která bude co nejdále od po átku
sou adnic, ale která bude mít s množinou p ípustných ešení spole ný alespo jeden bod.
Pokud chcete zakreslit n jakou p ímku ú elové funkce, dosa te za symbol „z“
libovolnou hodnotu a p ímku zakreslete. Hodnoty vhodné pro dosazení poznáte tak,
že se budou dob e po ítat pr se íky p ímky ú elové funkce s osami sou adnic.
V našem p ípad položíme z = 10. Nevhodné (i když p ípustné) hodnoty by byly t eba
z = 7,153 nebo z = 1000. V prvním p ípad by se p ímka z ejm zakreslila nep esn , ve
druhém by se v daném m ítku nevešla do obrázku.
Do obrázku zakreslíme p ímku ú elové funkce jako spojnici všech bod , pro které z = 10,
tedy
10 = 2x1 + x2
Pr se íky s osami mají sou adnice [0, 10] a [5, 0].
38


0
5
10
15
0 5 10 15 20 25 x1
x2
z(10)

Nyní je už snadné najít rovnob žku p ímky ú elové funkce, která je nejdále od po átku
(chceme její maximální hodnotu, p i minimalizaci bychom ji požadovali nejblíže po átku) a
která má stále s množinou p ípustných ešení spole ný alespo jeden bod.
0
5
10
15
0 5 10 15 20 25 x1
x2
z(10) z(opt.)
x(opt.)

Nakonec je pot eba stanovit hodnoty prom nných v optimálním ešení.
Pokud chcete stanovit hodnoty prom nných v optimálním ešení z grafu, podívejte
se, na kterých p ímkách omezujících podmínek tento bod leží. Hodnoty prom nných
potom vypo tete snadno jako ešení soustavy dvou rovnic o dvou neznámých.
Náš bod optima x(opt.) leží na p ímkách
x1 + 2x2 = 20 (první omezující podmínka) a
x1 = 8 (t etí omezující podmínka).
Po vy ešení této soustavy lineárních rovnic dostaneme
39


x1 = 8 a x2 = 6.
Dosazením tohoto bodu do p edpisu ú elové funkce dostaneme její hodnotu, tedy
z = 2.8 + 6 = 22.
Úloha je vy ešena, známe jak hodnoty obou rozhodovacích prom nných, tak hodnotu ú elové
funkce.

4.2. P íklady k procvi ení
ešte graficky následující modely lineárního programování. Jako výsledek uve te grafické
znázorn ní modelu a dále podle typu výsledku:
pokud má model práv jedno optimální ešení, uve te hodnoty všech rozhodovacích
prom nných a hodnotu ú elové funkce v optimálním ešení,
pokud model nemá p ípustné ešení nebo hodnota ú elové funkce m že neomezen r st
(klesat), pouze tuto skute nost uve te,
pokud má model nekone n mnoho optimálních ešení, uve te hodnoty všech
rozhodovacích prom nných ve všech bázických optimálních ešeních a hodnotu ú elové
funkce.
P íklad 1
x1 + x2 10
2x1 + 4x2 8
z = 5x1 + 2x2 MAX
x1, x2 0
P íklad 2
x1 + 2x2 = 6
2x1 - 4x2 8
-x1 + 3x2 6
z = 3x1 + 4x2 MIN
x1, x2 0
P íklad 3
-x1 + 4x2 6
3x1 - 2x2 4
4x1 + 12x2 12
z = 2x1 + x2 MIN
x1, x2 0
40


P íklad 4
4x1 + 12x2 24
4x1 + x2 2
-x1 + x2 1
5x1 - 2x2 5
z = 3x1 + 2x2 MAX
x1, x2 0

P íklad 5
2x1 + 4x2 8
3x1 + 2x2 12
x1 + 4x2 6
5x1 + x2 5
z = 6x1 + 4x2 MAX
x1, x2 0

P íklad 6
-x1 + x2 3
-2x1 + 6x2 6
2x1 + x2 3
z = x1 + 2x2 MAX
x1, x2 0

P íklad 7
8x1 + 4,8x2 48
2x1 - 2x2 4
4x1 - 2x2 -16
4,5x1 - 3x2 9
x1 + x2 2
z = 6x1 + 4x2 MIN
x1, x2 0
41



P íklad 8
x1 + 2x2 4
-2x1 + x2 2
x1 + x2 = 2
-x1 + x2 = 0
z = 2x1 + 3x2 MIN
x1, x2 0

P íklad 9
4x1 + 3x2 12
-2x1 + x2 2
x1 - x2 1
2x1 + 2x2 2
3x1 + 2x2 = 6
z = 4x1 + x2 MAX
x1, x2 0

P íklad 10
x1 3
x2 3
5x1 + 4x2 8
x1 + x2 6
x1 - x2 = 0
z = x1 + 2x2 MAX
x1, x2 0

42


4.3. ešení p íklad
P íklad 1
0
2
4
6
8
10
12
0 2 4 6 8 10 12 x1
x2
z(opt.)
x(opt.)

x1 = 10, x2 = 0, z = 50
P íklad 2
z(opt.)
x(opt.)
-5
-4
-3
-2
-1
0
1
2
3
4
5
-7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 x1
x2
x(opt.)
z(opt.)

x1 = 6/5, x2 = 12/5, z = 66/5

43


P íklad 3
-2,5
-2
-1,5
-1
-0,5
0
0,5
1
1,5
2
-6 -4 -2 0 2 4 6 x1
x2

Model nemá p ípustné ešení.
P íklad 4
-2,5
-2
-1,5
-1
-0,5
0
0,5
1
1,5
2
2,5
-6 -4 -2 0 2 4 6
x1
x2
z(opt.)
x(opt.)

x1 = 27/17 , x2 =25/17 , z = 131/17

44


P íklad 5
0
1
2
3
4
5
6
0 1 2 3 4 5 6
x1
x2
x(opt.)
z(opt.)
x(opt.)2
x(opt.)1

Úloha má nekone n mnoho optimálních ešení, leží na úse ce |x(opt.)1 x(opt.)2|
Hodnoty prom nných:
x(opt.)1: x1 = 0, x2 = 6, z = 24
x(opt.)2: x1 = 3,6, x2 = 0,6, z = 24

P íklad 6
-4
-3
-2
-1
0
1
2
3
4
-4 -3 -2 -1 0 1 2 3 4
x1
x2

Hodnota ú elové funkce m že neomezen r st.
45


P íklad 7
-4
-2
0
2
4
6
8
10
12
-6 -4 -2 0 2 4 6 8
x1
x2
z(opt.)
x(opt.)

x1 = 0, x2 = 2, z = 8

P íklad 8
-3
-2
-1
0
1
2
3
-4 -3 -2 -1 0 1 2 3 4
x1
x2
z(opt.)
x(opt.)

Model má jediné p ípustné ešení, které je zárove ešením optimálním
x1 = 1, x2 = 1, z = 5

46


P íklad 9
-4
-3
-2
-1
0
1
2
3
4
-3 -2 -1 0 1 2 3
x1
x2
z(opt.)
x(opt.)

x1 = 1,6 , x2 = 0,6 , z = 7

P íklad 10
0
1
2
3
4
5
6
7
8
9
10
11
12
0 1 2 3 4 5 6 7 8 9 10 11 12 x1
x2
x(opt.)
z(opt.)
x1 = 3, x2 = 3, z = 9




47


5. Simplexový algoritmus
Simplexový algoritmus je univerzální metoda pro ešení model lineárního
programování. Na rozdíl od metod grafického ešení není simplexový algoritmus limitován
rozm rem modelu.
Pro úsp šné použití simplexového algoritmu musíte znát pojmy: kanonický tvar
soustavy lineárních rovnic, bázické ešení soustavy lineárních rovnic, rovnicový tvar
modelu LP, dopl ková prom nná a její interpretace, bázická prom nná a nebázická
prom nná. Dále musíte bezpe n ovládat Jordanovu elimina ní metodu, pomocí které
dokážete p ejít od jednoho bazického ešení k jinému.
Cílem kapitoly je procvi it vlastní postup aplikace simplexové metody. Proto výše
uvedené pojmy a postupy nebudou opakovány. V p ípad nejasností se vra te k p edchozím
kapitolám cvi ebnice, p ípadn k jiné teoreticky zam ené publikaci.

5.1. ešené p íklady
P íklad 1
Pomocí simplexové metody vy ešte model lineárního programování
2x1 + 4x2 + x3 12
x1 + x2 + x3 4
2x1 – x2 + 4x3 = 6
z = 2x1 + 4x2 + x3 MAX
x1, x2, x3 0
Nejprve musíme model p evést do rovnicového tvaru p idáním dopl kových prom nných do
všech nerovnic v modelu. Princip jejich zavedení byl zopakován v kapitole 4, ešený
p íklad 2:
2x1 + 4x2 + x3 + d1 = 12
x1 + x2 + x3 – d2 = 4
2x1 – x2 + 4x3 = 6
z = 2x1 + 4x2 + x3 + 0d1 + 0d2 MAX
x1, x2, x3, d1, d2 0
Poté model p evedeme do tvaru kanonického. Na rozdíl od kapitoly 2 nebudeme zatím
používat Jordanovu elimina ní metodu, ale zavedeme do modelu tzv. „pomocné prom nné“,
v které doplní jednotkové vektory tam, kde jsou pot eba. Podívejme se na maticový zápis
matice soustavy:
48














00412
10111
01142

Ze zápisu vidíme, že matice soustavy obsahuje pouze jeden jednotkový vektor. Náleží
dopl kové prom nné d1, která byla p idána jako prom nná typu rezerva do první omezující
podmínky.
Do druhé omezující podmínky byla p idána dopl ková prom nná d2, která je typu p ekro ení,
a proto má v matici zápornou hodnotu. Sama jednotkový vektor nevytvo í, proto do druhé
omezující podmínky musíme p idat pomocnou prom nnou. Dodržíme princip indexování,
který jsme použili u prom nných dopl kových. Pomocnou prom nnou budeme ozna ovat
symbolem „p“ a indexem omezující podmínky, do které byla vložena.
Druhá omezující podmínka bude mít tedy tvar
x1 + x2 + x3 – d2 + p2 = 4
Do t etí omezující podmínky zatím nebyla p idána žádná prom nná, která by vytvo ila t etí
vektor jednotkové submatice. Proto i do t etí omezující podmínky p idáme pomocnou
prom nnou:
2x1 – x2 + 4x3 + p3 = 6
Pokud chcete model transformovat z rovnicového do kanonického tvaru, p idejte
pomocnou prom nnou do všech omezujících podmínek, které p vodn byly typu
„ “ nebo které byly rovnicemi. Získáte tak pot ebné jednotkové vektory, které vám
zkompletují jednotkovou submatici.
Pomocné prom nné stejn jako prom nné dopl kové p ebírají jednotky omezující podmínky,
do které byly p idány. Požadujeme také, aby nabývaly pouze nezáporných hodnot.
Kladnou hodnotu pomocné prom nné lze interpretovat jako míru nespln ní p vodní
omezující podmínky. Znamená to tedy, že pokud jakákoliv pomocná prom nná nabývá
v aktuálním ešení kladnou hodnotu, dané ešení není p ípustným ešením modelu lineárního
programování.
Z tohoto d vodu je požadováno, aby všechny pomocné prom nné m ly v optimálním ešení
nulovou hodnotu a byly tedy prom nnými nebázickými. To se eší jejich znevýhodn ním
v ú elové funkci.
Pokud chcete p idáváte pomocné prom nné do modelu, v ú elové funkci jim vždy
p i a te nevýhodnou (prohibitivní) sazbu. Zabráníte tak t mto prom nným vstoupit
do optimálního ešení úlohy.
Prohibitivní sazbu stanovujeme pro každý model zvláš . Bereme ohled na sazby
rozhodovacích prom nných. Prohibitivní sazbu volíme tak, aby byla v absolutní hodnot
alespo o jeden ád vyšší než je ád rozhodovacích prom nných. V minimaliza ním modelu
bude tato sazba kladná, v maximaliza ním záporná.
Náš model v kanonickém tvaru vypadá takto:
2x1 + 4x2 + x3 + d1 = 12
x1 + x2 + x3 – d2 + p2 = 4
49


2x1 – x2 + 4x3 + p3 = 6
z = 2x1 + 4x2 + x3 + 0d1 + 0d2 -10p2 - 10p3 MAX
x1, x2, x3, d1, d2, p2, p3 0
Sestavíme výchozí simplexovou tabulku. Do prvního sloupce zapíšeme vektor cen bázických
prom nných cB, do druhého jejich názvy. Do záhlaví tabulky zapíšeme názvy všech
prom nných a jejich ceny. Výchozí simplexová tabulka našeho modelu vypadá takto:
2 4 1 0 0 -10 -10
cB xB x1 x2 x3 d1 d2