Optimalizálás (matematika)

Az optimalizálás a matematika olyan ága, amely megpróbálja modellezni, elemezni és analitikusan vagy numerikusan megoldani azokat a problémákat, amelyek minimalizálják vagy maximalizálják a halmaz függvényét.

Optimization fontos szerepet játszik az operációkutatás (a mező határán számítástechnika , matematika és közgazdaságtan ), a alkalmazott matematika (alapvető ipar és mérnöki ), elemzés és numerikus analízis. , A statisztikák becslésére a maximum likelihood of a forgalmazás , a keresést stratégiák keretében játékelmélet , vagy ellenőrző és irányító elmélet .

Számos matematikai modell által leírható rendszer optimalizált. Az eredmények és az előrejelzések minősége a modell relevanciájától, az optimalizálni kívánt változók helyes megválasztásától, az algoritmus hatékonyságától és a digitális feldolgozás eszközeitől függ .

Előzmények és név

antikvitás

Az első optimalizálási problémákat fogalmazott meg Euclid , a III -én században, az ő történelmi munka tételeket . Háromszáz évvel később a catoptricai alexandriai Heron az optika összefüggésében mondja ki a "legrövidebb út elvét" (lásd az ábrát).

Differenciálszámítás bevezetése

A XVII . Században a kalkulus megjelenése optimalizálási technikák feltalálásához vezet, vagy legalábbis szükségét kelti. Newton fejleszt iteratív eljárás , amely lehetővé teszi, hogy megtalálja a helyi szélsőséges egy funkciót azáltal játékba fogalmának származék , ami az ő munkáját Leibniz . Ez az új elképzelés nagy előrelépést tesz lehetővé a funkciók optimalizálásában, mert a probléma a származék gyökereinek keresésére szorítkozik.

A XVIII -én században, a munka a matematikusok Euler és Lagrange vezet a variációszámítás egy ága, funkcionális elemzés, amely több optimalizálási módszerek. Ez utóbbi korlátok alatt feltalál egy optimalizálási technikát: a Lagrange-szorzókat .

Fejlesztések, alkalmazások és név

A XIX . Századot a közgazdászok növekvő érdeklődése jellemezte a matematika iránt. Olyan gazdasági modelleket hoznak létre , amelyeket optimalizálni kell, ami felgyorsítja a matematika fejlődését. Ebből az időszakból az optimalizálás az alkalmazott matematika oszlopává vált, és a technikák bősége olyan, hogy nem lehet összefoglalni néhány sorban.

Egy mind ugyanazt idézik a találmány több iteratív módszer alkalmazásával a gradiens a funkciót , valamint a használata a „matematikai programozás”, hogy kijelölje optimalizálási problémák.

Történelmileg az első bevezetett kifejezés a "lineáris programozás" volt, amelyet George Dantzig talált ki 1947 körül. A "programozás" kifejezés ebben az összefüggésben nem a számítógépes programozásra vonatkozik (bár a számítógépeket manapság széles körben használják a problémák megoldására. Matematikai programok). Ez abból ered, hogy az amerikai fegyveres erők a "program" szót használták a kiképzési ütemtervek és logisztikai döntések megalkotására , amelyet Danzig annak idején tanulmányozott. A "programozás" kifejezés használata szintén érdekes volt a pénzeszközök felszabadításához abban az időben, amikor a tervezés a kormányok számára prioritássá vált .

Így 1939-től Leonid Kantorovich matematikus megkezdte a lineáris optimalizálás elméleti munkáját annak érdekében, hogy konkrét alkalmazásokat vonzzon a Szovjetunió tervezett gazdasági termelésének optimalizálására .

A "matematikai programozás" kifejezés, amely a fenti hosszú magyarázatot igényli, hajlamos elhagyni. Például 2010 júniusában az ezt a tudományterületet képviselő nemzetközi tudós társadalom korábbi nevét a Matematikai Programozó Társaság Matematikai Optimalizálási Társaságra változtatta ; ugyanezen okból ma inkább a „lineáris / kvadratikus /… optimalizálás” kifejezéseket használjuk a „lineáris / kvadratikus /… programozás” helyett.

Definíciók

Minimalizálás

Formálisabban az optimalizálás a problémák tanulmányozása, amelyek az alábbiak szerint fejeződnek ki.

