Lineáris programozás

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. május 5-én felülvizsgált verziótól ; az ellenőrzések 5 szerkesztést igényelnek .

A lineáris programozás egy matematikai tudományág, amely a lineáris egyenlet- és egyenlőtlenségrendszerek által meghatározott -dimenziós vektorterek halmazain történő extremális problémák megoldásának elméletével és módszereivel foglalkozik. $n$

A lineáris programozás (LP) a konvex programozás speciális esete , amely viszont a matematikai programozás speciális esete . Ugyanakkor számos egész és nemlineáris programozási probléma megoldási módszerének az alapja . A lineáris programozás egyik általánosítása a tört lineáris programozás .

A lineáris programozási feladatok számos tulajdonsága poliéderek tulajdonságaiként is értelmezhető, így geometriailag is megfogalmazható és igazolható.

Történelem

Az egyes gazdasági problémák matematikai vizsgálata, a numerikus anyagok matematikai formalizálása már a XIX . A kiterjesztett termelési folyamat matematikai elemzése során algebrai összefüggéseket használtam, ezek elemzését differenciálszámítással végeztem el . Ez lehetővé tette, hogy általános képet kapjunk a problémáról.

A gazdaság fejlődése megkövetelte a mennyiségi mutatókat, az 1920 -as években létrejött az ágazatközi egyensúly ( IOB ). Ő volt az, aki lendületet adott a matematikai modellek létrehozásának és tanulmányozásának. A MOB fejlődése 1924-1925 között a Szovjetunióban befolyásolta Vaszilij Vasziljevics Leontyev közgazdász és statisztikus munkáját . Kidolgozta a termékek előállításának és elosztásának ágazatközi modelljét.

1938- ban Leonyid Vitalievich Kantorovich tudományos konzultáció során elkezdte tanulmányozni azt a tisztán gyakorlati feladatot, hogy kidolgozza a legjobb tervet a hámozógépek betöltésére (rétegelt lemez bizalom). Ez a feladat nem volt alkalmas a hagyományos módszerekre. Világossá vált, hogy a feladat nem véletlen. [egy]

1939 -ben Leonyid Kantorovich kiadta "A termelés szervezésének és tervezésének matematikai módszerei" című munkáját, amelyben az extrém problémák új osztályát fogalmazta meg korlátozásokkal, és hatékony módszert dolgozott ki ezek megoldására, lefektetve ezzel a lineáris programozás alapjait.

Az ilyen problémák tanulmányozása a lineáris programozás új tudományágának létrehozásához vezetett, és új szakaszt nyitott a gazdasági és matematikai módszerek fejlődésében.

1949- ben George Bernard Dantzig amerikai matematikus kifejlesztett egy hatékony módszert a lineáris programozási problémák (LPP) megoldására - a szimplex módszert . [egy]

A "programozás" kifejezést a "tervezés" értelmében kell érteni (az angol programozás egyik fordítása ). Az 1940-es évek közepén javasolta George Danzig, a lineáris programozás egyik megalapítója, mielőtt a számítógépeket lineáris optimalizálási problémák megoldására használták volna .

A belső pont módszerét először I. I. Dikin említette 1967 -ben . [2] . Ezeket a vizsgálatokat folytatták, köztük hazai tudósok is. Az 1970-es években V. G. Zhadannak sikerült megszereznie a fő eredményeket, és általános megközelítést kidolgoznia a belső pontmódszerek felépítéséhez a lineáris és nemlineáris programozás problémáinak megoldására, a terek transzformációján alapulva; akadály-projektív és barrier-newtoni numerikus módszereket javasol.

Feladatok

A lineáris programozás általános (standard) problémája a [3] alakú lineáris célfüggvény (lineáris alak) minimumának megtalálásának problémája:

f(x)=\sum _{j=1}^{n}c_{j}x_{j}=c_{1}x_{1}+c_{2}x_{2}+\ldots + c_{n}x_{n}.

Egy olyan problémát, amelyben egyenlőtlenségek formájában jelennek meg megszorítások, alapvető lineáris programozási problémának (BLP) nevezzük.

\sum _{j=1}^{n}a_{ij}x_{j}\geqslant b_{i},\quad (i=1,\;2,\;\ldots ,\;m)

x_{j}\geqslant 0.\quad (j=1,\;2,\;\ldots ,\;n)

A lineáris programozás problémája akkor lesz kanonikus formája , ha a fő problémában az első egyenlőtlenségrendszer helyett egy egyenletrendszer van megszorításokkal egyenlőség formájában [4] :

