Winfried Hochstättler

2 Winfried Hochstättler Lineárna optimalizácia

6 Predhovor VII Za čo vďačím Alexandrovi Malkisovi, ktorý ma upozornil (minimálne) na dve miesta, kde som nechal telo Q nepozorovane a kde to nebolo potrebné. Tiež by som sa chcel poďakovať za spoluprácu Stephanovi Dominique Andresovi, Immanuelovi Albrechtovi, Sylvii Sikore a Michaelovi Wilhelmimu. Hagen, v januári 2017 Winfried Hochstättler

7 Obsah 1 Lineárna optimalizácia - úloha a modelovanie Prvé príklady Problém so stravou Chamtivosť nie je vždy dobrá Problém miešania Všeobecné techniky úloh s lineárnou optimalizáciou pre ekvivalentné transformácie Riešenie problému so stravou od rezancov po zemiaky Grafické pokrytie metód a kombinácie Afinné medzipriestory ku konvexnému kužeľu v K n Konvexné množiny v K n Súhrn Duality Iný pohľad na problém stravovania Farkas Lemma Veta o dualite lineárneho programovania Dualizácia lineárnych programov Veta o komplementárnom sklze Mnohostena Dvojtriedna spoločnosť? Bočné povrchy Fazety Rohy a hrany Napríklad permutahedron Kónický mriežka bočného povrchu a hustá verzia Farkovej Lemmy IX

9 Obsah XI 8 Metódy vnútorného bodu Karmarkarova metóda Projektívna transformácia jednotky simplex Geometrická predstava Karmarkarovej metódy Pre analýzu správnosti a behu Karmarkarova normálna forma Algoritmus sledovania trasy Geometrické nápady Niektoré prípravy Šikmo-symetrický sebap duálny model Centrálna cesta a optimálna Oddiel Nájdenie optimálneho oddielu Nájdenie presného riešenia Všeobecný postup vnútorného bodu Outlook Navrhované riešenia cvičení Navrhované riešenia pre kapitolu Navrhnuté riešenia pre kapitolu Navrhnuté riešenia pre kapitolu Navrhnuté riešenia pre kapitolu Navrhnuté riešenia pre kapitolu Navrhované riešenia pre kapitolu

---