Problemă primară standard

O problemă în formă primară standard este o problemă matematică tipică teoriei programării liniare , o problemă în care vrem să maximizăm valoarea unei anumite funcții respectând în același timp constrângeri suplimentare exprimate sub formă de inegalități liniare.

Această schematizare pentru o problemă de optimizare este utilizată pe scară largă, deoarece există o versiune a algoritmului simplex care se aplică unei probleme de acest tip pentru a găsi o soluție optimă. Ansamblul spațiului soluțiilor posibile ale problemei ( domeniului ) se numește poliedru primar ( politop ), în timp ce funcția care este maximizată se numește „ funcție obiectivă ”.

Scrierea cu care este obișnuit să se reprezinte o problemă în format primar este

\left(P\right):{\begin{cases}\max \quad c^{T}x\\Ax\leq \ b\end{cases}}

{\ displaystyle \ left (P \ right): {\ begin {cases} \ max \ quad c ^ {T} x \\ Ax \ leq \ b \ end {cases}}}

{\ displaystyle \ left (P \ right): {\ begin {cases} \ max \ quad c ^ {T} x \\ Ax \ leq \ b \ end {cases}}}

Care poate fi scris în formă scalară ca

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

Prin urmare, problema primară standard este constituită de o anumită funcție care trebuie maximizată, funcția obiectivă și o serie de constrângeri (poliedrul primar); problema în ansamblu este indicată cu (P) , valoarea optimă a problemei (P) este indicată cu v (P) în timp ce P este simbolul asociat cu poliedrul primar.

Funcția obiectivă

Primul element important care este introdus atunci când vorbim despre probleme în formă primară este tocmai funcția obiectivă, adică o funcție care reprezintă modelul matematic al ceea ce vrem să maximizăm. În realitate, este posibilă transformarea unei cereri de maximizare în minimizare, pur și simplu prin amintirea conceptului că a căuta minimul unei funcții este ca și cum ai căuta opusul maximului opusului său, adică: $minf(x)=-max-f(x)$ ${\ displaystyle minf (x) = - max-f (x)}$ ${\ displaystyle minf (x) = - max-f (x)}$ si invers.

Deoarece avem de-a face cu probleme de programare liniară, este clar că funcția de mai sus trebuie să fie neapărat liniară, adică poate fi exprimată pur și simplu prin produse scalare între constante și variabile (de gradul I). De fapt, pentru a scrie funcția folosim notația cx , care este scrisă mai formal ca:

\left\langle c^{T},x\right\rangle =\sum _{i=1}^{n}c_{i}x_{i}

{\ displaystyle \ left \ langle c ^ {T}, x \ right \ rangle = \ sum _ {i = 1} ^ {n} c_ {i} x_ {i}}

{\ displaystyle \ left \ langle c ^ {T}, x \ right \ rangle = \ sum _ {i = 1} ^ {n} c_ {i} x_ {i}}

Acesta este produsul scalar al vectorului coloană al variabilelor x , de dimensiune $n\times 1$ ${\ displaystyle n \ times 1}$ $n \ ori 1$ și vectorul rând (apoi transpus) al coeficienților c (în general „costuri”) a funcției obiective a dimensiunii $1\times n$ ${\ displaystyle 1 \ times n}$ $1 \ ori n$ .

Numărul n , care apare de mai multe ori, se referă la numărul de variabile implicate în problemă, adică la dimensiunea spațiului soluției: de exemplu, dacă există două variabile atunci n va fi 2. În general spunem că n este dimensiunea vectorului variabil al problemei: $x\in \mathbb {R} ^{n}$ ${\ displaystyle x \ in \ mathbb {R} ^ {n}}$ ${\ displaystyle x \ in \ mathbb {R} ^ {n}}$

De exemplu, dacă luăm în considerare funcția obiectivă în 4 variabile
$x_{1}-5x_{2}+7x_{3}$ ${\ displaystyle x_ {1} -5x_ {2} + 7x_ {3}}$ ${\ displaystyle x_ {1} -5x_ {2} + 7x_ {3}}$
reprezentarea sa ca produs scalar va fi ${\begin{bmatrix}1&-5&7&0\end{bmatrix}}\cdot {\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\x_{4}\end{bmatrix}}$ ${\ displaystyle {\ begin {bmatrix} 1 & -5 & 7 & 0 \ end {bmatrix}} \ cdot {\ begin {bmatrix} x_ {1} \\ x_ {2} \\ x_ {3} \\ x_ {4} \ end {bmatrix}}}$ ${\ displaystyle {\ begin {bmatrix} 1 & -5 & 7 & 0 \ end {bmatrix}} \ cdot {\ begin {bmatrix} x_ {1} \\ x_ {2} \\ x_ {3} \\ x_ {4} \ end {bmatrix}}}$

Poliedrul primar

Setul de puncte (vectori) care sunt admisibile pentru problemă în format primar standard, adică cele care satisfac toate constrângerile de tip $Ax\leq \ b$ ${\ displaystyle Ax \ leq \ b}$ ${\ displaystyle Ax \ leq \ b}$ este nevoie, după cum am spus, de numele de poliedru primar sau politop primar.

După cum sa văzut deja pentru funcția obiectivă, scrierea completă a constrângerilor m , în n variabile, care formează poliedrul primar este

$\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$
$\vdots$ ${\ displaystyle \ vdots}$ $\ vdots$
$\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$

În scris $Ax\leq \ b$ ${\ displaystyle Ax \ leq \ b}$ ${\ displaystyle Ax \ leq \ b}$ A este o matrice , numită matrice tehnologică , care are dimensiune $m\times n$ ${\ displaystyle m \ times n}$ $m \ ori n$ , unde m este numărul de constrângeri de inegalitate definite de problemă.

În mod similar cu ceea ce s-a spus pentru funcția obiectivă, forma în termeni de inegalități a constrângerilor problemei nu este foarte restrictivă: de fapt, permite, de asemenea, să traducă constrângeri de egalitate sau inegalitate în acest format, dar în direcția opusă. O constrângere liniară generică $g\left(x\right)=0$ ${\ displaystyle g \ left (x \ right) = 0}$ ${\ displaystyle g \ left (x \ right) = 0}$ de fapt, poate fi redat cu două constrângeri de inegalitate:

{\begin{cases}g\left(x\right)\leq \ 0\\-g\left(x\right)\leq \ 0\end{cases}}

{\ displaystyle {\ begin {cases} g \ left (x \ right) \ leq \ 0 \\ - g \ left (x \ right) \ leq \ 0 \ end {cases}}}

{\ displaystyle {\ begin {cases} g \ left (x \ right) \ leq \ 0 \\ - g \ left (x \ right) \ leq \ 0 \ end {cases}}}

În dreapta simbolului mai mic sau egal găsim vectorul b , este așa-numitul vector al termenilor cunoscuți , al dimensiunii $m\times 1$ ${\ displaystyle m \ times 1}$ ${\ displaystyle m \ times 1}$ , așa cum se poate observa și din produsul vector matrice.

Asociat cu conceptul de constrângere al problemei primare este și cel al variabilelor deșeurilor : în practică este un vector de numere care se obține făcând diferența între vectorul termenilor cunoscuți și cel obținut prin dezvoltarea produsului între matricea tehnologică. și variabile (care trebuie cunoscute).

În formă analitică, acest lucru este scris ca:

{\bar {S}}=b-A{\tilde {x}}

{\ displaystyle {\ bar {S}} = bA {\ tilde {x}}}

{\ displaystyle {\ bar {S}} = b-A {\ tilde {x}}}

Unde cu ${\tilde {x}}$ ${\ displaystyle {\ tilde {x}}}$ ${\ displaystyle {\ tilde {x}}}$ ne referim la soluția cu privire la care vrem să cunoaștem diferențele.

Abaterile unei soluții sunt o metodă excelentă pentru a recunoaște dacă o soluție este fezabilă sau nu pentru poliedrul P : dacă o soluție generează abateri non-negative este admisibilă, în timp ce dacă chiar și o abatere este mai mică de 0 atunci acel punct nu aparține la poliedru. Prin urmare, se va spune că un punct al poliedrului primar este admisibil pentru problema atașată atunci când fiecare dintre ele este respectată prin substituirea componentelor sale în constrângeri, sau în mod similar atunci când abaterile asociate sunt întotdeauna pozitive sau nule.

Interpretare analitică

Analitic, un poliedru este definit ca $P=\left\{x\in \mathbb {R} ^{n}:Ax\leq \ b\right\}$ ${\ displaystyle P = \ left \ {x \ in \ mathbb {R} ^ {n}: Ax \ leq \ b \ right \}}$ ${\ displaystyle P = \ left \ {x \ in \ mathbb {R} ^ {n}: Ax \ leq \ b \ right \}}$ , adică ca un set de soluții ale unui sistem de inegalități m liniare în n variabile.

Tratamentul analitic al poliedrelor este foarte util atunci când se iau în considerare problemele care au un număr mare de variabile, cum ar fi să nu permită localizarea constrângerilor în spațiul tridimensional.