\sum _{j=1}^{n}a_{ij}x_{j}=b_{i}.\quad (i=1,\;2,\;\ldots ,\;m)

A fő probléma kanonikusra redukálható további változók bevezetésével.

A legáltalánosabb formájú lineáris programozási problémák (problémák vegyes megszorításokkal: egyenlőségek és egyenlőtlenségek, kötöttségektől mentes változók jelenléte) ekvivalens (azonos megoldási halmazzal rendelkező) változókra redukálhatók, és az egyenlőségeket egy párral helyettesítjük. egyenlőtlenségek [5] .

Könnyen belátható, hogy a maximum megtalálásának problémája felváltható a minimum megtalálásának problémájával, ha az együtthatókat ellenkező előjellel vesszük. $c$

Problémapéldák

Maximális egyezés

Tekintsük a maximális illesztési problémát egy kétoldalú gráfban : több fiú és lány létezik, és minden fiú és lány esetében ismert, hogy szeretik-e egymást. A lehető legtöbb házaspárt kölcsönös rokonszenvvel kell összeházasítani.

Vezessünk be olyan változókat , amelyek megfelelnek a -edik fiú és -edik lány párjának, és eleget tesznek a korlátozásoknak: $x_{ij}$ $én$ $j$

0\leqslant x_{{ij}}\leqslant 1,

x_{1j}+x_{2j}+\ldots +x_{nj}\leqslant 1,

x_{{i1}}+x_{{i2}}+\ldots +x_{{im}}\leqslant 1,

célfüggvénnyel , ahol 1 vagy 0, attól függően, hogy a -edik fiú és -edik lány kedvesek-e egymással. Megmutatható, hogy ennek a feladatnak az optimális megoldásai között van egy egész megoldás. Az 1-gyel egyenlő változók azoknak a pároknak felelnek meg, akiknek össze kell házasodniuk. ${\displaystyle f=c_{11}x_{11}+c_{12}x_{12}+\ldots +c_{nm}x_{nm))$ $c_{ij}$ $én$ $j$

Maximális áramlás

Legyen egy gráf (irányított élekkel), amelyben minden élre a kapacitása van megadva. És két csúcs adott: egy nyelő és egy forrás. Minden élnél meg kell határozni, hogy mennyi folyadék áramlik át rajta (legfeljebb a kapacitása), hogy maximalizáljuk a teljes áramlást a forrástól a nyelőig (a folyadék nem jelenhet meg vagy tűnhet el minden csúcson, kivéve a forrást és a nyelőt).

Vegyük változónak a th élen átáramló folyadék mennyiségét . Akkor $x_{i}$ $én$

0\leqslant x_{i}\leqslant c_{i},

hol van a th él kapacitása. Ezeket az egyenlőtlenségeket ki kell egészíteni a bejövő és kimenő folyadék mennyiségének egyenlőségével minden csúcsra, kivéve a nyelőt és a forrást. Függvényként természetes, hogy a forrásnál kifolyó és beáramló folyadék mennyisége közötti különbséget vesszük. $c_{i}$ $én$ $f$

Az előző probléma általánosítása a minimális költség maximális áramlása. Ebben a feladatban az egyes élek költségei adottak, és a maximális áramlások közül kell kiválasztani a minimális költségű áramlást. Ez a feladat két lineáris programozási feladatra redukálódik: először meg kell oldani a maximális áramlás problémáját, majd hozzá kell adni ehhez a problémához a megszorítást , ahol a maximális áramlás értéke, és megoldani a problémát egy új függvénnyel - az áramlás költsége. $f(x)\geqslant m$ $m$ $f(x)$

Ezek a problémák gyorsabban megoldhatók, mint a lineáris programozási feladatok általános megoldására szolgáló algoritmusok, az egyenletek és egyenlőtlenségek speciális szerkezete miatt.

Szállítási probléma

Van egy bizonyos homogén rakomány, amelyet a raktárakból a gyárakba kell szállítani . Minden raktárról ismert, hogy mennyi rakomány van benne , és minden egyes üzem esetében ismert a rakományigénye. A szállítás költsége arányos a raktár és az üzem távolságával (a -edik raktártól a -edik üzemig minden távolság ismert). A legolcsóbb szállítási tervet kell elkészíteni. $n$ $m$ $én$ $a_{i}$ $b_{j}$ $c_{ij}$ $én$ $j$

