Programare liniară

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 5 mai 2022; verificările necesită 5 modificări .

Programarea liniară este o disciplină matematică dedicată teoriei și metodelor de rezolvare a problemelor extreme pe mulțimi de spațiu vectorial -dimensional definite de sisteme de ecuații liniare și inegalități. $n$

Programarea liniară (LP) este un caz special de programare convexă , care, la rândul său, este un caz special de programare matematică . În același timp, stă la baza mai multor metode de rezolvare a problemelor de programare cu numere întregi și neliniare . O generalizare a programării liniare este programarea liniară fracțională .

Multe proprietăți ale problemelor de programare liniară pot fi interpretate și ca proprietăți ale poliedrelor și astfel pot fi formulate și demonstrate geometric.

Istorie

Studiile matematice ale problemelor economice individuale, formalizarea matematică a materialului numeric a fost efectuată încă din secolul al XIX-lea . În analiza matematică a procesului de producție extins, s-au folosit relații algebrice, analiza lor a fost efectuată folosind calcul diferențial . Acest lucru a permis să ne facem o idee generală a problemei.

Dezvoltarea economiei a necesitat indicatori cantitativi, iar în anii 1920 a fost creat un echilibru intersectorial ( IOB ). El a fost cel care a servit drept imbold în crearea și studiul modelelor matematice. Dezvoltarea MOB în 1924-1925 în URSS a influențat activitatea economistului și statisticianului Vasily Vasilievich Leontiev . El a dezvoltat un model intersectorial de producție și distribuție a produselor.

În 1938, Leonid Vitalievich Kantorovich , în cursul consultării științifice, a început să studieze sarcina pur practică de a elabora cel mai bun plan pentru încărcarea mașinilor de decojit (trust de placaj). Această sarcină nu se preta metodelor convenționale. A devenit clar că sarcina nu era întâmplătoare. [unu]

În 1939, Leonid Kantorovich a publicat lucrarea „Metode matematice de organizare și planificare a producției”, în care a formulat o nouă clasă de probleme extreme cu restricții și a dezvoltat o metodă eficientă de rezolvare a acestora, punând astfel bazele programării liniare.

Studiul unor astfel de probleme a condus la crearea unei noi discipline științifice de programare liniară și a deschis o nouă etapă în dezvoltarea metodelor economice și matematice.

În 1949, matematicianul american George Bernard Dantzig a dezvoltat o metodă eficientă pentru rezolvarea problemelor de programare liniară (LPP) - metoda simplex . [unu]

Termenul „programare” trebuie înțeles în sensul de „planificare” (una dintre traducerile programării în limba engleză ). A fost propus la mijlocul anilor 1940 de George Danzig, unul dintre fondatorii programării liniare, înainte ca calculatoarele să fie folosite pentru a rezolva probleme de optimizare liniară .

Metoda punctului interior a fost menționată pentru prima dată de I. I. Dikin în 1967 . [2] . Aceste studii au fost continuate, inclusiv de către oamenii de știință autohtoni. În anii 1970, V. G. Zhadan a reușit să obțină principalele rezultate și să dezvolte o abordare generală a construcției metodelor punctuale interioare pentru rezolvarea problemelor de programare liniară și neliniară, bazate pe transformarea spațiilor; propune metode numerice barieră-proiectivă și barieră-newtoniene.

Sarcini

Problema generală (standard) a programării liniare este problema găsirii minimului unei funcții obiective liniare (forma liniară) de forma [3] :

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

O problemă în care apar constrângeri sub formă de inegalități se numește problemă de programare liniară de bază (BLP)

\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)

Problema programării liniare va avea o formă canonică dacă în problema principală în locul primului sistem de inegalități există un sistem de ecuații cu constrângeri sub formă de egalitate [4] :

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

Problema principală poate fi redusă la una canonică prin introducerea unor variabile suplimentare.

