Ekonomicko-matematické
metody 5
přednáší
Mgr. Jiří Mazurek, Ph.D.

Úlohy lineárního programování (LP)
I
2

Primární úloha LP v kanonickém tvaru:
I
3

(P) a (D) úloha LP v kanonickém tvaru
•Úloha LP v kanonickém tvaru
I
4

(P) a (D) úloha LP v kanonickém tvaru
•Úloha LP v kanonickém tvaru
I
5

Úlohy LP v kanonickém tvaru
I
6

Ekonomická interpretace duální proměnné
7


Ekonomická interpretace duální proměnné II
8


Úlohy LP v kanonickém tvaru
I
9

I
10


Věta o silné dualitě (princip duality)
I
11

Věta o silné dualitě (princip duality)
•Úloha (P) má optimální řešení právě tehdy, když úloha (D) má optimální řešení.
 To jest, optimální řešení mají
•buď obě úlohy současně,
•anebo žádná z nich.
•Jestliže obě úlohy mají optimální řešení, potom jejich optimální hodnoty se rovnají.
I
12

Důsledek všech uvedených tvrzení
•Pro úlohy (P) a (D) nastává právě jedna
z následujících možností:
•obě úlohy (P) a (D) jsou přípustné, mají optimální řešení
a platí rovnost optimálních hodnot,
•úloha (P) není přípustná a úloha (D) není omezená zdola,
•úloha (D) není přípustná a úloha (P) není omezená shora,
•obě úlohy (P) a (D) jsou nepřípustné.
I
13

Úlohy LP v norm. a std. tvaru
II
14

Úlohy lineárního programování (LP)
III
15

Primární úloha LP ve standardním tvaru:
III
16

Úlohy LP ve standardním tvaru - příklad
II
17

Základní pojmy LP
III
18
Přípustné řešení: každý vektor x, který splňuje podmínky:

Základní pojmy LP
III
19

Základní pojmy LP
III
20

Základní pojmy LP
III
21

Simplexová metoda (algoritmus)
III
22
Autor: G. Dantzig (1947).
Simplexový algoritmus efektivně prohledává tzv. základní (bazická) řešení úloh lineárního
programování, kterých je konečný počet a hledá mezi nimi řešení optimální.
Optimální řešení je takové základní řešení, které poskytuje nejlepší hodnotu účelové funkce.
Metoda souvisí s vlastnostmi polytopu v N dimenzionálním prostoru. Řešená úloha je tak i graficky
interpretovatelná – hledají se co nejvzdálenější vrcholy polytopu.

Simplexová metoda
III
23

Simplexová metoda
III
24

Simplexová metoda
III
25

Simplexová metoda
III
26

Simplexová metoda
III
27

Simplexová metoda
III
28

Simplexová metoda
III
29

Simplexová metoda
III
30

Simplexová metoda
III
31

Simplexová metoda
III
32

Simplexová metoda
III
33