Vypracovane-zkouskove-otazky - teorie

Zápis vektorem bázického řešení

• např. XB = (0,0,b1,0,b2,b3) , obsahuje všechny proměnné jak jdou za sebou od X1,X2,…Xn, přes d1,d2….dn až po p1, p2….pn, s tím že všechny nebázické proměnné zapisujeme s jejich nulovou hodnotou a bázické s hodnotou vektoru pravých stran b

Zápis vektorem obecného řešení

pomocí něj přepisujeme výsledek do podoby parametrického řešení, jednotlivé proměnné (parametry) zapisujeme přímo názvy a bázické proměnné vyjadřujeme pomocí proměnných nebazických

x1

x2

b1 – a11 – a12

X0= d2

B2 - a21 –a 22 - +d2

B3 – a31 – a32

5) Co je to dualita modelů lineárního programování? Uveďte alespoň jeden příklad, kdy nám teorie duality výrazně zjednodušuje řešení úlohy.

- dualita je vztah mezi dvěma vektorovými prostory. V případě úloh LP se dualita projevuje tak, že ke každému modelu LP se dá přiřadit jeho duální verze, která má tytéž parametry, jako původní model, ale s jinou interpretací.

- duality se využívá zejména při analýze výsledků, kdy tvz. duální ceny poskytují důležité informace pro rozhodování

Princip: otočení úhlu pohledu o 90o

Matice koeficientů A v primárním modelu a matice AT v duálním =transponovaná

• Vektor pravých stran b v primárním modelu a vektor cen b v duálním

• Vektor cen c v primárním modelu a vektor pravých stran c v duálním

• Počet rozhodovacích proměnných v primárním modelu a počet omezujících podmínek v duálním

• Počet omezujících podmínek v primárním modelu se rovná počtu rozhodovacích proměnných v duálním modelu

• Největší problém: typ omezení a podmínky nezápornosti proměnných

6) Popište vztahy mezi prvky duálně sdružených úloh.

• Primární úloha má optimální řešení xo právě tehdy, když má duální úloha
  optimální řešení yo .

• Navíc platí cTxo = bTyo.

• Nechť má primární úloha přípustné řešení x a duální úloha přípustné
  řešení y, pro která platí cTx = bTy, pak jsou tato řešení optimálními řešeními obou úloh.

Omezující podmínky duálního modelu

Primární model Duální model Xj >= 0 Podmínka nezápornosti Ovlivňuje ji Max a Min

Yi <= Cj → MAX

Yi >= Cj → MIN

Xj <= 0 Podmínka nekladnosti Opačné omezení ovlivněné také Max Min

Yi >= Cj → MAX

Yi <= Cj → MIN

Xj………s.l. (bez omezení)- proměnné Proměnná není omezena Omezující podmínka typu rovnice Yi = Cj

Určení podmínek nezápornosti duálního modelu

Primární model Duální model

AijXj <= Bi →MAX

AijXj >= Bi →MIN

Směr optimalizace Klasická podmínka nezápornosti Yi >= 0

AijXj >= Bi →MAX

AijXj <= Bi →MIN

Typ omezení je opačný Podmínka nekladnosti Yi <= 0 AijXj = Bi typ omezení je rovnice Proměnná není omezena Yi……s.l.

Př.

11x1 + 12x2 + 13x3 <= 10 11y1 + 21y2 + 31y3 + 41y4 >= 100

21x1 + 22x2 + 23x3 >= 20 12y1 + 22y2 + 32y3 + 42y4 = 200