Cercetare operativă

Cercetarea operațională (cunoscută și sub numele de teoria deciziei , știința managementului sau, în limba engleză , cercetarea operațională („ Cercetarea operațională ” în Europa ) și indicată prin abrevierile RO sau OR ) este ramura matematicii aplicate în care sunt analizate probleme complexe de luare a deciziilor și rezolvate prin intermediul unor modele matematice și metode cantitative avansate ( optimizare , simulare etc.) ca suport pentru deciziile în sine. Cercetarea operațională joacă un rol important în activitățile de luare a deciziilor, deoarece vă permite să faceți cele mai bune alegeri pentru a atinge un obiectiv specific, respectând în același timp constrângerile impuse din exterior și care nu sunt sub controlul celor care trebuie să ia decizii.

Prin urmare, scopul este de a oferi sprijin pentru luarea deciziilor. Pentru a realiza acest lucru, cercetarea operațională oferă instrumente matematice pentru a sprijini activitățile de luare a deciziilor în care activitățile și resursele limitate trebuie gestionate și coordonate pentru a maximiza sau minimiza o funcție obiectivă.

Prin urmare, cercetarea operațională se referă la formalizarea unei probleme într-un model matematic și la calcularea unei soluții optime, atunci când este posibil, sau aproximativă (numită și suboptimă) pentru aceasta. Constituie o abordare științifică pentru rezolvarea problemelor complexe, poate fi urmărită până la domeniul matematicii aplicate, dar are caracteristici interdisciplinare puternice legate în principal de matematică , informatică , economie și finanțe, inginerie și altele. Mai mult, cercetarea operațională are numeroase aplicații comerciale, în special în domeniile economic, infrastructură, logistică, militară, de servicii și de sisteme de transport și tehnologie. În cazul particular al problemelor economice, funcția care trebuie maximizată poate coincide cu profitul maxim obținut sau cu cel mai mic cost care trebuie suportat.

Istorie

Nașterea cercetării operaționale se datorează nevoilor militare din timpul celui de- al doilea război mondial ^[1] .

Imediat înainte și în timpul războiului, în unele țări aliate au apărut grupuri de cercetare care vizau rezolvarea unor probleme strategice și tactice importante legate de apărarea națională.

Între 1935 și 1937 Regatul Unit a lucrat la proiectul radar ca apărare antiaeriană, dar era totuși important ca localizarea și interceptarea ulterioară și revenirea la sol a aeronavelor britanice să fie eficiente. Prin urmare, a părut esențial în primul rând optimizarea distribuției echipamentelor radar pe teritoriu și, în plus, că semnalizarea a fost trimisă prin radio în locațiile corespunzătoare, s-a născut „ Experimentul Biggin Hill ”. Rowe , superintendentul „ Bawdsey Research Station ”, a folosit termenul de „cercetare operațională” în 1938 într-un raport tehnic final al proiectului pentru a descrie tipul de activitate desfășurată.

În 1939 , Blackett a fost chemat să formeze un grup de cercetare, format din oameni de știință și personal militar, angajat în lupta împotriva submarinelor germane. Succesul obținut de acest grup, care a trecut în istorie, a produs rezultatul multiplicării grupurilor de cercetare cu caracteristici similare în Regatul Unit și alte țări aliate. Se estimează că, în cursul celui de-al doilea război mondial, în Marea Britanie, Canada și SUA au fost implicați în total peste 700 de oameni de știință; sfârșitul conflictului a determinat, așadar, o „reconversie” a abordării, folosită până atunci doar în scopuri de război, orientându-l spre problemele civile (cum ar fi amplasarea zăcămintelor industriale, amestecarea încărcăturii unui serviciu de transport rutier).

În sectoarele mai strict civile, cercetarea operațională a preluat tehnici cunoscute în sectorul industrial, îmbunătățindu-le și îmbogățindu-le cu utilizarea instrumentelor matematice și a cunoștințelor organizaționale: s-a ocupat de standardizarea producției, problemele legate de planificarea și programarea industrială. În Regatul Unit, transformarea a avut loc în principal în sectorul public, cu studii referitoare la transportul feroviar , rutier și urban.

Răspândirea cercetării operaționale în Italia a fost mai ales datorită lui Giuseppe Pompilj care, în a doua jumătate a anilor 1950, a colaborat cu Marina , în legătură cu Forțele Armate SUA. Pompilj , în 1961 , a fost și unul dintre fondatorii AIRO ( Asociația Italiană de Cercetare Operațională ), printre care trebuie să-l amintim și pe Benedetto Barberi , pe atunci director al Institutului Național de Statistică și Bruno de Finetti și în 1962 a înființat Școala Avansată în cercetare operațională la Universitatea din Roma.

Prima problemă de optimizare este conținută în legenda întemeierii vechii Cartagini de către Dido, relatată în prima carte a Eneidei.

În 880 î.Hr. regina feniciană Dido, care a fugit din Tir împreună cu câțiva credincioși, a aterizat pe coastele nordice ale Africii. Aici l-a rugat pe Iarba, regele Getuli, un teren pe care să construiască un nou oraș. Regele, ca răspuns, i-a oferit o piele de taur, spunându-i că ar putea să-și însușească cât de mult teren ar putea să înțeleagă cu acea piele („cât de mult piele de taur ar putea o parte din spate”).

