Lineáris optimalizálás : elmélete és pivot algoritmusai

Illes, Tibor (2013) Lineáris optimalizálás : elmélete és pivot algoritmusai. ELTE/BME. (http://www.cs.elte.hu/opres/orr/download/IT-LP-piv...)

[thumbnail of Tibor-Illes-ORR-2013-Lineáris-optimalizálás-elmélete-és-pivot]
Preview
 Text. Filename: Tibor_Illes_ORR_2013_Line_ris_optimaliz_l_s_elm_lete_s_pivot.pdf
Final Published Version
Download (1MB)| Preview

Abstract

A jegyzet anyaga. A jegyzet vázát azok az előadás fóliák alkotják, amelyeket az elmúlt 15 évben készítettem, illetve azok, amelyek szemináriumi vagy konferencia előadásaimhoz, cikkeimhez kapcsolódnak. Az anyag felépítése teljesen az alapoktól indul, így azt remélem, hogy érdeklődő és kitartó középiskolást, aki lineáris egyenletrendszerek megoldásáról már tanult, végig tudom vezetni a lineáris programozás érdekes és szép témakörein. A lineáris algebrai bevezető célja, hogy a közös kiindulási alapokat lerakja, rávilágítson a pivot technika szerepére; a pivot tábla, mint modell szerepére és előkészítse a következő fejezetek anyagát. A második fejezet a lineáris egyenletrendszerek megoldhatóságával és megoldásával foglalkozik. Ebben a fejezetben jelenik meg az első alternatíva tétel a Rouché-Kronecker-Capelli lemma. Kedvencem a Klafszky Emiltől származó un. Farkas-Minty-féle pivot táblás változat, amely tömören, képszerűen foglalja össze az állítást, ha az olvasó már megbarátkozott a pivot táblák világával. A lemma elnevezése is Klafszky Emiltől származik, és akkor válik igazán érthetővé, amikor a következő fejezetben a lemma előjeles változatát fogalmazzuk meg. Klafszky Emil, ennek a lemmának a kapcsán többször beszélt arról, hogy a Farkas-Minty előjeles lemma a Farkas lemmának és a Minty-féle színezési lemmának egy szép közös megfogalmazása, ha az előjeleket - a Minty lemma esetén - megfelelően értelmezzük. A második fejezetben a megoldások méretével kapcsolatos eredmények nem szerepeltek a Klafszky Emillel és Terlaky Tamással elképzelt jegyzet témakörei között. Ezek szerepe a harmadik fejezetben található MBU-szimplex algoritmus elemzéséhez kapcsolódnak először, amelyik szintén az elmúlt évek alatt jelent meg a jegyzet témakörei között. A harmadik fejezet geometriai jellegű része az új struktúrában került előre. Így a harmadik fejezet már jelentősen eltér az eredeti tervektől, annak ellenére, hogy a jegyzet egyik legérdekesebb Klafszky Emiltől származik. A 4. és az 5. fejezetek annak ellenére, hogy klasszikus eredményeket tárgyalunk bennük, mégis - a mai napig is újszerű tárgyalásról van szó - hiszen a végtelenül egyszerű, Terlaky-féle criss-cross algoritmus végességének a bizonyításán alapul az erős dualitás tétel konstruktív bizonyítása. A criss-cross algoritmus végesség bizonyítása egyszerűbb, mint Terlaky Tamás eredeti, az 1980-as évek közepéről származó bizonyítása és Klafszky Emil egy észrevételén alapul.

CORE (COnnecting REpositories)