Dacă, de exemplu, domeniul problemei noastre primare este dat de sistem

{\begin{cases}x_{1}-5x_{2}+4x_{3}\leq \ -6\\-x_{1}+6x_{3}-2x_{4}\leq \ 0\\x_{4}\leq \ 9\\6x_{1}-6x_{2}\leq \ 17\\x_{1}+x_{2}+x_{3}+x_{4}\leq \ 8\end{cases}}

{\ displaystyle {\ begin {cases} x_ {1} -5x_ {2} + 4x_ {3} \ leq \ -6 \\ - x_ {1} + 6x_ {3} -2x_ {4} \ leq \ 0 \ \ x_ {4} \ leq \ 9 \\ 6x_ {1} -6x_ {2} \ leq \ 17 \\ x_ {1} + x_ {2} + x_ {3} + x_ {4} \ leq \ 8 \ sfârșit {cazuri}}}

{\ displaystyle {\ begin {cases} x_ {1} -5x_ {2} + 4x_ {3} \ leq \ -6 \\ - x_ {1} + 6x_ {3} -2x_ {4} \ leq \ 0 \ \ x_ {4} \ leq \ 9 \\ 6x_ {1} -6x_ {2} \ leq \ 17 \\ x_ {1} + x_ {2} + x_ {3} + x_ {4} \ leq \ 8 \ sfârșit {cazuri}}}

aceasta poate fi reprezentată în formă $Ax\leq \ b$ ${\ displaystyle Ax \ leq \ b}$ ${\ displaystyle Ax \ leq \ b}$ În felul următor:

{\begin{bmatrix}1&-5&4&0\\-1&0&6&-2\\0&0&0&1\\6&-6&0&0\\1&1&1&1\end{bmatrix}}\cdot {\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\x_{4}\end{bmatrix}}\leq {\begin{bmatrix}-6\\0\\9\\17\\8\end{bmatrix}}

{\ displaystyle {\ begin {bmatrix} 1 & -5 & 4 & 0 \\ - 1 & 0 & 6 & -2 \\ 0 & 0 & 0 & 1 \\ 6 & -6 & 0 & 0 \\ 1 & 1 & 1 & 1 \ end {bmatrix}} \ cdot {\ begin {bmatrix} x_ {1} \\ x_ {2} \\ x_ {3} \\ x_ {4} \ end {bmatrix}} \ leq {\ begin {bmatrix} -6 \\ 0 \\ 9 \\ 17 \\ 8 \ end {bmatrix}}}

{\ displaystyle {\ begin {bmatrix} 1 & -5 & 4 & 0 \\ - 1 & 0 & 6 & -2 \\ 0 & 0 & 0 & 1 \\ 6 & -6 & 0 & 0 \\ 1 & 1 & 1 & 1 \ end {bmatrix}} \ cdot {\ begin {bmatrix} x_ {1} \\ x_ {2} \\ x_ {3} \\ x_ {4} \ end {bmatrix}} \ leq {\ begin {bmatrix} -6 \\ 0 \\ 9 \\ 17 \\ 8 \ end {bmatrix}}}

Interpretarea geometrică

Geometric un poliedru primar este intersecția unui număr finit de jumătăți închise - spații (numite jumătăți de plan, cu n = 2), care totuși poate fi și mulțimea goală.

Această afirmație pare mai evidentă atunci când amintim că forma analitică ne spune că poliedrul este ansamblul soluțiilor unui sistem de inegalități m liniare în n variabile: de fapt, întrucât un semi-spațiu închis al $\mathbb {R} ^{n}$ ${\ displaystyle \ mathbb {R} ^ {n}}$ ${\ mathbb {R}} ^ {n}$ poate fi descris algebric ca ansamblul soluțiilor unei inegalități liniare în n variabile, este clar că un poliedru, intersecția sa, va fi ansamblul soluțiilor unui sistem de inegalități liniare.

Un poliedru P poate fi limitat sau nelimitat, dar va fi întotdeauna convex , adică dacă conține două puncte, atunci conține tot segmentul care le are ca extreme. De fapt, dacă ne amintim că intersecția a două sau mai multe mulțimi convexe este o mulțime convexă, atunci deoarece jumătățile închise sunt mulțimi convexe la fel este și poliedrul.

Un poliedru care este, de asemenea, un con se numește con poliedric (con poliedric) și poate fi interpretat ca ansamblul soluțiilor unui sistem omogen de inegalități liniare.

Trebuie făcută o mică clarificare lingvistică: în matematică poliedrul este de fapt un obiect, o intersecție a jumătăților de spații (cu spațiu în 3 dimensiuni), aparținând spațiului real, adică cel tridimensional. În practică, poliedrul este o extensie a noțiunii de poligon din plan la spațiul obișnuit.

Pentru a fi precis, familia obiectelor matematice care au proprietățile descrise puțin mai devreme este aceea, așa cum am menționat deja, a politopilor ; în tratamentul următor, totuși, vom continua să folosim termenul de poliedru.

Vârfuri și direcții

Dacă ne gândim la un poligon, politop în 2 dimensiuni, putem vedea cu ușurință modul în care posedă unele elemente geometrice, cum ar fi marginile laterale și vârfurile : totuși, atunci când trebuie dată o definiție non-geometrică a vârfului unui poliedru , dificultate.

Presupunând că sunt cunoscute conceptele de set convex, combinație convexă și anvelopă convexă , putem defini un vârf al unui poliedru P ca un punct care nu poate fi exprimat ca o combinație convexă proprie altor puncte aparținând lui P.

În practică, un vârf al unui poliedru este un punct al acestuia care nu se află într-un segment care aparține poliedrului. Mulțimea vârfurilor unui poliedru P este notată cu $vert\left(P\right)$ ${\ displaystyle vert \ left (P \ right)}$ ${\ displaystyle vert \ left (P \ right)}$

Conceptul de vârf va fi foarte important mai târziu, când ne vom ocupa de metodologiile pentru identificarea soluțiilor optime ale problemelor de programare liniară pentru probleme în formă primară standard.

Să vedem acum conceptele de direcție de recesiune și liniaritate, utile pentru a întocmi câteva prime caracteristici ale poliedrelor și vârfurilor.

O direcție de recesiune pentru un poliedru P este un vector d astfel încât

x+td\in P\quad \forall x\in P,\forall t\geq \ 0

{\ displaystyle x + td \ in P \ quad \ forall x \ in P, \ forall t \ geq \ 0}

{\ displaystyle x + td \ in P \ quad \ forall x \ in P, \ forall t \ geq \ 0}

În practică, un vector d este o direcție de recesiune pentru un poliedru dacă conține toate jumătățile de direcție d care ies din punctele aparținând P.

Setul de direcții de recesiune a lui P este notat cu $rec\left(P\right)$ ${\ displaystyle rec \ left (P \ right)}$ ${\ displaystyle rec \ left (P \ right)}$ .

Este ușor de observat că un poliedru limitat nu are direcții de recesiune (diferite de zero).

Un alt concept foarte util în studiul poliedrelor este cel al direcției de liniaritate : o direcție de liniaritate pentru un poliedru P este un vector d astfel încât

\pm \ d\in rec\left(P\right)

{\ displaystyle \ pm \ d \ in rec \ left (P \ right)}

{\ displaystyle \ pm \ d \ in rec \ left (P \ right)}

.

Aceasta înseamnă că o direcție d este liniară pentru un poliedru dacă conține toate liniile de direcție d care trec prin puncte care îi aparțin: mulțimea tuturor direcțiilor de liniaritate a lui P este notată cu $lineal\left(P\right)$ ${\ displaystyle lineal \ left (P \ right)}$ ${\ displaystyle lineal \ left (P \ right)}$ .

Acum , să vedem o teorema care justifică introducerea acestor două concepte: „Pentru fiecare poliedru P non-gol că avem $vert\left(P\right)\neq \ \varnothing \iff lineal\left(P\right)=\left\{0\right\}$ ${\ displaystyle vert \ left (P \ right) \ neq \ \ varnothing \ if lineal \ left (P \ right) = \ left \ {0 \ right \}}$ ${\ displaystyle vert \ left (P \ right) \ neq \ \ varnothing \ if lineal \ left (P \ right) = \ left \ {0 \ right \}}$ "

În practică, teorema este echivalentă cu a spune că o condiție necesară și suficientă pentru ca un poliedru să aibă vârfuri este aceea că nu conține linii drepte.

Teorema lui Weyl

Să vedem acum o teoremă de programare liniară foarte importantă, cunoscută și sub numele de teorema reprezentării poliedrelor, care ne va permite să definim un poliedru prin conceptele de anvelopă conică și anvelopă convexă a două subseturi de puncte.

Oficial:

Este $P.$ ${\ displaystyle P}$ $P.$ un poliedru primar

dacă P nu este gol

atunci există un subgrup finit de puncte ale lui P