A döntő változók ebben az esetben - a -edik raktárból a -edik üzembe szállított rakomány mennyisége . Megfelelnek a korlátozásoknak: $x_{ij}$ $én$ $j$

x_{{i1}}+x_{{i2}}+\ldots +x_{{im}}\leqslant a_{i},

x_{{1j}}+x_{{2j}}+\ldots +x_{{nj}}\geqslant b_{j}.

A célfüggvény alakja: , amelyet minimalizálni kell. $f(x)=x_{{11}}c_{{11}}+x_{{12}}c_{{12}}+\ldots +x_{{nm}}c_{{nm}}$

Nulla összegű játék

Van egy méretmátrix . Az első játékos választ egy számot 1 és , a második 1 és 1 között . Ezután ellenőrzik a számokat, és az első játékos pontokat kap, a második pedig pontokat ( - az első játékos által választott szám - a második). Meg kell találnunk az optimális stratégiát az első játékos számára. $A$ $n\szer m$ $n$ $m$ $a_{{ij}}$ $(-a_{{ij}})$ $én$ $j$

Engedje meg az optimális stratégiát, például az első játékost, a számot valószínűséggel kell kiválasztani . Ekkor az optimális stratégia a következő lineáris programozási probléma megoldása: $én$ $p_{i}$

0\leqslant p_{i}\leqslant 1,

p_{1}+\ldots +p_{n}=1,

a_{1i}p_{1}+a_{2i}p_{2}+\ldots +a_{ni}p_{n}\geqslant c\quad (i=1,\;\ldots ,\;m ),

amelyben a függvényt maximalizálni kell . Az optimális megoldásban az érték az első játékos nyereményére vonatkozó legrosszabb elvárás. $f(p_{1},\;\ldots ,\;p_{n},\;c)=c$ $c$

Megoldási algoritmusok

A lineáris programozás (LP) általános problémájának megoldására a leghíresebb és a gyakorlatban legelterjedtebb a szimplex módszer . Annak ellenére, hogy a szimplex módszer egy meglehetősen hatékony algoritmus, amely jó eredményeket mutatott az alkalmazott LP problémák megoldásában, ez egy exponenciális bonyolultságú algoritmus . Ennek oka a szimplex módszer kombinatorikus jellege, amely egymás után számba veszi a megengedett megoldások poliéderének csúcsait, miközben az optimális megoldást keresi.

Az első polinomiális algoritmust , az ellipszoid módszert 1979 -ben L. Khachiyan szovjet matematikus javasolta , ezzel megoldva egy sokáig megoldatlan problémát. Az ellipszoid módszer teljesen más nem-kombinatorikus jellegű, mint a szimplex módszer. Számítási szempontból azonban ez a módszer kilátástalannak bizonyult. Mindazonáltal a problémák polinomiális összetettségének ténye a hatékony LP-algoritmusok egész osztályának – a belsőpont- módszereknek – létrehozásához vezetett , amelyek közül az első N. Karmarkar 1984 -ben javasolt algoritmusa volt . Az ilyen típusú algoritmusok az LP-probléma folyamatos értelmezését alkalmazzák, amikor az LP-probléma megoldási politópjának csúcsainak felsorolása helyett a feladat azon változóinak terében, amelyek nem haladnak át a csúcsokon, trajektóriák mentén keresnek. a politóp. A belső pont módszer, amely a szimplex módszertől eltérően a tűréstartomány belsejéből kikerüli a pontokat, a Fiacco és McCormick által az 1960 -as években kifejlesztett nemlineáris programozási logaritmikus gátfüggvény módszereket alkalmazza.

Az LP megoldásának másik módja a Seidel algoritmus:

Az LP kanonikus formában van megadva a halmazt alkotó változókkal és megszorításokkal . $d$ $m$ $H$
Ha vagy , származtassa az optimális alapmegoldást . $d=1$ $m=0$ $H$
Ellenkező esetben válasszon egy véletlenszerű megszorítást , és számítsa ki rekurzív módon az optimális alapmegoldást . $h\in H$ $H\setminus \{h\}$
Ha az optimális alapmegoldás nem sérti a megszorítást , adja vissza. $H\setminus \{h\}$ $h$
Ellenkező esetben számítsa ki az LP poliéder metszéspontját a hipersíkkal , és oldja meg rekurzív módon a kapott LP-t egy változóval. $h$ $d-1$

Ez a módszer aszimptotikus bonyolultságú . $O(m\cdot d!)$

Kettős lineáris programozási problémák

Az űrlap minden lineáris programozási problémája [6]