Înțeleptul Dido a acceptat provocarea. A avut pielea tăiată în multe fâșii subțiri și a obținut o frânghie cu care a putut delimita o zonă mare, în formă de semicerc, cu vedere la mare. S-a calculat că în acest fel s-ar putea include probabil un semicerc echivalent prin extensie la 15 terenuri de fotbal.

Descriere

Scopuri și metode

Cercetarea operațională constă în aplicarea unei metode științifice, de către grupuri interdisciplinare, la probleme care indică controlul sistemelor organizate pentru a oferi soluții care servesc cel mai bine scopurilor organizației în ansamblu. Nu înlocuiește factorii de decizie, dar, oferind soluții la problemele obținute prin metode științifice, permite să se facă alegeri raționale. Poate fi folosit în programarea liniară (planificarea problemelor); în planificarea dinamică (planificarea vânzărilor); în programarea rețelei (management de proiect); în teoria cozilor (pentru gestionarea problemelor de trafic); în teoria inventarului (depozitarea depozitului); în teoria graficelor (utilizată de exemplu pentru rețelele de telecomunicații ); în teoria jocurilor (probleme de decizie în condiții competitive).

Etape

Procesarea problemelor este împărțită în etape obligatorii, și anume:

examinarea situației reale și colectarea informațiilor (în companii sursa informației este contabilitatea industrială );
formularea problemei: identificarea variabilelor controlabile și necontrolabile; alegerea funcției economice de optimizat (maximizat sau minimizat);
construirea modelului matematic, care își propune să ofere o bună reprezentare a problemei; trebuie să fie simplu de utilizat; să reprezinte problema, oferind toate informațiile pentru a putea lua o decizie cât mai adecvată posibil;
soluția modelului (folosind diferite metode);
analiza și verificarea soluțiilor obținute: se verifică dacă funcția teoretică oferă avantaje așteptate și se verifică reprezentativitatea modelului;
aplicarea soluției.

Modele teoretice și sisteme reale

Scopul unui model este întotdeauna să reprezinte un sistem real, deci modelele sunt reprezentări simple ale realității și sunt adesea pur și simplu descriptive ale acesteia; aceste tipuri de modele sunt numite iconice sau, ca în așa-numita topologie , „analogice” [1] . Pe de altă parte, atunci când modelul este de natură „rezolutivă”, așa cum se întâmplă în așa-numitele „probleme de decizie”, care sunt de obicei la baza problemelor de cercetare operațională, așa-numitele „ modele simbolice ” sunt utilizate, care sunt mai abstracte și sunt exprimate cu relații matematice între variabile și cantitățile care urmează să fie optimizate, din acest motiv sunt definite în mod normal ca „ modele matematice ”. În acest caz, cea mai mare dificultate, care este și valoarea modelului, constă în selectarea variabilelor relevante, cu excepția celor considerate secundare. De fapt, în analiza finală, modelul este întotdeauna o simplificare a realității, care este influențată de un număr atât de mare de variabile încât să facă imposibilă identificarea unei soluții optime. Cu toate acestea, trebuie amintit întotdeauna că ultima fază a cercetării operaționale, adică implementarea soluției, este de obicei dincolo de îndemâna expertului în cercetarea operațională, care se limitează să comunice rezultatul cercetării sale clientului (antreprenor sau instituțional). administrator). Acest lucru nu scade valabilitatea acestei metode pentru abordarea și rezolvarea chiar și a așa-numitelor probleme „banale”, adică a alegerii individuale de tot felul: cumpărături, organizarea timpului liber sau a muncii, finanțe personale .

Clasificare

Cercetarea operațională este împărțită în numeroase subramuri. Prima și cea mai importantă clasificare face distincție între:

optimizare (numită și abordarea ce este cea mai bună ); care se ocupă cu formalizarea problemei într-un model matematic (de obicei un model de programare matematică sau o diagramă de flux ) și identificarea unei soluții optime sau suboptimale pentru aceasta.
simulare (numită și abordare what-if ); care se ocupă de probleme „dificile” de rezolvat pentru optimitate, deseori NP dificile . Aceste tehnici implică formalizarea problemei într-un model matematic și determinarea parametrilor „buni” folosind metode statistice sau teoretice de joc .
procese stochastice care se ocupă cu crearea de modele probabilistice pentru a determina comportamentul sistemelor. Această ramură pare a fi baza ingineriei financiare și a optimizării stochastice.

Optimizare

Același subiect în detaliu: Optimizare (matematică) .

Optimizarea se ocupă de probleme care pot fi formalizate ca minimizare sau maximizare a unei funcții (numită funcție obiectivă ) supusă unor constrângeri. O problemă de minimizare poate fi întotdeauna urmărită înapoi la o problemă de maximizare și invers.

Cel mai simplu caz constă în reducerea la minimum a unei funcții diferențiabile fără constrângeri; pentru rezolvarea acestor probleme se folosesc tehnicile de analiză diferențială . În mod tipic, însă, celelalte cazuri sunt atribuite unui model de programare matematică, a cărui formă generică este:

