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

Translated title of the contribution: Linear optimization: theory and pivot algorithms

Tibor Illes

Research output: Book/ReportOther report

123 Downloads (Pure)

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.
Translated title of the contributionLinear optimization: theory and pivot algorithms
Original languageOther
Number of pages158
Volume2013
Publication statusPublished - 31 Oct 2013

Publication series

NameOperations Research Report
PublisherELTE/BME
ISSN (Print)1215-5918

Keywords

  • linear algebra
  • linear equations
  • pivot technology

Fingerprint

Dive into the research topics of 'Linear optimization: theory and pivot algorithms'. Together they form a unique fingerprint.

Cite this