Grafické řešení úloh lineárního programování
Má smysl pouze tehdy, je – li počet proměnných roven 2 (řešení v rovině), případně 3 (řešení v prostoru).
Věta lineárního programování: K vyhledání optimálního řešení úlohy lineárního programování stačí prohledat krajní body množiny přípustných řešení (základní řešení), pokud ovšem optimální řešení existuje.
Dále platí: Má – li úloha lineárního programování jedno optimální řešení, pak je toto optimální řešení zároveň řešením základním. Má – li úloha nekonečně mnoho optimálních řešení, pak alespoň jedno optimální řešení je zároveň řešením základním.
Př. 1: Maximalizujte funkci 2x14x2 za následujících podmínek:
2x1x2 2,
x12x2 8,
x1, x2 0.
Postup: 1) Nalezneme množinu přípustných řešení (množina je vymezena podmínkami).
2) Vyhledáme optimální řešení úlohy.
2
2x1 x2 - rovnice přímky procházející body
0;2
a
1;0
. 82 2
1 x
x - rovnice přímky procházející body
0;4
a
8;0
.Pro účelovou funkci sestrojíme skupinu přímek:
4 4 2 1 2
x x
z - rovnice přímky procházející body
0;1
a
2;0
. 84 2 1 2
x x
z - rovnice přímky procházející body
0;2
a
4;0
.→ tato úloha má nekonečně mnoho řešení.
Př. 2: Maximalizujte funkci 2x1 6x2 za podmínek:
3x12x2 6,
x1x2 1,
x12x2 1,
x1, x2 0. 6
2
3x1 x2 - rovnice přímky procházející body
0;3
a
2;0
.2 1
1 x
x - rovnice přímky procházející body
0;1
a
1;0
. 12 2
1
x x - rovnice přímky procházející body 2
; 1
0 a
1;0
.→ tato úloha nemá řešení, neboť množina přípustných řešení je množina prázdná.
Př. 3: Minimalizujte funkci x12x2 za podmínek:
x13x2 6,
2x14x2 8,
x13x2 6,
x1, x2 0. 6
3 2
1 x
x - rovnice přímky procházející body
0;2
a
6;0
. 84
2x1 x2 - rovnice přímky procházející body
0;2
a
4;0
. 63 2
1 x
x - rovnice přímky procházející body
0;2
a
6;0
. Pro účelovou funkci sestrojíme skupinu přímek:2 2 2
1
x x
z - rovnice přímky procházející body
0;1
a
2;0
. 42 2
1
x x
z - rovnice přímky procházející body
0;2
a
4;0
.→ tato úloha má jedno optimální řešení a to pro x1 0 a x2 2.