$\max C(x_{1},\dots ,x_{n})$ ${\ displaystyle \ max C (x_ {1}, \ dots, x_ {n})}$ $\ max C (x_1, \ dots, x_n)$	(funcție obiectivă)
$\varphi _{1}(x_{1},\dots ,x_{n})\leq b_{1}$ ${\ displaystyle \ varphi _ {1} (x_ {1}, \ dots, x_ {n}) \ leq b_ {1}}$ $\ varphi_1 (x_1, \ dots, x_n) \ leq b_1$
$\dots$ ${\ displaystyle \ dots}$ $\ dots$	(constrângeri)
$\varphi _{m}(x_{1},\dots ,x_{n})\leq b_{m}$ ${\ displaystyle \ varphi _ {m} (x_ {1}, \ dots, x_ {n}) \ leq b_ {m}}$ $\ varphi_m (x_1, \ dots, x_n) \ leq b_m$

ceea ce reprezintă o problemă cu n variabile și m constrângeri. Constrângerile și ținta sunt funcții reale cu variabile vectoriale și pot reprezenta, de asemenea, constrângeri asupra valorii variabilelor (de exemplu, non-negativitate sau integralitate). Constrângerile și obiectivul pot fi liniare, caz în care vorbim de programare liniară sau PL, iar modelul generic devine:

$\max \sum _{i=1}^{n}c_{i}x_{i}$ ${\ displaystyle \ max \ sum _ {i = 1} ^ {n} c_ {i} x_ {i}}$ $\ max \ sum_ {i = 1} ^ n c_i x_i$	(funcție obiectivă)
$\sum _{i=1}^{n}a_{1,i}x_{i}\leq b_{1}$ ${\ displaystyle \ sum _ {i = 1} ^ {n} a_ {1, i} x_ {i} \ leq b_ {1}}$ $\ sum_ {i = 1} ^ n a_ {1, i} x_i \ leq b_1$
$\dots$ ${\ displaystyle \ dots}$ $\ dots$	(constrângeri)
$\sum _{i=1}^{n}a_{m,i}x_{i}\leq b_{m}$ ${\ displaystyle \ sum _ {i = 1} ^ {n} a_ {m, i} x_ {i} \ leq b_ {m}}$ $\ sum_ {i = 1} ^ n a_ {m, i} x_i \ leq b_m$

Cu toate acestea, adesea în aplicații variabilele sunt constrânse să-și asume valori binare (caz în care vorbim de programare-0,1 ) sau întregi ( programare liniară întreagă sau PLI). În aceste cazuri, problema poate deveni complicată și soluția nu poate fi generică, dar este necesar să se studieze problema specifică și utilizarea anumitor tehnici de soluționare, cum ar fi algoritmi Branch and bound sau Branch and Cut . În alte aplicații, pot apărea funcții obiective sau constrângeri neliniare; dacă acestea sunt pătratice vorbim de programare pătratică sau optimizare pătratică, altfel vorbim generic de optimizare neliniară; ambele cazuri prezintă probleme de „soluție dificilă” și există tehnici specifice (cum ar fi metoda gradientului ).

Dualitate

Același subiect în detaliu: Problema primară standard § Algebra LP .

Conceptul de dualitate are o importanță fundamentală în teoria optimizării. În acest fel, este posibilă și definirea condițiilor de optimitate.

Dualitatea în cercetarea operațională poate fi interpretată ca o corespondență între două probleme formalizate într-un model de programare liniară. De obicei, o pereche de probleme duale are aceeași valoare optimă a funcției obiective ( dualitate puternică ) sau valoarea optimă a unei probleme reprezintă o limitare a celeilalte. Cea mai importantă și cea mai cunoscută formă de dualitate este cea care asociază două probleme de programare liniară ( dualitatea liniară ); totuși există și alte tipuri de dualitate, de exemplu în prezența problemelor de programare pătratică vorbim de dualitate pătratică și în prezența unor probleme de programare liniară întregi vorbim de dualitate lagrangiană .

O pereche tipică de probleme duale liniare este următoarea:

Problemă primară standard	Problemă dublă standard
$\max \sum _{i=1}^{n}c_{i}x_{i}$ ${\ displaystyle \ max \ sum _ {i = 1} ^ {n} c_ {i} x_ {i}}$ $\ max \ sum_ {i = 1} ^ n c_i x_i$	$\min \sum _{j=1}^{m}y_{j}b_{j}$ ${\ displaystyle \ min \ sum _ {j = 1} ^ {m} y_ {j} b_ {j}}$ $\ min \ sum_ {j = 1} ^ m y_j b_j$	(funcție obiectivă)
$\sum _{i=1}^{n}a_{1,i}x_{i}\leq b_{1}$ ${\ displaystyle \ sum _ {i = 1} ^ {n} a_ {1, i} x_ {i} \ leq b_ {1}}$ $\ sum_ {i = 1} ^ n a_ {1, i} x_i \ leq b_1$	$\sum _{j=1}^{m}y_{j}a_{j,1}=c_{1}$ ${\ displaystyle \ sum _ {j = 1} ^ {m} y_ {j} a_ {j, 1} = c_ {1}}$ $\ sum_ {j = 1} ^ m y_j a_ {j, 1} = c_1$
$\dots$ ${\ displaystyle \ dots}$ $\ dots$	$\dots$ ${\ displaystyle \ dots}$ $\ dots$	(constrângeri)
$\sum _{i=1}^{n}a_{m,i}x_{i}\leq b_{m}$ ${\ displaystyle \ sum _ {i = 1} ^ {n} a_ {m, i} x_ {i} \ leq b_ {m}}$ $\ sum_ {i = 1} ^ n a_ {m, i} x_i \ leq b_m$	$\sum _{j=1}^{m}y_{j}a_{j,n}=c_{n}$ ${\ displaystyle \ sum _ {j = 1} ^ {m} y_ {j} a_ {j, n} = c_ {n}}$ $\ sum_ {j = 1} ^ m y_j a_ {j, n} = c_n$
	$y_{j}\geq 0\qquad j=1,\dots ,m$ ${\ displaystyle y_ {j} \ geq 0 \ qquad j = 1, \ dots, m}$ $y_j \ geq 0 \ qquad j = 1, \ dots, m$