Problemele de programare liniară de cea mai generală formă (probleme cu constrângeri mixte: egalități și inegalități, prezența variabilelor libere de constrângeri) pot fi reduse la echivalente (având același set de soluții) modificări ale variabilelor și înlocuirea egalităților cu o pereche de inegalități [5] .

Este ușor de observat că problema găsirii maximului poate fi înlocuită cu problema găsirii minimului luând coeficienții cu semnul opus. $c$

Exemple de probleme

Potrivire maximă

Luați în considerare problema de potrivire maximă într-un grafic bipartit : există mai mulți băieți și fete, iar pentru fiecare băiat și fată se știe dacă se plac. Este necesar să se căsătorească numărul maxim de cupluri cu simpatie reciprocă.

Să introducem variabile care corespund perechii de la --lea băiat și ---a fată și să satisfacem restricțiile: $x_{ij}$ $i$ $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,

cu o funcție obiectivă , unde sunt egale cu 1 sau 0, în funcție de dacă cel de -al -lea băiat și --a fată sunt drăguți unul cu celălalt. Se poate arăta că printre soluțiile optime ale acestei probleme există o soluție întreagă. Variabilele egale cu 1 vor corespunde cuplurilor care ar trebui să fie căsătorite. ${\displaystyle f=c_{11}x_{11}+c_{12}x_{12}+\ldots +c_{nm}x_{nm))$ $c_{ij}$ $i$ $j$

Debit maxim

Să existe un grafic (cu muchii direcționate) în care pentru fiecare muchie să fie indicată capacitatea sa. Și sunt date două vârfuri: o chiuvetă și o sursă. Este necesar să se precizeze pentru fiecare muchie cât de mult fluid va curge prin ea (nu mai mult decât capacitatea sa) astfel încât să se maximizeze debitul total de la sursă la chiuvetă (fluidul nu poate apărea sau dispărea la toate vârfurile cu excepția sursei și, respectiv, a chiuvei).

Să luăm ca variabile cantitatea de fluid care curge prin marginea a treia. Apoi $x_{i}$ $i$

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

unde este capacitatea muchiei. Aceste inegalități trebuie completate de egalitatea cantității de fluid de intrare și de ieșire pentru fiecare vârf, cu excepția chiuvetei și a sursei. Ca o funcție, este firesc să luăm diferența dintre cantitatea de lichid care curge și cea care intra la sursă. $c_{i}$ $i$ $f$

O generalizare a problemei anterioare este fluxul maxim al costului minim. In aceasta problema se dau costurile pentru fiecare muchie si este necesar sa se aleaga dintre debitele maxime debitul cu costul minim. Această sarcină este redusă la două probleme de programare liniară: mai întâi, trebuie să rezolvați problema debitului maxim, apoi să adăugați la această problemă constrângerea , unde este valoarea debitului maxim și să rezolvați problema cu o nouă funcție - costul fluxului. $f(x)\geqslant m$ $m$ $f(x)$

Aceste probleme pot fi rezolvate mai rapid decât prin algoritmi generali de rezolvare a problemelor de programare liniară datorită structurii speciale a ecuațiilor și inegalităților.

Problemă de transport

Există o anumită marfă omogenă care trebuie transportată de la depozite la fabrici. Pentru fiecare depozit , se știe câtă încărcătură este în el și pentru fiecare fabrică se cunoaște nevoia de marfă. Costul transportului este proporțional cu distanța de la depozit la fabrică (se cunosc toate distanțele de la --lea depozit până la ----a fabrică). Este necesar să întocmească cel mai ieftin plan de transport. $n$ $m$ $i$ $a_{i}$ $B j}$ $c_{ij}$ $i$ $j$

Variabilele decisive în acest caz sunt - cantitatea de marfă transportată de la --lea depozit la --a uzină. Acestea îndeplinesc restricțiile: $x_{ij}$ $i$ $j$

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

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