\sum _{j=1}^{n}a_{ij}x_{j}\leqslant c_{i},\;i={\overline {1,\;m));

x_{j}\geqslant 0,\;j={\overline {1,\;n));

F(x)=\sum _{j=1}^{n}b_{j}x_{j}\to \max

bizonyos módon össze lehet hasonlítani egy másik lineáris programozási problémát, amelyet duálisnak vagy konjugáltnak neveznek az eredetihez vagy közvetlenhez képest. Az eredeti és a kettős probléma közötti kapcsolat főként abban rejlik, hogy az egyik megoldása közvetlenül a másik megoldásából nyerhető. Határozzuk meg a kettős problémát az eredeti lineáris programozási feladathoz képest

Kezdeti feladat	Kettős probléma
$\sum _{j=1}^{n}a_{ij}x_{j}\leqslant c_{i},\;i={\overline {1,\;m))$	$y_{i}\geqslant 0,\;i={\overline {1,\;m))$
$x_{j}\geqslant 0,\;j={\overline {1,\;n))$	$\sum _{i=1}^{m}a_{ij}y_{i}\geqslant b_{j},\;j={\overline {1,\;n))$
$F(x)=\sum _{j=1}^{n}b_{j}x_{j}\to \max$	$T(y)=\sum _{i=1}^{m}c_{i}y_{i}\to \min$

Ha a és vektorok elfogadható megoldások a primális és a duális problémákra, akkor a , és az egyenlőség akkor és csak akkor érhető el, ha és optimális megoldások. Ha az egyik kettős feladatpár célfüggvénye nincs korlátozva (felülről az eredetire, alulról a duálisra), akkor a másik probléma megvalósítható megoldásainak területe üres. $x$ $y$ $F(x)\leqslant T(y)$ $x$ $y$

Ha a és vektorok a direkt és a duális feladatok optimális megoldásai, akkor a következő egyenlőségek igazak $x^{*}$ $y^{*}$

x_{j}^{*}(\sum _{i=1}^{m}a_{ij}y_{i}^{*}-b_{j})=0,\;j={ \overline {1,\;n}};

y_{i}^{*}(\sum _{j=1}^{n}a_{ij}x_{j}^{*}-c_{i})=0,\;i={ \overline {1,\;m}}.

Vagyis a primális és duális problémák optimális megoldásához a nem feszült (szigorú egyenlőtlenség teljesül) megszorítások nulla változónak, a nem nulla változók (amelyek a támogatási tervben szerepelnek) pedig szorosnak (nem szigorú egyenlőtlenség valósul meg) mint egyenlőség) kötöttségek. De előfordulhat, hogy nulla változó megfelel a szigorú megszorításoknak.

A kettős megoldások ezen tulajdonságai jelentősen csökkenthetik a megoldási időt, ha a változók számánál jóval nagyobb megszorításokkal kell megoldani egy problémát. Ekkor a kettős feladat megoldása után meg lehet találni annak támogatási tervét, amely után a közvetlen feladatban csak a támogatási tervnek megfelelő kényszereket (ezeket a korlátokat feszülni kell) kiválasztva a szokásos lineáris egyenletrendszert. nekik.

Tétel. A kettős LP probléma kettőse az elsődleges LP probléma.

Bizonyítás: Tekintsük az űrlap közvetlen LP-jét a feltétel alatt . Társítsuk hozzá a duális LP-t, és kapjuk meg a feltétel alatt . Vegyük át egy másik, jelentésében egyenértékű formába: a feltétel alatt . Hasonlítsuk össze ismét a duális LP-t vele, és kapjuk meg a feltétel alatt . Egyenértékű formába hozzuk, és az eredetivel megegyező LP-t kapunk: a feltétel mellett . ${\displaystyle \max c^{T))$ $Ax\leqslant b,x\geqslant 0$ $\min b^{T}y$ $A^{T}y\geqslant c,y\geqslant 0$ $\max -b^{T}y$ $-A^{T}y\leqslant -c,y\geqslant 0$ $\min -c^{T}x$ $-Ax\geqslant -b,x\geqslant 0$ ${\displaystyle \max c^{T))$ $Ax\leqslant b,x\geqslant 0$

Szoftver

Az lp_solve egy nyílt forráskódú szoftver (LGPL GNU GNU General Public License for Libraries ) lineáris egyenletek megoldására. Az LpSolve rendelkezik IDE -vel , natív C API-val és sok más API-val a Java, AMPL, MATLAB, Wolfram Mathematica, O-Matrix, Sysquake, Scilab, Octave, FreeMat, Euler, Python, Sage, PHP, R és a Microsoft Solver Foundation számára. .

