Simplex módszer

Nem tévesztendő össze a "simplex módszerrel" - egy tetszőleges függvény optimalizálásának módszerével. Lásd: Nelder-Mead módszer

A szimplex módszer a lineáris programozás optimalizálási problémájának megoldására szolgáló algoritmus egy konvex poliéder csúcsainak többdimenziós térben történő felsorolásával.

A módszer lényege: olyan alapmegoldások felépítése, amelyeken a lineáris funkcionális monoton csökken, egészen addig a helyzetig, amikor a lokális optimalitás szükséges feltételei teljesülnek.

L. V. Kantorovich "A termelés szervezésének és tervezésének matematikai módszerei" (1939) című munkájában először fogalmazták meg a matematika egy új ágának alapelveit, amely később lineáris programozás néven vált ismertté. [egy]

Történelmileg a lineáris programozás általános problémáját először 1947-ben vetette fel George Bernard Dantzig , Marshall Wood és munkatársaik az Egyesült Államok Légierejének Minisztériumában. Ez a csoport akkoriban a matematikai és kapcsolódó módszerek katonai és tervezési problémák megoldásának lehetőségét vizsgálta. Később a Légierőnél Project SCOOP néven kutatócsoportot szerveztek ezen ötletek kidolgozására. A lineáris programozási probléma első sikeres megoldását SEAC számítógépen 1952 januárjában hajtották végre [2] .

Leírás

A lineáris programozás problémája az, hogy egy többdimenziós téren adott lineáris megszorítások mellett szükség van néhány lineáris függvény maximalizálására vagy minimalizálására .

Vegyük észre, hogy a változókra vonatkozó lineáris egyenlőtlenségek mindegyike egy félteret határol a megfelelő lineáris térben. Ennek eredményeként minden egyenlőtlenség korlátoz néhány (esetleg végtelen) konvex poliédert, amelyet poliéder komplexumnak is neveznek . A W ( x ) = c egyenlet , ahol W ( x ) egy maximalizált (vagy minimalizált) lineáris függvény, egy L(c) hipersíkot generál . A c -től való függés párhuzamos hipersíkok családját generálja. Ekkor az extremális probléma a következő megfogalmazást kapja: meg kell találni a legnagyobb c -t úgy, hogy az L(c) hipersík legalább egy pontban metszi a poliédert. Figyeljük meg, hogy egy optimális hipersík és egy poliéder metszéspontja legalább egy csúcsot tartalmaz, és több is lesz, ha a metszés élt vagy k - dimenziós lapot tartalmaz. Ezért a funkcionális maximuma a poliéder csúcsaiban kereshető. A szimplex módszer elve az, hogy a poliéder egyik csúcsát választjuk, ami után megkezdődik a mozgás az élei mentén a csúcstól a csúcsig a funkcionális érték növelésének irányába. Ha az él mentén az aktuális csúcsból egy másik csúcsba, ahol a funkcionális magasabb értéke nem lehetséges, úgy tekintjük, hogy megtaláltuk c optimális értékét .

A szimplex módszerrel végzett számítási sorrend két fő fázisra osztható :

megtalálni a megvalósítható megoldások halmazának kezdeti csúcsát,
szekvenciális átmenet egyik csúcsból a másikba, ami a célfüggvény értékének optimalizálásához vezet.

Sőt, bizonyos esetekben a kezdeti megoldás kézenfekvő, vagy annak meghatározása nem igényel bonyolult számításokat, például amikor az összes megszorítást „kisebb vagy egyenlő” alakú egyenlőtlenségek reprezentálják (akkor a nulla vektor mindenképpen megvalósítható megoldás , bár nagy valószínűséggel messze nem a legoptimálisabb) . Ilyen problémák esetén a szimplex módszer első fázisa teljesen elhagyható. A szimplex módszer egyfázisúra és kétfázisúra oszlik .

A szimplex módszer algoritmusa

Megerősített problémafelvetés

Tekintsük a következő lineáris programozási problémát :

c^{T}x\to \max ,Ax\leqslant b,x\geqslant 0,b\geqslant 0.

Tegyük fel most ezt a problémát egy ekvivalens továbbfejlesztett formában. Z -t kell maximalizálni , ahol:

{\begin{bmatrix}1&-c^{T}&0\\0&A&E\end{bmatrix}}{\begin{bmatrix}Z\\x\\x_{s}\end{bmatrix}}={\begin{ bmatrix}0\\b\end{bmatrix}},x,x_{s}\geqslant 0