Funcția obiectiv are forma: , care trebuie minimizată. $f(x)=x_{{11}}c_{{11}}+x_{{12}}c_{{{12}}+\ldots +x_{{nm}}c_{{nm}}$

Joc cu sumă zero

Există o matrice de dimensiuni . Primul jucător alege un număr de la 1 la , al doilea - de la 1 la . Apoi verifică numerele și primul jucător primește puncte, iar al doilea primește puncte ( - numărul ales de primul jucător - al doilea). Trebuie să găsim strategia optimă pentru primul jucător. $A$ $de n\ ori m$ $n$ $m$ $a_{{ij}}$ $(-a_{{ij}})$ $i$ $j$

Lăsați strategia optimă, de exemplu, primul jucător, numărul trebuie ales cu probabilitate . Atunci strategia optimă este o soluție la următoarea problemă de programare liniară: $i$ $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 ),

în care funcţia urmează să fie maximizată . Valoarea în soluția optimă va fi cea mai nefavorabilă așteptare a primului jucător. $f(p_{1},\;\ldots ,\;p_{n},\;c)=c$ $c$

Algoritmi de soluție

Cea mai cunoscută și utilizată pe scară largă în practică pentru rezolvarea problemei generale a programării liniare (LP) este metoda simplex . În ciuda faptului că metoda simplex este un algoritm destul de eficient care a dat rezultate bune în rezolvarea problemelor aplicate LP, este un algoritm cu complexitate exponențială . Motivul pentru aceasta este natura combinatorie a metodei simplex, care enumeră succesiv vârfurile poliedrului soluțiilor admisibile în căutarea soluției optime.

Primul algoritm polinomial , metoda elipsoidului , a fost propus în 1979 de matematicianul sovietic L. Khachiyan , rezolvând astfel o problemă care rămăsese nerezolvată multă vreme. Metoda elipsoidală are o natură necombinatorie complet diferită de metoda simplex. Cu toate acestea, din punct de vedere computațional, această metodă s-a dovedit a fi nepromițătoare. Cu toate acestea, însuși faptul complexității polinomiale a problemelor a condus la crearea unei clase întregi de algoritmi LP eficienți - metode de punct interior , primul dintre care a fost algoritmul lui N. Karmarkar propus în 1984 . Algoritmii de acest tip folosesc o interpretare continua a problemei LP, cand in loc de enumerarea varfurilor politopului de solutii la problema LP se face o cautare de-a lungul traiectoriilor in spatiul variabilelor problemei care nu trec prin varfuri. a politopului. Metoda punctului interior, care, spre deosebire de metoda simplex, ocolește punctele din interiorul intervalului de toleranță, utilizează metode de programare neliniară a funcției de barieră logaritmică dezvoltate în anii 1960 de Fiacco și McCormick.

O altă metodă de rezolvare a LP este utilizarea algoritmului Seidel:

LP este dat în formă canonică cu variabile și constrângeri care alcătuiesc mulțimea . $d$ $m$ $H$
Dacă sau , deduceți soluția de bază optimă . $d=1$ $m=0$ $H$
În caz contrar, alegeți o constrângere aleatorie și calculați recursiv soluția de bază optimă pentru . $h\în H$ $H\setminus \{h\)$
Dacă soluția de bază optimă pentru nu încalcă constrângerea , returnați-o. $H\setminus \{h\)$ $h$
În caz contrar, se calculează intersecția poliedrului LP cu hiperplanul și se rezolvă recursiv LP rezultat cu o variabilă. $h$ $d-1$

Această metodă are complexitate asimptotică . $O(m\cdot d!)$

Probleme de programare liniară duală

Fiecare problemă de programare liniară [6] din forma

\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

este posibil într-un anumit fel să comparăm o altă problemă de programare liniară, numită duală sau conjugată cu cea originală sau directă. Legătura dintre problemele inițiale și cele duale constă în principal în faptul că rezolvarea uneia dintre ele poate fi obținută direct din rezolvarea celeilalte. Să definim problema duală în raport cu problema originală de programare liniară