Lásd még

Jegyzetek

↑ 1 2 Forrás: Altai Regionális Egyetemes Tudományos Könyvtár. V. Ya. Shishkova (AKUNB) Archiválva : 2022. március 5. a Wayback Machine -nél . Optimalizálási módszerek: Proc. juttatás. Brazovskaya N.V.; Altáj Állami Műszaki Egyetem I. I. Polzunova, [Távolsági központ. tanulás]. - Barnaul: AltGTU Kiadó, 2000. - 120 p. - ISBN 5-BNV-MOr.9.00 - UDC / LBC 22.183.4 B871.
↑ Dikin I. I. Lineáris és másodfokú programozási feladatok iteratív megoldása // Dokl. A Szovjetunió Tudományos Akadémia. - 1967. - T. 174 , 4. sz . - S. 747-748 .
↑ Karmanov, 1986 , p. 63.
↑ Karmanov, 1986 , p. 80.
↑ Karmanov, 1986 , p. 77.
↑ Elektronikus tankönyv „Gazdasági és matematikai módszerek”. Kettősség a lineáris programozásban archiválva : 2016. június 17. a Wayback Machine -nál

Irodalom

Abramov L. M., Kapustin V. F. Matematikai programozás. - Oktatóanyag. - L. : LGU, 1981. - 328 p.
Akof R., Sasieni M. Az operációkutatás alapjai. — Per. angolról. V. Ya. Altaeva., szerk. I. A. Ushakova. — M .: Mir, 1971. — 551 p.
Akulich I. L. 1. fejezet A lineáris programozás problémái, 2. fejezet A lineáris programozás speciális problémái // Matematikai programozás példákban és feladatokban. - M . : Felsőiskola, 1986. - 319 p. — ISBN 5-06-002663-9 .
Astafjev NN Lineáris egyenlőtlenségek végtelen rendszerei a matematikai programozásban. - M. : Nauka, 1991. - 134 p.
Ashmanov S. A., Timokhov A. V. Optimalizációs elmélet feladatokban és gyakorlatokban. - M. : Nauka, 1991. - 446 p.
Gass S. Lineáris programozás. - M. : Fizikai-matematikai irodalom, 1961. - 300 p.
Davydov E. G. Operációkutatás. - M . : Felsőiskola, 1990. - 382 p.
Degtyarev Yu. I. Műveletek kutatása. — Tankönyv egyetemek számára. - M . : Felsőiskola, 1986. - 320 p.
Zukhovitsky S. I., Avdeeva L. I. Lineáris és konvex programozás. — M .: Nauka, 1966. — 348 p.
Karmanov VG Matematikai programozás. — 3. kiadás. — M .: Nauka, 1986. — 288 p.
Kuznyecov A. V., Sakovich V. A., Kholod N. I. Felső matematika. Matematikai programozás. - Minszk.: Felsőiskola, 1994. - 286 p.
Thomas H. Kormen és munkatársai 29. fejezet Lineáris programozás // Algoritmusok: Konstrukció és elemzés = Introduction to Algorithms. - 2. kiadás - M .: "Williams" , 2006. - S. 1296. - ISBN 5-8459-0857-4 .
Yudin D. B. , Holstein E. G. Lineáris programozás. — M .: Nauka, 1969. — 424 p.
Dantzig JB Emlékek a lineáris programozás kezdetéről.
Gabasov R., Kirillova F. M. A lineáris programozás módszerei. - Minszk: BGU, 1977. - 176 p.

Linkek

Linear Program Solver (LiPS) – Ingyenes optimalizáló csomag lineáris, egész és célprogramozási problémák megoldására.
Vershik A. M. O L. V. Kantorovich és a lineáris programozás
Lineáris programozási diák
Bolshakova I. V., Kuralenko M. V. Lineáris programozás. Oktatási segédlet az ellenőrző munkához . (lefelé mutató link 2013-05-13 óta [3461 nap])
Barsov A. S. Mi a lineáris programozás // Népszerű előadások a matematikáról , Gostekhizdat, 1959.
Vyalyi MN Lineáris egyenlőtlenségek és kombinatorika . – MTsNMO , 2003.

Szótárak és enciklopédiák

Bibliográfiai katalógusokban
BNF : 119415380 GND : 4035816-1 J9U : 987007555765405171 LCCN : sh85082127 NDL : 00570683 NKC : ph122356

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