Itt x az eredeti lineáris funkcionális változói, x s új változók, amelyek úgy egészítik ki a régieket, hogy az egyenlőtlenség egyenlőséggé alakul, c az eredeti lineáris funkcionális együtthatói, Z a maximalizálandó változó. A félterek és a metszéspontban a megvalósítható megoldások halmazát reprezentáló poliédert alkotnak. A változók és az egyenletek számának különbsége adja meg a szabadsági fokok számát. Leegyszerűsítve, ha egy poliéder csúcsát vesszük figyelembe, akkor ez azoknak az éleknek a száma, amelyek mentén tovább tudunk haladni. Ezután ehhez a számú változóhoz 0 értéket rendelhetünk, és "nem alapvetőnek" nevezhetjük őket . Ebben az esetben a fennmaradó változók kiszámítása egyedileg történik, és "alap" -nak nevezik őket . Ezeknek a változóknak ugyanazt a halmazát nevezzük bázisnak . Az eredményül kapott pont a nem alapváltozóknak megfelelő hipersíkok metszéspontjában lévő csúcs lesz. Annak érdekében, hogy megtaláljuk az ún. a kezdeti elfogadható megoldást (a csúcsot, ahonnan elindulunk), minden x kezdőváltozóhoz 0 értéket rendelünk , és nem alapváltozónak tekintjük, az újakat pedig alapvetőnek. Ebben az esetben a kezdeti elfogadható megoldás kiszámítása egyedileg történik: . $x\geqslant 0$ $x_{s}\geqslant 0$ ${\mathbf {x}}_{{si}}={\mathbf {b}}_{i}$

Algoritmus

Most bemutatjuk az algoritmus lépéseit. Minden lépésben megváltoztatjuk az alapvektorok és a nem alapvektorok halmazait (mozogunk az élek mentén), és a mátrix így fog kinézni:

{\begin{bmatrix}1&c_{B}^{T}B^{{-1}}Ac^{T}&c_{B}^{T}B^{{-1}}\\0&B^{{- 1}}A&B^{{-1}}\end{bmatrix}}{\begin{bmatrix}Z\\x\\x_{s}\end{bmatrix}}={\begin{bmatrix}c_{B} ^{T}B^{{-1}}b\\B^{{-1}}b\end{bmátrix}},

ahol az alapváltozóknak megfelelő vektor együtthatói (a változók 0-nak felelnek meg), az alapváltozóknak megfelelő oszlopok vannak . A fennmaradó oszlopok által alkotott mátrixot jelöli . Hogy a mátrixnak miért lesz ilyen alakja, azt az algoritmus lépéseinek leírásában magyarázzuk meg. $c_{B}$ $c$ $x_{s}$ $B$ $[{\mathbf {A}}{\mathbf {E}}]$ $D$

Első lépés .

Kiválasztjuk a kezdeti érvényes értéket, ahogy fentebb jeleztük. Első lépésben az identitásmátrixot, mivel az alapváltozók a . ugyanazon okokból nullvektor. $B$ $x_{s}$ $c_{B}$

Második lépés

Mutassuk meg, hogy a kifejezésben csak a nem alapváltozók rendelkeznek nullától eltérő együtthatóval. Vegyük észre, hogy a kifejezésből az alapváltozók egyértelműen nem alapvető változókkal vannak kifejezve, mivel az alapváltozók száma megegyezik az egyenletek számával. Legyenek alapvető és nem alapvető változók egy adott iterációnál. Az egyenlet átírható így . Szorozzuk meg a bal oldalon: . Így az alapváltozókat nem alapváltozókkal fejeztük ki , az egyenlőség bal oldalával ekvivalens kifejezésben pedig minden alapváltozó egységegyütthatós. Ha tehát az egyenlőséghez egyenlőséget adunk , akkor a kapott egyenlőségben minden alapváltozó nulla együtthatós lesz - minden x alakú alapváltozó le lesz redukálva, és az x s formájú alapváltozók nem fognak szerepelni a kifejezésben . $(c_{B}^{T}B^{{-1}}Ac^{T})x+(c_{B}^{T}B^{{-1}})x_{s}$ $Ax+x_{s}=b$ $x'$ $x''$ $Ax+x_{s}=b$ $Bx'+Dx''=b$ $B^{{-1}}$ $x'+B^{{-1}}Dx''=B^{{-1}}b$ $B^{{-1}}Ax+B^{{-1}}x_{s}$ $Zc^{T}x=0$ $c_{B}^{T}B^{{-1}}Ax+c_{B}^{T}B^{{-1}}x_{s}$ $c_{B}^{T}B^{{-1}}x_{s}$

