Linear optimization: theory and pivot algorithms

Tibor Illes

Research output: Book/ReportOther report

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
LanguageOther
Number of pages158
Volume2013
Publication statusPublished - 31 Oct 2013

Publication series

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

Fingerprint

Optimization Theory
Linear Optimization
Pivot
Lemma

Keywords

  • linear algebra
  • linear equations
  • pivot technology

Cite this

Illes, T. (2013). Lineáris optimalizálás: elmélete és pivot algoritmusai. (Operations Research Report).
Illes, Tibor. / Lineáris optimalizálás : elmélete és pivot algoritmusai. 2013. 158 p. (Operations Research Report).
@book{19d6e84d8d2f4f138a8d0ae1afafa2ae,
title = "Line{\'a}ris optimaliz{\'a}l{\'a}s: elm{\'e}lete {\'e}s pivot algoritmusai",
abstract = "A jegyzet anyaga. A jegyzet v{\'a}z{\'a}t azok az előad{\'a}s f{\'o}li{\'a}k alkotj{\'a}k, amelyeket az elm{\'u}lt 15 {\'e}vben k{\'e}sz{\'i}tettem, illetve azok, amelyek szemin{\'a}riumi vagy konferencia előad{\'a}saimhoz, cikkeimhez kapcsol{\'o}dnak. Az anyag fel{\'e}p{\'i}t{\'e}se teljesen az alapokt{\'o}l indul, {\'i}gy azt rem{\'e}lem, hogy {\'e}rdeklődő {\'e}s kitart{\'o} k{\"o}z{\'e}piskol{\'a}st, aki line{\'a}ris egyenletrendszerek megold{\'a}s{\'a}r{\'o}l m{\'a}r tanult, v{\'e}gig tudom vezetni a line{\'a}ris programoz{\'a}s {\'e}rdekes {\'e}s sz{\'e}p t{\'e}mak{\"o}rein. A line{\'a}ris algebrai bevezető c{\'e}lja, hogy a k{\"o}z{\"o}s kiindul{\'a}si alapokat lerakja, r{\'a}vil{\'a}g{\'i}tson a pivot technika szerep{\'e}re; a pivot t{\'a}bla, mint modell szerep{\'e}re {\'e}s elők{\'e}sz{\'i}tse a k{\"o}vetkező fejezetek anyag{\'a}t. A m{\'a}sodik fejezet a line{\'a}ris egyenletrendszerek megoldhat{\'o}s{\'a}g{\'a}val {\'e}s megold{\'a}s{\'a}val foglalkozik. Ebben a fejezetben jelenik meg az első alternat{\'i}va t{\'e}tel a Rouch{\'e}-Kronecker-Capelli lemma. Kedvencem a Klafszky Emiltől sz{\'a}rmaz{\'o} un. Farkas-Minty-f{\'e}le pivot t{\'a}bl{\'a}s v{\'a}ltozat, amely t{\"o}m{\"o}ren, k{\'e}pszerűen foglalja {\"o}ssze az {\'a}ll{\'i}t{\'a}st, ha az olvas{\'o} m{\'a}r megbar{\'a}tkozott a pivot t{\'a}bl{\'a}k vil{\'a}g{\'a}val. A lemma elnevez{\'e}se is Klafszky Emiltől sz{\'a}rmazik, {\'e}s akkor v{\'a}lik igaz{\'a}n {\'e}rthetőv{\'e}, amikor a k{\"o}vetkező fejezetben a lemma előjeles v{\'a}ltozat{\'a}t fogalmazzuk meg. Klafszky Emil, ennek a lemm{\'a}nak a kapcs{\'a}n t{\"o}bbsz{\"o}r besz{\'e}lt arr{\'o}l, hogy a Farkas-Minty előjeles lemma a Farkas lemm{\'a}nak {\'e}s a Minty-f{\'e}le sz{\'i}nez{\'e}si lemm{\'a}nak egy sz{\'e}p k{\"o}z{\"o}s megfogalmaz{\'a}sa, ha az előjeleket - a Minty lemma eset{\'e}n - megfelelően {\'e}rtelmezz{\"u}k. A m{\'a}sodik fejezetben a megold{\'a}sok m{\'e}ret{\'e}vel kapcsolatos eredm{\'e}nyek nem szerepeltek a Klafszky Emillel {\'e}s Terlaky Tam{\'a}ssal elk{\'e}pzelt jegyzet t{\'e}mak{\"o}rei k{\"o}z{\"o}tt. Ezek szerepe a harmadik fejezetben tal{\'a}lhat{\'o} MBU-szimplex algoritmus elemz{\'e}s{\'e}hez kapcsol{\'o}dnak elősz{\"o}r, amelyik szint{\'e}n az elm{\'u}lt {\'e}vek alatt jelent meg a jegyzet t{\'e}mak{\"o}rei k{\"o}z{\"o}tt. A harmadik fejezet geometriai jellegű r{\'e}sze az {\'u}j strukt{\'u}r{\'a}ban ker{\"u}lt előre. {\'I}gy a harmadik fejezet m{\'a}r jelentősen elt{\'e}r az eredeti tervektől, annak ellen{\'e}re, hogy a jegyzet egyik leg{\'e}rdekesebb Klafszky Emiltől sz{\'a}rmazik. A 4. {\'e}s az 5. fejezetek annak ellen{\'e}re, hogy klasszikus eredm{\'e}nyeket t{\'a}rgyalunk benn{\"u}k, m{\'e}gis - a mai napig is {\'u}jszerű t{\'a}rgyal{\'a}sr{\'o}l van sz{\'o} - hiszen a v{\'e}gtelen{\"u}l egyszerű, Terlaky-f{\'e}le criss-cross algoritmus v{\'e}gess{\'e}g{\'e}nek a bizony{\'i}t{\'a}s{\'a}n alapul az erős dualit{\'a}s t{\'e}tel konstrukt{\'i}v bizony{\'i}t{\'a}sa. A criss-cross algoritmus v{\'e}gess{\'e}g bizony{\'i}t{\'a}sa egyszerűbb, mint Terlaky Tam{\'a}s eredeti, az 1980-as {\'e}vek k{\"o}zep{\'e}ről sz{\'a}rmaz{\'o} bizony{\'i}t{\'a}sa {\'e}s Klafszky Emil egy {\'e}szrev{\'e}tel{\'e}n alapul.",
keywords = "linear algebra, linear equations, pivot technology",
author = "Tibor Illes",
note = "Lecture Notes",
year = "2013",
month = "10",
day = "31",
language = "Other",
volume = "2013",
series = "Operations Research Report",
publisher = "ELTE/BME",

}

Illes, T 2013, Lineáris optimalizálás: elmélete és pivot algoritmusai. Operations Research Report, vol. 2013.

Lineáris optimalizálás : elmélete és pivot algoritmusai. / Illes, Tibor.

2013. 158 p. (Operations Research Report).

Research output: Book/ReportOther report

TY - BOOK

T1 - Lineáris optimalizálás

T2 - elmélete és pivot algoritmusai

AU - Illes, Tibor

N1 - Lecture Notes

PY - 2013/10/31

Y1 - 2013/10/31

N2 - 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.

AB - 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.

KW - linear algebra

KW - linear equations

KW - pivot technology

UR - http://www.cs.elte.hu/opres/orr/download/IT-LP-pivot-jegyzet-20131031.pdf

M3 - Other report

VL - 2013

T3 - Operations Research Report

BT - Lineáris optimalizálás

ER -

Illes T. Lineáris optimalizálás: elmélete és pivot algoritmusai. 2013. 158 p. (Operations Research Report).