În realitate, o problemă primară poate avea formulări diferite și pentru fiecare dintre ele există o formulare duală diferită, care este, de asemenea, echivalentă cu celelalte formulări duale. Cu toate acestea, orice problemă de programare liniară poate fi urmărită înapoi la această pereche.

Problemele duale liniare au proprietăți importante:

dualul dualului este primal , adică prin readucerea problemei duale la forma primară și aplicarea corespondenței de mai sus, se va obține o formulare echivalentă a problemei primare.
valorile obiective , valorile optime ale funcțiilor obiective ale celor două probleme de mai sus coincid
optimitate , în programarea liniară există o modalitate de a calcula, dată fiind o soluție (chiar dacă nu optimă) a problemei primare, soluția duală corespunzătoare. Această proprietate este utilizată ca procedură de decizie pentru optimitatea celor două soluții: dacă valorile corespunzătoare ale funcției obiective coincid, soluția este optimă.

Algoritmul simplex exploatează pe deplin aceste proprietăți și același algoritm, implicit aplicat la problema duală, este numit algoritmul dual simplex.

Aspecte geometrice ale programării matematice

Deși formulările introduse anterior sunt intuitive și „apropiate” de elementele domeniului problemei care urmează să fie modelate, este de multe ori preferat să se dea o formulare geometrică și o interpretare a problemelor și a teoriei programării matematice.

În acest caz, problema este formulată ca minimizarea sau maximizarea unei funcții (adică funcția obiectivă ) într-un set numit regiune fezabilă . Prin urmare, cazul programării liniare devine minimizarea unei funcții liniare într-o regiune poliedrică , adică definită de o matrice de constrângeri liniare:

${\mathcal {P}}=\{x\in \mathbb {R} ^{n}:Ax\leq b\}$ ${\ displaystyle {\ mathcal {P}} = \ {x \ in \ mathbb {R} ^ {n}: Ax \ leq b \}}$ $\ mathcal {P} = \ {x \ in \ mathbb {R} ^ n: Ax \ leq b \}$ .

În acest caz, sistemul matricial care definește poliedrul este constituit exact de constrângerile problemei de programare liniară. Prin urmare, o problemă de programare liniară poate fi exprimată ca:

${\begin{array}{l}\max \langle c,x\rangle \\{\begin{cases}Ax\leq b\\x\geq 0\end{cases}}\end{array}}$ ${\ displaystyle {\ begin {array} {l} \ max \ langle c, x \ rangle \\ {\ begin {cases} Ax \ leq b \\ x \ geq 0 \ end {cases}} \ end {array} }}$ $\ begin {array} {l} \ max \ langle c, x \ rangle \\ \ begin {cases} Ax \ leq b \\ x \ geq 0 \ end {cases} \ end {array}$

Acest tip de formulare este important atât în contextul programării liniare întregi, cât și al tuturor programărilor matematice, deoarece permite studierea bine a proprietăților unei probleme și definirea unor aspecte ale programării liniare într-un mod simplu și elegant. De exemplu, este posibil să se definească condiția de optimitate a unei soluții în termeni geometrici. Fiecare rând al unei matrice identifică o constrângere, tocmai un hiperplan care definește o jumătate de spațiu cu care indicăm $A_{i}$ ${\ displaystyle A_ {i}}$ $Către}$ . Sa spunem $I(x)$ ${\ displaystyle I (x)}$ $Eu (x)$ setul de constrângeri active ale unei soluții, adică:

$I(x)=\{i\,:\,A_{i}x=b_{i}\}.$ ${\ displaystyle I (x) = \ {i \ ,: \, A_ {i} x = b_ {i} \}.}$ $I (x) = \ {i \ ,: \, A_i x = b_i \}.$

Prin urmare, o soluție se poate spune că este optimă dacă și numai dacă vectorul de cost aparține conului convex generat de constrângerile active, adică:

$x^{*}\leq x\quad \forall x\in S\Leftrightarrow c\in {\mbox{Cono}}(A_{I(x^{*})})\Leftrightarrow c=\sum _{i\in I(x^{*})}\lambda _{i}A_{i},\quad \lambda _{i}\geq 0\,\forall i\in I(x^{*})$ ${\ displaystyle x ^ {*} \ leq x \ quad \ forall x \ in S \ Leftrightarrow c \ in {\ mbox {Cone}} (A_ {I (x ^ {*})}) \ Leftrightarrow c = \ sum _ {i \ in I (x ^ {*})} \ lambda _ {i} A_ {i}, \ quad \ lambda _ {i} \ geq 0 \, \ forall i \ in I (x ^ {*} )}}$ $x ^ * \ leq x \ quad \ forall x \ in S \ Leftrightarrow c \ in \ mbox {Cone} (A_ {I (x ^ *)}) \ Leftrightarrow c = \ sum_ {i \ in I (x ^ * )} \ lambda_i A_i, \ quad \ lambda_i \ geq 0 \, \ forall i \ in I (x ^ *)$ .