Válasszunk egy élt, amely mentén haladunk. Mivel Z -t szeretnénk maximalizálni , olyan változót kell választani, amely a leginkább csökkenti a kifejezést

$(c_{B}^{T}B^{{-1}}Ac^{T})x+(c_{B}^{T}B^{{-1}})x_{s}$ .

Ehhez olyan változót választunk, amelynek modulusában a legnagyobb a negatív együtthatója [3] . Ha nincsenek ilyen változók, vagyis ennek a kifejezésnek minden együtthatója nem negatív, akkor elérkeztünk a kívánt csúcshoz, és megtaláltuk az optimális megoldást. Ellenkező esetben elkezdjük növelni ezt a nem alapváltozót, vagyis a neki megfelelő él mentén haladunk. Nevezzük ezt a változót bemenetnek .

Harmadik lépés

Most meg kell értenünk, hogy a bemeneti változó növekedésével melyik alapváltozó lesz először nulla. Ehhez elegendő figyelembe venni a rendszert:

{\begin{bmatrix}B^{-1}A&B^{-1}\end{bmatrix}}{\begin{bmatrix}x\\x_{s}\end{bmatrix}}=B^{ -1}b

A nem alapváltozók fix értékeinél a rendszer egyedileg megoldható az alapváltozók tekintetében, így meg tudjuk határozni, hogy az alapváltozók közül melyik éri el először a nullát a bemenet növekedésével. Nevezzük ezt a változót kimenetnek . Ez azt jelenti, hogy új csúcsot értünk el. Most cseréljük fel a bejövő és a kimenő változókat - a bejövő "belép" az alapba, a kimenő pedig "elhagyja" a nem alapváltozókat. Most átírjuk a B mátrixot és a c B vektort az új alap- és nem-alapváltozós halmazoknak megfelelően, majd visszatérünk a második lépéshez. x''

Mivel a csúcsok száma véges, az algoritmus egy napon véget ér. A talált csúcs lesz az optimális megoldás.

Kétfázisú szimplex módszer

A

Ha egy lineáris programozási probléma esetén nem minden kényszert reprezentál a „≤” típusú egyenlőtlenség, akkor a nulla vektor nem mindig lesz érvényes megoldás. A szimplex módszer minden iterációja azonban átmenet az egyik csúcsból a másikba, és ha nem ismert csúcs, akkor az algoritmus egyáltalán nem indítható el.

A kezdeti csúcs megtalálásának folyamata nem sokban különbözik az egyfázisú szimplex módszertől, de végül nehezebb lehet, mint a további optimalizálás.

Korlátozás módosításai

Az összes feladatmegkötés a következő szabályok szerint módosul:

A "≤" típusú korlátozások egyenlőségekké alakulnak egy további "+1" együtthatójú változó létrehozásával. Ezt a módosítást az egyfázisú szimplex módszerben is végrehajtják, további változókat használnak kiindulási alapként.
a "≥" típusú megszorításokat egy " -1 " együtthatójú változó egészíti ki . Mivel egy ilyen változó az eredeti bázisban nem használható negatív együttható miatt, szükséges még egy segédváltozó létrehozása . A segédváltozók mindig "+1" tényezővel jönnek létre.
az "=" típusú korlátozások egy segédváltozóval egészülnek ki.

Ennek megfelelően számos további és segédváltozó jön létre. Kezdetben további változókat választanak ki "+1" együtthatóval és minden segédváltozót. Figyelem: az a megoldás, amelynek ez az alap megfelel, nem elfogadható.

A kiegészítő és a segédváltozók közötti különbségek

Annak ellenére, hogy mind a kiegészítő, mind a segédváltozókat mesterségesen hozzák létre, és a kezdeti alap létrehozására használják, értékük a megoldásban nagyon eltérő:

további változók arról számolnak be, hogy mennyire "alulhasznált" a megfelelő megszorításuk. A további változó nullával egyenlő értéke megfelel a megszorítás jobb és bal oldali részének értékeinek egyenlőségének.
A segédváltozók megmondják, hogy az adott feltétel milyen messze van az elfogadhatótól (egy adott megszorításhoz képest). Ha a segédváltozó értéke nagyobb, mint nulla, akkor ez a megoldás nem tesz eleget egy bizonyos megkötésnek, ezért nem érvényes.

