În optimizarea matematică , o problemă de optimizare liniară necesită minimizarea unei funcții liniare pe un poliedru convex . Funcția care este minimizată, precum și constrângerile sunt descrise de funcții liniare , de unde și numele dat acestor probleme. Optimizare liniara (LO) este disciplina care studiază problemele. Este denumit și numele de programare liniară , termen introdus de George Dantzig în jurul anului 1947, dar acest nume tinde să fie abandonat din cauza unei posibile confuzii cu noțiunea de programare pe computer .
De exemplu, următoarea problemă cu două variabile
care constă în minimizarea funcției liniare sub constrângerea inegalității afine x 1 + 2 x 2 ≥ 2 și constrângerile de pozitivitate ale lui x i reprezintă o problemă de optimizare liniară. Soluția sa este ( x 1 , x 2 ) = (0,1) . De îndată ce numărul de variabile și constrângeri crește, problema nu mai poate fi rezolvată prin încercări și erori.
Mai general, o problemă OL va fi deci scrisă în notație matricială după cum urmează
unde este necunoscutul, vectorul variabilelor reale x 1 , ..., x n care trebuie optimizat, iar datele sunt vectori și și o matrice . Inegalitatea vectorială Ax ≤ b trebuie înțeleasă componentă cu componentă: pentru orice indice i , trebuie să avem ( Ax - b ) i ≤ 0 . Setul admisibil este , prin urmare , într - adevăr un poliedru convex, deoarece este vorba de intersecția jumătățile de spații , pentru i = 1, ..., m , în număr finit . O problemă de maximizare revine la formularea anterioară prin minimizarea opusului funcției de cost pe același poliedru convex.
Printre problemele de optimizare cu constrângeri de inegalitate, problemele liniare sunt ușor de rezolvat numeric. Într-adevăr, sunt cunoscuți algoritmi polinomiali eficienți, necesitând, prin urmare, o serie de iterații care este crescută cu un polinom, în funcție de dimensiunile problemei. De obicei, un algoritm punct interior va necesita teoretic cel mult ordinea iterațiilor O ( √ n ) pentru o formulare a problemei apropiată de cea dată mai sus.
Multe probleme de cercetare operațională pot fi exprimate ca probleme de optimizare liniară. Aceste probleme apar, de asemenea, ca produse secundare în algoritmi concepuți pentru a rezolva probleme mai dificile.
În anumite probleme LO, se impune în plus ca variabilele să ia doar valori întregi (așa-numitele constrângeri de integritate ) sau chiar că valorile 0 sau 1. Vorbim apoi de o problemă de optimizare liniară în numere întregi . Aceste ultime probleme sunt mult mai dificil de rezolvat decât problemele variabilei continue LO descrise mai sus.
Putem prevedea problema din dimensiunea a doua observând următoarea situație: „O firmă are proiectul de a construi două produse care necesită utilizarea a trei mașini. mașina A poate funcționa doar 150 de ore pe lună, mașina B 210 ore și mașina C 180 de ore. Primul produs P1 necesită 1 oră de la mașina A și 1 oră de la mașina B și se vinde cu 300 de euro pe unitate. Al doilea produs P2 necesită o oră de la mașina A, trei ore de la mașina B și 3 ore de la mașina C și se vinde cu 500 de euro pe unitate. Firma caută să definească programul de fabricație permițându-i să-și maximizeze profitul. "
O modelare matematică conduce la apelarea x numărul de produse P1 care urmează să fie fabricate și y numărul de produse P2; M va fi punctul coordonatelor ( x , y ) . Constrângerile de fabricație sunt exprimate folosind următoarele inegalități:
Fiecare dintre aceste constrângeri definește un semiplan de care trebuie să aparțină M. Intersecția acestor semiplane trasează un poligon convex (OABCD) numit set admisibil .
Pe acest set admisibil, definim funcția de venit net: f ( x , y ) = 300 x + 500 y pe care încercăm să o facem maximă. Programele de producție care permit introducerea, de exemplu, a 40.000 de euro, corespund punctelor de pe linie (d 40.000 ): 300 x + 500 y = 40.000 . Această linie împarte planul în două semiplane, unul în care f ( x , y ) <40.000 și celălalt în care f ( x , y )> 40.000 . Deoarece există puncte din setul eligibil aparținând celui de-al doilea semiplan, se pot găsi programe de producție care să aducă venituri mai mari. Programele de fabricație care dau un venit S corespund punctelor unei linii (d S ) paralele cu (d 40000 ). Pentru a maximiza venitul net, este suficient să găsiți linia (d S ) paralelă cu (d 40000 ) care conține cel puțin un punct al setului admisibil fără a-l traversa: o astfel de linie trece în mod necesar printr-un vârf al poligonului și o linie simplă. observarea grafică plasează linia în cauză la punctul B.
O optimizare liniară în dimensiunea doi constă în general în desenarea setului admisibil (poligon convex mărginit sau nu) și în găsirea celei mai bune poziții a unei linii cu direcție fixă pentru a face maximă sau minimă o valoare dată. Această linie, dacă există, trece întotdeauna printr-un vârf al poligonului. Într-o optimizare liniară a dimensiunii trei, setul admisibil este un poliedru, iar optimizarea constă în găsirea celei mai bune poziții a unui plan de direcție fixă.
Problema devine mai complexă în dimensiuni superioare, unde o rezoluție grafică este de neconceput și necesită instrumente care necesită formalizare sub formă de matrice.
Formalizarea canonică : în exemplul de mai sus, stabilim Constrângerile pot fi rezumate ca Au ≤ b . Funcția de venit net este că trebuie să maximizați. Formalizarea canonică este în cele din urmă scrisă
care poate fi scris sub forma introducerii prin schimbarea lui A , b și c în opusele lor.
Formalizarea standardUneori este util să înlocuiți inegalitatea care definește setul admisibil printr-o egalitate. Acest lucru se poate face prin creșterea dimensiunii de studiu a problemei. În exemplul de mai sus, cele trei inegalități au ca rezultat trei egalități și trei constrângeri pozitive în următoarea formă
Este suficient atunci să întrebi pentru a obține formalizarea
Pe aceste forme (canonice sau standard) sunt stabilite tehnicile de optimizare n- dimensională . Aceștia își asumă cunoașterea algebrei liniare , a notațiilor matriciale și a elementelor de bază ale optimizării (în special, vocabularul acestei discipline).
Putem reprezenta un poliedru convex în diferite moduri. Când este văzut ca mai sus, și anume ca o intersecție a unui număr finit de jumătăți de spații:
spunem că poliedrul (sau problema de optimizare liniară cu un astfel de poliedru) este scris în formă canonică . Când poliedrul convex este văzut ca intersecția ortantului pozitiv și a unui subspatiu afin:
spunem că poliedrul (sau problema de optimizare liniară cu un astfel de poliedru) este scris în formă standard .
În practică, problemele pot avea constrângeri mai variate sau mai structurate , cum ar fi constrângeri de egalitate sau constrângeri de limită inferioară și superioară:
Solvenții buni permit utilizarea unor astfel de reprezentări ale setului admisibil. Cu toate acestea, întrucât multe constrângeri complică și împovără inutil analiza problemelor de optimizare liniară, astfel încât aceasta din urmă se face în general pe o formulare simplificată a setului admisibil permițând totuși să reprezinte toate constrângerile afine imaginabile. Formulările canonice și standard au această proprietate de genericitate, cu condiția să fie introduse date și variabile suplimentare. În special, un set admisibil scris în formă canonică poate fi reprezentat în următoarea formă standard:
legătura dintre variabila x a formei canonice și variabilele ( u , v , s ) ale formulării standard de mai sus fiind realizată de x = u - v . În schimb, un set admisibil scris în formă standard poate fi reprezentat în următoarea formă canonică:
Analizele problemei de optimizare liniară se fac cel mai adesea pe problema al cărei set admisibil este reprezentat în forma standard, problemă pe care o vom scrie după cum urmează:
Observăm
valoarea optimă a ( P L ) și
toate soluțiile sale (care pot fi goale).
Calificatorul liniar dat problemei ( P L ) definit mai sus poate fi înșelător. Într-adevăr, aceste probleme nu sunt liniare în sensul că soluțiile lor ar depinde liniar de unele dintre datele lor. Acestea sunt inegalitățile care definesc constrângerile care introduc neliniaritatea. În absența inegalităților, problema devine liniară în acest sens, dar este apoi banală: fie nu există o soluție, fie toate punctele admisibile sunt soluții.
varf de munte
Unii algoritmi sunt interesați de vârfurile poliedrului convex pe care se minimizează o funcție liniară. În algoritmul simplex , de exemplu, toate iterațiile sunt vârfurile poliedrului convex care este mulțimea admisibilă.
Un vârf al unui poliedru convex este o față zero dimensională a acestui set, adică un punct care poate fi îndepărtat din convex fără a pune sub semnul întrebării convexitatea acestuia; spuneți-l altfel și aceasta este definiția precisă, este un punct care nu poate fi scris ca jumătate de sumă a două puncte distincte ale poliedrului convex. Deci x este un vârf al poliedrului convex P dacă x ∈ P și dacă
Nu toate poliedrele convexe au neapărat un vârf. De exemplu, jumătatea nu are unul. Cu toate acestea, un poliedru convex scris în forma standard are întotdeauna unul; acesta este unul dintre motivele pentru care algoritmul simplex este definit pe o problemă OL având setul său admisibil scris în această formă. Mai mult decât atât, este ușor să le recunoaștem printr-o tehnică de algebră liniară.
Notă A j coloană c a matricei A .
Partea de sus a unui poliedru convex într -o formă standard , - Să o nevid convex poliedru si x ∈ P . Apoi, următoarele proprietăți sunt echivalente:
Mai mult, P are cel puțin un vârf.
Există exact două cazuri (exclusive) în care problema de optimizare liniară nu are nicio soluție.
În toate celelalte cazuri, valoarea optimă a problemei de optimizare liniară este finită și problema are o soluție.
Existența soluției - Pentru o problemă de optimizare liniară, următoarele proprietăți sunt echivalente:
Un alt rezultat al existenței soluției, bazat pe cel anterior și foarte des utilizat, este dat de teorema puternică a dualității din secțiunea Proprietăți ale dualității .
Deoarece setul de soluții al lui ( P L ) este un poliedru convex scris în formă standard, acesta va avea un vârf dacă nu este gol și acest vârf va fi, de asemenea, un vârf al mulțimii admisibile a ( P L ) .
Existența unei soluții de vârf - Dacă problema ( P L ) are o soluție, ea are o soluție la un vârf al setului său admisibil.
Acest rezultat este important pentru algoritmul simplex , deoarece acesta din urmă, generându-și iterațiile pe vârfuri, caută o soluție de vârf (care, prin urmare, trebuie să existe pentru ca acesta să găsească una!).
Condițiile de optimitate ale problemei de optimizare liniară ( P L ) pot fi obținute ca un caz special al teoriei generale a problemelor de optimizare diferențiată cu dimensiuni finite ( condițiile lui Karush, Kuhn și Tucker ), cu simplificarea suplimentară a ne cu calificarea constrângerilor problemei. Afinitatea acestora le face într-adevăr calificate (vezi secțiunea Afinitate locală (QC-A) ), astfel încât să nu găsim nicio urmă a acestor întrebări în manualele de optimizare liniară. Mai mult, datorită convexității problemei OL, condițiile enumerate mai jos sunt necesare și suficiente pentru optimitate.
Condiții de optimitate - Punctul este soluția lui ( P L ) dacă și numai dacă există vectori și astfel încât
Variabilele y și s introduse de aceste condiții de optimitate poartă numele multiplicatorilor Lagrange sau variabile duale . Primele sunt asociate cu constrângerile egalității (există una prin constrângere) și a doua cu constrângerile pozitivității variabilei primare x . După cum vom avea ocazia să vedem mai jos, aceste variabile ascunse în problemă ( P L ) joacă un rol important în analiza sa. Notăm setul de soluții primal-duale , adică setul de tripluri ( x , y , s ) care îndeplinesc condițiile de optimitate de mai sus.
Relațiile ( a ) exprimă admisibilitatea duală și prima dintre aceste relații este gradientul în x al Lagrangianului problemei, care este funcția
Relațiile ( b ) exprimă admisibilitatea primară și relația ( c ) exprimă complementaritatea existentă între variabilele primare x și multiplicatorii lor s : x i unde s i este zero (sau ambii); vezi și mai jos.
Fiecare variabilă optimă duală este interpretată ca fiind costul marginal asociat constrângerii sale.
După eliminarea variabilei cu variație duală s , condițiile de optimitate pot fi scrise sub forma unei probleme de complementaritate liniară cu constrângere liniară :
Aceste condiții de optimitate au multiple utilizări. Acestea fac posibilă în special proiectarea de algoritmi primali-duali (astfel calificați deoarece utilizează apoi variabilele primare și duale) de rezoluție. De asemenea, fac posibilă stabilirea diferitelor proprietăți ale problemelor OL.
Produs cartezian al soluțiilor - Setul de soluții primale-duale este un produs cartezian :
Cu alte cuvinte, dacă ( x 1 , y 1 , s 1 ) și ( x 2 , y 2 , s 2 ) sunt soluții primal-dual, atunci ( x 1 , y 2 , s 2 ) este, de asemenea, o soluție primal-dual .
Soluție strict complementarăSă ne întoarcem la condițiile de complementaritate, condiția ( c ) a sistemului de optimitate. Această condiție este scrisă
Deoarece x și s au componentele lor pozitive, este la fel să scriem
sau
Acest lucru nu implică faptul că s i > 0 când x i = 0 .
O soluție primală-duală ( x , y , s ) se spune că este strict complementară , dacă
O problemă de optimizare liniară cu soluție are întotdeauna o soluție primară-duală strict complementară. Observăm
Soluție primar-duală strict complementară - Dacă problema ( P L ) are o soluție, atunci are o soluție primară-duală strict complementară. Această afirmație înseamnă a spune că ( B , N ) formează o partiție a :
Dualizarea Lagrangiene este o tehnică utilizată pentru a introduce o problemă duală a unei probleme de optimizare. Dacă luăm în considerare problema de optimizare ( P L ) , dualizarea lagrangiană duce la următoarea problemă dublă standard
Acestea sunt două probleme de maximizare; cea din dreapta se obține din cea din stânga prin eliminarea variabilei , astfel încât să rămână doar variabila .
Observăm
valoarea optimă a ( D L ) și
toate soluțiile sale (care pot fi goale).
Tehnica dualizăriiAm putea afirma problema dublă a celei mai generale probleme de optimizare liniară, dar preferăm să oferim aici tehnica utilizată pentru a le stabili, ceea ce ne va permite să ieșim din ea în toate cazurile. Pornim de la problema ( P L ) , calificată aici ca primară .
Primul pas este să scriem problema primară ca inf inf . De exemplu, ca la fix
avem
Egalitatea ia în considerare convenția conform căreia minimul peste un set gol este + ∞ ; prin urmare, dacă nu există x ≥ 0 care să satisfacă Ax = b , vom găsi + ∞ în ambii membri. Am scris astfel problema primară ca un inf sup (eliminăm parantezele, ținând cont că sensul care trebuie dat acestui inf sup este cel de mai sus):
Spunem că am dualizat constrângerea egalității Ax = b , deoarece cu aceasta am construit Lagrangianul intervenind în tehnica dualizării de mai sus.
Al doilea pas constă în inversarea ordinii în care sunt luate infinitul și supremul, pentru a obține dubla problemă
Rămâne să o interpretăm. Să începem cu problema internă :
Deoarece, prin convenție, supremul asupra unui set gol este –∞ , problema dublă este scrisă
după cum este publicat mai sus.
Proprietăți de dualitateOricare ar fi funcția definită pe seturile arbitrare X și Y , avem
Aceasta se numește relația de dualitate slabă . Prin tehnica dualizării lagrangiene expusă mai sus, se obține apoi următoarea relație între valorile primare optime și cele duale.
Dualitate slabă - .
În cazul optimizării liniare, această inegalitate se obține prin calcul simplu: luăm un punct primar admisibil x , un punct dual admisibil y , deducem acest lucru și încheiem luând limita superioară din stânga și limita inferioară în dreapta .
Deducem din rezultatul dualității slabe că, dacă una dintre cele două probleme este nelimitată, cealaltă nu este fezabilă.
Diferența dintre valorile primare optime și cele duale este ceea ce numim saltul dualității :
Spunem că nu există salt de dualitate dacă val ( P L ) = val ( D L ) . În optimizarea liniară, este rar să existe un salt de dualitate. Singura posibilitate este că avem val ( P L ) = + ∞ (adică, problema primară nu este fezabilă; de exemplu, dacă A = 0 și b ≠ 0 ) și val ( D L ) = –∞ (adică dualul problema nu este fezabilă; de exemplu, dacă A = 0 și ). Este o consecință a rezultatului existenței soluției în OL (a se vedea mai sus) și a rezultatului următor al dualității puternice .
Dualitate puternică - Următoarele proprietăți sunt echivalente:
În acest caz, nu există un salt de dualitate.
Demonstrarea acestui rezultat nu este lipsită de interes. Să oferim câteva dovezi, care vor oferi câteva informații suplimentare.
Implicația 1 → 2 [resp. 1 → 3] este foarte des folosit pentru a arăta că problema primară [resp. dual] are o soluție. Pentru ca acesta să fie cazul, este suficient să se verifice dacă problemele primare și duale sunt fezabile, fapt care poate fi observat fără dificultate în anumite cazuri.
Algoritmul simplex , dezvoltat de Danzig din 1947, este o finit metodă de rezolvare a unei probleme OL. Calificativul finit înseamnă că într-un număr finit de pași, algoritmul găsește o soluție sau arată că problema este nelimitată sau arată că problema nu este fezabilă (singurele trei posibilități pentru o problemă de OL, vezi mai sus ). Algoritmul are o interpretare geometrică simplă. Iterațiile sunt vârfurile mulțimii admisibile (un poliedru convex). La un vârf, algoritmul determină o margine (fața dimensiunii 1) a setului admisibil de-a lungul căreia funcția de cost scade și ia ca nou iterat vârful situat la sfârșitul marginii selectate (operație numită pivotare ). Pot exista mai multe margini care fac posibilă scăderea funcției de cost. În regula costului redus minim , algoritmul alege o margine de-a lungul căreia funcția de cost scade cel mai mult.
Deși algoritmul simplex este adesea eficient în practică, nu este un algoritm polinomial: în realitate, este exponențial în cel mai rău caz. Klee și Minty (1972) au construit într-adevăr o problemă, în care mulțimea admisibilă este un „cub” ușor deformat, pentru care algoritmul simplex vizitează cele 2 n vârfuri ale mulțimii admisibile. Este faptul de a lua o decizie la fiecare iterație din informațiile locale ( costul redus de exemplu), având efecte globale (numărul de iterații depinde de numărul de vârfuri vizitate înainte de a ajunge la o soluție), ceea ce nu permite obținerea polinomialitatea algoritmului. Acest exemplu este legat de o anumită regulă pivot, dar există variații ale exemplului Klee și Minty pentru majoritatea regulilor pivot, a se vedea Terlaky și Zhang (1993). Nu știm astăzi (2011) dacă există o regulă pivotantă care să permită polinomialitatea, a se vedea De Loera (2011). Acest contraexemplu a stimulat căutarea algoritmilor care pot fi polinomiali în optimizarea liniară, o problemă considerată suficient de simplă pentru a admite un astfel de algoritm. Acest lucru a condus la algoritmii punctelor interioare , care au fost apoi extinse la toate problemele de optimizare (posibil neconvexe).
Eficiența adesea observată a algoritmului simplex este justificată astăzi de faptul demonstrat al polinomialității sale în medie , pentru date distribuite aleatoriu în conformitate cu diferite legi de probabilitate; vezi Borgwardt (1982, 1987), Smale (1983), Megiddo (1987), Sharmir (1987).
Primul algoritm polinomial pentru OL a fost propus de Leonid Khatchian în 1979 . Se bazează pe metoda elipsoidă în optimizarea neliniară propusă anterior de Naum Z. Shor . Această metodă este în sine o generalizare a metodei elipsoidelor în optimizarea convexă datorită lui Arkadi Nemirovski ( Premiul John von Neumann 2003 ), și a lui David B. Yudin . Eficiența practică a algoritmului Khachiyan este dezamăgitoare: algoritmul simplex este aproape întotdeauna mai rapid. Cu toate acestea, acest rezultat a încurajat cercetarea metodelor de cusătură interioară .
În 1984 , Narendra Karmarkar a propus metoda proiectivă . Este primul algoritm eficient atât în teorie, cât și în practică. Complexitatea sa în cel mai rău caz este polinomul și experimentele pe probleme practice arată că metoda poate fi comparată în mod rezonabil cu algoritmul simplex.
De atunci, au fost propuse și studiate mai multe metode de punct interior . Spre deosebire de algoritmul simplex ale cărui iterații sunt vârfurile poliedrului convex definite de constrângeri, deci aparținând graniței acestui poliedru, metodele punctelor interioare (în versiunea lor admisibilă ) generează iterații în interiorul relativ al setului admisibil. Una dintre metodele cele mai frecvent implementate este algoritmul predictor-corector .
Următorul tabel oferă câteva elemente de comparație între algoritmul simplex primar și algoritmii punctelor interioare cele mai frecvent utilizate, cele care generează iterații urmând o cale centrală.
Simplex | Puncte de interior | |
---|---|---|
Autor-inițiator | Danzig (în jurul anului 1947) | Karmarkar (1984) |
Concept de bază | vârf al unui poliedru convex | cale centrală |
Repetare | de la un vârf la altul urmând o margine | dintr-un cartier dintr-un punct central în altul printr-un pas Newton |
Tipul convergenței | terminat | infinit |
Polinomialitatea | probabil nepolinom, polinom în medie | polinom: convergență până la ε > 0 în iterații O ( n 1/2 log ε −1 ) |
Scopul principal al acestui tabel este de a oferi principalele tendințe ale celor două abordări algoritmice. Cu siguranță îi lipsește nuanța și precizia. Vom consulta articolele de specialitate pe acești algoritmi pentru mai multe informații.
În cazul unui număr mare de variabile și constrângeri, rezoluția poate dura mult timp. În anumite cazuri, se poate accelera rezoluția fără a lua în considerare toate datele de la început (de exemplu, luând în considerare doar un subset de constrângeri) sau profitând de o anumită formă a problemei. asta fac următoarele metode:
Optimizarea liniară se aplică în principal pentru rezolvarea problemelor de optimizare pe termen mediu și lung (probleme strategice și tactice, în vocabularul cercetării operaționale). Domeniile de aplicare a acestor probleme sunt foarte numeroase atât prin natura problemelor abordate ( planificarea și controlul producției, distribuția în rețele ), cât și în sectoarele industriei: industria prelucrătoare, energia ( petrol , gaze , electricitate , nuclear ), transport (aerian, rutier și feroviar), telecomunicații , industria forestieră, finanțe .