\quad \quad V=\left\{v^{1},v^{2},\ldots ,v^{k}\right\}

{\ displaystyle \ quad \ quad V = \ left \ {v ^ {1}, v ^ {2}, \ ldots, v ^ {k} \ right \}}

{\ displaystyle \ quad \ quad V = \ left \ {v ^ {1}, v ^ {2}, \ ldots, v ^ {k} \ right \}}

și un set finit de direcții de recesiune

$\quad \quad E=\left\{e^{1},e^{2},\ldots ,e^{z}\right\}$ ${\ displaystyle \ quad \ quad E = \ left \ {e ^ {1}, e ^ {2}, \ ldots, e ^ {z} \ right \}}$ ${\ displaystyle \ quad \ quad E = \ left \ {e ^ {1}, e ^ {2}, \ ldots, e ^ {z} \ right \}}$ , posibil și gol, astfel încât

$P=conv\left(V\right)+cono\left(E\right)$ ${\ displaystyle P = conv \ left (V \ right) + con \ left (E \ right)}$ ${\ displaystyle P = conv \ left (V \ right) + con \ left (E \ right)}$

În practică, ceea ce face teorema este să „descarce” structura poliedrului într-o combinație finită de puncte aparținând a două mulțimi distincte.

Este necesar să acordați o atenție deosebită sumei definite între cele două mulțimi E și V : este de fapt o sumă directă, adică o sumă în sensul mulțimii, care este alcătuită din toate sumele posibile a două elemente, unul din V și unul din E. Deci grafic punctele poliedrului vor fi cele rezultate din toate sumele posibile dintre combinațiile convexe ale punctelor lui V și combinațiile conice ale elementelor lui E.

Există, de asemenea, o lemă foarte utilă pe vârfuri și poliedre care ne garantează că, dacă poliedrul P are vârfuri, toate și numai elementele unei mulțimi O , atunci $V=O$ ${\ displaystyle V = O}$ ${\ displaystyle V = O}$ . Cu alte cuvinte, lema ne garantează că dacă un poliedru cu vârfuri este descompus așa cum este garantat de teorema lui Weyl, atunci setul de pornire pentru combinațiile convexe este exact cel al vârfurilor.

Condiții de optimitate

Vom vedea acum o serie de teoreme, definiții și algoritmi care vor prezenta mai întâi caracteristicile soluțiilor optime ale unei probleme în format primar

\left(P\right)={\begin{cases}\max \quad cx\\Ax\leq \ b\end{cases}}

{\ displaystyle \ left (P \ right) = {\ begin {cases} \ max \ quad cx \\ Ax \ leq \ b \ end {cases}}}

{\ displaystyle \ left (P \ right) = {\ begin {cases} \ max \ quad cx \\ Ax \ leq \ b \ end {cases}}}

și apoi vor lega conceptul de punct optim de poliedru, sugerând cum să procedăm la rezolvarea problemei de optimizare de mai sus.

Caracterizarea elementară a optimității

Prezentăm acum o teoremă fundamentală care ne prezintă câteva caracteristici fundamentale ale unei soluții optime a unei probleme de programare liniară în cazul primar:

Este dată o problemă în formatul primar standard $\left(P\right)={\begin{cases}\max \quad cx\\Ax\leq \ b\end{cases}}$ ${\ displaystyle \ left (P \ right) = {\ begin {cases} \ max \ quad cx \\ Ax \ leq \ b \ end {cases}}}$ ${\ displaystyle \ left (P \ right) = {\ begin {cases} \ max \ quad cx \\ Ax \ leq \ b \ end {cases}}}$

de sine $c\neq \ 0$ ${\ displaystyle c \ neq \ 0}$ ${\ displaystyle c \ neq \ 0}$ atunci fiecare soluție optimă nu este internă poliedrului

de sine $P\neq \ \varnothing$ ${\ displaystyle P \ neq \ \ varnothing}$ ${\ displaystyle P \ neq \ \ varnothing}$ atunci problema are o singură soluție optimă sau are infinite

Soluțiile optime locale sunt, de asemenea, optime la nivel global

Demonstrație

Deoarece există trei teze, atunci trebuie să facem trei dovezi separate:

Dacă o soluție optimă ar fi internă poliedrului, atunci gradientul funcției obiective ar trebui să fie zero de teorema lui Fermat ; dar întrucât gradientul funcției este $\nabla \ cx=c$ ${\ displaystyle \ nabla \ cx = c}$ ${\ displaystyle \ nabla \ cx = c}$ , c exact, atunci acest lucru este fals, cu excepția cazului în care c este 0.

Să încercăm să spunem că dacă există mai multe soluții optime, de exemplu 2, atunci există infinit. Să numim cele două soluții optice generice ale problemei $\left(P\right)$ ${\ displaystyle \ left (P \ right)}$ ${\ displaystyle \ left (P \ right)}$ $x_{1},x_{2}$ ${\ displaystyle x_ {1}, x_ {2}}$ $x_1, x_2$ .
Deoarece poliedrul primar P este convex , prin însăși definiția sa de intersecție a jumătăților închise (convexe), atunci pentru definiția convexității luăm oricare două puncte aparținând acestui set convex, mulțimea conține tot segmentul care le unește.
Scriem această condiție analitic pentru P și punctele sale $x_{1},x_{2}:\quad tx_{1}+(1-t)x_{2}\in P\quad \forall t\in [0,1]$ ${\ displaystyle x_ {1}, x_ {2}: \ quad tx_ {1} + (1-t) x_ {2} \ in P \ quad \ forall t \ in [0,1]}$ ${\ displaystyle x_ {1}, x_ {2}: \ quad tx_ {1} + (1-t) x_ {2} \ in P \ quad \ forall t \ in [0,1]}$ .
Acum scriem valorile pe care le asumă funcția obiectivă cx și trebuie să le asumăm, deoarece punctele aparțin poliedrului, pe punctele unuia dintre segmentele menționate mai sus și apoi dezvoltăm: $\quad \quad c(tx_{1}+(1-t)x_{2})=tcx_{1}+(1-t)cx_{2}$ ${\ displaystyle \ quad \ quad c (tx_ {1} + (1-t) x_ {2}) = tcx_ {1} + (1-t) cx_ {2}}$ ${\ displaystyle \ quad \ quad c (tx_ {1} + (1-t) x_ {2}) = tcx_ {1} + (1-t) cx_ {2}}$ .
Fiind totuși $x_{1}$ ${\ displaystyle x_ {1}}$ $x_1$ Și $x_{2}$ ${\ displaystyle x_ {2}}$ $x_2$ două soluții optime, atunci funcția obiectivă pe ele trebuie să își asume aceleași valori, adică $\quad \quad cx_{1}=cx_{2}$ ${\ displaystyle \ quad \ quad cx_ {1} = cx_ {2}}$ ${\ displaystyle \ quad \ quad cx_ {1} = cx_ {2}}$ , egalitate pe care o exploatăm în expresia de mai sus: $\quad \quad tcx_{1}+(1-t)cx_{1}=tcx_{1}+cx_{1}-tcx_{1}=cx_{1}$ ${\ displaystyle \ quad \ quad tcx_ {1} + (1-t) cx_ {1} = tcx_ {1} + cx_ {1} -tcx_ {1} = cx_ {1}}$ ${\ displaystyle \ quad \ quad tcx_ {1} + (1-t) cx_ {1} = tcx_ {1} + cx_ {1} -tcx_ {1} = cx_ {1}}$
Prin urmare, am constatat că funcția obiectivă își asumă aceleași valori ca soluțiile optime, adică valori optime, pe toate punctele infinite ale segmentului analizat, pentru care există infinite soluții optime.