Ez azt jelenti, hogy a kiegészítő változó nullától eltérő értéke jelezheti (de nem szabad), hogy a megoldás nem optimális . A segédváltozó nullától eltérő értéke azt jelzi, hogy a megoldás érvénytelen .

Döntési fázisok

A feltétel módosítása után egy segédcélfüggvény jön létre . Ha a segédváltozók , ként lettek kijelölve , akkor a segédfüggvényt a következőképpen definiáljuk $y_{i}$ $i\in \left\{1,\dots ,k\right\}$

z'=\sum _{{i=1}}^{k}y_{i}\to min

Ezt követően a szokásos szimplex módszert hajtjuk végre a segédcélfüggvény tekintetében. Mivel minden segédváltozó növeli az értékét , ezért az algoritmus során egyenként levezetjük a bázisból, és minden átmenet után az új megoldás közelebb kerül a megvalósítható megoldások halmazához. $z'$

Ha megtaláljuk a segédcélfüggvény optimális értékét, két helyzet adódhat:

az optimális érték nagyobb, mint nulla. Ez azt jelenti, hogy a segédváltozók közül legalább egy a bázisban maradt. Ebben az esetben azt a következtetést vonhatjuk le, hogy erre a lineáris programozási problémára nincs megvalósítható megoldás. $z'$
az optimális érték nulla. Ez azt jelenti, hogy az összes segédváltozó kikerült a bázisból, és az aktuális megoldás érvényes. $z'$

A második esetben van egy elfogadható alapunk, vagy más szóval egy kezdeti elfogadható megoldásunk. A további optimalizálás az eredeti célfüggvény figyelembevételével is elvégezhető, a segédváltozókra figyelmen kívül hagyva. Ez a megoldás második fázisa.

Módosított szimplex metódus

A módosított módszerben a mátrix

${\begin{bmatrix}1&c_{B}^{T}B^{{-1}}Ac^{T}&c_{B}^{T}B^{{-1}}\\0&B^{{- 1}}A&B^{{-1}}\end{bmátrix}}$

nem számítják újra, csak a mátrix tárolása és újraszámítása történik . Az algoritmus többi része hasonló a fent leírtakhoz. $B^{{-1}}$

1. Számítson ki kettős változókat $d=c_{B}^{T}B^{{-1}}$

2. Optimalitás ellenőrzése. -re konvertálódik . $c_{B}^{T}B^{{-1}}Ac^{T}$ $d^{T}Ac^{T}$

Az ellenőrzés az összes oszlopra vonatkozó számításból áll . A bázisba < 0 értékű oszlop is beírható. $d^{T}A_{n}-c_{n}$ $n\-ben N$

Gyakran válassza ki a minimális értéket, de ehhez az összes oszlopot ismételnie kell.

Gyakrabban válasszon egy adott értéknél kisebb értéket $-\varepsilon$

Ha ilyen oszlop nem található, akkor a maximálisan talált abszolút értéket veszi a talált értéknek, és a megfelelő oszlop kerül be a bázisba. $\varepsilon$ $A_{J}$

3. A kimenet meghatározása.

Legyen a változónak megfelelő beviteli oszlop Az alapterv a Növelés rendszer megoldása . $A_{J}$ $x_{J}$ $A_{B}p=b$ $A_{B}p+\vartheta A_{J}=b$

Szorozd meg a bal oldalon -val , azaz . $B^{{-1}}$ $B^{{-1}}A_{B}p+\vartheta B^{{-1}}A_{J}=B^{{-1}}b$

Itt van az alapterv, a beviteli oszlop bővítése az alap szempontjából. $B^{{-1}}b$ $q=B^{{-1}}A_{J}$

Keresse meg azt a maximális értéket , amelynél az összes érték nem negatív. Ha tetszőleges nagyot lehet venni, akkor a megoldás korlátlan. Ellenkező esetben az egyik elem nullára kerül. Az alapból levezetjük a megfelelő oszlopot. $\vartheta$ $\vartheta$

4. Referencia (alap)terv újraszámítása.

Új referenciatervet számolunk a már megadott képlet alapján a talált értékkel . $x=p+\vartheta B^{{-1}}A_{J}$ $\vartheta$