Optimalizálási probléma - Adott egy függvény meghatározása egy sor értékek a beállított a valós számok (esetleg a befejezett vonal ), meg egy elem az , hogy az összes itt . $f: A \ rightarrow \ mathbb {R}$ $NÁL NÉL$ $\ mathbb {R}$ ${\ displaystyle {\ overline {\ mathbb {R}}}: = \ mathbb {R} \ cup \ {- \ infty, + \ infty \}}$ ${\ bar x}$ $NÁL NÉL$ ${\ displaystyle f ({\ bar {x}}) \ leqslant f (x)}$ $x$ $NÁL NÉL$

Azt mondjuk, hogy a függvény minimalizálására törekszünk a halmaz felett . $f$ $NÁL NÉL$

A függvénynek több neve van: költség-függvény vagy egyszerűen költség , cél-függvény vagy egyszerűen objektív , kritérium stb. $f$

A készlet az úgynevezett elfogadhatónak beállított és pontok nevezzük elfogadható pontok a probléma (különösen, ha ez egy része egy másik , és nem akarjuk, hogy tartozik a komplementer ). Azt mondjuk, hogy a probléma akkor valósítható meg, ha nem üres (az elfogadható halmazt gyakran implicit módon definiálják, nem üres jellege nem feltétlenül nyilvánvaló, ami indokolja a megvalósíthatóság ezen koncepciójának szükségességét). $NÁL NÉL$ $NÁL NÉL$ $B$ ${\ bar x}$ $B \ setminus A$ $NÁL NÉL$

A pontot az optimalizálási probléma (vagy minimum vagy minimalizáló ) megoldásának nevezzük . Néha globális megoldásnak is nevezik, hogy megkülönböztesse az alábbiakban bemutatott helyi fogalmaktól. Azt mondják, hogy egy csupasz minimum , ha és mindent . ${\ bar x}$ ${\ displaystyle {\ bar {x}} \ in A}$ ${\ displaystyle f ({\ bar {x}}) <f (x)}$ ${\ displaystyle x \ in A \ setminus \ {{\ bar {x}} \}}$

Különböző módon írhatjuk ezt a problémát:

${\ displaystyle \ inf _ {x \ in A} \, f (x) \ quad {\ mbox {vagy}} \ quad \ inf {\ {f (x) \ x x közepe A-ban \}} \ quad { \ mbox {vagy}} \ quad \ inf {f (A)} \ quad {\ mbox {vagy}} \ quad \ left \ {{\ begin {tömb} {l} \ inf {f (x)} \\ x \ A.-ban \ end {tömb}} \ jobb.}$

Néha megjegyezzük a probléma összes megoldását. ${\ displaystyle \ kezelőnév {arg \, min} \, \ {f (x) \ x közepe \ -ban A \}}$

A halmaz a (vagy ha értéke van ) része, és alsó határát (vagy infimumát) a probléma optimális értékének nevezzük . Ez az optimális érték akkor érhető el (vagyis van olyan , amelyik ), és csak akkor, ha az optimalizálási problémának van megoldása. Igen , azt mondjuk, hogy a probléma korlátozott . ${\ displaystyle f (A): = \ {f (x) \ x x közepe A-ban \}}$ $\ mathbb {R}$ ${\ displaystyle {\ overline {\ mathbb {R}}}}$ $f$ ${\ displaystyle {\ overline {\ mathbb {R}}}}$ ${\ displaystyle \ inf {f (A)}}$ ${\ displaystyle {\ bar {x}} \ in A}$ ${\ displaystyle f ({\ bar {x}}) = \ inf \, f (A)}$ ${\ displaystyle \ inf {f (A)}> - \ infty}$

Azt mondjuk, hogy a probléma az, konvex , ha egy konvex része egy vektortér, és ha egy konvex függvény a . ${\ displaystyle \ inf {\ {f (x) \ x közepe \ -ban A \}}}$ $NÁL NÉL$ $f$ $NÁL NÉL$

Maximalizálás

A fent leírt probléma minimalizálási probléma . Ahogy van

${\ displaystyle \ sup _ {x \ in A} {f (x)} = - \ inf _ {x \ in A} \ bal (-f (x) \ right),}$

Egy függvény maximalizálási probléma (balra fent) egyenértékű a minimalizálási problémáját (jobbra fent). Az ekvivalencia itt azt jelenti, hogy a megoldások azonosak és az optimális értékek ellentétesek. Különösen egy minimalizálási probléma elemzésére / megoldására szolgáló módszert lehetne használni egy maximalizálási probléma elemzésére / megoldására. $f$ $-f$

Helyi megoldás

Bizonyos körülmények között az optimalizálási folyamat megtalálja a teljes maximumot. De az optimalizálás egyes eseteiben - mint a mesterséges ideghálózatok - az eredmény helyi megoldás lehet.

A lokális maximum egy pont olyan, hogy létezik egy környéken , ahol minden , . A helyi minimum hasonlóan van meghatározva. $nál nél$ $NÁL NÉL$ $V$ $x \ V-ben$ ${\ displaystyle f (x) \ leqslant f (a)}$

A helyi maximumokat általában könnyű numerikusan meghatározni süllyedési algoritmusokkal - például a gradiens algoritmussal . Annak igazolására, hogy a megtalált megoldás globális maximum , néha lehetséges további ismeretekhez folyamodni a problémával kapcsolatban. A függvény jellegétől vagy függvényétől függően a különböző tételek a megoldás bizonyos tulajdonságait biztosítják, amelyek egyszerűsítik a keresést (lásd a maximális elvet ). $NÁL NÉL$ $f$

Kombinatorikus optimalizálás

Leggyakrabban egy részhalmaza az euklideszi térben . Amikor egy részhalmaza vagy álló vektorok megfelelő bizonyos számú korlátok (az egyenlőség vagy egyenlőtlenség típus), beszélünk a kombinatorikus optimalizálás . $NÁL NÉL$ $\ mathbb {R} ^ {n}$ $NÁL NÉL$ ${\ displaystyle \ mathbb {N} ^ {n}}$ ${\ displaystyle \ mathbb {N} ^ {p} \ times \ mathbb {R} ^ {q}}$

Néhány problémaosztály

Az optimalizálás egymást átfedő részdiszciplinákra oszlik, a célfüggvény és a korlátok formája szerint : optimalizálás véges vagy végtelen dimenzióban (itt az optimalizálandó változók vektorterének dimenziójáról beszélünk) , folyamatos vagy kombinatorikus optimalizálás (utóbbi esetben az optimalizálandó változók diszkrétek), differenciálható vagy nem sima optimalizálás (itt a problémát meghatározó függvények szabályszerűségét minősítjük), lineáris optimalizálás (affin függvények), másodfokú (másodfokú cél és affin korlátok), pozitív félig határozott (a variábilis kell optimalizálni egy olyan mátrix, amelyhez a félig határozott pozitivitás szükséges ), copositive (változó kell optimalizálni egy olyan mátrix, amelyhez a CO -positivity szükséges ), kúpos (korábbi diszciplínák általánosítása, amelyben minimalizálunk egy lineáris függvényt egy kúp és egy affin altér metszéspontján), konvex ( konvex függvények ), nemlineáris , a parancs optimális e , sztochasztikus (en) és robusztus optimalizálás (veszélyek jelenléte), több kritérium optimalizálás (kompromisszumra törekszik több ellentmondásos cél között), algebrai optimalizálás (polinomfüggvények), kétszintű optimalizálás , a komplementaritás korlátai alatt történő optimalizálás , a diszjunktív optimalizálás (az elfogadható halmaz halmazok találkozása ) stb.

A tudományterületek ilyen sokasága abból a tényből fakad, hogy a modellezhető problémák gyakorlatilag bármely osztálya vezethet optimalizálási problémához, feltéve, hogy bevezetjük az optimalizálandó paramétereket. Ezenfelül ezeknek az optimalizálási problémáknak az optimális feltételei olykor eredeti matematikai kifejezéseket adnak, amelyek az előző mechanizmus révén viszont új optimalizálási problémákhoz vezetnek.

A lineáris optimalizálási vizsgálatok az eset, amelyben a célfüggvény és korlátok jellemző minden olyan lineáris . Ez egy olyan módszer, amelyet széles körben használnak az olajfinomító programok létrehozására, de a sós keverék jövedelmezőbb összetételének korlátozás alapján történő meghatározására is a jelenlegi piaci árak alapján. $NÁL NÉL$
Az egész programozás azokat a lineáris optimalizálási problémákat vizsgálja, amelyekben néhány vagy az összes változót egész számok befogadására kényszerítik. Ezeket a problémákat különféle módszerekkel lehet megoldani: szétválasztással és értékeléssel , szekundáns síkok módszerével .
A másodfokú optimalizálás azt az esetet vizsgálja, amikor a célfüggvény kvadratikus forma (lineáris korlátozásokkal ) $NÁL NÉL$
A nemlineáris optimalizálás, figyelembe véve az általános esetet, ahol a lencse vagy a kényszerek (vagy mindkettő) nem lineáris részeket, esetleg nem domború részeket tartalmaznak.
A sztochasztikus optimalizálás (in) azt az esetet tanulmányozza, amelyben a korlátozások egy része véletlenszerű változóktól függ . A robusztus optimalizálás során feltételezzük, hogy a veszélyek a névleges pozíciók körüli időközönként helyezkednek el, és a legrosszabb esetben az ilyen veszélyeknek kitett rendszer optimalizálására törekszünk.
A dinamikus programozás azt a tulajdonságot használja, hogy egy megoldás szükségszerűen nem optimális megoldásokból áll (megjegyzés: az ellenkezője általában nem igaz) a probléma lebontásához a kombinatorikus robbanás elkerülésével . Akkor használható, ha a célfüggvény növekvő monoton függvények összege, amelyek érvei különálló ismeretlenek. A dinamikus programozás lehetővé teszi például:
- repülőgépgyártók, hogy megtalálják gépeik optimális felszállási terveit,
- medencemérnökök a bányászati termelés szétosztására a különböző kutak között,
- villamosenergia-termelők tervezzék meg a vízerőművek működését,
- a médiatervezőknek, hogy hatékonyan osszanak szét hirdetési költségvetést a különböző médiumok között.

Numerikus módszerek

A matematikai optimalizálási probléma megoldásának technikája itt jelöli

az eredeti probléma átalakítása egyenértékű problémává,
elméleti módszer, amelynek leírása lehetővé teszi egy numerikusan alkalmazható algoritmus kifejlesztését .

A megfelelő technika megválasztása attól függ

a célfüggvény jellege , annak szabályszerűsége ( folytonosság , levezethetőség ), specifikus tulajdonságok ( paritás , konvexitás ), extrém szomszédságainak ismerete, $f$
az elfogadható pontok halmazát jellemző korlátok . $NÁL NÉL$

Egyszerűsítések

Az optimalizálás megoldásának megtalálásához az eredeti problémát egy ekvivalens probléma váltja fel. Például meg lehet változtatni azokat a változókat, amelyek lehetővé teszik a probléma részproblémákra bontását vagy ismeretlenek helyettesítését, lehetővé téve számuk csökkentését.

A Lagrange-szorzó technikája lehetővé teszi bizonyos korlátok leküzdését; ez a módszer növekvő büntetések bevezetésével jár, amikor a pont közelít a korlátokhoz. A Hugh Everett miatti algoritmus lehetővé teszi a szorzók értékeinek következetes frissítését az egyes iterációknál a konvergencia biztosítása érdekében. Ezeknek a szorzóknak az értelmezését is általánosította, hogy azokat olyan funkciókra alkalmazza, amelyek nem folyamatosak és nem is levezethetők. A lambda büntetési együtthatót fejez ki ( a közgazdaságtani kényszer határköltségének fogalma ).

Gradiens nullák keresése

Számos módszer és algoritmus lehetővé teszi, hogy nullát találjunk a derivált (némelyik a változó funkcióira jellemző) származékából vagy annak gradienséből . Érvényesen alkalmazandók olyan helyzetekben, amikor a korlátozások nem túl aktívak. $f$ $\ mathbf {\ nabla} f$ $NÁL NÉL$

Mindezeket a módszereket egy iteratív folyamat keretein belül fejlesztjük ki .

Ezek a megközelítések néhány hibában szenvedhetnek:

A függvénynek elég szabályosnak kell lennie (legalább lokálisan) ahhoz, hogy megkülönböztethető legyen (vagy akár kétszer is megkülönböztethető legyen, hogy hozzáférjen a Hessian-mátrixhoz vagy annak közelítéséhez).
Nem mindig lehet kifejezetten kifejezni a célfüggvény gradiensét.
Az iterációs folyamat megkezdése előtt meg kell határozni a kezdési feltételeket. A kezdeti választás jelentősen befolyásolhatja az eredményt (az iterációs folyamat divergenciája). A gyorsan konvergáló módszerek általában érzékenyebbek ebből a szempontból.
Bizonyos esetekben a konvergencia sebessége katasztrofális lehet: az egymást követő iterációk fáradságosan (stagnálva) járnak egy keskeny völgy mentén ( Rosenbrock-függvény ).
Ha a kapott megoldás valóban extrém (miután ellenőriztük, hogy ez nem nyeregpont ), akkor ez lokálisnak bizonyulhat.

Különleges eset: Mikor van a 2. fokú polinom az érveiben ( kvadratikus és lineáris forma ) és korlátozás nélkül, a gradiens összegének törlése egy lineáris rendszer megoldásához (vö. Kategória: Mátrix numerikus elemzés ). $f$

Közvetlen analitikai módszerek

Ebben a kategóriában az általános algoritmusok többsége olyan helyzetekre vonatkozik, ahol a korlátozások nem túl aktívak. Néhány domináns ötleten alapulnak: $NÁL NÉL$

Mozgások egy gradiens által hordozott vonalon.
Közelítés egy egyszerűbb függvénnyel (például a 2. rend Taylor-bővítése ), amelyet az iterációk során frissítettek. $f$

Különféle fejlesztések történtek az alábbiak elkerülése érdekében:

stagnálások (pl. konjugált gradiens módszer nemlineáris optimalizálásban (in) )
a Hessian-mátrix kifejezett vagy túl gyakori kiszámítása (például BFGS )

Itt is előfordulhatnak ugyanazok a hibák, mint az előző kategóriában.

A Kategória: Optimalizálás algoritmus felsorol egy listát, és hozzáférést biztosít ezekhez a módszerekhez.

Kombinatorikus optimalizálási technikák

A kombinatorikus optimalizálási technikák olyan problémákkal foglalkoznak, amikor a halmaz változóinak egy része (legalábbis) diszkrét értékeket vesz fel . Keretein belül találkozunk velük $NÁL NÉL$

a gráfelmélet (az út optimális, amelynek utazó eladó problémája van )
A játékelmélet ( stratégia teljesítmény)
a vezérlés , a szabályozás és az automata elmélete (vö. Kategória: Automatikus )
a multidiszciplináris optimalizálás

Heurisztika és metaheurisztika

A nehéz problémák megoldására (pl. Azoknak, akiknek sok a gyenge a helyi szélsőségük) technikákat dolgoztak ki, amelyek meghatározzák azokat a pontokat, amelyek nem szigorúan optimálisak, de megközelítik azokat. Ezek a heurisztikának és metaheurisztikának nevezett módszerek általában fizikai, biológiai, szociálpszichológiai jelenségeken alapulnak vagy véletlenszerűségen alapulnak. Az alkalmazási területek hatalmasak, és gyakran messze túlmutatnak azon problémákon, amelyekre eredetileg tervezték.

a szimulált izzítás
a Nelder-Mead módszer szimulált hőkezeléssel
a hangyakolóniák algoritmusai
a genetikai algoritmusok
az evolúciós algoritmusok
részecske raj optimalizálási módszerek

A Category: Metaheuristic felsorol egy listát, és hozzáférést biztosít ezekhez a módszerekhez.

Multiobjektív optimalizálási technikák

A multiobjektív optimalizálás problémái túlmutatnak a fenti definíció szigorú keretein: egy megengedhető pontig az objektív függvény nem numerikus értéket, hanem egy halmaz egy pontját társítja, amely leggyakrabban egy vektorhoz fog társulni. A cél ekkor a vektor összes komponensének egyidejű optimalizálása. A multiobjektív optimalizálást úgy is tekinthetjük, mint ugyanazon paraméterektől függő optimalizálási problémák összességét, amelyeknek ellentmondásos céljai vannak, és melyiket igyekszik a lehető legjobban megoldani.

Általánosságban elmondható, hogy az a megoldás, amelyben az oldatvektor kifejeződik, részleges sorrendben van, amely dominancia kritériumokat tartalmaz (például a Pareto határhoz viszonyítva ). Az állásfoglalás egy elfogadható pont megtalálásából áll, amelynek célkitűzését nem uralja más.

Alkalmazási területek

Rendkívül változatosak: az útvonal optimalizálása , a tárgy alakja , az eladási ár , a vegyi reakció , a légiforgalmi irányítás , az eszköz hatékonysága , a motor működése , a vasútvonalak kezelése, a gazdasági választás beruházások, hajóépítés stb. E rendszerek optimalizálása lehetővé teszi az ideális konfiguráció megtalálását, az erőfeszítések, idő, pénz, energia, nyersanyag vagy akár elégedettség megtakarítását.

A nem formálható szilárd anyagok dinamikájának problémái (különösen az artikulált merev testek dinamikája) gyakran matematikai optimalizálási technikákat igényelnek, mivel a merev testek dinamikáját úgy tekinthetjük meg, mint egy megszokott differenciálegyenlet megoldását egy korlátozott sokaságon; a kényszerek különféle nemlineáris geometriai kényszerek, például "ennek a két pontnak mindig egybe kell esnie", vagy "ennek a pontnak mindig ezen a görbén kell lennie". Az érintkezési erők kiszámításának problémája kiegészülhet egy lineáris komplementaritási probléma megoldásával , amely másodfokú optimalizálási problémának is tekinthető.

Számos tervezési probléma optimalizálási problémaként is kifejezhető. Ezt az alkalmazást alakoptimalizálásnak hívják. Ennek a területnek egy újabb és egyre növekvő részhalmazát hívják Multidiszciplináris optimalizálásnak, amely bár számos probléma esetén hasznos, de különösen a mérnöki és az űrtechnikai problémákra alkalmazható .

Az optimalizálási technikákat alkalmazó másik terület az operációkutatás .

Az optimalizálás a mikroökonómia egyik központi eszköze, amely a racionalitás és a viselkedés optimalizálásának, a vállalatok profitjának és a fogyasztók hasznosságának az elvén alapul .

A mechanikában az optimalizálásnak három formája van:

méretoptimalizálás vagy parametrikus optimalizálás , amely a mechanikai szerkezet méretének (hossza, vastagsága, átmérője stb.) optimalizálásából áll;
az alakoptimalizálás , amelynek célja egy helyiség burkolatának optimalizálása a topológia megváltoztatása nélkül, vagyis a munkadarabban lévő lyukak hozzáadása nélkül;
a topológia optimalizálása , amely magában foglalja az anyageloszlás változtatását egy adott kiindulási térfogaton belül.

Ez a néhány példa nem teljes körű felsorolást jelent a készítmények változatosságáról, és előrevetíti a problémák megoldására alkalmas matematikai eszközök sokféleségét.

Megjegyzések és hivatkozások

(fr) Ez a cikk részben vagy teljes egészében kivett angol Wikipedia cikket „ Optimization (matematika) ” ( lásd a szerzők listáját ) .

Sebastian Xhonneux, „A matematika és a közgazdaságtan optimalizálásának észlelése az évszázadok során és Lagrange-tétel tanítása ” , az APMEP-en ,2008. október 27(megtekintés : 2010. március 15. ) .
Lásd a " Newton-módszer " című cikket .
(in) GB Danzig, "Lineáris egyenlőtlenségeknek kitett változók lineáris függvényének maximalizálása" a Tj. C. Koopmans, A termelés és az allokáció tevékenységelemzése , New York, Wiley,1951, P. 339-347.
(in) " Mathematical Optimization Society (MOS) " a mathopt.org oldalon .
M. Gori és A. Tesi , „ A lokális minimumok problémájáról a szaporításban ”, IEEE Transaction on Pattern Analysis and Machine Intelligence , vol. 14, n o 1,1992, P. 76–86 ( ISSN 0162-8828 , DOI 10.1109 / 34.107014 , online olvasás , hozzáférés: 2019. augusztus 21. )
Catherine Vayssade, " Mechanikai optimalizálás, topológiai optimalizálás " ,2004(megtekintés : 2008. december 24. ) .

Lásd is

Kapcsolódó cikkek

Általános munkák

(en) JF Bonnans, J. Ch. Gilbert, C. Lemaréchal és C. Sagastizábal, Numerikus optimalizálás - elméleti és numerikus szempontok [ a kiadások részlete ]
(en) JF Bonnans és A. Shapiro, Az optimalizálási problémák Perturbation analysis , Springer, 2000 ( ISBN 978-0-387-98705-7 )
(in) Christodoulos A. Floudas Pardalos és Panos M. (szerk) Encyclopedia of Optimization , 2 th Edition 2009 ( ISBN 978-0-387-74758-3 )
Michel Minoux, Matematikai programozás - elmélet és algoritmusok , Dunod kiadások, 1983 ( ISBN 2040154876 )

Külső linkek

" A folyó " [PDF] , az ÉducMath- on : a folyó mellett elhaladó két ház közötti legrövidebb út problémája
(en) NEOS útmutató
en) „ Matematikai programozási szószedet ”