Raționăm în mod absurd : să presupunem că există un punct al poliedrului care este o soluție maximă locală, dar nu globală, și să-l numim z ; atunci, ca maxim local, dincolo de un anumit vecinătate va fi mai puțin de cel puțin un punct aparținând poliedrului, adică $\exists \ x\in P:cx>\ cz$ ${\ displaystyle \ există \ x \ în P: cx> \ cz}$ ${\ displaystyle \ există \ x \ în P: cx> \ cz}$ .
Să luăm acum în considerare segmentul care unește cele două puncte de mai sus, pe care îl vom numi ${\overline {xz}}$ ${\ displaystyle {\ overline {xz}}}$ ${\ displaystyle {\ overline {xz}}}$ : întrucât poliedrul primar este întotdeauna convex și extremele segmentului considerat aparțin lui P , atunci ${\overline {xz}}\in P$ ${\ displaystyle {\ overline {xz}} \ în P}$ ${\ displaystyle {\ overline {xz}} \ în P}$ , care este echivalent cu scrierea $tx+(1-t)z\in P\quad \forall t\in [0,1]$ ${\ displaystyle tx + (1-t) z \ in P \ quad \ forall t \ in [0,1]}$ ${\ displaystyle tx + (1-t) z \ in P \ quad \ forall t \ in [0,1]}$ .
În acest moment, studiem comportamentul funcției obiective de-a lungul tuturor punctelor acestui segment: $c(tx+(1-t)z)=tcx+(1-t)cz$ ${\ displaystyle c (tx + (1-t) z) = tcx + (1-t) cz}$ ${\ displaystyle c (tx + (1-t) z) = tcx + (1-t) cz}$ .
Anterior am procedat $cx>\ cz$ ${\ displaystyle cx> \ cz}$ ${\ displaystyle cx> \ cz}$ , deci îl putem folosi așa cum am scris înainte: $tcx+(1-t)cz\Rightarrow \ tcx+(1-t)cz>\ tcz+(1-t)cz=tcz+cz-tcz=cz$ ${\ displaystyle tcx + (1-t) cz \ Rightarrow \ tcx + (1-t) cz> \ tcz + (1-t) cz = tcz + cz-tcz = cz}$ ${\ displaystyle tcx + (1-t) cz \ Rightarrow \ tcx + (1-t) cz> \ tcz + (1-t) cz = tcz + cz-tcz = cz}$ .
Expresia tocmai obținută ne spune că în fiecare punct al segmentului, cu excepția z , funcția obiectivă capătă o valoare mai mare decât în z , adică: $\forall x\in {\overline {xz}},x\neq \ z\quad cx>\ cz$ ${\ displaystyle \ forall x \ in {\ overline {xz}}, x \ neq \ z \ quad cx> \ cz}$ ${\ displaystyle \ forall x \ in {\ overline {xz}}, x \ neq \ z \ quad cx> \ cz}$
Dar din această afirmație rezultă că în fiecare vecinătate a z de -a lungul unui anumit segment funcția obiectivă crește, deci z nu poate fi o soluție optimă locală: aceasta contrazice ipoteza și, prin urmare, deoarece am procedat în mod absurd, teza noastră este demonstrată.

Observații

Ceea ce tocmai a fost afirmat este una dintre cele mai importante teoreme ale programării liniare : permite, de fapt, să producă o serie de simplificări asupra studiului și să caute soluții optime ale unei probleme în formă primară standard.

Prima teză ne spune că, dacă funcția obiectivă nu este constantă, soluția optimă se află la frontiera poliedrului. De fapt, dacă funcția este constantă, gradientul c = 0. Este foarte util deoarece restricționează căutarea punctelor optime numai la marginile poliedrului, chiar dacă vom vedea mai târziu că o simplificare suplimentară poate fi efectuată în anumite condiții.

A doua teză este la fel de importantă, deși mai mult din punct de vedere conceptual decât practic: datorită acesteia putem spune întotdeauna care sunt toate soluțiile optime ale unei probleme primare. De fapt, suntem fie în cazul în care există o singură soluție, fie în cel în care există infinit, astfel încât orice cerere de a le găsi pe toate cade pe auz.

În cele din urmă, observăm a treia teză garantată de teorema elementară de caracterizare a optimității: dacă o soluție este un maxim local, atunci este și o soluție optimă globală. Aceasta înseamnă că, dacă găsim un punct al poliedrului care este mai mare decât toate punctele din vecinătatea sa din domeniul problemei, atunci nu este necesar să facem alte verificări, acel punct este excelent! Similar cu prima teză, această parte a teoremei este extrem de utilă pentru reducerea drastică a lungimii procedurii optime de căutare.

Teorema fundamentală a LP

Afirmație

Cea mai importantă teoremă pentru rezolvarea problemelor în formă primară standard, care ne oferă o bază teoretică solidă pentru a găsi o procedură de căutare rapidă și corectă pentru a optimiza o funcție este următoarea:

Este dată o problemă în formatul primar standard $\left(P\right)={\begin{cases}\max \quad cx\\Ax\leq \ b\end{cases}}$ ${\ displaystyle \ left (P \ right) = {\ begin {cases} \ max \ quad cx \\ Ax \ leq \ b \ end {cases}}}$ ${\ displaystyle \ left (P \ right) = {\ begin {cases} \ max \ quad cx \\ Ax \ leq \ b \ end {cases}}}$

de sine

$P\neq \ \varnothing$ ${\ displaystyle P \ neq \ \ varnothing}$ ${\ displaystyle P \ neq \ \ varnothing}$
$\left(P\right)<\ +\infty$ ${\ displaystyle \ left (P \ right) <\ + \ infty}$ ${\ displaystyle \ left (P \ right) <\ + \ infty}$
$P.$ ${\ displaystyle P}$ $P.$ are vârfuri

asa de

Există cel puțin un vârf optim.

Demonstrație

Pentru început, să luăm în considerare un punct generic $x\in P$ ${\ displaystyle x \ în P}$ ${\ displaystyle x \ în P}$ , care, datorită teoremei lui Weyl , putem scrie prin conceptele de combinație conică și combinație convexă , adică

$x=\sum _{i=1}^{k}\lambda _{i}v_{i}\ +\ \sum _{j=1}^{z}\mu _{j}e_{j}$ ${\ displaystyle x = \ sum _ {i = 1} ^ {k} \ lambda _ {i} v_ {i} \ + \ \ sum _ {j = 1} ^ {z} \ mu _ {j} e_ { j}}$ ${\ displaystyle x = \ sum _ {i = 1} ^ {k} \ lambda _ {i} v_ {i} \ + \ \ sum _ {j = 1} ^ {z} \ mu _ {j} e_ { j}}$

De asemenea, ne amintim că, prin definiție

$\sum _{i=1}^{k}\lambda _{i}=1,\lambda _{i}\in \left[0,1\right]\ \forall i\in \left\{1,2.....k\right\}$ ${\ displaystyle \ sum _ {i = 1} ^ {k} \ lambda _ {i} = 1, \ lambda _ {i} \ in \ left [0,1 \ right] \ \ forall i \ in \ left \ {1,2 ..... k \ right \}}$ ${\ displaystyle \ sum _ {i = 1} ^ {k} \ lambda _ {i} = 1, \ lambda _ {i} \ in \ left [0,1 \ right] \ \ forall i \ in \ left \ {1,2 ..... k \ right \}}$

$\mu _{j}\geq \ 0\ \ \forall j\in \left\{1,2.....z\right\}$ ${\ displaystyle \ mu _ {j} \ geq \ 0 \ \ \ forall j \ in \ left \ {1,2 ..... z \ right \}}$ ${\ displaystyle \ mu _ {j} \ geq \ 0 \ \ \ forall j \ in \ left \ {1,2 ..... z \ right \}}$

Deoarece teza necesită o relație cu o soluție optimă a problemei LP, scriem funcția obiectivă a acesteia în punctul nostru generic:

$cx=c\left(\sum _{i=1}^{k}\lambda _{i}v_{i}\ +\ \sum _{j=1}^{z}\mu _{j}e_{j}\right)=$ ${\ displaystyle cx = c \ left (\ sum _ {i = 1} ^ {k} \ lambda _ {i} v_ {i} \ + \ \ sum _ {j = 1} ^ {z} \ mu _ { j} e_ {j} \ right) =}$ ${\ displaystyle cx = c \ left (\ sum _ {i = 1} ^ {k} \ lambda _ {i} v_ {i} \ + \ \ sum _ {j = 1} ^ {z} \ mu _ { j} e_ {j} \ right) =}$ $c\sum _{i=1}^{k}\lambda _{i}v_{i}\ +\ c\sum _{j=1}^{z}\mu _{j}e_{j}=$ ${\ displaystyle c \ sum _ {i = 1} ^ {k} \ lambda _ {i} v_ {i} \ + \ c \ sum _ {j = 1} ^ {z} \ mu _ {j} e_ { j} =}$ ${\ displaystyle c \ sum _ {i = 1} ^ {k} \ lambda _ {i} v_ {i} \ + \ c \ sum _ {j = 1} ^ {z} \ mu _ {j} e_ { j} =}$ $\sum _{i=1}^{k}\lambda _{i}\left(cv_{i}\right)\ +\ \sum _{j=1}^{z}\mu _{j}\left(ce_{j}\right)$ ${\ displaystyle \ sum _ {i = 1} ^ {k} \ lambda _ {i} \ left (cv_ {i} \ right) \ + \ \ sum _ {j = 1} ^ {z} \ mu _ { j} \ left (ce_ {j} \ right)}$ ${\ displaystyle \ sum _ {i = 1} ^ {k} \ lambda _ {i} \ left (cv_ {i} \ right) \ + \ \ sum _ {j = 1} ^ {z} \ mu _ { j} \ left (ce_ {j} \ right)}$

Primul și al doilea pas au fost posibile datorită proprietății de liniaritate a produsului scalar și apoi datorită celui distributiv .

După ce am „descărcat” structura problemei într-o combinație finită de puncte, să analizăm exact această expresie.

Privind la toate produsele scalare (presupunând că există) prezente în însumări, înmulțite cu orice coeficienți non-negativi, mă pot gândi să găsesc al doilea, cei derivați din combinația conică, având un semn pozitiv, adică $\exists \ \left(ce_{j}\right)>\ 0$ ${\ displaystyle \ există \ \ left (ce_ {j} \ right)> \ 0}$ ${\ displaystyle \ există \ \ left (ce_ {j} \ right)> \ 0}$ .