Sarcina inițială	Problemă dublă
$\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$

Dacă vectorii și sunt soluții admisibile la problemele primare și duale, atunci , și egalitatea este atinsă dacă și numai dacă și sunt soluții optime. Dacă funcția obiectivă a uneia dintre perechile de probleme duale nu este limitată (de sus pentru cea originală, de jos pentru cea duală), atunci zona de soluții fezabile a celeilalte probleme este goală. $X$ $y$ $F(x)\leqslant T(y)$ $X$ $y$

Dacă vectorii și sunt soluțiile optime ale problemelor directe și, respectiv, duale, atunci următoarele egalități sunt adevărate $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}}.

Adică, pentru soluții optime la problemele primale și duale, constrângerile non-temporale (ineegalitatea strictă este satisfăcută) corespund variabilelor zero, iar variabilelor diferite de zero (incluse în planul de suport) corespund unor constrângeri strânse (este implementată inegalitatea nestrictă). ca egalitate) constrângeri. Dar pot exista zero variabile care corespund unor constrângeri stricte.

Aceste proprietăți ale soluțiilor duale pot reduce semnificativ timpul de rezolvare dacă trebuie să rezolvați o problemă cu un număr de constrângeri mult mai mare decât numărul de variabile. Atunci este posibil, după rezolvarea problemei duale, să se găsească planul de sprijin al acesteia, după care, selectând în problema directă doar constrângerile corespunzătoare planului de sprijin (toate aceste constrângeri trebuie tensionate), se rezolvă sistemul obișnuit de ecuații liniare. pentru ei.

Teorema. Problema duală a LP-ului dual este problema LP primară.

Dovada: Luați în considerare un LP direct al formei sub condiția . Să asociem LP-ul dublu cu acesta și să obținem sub condiția . Să o aducem la o altă formă, echivalentă ca sens: sub condiția . Să comparăm din nou LP-ul dublu cu acesta și să obținem în condiția . Îl aducem într-o formă echivalentă și obținem un LP identic cu cel original: sub condiția . $\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$ $\max c^{T)$ $Ax\leqslant b,x\geqslant 0$

Software

lp_solve este un software open source (LGPL GNU GNU General Public License for Libraries ) pentru rezolvarea ecuațiilor liniare. LpSolve are un IDE , C API nativ și multe alte API-uri pentru Java, AMPL, MATLAB, Wolfram Mathematica, O-Matrix, Sysquake, Scilab, Octave, FreeMat, Euler, Python, Sage, PHP, R și Microsoft Solver Foundation .

Vezi și

Note

↑ 1 2 Sursa: Biblioteca Științifică Universală Regională Altai. V. Ya. Shishkova (AKUNB) Arhivat pe 5 martie 2022 la Wayback Machine . Metode de optimizare: Proc. indemnizatie. Brazovskaya N.V.; Universitatea Tehnică de Stat din Altai I. I. Polzunova, [Centrul distanței. învăţare]. - Barnaul: Editura AltGTU, 2000. - 120 p. - ISBN 5-BNV-MOr.9.00 - UDC / LBC 22.183.4 B871.
↑ Dikin I. I. Rezolvarea iterativă a problemelor de programare liniară și pătratică // Dokl. Academia de Științe a URSS. - 1967. - T. 174 , nr 4 . - S. 747-748 .
↑ Karmanov, 1986 , p. 63.
↑ Karmanov, 1986 , p. 80.
↑ Karmanov, 1986 , p. 77.
↑ Manual electronic „Metode economice și matematice”. Dualitate în programarea liniară Arhivat 17 iunie 2016 la Wayback Machine

Literatură