În plus, această condiție poate fi generalizată pentru a înțelege cazul neliniar. De fapt, vectorul de cost nu este altul decât gradientul funcției obiective (constant deoarece funcția este liniară), iar conul constrângerilor active este așa-numitul con normal definit pe orice set.

Programare liniară întregi

O problemă de programare liniară întreagă (indicată prin acronimul PLI ) este o problemă de programare liniară în care variabilele sunt constrânse să își asume valori întregi. Un caz particular, foarte frecvent, este așa - numita programare 0,1 sau programare binară , în care variabilele sunt obligate să-și asume valori binare. În general, problemele de programare liniară întregi sunt NP-Ardui , cu excepția cazului în care au proprietatea integralității (vezi mai jos). Aceasta înseamnă că (cu excepția cazului în care P = NP deține), multe probleme ILP necesită, în cel mai rău caz, un timp de calcul al soluției exponențiale cu privire la dimensiunea datelor de intrare. În practică, acestea sunt probleme „greu” de rezolvat. Cu toate acestea, unele dintre aceste probleme, utilizate în mod obișnuit în aplicații, au fost studiate temeinic și astăzi există tehnici care permit rezolvarea acestora într-un timp rezonabil în cele mai frecvente aplicații. În mod obișnuit, atunci, se încearcă reducerea soluției unei probleme ILP „dificile” la cea simplă sau una care a fost deja studiată (a se vedea relaxările și euristica ); în acest fel este posibil să abordăm o mare varietate de probleme.

Forma generică a unei probleme de programare liniară întreagă este:

{\begin{array}{l}\max \langle c,x\rangle \\{\begin{cases}Ax\leq b\\x\in \mathbb {Z} ^{n}\end{cases}}\end{array}}

{\ displaystyle {\ begin {array} {l} \ max \ langle c, x \ rangle \\ {\ begin {cases} Ax \ leq b \\ x \ in \ mathbb {Z} ^ {n} \ end { cazuri}} \ end {array}}}

\ begin {array} {l} \ max \ langle c, x \ rangle \\ \ begin {cases} A x \ leq b \\ x \ in \ mathbb Z ^ n \ end {cases} \ end {array}

Proprietăți de integritate

Când constrângerile sunt eliminate într-o problemă ILP $x\in \mathbb {Z} ^{n}$ ${\ displaystyle x \ in \ mathbb {Z} ^ {n}}$ $x \ in \ mathbb {Z} ^ n$ obținem o problemă de programare liniară numită relaxare continuă . Mai mult, dacă se întâmplă ca soluțiile optime ale problemei originale să fie și soluții optime ale relaxării sale continue, se spune că problema are proprietatea integralității .

Într-adevăr, proprietatea integralității privește mai degrabă setul fezabil al problemei decât problema în sine. De fapt, funcția obiectivă a relaxării continue are aceeași valoare ca cea a problemei originale pe setul său fezabil și, mai mult, deoarece este o problemă de programare liniară, are întotdeauna o soluție optimă de vârf. Prin urmare, rezultă că o problemă are proprietatea integralității dacă regiunea fezabilă a relaxării sale continue este „strânsă” de setul fezabil original; adică, în termeni geometrici, dacă coincide cu plicul său convex.

Prin urmare, în mod formal, definim setul fezabil al problemei inițiale ca:

X=\{x\in \mathbb {Z} ^{n}:Ax\leq b\}

{\ displaystyle X = \ {x \ in \ mathbb {Z} ^ {n}: Ax \ leq b \}}

X = \ {x \ in \ mathbb {Z} ^ n: A x \ leq b \}

;

și plicul său convex ca:

Conv(X)=\{y\in \mathbb {R} ^{n}:y=\sum _{i=1}^{n}\lambda _{i}x_{i},x_{i}\in X,\sum _{i=1}^{n}\lambda _{i}=1\}

{\ displaystyle Conv (X) = \ {y \ in \ mathbb {R} ^ {n}: y = \ sum _ {i = 1} ^ {n} \ lambda _ {i} x_ {i}, x_ { i} \ în X, \ sum _ {i = 1} ^ {n} \ lambda _ {i} = 1 \}}

Conv (X) = \ {y \ in \ mathbb {R} ^ n: y = \ sum_ {i = 1} ^ n \ lambda_i x_i, x_i \ in X, \ sum_ {i = 1} ^ n \ lambda_i = 1 \}

.

Prin urmare, problema are proprietatea integralității dacă are:

\{x\in \mathbb {R} ^{n}:Ax\leq b\}=Conv(X)

{\ displaystyle \ {x \ in \ mathbb {R} ^ {n}: Ax \ leq b \} = Conv (X)}

\ {x \ in \ mathbb {R} ^ n: A x \ leq b \} = Conv (X)

.

Regiune admisibilă cu proprietăți de integritate