În acest moment m-aș putea gândi să găsesc și coeficientul corespunzător $\mu _{j}$ ${\ displaystyle \ mu _ {j}}$ ${\ displaystyle \ mu _ {j}}$ : dar având ca singură limită aceea de a fi non-negativ, îmi pot imagina atât de mare încât să trimit suma la valori infinit de mari, adică $\mu _{j}\to \ +\infty \ \ \Rightarrow \ \ \ \sum _{j=1}^{z}\mu _{j}\left(ce_{j}\right)\to \ +\infty$ ${\ displaystyle \ mu _ {j} \ to \ + \ infty \ \ \ Rightarrow \ \ \ \ sum _ {j = 1} ^ {z} \ mu _ {j} \ left (ce_ {j} \ right) \ to \ + \ infty}$ ${\ displaystyle \ mu _ {j} \ to \ + \ infty \ \ \ Rightarrow \ \ \ \ sum _ {j = 1} ^ {z} \ mu _ {j} \ left (ce_ {j} \ right) \ to \ + \ infty}$ .

Acum observăm că însumarea $\sum _{i=1}^{k}\lambda _{i}\left(cv_{i}\right)$ ${\ displaystyle \ sum _ {i = 1} ^ {k} \ lambda _ {i} \ left (cv_ {i} \ right)}$ ${\ displaystyle \ sum _ {i = 1} ^ {k} \ lambda _ {i} \ left (cv_ {i} \ right)}$ nu poate fi trimis la valori foarte mari (negative), pentru a „compensa” celălalt: acest lucru se datorează faptului că coeficienții săi sunt limitați cu $\sum _{i=1}^{k}\lambda _{i}=1,\lambda _{i}\in \left[0,1\right]\ \forall i\in \left\{1,2.....k\right\}$ ${\ displaystyle \ sum _ {i = 1} ^ {k} \ lambda _ {i} = 1, \ lambda _ {i} \ in \ left [0,1 \ right] \ \ forall i \ in \ left \ {1,2 ..... k \ right \}}$ ${\ displaystyle \ sum _ {i = 1} ^ {k} \ lambda _ {i} = 1, \ lambda _ {i} \ in \ left [0,1 \ right] \ \ forall i \ in \ left \ {1,2 ..... k \ right \}}$ .

Această situație ne face să spunem că, dacă prima însumare este trimisă la valori mari, funcția obiectivă devine: $cx=\sum _{i=1}^{k}\lambda _{i}\left(cv_{i}\right)\ +\ \sum _{j=1}^{z}\mu _{j}\left(ce_{j}\right)=\sum _{i=1}^{k}\lambda _{i}\left(cv_{i}\right)\ +\infty =+\infty$ ${\ displaystyle cx = \ sum _ {i = 1} ^ {k} \ lambda _ {i} \ left (cv_ {i} \ right) \ + \ \ sum _ {j = 1} ^ {z} \ mu _ {j} \ left (ce_ {j} \ right) = \ sum _ {i = 1} ^ {k} \ lambda _ {i} \ left (cv_ {i} \ right) \ + \ infty = + \ infty}$ ${\ displaystyle cx = \ sum _ {i = 1} ^ {k} \ lambda _ {i} \ left (cv_ {i} \ right) \ + \ \ sum _ {j = 1} ^ {z} \ mu _ {j} \ left (ce_ {j} \ right) = \ sum _ {i = 1} ^ {k} \ lambda _ {i} \ left (cv_ {i} \ right) \ + \ infty = + \ infty}$

Totuși, acest lucru contrazice ipoteza $\left(P\right)<\ +\infty$ ${\ displaystyle \ left (P \ right) <\ + \ infty}$ ${\ displaystyle \ left (P \ right) <\ + \ infty}$ .

Deci, singura modalitate de a „ieși” din această problemă este angajarea $ce_{j}\leq \ 0\ \ \forall j\in \left\{1,2.....z\right\}$ ${\ displaystyle ce_ {j} \ leq \ 0 \ \ \ forall j \ in \ left \ {1,2 ..... z \ right \}}$ ${\ displaystyle ce_ {j} \ leq \ 0 \ \ \ forall j \ in \ left \ {1,2 ..... z \ right \}}$ ; de fapt, așa cum am spus deja, ar fi suficient ca chiar și unul să fie pozitiv pentru a putea acționa foarte bine asupra rudei sale $\mu _{j}$ ${\ displaystyle \ mu _ {j}}$ ${\ displaystyle \ mu _ {j}}$ pentru a-și maximiza valoarea și a face funcția obiectivă să „stropească” la nesfârșit.

În acest moment mă întorc să observ teza pe care trebuie să o dovedim: întrucât încercăm să găsim o soluție optimă, încercăm să maximizăm funcția obiectivă pentru problemă ${\begin{cases}\max \quad cx\\Ax\leq \ b\end{cases}}$ ${\ displaystyle {\ begin {cases} \ max \ quad cx \\ Ax \ leq \ b \ end {cases}}}$ ${\ displaystyle {\ begin {cases} \ max \ quad cx \\ Ax \ leq \ b \ end {cases}}}$

Așadar, trebuie să maximizăm $\quad cx=\sum _{i=1}^{k}\lambda _{i}\left(cv_{i}\right)\ +\ \sum _{j=1}^{z}\mu _{j}\left(ce_{j}\right)$ ${\ displaystyle \ quad cx = \ sum _ {i = 1} ^ {k} \ lambda _ {i} \ left (cv_ {i} \ right) \ + \ \ sum _ {j = 1} ^ {z} \ mu _ {j} \ left (ce_ {j} \ right)}$ ${\ displaystyle \ quad cx = \ sum _ {i = 1} ^ {k} \ lambda _ {i} \ left (cv_ {i} \ right) \ + \ \ sum _ {j = 1} ^ {z} \ mu _ {j} \ left (ce_ {j} \ right)}$ ; a doua însumare este alcătuită din aditivi non-pozitivi, deoarece coeficienții sunt toți non-negativi prin definiție, iar produsele scalare sunt toate non-pozitive așa cum sa menționat anterior. Dacă maximizăm o sumă de termeni non-pozitivi, rezultatul este evident că devine nul, adică presupunem $\mu _{j}=0\ \ \forall j\in \left\{1,2.....z\right\}$ ${\ displaystyle \ mu _ {j} = 0 \ \ \ forall j \ in \ left \ {1,2 ..... z \ right \}}$ ${\ displaystyle \ mu _ {j} = 0 \ \ \ forall j \ in \ left \ {1,2 ..... z \ right \}}$ .

În lumina acestei operații scriem: $max\ \ cx=max\sum _{i=1}^{k}\lambda _{i}\left(cv_{i}\right)\ +\ max\sum _{j=1}^{z}\mu _{j}\left(ce_{j}\right)=max\sum _{i=1}^{k}\lambda _{i}\left(cv_{i}\right)\ +0$ ${\ displaystyle max \ \ cx = max \ sum _ {i = 1} ^ {k} \ lambda _ {i} \ left (cv_ {i} \ right) \ + \ max \ sum _ {j = 1} ^ {z} \ mu _ {j} \ left (ce_ {j} \ right) = max \ sum _ {i = 1} ^ {k} \ lambda _ {i} \ left (cv_ {i} \ right) \ +0}$ ${\ displaystyle max \ \ cx = max \ sum _ {i = 1} ^ {k} \ lambda _ {i} \ left (cv_ {i} \ right) \ + \ max \ sum _ {j = 1} ^ {z} \ mu _ {j} \ left (ce_ {j} \ right) = max \ sum _ {i = 1} ^ {k} \ lambda _ {i} \ left (cv_ {i} \ right) \ +0}$

Următorul pas este să eliminați suma prin dezvoltarea acesteia: $max\ \ cx=max\sum _{i=1}^{k}\lambda _{i}\left(cv_{i}\right)\ =max\ \left\{\lambda _{1}\left(cv_{1}\right)+\lambda _{2}\left(cv_{2}\right)+\ldots \lambda _{k}\left(cv_{k}\right)\right\}$ $max\ \ cx=max\sum _{i=1}^{k}\lambda _{i}\left(cv_{i}\right)\ =max\ \left\{\lambda _{1}\left(cv_{1}\right)+\lambda _{2}\left(cv_{2}\right)+\ldots \lambda _{k}\left(cv_{k}\right)\right\}$ $max\ \ cx=max\sum _{i=1}^{k}\lambda _{i}\left(cv_{i}\right)\ =max\ \left\{\lambda _{1}\left(cv_{1}\right)+\lambda _{2}\left(cv_{2}\right)+\ldots \lambda _{k}\left(cv_{k}\right)\right\}$ , dove ricordiamo che i k prodotti scalari sono numeri veri e propri.

Di questi k numeri prendiamo il maggiore, che chiamiamo $\quad cv_{\bar {k}}$ $\quad cv_{\bar {k}}$ $\quad cv_{\bar {k}}$ , ovvero $cv_{\bar {k}}=max\ \left(cv_{i}\right)\forall i\in \left\{1,2.....k\right\}$ $cv_{\bar {k}}=max\ \left(cv_{i}\right)\forall i\in \left\{1,2.....k\right\}$ $cv_{\bar {k}}=max\ \left(cv_{i}\right)\forall i\in \left\{1,2.....k\right\}$ .

Quindi se sostituiamo questo prodotto scalare al posto di tutti gli altri k , sicuramente otterremo una maggiorazione della sommatoria, cioè $max\ \ cx=max\ \left\{\lambda _{1}\left(cv_{1}\right)+\lambda _{2}\left(cv_{2}\right)+\ldots \lambda _{k}\left(cv_{k}\right)\right\}\leq \ max\ \left\{\lambda _{1}\left(cv_{\bar {k}}\right)+\lambda _{2}\left(cv_{\bar {k}}\right)+\ldots \lambda _{k}\left(cv_{\bar {k}}\right)\right\}$ $max\ \ cx=max\ \left\{\lambda _{1}\left(cv_{1}\right)+\lambda _{2}\left(cv_{2}\right)+\ldots \lambda _{k}\left(cv_{k}\right)\right\}\leq \ max\ \left\{\lambda _{1}\left(cv_{\bar {k}}\right)+\lambda _{2}\left(cv_{\bar {k}}\right)+\ldots \lambda _{k}\left(cv_{\bar {k}}\right)\right\}$ $max\ \ cx=max\ \left\{\lambda _{1}\left(cv_{1}\right)+\lambda _{2}\left(cv_{2}\right)+\ldots \lambda _{k}\left(cv_{k}\right)\right\}\leq \ max\ \left\{\lambda _{1}\left(cv_{\bar {k}}\right)+\lambda _{2}\left(cv_{\bar {k}}\right)+\ldots \lambda _{k}\left(cv_{\bar {k}}\right)\right\}$

Adesso sviluppiamo la somma ricordando che $\sum _{i=1}^{k}\lambda _{i}=1$ $\sum _{i=1}^{k}\lambda _{i}=1$ $\sum _{i=1}^{k}\lambda _{i}=1$ :

$max\ \left\{\lambda _{1}\left(cv_{\bar {k}}\right)+\lambda _{2}\left(cv_{\bar {k}}\right)+\ldots \lambda _{k}\left(cv_{\bar {k}}\right)\right\}=$ $max\ \left\{\lambda _{1}\left(cv_{\bar {k}}\right)+\lambda _{2}\left(cv_{\bar {k}}\right)+\ldots \lambda _{k}\left(cv_{\bar {k}}\right)\right\}=$ $max\ \left\{\lambda _{1}\left(cv_{\bar {k}}\right)+\lambda _{2}\left(cv_{\bar {k}}\right)+\ldots \lambda _{k}\left(cv_{\bar {k}}\right)\right\}=$

$max\ \left\{\left(cv_{\bar {k}}\right)\cdot \left(\lambda _{1}+\lambda _{2}+\ldots \lambda _{k}\right)\right\}=$ $max\ \left\{\left(cv_{\bar {k}}\right)\cdot \left(\lambda _{1}+\lambda _{2}+\ldots \lambda _{k}\right)\right\}=$ $max\ \left\{\left(cv_{\bar {k}}\right)\cdot \left(\lambda _{1}+\lambda _{2}+\ldots \lambda _{k}\right)\right\}=$

$max\ \left\{\left(cv_{\bar {k}}\right)\cdot 1\right\}=$ $max\ \left\{\left(cv_{\bar {k}}\right)\cdot 1\right\}=$ $max\ \left\{\left(cv_{\bar {k}}\right)\cdot 1\right\}=$

$max\ cv_{\bar {k}}$ $max\ cv_{\bar {k}}$ $max\ cv_{\bar {k}}$

Ma dal momento che $cv_{\bar {k}}$ $cv_{\bar {k}}$ $cv_{\bar {k}}$ è un numero preciso, costante, la sua massimizzazione è se stesso, cioè $\quad max\ cv_{\bar {k}}=cv_{\bar {k}}$ $\quad max\ cv_{\bar {k}}=cv_{\bar {k}}$ $\quad max\ cv_{\bar {k}}=cv_{\bar {k}}$

Sfruttando quindi il fatto che questo valore era maggiore del valore in un generico punto della funzione obiettivo si può scrivere che $max\ cx\leq \ cv_{\bar {k}}$ $max\ cx\leq \ cv_{\bar {k}}$ $max\ cx\leq \ cv_{\bar {k}}$ .

Possiamo ora sfruttare un lemma associato al teorema di Weyl che ci garantiva che se il poliedro P ha vertici, tutti e soli gli elementi di un insieme O , allora V = O , cioè il sottoinsieme di punti di cui si cerca l' involucro convesso è quello che contiene i vertici. Alla luce di questo si deduce che $V=\left\{v_{1},v_{2}\ldots v_{k}\right\}=\left\{vertici\right\}$ $V=\left\{v_{1},v_{2}\ldots v_{k}\right\}=\left\{vertici\right\}$ $V=\left\{v_{1},v_{2}\ldots v_{k}\right\}=\left\{vertici\right\}$ ; da questo si trova infine: $v_{\bar {k}}\in V\rightarrow \ v_{\bar {k}}\in \left\{vertici\right\}$ $v_{\bar {k}}\in V\rightarrow \ v_{\bar {k}}\in \left\{vertici\right\}$ $v_{\bar {k}}\in V\rightarrow \ v_{\bar {k}}\in \left\{vertici\right\}$ .

Abbiamo quindi scoperto che $v_{\bar {k}}$ $v_{\bar {k}}$ $v_{\bar {k}}$ è uno dei vertici del poliedro primale.

Consideriamo adesso la funzione obiettivo: essa, in quanto funzione definita su un certo dominio, segue la regola per cui il valore che assume in un generico punto è sicuramente uguale o minore al massimo dei valori che può assumere, analiticamente $f(x)\leq \ max\ f(x)\ \ \forall x\in D$ $f(x)\leq \ max\ f(x)\ \ \forall x\in D$ $f(x)\leq \ max\ f(x)\ \ \forall x\in D$ ; questo, considerando che la nostra funzione cx è definita sul poliedro primale P significa che $cx\leq \ max\ cx\ \ \forall x\in P$ $cx\leq \ max\ cx\ \ \forall x\in P$ $cx\leq \ max\ cx\ \ \forall x\in P$ .

Questa proprietà vale anche per $\quad v_{\bar {k}}$ $\quad v_{\bar {k}}$ $\quad v_{\bar {k}}$ , che in quanto vertice appartiene al poliedro; quindi si ha che $\quad cv_{\bar {k}}\leq \ max\ cx\ \ \forall x\in P$ $\quad cv_{\bar {k}}\leq \ max\ cx\ \ \forall x\in P$ $\quad cv_{\bar {k}}\leq \ max\ cx\ \ \forall x\in P$ .

Per concludere è sufficiente mettera a sistema le due disuguglianze trovate: $\quad cv_{\bar {k}}\leq \ max\ cx$ $\quad cv_{\bar {k}}\leq \ max\ cx$ $\quad cv_{\bar {k}}\leq \ max\ cx$ e $\quad max\ cx\leq \ cv_{\bar {k}}$ $\quad max\ cx\leq \ cv_{\bar {k}}$ $\quad max\ cx\leq \ cv_{\bar {k}}$ . Appare chiaro come affinché esse valgano contemporaneamente deve risultare $\quad max\ cx=cv_{\bar {k}}$ $\quad max\ cx=cv_{\bar {k}}$ $\quad max\ cx=cv_{\bar {k}}$ .

Abbiamo così provato la nostra tesi, esiste un vertice del poliedro che è soluzione ottima del problema primale standard.

Osservazioni

Un facile errore di interpretazione del teorema fondamentale della programmazione lineare è quello di considerare la tesi nel senso che tutti gli ottimi sono vertici: è bene ricordare come il teorema ci garantisca che uno dei vertici, anche se potrebbero essere due o più (anche tutti), è ottimo. Tra l'altro questa condizione è sufficiente per risolvere un problema primale, in quanto, ai fini della ricerca operativa non ci interessa trovare tutte le soluzioni ottime, ma una sola, e inoltre per il teorema di caratterizzazione elementare dell'ottimalità le soluzione ottime locali di (P) sono anche ottime globali.

L'importanza del teorema è notevole, ma bisogna prestare attenzione ai casi nei quali non si può applicare, in pratica quando almeno una delle ipotesi non è rispettata:

Il poliedro può essere vuoto, ovvero ci sono troppi vincoli , non in senso solo numerico, ma anche solo perché in teoria bastano due semispazi per generare un' intersezione vuota
Il problema può non assumere un valore ottimo, ovvero la funzione può divergere verso valori positivi e infiniti
Il poliedro potrebbe non avere vertici, quindi perché quest'ipotesi sia verificata, P non deve contenere rette . Si può facilmente vedere che anche se P non ha vertici non è possibile escludere l'esistenza di un valore ottimo (che in questo caso sarebbe eventualmente raggiunto sull'insieme dei punti appartenenti a una certa retta).

Basi e soluzioni di base

Il teorema fondamentale della programmazione lineare indica la strada da seguire per ottimizzare problemi in forma primale standard: analizzare i vertici, dato che nelle condizioni determinate dalle ipotesi del suddetto teorema almeno uno di essi è v(P) , cioè un ottimo.

Supponendo che il problema abbia ottimo finito, dominio non vuoto e almeno un vertice se si vuole scrivere un algoritmo che trovi una soluzione ottima è chiaro che per prima cosa è necessario avere a disposizione un procedimento per trovare, dato il poliedro P , i suoi vertici.

Geometricamente si potrebbe pensare che essi siano tutte le intersezioni tra i vincoli (semispazi chiusi) del problema, ma non è così, anche se in questo insieme ci sono anche i vertici: è necessario quindi introdurre il concetto di base .

Considerando un problema di programmazione lineare nella forma primale $\left(P\right)={\begin{cases}\max \quad cx\\Ax\leq \ b\end{cases}}$ $\left(P\right)={\begin{cases}\max \quad cx\\Ax\leq \ b\end{cases}}$ $\left(P\right)={\begin{cases}\max \quad cx\\Ax\leq \ b\end{cases}}$ chiameremo base un insieme B di n indici di riga, $B\subseteq \left\{1,2,\ldots m\right\}$ $B\subseteq \left\{1,2,\ldots m\right\}$ $B\subseteq \left\{1,2,\ldots m\right\}$ , tale che la sottomatrice quadrata di lato n $A_{B}$ $A_{B}$ $A_{B}$ , ottenuta da A estraendo le righe con indici $i\in B$ $i\in B$ $i\in B$ , sia invertibile , cioè $det(A_{B})\neq \ 0$ $det(A_{B})\neq \ 0$ $det(A_{B})\neq \ 0$ .

La matrice $A_{B}$ $A_{B}$ $A_{B}$ prende il nome di matrice di base , gli $i\in B$ $i\in B$ $i\in B$ sono detti indici di base mentre si indicherà con N l'insieme degli mn indici di riga ( indici non di base ) che non appartengono a B .

In pratica si prende un certo numero, n , di vincoli, e se ne fa l'intersezione costruendo la matrice con le righe corrispondenti agli indici: se la matrice così ottenuta è invertibile allora significa che i vincoli presi non erano paralleli, quindi che si intersecavano.

A questo punto si deve trovare la suddetta intersezione, e per farlo si calcola la soluzione del sistema di n equazioni in n incognite formato dalle righe di B ; il sistema produrrà una soluzione, che prenderà il nome di soluzione di base . Questo punto , ottenuto tramite un'intersezione di vincoli, è candidato a essere vertice: per controllare che lo sia veramente è necessario sostituire le coordinate del punto all'interno degli altri vincoli non utilizzati e vedere se esso risulta ammissibile per essi. Se il punto (la soluzione di base) risulta ammissibile per tutti i vincoli non di base allora il punto trovato prende il nome di soluzione di base ammissibile .

La procedura risulta facilmente intuibile pensando a un poliedro in due dimensioni: si prendono tutti i vincoli (rette) a due a due ( n =2) e si controlla, attraverso il determinante della relativa matrice , se si intersecano (se non sono rette parallele, quindi zero intersezioni, o coincidenti, con infiniti punti di intersezione); in caso affermativo si trova il punto, che è una soluzione di base. Per vedere se quest'ultima è anche ammissibile si guarda se rispetta gli altri vincoli, cioè se il punto appartiene al poligono corrispondente alla regione ammissibile.

La procedura descritta in precedenza permette di individuare tutti e soli i vertici del poliedro primale, infatti esiste un teorema che dice che condizione necessaria e sufficiente affinché un punto sia un vertice è che sia una soluzione di base ammissibile.

Per quanto riguarda i vertici esiste anche un'altra loro possibile classificazione: una soluzione di base (vertice) si dice degenere se soddisfa almeno un vincolo non di base con l'uguaglianza: gli altri vertici che non soddisfano tale proprietà vengono detti non degeneri . Ritornando all'esempio di poliedro in due dimensioni una soluzione di base degenere è un vertice individuato dall'intersezione di tre ( n +1) o più rette .

Ecco la procedura analitica per trovare il vertice corrispondente a una base data ( n indici) per un problema del tipo $\left(P\right)={\begin{cases}\max \quad cx\\Ax\leq \ b\end{cases}}$ $\left(P\right)={\begin{cases}\max \quad cx\\Ax\leq \ b\end{cases}}$ $\left(P\right)={\begin{cases}\max \quad cx\\Ax\leq \ b\end{cases}}$ :

Si costruisce da A la sottomatrice quadrata $A_{B}$ $A_{B}$ $A_{B}$ selezionando le n righe di B
Si seleziona da b il vettore $b_{B}$ $b_{B}$ $b_{B}$ scegliendo le n righe di B
Si suppone che $det(A_{B})\neq \ 0$ $det(A_{B})\neq \ 0$ $det(A_{B})\neq \ 0$
Si calcola ${A_{B}}^{-1}$ ${A_{B}}^{-1}$ ${A_{B}}^{-1}$
La soluzione di base è $x={A_{B}}^{-1}b_{B}$ $x={A_{B}}^{-1}b_{B}$ $x={A_{B}}^{-1}b_{B}$
x si dice:
- Ammissibile se $A_{i}x\leq \ b_{i}\ \forall i\in N$ $A_{i}x\leq \ b_{i}\ \forall i\in N$ $A_{i}x\leq \ b_{i}\ \forall i\in N$
- Non ammissibile se $\exists i\in N:A_{i}x>\ b_{i}$ $\exists i\in N:A_{i}x>\ b_{i}$ $\exists i\in N:A_{i}x>\ b_{i}$
x si dice:
- Degenere se $\exists i\in N:A_{i}x=b_{i}$ $\exists i\in N:A_{i}x=b_{i}$ $\exists i\in N:A_{i}x=b_{i}$
- Non degenere se $A_{i}x\neq \ b_{i}\ \forall i\in N$ $A_{i}x\neq \ b_{i}\ \forall i\in N$ $A_{i}x\neq \ b_{i}\ \forall i\in N$

Algebra della PL

Una volta trovati i vertici, per utilizzare il teorema fondamentale della programmazione lineare si deve vedere quali di essi sono soluzioni ottime del problema. Per fare questo serve un test di ottimalità, cioè un procedimento di verifica che, applicato a un vertice, dica se esso può essere considerato un ottimo del problema; fondamento teorico necessario per arrivare a questo punto è quello della teoria delle dualità.

La teoria della dualità

La dualità nella ricerca operativa può essere interpretata come una corrispondenza tra due problemi formalizzati in un modello di programmazione lineare . La forma di dualità più importante e più conosciuta è quella che associa due problemi di Programmazione Lineare ( dualità lineare ), ed è quella che serve per stabilire condizioni di ottimalità per problemi in forma primale standard; tuttavia esistono anche altri tipi di dualità: ad esempio, in presenza di problemi di programmazione quadratica si parla di dualità quadratica , mentre in presenza di problemi di Programmazione lineare intera si parla di dualità lagrangiana .

La coppia di problemi che studieremo è la seguente:

Problema primale standard	Problema duale standard
$\max \sum _{i=1}^{n}c_{i}x_{i}$ $\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}$ $\min \sum _{j=1}^{m}y_{j}b_{j}$ $\min \sum_{j=1}^m y_j b_j$	(funzione obiettivo)
$\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_{i = 1}^n a_{1,i} x_i \leq b_1$	$\sum _{j=1}^{m}y_{j}a_{j,1}=c_{1}$ $\sum _{j=1}^{m}y_{j}a_{j,1}=c_{1}$ $\sum_{j = 1}^m y_j a_{j,1} = c_1$
$\dots$ $\dots$ $\dots$	$\dots$ $\dots$ $\dots$	(vincoli)
$\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_{i = 1}^n a_{m,i} x_i \leq b_m$	$\sum _{j=1}^{m}y_{j}a_{j,n}=c_{n}$ $\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$ $y_{j}\geq 0\qquad j=1,\dots ,m$ $y_j \geq 0 \qquad j = 1, \dots, m$

Quindi se consideriamo un problema di PL in formato primale standard possiamo associarvi un problema di PL in una forma duale standard; sfruttando i concetti di matrici e vettori possiamo scrivere questa corrispondenza così:

{\begin{cases}\max \quad cx\\Ax\leq \ b\end{cases}}

{\begin{cases}\max \quad cx\\Ax\leq \ b\end{cases}}