Abramov L. M., Kapustin V. F. Programare matematică. - Tutorial. - L . : LGU, 1981. - 328 p.
Akof R., Sasieni M. Fundamentele cercetării operaționale. — Trans. din engleza. V. Ya. Altaeva., ed. I. A. Ushakova. — M .: Mir, 1971. — 551 p.
Akulich I. L. Capitolul 1. Probleme de programare liniară, Capitolul 2. Probleme speciale de programare liniară // Programarea matematică în exemple și probleme. - M . : Şcoala superioară, 1986. - 319 p. — ISBN 5-06-002663-9 .
Astafiev NN Sisteme infinite de inegalități liniare în programarea matematică. - M. : Nauka, 1991. - 134 p.
Ashmanov S. A., Timokhov A. V. Teoria optimizării în sarcini și exerciții. - M. : Nauka, 1991. - 446 p.
Gass S. Programare liniară. - M. : Literatură fizico-matematică, 1961. - 300 p.
Davydov E. G. Cercetare operațională. - M . : Şcoala superioară, 1990. - 382 p.
Degtyarev Yu. I. Cercetarea operațiunilor. — Manual pentru universități. - M . : Şcoala superioară, 1986. - 320 p.
Zukhovitsky S. I., Avdeeva L. I. Programare liniară și convexă. — M .: Nauka, 1966. — 348 p.
Karmanov VG Programare matematică. — ediția a 3-a. — M .: Nauka, 1986. — 288 p.
Kuznetsov A. V., Sakovich V. A., Kholod N. I. Matematică superioară. Programare matematică. - Minsk.: Şcoala superioară, 1994. - 286 p.
Thomas H. Kormen și colab.Capitolul 29. Programare liniară // Algoritmi: Construcție și analiză = Introducere în algoritmi. - Ed. a II-a. - M .: „Williams” , 2006. - S. 1296. - ISBN 5-8459-0857-4 .
Yudin D. B. , Holstein E. G. Programare liniară. — M .: Nauka, 1969. — 424 p.
Dantzig JB Amintiri de la începutul programării liniare.
Gabasov R., Kirillova F. M. Metode de programare liniara. - Minsk: BGU, 1977. - 176 p.

Link -uri

Linear Program Solver (LiPS) — Un pachet de optimizare gratuit pentru rezolvarea problemelor de programare liniară, întregă și țintă.
Vershik A. M. O L. V. Kantorovich și programarea liniară
Diapozitive de programare liniară
Bolshakova I. V., Kuralenko M. V. Programare liniară. Ajutor didactic pentru munca de control . (link descendent din 13-05-2013 [3461 zile])
Barsov A. S. Ce este programarea liniară // Prelegeri populare despre matematică , Gostekhizdat, 1959.
Vyalyi MN Inegalități liniare și combinatorie . — MTsNMO , 2003.

Dicționare și enciclopedii

În cataloagele bibliografice
BNF : 119415380 GND : 4035816-1 J9U : 987007555765405171 LCCN : sh85082127 NDL : 00570683 NKC : ph122356

Metode de optimizare
Unidimensional	metoda secțiunii de aur Dihotomie Metoda parabolelor Căutare în grilă Metoda de căutare uniformă a blocurilor Metoda Fibonacci Căutare ternară metoda Piyavsky Metoda Strongin
Comanda zero	metoda Gauss Metoda Nelder-Mead Metoda Hook-Jeeves metoda Rosenbrock metoda Powell
Prima comanda	coborâre în gradient Metoda Zeutendijk Coordonarea coborârii Metoda gradientului conjugat Metode cvasi-newtoniene Algoritmul Levenberg-Marquardt
a doua comanda	metoda lui Newton Metoda Newton-Raphson Algoritmul Broyden-Fletcher-Goldfarb-Shanno (BFGS)
Stochastic	Metoda Monte Carlo Recoacere simulată Algoritmi evolutivi evolutie diferentiala Algoritmul furnicilor Metoda roiului de particule Algoritmul coloniilor de albine Metoda de mers aleatoriu
Metode de programare liniară	Metoda simplex algoritmul lui Gomori Metoda elipsoidă Metoda potențială
Metode de programare neliniară	Programare secvenţială pătratică