Optimalizácia SIMPLEX metódou

Úvod do lineárneho programovania

Lineárnym programovaním nazývame postup riešenia takého optimalizačného problému, ktorého účelová funkcia je lineárna, teda v tvare:



a ohraničenia problému tvorí sústava lineárnych rovníc a nerovníc.

Úlohu lineárneho programovania je možné zapísať v maticovom tvare:



kde jednotlivé symboly predstavujú:

	x - vektor optimalizačných premenných
	c - vektor argumentov účelovej funkcie, ktorý má rovnaký rozmer ako vektor x. c^T predstavuje transponovaný vektor, ktorým je možné násobiť x.
	A - matica koeficientov ohraničení, ktoré vymedzujú množinu prípustných riešení. Počet ohraničení, t.j. počet riadkov matice označíme m.
	b - vektor pravých strán ohraničení. Dva vektory - Ax a b je možné porovnať práve vtedy, keď sa rovnajú ich rozmery. Preto:

Grafická interpretácia problémov lin. programovania

Majme dvojrozmerný lineárny optimalizaèný problém, ktorý je zadaný v tvare:

Vidíme, že všetky zadané ohraničenia sú v tvare nerovnosti. V karteziánskej súradnicovej sústave danej premennými x₁ a x₂ ( x₂ = f(x₁) ) predstavujú tieto ohraničenia polroviny (ohraničenia v tvare rovnosti by predstavovali priamky). Množina prípustných riešení je daná prienikom všetkých ohraničení. Všetky ohraničenia zakreslíme do sústavy a získame tak množinu M.

Obr. 1 - grafická interpretácia množiny prípustných riešení M

Účelová funkcia je daná rovnicou:

Rovnica priamky v súradnicovej sústave x₂ = f(x₁), daná účelovou funkciou, má tvar:

Vidíme, že smernica tejto priamky sa s hodnotou účelovej funkcie J nemení. Nazveme ju preto vrstevnica účelovej funkcie. Položme najprv J = 0 a zakreslime vrstevnicu do sústavy:

Obr. 2 - grafické znázornenie vrstevnice účelovej funkcie

Cieľom riešenia je maximalizovať hodnotu J, pričom zvyšovaním tejto hodnoty sa vrstevnica posúva smerom nahor (zvyšovaním J rastie x₂ ). Hľadáme preto najvzdialenejší bod množiny prípustných riešení M v smere rastu J (smer vyznačený šípkou).

Obr. 3 - grafické znázornenie optimálneho riešenia

Posúvaním vrstevnice smerom nahor sme našli bod, ktorý je súčasťou množiny M a pre každý iný bod z má účelová funkcia menšiu hodnotu. Tento bod je hľadaným optimálnym riešením problému.
Optimálne riešenie je teda dané prienikom dvoch priamok ohraničení:

Vyriešením tejto sústavy rovníc dostaneme hodnoty premenných v optime:

Dosadením x1 a x2 do rovnice úèelovej funkcie zistíme jej optimálnu hodnotu: