Matematický základ lineární optimalizace

Recenze čtenářů

Aktuálně nejsou k dispozici žádné recenze čtenářů. Hodnocení je založeno na 4 hlasů.

Původní název:

A Mathematical Primer on Linear Optimization

Obsah knihy:

Kniha poskytuje samostatný matematický úvod do lineární optimalizace pro vysokoškolské studenty matematiky. Kniha je stejně tak vhodná pro studenty přírodovědných, technických a ekonomických oborů, kteří mají zájem o hlubší pochopení matematických aspektů tohoto tématu.

Problém lineární optimalizace je analyzován z různých hledisek: topologického, algebraického, geometrického, logického a algoritmického. Přesto nejsou vyžadovány žádné předchozí znalosti těchto předmětů. Podstatné detaily jsou vždy uvedeny ve speciální části na konci každé kapitoly.

Odborný materiál je ilustrován četnými příklady, úlohami s plně zpracovanými řešeními a řadou navržených cvičení.

V kapitole 1 je představeno několik formulací lineárního optimalizačního problému, které se týkají přípustných vektorů a optimalizátorů. V kapitole 2 jsou pak diskutovány postačující podmínky pro existenci optimalizátorů založené na topologických technikách.

Hlavním cílem kapitoly 3 je poskytnout způsob, jak rozhodnout, zda přípustný vektor je či není optimalizátorem, a to na základě Farkasova lemmatu. V kapitole 4 je použita lineární algebra pro výpočet optimalizátorů prostřednictvím základních přípustných vektorů. Cílem kapitoly 5 je geometrická charakterizace těchto vektorů.

Dualita je diskutována v kapitole 6, která poskytuje ještě novou techniku pro nalezení optimalizátorů. V kapitole 7 je uveden úvod do výpočetní složitosti s cílem analyzovat efektivitu lineárních optimalizačních algoritmů. Ukazuje se, že složitost algoritmu hrubé síly není polynomiální.

Kapitola 8 je zaměřena na simplexový algoritmus. Obsahuje důkaz jeho správnosti a úplnosti a vysvětlení jeho nepolynomiální složitosti.

Konečně kapitola 9 se soustřeďuje na celočíselný optimalizační problém s důrazem na zcela unimodularitu. Analyzován je algoritmus založený na technice Branch and Bound.