{\begin{cases}\max \quad cx\\Ax\leq \ b\end{cases}}

{\begin{cases}\min \quad yb\\yA=\ c\\y\geq \ 0\end{cases}}

{\begin{cases}\min \quad yb\\yA=\ c\\y\geq \ 0\end{cases}}

{\begin{cases}\min \quad yb\\yA=\ c\\y\geq \ 0\end{cases}}

Ai fini della creazione di un test di ottimalità introduciamo solamente alcuni brevi elementi teorici a propositi del problema duale standard (rimandando la trattazione alla pagina apposita ):

mentre il problema in forma primale standard si scriveva con (P) , quello in forma duale standard si scrive (D)
il valore ottimo del duale è indicato con v(D)
il poliedro duale è definito come: $D=\left\{yA=c,\ \ y\geq \ 0\right\}$ $D=\left\{yA=c,\ \ y\geq \ 0\right\}$ $D=\left\{yA=c,\ \ y\geq \ 0\right\}$
per minimizzare il problema duale si ricercano delle soluzioni di base (avendo una base B ),

che saranno quelle trovate risolvendo il sistema prendendo solo le variabili relative agli indici in base (e le altre nulle), o analogamente le componenti del vettore $c{A_{B}}^{-1}$ $c{A_{B}}^{-1}$ $c{A_{B}}^{-1}$ e $y_{N}=0$ $y_{N}=0$ $y_{N}=0$

le soluzioni di base, relative a una base B , possono essere ammissibili, nel caso rispettino $\forall i\in B\ y_{i}\geq \ 0$ $\forall i\in B\ y_{i}\geq \ 0$ $\forall i\in B\ y_{i}\geq \ 0$ , prendendo il nome di vertici del poliedro duale
I vertici duali possono essere degeneri o no, nel caso rispettino o meno la condizione $\exists i\in B:\ y_{i}=0$ $\exists i\in B:\ y_{i}=0$ $\exists i\in B:\ y_{i}=0$

Un'importante proprietà dei problemi duali lineari è che il duale del duale è il primale, cioè riconducendo il problema duale alla forma primale e applicando la corrispondenza di cui sopra si riotterrà una formulazione equivalente del problema primale.

Questo significa che l'operazione di associazione primale-duale è un' operazione involutoria , cioè se applicata a se stessa torna la situazione di base.

Ottimalità duale e primale

Grazie alle conoscenze acquisite in precedenza adesso si è in grado di formulare il procedimento che dice quali vertici del problema primale standard sono soluzioni ottime; esiste infatti un teorema che ci garantisce le condizioni sufficienti di ottimalità per soluzioni di base (non soli del problema primale ma anche di quello duale): date due soluzioni di base $\ x\in P,\ \ y\in D$ $\ x\in P,\ \ y\in D$ $\ x\in P,\ \ y\in D$ si ha che se esse sono ammissibili (sono vertici dei rispettivi poliedri ) rispettivamente per (P) e (D) allora sono ottime rispettivamente per (P) e (D) .

La dimostrazione di questo fondamentale teorema prevede la conoscenza di un importantissimo teorema della programmazione lineare , molto utile per costruire i fondamenti teorici dell'algoritmo del simplesso , il teorema degli scarti complementari .

Dimostrazione

Alla luce del teorema degli scarti complementari, che ci garantisce che se si hanno $\ {\bar {x}}\in P,\ \ {\bar {y}}\in D$ $\ {\bar {x}}\in P,\ \ {\bar {y}}\in D$ $\ {\bar {x}}\in P,\ \ {\bar {y}}\in D$ , ammissibili rispettivamente per (P) e (D), allora si ha che esse sono ottime se e solo se ${\bar {y}}\left(b-A{\bar {x}}\right)=0$ ${\bar {y}}\left(bA{\bar {x}}\right)=0$ ${\bar {y}}\left(b-A{\bar {x}}\right)=0$ .

Quindi per dimostrare la tesi basta dimostrare che dati due vertici, primale e duale (associati), essi soddisfano sempre ${\bar {y}}\left(b-A{\bar {x}}\right)=0$ ${\bar {y}}\left(bA{\bar {x}}\right)=0$ ${\bar {y}}\left(b-A{\bar {x}}\right)=0$ , e quindi sono ottime.

Prendiamo due generiche soluzioni di base ammissibili, ${\breve {x}}\in P,\quad {\breve {y}}\in D$ ${\breve {x}}\in P,\quad {\breve {y}}\in D$ ${\breve {x}}\in P,\quad {\breve {y}}\in D$ ; sappiamo, per la struttura dei vertici duali, che ${\breve {y}}=\left({\breve {y}}_{B},{\breve {y}}_{N}\right)=\left({\breve {y}}_{B},0\right)$ ${\breve {y}}=\left({\breve {y}}_{B},{\breve {y}}_{N}\right)=\left({\breve {y}}_{B},0\right)$ ${\breve {y}}=\left({\breve {y}}_{B},{\breve {y}}_{N}\right)=\left({\breve {y}}_{B},0\right)$ perché le variabili corrispondenti agli indici non in base sono nulle. Sappiamo inoltre che il vettore di tali soluzioni è un vettore riga di dimensione $1\times m$ $1\times m$ $1\times m$ .

Adesso consideriamo gli scarti della generica soluzione, ammissibile, del problema primale standard: essi saranno del tipo ${S_{B} \choose S_{N}}$ ${S_{B} \choose S_{N}}$ ${S_{B} \choose S_{N}}$ , cioè un vettore colonna, di dimensione $m\times 1$ $m\times 1$ $m\times 1$ , con gli scarti generati dai vincoli in base e da quelli non in base. Ma dal momento che sappiamo che gli scarti di base di una soluzione di base sono nulli (essendo il vertice di P ottenuto proprio dal sistema che annulla la matrice con le righe corrispondenti agli indici di base), allora il vettore degli scarti diventa ${0 \choose S_{N}}$ ${0 \choose S_{N}}$ ${0 \choose S_{N}}$ .

A questo punto possiamo vedere se ${\breve {y}}\left(b-A{\breve {x}}\right)=0$ ${\breve {y}}\left(bA{\breve {x}}\right)=0$ ${\breve {y}}\left(b-A{\breve {x}}\right)=0$ : operazione possibile dal momento che il vettore delle soluzioni del primale ha m componenti, n in base e le altre altri no, e analogamente gli scarti del primale $\left(b-A{\breve {x}}\right)={S_{B} \choose S_{N}}$ $\left(bA{\breve {x}}\right)={S_{B} \choose S_{N}}$ $\left(b-A{\breve {x}}\right)={S_{B} \choose S_{N}}$ sono uno per vincolo, m , e n di questi sono scarti di base.

Svolgiamo quindi il prodotto riga-colonna che ci interessa: ${\breve {y}}\left(b-A{\breve {x}}\right)=\left({\breve {y}}_{B},{\breve {y}}_{N}\right)\cdot {S_{B} \choose S_{N}}=\left({\breve {y}}_{B},0\right)\cdot {0 \choose S_{N}}=0$ ${\breve {y}}\left(bA{\breve {x}}\right)=\left({\breve {y}}_{B},{\breve {y}}_{N}\right)\cdot {S_{B} \choose S_{N}}=\left({\breve {y}}_{B},0\right)\cdot {0 \choose S_{N}}=0$ ${\breve {y}}\left(b-A{\breve {x}}\right)=\left({\breve {y}}_{B},{\breve {y}}_{N}\right)\cdot {S_{B} \choose S_{N}}=\left({\breve {y}}_{B},0\right)\cdot {0 \choose S_{N}}=0$ . Abbiamo così dimostrato, per il teorema degli scarti complementari , la tesi.

Ora siamo in grado di formulare il procedimento che ci dice quali vertici siano soluzioni ottime, ovvero possiamo scrivere il cosiddetto test di ottimalità: dato un problema in forma primale (P) e l'associato problema duale (D) e dato un vertice $x\in P$ $x\in P$ $x\in P$ si opera così:

Si trova la soluzione di base duale con la stessa base usata per x , soluzione che chiameremo y
Se y è una soluzione di base ammissibile allora x è ottima per il problema primale (e anche y per il duale)

Come si vede il procedimento semplifica moltissimo le operazioni da fare per massimizzare un problema in forma primale, ma è comunque assai lungo perché richiede, nel peggior caso, tante verifiche di ottimalità quanti sono i vertici, e nel caso medio (per problemi con moltissimi vincoli e variabili) un numero improponibile operativamente di passi.

Se allora ai fini pratici il test di ottimalità, pur essendo molto utile, necessita di conoscere in teoria tutti i vertici del poliedro in questione, o comunque una gran parte, e dal momento che nei problemi di produzione industriale vengono fuori moltissimi vincoli e moltissimi vertici, bisogna trovare un modo intelligente per procedere tra i vertici del poliedro, e questo sarà proprio l'algoritmo del simplesso primale , caso particolare del simplesso generico.

Voci correlate

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