5. Átszámoljuk az inverzt a bázisra . $B^{{-1}}$

Legyen a kimeneti oszlop. $B^{{-1}}A_{F}$

A B mátrixot úgy ábrázolhatjuk $[B_{G}A_{F}]$

ahol az alapmátrix a kimeneti oszlop nélkül. $B_{G}$

Az oszlop megváltoztatása után az alapmátrix így fog kinézni $[B_{G}A_{J}]$

Olyan mátrixot kell találnunk $B_1$

$[B_{G},A_{J}]B_{1}^{{-1}}=E$ => => => $[B^{{-1}}B_{G}B_{1}^{{-1}},B^{{-1}}A_{J}]=B^{{-1}}$ $[B^{{-1}}B_{G},q]B_{1}^{{-1}}=B^{{-1}}$

${\begin{bmatrix}E&q'\\0&q_{f}\end{bmatrix}}B_{1}^{{-1}}=B^{{-1}}$

Ahol $B_{1}^{{-1}}={\begin{bmatrix}E&-q'/q_{f}\\0&1/q_{f}\end{bmatrix}}B^{{-1}}$

Megjegyzés.

A mátrix újraszámítása felhalmozza a kerekítési hibákat. A nagy hibák elkerülése érdekében a mátrixot időről időre teljesen újraszámítják. Ezt a folyamatot "ismétlésnek" nevezik. $B^{{-1}}$

A szimplex metódus multiplikatív változata

A multiplikatív változatban a mátrix nem tárolódik, csak a faktorok tárolódnak $B^{{-1}}$ ${\begin{bmatrix}E&-q'/q_{f}\\0&1/q_{f}\end{bmatrix))$

A gazdasági problémák megoldása során a kényszermátrix gyakran ritka , ebben az esetben a szorzó opció további előnyökkel jár - a szorzókat tömörített formában tárolhatja (ne tároljon nullákat).

A szimplex módszer egyéb változatai

A mátrix LU dekompozíciója felhasználható a kerekítési hibák felhalmozódásának elkerülésére .

Az "egyenlőtlenség" típusú korlátozások túlnyomó számával a változó alapú módszer használható . [négy]

A módszer azon alapul, hogy a bázismátrixot úgy lehet ábrázolni, mint

${\begin{bmatrix}A_{B}&0\\A_{E}&E\end{bmatrix}}$

Az inverze megvan a formája

${\begin{bmatrix}A_{B}^{{-1}}&0\\-A_{B}^{{-1}}A_{E}&E\end{bmatrix}}$

Viszonylag kis mátrixméretek esetén előfordulhat, hogy a mátrix többi része nem tárolható. $A_{B}^{{-1}}$

Ez a megközelítés több tízmillió korlátozási sorozattal is megoldhat problémákat (például a játékelméletből).

A kettős szimplex metódus

A kettős módszer megvalósításához az együtthatók mátrixának transzponálásával a feladattól a minimumig kell eljutni a maximumig (vagy fordítva). A feladattól a minimum felé haladva a célfüggvény a következő formában jelenik meg:

$g=\sum _{{i=1}}^{n}b_{i}y_{i}\to max$

korlátozások alatt

$\sum _{i=1}^{n}a_{ij}y_{i}\leq c_{j}$ .

A dualitástétel . Ha a kettős feladatpárok közül az egyiknek van optimális terve, akkor a másiknak van megoldása, és ezen feladatok lineáris függvényeinek szélsőértékei egyenlők.

Ha az egyik feladat lineáris függvénye nem korlátozott, akkor a másiknak nincs megoldása.

Számítási hatékonyság

A szimplex módszer meglepően hatékony a gyakorlatban, de 1972-ben Klee és Minty [5] hozott egy példát, amelyben a szimplex módszer a szimplex összes csúcsán iterált, ami a legrosszabb esetben a módszer exponenciális konvergenciáját mutatja. Azóta a módszer minden változatára találtak olyan példát, amelyen a módszer rendkívül rosszul viselkedett.

A gyakorlati alkalmazásokban a módszer hatékonyságának megfigyelése és elemzése a hatékonyság mérésének más módszereinek kidolgozását eredményezte.

A szimplex módszer átlagos polinomiális konvergenciával rendelkezik, az értékek eloszlásának széles választékával a véletlen mátrixokban. [6] [7]

A számítási hatékonyságot általában két paraméter segítségével becsülik meg:

a megoldás eléréséhez szükséges iterációk száma;
gépi idő költségek.

A numerikus kísérletek eredményeként a következő eredményeket kaptuk.

Az iterációk száma a lineáris programozási feladatok szabványos formában, megszorításokkal és változókkal történő megoldásában és között van . Az iterációk átlagos száma . Az iterációk számának felső korlátja . $m$ $n$ $m$ $3m$ $2 m$ $2m+n$
A szükséges gépidő arányos . $m^{3}$

A korlátozások száma jobban befolyásolja a számítási hatékonyságot, mint a változók száma, ezért a lineáris programozási feladatok megfogalmazásakor törekedni kell a korlátozások számának csökkentésére, még ha a változók számának növelésével is.

Módszerek a hatékonyság javítására

A szimplex módszer egyik legidőigényesebb eljárása az alapba bevitt oszlop keresése. A jobb konvergencia érdekében úgy tűnik, hogy ki kell választania a legjobb reziduális változót, de ehhez teljes vizsgálatra van szükség, azaz meg kell szoroznia a kettős változók oszlopát (ezt néha árnyékáraknak is nevezik) a mátrix összes oszlopával. [8] . Ez a megközelítés jól működik kis problémák esetén, amelyeket manuálisan oldanak meg. Ezen túlmenően a maximális maradék modulusz megválasztására vonatkozó szabály szigorú betartása szuboptimálisnak bizonyulhat az extrémum megszerzéséhez szükséges iterációk teljes számát tekintve. A maximális erősítés egy iterációnál a célfüggvény értékének lassú csökkenéséhez vezethet a következő lépésekben, és ezáltal lelassítja a probléma megoldásának folyamatát [9] .

Nagy kényszermátrixok esetén a bemeneti változó keresése sok időt vesz igénybe, és gyakran megpróbálják elkerülni a mátrix összes oszlopának áttekintését, amelyhez a következő módszerek használhatók:

Gát . Amint a változó eltérése kellően eltér a nullától (meghalad egy bizonyos értéket, amelyet akadálynak nevezünk), a változó bekerül a bázisba. Ha az összes maradék kisebbnek bizonyult, mint a gát, akkor a legkisebb maradékot tartalmazó változót választjuk bemenetként, míg magát az akadályt valamilyen szabály szerint csökkentjük (például a legkisebb maradék fele). Az akadályt gyakran használják a következő technikával. Hasonló megközelítést ír le Murtaugh könyve, lásd a 3.6.2. fejezetet. A könyv részleges értékelése [10] . Ciklus nézet . A bemeneti változó keresése az előző iteráció során bevezetett változó utáni pozícióból indul. Csoportkiválasztás (Murtaugh könyvében ezt a technikát többszörös kiértékelésnek nevezik . Lásd 3.6.3. Többszörös kiértékelés [11] .) Egy bemeneti változó keresésekor nem egy változót választunk ki, hanem több jelöltet. A következő iterációknál a megtekintés csak a kiválasztott jelöltek között történik, míg a jelölt törölhető a listáról. A mérleg célja . A változókhoz súlyokat rendelnek. Lásd a 3.6.4 fejezetet: Murtafa DEVEX pontozási módszere [12] . Keresse meg Goldfarb és Reed legmeredekebb bordáját . Lásd Murtaugh könyvének [13] 3.6.5 legmeredekebb élbecslési módszere című részét .

Más trükkök is lehetségesek, például a Zadeh-szabály .

Jegyzetek

↑ Kantorovich L. V. Matematikai módszerek a termelés tervezésének megszervezéséhez // A Leningrádi Állami Egyetem kiadása. - Leningrád, 1939.
↑ S. Gass. Lineáris programozás (módszerek és alkalmazások). - Moszkva: Állami Fizikai és Matematikai Irodalmi Kiadó, 1961. - (Mérnöki Fizikai és Matematikai Könyvtár).
↑ Ez az ajánlás gyakran megtalálható a tankönyvekben, de nem mindig helyes. Lásd: #Módszerek a hatékonyság növelésére
↑ V.I. Muravjov. Szekvenciális fejlesztési módszer változó méretű alappal lineáris programozási problémákhoz. — „A statisztikai modellezés műveleteinek és módszereinek kutatása” gyűjtemény. - Leningrád: Leningrádi Állami Egyetem, 1972.
↑ Klee, Victor; Minty, George J. Mennyire jó a szimplex algoritmus? // Inequalities III (Proceedings of the Third Symposium on Equalities held at the University of California, Los Angeles, California, 1969. szeptember 1–9., Theodore S. Motzkin emlékének szentelve) (angol) / Shisha, Oved. - New York-London: Academic Press , 1972. - P. 159-175.
↑ Alexander Schrijver, A lineáris és egészszámú programozás elmélete . John Wiley és fiai, 1998, ISBN 0-471-98232-6 (matematikai)
↑ A szimplex algoritmus átlagosan D lépést tesz meg egy kocka esetében. Borgwardt, Karl-Heinz. A szimplex módszer: Valószínűségi elemzés . - Berlin: Springer-Verlag , 1987. - 20. évf. 1. - P.xii+268. - (Algoritmusok és kombinatorikák (tanulmányi és kutatási szövegek)). - ISBN 3-540-17096-0 .
↑ A maradék modulo maximális értékének megválasztására vonatkozó ajánlás gyakran megtalálható a szimplex módszer leírásaiban, például az Algoritmus szimplex módszerhez cikkekben Archivált 2018. március 17. a Wayback Machine -en és a SIMPLEX LINEÁRIS PROGRAMOZÁSI MÓDSZER Archivált 2018. március 17-én a Wayback Machine -en
↑ Shamray, 2009 , p. 44.
↑ Murtaf, 1984 .
↑ Murtaf, 1984 , p. 61.
↑ Murtaf, 1984 , p. 62.
↑ Murtaf, 1984 , p. 63.

Irodalom

Hemdy A. Taha. 3. fejezet A szimplex módszer // Bevezetés az operációkutatásba = Operations Research: An Introduction. - 7. kiadás - M . : "Williams" , 2007. - S. 95-141. — ISBN 0-13-032374-8 .
Akulich I.L. 1. fejezet Lineáris programozás problémái // Matematikai programozás példákban és feladatokban. - M . : Felsőiskola , 1986. - 319 p. — ISBN 5-06-002663-9 .
Thomas H. Kormen et al. , 29. fejezet Lineáris programozás // Algoritmusok: Konstrukció és elemzés = BEVEZETÉS AZ ALGORITMUSOKBA. - 2. kiadás - M .: "Williams" , 2006. - S. 1296. - ISBN 5-8459-0857-4 .
V. N. Sevcsenko, N. Yu. Zolotyk. Lineáris és egész számú Lineáris programozás . - Nyizsnyij Novgorod: A Nyizsnyij Novgorodi Állami Egyetem kiadója. N.I. Lobachevsky, 2004. - P. 63 -66 (2.8. szakasz Megjegyzések az LLP megoldásának összetettségéhez). — ISBN 5-85746-761-6 .
Shamray Natalya Borisovna. Gyakorlati lineáris programozás közgazdászok számára . - Vlagyivosztok: Távol-keleti Egyetem Kiadója, 2009. - P. 44. - ISBN 978-5-7444-2215-8 . Archiválva : 2018. március 17. a Wayback Machine -nál
Murtaf B. Modern lineáris programozás. - Moszkva: Mir, 1984.

Linkek

Szótárak és enciklopédiák	Britannica (online)
Bibliográfiai katalógusokban	GND : 4181488-5 J9U : 987007546249105171 LCCN : sh85122745

Optimalizálási módszerek
Egydimenziós	aranymetszet módszer Kettősség Parabola módszer Rács keresés Egységes blokkkeresési módszer Fibonacci módszer Háromszoros keresés Piyavsky módszer Strongin módszer
Nulla sorrend	Gauss módszer Nelder-Mead módszer Hook-Jeeves módszer Rosenbrock módszer Powell-módszer
Első rendelés	gradiens süllyedés Zeutendijk módszer Koordináta süllyedés Konjugált gradiens módszer Kvázi-Newtoni módszerek Levenberg-Marquardt algoritmus
másodrendű	Newton módszere Newton-Raphson módszer Broyden-Fletcher-Goldfarb-Shanno algoritmus (BFGS)
Sztochasztikus	Monte Carlo módszer Szimulált lágyítás Evolúciós algoritmusok differenciális evolúció Hangya algoritmus Részecskeraj módszer Méhtelep algoritmus Véletlenszerű séta módszer
Lineáris programozási módszerek	Simplex módszer Gomori algoritmusa Ellipszoid módszer Potenciális módszer
Nemlineáris programozási módszerek	Szekvenciális kvadratikus programozás