De exemplu, reprezentarea grafică a regiunii fezabile a unei probleme cu două variabile caracterizată prin constrângeri este prezentată în imaginea de mai jos:

\left\{{\begin{array}{l}x_{1}+x_{2}\leq 3\\x_{1}\leq 2\\x_{2}\leq 2\\-x_{1}\leq 0\\-x_{2}\leq 0\\x_{1},x_{2}\in \mathbb {N} \end{array}}\right.

{\ displaystyle \ left \ {{\ begin {array} {l} x_ {1} + x_ {2} \ leq 3 \\ x_ {1} \ leq 2 \\ x_ {2} \ leq 2 \\ - x_ {1} \ leq 0 \\ - x_ {2} \ leq 0 \\ x_ {1}, x_ {2} \ in \ mathbb {N} \ end {array}} \ right.}

\ left \ {\ begin {array} {l} x_1 + x_2 \ leq 3 \\ x_1 \ leq 2 \\ x_2 \ leq 2 \\ - x_1 \ leq 0 \\ - x_2 \ leq 0 \\ x_1, x_2 \ în \ mathbb {N} \ end {array} \ right.

Setul fezabil original este indicat cu puncte negre, iar plicul său convex este reprezentat în gri. După cum se poate vedea, regiunea definită de constrângerile de mai sus coincide exact cu anvelopa convexă a problemei inițiale.

Proprietatea integralității este extrem de importantă, deoarece ne permite să aplicăm metodele simple și relativ rapide pentru rezolvarea unei probleme de programare liniară la o problemă de programare liniară întreagă. Cu alte cuvinte, în fața unei probleme ILP care are proprietatea integralității, este posibil să se rezolve relaxarea sa continuă și să se obțină o soluție optimă pentru aceasta. Multe probleme ITP care se bucură de proprietatea integralității sunt bine cunoscute și utilizate pe scară largă. De exemplu, putem cita problema fluxului de cost minim (sau fluxul de cost minim , MCF ) și debitul maxim pe un grafic de flux și problema de cuplare a costului minim.

Relaxări și euristici

După cum sa menționat deja, rezolvarea unei probleme de programare liniară întreagă poate fi adesea „dificilă”; în aceste cazuri este posibil să se obțină limitări superioare și inferioare ale valorii optime a funcției obiective. Acest lucru este foarte important atât pentru că uneori aplicațiile sunt preocupate de valoarea optimă a funcției obiective, mai degrabă decât de soluția optimă a problemei, și pentru că cunoașterea acestei valori este esențială pentru utilizarea algoritmilor de enumerare implicită, cum ar fi algoritmii Branch și Bound .

Să luăm deci în considerare o problemă de maximizare în programarea liniară întreagă, menționând că cazul de minimizare este absolut echivalent.

{\begin{array}{l}\max \langle c,x\rangle \\{\begin{cases}Ax\leq b\\x\in \mathbb {Z} ^{n}\end{cases}}\end{array}}

{\ displaystyle {\ begin {array} {l} \ max \ langle c, x \ rangle \\ {\ begin {cases} Ax \ leq b \\ x \ in \ mathbb {Z} ^ {n} \ end { cazuri}} \ end {array}}}

\ begin {array} {l} \ max \ langle c, x \ rangle \\ \ begin {cases} A x \ leq b \\ x \ in \ mathbb Z ^ n \ end {cases} \ end {array}

Pornind de la această problemă generică, este posibil să se construiască una sau mai multe probleme numite relaxări care oferă o limitare superioară a valorii optime a funcției obiective. Cu alte cuvinte, valoarea optimă a unei relaxări este mai mare sau egală cu valoarea optimă a problemei inițiale; în mod evident, acest lucru este util dacă relaxarea este mai ușor de rezolvat decât problema inițială. Rețineți că, dacă am avea o problemă de minimizare, relaxările ar oferi o limitare mai mică a valorii optime a problemei inițiale, deoarece relaxările calculează aproape întotdeauna o soluție inadmisibilă pentru problema inițială și unde soluția optimă a unei relaxări a fost, de asemenea, admisibilă pentru problema originală ar fi, de asemenea, excelentă.

În general, o problemă de programare matematică (P ^' ) este o relaxare a lui (P) dacă și numai dacă regiunea sa fezabilă conține cea a lui (P) și pe intersecția lor valorile funcțiilor obiective coincid. În programarea liniară întreagă există diferite tipuri de relaxări.

Relaxare continuă : se obține prin înlocuirea constrângerilor de integritate ale variabilelor cu constrângeri simple de non-negativitate sau prin eliminarea acestora în totalitate în funcție de structura problemei; o relaxare continuă poate fi rezolvată cu ușurință cu tehnicile de soluționare a programării liniare, în plus dacă problema originală are proprietatea integralității este suficientă rezolvarea problemei.
Relaxarea prin eliminarea constrângerilor : Structura problemei este studiată și sunt identificate constrângerile complicate, adică constrângerile fără de care problema este ușor de rezolvat și sunt eliminate. Rețineți că problema astfel obținută nu este neapărat polinomială, ci poate fi o problemă NP-Arduous a cărei structură este bine cunoscută și care poate fi abordată, de exemplu o problemă cu rucsacul .
Relaxare surogat : se studiază structura problemei și se adaugă o constrângere redundantă obținută prin înmulțirea unor constrângeri (numite surogate) cu coeficienți $\pi _{i}$ ${\ displaystyle \ pi _ {i}}$ $\ pi _ {i}$ numiți multiplicatori surogat . Ulterior constrângerile surogate sunt eliminate, obținându-se astfel relaxarea problemei.
Relaxare lagrangiană : Structura problemei este studiată și constrângerile complicate identificate, scriind astfel problema ca

{\begin{array}{l}\max \langle c,x\rangle \\{\begin{cases}Ax\leq b\\Ex\leq d\\x\in \mathbb {Z} ^{n}\end{cases}}\end{array}}

{\ displaystyle {\ begin {array} {l} \ max \ langle c, x \ rangle \\ {\ begin {cases} Ax \ leq b \\ Ex \ leq d \\ x \ in \ mathbb {Z} ^ {n} \ end {cases}} \ end {array}}}

\ begin {array} {l} \ max \ langle c, x \ rangle \\ \ begin {cases} A x \ leq b \\ E x \ leq d \\ x \ in \ mathbb Z ^ n \ end {cases } \ end {array}

unde primele sunt constrângerile complicante, în acest moment constrângerile complicate sunt eliminate, dar se adaugă un termen de penalizare funcției obiective ponderate în conformitate cu un vector de parametri de relaxare numit vectorul multiplicatorilor Lagrangieni . Astfel obținem următoarea problemă indicată cu (P _y ):

{\begin{array}{l}\max(\langle c,x\rangle +\langle y,b-Ax\rangle )=\langle y,b\rangle +\max \langle c-yA,x\rangle \\Ex\leq d\\x\in \mathbb {Z} ^{n}\end{array}}

{\ displaystyle {\ begin {array} {l} \ max (\ langle c, x \ rangle + \ langle y, b-Ax \ rangle) = \ langle y, b \ rangle + \ max \ langle c-yA, x \ rangle \\ Ex \ leq d \\ x \ in \ mathbb {Z} ^ {n} \ end {array}}}

\ begin {array} {l} \ max (\ langle c, x \ rangle + \ langle y, b - A x \ rangle) = \ langle y, b \ rangle + \ max \ langle c - yA, x \ rangle \\ E x \ leq d \\ x \ in \ mathbb Z ^ n \ end {array}

Pentru a obține, în schimb, o limitare mai mică a valorii optime a funcției obiective, se utilizează euristicile ; adică algoritmi care calculează o soluție bună, dar nu neapărat optimă. Tipicamente una buona euristica dovrebbe fornire anche una limitazione teorica dell'errore commesso (lo scarto rispetto alla soluzione ottima), tuttavia non sempre è possibile costruire euristiche supportate da questa proprietà. In qualunque caso le euristiche dipendono strettamente dal problema in esame, pertanto non esiste una tecnica euristica applicabile al problema generico di programmazione lineare intera. Prendono il nome di Euristiche Lagrangiane quelle tecniche ottenute generando una soluzione ammissibile a partire dalla soluzione ottima di un rilassamento Lagrangiano o di un duale Lagragiano .

Dualità Lagrangiana

In presenza di un problema di PLI "difficile" da risolvere spesso si considera un suo rilassamento Lagrangiano (vedi Rilassamenti ed euristiche ) tuttavia di solito interessa calcolare il valore del parametro y che permetta di ottenere il miglior valore obiettivo (ovvero, nel caso in cui il problema originale sia un problema di massimizzazione, il valore di y che minimizza z(P _y ), valore ottimo del problema (P _y )). Formalizzando questo approccio si ottiene il seguente problema:

(LD)\min\{\langle y,b\rangle +\max \langle c-yA,x\rangle :y\geq 0\}

(LD)\min\{\langle y,b\rangle +\max \langle c-yA,x\rangle :y\geq 0\}

(LD) \min \{ \langle y, b \rangle + \max \langle c - yA, x \rangle : y \geq 0\}

.

Il problema (LD) prende il nome di Duale Lagrangiano. Se consideriamo il duale lineare del problema (LD) otteniamo il seguente:

({\tilde {P}})\max\{\langle c,x\rangle :Ax\leq b,x\in Conv(X)\}

({\tilde {P}})\max\{\langle c,x\rangle :Ax\leq b,x\in Conv(X)\}

(\tilde{P}) \max \{ \langle c, x \rangle: Ax \leq b, x \in Conv(X)\}

,

dove $X=\{x\in \mathbb {N} ^{n}:Ex\leq d\}$ $X=\{x\in \mathbb {N} ^{n}:Ex\leq d\}$ $X = \{x \in \mathbb{N}^n: Ex \leq d\}$ .

Questo risultato è di fondamentale importanza perché la risoluzione del problema $({\tilde {P}})$ $({\tilde {P}})$ $(\tilde{P})$ può essere molto difficile, soprattutto a causa della difficoltà nel reperire una descrizione poliedrale di Conv(X). Risolvendo (LD), invece, si ottiene il valore ottimo di $({\tilde {P}})$ $({\tilde {P}})$ $(\tilde{P})$ ed è possibile generare una soluzione ottima x ^* di $({\tilde {P}})$ $({\tilde {P}})$ $(\tilde{P})$ a partire da una soluzione ottima y ^* di (LD).

Sebbene più semplice da risolvere anche il problema (LD) presenta delle difficoltà; infatti non solo la funzione obiettivo non è lineare ma, generalmente, non è nemmeno differenziabile. Tuttavia esistono degli algoritmi studiati a fondo applicabili, tra le altre cose, alla risoluzione di Duali Lagrangiani quali, ad esempio, l'algoritmo dei piani di taglio, gli algoritmi del subgradiente e gli algoritmi Bundle.

Esempi di problemi

Ottimizzazione

Una fabbrica produce n _i prodotti di tipo i , ognuno dei quali genera un profitto p _i e richiede un certo quantitativo di risorse r _i,j . La fabbrica dispone di una quantità limitata per alcune risorse r _j . Alcuni prodotti non possono essere realizzati in una quantità minore di m _i e non superiore a M _i . Si chiede quali prodotti produrre e in che quantità per ottenere il massimo profitto, rispettando tutti i vincoli.

Pianificazione

Immaginando di dover consegnare della merce an destinatari diversi usando m corrieri, sapendo che ognuno dei destinatari è reperibile soltanto in una determinata fascia oraria e che un corriere non può caricare più di l lotti, individuare i percorsi che devono eseguire i corrieri al fine di minimizzare i chilometri percorsi e consegnare tutti i pacchi.

Schedulazione

Si vogliono ordinare gli ordini di lavorazione su una medesima macchina in base alle date di consegna richieste dal cliente tenendo conto dell'eventuale tempo di set-up per incominciare la lavorazione del lotto. Il problema di schedulazione, inquadrato nella teoria della schedulazione , viene risolto ricorrendo alla programmazione lineare : si tratta di trovare la permutazione ottimale delle righe d'ordine in modo da rispettare il più possibile le date di consegna richieste dal cliente e in caso di ritardo, in modo da minimizzare i giorni di ritardo. La sequenza trovata tiene conto anche dei tempi di set-up facendo in modo di lavorare in successione lotti che richiedono lo stesso attrezzaggio.

Note

^ Australian War Memorial, WWII, CHAPTER 8 - BOMBER COMMAND: JUNE 1941 TO FEBRUARY 1942 ( PDF ), su awm.gov.au . URL consultato il 27 giugno 2013 . pag. 177

Bibliografia

( EN ) Aleksei D. Korshunov ed. (1996): Discrete Analysis and Operation Research , Kluwer, ISBN 0-7923-3866-9
( EN ) William Greenberg, Jacek Polewczak (1991): Modern Mathematical Methods in Transport Theory , Birkhäuser, ISBN 3-7643-2571-2
( EN ) Frederick S. Hillier, Gerald J. Lieberman: Introduction to Operations Research , McGraw-Hill Professional, ISBN 0-07-301779-5
Mario Volpato, Studi e modelli di ricerca operativa , Torino, UTET, 1971.
David Carfì, Fondamenti di teoria delle decisioni. Teoria dei preordini e applicazioni , Antipodes, 2012. ISBN 978-88-96926-10-9

Algoritmi

Alcuni degli algoritmi utilizzati in ricerca operativa per la programmazione lineare sono:

Algoritmo del simplesso per risolvere problemi di ottimizzazione lineare.
Algoritmo della barriera logaritmica per risolvere i problemi di ottimizzazione convessa.

Alcuni degli algoritmi utilizzati in ricerca operativa per la teoria dei grafi sono:

Algoritmo di Prim o algoritmo di Kruskal per individuare il minimum spanning tree di un grafo .
Algoritmo di Dijkstra per individuare il cammino più breve tra due nodi di un grafo pesato con pesi non negativi.
Algoritmo di Bellman-Ford per individuare il cammino più breve tra due nodi di un grafo pesato; meno efficiente del precedente, ma funzionante anche con pesi negativi.
Algoritmo di Ford-Fulkerson per individuare il flusso massimo passante tra due punti di una rete.
Problema di assegnazione .

Voci correlate

Altri progetti

Wikimedia Commons contiene immagini o altri file su ricerca operativa

Collegamenti esterni

( EN )Ricerca operativa , su Enciclopedia Britannica , Encyclopædia Britannica, Inc.
Associazione italiana di ricerca operativa , su airo.org .
Associazione europea delle società di ricerca operativa , su euro-online.org .
( EN ) Associazione internazionale delle società di ricerca operativa , su ifors.org .
( EN ) Associazione americana di Ricerca Operativa e Management Science , su informs.org .
Appunti di ricerca operativa a cura dell'Università di Trieste , su univ.trieste.it . URL consultato il 29 giugno 2006 (archiviato dall' url originale il 20 marzo 2007) .
Appunti di ricerca operativa a cura dell'Università di Pisa, facoltà d'informatica , su di.unipi.it .

Controllo di autorità	Thesaurus BNCF 7400 · LCCN ( EN ) sh85095020 · GND ( DE ) 4043586-6 · BNF ( FR ) cb11941329g (data)

Portale Matematica : accedi alle voci di Wikipedia che trattano di matematica

[1] Australian War Memorial, WWII, CHAPTER 8 - BOMBER COMMAND: JUNE 1941 TO FEBRUARY 1942 ( PDF ), su awm.gov.au . URL consultato il 27 giugno 2013 . pag. 177

[1]