Vlastnosti úlohy lineárního programování a jejího řešení

17.4.4

Vlastnosti úlohy lineárního programování a jejího řešení

Doc. Ing. Alois Fiala, CSc.

Přípustné řešení úlohy LP je takový vektor x, který vyhovuje všem omezujícím podmínkám. Optimální řešení je takové přípustné řešení, v němž účelová funkce nabývá svého optima (maxima v případě maximalizační úlohy, minima v případě minimalizační úlohy).

Je-li množina přípustných řešení úlohy LP neprázdná, je to konvexní polyedrická množina. To je taková množina, která je průnikem konečného počtu nadrovin (ty odpovídají rovnicím) a uzavřených poloprostorů (ty odpovídají nerovnicím a podmínkám nezápornosti).

Řekneme, že množina M je konvexní množinou, jestliže s libovolnými dvěma body x₁ Є M, x₂ Є M leží v této množině také všechny body

x = t x₁ + (1–t) x₂

kde 0 < t < 1. Geometricky to znamená, že množina M spolu s libovolnými dvěma různými body musí obsahovat i úsečku spojující tyto dva body. Bod x z konvexní množiny M se nazývá krajním bodem nebo vrcholem této množiny, jestliže neleží na úsečce spojující dva jiné body této množiny.

Konvexní polyedrická množina má konečný počet krajních bodů a může být ohraničená nebo neohraničená. Ohraničená konvexní polyedrická množina se nazývá konvexní polyedr. Jestliže je množina optimálních řešení úlohy LP neprázdná, je to také konvexní polyedrická množina, která může být ohraničená nebo neohraničená. Ilustrací uvedených vlastností jsou dříve použité obrázky, ukazující příklady grafického řešení úloh LP.

Mějme úlohu LP ve standardním tvaru:

max {c^T x | Ax = b, x ≥ 0}.

Nechť A je typu (m, n) o hodnosti m a nechť B je matice tvořená m lineárně nezávislými sloupci matice A. Pak matice B se nazývá bází uvedené úlohy LP. Proměnné odpovídající sloupcům matice B se nazývají bazické a ostatní proměnné se nazývají nebazické.

Každé bázi odpovídá právě jedno bazické řešení soustavy Ax = b, určené následujícím způsobem. Označme symbolem x_B vektor bazických proměnných odpovídajících bázi B a symbolem x_N vektor nebazických proměnných. Položme nebazické proměnné rovny nule, tj. x_N = 0. Pak vektor x_B je řešením rovnice Bx_B = b, a můžeme jej tedy vyjádřit ve tvaru x_B = B^–1 b, kde B^–1 je matice inverzní k matici…