1. CAPITOLUL 1 – INTRODUCERE IN OPTIMIZAREA LINIARĂ ………………………….. ….. 3 1.1 Evoluția teoriei optimizării… [605736]

CUPRINS :

1. CAPITOLUL 1 – INTRODUCERE IN OPTIMIZAREA LINIARĂ ………………………….. ….. 3
1.1 Evoluția teoriei optimizării ………………………….. ………………………….. ………………………….. …….. 3
1.2 Concepte fundamen tale din teoria optimizării ………………………….. ………………………….. ………. 4
1.3 Definirea unei probleme de optimizare ………………………….. ………………………….. ………………… 6
1.4 Probleme de optimizare ………………………….. ………………………….. ………………………….. …………. 6
2. CAPITOLUL 2 – PRELIMINARII ………………………….. ………………………….. ………………….. 10
2.1 Nota ții Și Proprietăți Ale Sistemelor Liniare ………………………….. ………………………….. ………. 10
2.2 Forme Ale Problemelor De Programare Liniară ………………………….. ………………………….. ….. 12
2.2.1 Forma Generală / Standard A Unei Probeleme De Optimizării Liniare ………………………….. ……… 12
2.2.2 Forma Canonică A Unei Probeleme De Optimizării Liniare ………………………….. …………………….. 13
2.2.3 Forma Mixtă A Unei Probeleme De Optimizării Liniare ………………………….. …………………………. 15
2.3 Rezulta te Fundamentale Pentru Problema De Optimizare Liniară ………………………….. ……… 16
2.3.1. Spațiul De Căutare A Soluțiilor ………………………….. ………………………….. ………………………….. ……… 16
2.3.2. Criteriul De Optim (Funcția Obiectiv ………………………….. ………………………….. ………………………….. .. 16
2.3.3. Restricții ………………………….. ………………………….. ………………………….. ………………………….. …………… 16
2.4 Etape În Rezolvarea Problemelor De Optimizare ………………………….. ………………………….. … 17
2.5 METODA SIMPLEX DEZVOLTATĂ DE GEORGE B. DANTZIG 1947 – 1951 ……………. 22
2.5.1 Algoritmul Simplex ………………………….. ………………………….. ………………………….. ……………………. 22
2.5.2 Algoritmul Simplex Primal ………………………….. ………………………….. ………………………….. …………. 24
2.5.3 Tabelul Simplex ………………………….. ………………………….. ………………………….. ………………………… 27
2.5.4 Algoritmul Simplex Dual ………………………….. ………………………….. ………………………….. ……………. 29
3. CAPITOLUL 3 – METODE DE DESCOMPUNERE ………………………….. …………………….. 32
3.1 Pricipiul de descompunere Dantzig – Wolfe ………………………….. ………………………….. ……….. 34
3.2 Algoritmul de descompunere Dantzing – Wolfe ………………………….. ………………………….. ….. 37
3.3 Programul principal restrâns ………………………….. ………………………….. ………………………….. … 38
3.4 Metode de Partiționare și Relaxare (metoda relaxării și metoda restrângerii) …………………… 39
3.5 Principiul de relaxare ………………………….. ………………………….. ………………………….. ………….. 40
3.6 Agloritmul general de partiționare și relaxare ………………………….. ………………………….. ……… 40
3.7 Algoritmul lui Ritter ………………………….. ………………………….. ………………………….. ……………. 42
3.8 Algoritmul lui Rosen ………………………….. ………………………….. ………………………….. …………… 47
3.9 Metoda de descompunere a lui Benders ………………………….. ………………………….. ……………… 51

2
4. CAPITOLUL 4 – EXEMPLE NUMERICE ………………………….. ………………………….. ………. 52

3

1. CAPITOLUL 1 – INTRODUCERE IN OPTIMIZAREA LINIARĂ
Scurt istoric – nota istorica

Progamarea sau Optimizarea liniară, ca disciplină matematică, a apă rut la mijlocul secolului trecut ,
primele lucrări fiind publicate de L. Kantorovich (1939) și F. Hitchcock (1941 ).

Primele probleme rezolvate se refereau la organizarea optimă a transporturilor maritime, necesitățile
de aprovizionare a frontului, planifi carea misiunilor aviației de bombardament.

În 1947 G. Dantzig și J. Von Neu mann creează metoda simplex care stă l a baza rezolvării
problemelor de programare liniară.

L. Kantorovich F. Hitchcock G. Dantzig J. Von Neumann

Ulterior programarea liniară a cunoscut un mare avânt prin lucrările unor matematicieni și economiști
ca T. Koopmans, L. Ford, D. Fulkerson, W. Cooper, H. Kuhn, găsindu -și un câmp foarte larg de aplicații
în econom ie, matematică, fizică, chimie.
Necesitățile reale ale vieții economice au condus la apariția și dezvoltarea altor tipuri de programări, cum
ar fi:

• programarea pătratică,
• programarea convexă,
• programarea în numere întregi,
• programarea stohastică,
• programarea dinamică,

toate acestea fiind înglobate în termenul generic de programare matematică.

1.1 Evoluția teoriei optimizării

Optimizarea are aplicații în extrem de numeroase domenii, dintre care putem aminti următoarele:

– economie : alocarea resu rselor în logistică, invesții, calcularea unui portofoliu optim;

4
– științele exacte : estimarea și proiectarea de modele pentru seturi de date măsurate, proiectarea de
experimente;

– inginerie : proiectarea și operarea în domeniul sistemelor tehnologice (p oduri, autovehicule, dispozitive
electronice), optimizarea motoarelor de căutare, control optimal, procesarea de semnale.

– înainte de 1990 : cercet ări operaționale (finanțe, logistică , manufacturing, scheduling) ,

– după 1990 : aplicații inginereș ti (con trol, procesare de semnal, moto are de căutare, rețele); medicină
(tomografie); biologie (recunoașterea de gene); fizică (predicț ia vremii).

Apariția teoriei optimizării în problemele de extreme (minimum/maximum) datează cu câteva secole
înaintea lui Hrist os.

În 1744 Leonhard Euler, unul din cei mai mari matematicieni spunea că:
“Namely, because the shape of the whole universe is most perfect and, in fact, designed by the wisest
creator, nothing in all of the world will occur in whic h no maximum or minimum rule is somehow shining
forth .”

În latina: “…nihi omnino in mundo contingint, in quo non maximi minimive ratio quapiam eluceat.”
Prin traducere în limba română întelegem că “Deoarece forma întregului univers este cea mai
perfec tă și proiectată de cel mai întelept creator, nu există nimic în lume care se va întampla în care nici
regula minimului sau regula maximului într -un fel care să stralucească.

Putem trata această afirmație fermă de Euler, ca principiul fundamental al anal izei variaționale. Acest
principiu justifică o varietate izbitoare de implementări de optimizare / variaționale abordări de rezolvare
a numeroase probleme în matematică și științe aplicate, care pot să nu fie de natură variaționale.
Într-adevăr, în suși conceptul de derivată introdus de Fermat în 1637 prin atingerea pantei la grafi cul
unei funcții a fost motivat de rezolvarea unei probleme de optimizare, a condus la ceea ce se numește
acum staționar principiul lui Fermat. În afară de cererile de opti mizare, acesta principiu joacă un rol
crucial în dovedirea celui mai important rezultat, in clusiv calcularea valorii medii .

De fapt, conceptul de derivat ă a funcției (una din cele mai importante construcții matematice) a fost
introdus cu scopul rezolvării unei probleme de optimizare.

1.2 Concepte fundamentale din teoria optimizării

Matematicienii din Antichitate manifestau interes pentru un număr d e probleme de tip izoperimetric
de exemplu care este curba închisă de lungime fixată ce înconjoară supraf ața de arie maximă ?
În această perioadă au fost folosite abordări geometrice pentru rezolvarea problemelor de optimizare și
determinarea punctului de optim. Cu toate acestea, o soluție riguroasă pentru aceste tipuri de problem e
nu a fost găsită până în sec olul al XIX -lea. Problema izoperimetrică îș i are originile în legenda reginei
Dido, descrisă de Virgil în Eneida .
Didona (secolul al IX-lea î.Hr. ) era fiica regelui din Tyr, Mutto, și sora lui Pygmalion (nu sculptorul
îndrăgostit de propria operă). Tyrul era o bogată cetate feniciană și la moartea regelui a fost moștenită
de cei doi frați. A fost căsătorită cu Sichaeus, un înalt dregător și preot, dar fratele Didonei care a dorit să

5

pună mâna pe averea lui, l -a ucis pe acesta și chiar s -a hotărât să -și ucidă și sora. Didona și -a iubit soțul
cu devoțiune și s -a jurat să -i rămână credincioasă și după moarte. Aflând ce făcuse și ce punea la cale
Pygmalion și îndurerată atât de moartea soțului cât și de trădarea fratelui, și -a încărcat averea pe corăbii
și, însoțită de slujitorii săi credincioși, a plecat pe Mediterana. După peregrinări nenumărate se oprește pe
țărmul de nord al Africii, în dreptul unei locații numită Byrsa (în Tunisul de astăzi). Aici le cere
localnicilor să -i ofere un loc pentru a -și sta bili sălașul. Aceștia i-au oferit, în bătaie de joc, atâta
suprafață de pământ cât poate cuprinde cu o piele de bou (în traducere Byrsa înseamnă piele de bou).
Ambiguitatea termenilor cererii berberilor a condus -o la o rezolvare ingenioasă a problemei: a t ăiat pielea
de bou în fâșii foarte subțiri, le -a pus cap la cap și a înconjurat cu ele un deal de pe litoral. Presupunem
că pielea boului ar fi avut 4 metri pătrați din care s-au tăiat fâșii late de 2,5mm. Rezultă 800 de fâșii
lungi de câte 2 metri, deci perimetrul înconjurat ar fi avut valoarea de 1600 metri, care este în
același timp lungimea cercului de la baza dealului. Adică aproximativ 20 de hectare , suficient pentru
un început. În perioada de glorie a cetății, lungimea zidurilor de apărare a ajuns la 35 Km, în portul bine
amenajat și protejat încăpeau și câte 220 de corăbii de război. În decursul timpului cetatea Cartaginei a
pus mari probleme Romei, Cato cel Bătrân (234 – 146 î.Hr.) încheindu -și fiecare cuvântare din Senat cu
expresia “censeo carthag inem esse delendam” (cred că trebuie să distrugem Cartagina). Legenda spune
că fenicienii au tăiat piel ea de bizon în fâsii subțiri și în acest fel, au reușit să îngrădească o suprafață
foarte mare. Nu este exclus faptul ca supușii reginei să fi rezolvat o versiune practică a problemei.

Cetatea Catarginei Regina Didona ilustrată pe o monedă

Rezolvarea problemei de către Didona este dovada că ea stăpânea cunoștințe de matematică :
dintre toate suprafețele cu același perimetru, cea mai mare este cea a cercului. Această problemă, numită
a izoperimetrelor a fost studiată de Bernoulli. Mai mult, fiind vorba de un deal (asimilat cu un con), aria
suprafeței laterale a acestuia este mai mare decât aria bazei (oblica este mai mare decât perpendiculara).
Problemele de maxim sunt unele dintre cele mai interesante probleme de matematică. La început se
puneau probleme geometrice, și de multe ori soluția intuitivă era cea acceptată. Cu timpul probl emele
de maxim și minim au devenit probleme de calcul diferențial și integral sau de programare liniară și
optimizare, atât de des folosite în economie sau în teoria probabilităților , și în câte alte domenii .
Există și alte metode pe care matematicie nii din perioada ce precedă calculul diferențial le foloseau
pentru a rezolva probleme de optimizare,și anume abordările algebrice . Una dintre cele mai elegante este
inegalitatea mediilor .

Optimizarea deciziilor a devenit o știință începând cu a dou a jumătate a secolului XIX -lea, perioadă
în care calculul diferential a fost puternic dezvoltat. Folosirea metodei gradient ( adică utilizarea derivatei
funcț iei obiectiv) pentru minimizare a fost prezentată de Cauchy în 1847.
Metodele de optimizare moderne au fost pentru prima dată propuse într -o lucrare de Courant (1943)
unde a fost introdusă noțiunea de funcție penalitate, în lucrarea lui Dantzig (1951) unde a fost prezentată

6
metoda simplex pentru programare liniară și la Karush -Kuhn -Tucker care derivează condițiile de
optimalitate pentru probleme de optimizare constrânsă (1939,1951).

1.3 Definirea unei probleme de optimizare

În sens larg , optimizare a = acțiunea de stabilire, pe baza unui criteriu prestabilit, a celei mai bune
decizii într -o situație dat ă când sunt posibile mai multe decizii, precum și acțiunea de implementare a
deciziei stabilite precum și a rezultatului acesteia.
În sens restrâns , optimizare a = doar ac țiunea de stabilire a celei mai bune decizii (solu ții), decizie optimal
(soluție optimă ).

Metoda de optimizare este ansamblul de mijloace utilizate pentru determinarea deciziei optimale pe
baza modelului mediului și a funcției obiectiv.

Metoda simplex rezolvat ă cu algoritmul lui Dantzig – printre cele mai vechi, d ezavantaj: cre șterea
complexit ății pe m ăsura cre șterii num ărului variabilelor asociate problemei. Pentru un num ăr de două
variabile problemele de programare liniar ă pot fi rezolvate convenabil prin metode grafo -analitice .

Observații:

1. Orice problem ă de maximizare poate fi transformat ă într-o problem ă de minimizare prin schimbarea
semnului funcției obiectiv.
2. Într -o problemă de optimizare valoarea funcției obiectiv e mai pu țin important ă, conteaz ă doar ca
valoarea sa s ă fie minim ă. Sunt probleme de op timizare cu restricții de tip egalitate
și de tip inegalitate , cu aplica ții în multe domenii și considerate ca parte a problemelor de cercetare
opera țional ă.

1.4 Probleme de optimizare

Problemele de optimizare reprezintă una dintre clasele de probleme cel mai frecvent întâlnite în
aplicații care necesită:

➢ Planificare (planificarea și / sau stabilirea ordinii de execuție a unor activități, alocarea de resurse
unor activități),
➢ Modelare (construirea unui model care să se potrivească cât mai bine cu date le experimentale),
➢ Adaptare (învățare) (modificarea comportamentului unui sistem astfel încât să aibă
comportamentul dorit).

7
Exem ple de probleme de optimizare liniară:
a) Problema planului optim de producție
Fie mașinile 𝑀1,𝑀2,𝑀𝑛, …, care consumă produsele 𝑃1,𝑃2,𝑃𝑚, …, în cantități date pe unitatea de timp,
anume 𝑎𝑖𝑗 din 𝑃𝑖 pentru mașina 𝑀𝑗, 1 ≤ i ≤ m, 1≤ j ≤ n. (Dacă 𝑀𝑗 produce în unitatea de timp cantitatea
𝑎𝑖𝑗 din 𝑃𝑖, atunci 𝑎𝑖𝑗 > 0, dacă consumă atunci 𝑎𝑖𝑗 < 0 , iar dacă 𝑎𝑖𝑗 = 0, 𝑀𝑗 nu produce și nu
consumă 𝑃𝑖). Producția (respectiv consumul) produsului 𝑃𝑖 nu trebuie să fie sub limita (respectiv să
depășească) 𝑏𝑖, 𝑏𝑖 ≥ 0(respectiv – 𝑏𝑖 dacă 𝑏𝑖 < 0) pentru 1≤ i ≤ m.

Fie 𝑥𝑗 timpul de funcționare al mașinii 𝑀𝑗, iar 𝑐𝑗 beneficiul obținut prin funcționarea lui 𝑀𝑗 în unitatea
de timp, 1≤ j ≤ n. Un sistem de numere reale,( 𝑥1,𝑥2,𝑥3,…,𝑥𝑛), constituie un plan optim de producție,
dacă maximizeză beneficiul total adică funcția:
𝑓=∑𝑐𝑗𝑥𝑗𝑛
𝑗=1 în condițiile restictive
∑𝑎𝑖𝑗𝑥𝑗≥𝑏𝑖,1≤𝑖≤𝑚 ș𝑖 𝑥𝑗 ≥0𝑛
𝑗=1

Dacă 𝑐𝑗 reprezintă costul funcționării mașinii 𝑀𝑗 în unitatea de timp, atunci se va cere minimizarea
funcției de cost:
𝑓=∑𝑐𝑗𝑥𝑗𝑛
𝑗=1
b) Problema dietei (a amestecului)
Problema dietei a devenit o ilustrare clasica a programarii liniare, fiind întâlnita în mai
toate textele de specialitate. Ea se ocupa cu hranirea unei colectivitati, de exemplu vreau să determinăm
cantitățile 𝑥𝑗 din alimentele 𝐴𝑗, 1≤ j ≤ n, alcătuind o dietă ( 𝑥1,𝑥2,𝑥3,…,𝑥𝑛), astfel încât costul acesteia f =
∑𝒄𝒋𝒙𝒋𝒏
𝒋=𝟏 , să fie minim , unde 𝑐𝑗 reprezintă costul unitar al alimentului 𝐴𝑗, dacă se mai cunoaște
componența în substanțe nutritive ( 𝑆1,𝑆2,𝑆3,…,𝑆𝑚), (cum ar fi: glucide, lipide, vitamine) a alimentelor 𝐴𝑗,
1≤ j ≤ n, dată prin matricea: ( 𝑎𝑖𝑗)1 ≤ 𝑖 ≤ 𝑚
1≤ 𝑗 ≤ 𝑛 unde 𝑎𝑖𝑗 este cantitatea de substanță 𝑆𝑖, conținută în unitatea din
alimentul 𝐴𝑗, și se cere ca fiecare dietă să conțină cel puțin cantitățile 𝑏𝑖 din substanța 𝑆𝑖, 1≤ i ≤ m.
Deci, matematic probl ema se transcrie:
𝑚𝑖𝑛∑𝑐𝑗𝑥𝑗𝑛
𝑗=1 în condiții restrictive :
∑𝑎𝑖𝑗𝑥𝑗 𝑛
𝑗=1≥𝑏𝑖,1≤ 𝑖 ≤ 𝑚
𝑥𝑗 ≥0 𝑗=1,2,…

Din nou au fost tă cit utilizate ipotezele de liniaritate întâlnit e si în modelul precedent.

8
c) Problema folosirii optime a resurselor
O unitate economică trebuie să producă produsele 𝑃1,𝑃2,…,𝑃𝑛, având la dispoziție cel mult cantitățile
𝑏1,𝑏2,…,𝑏𝑚, din resursele, 𝑅1,𝑅2,…,𝑅𝑚. Știind că producerea unei unități din produsul 𝑃𝑗 necesită
cantitatea 𝑎𝑖𝑗 din resursa 𝑅𝑖 și că prin livrarea unei unități din același produs se obține beneficiul 𝑐𝑗, 1≤ j
≤ n se cere să se determine cantitățile ( 𝑥1,𝑥2,𝑥3,…,𝑥𝑛), din produsele 𝑃1,𝑃2,…,𝑃𝑛, astfel ca beneficiul
să fie maxim. Deci vom avea:
𝑚𝑎𝑥∑𝑐𝑗𝑥𝑗𝑛
𝑗=1 în condiții restrictive :
∑𝑎𝑖𝑗𝑥𝑗 𝑛
𝑗=1≥𝑏𝑖,1≤ 𝑖 ≤ 𝑚
𝑥𝑗 ≥0 𝑗=1,2,…

d) Problema de transport
Problema standard de transport consta în alegerea modalității de a apr oviziona cu marfă de la m
depozite , n consumatori în condițiile:
1. Se cunosc cantitațile de marfă solicitate de fiecare consumator și cele de care dispune fiecare depozit;
2. Totalul cererilor este egal cu totalul mărfii disponibile;
3. M arfa se expediază direct consumatorului;
4. Costul transportului este proporțional cu cantitatea de marfa expediată.
Soluția problemei este optimă dacă asigură aprovizionarea consumatorilor cu minimum de cheltuieli de
transport. Problema a fost enunțata în forma standard de F. L. Hithcock în 1941 și rezolvată printr -o
metodă care nu utilizează proprietățile speciale ale problemei decât în determinar ea soluției inițiale. În
1947, T. C. Koopmans publică o lucrare care conține importante îmbunătățiri ale metodei de rezolvare,
astfel, problem ele standard de transport sunt tratate sub denumirea de problema Hithcock -Koopma ns.
Pentru formularea matematică a problemei de transport vom folosi urmă toarele notații:
• 𝑎𝑖 – cantitatea de marfă disponibilă din depozitul i cu i =1,𝑚̅̅̅̅̅̅
• 𝑏𝑗 – cantinatea de marfă cerută de consumatorul j
• 𝑐𝑖𝑗 – costul transportului unei unități de marfă de la depozitul i consumatorului j
• 𝑥𝑖𝑗 – cantitatea de marfă transportată de la depozitul i la consumatorul j
Se cere să se organizeze transportul mărfii de la depozite la consumator astfel încât costul total
să fie minim.
Cu aceste notații, modelul problemei standard este:{∑𝑥𝑖𝑗=𝑎𝑖𝑛
𝑗=1 ,∀ 𝑖=1,𝑚̅̅̅̅̅̅
∑𝑥𝑖𝑗=𝑚
𝑖=1𝑏𝑗,∀ 𝑗=1,𝑛̅̅̅̅̅
𝑥𝑖𝑗≥0,𝑝𝑒𝑛𝑡𝑟𝑢 𝑖=1,𝑚̅̅̅̅̅̅ ș𝑖 𝑗=1,𝑛̅̅̅̅̅

9
Cu condiția:
∑𝑎𝑖𝑚
𝑖=1=∑𝑏𝑗𝑛
𝑗=1
(oferta tot ală = cerere totală)
Exemplele prezentate anterior conduc la rezolvarea unor probleme matemetice asemănătoare.

10
CAPITOLUL 2 – PRELIMINARI I

2.1 NOTA ȚII ȘI PROPRIETĂȚI ALE SISTEMELOR LINIARE

Notam A ϵ ℝ𝑚 𝑥 𝑛 o matrice cu m linii si n coloane de forma:
A = (𝑎11⋯𝑎1𝑛
⋮⋱⋮
𝑎𝑚1⋯𝑎𝑚𝑛) = (𝑎𝑖𝑗)1⩽i⩽m
1≤𝑗≤𝑛
unde 𝑎𝑖𝑗ϵ ℝ, 1⩽i⩽m, 1≤𝑗≤𝑛, sunt ele mentele matricei A. Spunem c ă matricea A este de dimensiune m x n.
Facem transpusa matricei, pe care o vom nota cu AT și va fi de forma:
AT = (𝑎11⋯𝑎𝑚1
⋮⋱⋮
𝑎1𝑛⋯𝑎𝑚𝑛) = (𝑎𝑗𝑖)1⩽j⩽n
1≤𝑖≤𝑚 evident, AT este de dimensiune n x m.
Dacă m = n , atunci A ϵ ℝ𝑚 𝑥 𝑛se num ește matri ce pătratică de ordinu l n.
Pe mulțimea matricelor d e aceași dimensiune putem defin i operația de adunare: A ϵ ℝ𝑚 𝑥 𝑛și
B ϵ ℝ𝑚 𝑥 𝑛, avem: A + B = (𝑎𝑖𝑗+ 𝑏𝑖𝑗)1⩽i⩽m
1≤𝑗≤𝑛.
Înmulț irea matricei A cu un scalar α ϵ ℝ este de forma: αA = (α𝑎𝑗𝑖)1⩽i⩽m
1≤𝑗≤𝑛 = Aα.
În raport cu aceste operații, mulțimea matricelor de aceași dimensiune formează un spațiu vectorial peste
corpul numerelor reale .
Avem A ϵ ℝ𝑚 𝑥 𝑘 și B ϵ ℝ𝑘 𝑥 𝑛, definim produsul : AB = C ϵ ℝ𝑚 𝑥 𝑛, iar elementele matricei produs C se
calculează astfel:
𝑐𝑗𝑖 = ∑𝑎𝑖𝑙𝑏𝑙𝑗𝑘
𝑙=1 , 1⩽i⩽m,1≤𝑗≤𝑛.

Determinantul unei matrice pătratice A ϵ ℝ𝑚 𝑥 𝑛 este egal cu:
det A = |A| = ∑ℇ(𝜎)𝑎1𝜎(1)𝑎2𝜎(2) 𝜎𝜖𝑆𝑛… 𝑎𝑛𝜎(𝑛)
unde 𝑆𝑛 este mulțimea permutărilor σ de ordinul n, iar ℇ(𝜎) este signatura permutării σ.
Dacă determinanutul matricei A este diferit de 0, A se numește matrice nesingulară, iar în acest caz,
exista o unică matrice A-1 ϵ ℝ𝑚 𝑥 𝑛, num ită “matricea inversă” , cu urm ătoarea proprietate:
A A-1 = A-1 A = I n
unde I n ϵ ℝ𝑚 𝑥 𝑛 este matricea unitate de dimensiune m x n.
Considerăm următorul sistem de ecuații liniare:

11
A x = b, (1)
unde variabila vectorială x ϵ ℝ𝑛, xi, i = 1,𝑛̅̅̅̅̅, ale sistemului (1).
Avem:
Ai = ( 𝑎𝑖1,𝑎𝑖2,… ,𝑎𝑖𝑛) unde “i” este linia matricei A,
Aj = ( 𝑎1𝑗,𝑎2𝑗,… ,𝑎𝑚𝑗) unde “j” este coloana matricei A.
Putem scrie sistemul de ecuații în următoarele forme echivalente:
Ai x = b i , i = 1,𝑛̅̅̅̅̅ sau ∑𝐴𝑗𝑛
𝑗=1𝑥𝑗 = b.
Prin urmare sistemul de ecuații are soluții dacă și numai dacă rang (A) = rang (A ⁝ b) conform teoremei
Kronecker – Capelli care ne s pune că u n sistem de ecuatii este compatibil daca si numai daca rang A =
rang A’.
Fie rang (A) = rang (A ⁝ b) = k . Se vor numi ecuații principale , respectiv variabile principale , ale
căror coeficien ți care intra în compunera unui minor de ordin k nenul, analog se vor numi ecuații
secundare , respectiv variabile secundare .
Luăm orice vector x ϵ ℝ𝑛, care satisface sistemul de ecuații format din ecuații principale satisface și
ecuații secundare, care pot fi eliminate fără a influența natura sis temului inițial. Considerăm că ecuațiile
secundare sunt eliminate din sistemnul de ecuații (1) și vom avea:
rang (A) = m ≤ n.
• dacă m = n , sistemul (1) are o soluție unică x = A-1 b,
• dacă m < n , atunci sistemul are o infinitate de soluții.
Vectorul x ϵ ℝ𝑛 se numește soluția sistemului (1) dacă verifică A x = b, această soluție a sistemului
este numită soluție de bază , dacă componentele ei sunt diferite de zero corespund unor coloane liniar
independente ale lui A. Deoarece rang (A) = m, cel mult m comp onente ale unei soluții de bază pot fi
nenule. Dacă soluția de bază are exact m componente nenule, ea se numește nedegenerată , în caz
contrar este degenarată .

DEFINIREA PRINCIPALELOR CONCEPTE DE OPTIMIZARE MATEMATICĂ
“Optimizarea matematica = Urcarea unui munte” (Ion Necoara)
Problemele de programare liniar ă se pot descrie în diferite forme, în funcție de condițiile și scopul în
care sunt folosite. Modelul problemei de programare liniară își are originea în domeniul economic din
necesitatea de a util iza resursele cât mai eficient și obținerea un ui profit cât mai mare. Modelul matematic
care stă la baza rezolvării problemei de programare / optimizare liniară oferă algoritmi care pot să
determine modalitatea optimă în care trebuie utilizate resursele af late la dispoziție pentru obținerea unei
performanțe maxime.

12
Spunem că este definită o problemă de optimizare sau de programare matematică dacă se cere
determinarea valorii maxime (sau a valorii minime) a unei funcții de una sau mai multe variabile, care
sunt supuse unui anumit număr de condiții sau restricții.

2.2 FORME ALE PROBLEMELOR DE PROGRAMARE LINIARĂ

2.2.1 FORMA GENERALĂ / STANDARD A UNEI PROBELEME DE OPTIMIZĂRII LINIARE

Spunem că o problem ă de programare liniar ă este în form ă standard dacă to ate restricțiile ei sunt
egalit ăți. Problemele de programare liniară, de obicei au o anumită forma structurală specială și trebuie
să fie exploatate pentru a dezvolta proceduri de calcul eficiente .
O problemă de programare liniară în formă generală conține toate tipurile de restricții și variabile care
pot să apară în descrierea problemei.
Noua problema, numită forma standard a problemei , se construieste astfel:
O restric ție inegalitate din problema original a de tipul " ≤" (respectiv de tipul "≥") se
transform a în egalitate prin ad augarea (respectiv prin sc aderea) unei variabile nenegative din membrul
sau stâng. Aceste variabile se numesc variabile de abatere sau de ecart .
Restric țiile egalit ăți nu se modific a.
Noile variabile introduse nu ap ar în func ția obiectiv a problemei originale (alternativ,
spunem c a ele apar cu coeficien ți nuli).
Termenul programare, în această lucrare va fi sinonim cu optimizare și își are
originea în planificarea optimală. Când variabilele sunt supuse unor res tricții (relații) avem de -a face cu
programare cu restricții, care face obiectul acestei lucrări. În lipsa restricțiilor
spunem că avem programare fară restricții (Luenberger, 1989).

Problemele fără restricții par lipsite de proprietăți structurale astfel încât aplicabilitatea lor în probleme
practice este redusă. Problemele cu restricții permit mode larea fenomenelor complexe prin
descompunerea în subprobleme și fiecare subproblemă având mai multe restricții. Forma generală a unei
probleme de optimi zare liniară cu restricț ii este:

{ inf (sup) ( 𝑐1𝑇𝑥1+ 𝑐2𝑇𝑥2+𝑐3𝑇𝑥3)
𝐴11𝑥1+ 𝐴12𝑥2+𝐴13𝑥3 ≥ 𝑏1
𝐴21𝑥1+ 𝐴22𝑥2+𝐴23𝑥3 = 𝑏2
𝐴31𝑥1+ 𝐴32𝑥2+𝐴33𝑥3 ≤ 𝑏2
𝑥1 ≥ 0; 𝑥2 arbitrar; 𝑥3 ≥ 0 (2)

unde datele problemei sunt matricile 𝐴𝑖𝑗 ϵ ℝ𝑚𝑗 𝑥 𝑛𝑗 și vectorii 𝑏𝑖 ϵ ℝ𝑚𝑖, 𝑐𝑖 ϵ ℝ𝑛𝑗, 1 ≤ i ≤ 3 , 1 ≤ j≤ 3 .
Necunoscutele problemei sunt grupate în trei vari abile vectoriale 𝑥𝑗 ϵ ℝ𝑛𝑗, 1 ≤ j≤ 3 , iar pentru 𝑥1 și 𝑥3 sunt
impuse condiții de semn, în timp ce componentele lui 𝑥2 nu au condiții, ele putând lua orice valori , de

13

asemenea observăm ca sunt prezente toate formele de restricții: c oncordante, de tip egalitate și
neconcordante.

O problemă de optimizare se mai poate scrie:

(3)

unde: f este funcția obiectiv,
𝑔𝑖 sunt funcțiile care dau restricțiile asupra variabilelor 𝑥1, 𝑥2, …, 𝑥𝑛,
ℇ este mulțimea indicilor pentru restricțiile cu egalitate
I este mulțimea indicilor pentru restricțiile cu inegalitate.
Restric țiile de forma 𝑔𝑖(x) ≤ 𝑏𝑖 și pot fi puse sub forma 𝑔𝑖(x) – 𝑏𝑖 ≤ 0.
Observații:

1. “Liniar ă” – funcția obiectiv este liniar ă și restric țiile de tip egalitate reprezint ă un sistem de ecua ții
liniare.
2. Importan ța problemei corespunde scopului general de optimizare a utiliz ării unor resurse rare în
condi țiile îndeplinirii unui anumit obiectiv.
3. Exist ă și alte forme care pot fi aduse la forma standard.

2.2.2 FORMA CANONICĂ A UNEI PROBELEME DE OPTIMIZĂRII LINIARE

Fie α ϵ ℝ𝑛 și β ϵ ℝ, spunem că o restricție concordantă în raport cu o problemă maximizare , dacă
ea este de forma 𝜶𝑻𝒙 ≤𝜷, și neconcordantă dacă 𝜶𝑻𝒙≥𝜷. Analog vom spune ca o restricție este
concordantă în raport cu o problemă de minimizare , dacă ea este de forma 𝜶𝑻𝒙≥𝜷 și neconcordantă
dacă 𝜶𝑻𝒙 ≤𝜷. Restrictiile egalităț i nu fac obiectul acestei clasificari.

Spunem c ă o problemă de programare liniară este în form a canon ică dacă toate restricț iile ei sunt
inegalit ăți concordante .

Forma canonică conține doar restricții concordante și variabile negative precum:
inf {𝑐𝑇𝑥 | 𝐴 𝑥≥𝑏,𝑥≥0}
unde date problemei sunt A ϵ ℝ𝑚 𝑥 𝑛, b ϵ ℝ𝑚 , c ϵ ℝ 𝑛.

Forma canonică poate fi : extinsă și matriceală.

14

Se spune că o problemă de programare li niară este definită sub formă canonică extinsă , dacă este
scrisă sub forma, pentru o problemă de maxim :

(4)

Repectiv pentru o problemă de minim sub forma:

(5)

Se spune că o problemă de programare liniară este definită sub formă canonică m atriceală pentru o
problemă de maxim , dacă este scrisă sub forma:

(6)

Repectiv pentru o problemă de minim sub forma:

(7)

unde:

15
Se observă că în forma canonică a problemei de programare liniară, restricțiile apar sub formă de
inegalități. Orice problema de programare l iniara se poate pune sub o formă canonică de maximizare sau
minimizare, fara modificarea mulțimii sol uțiilor admisibile, observând că :

➢ egalitate se poate înlocui cu dou a inegalit ati de sens contrar,
➢ restric tie ne concordant a devine concordant a prin înmul țire cu -1,
➢ putem schimba sensul optimiz arii func ției obiectiv, gra ție formulei generale:
min f(x) = – max ( – f(x))
În consecinta, putem face anumite raționamente teoretice pe o formă canonică (ca de exemplu în
teoria dualitatii liniare), fără ca prin aceasta să restrângem generalitatea.

Exemplu:

(max)f = 2𝑥1 – 3𝑥2 + 4𝑥3 (min)( -f) = – 2𝑥1 + 3𝑥2 – 4𝑥3
𝑥1- 3𝑥2 + 5𝑥3 = 3 𝑥1- 3𝑥2 + 5𝑥3 ≥ 3
3𝑥1 + 𝑥2 ≥ 5 (8) – 𝑥1+ 3𝑥2 – 5𝑥3 ≥ – 3 (9)
2𝑥1 + 3𝑥3 ≤ 10 3𝑥1 + 𝑥2 ≥ 5
𝑥1, 𝑥2, 𝑥3 ≥ 0 – 2𝑥1 – 3𝑥3 ≤ 10

Probelma inițială Forma canonică de minimizare a problemei

2.2.3 FORMA MIXTĂ A UNEI PROBELEME DE OPTIMIZĂRII LINIARE

O problemă de programare liniară în formă mixtă conține restricții concordante și de tip egalitate, iar
variabilele sunt supuse condiție i de negativitate.
inf{𝑐𝑇𝑥 |𝐴1 𝑥≥𝑏1
𝐴2 𝑥=𝑏2,𝑥≥0}
Dacă o problemă de programare liniară este prezentată într -o anumită formă, ea poate fi transformată în
oricare altă formă dorită, folosind următoarele transformări echivale nte:

✓ Sensul unei inegalități se schimbă prin înmulțire cu -1.
✓ Transformarea unei inegalități într -o ecuație: o inegalitate de forma 𝜶𝑻𝒙 ≤𝜷 este echivalentă cu
ecuația 𝜶𝑻𝒙 +𝒚=𝜷 și 𝒚 ≥𝟎, unde variabila y se numește variabilă ecart sau vari abilă de
compensare; iar inegalitatea 𝜶𝑻𝒙 ≥𝜷 este echivalentă cu 𝜶𝑻𝒙−𝒚=𝜷 și 𝒚 ≥𝟎.

16
✓ Transformarea unei ecuații în inegalității: o ecuație 𝜶𝑻𝒙=𝜷 este echivalentă cu perechea de
inegalități 𝜶𝑻𝒙 ≤𝜷 și 𝜶𝑻𝒙 ≥𝜷.
✓ O variabilă s upusă condiției 𝒙 ≤𝟎 se transformă într -o variabilă negativă prin substituția
x’ = – x.
✓ O variabilă x care nu este supusă unor condiții de semn, se transformă într -o pereche de variabile
nenegative x+ ≥ 0 și x- ≥ 0, prin substituția: x = x+ – x-.

Din cele menționate mai sus rezulă că atât studiul teoretic cât și metodele de rezolvare pot fi abordate
utilizând oricare dintre formele problemelor de programare liniară , drept urmare voi utiliza forma standard
pentru toate exemplele .

Este clar că o problemă de programare liniară în formă generală poate fi adusă la forma standard,
canonică sau mixtă folosind următoarele transformă ri echivalente ale problemelor:

2.3 REZULTATE FUNDAMENTALE PENTRU PROBLEMA DE OPTIMIZARE
LINIARĂ
2.3.1. Spațiul de căutare a soluțiilor . Principalele variante sunt:

➢ spațiu discret de căutare (de regulă o mulțime finită dar de dimensiuni mari ),
➢ spațiu continuu de căutare.

Din punctul de vedere al spațiului de căutare problemele de optimizare se grupează în:

➢ Probleme de optimizare combinatorială

✓ Problema de alocare / selecție (exemplu: problema rucsacului, problema împachetării),
✓ Probleme de ordonanțare/rutare (exemplu: problema comis voiajorului).

➢ Probleme de optimizare continuă

✓ Estimarea parametrilor unor modele (exemplu: determinarea reprezentanților în probleme de
grupare a datelor, antrenarea rețelelor neuronale).

2.3.2. Criteriul de optim (funcția obiectiv ). Reprezintă valoarea care trebuie optimizată (minimizată sau
maximizată). Î n funcție de numărul de cri terii de optimizat problemele pot fi de:

➢ Optimizare unicriterială (o singură funcție obiectiv),
➢ Optimizare multicriterială (mai multe funcții obiectiv).

2.3.3. Restricții . Restricțiile definesc subspațiul soluțiilor fezabile și pot fi de diferite tipuri :

➢ Restricții de mărginire (domeniu): a ≤ x ≤b

17
➢ Restricții de tip egalitate: g(x) = a
➢ Restricții de tip inegalitate: h(x) ≤ b

În funcție de importanța restricțiilor acestea pot fi:

➢ Stricte: trebuie neapărat să fie satisfăcute
➢ Relaxate: e preferabil să fie satisfăcute însă încălcarea lor nu conduce la soluții nefezabile ci doar
la soluții de calitate mai scăzută.

2.4 ETAPE ÎN REZOLVAREA PROBLEMELOR DE OPTIMIZARE

Etapa 1: Analiza rea problemei și identificarea următoarelor elemente:

➢ Structura (modul de re prezentare) a soluțiilor candidat, aceasta permite stabilirea
proprietăților și dimensiunii spațiului de căutare. Problema poate fi încadrată în categoria:

✓ Optimizare combinatorială
✓ Optimizare continuă de dimensiune
✓ mică (sub 10 variabile)
✓ medie (între 10 și 100 de variabile)
✓ mare (peste 100 de variabile)

➢ Restricții

➢ Funcția obiectiv și proprietățile acesteia:
✓ Lineară, pătratică, arbitrară
✓ Continuă/discontinuă, diferențiabilă/nediferențiabilă
✓ O singură funcție/ mai multe funcții, funcție unimodală/multimo dală

Etapa 2: Selectarea metodei:

➢ Metode specifice pentru funcții obiectiv/restricții liniare/pătratice (din domeniul
programării liniare sau a programării pătratice)
➢ Optimizare locală care utilizează derivate
➢ Optimizare locală care nu utilizează derivat e
➢ Optimizare globală
➢ Optimizare multicriterială

Definim următoarele noțiuni:
Un punct x ϵ ℝ𝑛care verifică restricțiile se numește soluție (punct) admisibilă (sau soluție posibilă sau
program ) a problemei de optimizare dacă A x = b și x ≥ 0 și mul țimea tuturor acestor puncte ℝ, formeaz ă
regiunea admisibil ă (realizabil ă).

Orice soluție admisibilă a problemei de optimizare , care optimizează (maximizează sau
minimizează) funcția obiectiv f se numește soluție optimă , dacă avem 𝑐𝑇𝑥 ≤ 𝑐𝑇𝑦.

18

Fără a restrânge generalitatea, spunem că:
rang (A) = m < n.
În cazul în care m = n , sistemul de ecuații ar avea o soluție unică și problema ar deveni banală.

Se spune că mulțimea soluțiilor admisibile este:

(1) discretă , dacă este fi nită sau cel mult numărabilă;
(2) continuă (sau de puterea continuului), dacă nu este numărabilă .

Se spune că o problemă de programare matematică este:

(1) cu variabile discrete , dacă mulțimea soluțiilor admisibile este discretă;
(2) cu variabile continu e (sau de puterea continuului), dacă mulțimea soluțiilor
admisibile este continuă .

Din def inițiile anterioare rezultă că:
• problema de programare matematică are optim finit unic , dacă conține un singur element 𝑥0 și f
(𝑥0) este un număr real finit .
• problema de programare matematică are optim finit multiplu , dacă există cel puțin două elemente,
pentru care f ia valori reale finite.

Se spune că o problemă de programare matematică este:

(1) deterministă , dacă toate elementele sale (funcția obiectiv și restricțiile) sunt definite
în mod determinist, fără a utiliza concepte din teoria probabilităților;
(2) probabilistă sau stohastică , dacă cel puțin unul din elementele sale (funcția obiectiv
sau restricțiile) sunt definite utilizându -se concepte din te oria probabilităților .

Se spune că o problemă de programare matematică este:

(1) liniară , dacă toate elementele sale (funcția obiectiv și restricțiile) sunt definite prin
relații liniare;
(2) neliniară , dacă cel puțin unul din elementele sale (funcția ob iectiv sau restricțiile)
sunt definite prin relații neliniare .

TEOREMA FUNDAMENTALĂ A PROGRAMĂRI LINIARE:

Fie problema (10): {inf 𝑐𝑇𝑥,
𝐴𝑥 = 𝑏,
𝑥 ≥ 0.

a) Dacă problema (10) are o soluție admisibilă, atunci ea are și soluție admisibilă de bază.
b) Dacă problema (10) are o soluție optimă, atunci ea are și soluție optimă de bază.

19

Demonstră m că dacă problema are soluție admisibilă , atunci ea are și soluție admisibilă de bază.

Fie x ϵ P: Dacă x = 0, atunci x este soluție de bază, iar dacă x ≠ 0, atunci renumerotăm variabilele astefl
încat x = ( 𝑥1,𝑥2,⋯,𝑥𝑘,0,⋯,0)T cu 𝑥𝑖 ≠ 0, i = 1,𝑘

Dacă 𝑎1,⋯,𝑎𝑘 sunt liniar independenți, atunci x este soluție de bază.
Dacă 𝑎1,⋯,𝑎𝑘 sunt liniar dependenți, atunci ∃ 𝛼1, ⋯,𝛼𝑘 ϵ ℝ𝑛 astfel încat ∑𝑎𝑖𝛼𝑖𝑘
𝑖=1 = 0.

α = ( 𝛼1, ⋯,𝛼𝑘, 0, ⋯, 0)T ϵ ℝ𝑛
x(𝜆) = x + λx, λ ϵ ℝ
Ax(λ) = Ax + 𝜆Ax = b + 0 = b , ∀ λ ϵ ℝ

Determinăm λ ϵ ℝastfel încât x(𝜆) ≥ 0 ⇔ 𝑥𝑖 + λ𝛼𝑖 ≥ 0, ∀ i = 1,𝑘.

⇔ {𝜆 ≥ − 𝑥𝑖
𝛼𝑖,𝑑𝑎𝑐ă 𝛼𝑖>0
𝜆 ≤ − 𝑥𝑖
𝛼𝑖,𝑑𝑎𝑐ă 𝛼𝑖 < 0
I+ = { i ϵ 1,𝑘 | 𝛼𝑖>0 } și I – = { i | 𝛼𝑖 < 0} ⇒ I+ ∩ I- = ∅, iar nu toți 𝛼𝑖 sunt 0 ⇒ I+ ∪ I- ≠ ∅.
Și vom obține:
𝜆1 = {min
𝑖 ϵ I+(− 𝑥𝑖
𝛼𝑖),I+≠0
− ∞ ,𝑑𝑎𝑐ă I+=0
𝜆2= {max
𝑖 ϵ I+(− 𝑥𝑖
𝛼𝑖),I−≠0
∞ ,𝑑𝑎𝑐ă I−=0 ⇒ x(𝜆) ϵ P, ∀ 𝜆 𝜖 [𝜆1,𝜆2] (cu convenien ța că intervalul este deschis la
capăt ul care este infinit ).

I+≠0 sau I−≠0, vom presupune că I+≠0 și rezultă ca x (𝜆1 ) ϵ P, ∃ 𝑖0 𝜖 I+ astfel încât – 𝑥𝑖
𝛼𝑖 = 𝜆1
⇒ 𝑥𝑖0 + 𝜆1𝛼𝑖0= 0 ⇒ x (𝜆1 ) este soluție admisibilă cu cel mult k-1 componente nenule.

Dacă x (𝜆1 ) este soluție de bază demonstrația se încheie, dacă nu repetăm procedeul, obținând o soluție
admisibilă, cu cel mult k-2 componente nenule. Într -un număr finit de pași (cel mult k) se obține o soluție
admisibilă de bază , iar demonstrația se încheie.

Demonstrăm că dacă problema are soluție optimă , atunci ea are și soluție optimă de bază.

Fie x ϵ P*: Dacă x = 0 , atunci x este soluție de bază, iar dacă x ≠ 0, atunci renumerotăm variabilele astefl
încat x = ( 𝑥1,𝑥2,⋯,𝑥𝑘,0,⋯,0)T cu 𝑥𝑖 ≠ 0, i = 1,𝑘.

Dacă 𝑎1,⋯,𝑎𝑘 sunt liniar independenți, atunci x este soluție de bază.
Dacă 𝑎1,⋯,𝑎𝑘 sunt liniar dependenți, atunci ∃ 𝛼1, ⋯,𝛼𝑘 ϵ ℝ𝑛 astfel încat ∑𝑎𝑖𝛼𝑖𝑘
𝑖=1 = 0 (repetăm
construcția de la punctul a)

20
⇒ x (𝜆 ) ϵ P, ∀ 𝜆 𝜖 [𝜆1,𝜆2] (*) și x ϵ P* rezultă că 𝑐𝑇x (𝜆 ) ≥ 𝑐𝑇x, ∀ 𝜆 𝜖 [𝜆1,𝜆2]
⇒{𝜆𝑐𝑇𝛼,∀ 𝜆 𝜖 [𝜆1,𝜆2]
𝜆1 <0
𝜆2 >0 ⇒ 𝑐𝑇𝛼 = 0 ⇒ 𝑐𝑇x (𝜆 ) = 𝑐𝑇x, 𝜆 𝜖 [𝜆1,𝜆2]
(*) ⇒ x (𝜆 ) ϵ P* ⇒ x (𝜆 ) ϵ P*, 𝜆 𝜖 [𝜆1,𝜆2].

Presupunem că 𝜆1 este finit și rezultă că x (𝜆1) ϵ P* cu cel mult k -1 componente nenule (conform
raționamentului de la punctu l a).
Repetăm procedeul de un număr finit de ori, până când se obține o soluție optimă de bază.

Observăm că o soluție optimă se poate căuta printre soluțiile de bază, care sunt, cel mult, 𝐶𝑛𝑚.

Conform celor menționate mai sus, teorema es te demonstrată.

Din Teorema fundamentală a programării liniare rezultă că, din punct de vedere t eoretic, rezolvarea
problemei (10 ) (adică determinarea unui program optim în cazul în care există) se poate face în modul
următor:

➢ Se demonstrează că p roblema are soluție optimă,
➢ Se determină toate soluțiile admisibile de bază,
➢ Se determină toate soluțiile optime de bază prin compararea valorilor funcției obiectiv pentru
soluțiile admisibile de bază.

Realizarea etapei (b) presupune să considerăm 𝐶𝑛𝑚, sisteme de m ecuații liniare în n necunoscute (numărul
maxim al bazelor ce se pot forma din matricea A este 𝐶𝑛𝑚). Pentru n = 20 necunoscute și m = 10 ecuații,
vor trebui deci considerate 184756 sisteme de 10 ecuații cu 10 necunoscute. Rezultă c ă, chiar pentru
probleme de dimensiuni modeste ( în practică m este de ordinul sutelor, iar n de ordinul miilor, uneori
depășindu -se aceste ordine), metoda prezentată mai sus este numită și metoda descrierii complete , această
metodă nu se poate aplica prac tic din cauza primelor două puncte.

Programarea liniară permite rezolvarea unei gam e largi de probleme cu un efort redus. Popularitatea
programării liniare se datorează în principal etapei de formulare, și nu celei de rezolvare numerică,
deoarece mul te dintre restricțiile ș i obiectivele care apar în practică sunt liniare prin definiție.

Optimizarea sistemelor reale cu evoluție în etape constituie obiectul programării dinamice , care are la
bază pricipiul de optimalitate al lui Bellman (Kaufmann, I I, 1967), care poate fi exprimat astfel:

Orice politică optimă nu poate fi alcătuită decât din subpolitici optime.

Fenomenele de așteptare se optimizează cu modele de așteptare care dau informații asupra organiză rii
sistemului în vederea reducerii t impilor de aș teptare în sistem, a reducerii cheltuielilor de funcționare a
sistemului de așteptare etc.
Asigurarea unui regim optim de funcționare a unui proces de producț ie sau aprovizionarea optimă cu
anume sortimente a cererilor pieței se realizează cu ajutorul modelelor de stocare .

21
O măsură a complexității problemei de progr amare este dimensiunea acesteia exprimată prin numărul
de necunoscute și de restricții (Luenberger, 1989). Dimensiunea problemelor care pot fi rezolvate a
crescut o dată cu d ezvoltarea teoriei și a tehnicilor de calcul.
Se pot distinge acum trei categorii de problem e: de dimensiune redusă (cu cel mult 5 variabile sau
restricții), de dimensiune medie ( între 5 și 100 de variabile sau restricții) și de dimensiuni mari (cu pes te
100 de va riabile și restricții). Această clasificare reflectă nu numai dif erențe de dimensiuni, dar și de
abordare. Astfel p roblemele de dimensiuni mici pot fi rezolvate de mână sau cu un calculator de buzunar.
Problemele de dimensiuni medii pot fi rezo lvate pe un calculator, folosind programe matematice generale.
Problemele de dimensiuni mar i necesită programe sofisticate care exploatează caracteristicile particulare
ale problemei și de obicei se rulează pe calculatoare de mare capacitate.
Teoria iniția lă a optimizării s -a concentrat asupra obținerii rezul tatelor teoretice, ignorând aspectele de
calcul ale metodelor propuse. Abordările recente se axează pe e xploatarea caracteristicilor calculatoarelor,
obținând soluția prin metode iterative.

22

2.5 METODA SIMPLEX DEZVOLTATĂ DE GEORGE B. DANTZIG 1947 – 1951

2.5.1 ALGORITMUL SIMPLEX

O metodă modern fundamental de rezolvarea a problemelor de optimizare este algoritmului
simplex . Acest algorimt a fost introdus pentru prima dat ă de către matematicianul George B. Dantzig în
1947. Acesta este un pachet invariabil de instruc tiuni logice si de calcul care,aplicate unei solu tii
admisibile de baz a a programului, stabile ste dac a solutia respectiv a este optim a si, în caz contrar, pune
în eviden ta situa tia de optim infinit sau construie ste efectiv o solu tie admisibil a de baz a mai bun a decât
cea curent a.

Algoritmul se bazează pe noțiunea de soluție fundamental a unui sistem de ecuații. Se poate arăta că
un program liniar general po ate fi scris întotdeauna în foma standard.
𝑚𝑖𝑛
𝑥𝜖 ℝ𝑛{𝑐𝑇𝑥: 𝐴𝑥=𝑏,𝑥≥0}
prin folosirea de variabile suplimentare (numite și variabile artificiale ). Dezavantajul ce apare constă în
volumul mare de calcule, chiar și atunci când proble ma este de dimensiuni mici.

Algoritmul simplex ne oferă o metodă de exploatare sistematică și economic a programelor de bază,
mai precis de trecere de la un program de bază la altul care ne dă funcția obiectiv o valoare mai mare
sau mai mică, după c um este problema de maximizare sau minimizare. De asemenea, algorimtul
furnizează criteria pentru cazurile în care problema de programare liniară nu are programe sau are optim
infinit.

Ideea de bază în metoda simplex este următoarea: pornind de la o soluție fundamentală fezabilă
găsim o nouă soluție fundamentală fezabilă în care funcția obiectiv să descrească și această căutare se
face folosind tabelul simplex , care deși necesită o matematică extrem de simplă nu se poate exprima
ușor într -o formă m atriceală compactă. A durat mult timp până s -a demonstrat că algoritmul simplex
standard nu are complexitate polinomială.

Algoritmul simplex rămâne, și în zilele noastre cel mai eficient algoritm în ceea ce privește viteza de
lucru, simplitatea și implementarea pe calculator. Mai mult, folosirea acestuia aduce informații mult mai
ample decât găsirea soluției propriu -zise, este mult mai maleabil în cazul modificărilor ulterioare ale
datelor problemei și se pretează mult mai bine la interpretări econo mice. Un argument în plus în
favoarea acestui algoritm este acela că încă nu a apărut o problemă practică în fața căruia să clacheze.

23
Enunțul algoritmului simplex

Fie problema de programare liniar ă sub forma standard (11). Pentru acestă problemă algo ritmul simplex
are următorul enunț:
Pas 0. Se determină o bază ℬ în matricea A, se calculează 𝑥̅ℬ = ℬ−1𝑏, 𝑧̅ℬ = 𝑐ℬ𝑇 𝑥̅ℬ, 𝑦̅𝑗ℬ = ℬ−1𝑎𝑗 (𝑎𝑗 –
coloanele din A), 𝑧𝑗ℬ – 𝑐𝑗, 1 ≤𝑗≤𝑛.
Pas 1. a) Criteriu de intrare în bază:
1) Dacă toți 𝑧𝑗ℬ – 𝑐𝑗 ≤ 0 , 𝑗∈ ℬ, programul are optim infinit. STOP.
2) Dacă există 𝑧𝑗ℬ – 𝑐𝑗 >0 se determină k astfel încât:
𝑧𝑘−𝑐𝑘=max { 𝑧𝑗−𝑐𝑗}
b) Criteriu de ieșire din bază:
1) Dacă toți 𝑦𝑖𝑘≤0 problema are optim infinit.
2) Dacă există 𝑦𝑖𝑘>0, se determină r astfel încât:
𝑥̅𝑟𝐵
𝑦𝑟𝑘𝐵 = min
1≤𝑖≤𝑛{𝑥̅𝑖𝐵
𝑦𝑖𝑘𝐵 | 𝑦𝑖𝑘𝐵>0}
Pas 2. Se inlocuiește în baza ℬ vector ul 𝑎𝑟 cu vectorul 𝑎𝑘, obțințndu -se baza ℬ̃, și se calculează 𝑥̅ℬ̃, 𝑧̅ℬ̃,
𝑦̅𝑗ℬ̃, 𝑧̅ℬ̃− 𝑐𝑗ℬ, 1 ≤𝑗≤𝑛, apoi se trece la pasul 1, înlocuind baza ℬ cu ℬ̃.

24
2.5.2 ALGORITMUL SIMPLEX PRIMAL

Algoritmul simplex primal constă în construcția succesivă a unor soluții de bază ale problemei ințiale
astfel încât fiecare nouă soluție obținută să fie mai bună decat cea precedentă.

Deoarece numărul soluțiilor de bază este finit, dintre soluțiile d e bază se rețin numai cele admisibile
și dintre acestea pe cele care minimizează (maximizează) funcția obiectiv.

Acest algoritm oferă criterii care stabilesc daca o problemă de programare liniară nu admite soluție
optimă sau are optim infinit.
Consid erăm următoarea problemă liniară de minimizare în formă standard:
{min𝑓=𝑐𝑇𝑥
𝐴𝑥=𝑏
𝑥 ≥0 (11)

O solutie de bază B a programului se va numi primal admisibilă ( 𝐵−1𝑏≥0) dacă este admisibilă
în sensul de pâna acum adică are toate componentele nenegative.

Dacă B este baza pentru problema , atunci B este primal admisibilă dacă și numai dacă soluția de bază
asociată lui B este adimisibilă.

𝐵−1𝑏≥0⇔{𝑥𝐵=𝐵−1𝑏
𝑥𝑅=0
Fie B bază primal admisibilă pentru (11), B = (𝑎𝑗1,⋯,𝑎𝑗𝑚).

𝑥𝐵=𝐵−1𝑏−𝐵−1𝑅𝑥𝑅, 𝑥𝑅=0
ℬ={𝑗1,⋯𝑗𝑚}
ℛ={1,⋯,𝑛}\{𝑗1,⋯𝑗𝑚}
{𝑥̅𝐵=𝐵−1𝑏
𝑦𝑗𝐵=𝐵−1𝑎𝑗 ⇒𝑥𝐵=𝑥̅𝐵−∑𝑦𝑗𝐵𝑥𝑗 𝑗∈ℛ
𝑥𝑖𝐵=𝑥̅𝐵−∑𝑦𝑖𝑗𝐵𝑥𝑗,𝑖∈ℬ
𝑗∈ℛ
𝑐𝐵=(𝑐𝑗1,⋯,𝑐𝑗𝑚)𝑇, 𝑐𝑅=(𝑐𝑗)𝑗∈ℛ
𝒄𝑻𝒙=∑𝑐𝑗𝑥𝑗𝑛
𝑗=1=𝑐𝐵𝑇𝑥𝐵+𝑐𝑅𝑇𝑥𝑅=𝑐𝐵𝑇(𝑥̅𝐵−∑𝑦𝑗𝐵𝑥𝑗) 𝑗∈ℛ + ∑𝑐𝑗𝑥𝑗 𝑗∈ℛ = 𝑐𝐵𝑇𝑥̅𝐵−
−∑𝑐𝐵𝑇𝑦𝑗𝐵−𝑐𝑗)𝑥𝑗 𝑗∈ℛ

𝑧̅𝐵=𝑐𝐵𝑇𝑥̅𝐵
𝑧𝑗𝐵=𝑐𝐵𝑇𝑦𝑗𝐵
⇒ 𝐜𝐓𝐱=𝐳̅𝐁−∑(𝐣∈ℝ𝐳𝐣𝐁−𝐜𝐣) 𝐱𝐣, z=𝐜𝐓𝐱
Evident 𝑧̅𝐵 este valoarea funcției obiectiv corespunzătoare soluției de bază a sociată bazei B ( 𝑥𝐵=
𝑥̅𝐵ș𝑖 𝑥𝑅=0).

25
Teorema de optimalitate (Testul de optim)

Fie B o bază primal admisibilă, dacă:
𝑧𝑗𝐵−𝑐𝑗≤0,∀𝑗∈ℛ
Atunci baza B este optimă (adică soluția de bază 𝑥𝐵=𝐵−1𝑏 𝑒𝑠𝑡𝑒 𝑜𝑝𝑡𝑖𝑚ă).

Pentru a de monstra această teoremă avem nevoie de o soluție admisibilă a problemei:
Fie 𝑥𝑗∈ℝ𝑛 o soluție admisibilă a problemei (11), pentru că 𝑥𝑗≥0, iar funția obiectiv se poate exprima:
𝑧=𝑐𝑇𝑥𝑗=𝑧̅𝐵−∑(
j∈ℛzjB−cj) xj≥𝑧̅𝐵,xj≥0
≤ 0

B primal admisibilă ⇒soluția de bază asociată lui B este admisibilă }
⇒

⇒ soluția de bază asociată lui B este soluție optimă.

Teorema de optim infinit (Testul de optim infinit )

Fie B o bază primal admisibilă , dacă există k ∈ℛ astfel încât 𝑧𝑘𝐵−𝑐𝑘>0 și 𝑌𝑘𝐵= 𝐵−1𝐴𝐾≤0,
atunci problema (11) are optim infinit.

Fie 𝛼∈ℝ,𝛼≥0, definim vectorul 𝑥(𝛼)=(𝑥𝐵(𝛼)
𝑥𝑅(𝛼)) în felul următor:

𝑥𝐵(𝛼) = 𝑥̅𝐵− 𝛼𝑌𝑘𝐵
𝑥𝑅(𝛼) = 𝛼𝑒𝑙𝑜𝑐(𝑘), unde loc(k) este un vector unitar, având 1 pe poziția loc(k) a incicelui k din ℛ.

Deoarece baza B este primal admisibilă, 𝛼≥0 și 𝑌𝑘𝐵≤0, rezultă evident 𝑥(𝛼) ≥ 0. Pe de altă parte
vom avea:
A 𝑥(𝛼)= B𝑥𝐵(𝛼)+𝑅𝑥𝑅(𝛼)=𝑏−𝛼𝐴𝑘+𝛼𝐴𝑘=𝑏
Prin urmare pentru orice 𝛼≥0, vectorul 𝑥(𝛼) este o soluție admisibilă.

Valoarea corespunzătoare funcției obiec tiv este:
𝑐𝑇𝑥(𝛼)=𝑐𝐵𝑇𝑥𝐵(𝛼)+𝑐𝑅𝑇𝑥𝑅(𝛼)=𝑐𝐵𝑇(𝑥̅𝐵−𝛼𝑌𝑘𝐵) + 𝛼𝑐𝑘𝐵=𝑧̅𝐵− 𝛼(𝑧𝑘𝐵−𝑐𝑘)
Deoarece 𝑧𝑘𝐵−𝑐𝑘>0, rezultă că lim
𝛼→∞𝑐𝑇𝑥(𝛼)=−∞

Lema substituției

Fie 𝐵=(𝐴𝑠1,⋯,𝐴𝑠𝑚)∈ℳ𝑚(ℝ) o matrice pătratică nesingulară și vectorul 𝐴𝑘 ∈ ℝ𝑚, cu indicele k ∉
{𝑠1,⋯𝑠𝑚}, cosiderăm matrice: 𝐵̃=(𝐴𝑠1⋯ 𝐴𝑠𝑟−1 𝐴𝑘 𝐴𝑠𝑟+1⋯ 𝐴𝑠𝑚) matrice obținută din 𝐵 și notăm
vectorul 𝑦𝑘 = 𝐵−1𝐴𝑘, au loc următoarele afirmații:

26
a) Condiția necesară și suficientă pentru ca matricea ℬ̃ să fie nesingulară este ca elementul 𝑦𝑟𝑘≠0,
unde r = loc( 𝑠𝑟)
b) Dacă 𝑦𝑟𝑘≠0, notăm vectorul 𝜂= (−𝑦1𝑘
𝑦𝑟𝑘,⋯ −𝑦𝑟−1,𝑘
𝑦𝑟𝑘,1
𝑦𝑟𝑘,−𝑦𝑟+1,𝑘
𝑦𝑟𝑘 ,⋯,−𝑦𝑚𝑘
𝑦𝑟𝑘) și matricea pătratică
𝐸𝑟(𝜂) =(𝑒1,⋯𝑒𝑟−1,𝜂,𝑒𝑟+1,⋯,𝑒𝑛) unde 𝑒𝑗∈ℝ𝑚 este vectorul unitar cu 1 în poziția j atunci
𝐵̃−1=𝐸𝑟(𝜂)ℬ−1.
.

Lema substituției este un rezultat al algebrei linare, independent de contextul problemelor de
optimizare pe care îl studiem, având importanță atât teoretică, cât mai ales practică, datorită formulei:
𝐵̃−1=𝐸𝑟(𝜂)ℬ−1

Teorema de schimbare a bazei

Fie B o bază primal admisibilă, presupunem că există 𝑘∈ℛ astfel încât 𝑧𝑘𝐵−𝑐𝑘>0 și vectorul
𝑦𝑘𝐵= 𝐵−1𝐴𝐾are cel puțin un element pozitiv și 𝑟 ∈ℬ astfel încât 𝑦𝑟𝑘𝐵 > 0 și:
𝑥̅𝑟𝐵
𝑦𝑟𝑘𝐵 = min
1≤𝑖≤𝑛{𝑥̅𝑖𝐵
𝑦𝑖𝑘𝐵 | 𝑦𝑖𝑘𝐵>0} atunci:
matricea 𝐵̃, obținută din matricea B înlocuind 𝑎𝑟 𝑐𝑢 𝑎𝑘 este o matrice de bază primal admisibilă pentru
care avem: 𝑧̅𝐵̃=𝑐𝐵̃𝑇𝐵̃−1𝑏≤𝑐𝐵𝑇𝐵−1𝑏=𝑧̅𝐵

În raport cu aceste date de intrare, vom folosi următorii pași:

Pasul 0 (inițializare) : Se determină (dacă există) o bază primal admisibilă B. Se calculează
𝐵−1,𝑥̅𝐵=𝐵−1𝑏, 𝑧̅𝐵=𝑐𝐵𝑇𝑥̅,y=𝐵−1𝐴.
Pasul 1 (Testul de optim ): Dacă 𝑧𝑘𝐵−𝑐𝑘≤0 atunci 𝑧̅𝐵este valoarea optimă și 𝑥𝐵= 𝑥̅𝐵,𝑥𝑅=
0 soluția de bază optimă, STOP.
Pasul 2 (Testul de optim infinit) : Dacă există 𝑘∈ℛ pentru care 𝑧𝑘𝐵−𝑐𝑘>0 și 𝑦𝑘≤0, atunci
problema are optim infinit, STOP.
Criteriu de intrare în bază : Fie 𝑘∈ℛ astfel încât 𝑧𝑘𝐵−𝑐𝑘= max
𝑗∈ℛ(𝑧𝑗𝐵−𝑐𝑗) (acest k ne indică
indicele coloanei care intră în bază).
Crieteriu de ieșire din bază : Fie 𝑟∈ℬ astfel înc ât 𝑦𝑟𝑘𝐵>0 și 𝑥̅𝑟𝐵
𝑦𝑟𝑘𝐵 = min
1≤𝑖≤𝑛{𝑥̅𝑖𝐵
𝑦𝑖𝑘𝐵 | 𝑦𝑖𝑘𝐵>0} (acest r ne
indică indicele care iese din bază).

Pasul 3 (Schimbarea Bazei) : Se alege 𝑘∈ℛ cu 𝑧𝑘𝐵−𝑐𝑘>0 și 𝑟∈ℬ astfel încât 𝑦𝑟𝑘𝐵>0,
𝑥̅𝑟𝐵
𝑦𝑟𝑘𝐵 = min
1≤𝑖≤𝑛{𝑥̅𝑖𝐵
𝑦𝑖𝑘𝐵 | 𝑦𝑖𝑘𝐵>0}.
Fie 𝐵̃ obținut din B înlocuind 𝑎𝑟 cu 𝑎𝑘 . Calculăm: 𝑥̅𝐵̃, 𝑧̅𝐵̃,𝑌𝑗𝐵̃, 𝑧𝑗𝐵̃−𝑐𝑗, pentru orice j ∈ℛ trece m la
pasul 1 unde vom lucra cu 𝐵̃ în loc de B.

27

Formule pentru schimbarea bazei

Fiecare iterație a algoritmului simplex este caracterizat de inversa lui 𝐵−1 a unei baze primal
admisibile. Cu ajutorul acesteia sunt calculate toate celelalte elemente necesare pentru efectuarea pașilor
algoritmului. Acestea sunt următoarele:

𝑥̅ = ℬ−1𝑏, 𝑢𝑇= 𝑐ℬ𝑇𝐵−1,
𝑧̅= 𝑐𝐵𝑇𝑥̅=𝑐𝐵𝑇 𝐵−1 𝑏 = 𝑢𝑇 𝑏,
𝑧𝑇 − 𝑐𝑇=𝑐𝐵𝑇 𝑦−𝑐𝑇= 𝑢𝑇𝐴 𝑐𝑇.

Compone ntele vectorului u se mai numesc și multiplicatori simplex, deoarece cu ajutorul lor se poate
calcula valoarea funcției obiectiv, corespunz ătoare soluției de bază curente, cât și componentele lui
z – c, care la rândul lor se mai numesc și costuri reduse. Dacă testul de optimalitate sau de optim infinit,
nu este îndeplinit, atunci conform teoremei de schimbarea a bazei, putem găsi o nouă bază primal
admisibilă 𝐵̃ cu inversa căreia se calculeazăm din nou formulele menționate mai sus. Trecerea de la 𝐵−1 la
𝐵̃−1 se poate face cu ajutorul Lemei substituție i: cunoscând indicele k pentru coloana 𝐴𝑘 care intră în bază,
indicele r = loc(𝑠𝑟) pentru coloana 𝐴𝑠𝑟 care iese din bază și vectorul 𝑦𝑘= 𝐵−1𝐴𝑘 se formează matricea
𝐸𝑟(𝜂) și atunci putem folosi 𝐵̃−1=𝐸𝑟(𝜂)𝐵−1

2.5.3 Tabelul simplex

În aplicarea algoritmului simplex la rezolvarea manuală a problemelor de optimizare liniară de dimensiuni
mici se utilizează tabelele simplex. La fiecare bază utilizată ℬ corespunde un tabel simplex. Tabelul
simplex asociat bazei ℬ are în prima coloana variabilele de bază (vectorul 𝑥ℬ), în a doua coloană valorile
variabilelor de bază (vectorul 𝑥̅ℬ), iar următoarele n coloane vectorii 𝑦𝑗ℬ, 1 ≤𝑗 ≤𝑛.
Pe o linie suplimentară se trece funcția obiectiv z = 𝑐𝑇𝑥, valoarea sa în baza 𝐵 (adică 𝑧̅𝐵) precum și
cantitățile 𝑧𝑗𝐵- 𝑐𝑗, 1 ≤𝑗 ≤𝑛, necesare în aplicarea algoritmului simplex. Este de asemenea util să scriem
alături de coloana 𝑥ℬ vecto rul 𝑐ℬ, iar alături de lista variabilelor 𝑥𝑗, 1 ≤𝑗 ≤𝑛, coeficienții 𝑐𝑗,
1 ≤𝑗 ≤𝑛 din funcția obiectiv.

Tabelul simplex asociat bazei ℬ are forma următoare :
𝑐1 𝑐𝑗 𝑐𝑛
V.B. = 𝑥ℬ V.V.B. = 𝑥ℬ 𝑥1 ⋯ 𝑥𝑗 ⋯ 𝑥𝑛
𝑐ℬ 𝑥𝐵 𝑥𝐵 𝑦1𝐵 ⋯ 𝑦𝑗𝐵 ⋯ 𝑦𝑛𝐵
z 𝑧̅𝐵 𝑧1𝐵- 𝑐1 ⋯ 𝑧𝑗𝐵- 𝑐𝑗 ⋯ 𝑧𝑛𝐵- 𝑐𝑛

Elementul 𝑦𝑟𝑘 care apare în teorema de sch imbare a bazei este numit pivot. Linia de rang r a tabelului
simplex este numită linia pivotului, iar coloana de rang k este numită coloana pivotului.

Regulri de transformare a tabelului simplex:
• Elementele situate pe linia pivotului se împart la pivot ( 𝑦𝑘𝑗𝐵̃ = 𝑦𝑟𝑗𝐵
𝑦𝑟𝑘𝐵 ),

28
• Elementele situate pe coloana pivotului devin 0, cu excepția pivotului care devine 1 (vectorul 𝑦𝑘𝐵 este
unitar, deoarece k ∈ ℬ),
• Celelalte elemente ale tabelului simplex se transformă după regula drep tunghiului ( se formează un
dreptunghi, având în vârful unei diagonale valoarea de calculat și pivotul, iar noua valoare se obține
din valoarea veche minus produsul elementelor din vârful diagonalei opuse împărțit la pivot).

29
2.5.4 ALGORITMUL SIMPLEX DUAL

Algoritmul simplex dual caută bazele dual admisibile ale problemei de programare liniară până la
obținerea unei baze dual admisibile care să fie și primal admisibilă sau până la punerea în evidență a
faptului că p roblema duală nu are programe.

În algoritmul simplex primal se obțin o succesiune de programede bază, iar în algoritmul simplex dual
se obțin o succesiune de soluții de bază care nu sunt programe. Pentru o problemă de minimizare în
algoritmul simple x primal funcția obictiv descrește până spre minim, pe când în algoritmul simplex dual
funcția obiectiv crește spre maxim.

Adesea pentru problemele de programare / optimizare liniară se cunoaște o soluție de bază, dar care
nu este și admisibilă și p entru care multiplicatorii simplex sunt admisibili pentru problema duală asociată.
În tabelul simplex acestă situație corespunde stării în care ultima linie nu are elemente pozitive, dar soluția
nu este admisibilă.
O astfel de situație o întânim de e xemplu atunci când o problemă de programare liniară este rezolvată
și din acesta se construiește o problemă nouă prin schimbarea vectorului termenilor liberi. În acestă
situație, dispunem de o soluție admisibilă de bază pentru problema duală este de prefer at sa rezolvăm
problema duală.

Oricărei probleme de programare liniară (numită problemă primală) i se asociază o problemă de
programare liniară duală por nind de la aceleași costuri și coeficienți ai restricțiilor, dar în timp ce o
problemă este de minim, cealaltă este de maxim.
Duala unei probleme de optimizare liniară se construiește după următoarele reguli:
➢ o problemă de minimizare (maximizare) se transformă într -o problemă de maximizare
(minimizare),
➢ teremenii liberi din problema primală devin coeficie nții funcției obiectiv în problema duală, iar
coeficienții funcției obiectiv din problema primală devin termeni liberi în problema duală,
➢ matricea coeficienților sistemului de restricții din problema duală este transpusa matricei
coeficienților sistemului de restricții din problema primală,
➢ variabilele duale (respectiv din problema primală) asociate unor restricții din problema primală
(respectiv din problema duală) concordante sunt supuse condiției de n enegativitate (condiții
concordante înseamnă că dacă p roblema este de minim atunci restricțiile trebuie să fie ≥, iar dacă
problema este de maxim, atunci restricțiile trebuie să fie ≤),
➢ variabilele duale (respectiv din problema primală) asociate unor restricții din problema primală
(respectiv din problema dua lă) neconcordante sunt supuse condiției de nepozitivitate,
➢ variabilele duale asociate unor restricții din problema primală care sunt ecuații nu sunt supuse
restricțiilor de semn.

30
Exemplu :

PROBLEMA PRIMALĂ PROBLEMA DUALĂ
{ max𝑓= 8𝑥1 +3𝑥2+𝑥3+5𝑥4+7𝑥5
3𝑥1−2𝑥2+𝑥3+4𝑥4−𝑥5≤6
2𝑥1 +2𝑥3+5𝑥4+𝑥5=9
𝑥1+6𝑥2+𝑥3+2𝑥4 ≥3
𝑥1≥0
𝑥2≥0
𝑥3 𝑓ă𝑟ă 𝑟𝑒𝑠𝑡𝑟𝑖𝑐ț𝑖𝑖
𝑥4 𝑓ă𝑟ă 𝑟𝑒𝑠𝑡𝑟𝑖𝑐ț𝑖𝑖
𝑥5≤0min𝑔(𝑢)=6𝑢1+9𝑢2+3𝑢3
𝑢1≥0
𝑢2 𝑓ă𝑟ă 𝑟𝑒𝑠𝑡𝑟𝑖𝑐ț𝑖𝑖
𝑢3≤0
3𝑢1+2𝑢2+𝑢3≥8
−2𝑢1 +6𝑢3≥3
𝑢1+2𝑢2+𝑢3=1
4𝑢1+5𝑢2+2𝑢3=5
−𝑢1+𝑢2 ≤7}

Observatii:
1) Problema duala are atâtea variabile (respec tiv restricții) câte restricții (respectiv v ariabile) are
problema primală.
2) Regulile enunțate mai s us pun în evidență urmatoarele corespondente de termeni prin trecere la
duală :
min  max
(restricție) concordantă  (variabilă) nenegativă
(restricție) neconcordantă  (variabilă) nepozitivă
(restricț ie) egalitate  (variabilă) fără restricție de semn
termen liber al unei restrictii  coeficient al funcț iei obiectiv

3) Din constructia de mai sus rezulta urmatoarea concluzie:

Duala dualei este problema primala.

Spunem că dualitatea în programarea liniară are un caracter involutiv.
4) Algoritmul nu se te rmină decât cu soluția optimă și valoarea corespunzătoare pentru funcția obiectiv
sau dacă problema duală are valoarea nemărgin ită pentru funcția obiectiv. Deoarece există numai un
număr finit de baze, optimul trebuie să fie obținut dintr -un număr finit de iterații.

Algoritmului simplex dual se compune din urmatorii pasi:

Pasul 0 : Se determină (dacă există) o bază dual admisibilă 𝐵 și se calculează 𝐵−1.
Pasul 1 : Se calculează 𝑥̅=𝐵−1𝑏,𝑧̅= 𝑐𝐵𝑇𝑥̅,𝑦=𝐵−1𝐴,𝑧𝑇−𝑐𝑇=𝑐𝐵𝑇𝑦−𝑐𝑇.
Pasul 2 : (Testul de optimalitate) Dacă 𝑥̅≥0, atunci 𝑧̅ este valoarea optimă, iar 𝑥𝐵=𝑥̅ și 𝑥𝑅 = 0
este soluția de bază optimă a problemei. STOP.
Pasul 3 : (Testul de domeniu Vid) Dacă există 𝑥̅𝑖≥0 astfel încât 𝑦𝑖𝑗 ≥ 0, pentru orice j = 1,𝑛̅̅̅̅̅ atunci
problema nu are soluții. STOP.
Pasul 4: (Schimbarea bazei) 𝑥̅𝑅<0, și din relația 𝑧𝑘−𝑐𝑘
𝑦𝑟𝑘= min
𝑗∈ℛ {𝑧𝑗−𝑐𝑗
𝑦𝑟𝑗, 𝑦𝑟𝑗<0𝑧𝑗−𝑐𝑗
𝑦𝑟𝑗} se determină
k ∈ℛ. Se formează matricea 𝐵̃, care se obține din 𝐵 prin înlocuirea coanei 𝐴𝑠𝑟 cu 𝐴𝑘(unde indicele 𝑠𝑟∈

31
ℬ, iar loc (𝑠𝑟)= r), se calculează 𝐵̃−1 cu formula 𝐵̃−1=𝐸𝑟(𝜂)𝐵−1 și cu această inver să a noii matrice
de bază se revine la Pasul 1 .

O solutie de bază B a programului se va numi dual admisibilă dacă verifică criteriul de optimalitate
al algoritmului simplex. O bază a programului se va numi dual admisibi lă dacă soluț ia asociată este dual
admisibilă .

În concluzie una din solutii este primal admisibilă dacă și numai dacă cealaltă este dual admisibilă .
Oricare din ele este optimă dacă și numai dacă este simu ltan primal si dual admisibilă.

32
3. CAPITOLUL 3 – METO DE DE DESCOMPUNERE

Rezolvarea problemelor de optimizare liniară de dimensiuni mari prezintă deseori numeroase
dificultăți deoarece sunt greu de rezolvat sau imposibil de rezolvat folosind aloritmul simplex primal sau
dual. În astfel de situații poa te prezenta interes ideea de a „ descompune” problema inițială în
subprobleme de dimensiuni mai reduse, a căror rezolvare să permită obținerea unei soluții optime pentru
problema considerată inițial.

Ideea de a descompune problemele de optimizare liniară în subprobleme de dimensiuni mai mici este
legată de anumite forme particulare în care apare problema inițială, cunoscute sub denumirea de probleme
unghiulare sau în blocuri .

Considerăm următoare problemă:
{ max(∑𝑐𝑗𝑥𝑗𝑛
𝑗=1)
𝐴𝑗𝑥𝑗=𝑏𝑗
∑ℬ𝑗𝑥𝑗𝑛
𝑗=1=𝑏0
𝑥𝑗≥0,1≤𝑗≤𝑛 (12)

Unde 𝐴𝑗 este matricea cu 𝑚𝑗 linii și cu 𝑛𝑗 coloane, ℬ𝑗 este matricea cu 𝑚𝑗 linii și cu 𝑛𝑗 coloane, iar
𝑥𝑗, 𝑐𝑗, 𝑏𝑗 sunt vectori de dimensiuni corespunzătoare. Presupunem că 𝑏0≥0.
Matricea A a sistemului de ecuații considerat în (12) are forma particulară:

A = (𝐴1⋯0
⋮⋱⋮
0⋯𝐴𝑛
𝐵1 ⋯ 𝐵𝑛 ) (12.1) numită unghiulară sau în blocuri , de asemenea și problema (12) este

unghiulară sau în blocuri .

O interpretare economică imediată pentru forma particulară a problemei (12) se obține dacă se
consideră un sistem de n unități economice conduse de un centru comun. La fiecare unitate eco nomică j,
1≤𝑗≤𝑛, există restricții specifice în care apare numai vectorul 𝑥𝑗 ale cărui componente reprezintă
nivelurile la care urmează să se desfășoare activitățile economice considerate la această unitate
economică, aceste restricții specifice sun t de forma:

{𝐴𝑗𝑥𝑗=𝑏𝑗
𝑥𝑗≥0,1≤𝑗≤𝑛 (12.2)

33
Pe de altă parte, există restricții de ordin general, impuse de apartenența întreprinderilor considerate
la un centru comun de conducere, aceste restricții „ de cuplare” sunt de fo rma:
∑𝐵𝑗𝑥𝑗=𝑏0 (12.3)𝑛
𝑗=1
Problema constă în optimizarea activităților desfășurate de cele n întreprinderi din punct de vedere
al centrului comun de conducere, exprimat matematic prin maximizarea funcției obiectiv:

𝑧=∑𝑐𝑗𝑇𝑥𝑗𝑛
𝑗=1 (12.4)
Duala problemei de optimizare liniară a problemei (12) este:

{ min(∑𝑏𝑗𝑇𝑢𝑗𝑛
𝑗=1)
𝐴𝑗𝑇𝑢𝑗+𝐵𝑗𝑇𝑢0≥𝑐𝑗,1≤𝑗≤𝑛
𝑢𝑗 𝑎𝑟𝑏𝑖𝑡𝑟𝑎𝑟 ,1≤𝑗≤𝑛 (12.5)
În pro blema duală putem interpreta componentele vectorului 𝑢0 ca fiind variabilele de cuplare, care
fac legătura dintre variabilele 𝑢1…….….𝑢𝑛 asociate celor n întreprinderi economice considerate mai sus.

Considerăm pentru fiecare j, 1≤𝑗≤𝑛, fixa t problema de optimizare liniară devine:

{max((𝑐𝑗𝑇−𝑢𝑇𝐵𝑗)𝑥𝑗)
𝐴𝑗𝑥𝑗=𝑏𝑗
𝑥𝑗≥0,1≤𝑗≤𝑛 (12.6)
Fie 𝑢∈ ℝ fixat astfel încât, problema (12.6), 1≤𝑗≤𝑛, să aibă soluții optime. Dacă 𝑥𝑗∗, 1≤𝑗≤𝑛
sunt sol uții optime, dacă este îndeplinită condiția:

∑𝐵𝑗𝑥𝑗∗=𝑏0 (12.7)𝑛
𝑗=1
atunci 𝑥∗= (𝑥1∗,………,𝑥𝑛∗) este o soluție optimă a problemei de programare liniară (12).

Ideea descrisă poate fi realizată în mai multe modu ri, obținând diverși algoritmi de descompunere pentru
problema (12). Cel mai cunoscut algoritm este algoritmul propus de Dantzig și Wolfe (1960).

34
3.1 Pricipiul de descompunere Dantzig – Wolfe

Dantzing și Wolfe au fost primii care au publicat î n 1960 un algoritm de descompunere pentru
problemele de optimizare liniară. Algoritmul devine eficient dacă este aplicat în problemele liniare cu
restricții în formă bloc-unghiulară.

Principiul constă în construirea unui program principal care este echiva lent cu problema inițială și care
are un număr de linii doar cu o unitate mai mare decât numărul restricțiilor de cuplare, iar numărul de
coloanele devine foarte mare, dar acestea nu trebuie tabelate de la început deoarece se generează în
momentul în care ele sunt necesare în aplicarea algoritmului simplex.

Algoritmul constă în doua etape: în prima etapă, se rezolvă un număr de subprobleme independente,
iar în a doua etapă , se rezolvă programul principal în care se introduc rezultatele obținute prin rezolvarea
subprobelemelor.

Să considerăm o problemă de programare liniară în care restricțiile sunt grupate în două părți:

𝑖𝑛𝑓 𝑐𝑇𝑥 (13)

în raport cu: 𝐴 𝑥=𝑏0 (𝑚0 restricții )
𝐷 𝑥=𝑏 ( m resticții)
𝑥 ≥0
unde A∈ℝ𝑚 𝑥 𝑛, D ∈ℝ𝑚 𝑥 𝑛, c ∈ℝ 𝑛, 𝑏0∈ℝ𝑚0, b∈ℝ𝑚.

Vom presupune că poliedrul convex este:

𝑆={𝑥 ∈ ℝ𝑛 | 𝐷 𝑥=𝑏,𝑥≥0} este mărginit și mulțimea punctelor sale extreme este:

Ext (S) = {𝑥𝑗,1≤𝑗≤𝑟}

TEOREMĂ : Fie mulțimea X = { ∈ ℝ𝑛 | 𝐴 𝑥=𝑏,𝑥≥0} ≠0, atunci x ∈𝑋, dacă și numai dacă x poate
fi scris ca o combinație convexă de puncte extreme ale lui X, plus o combinație liniară nenegativă de raze
extreme ( soluții nenule ale sistemului omogen ) ale lui X:
𝑥= ∑𝜆𝑖𝑥𝑖
𝑖 (13.1)
unde
∑𝛿𝑖𝜆𝑖=1,𝜆𝑖≥0
𝑖 (13.2)

și 𝛿𝑖={1
0} după cum 𝑥𝑖 este {𝑝𝑢𝑛𝑐𝑡 𝑒𝑥𝑡𝑟𝑒𝑚
𝑟𝑎𝑧ă 𝑒𝑥𝑡𝑟𝑒𝑚ă} a lui X. (13.3)

De unde vom avea pentru orice 𝑥∈𝑆:

35
𝑥= ∑𝜆𝑗𝑥𝑗𝑟
𝑗=1,𝜆𝑗≥0 ș𝑖 ∑𝜆𝑗=1𝑟
𝑗=1 (13.4)

Problema inițială se poa te formula astfel:
Să se determine 𝑥∈𝑆 astfel încât să fie satisfăcute restricțiile 𝐴 𝑥=𝑏0 și să se realizeze minimul
lui 𝑐𝑇𝑥.

Vom nota: 𝛾𝑖= 𝑐𝑇𝑥𝑖 ș𝑖 𝛼𝑖=𝐴 𝑥𝑖 (13.5) atunci, problema inițială se poate scrie în funcție de
variabilele 𝜆𝑖 astfel:
inf∑𝛾𝑗𝜆𝑗𝑟
𝑗=1 î𝑛 𝑟𝑎𝑝𝑜𝑟𝑡 𝑐𝑢:
∑𝛼𝑗𝑟
𝑗=1𝜆𝑗=𝑏0,
∑𝜆𝑗=1𝑟
𝑗=1
𝜆𝑗≥0,1≤𝑗≤𝑟 }
(𝑃𝑃)

Problema (PP) s e numește program principal și este echivalent cu problema (13) , ceea ce este de
remarcat este faptul că programul principal al doar 𝑚0+1 restricții, față de 𝑚0+𝑚 cât are problema
(13), iar acest lucru reprezintă o restrângere a dimensiunii în caz ul în care m este mare. În schimb numărul
coloanelor este egal cu numărul punctelor de extrem ale mulțimii S, care poate fi considerabil mare.

Pentru a determina o bază primal admisibilă a programului principal se poate folosi o metodă de fază 1,
după ce s-au determinat un număr 𝑙≥𝑚0+1 de puncte extreme ale mulțimii S, la fel punctele de extrem
se pot obține printr -o metodă de fază 1 aplicată restricțiilor ( 𝐷 𝑥=𝑏, 𝑥 ≥0), urmată de un număr de
iterații de schimbare a bazei, cu respectarea crite riului din algoritmul simplex.
Fie ℬ o bază primal admisibilă a programului principal, ℬ mulțimea indicilor de bază și 𝑢𝑇=𝛾ℬ𝑇𝐵−1,
vectorul multiplicatorilor simplex corespunzători acestei baze. Pentru a afla dacă această bază este optimă
trebuie să calculăm:
𝑢𝑇(𝛼𝑆
1)−𝛾𝑆=max
𝑗{𝑢𝑇(𝛼𝑗
1)−𝛾𝑗} (13.6)
Dacă parționăm vectorul 𝑢𝑇= (𝑢0𝑇,𝑢1), cu 𝑢0∈ ℝ𝑚0 și 𝑢1∈ ℝ, și ținem seama de notațiile (13.5)
atunci vom obține:

𝑢𝑇(𝛼𝑗
1)−𝛾𝑗=(𝑢0𝑇,𝑢1)(𝐴 𝑥𝑗
1)− 𝑐𝑇𝑥𝑗=(𝑢0𝑇 𝐴− 𝑐𝑇)𝑥𝑗+𝑢1
Prin urmare, determinarea maximului în relația (13.6) se poate scrie:
max
𝑗{𝑢𝑇(𝛼𝑗
1)−𝛾𝑗}=max
𝑥𝑗∈𝐸𝑥𝑡 (𝑆){(𝑢0𝑇 𝐴− 𝑐𝑇)𝑥𝑗}+𝑢1 (13.7)

36
Reamintim că 𝑥𝑗 este un punct de extrem a lui S și observăm că expresia de maximizat în (13.7) este
liniară în 𝑥𝑗. Deoarece o soluție optimă a unei probleme de optimizare liniară, cu domeniul de
admisibilitate mărginit, este întotdeauna și un punct de extrem al acestei mulțimi, maximizarea din (13.7)
este echivalenta cu subproblema:

max
𝑥∈ℝ𝑛{(𝑢0𝑇 𝐴− 𝑐𝑇) 𝑥 | 𝐷 𝑥=𝑏,𝑥≥0} (13.8)
Rezolvând această sub problemă, se poate obține o soluție 𝑥𝑆 pentru care valoarea maximă din relația
(13.6) pe care o vom nota cu △, este:
△=𝑢𝑇(𝛼𝑆
1)−𝛾𝑆=(𝑢0𝑇 𝐴− 𝑐𝑇)𝑥𝑆+𝑢1
Dacă △≤0 atunci baza ℬ este optimă pentru programul principa l și 𝜆̅=ℬ−1(𝑏0
1) este soluția optimă
corespunzătoare. Soluția optimă pentru problema inițială se obține din relația (13.4):
𝑥̅=∑ 𝜆̅𝑖𝑥𝑖
𝑖∈ℬ
Dacă △>0, atunci coloana care intră în bază este 𝛼𝑆=(𝐴 𝑥𝑆
1) cu coeficie ntul de cost 𝛾𝑆= 𝑐𝑇𝑥𝑆.
Facem o operație de schimbare a bazei în programul principal, obținem o nouă bază primal admisibilă și
calculele se reiau cu testul de optimalitate a acesteia. Acest procedeu de rezolvare devine atractiv dacă
este apli cat la probleme cu o structură bloc-unghiulară a restricțiilor, de forma:

(PBU)
{ inf { 𝑐1𝑇𝑥1+ 𝑐2𝑇𝑥2+⋯+𝑐𝑘𝑇𝑥𝑘}
𝐴1𝑥1+ 𝐴2𝑥2+…+𝐴𝑘𝑥𝑘 = 𝑏0
𝐷1𝑥1 = 𝑏1
𝐷2𝑥2 = 𝑏2
⋱
𝐷𝑘𝑥𝑘 =𝑏𝑘
𝑥𝑖≥0,𝑖=1,𝑘̅̅̅̅̅,𝑘>0
pentru orice 𝑖=1,𝑘̅̅̅̅̅, avem 𝐴𝑖∈ ℝ𝑚0𝑥 𝑛𝑖, 𝐷𝑖∈ ℝ𝑚𝑖 𝑥 𝑛𝑖, 𝑐𝑖∈ ℝ 𝑛𝑖, 𝑏𝑖∈ ℝ 𝑚𝑖 și 𝑏0∈ ℝ 𝑚0.

Pentru problema bloc -unghiulară (PBU), subproblema (13.8) devine:

max{(∑𝑢0𝑇 𝐴𝑖−𝑐𝑖𝑇𝑘
𝑖=1)𝑥𝑖 | 𝐷𝑖 𝑥𝑖 =𝑏𝑖,𝑥𝑖 ≥0,𝑖=1,𝑘̅̅̅̅̅ } (13.9)
Deoarece în (13.9) funcția obiectiv este aditiv separabilă în 𝑥𝑖 , iar restricțiile sunt independente în
raport cu 𝑥𝑖 , această problemă se reduce la rezolvarea a k subprobleme independente:

max
𝑥𝑖∈ℝ𝑛𝑖{(𝑢0𝑇 𝐴𝑖−𝑐𝑖𝑇) 𝑥𝑖 | 𝐷𝑖 𝑥𝑖 =𝑏𝑖,𝑢0𝑇 𝐴𝑖−𝑐𝑖𝑇 𝑥𝑖 ≥0},𝑖=1,𝑘̅̅̅̅̅ (13.10)
În baza principiului de descompunere Dantzing – Wolfe prezentat, vom enunța algoritmul pentru
rezolvarea p roblemei bloc -unghiulare (PBU). Presupunem ca avem la dispoziție o bază primal admisibilă
ℬ a programului principal (PP) și multiplicatorii simplex 𝑢𝑇=(𝑢0𝑇,𝑢1) corespunzători.

37
3.2 Algoritmul de descompunere Dantzing – Wolfe

Pasul 0 : Se determină o bază primal admisibilă ℬ pentru programul principal (PP) și multimplicatorii
simplex 𝑢𝑇=(𝑢0𝑇,𝑢1) corespunzători.

Pasul 1 : Folosind multiplicatorii simplex se rezolvă subproblemele (13.10), obținând soluțiile
𝑥̅𝑖(𝑢0),𝑖=1,𝑘̅̅̅̅̅.

Pasul 2 : Se calculează
△=∑(𝑢0𝑇 𝐴𝑖−𝑐𝑖𝑇)𝑘
𝑖=1𝑥̅𝑖(𝑢0)+𝑢1

Dacă Δ ≤0, atunci soluția optimă pentru (PBU) este:

𝑥̅=∑ 𝜆𝑖𝑥𝑖 (13.11)
𝑖∈ℬ
unde 𝑥𝑖 sunt punctele de extrem ale mulțimii
𝑆={𝑥 ∈ ℝ∑𝑛𝑖𝑘
𝑖=1| (𝐷1
⋱
𝐷𝑘) 𝑥=(𝑏1
⋮
𝑏𝑘)} (13.12)
Corespunzătoare soluțiilor de bază 𝜆𝑖. STOP.

Pasul 3 : Dacă Δ >0, se formează coloana:
(𝛼𝑆
1)=(∑𝐴𝑖𝑥𝑖(𝑢0)𝑘
𝑖=1
1)

care pri ntr-o operație de schimbare a bazei din algoritmul simplex va fi introdusă într -o nouă bază primal
admisibilă pentru (PP) și în mod corespunzător, se obține un nou vector al multiplicatorilor simplex. Dupa
aceasta, se revine la Pasul 1 .

Observația (1) :
Dacă programul principal are toate soluțiile de bază nedegenerate, atunci fiecare iterație va produce
o descreștere strictă a funcției obiectiv. Deoarece există un număr finit de baze posibile și niciuna nu se
poate repeta, principiul de descompunere va determina soluția optimă într -un număr finit de iterații.

Observația (2):
Trebuie subliniat faptul că soluția optimă 𝑥̅ a problemei (PBU) nu este neapărat una dintre cele obținute
la rezolvarea subproblemelor (13.10). Din (13.11) rezultă că 𝑥̅ este o anumită combinație convexă a unui
număr de astfel de soluții. Prin urmare, programul principal nu poate obține optimul global pur și simplu
prin trimiterea preturilor corespunzătoare lui 𝑢0 către subprobleme, el trebuie să combine soluțiile
subpro blemelor întru -un plan general. În acest sens, descompunerea lui Dantzig – Wolfe nu este o

38
descentralizare completă a procesului de luare a deciziei. Din această cauză Dantzig a denumit această
descompunere planifi care centralizată fără informați e completă la centru .

3.3 Programul principal restrâns

Principiul de descompunere Dantzing – Wolfe, în forma prezentată mai sus, rezolvă probleme de
optimizare doar în prima etapă, în timp ce în a doua etapă, se execută doar o singură operație de schimbare
a bazei . Se poate da însă o formulare mai simetrică a acestei metode, astfel ca în ambele etape să se rezolve
probleme de optimizare. În locul programului principal (PP), vom considera un program principal
restrâns , format doar din coloanele care formează baza cu rentă în (PP) și coloana care urmează să fie
introdusă în noua bază.

Programul principal restrâns este:
inf∑𝛾𝑖𝜆𝑖+𝛾𝜆𝑚
𝑖=1 î𝑛 𝑟𝑎𝑝𝑜𝑟𝑡 𝑐𝑢:
∑𝛼𝑖𝑚
𝑖=1𝜆𝑖+𝛼𝜆=𝑏0,
∑𝜆𝑖+𝜆=1𝑚
𝑖=1
𝜆𝑖≥0,𝑖=1,𝑚,̅̅̅̅̅̅ 𝜆≥0 }
(𝑃𝑃𝑅)

unde 𝑚=𝑚0+1,𝜆𝑖 sunt variabilele de bază curente și 𝜆 este variabila care intră în noua bază, având
coeficientul de cost redus: 𝑢0𝑇 𝛼+𝑢1−𝛾>0.

Rezolvarea acestei probleme este echivalentă cu iterația de schimbare a b azei prezentată în algoritmul
de descompunere.

39
3.4 Metode de Partiționare și R elaxare (metoda relaxării și metoda restrângerii)

Probelemele de dimensiuni mari au o structură bloc diagonală în care legătura dintre blocuri se
realizează at ât prin resticții de cuplare, cât și prin variabile de cuplare.

Considerăm următoarea problemă cu blocurile cuplate în ambele moduri:

inf{𝑐1𝑇𝑥1+𝑐2𝑇𝑥2+⋯+𝑐𝑘𝑇𝑥𝑘+𝑐0𝑇𝑦} (14)

în raport cu:

𝐴1𝑥1+𝐴2𝑥2+⋯+𝐴𝑘𝑥𝑘+𝐺0 𝑦=𝑏0 (14.1)

𝐷1𝑥1 +𝐺1𝑦=𝑏1
𝐷2𝑥2 +𝐺2𝑦=𝑏2 (14.2)
⋱ ⋮
⋮
𝐷𝑘𝑥𝑘+𝐺𝑘𝑦

Pentru r ezolvarea acestei probleme putem folosi principiul de descompunere Dantzig – Wolfe, dacă
problema are numai variabile de cuplare, atunci algoritmul Dantzig – Wolfe se poate aplica dualei, care
are numai restricții de cuplare. Dacă sunt prezente atat variab ile cât și restricții de cuplare, atunci
restricțiile se pot partiționa în (14.1) și (14.3). Restricțiile (14.2) vor fi folosite la programul principal, iar
(14.3) la subproblemă.

Deoarece subproblema are formă dual -unghiulară, ea poate fi rezolvată direc t, sau prin aplicarea
algoritmului Dantzig – Wolfe. Drept urmare problema (14) -(14.3) poate fi rezolvată cu principiul de
descompunere Dantzig – Wolfe, care se folosește într -un algoritm în care o iterație este structurată pe 3
nivele și anume: două nivele pentru rezolvarea subproblemei și al treilea nivel, pentru rezolvarea
programului principal.

Problema (14) -(14.3) poate fi abordată și într -un alt mod, și anume prin partiționarea variabilelor în
două submulțimi, variabilele de cuplare y și a variabi lelor bloc 𝑥𝑖. Variabilele 𝑥𝑖 sunt din nou partiționate
în mulțimi dependente și independente, în raport cu matricele de bază ale blocurilor 𝐷𝑖. Această
partiționare permite ca restricțiile bloc și variabilele dependente să fie eliminate din program, astfel încât
sa obținem o problemă redusă, de dimensiuni mici.

Astfel de metode se numesc de partiționare și relaxare, se folosește termenul de relaxare deoarece, prin
eliminarea variabilelor dependente, se pierde controlul asupra condițiilo r de nenegativitate ale acestora.
Acest concept a fost plasat de Geoffrion într -un cadru general, pentru o întelegere mai bună la aceste
metode. 𝑥𝑖≥0,𝑖=1,𝑘̅̅̅̅̅,𝑦≥0 (14.3)

40
3.5 Principiul de relaxare

Considerăm problema convexă:

inf{𝑓(𝑥)|𝑔𝑖(𝑥)≤0,𝑖=1,𝑚̅̅̅̅̅̅,𝑥∈𝑆⊆ℝ𝑛} (𝑃)

unde f și g sunt funcții convexe definite pe mulțimea convexă S. Presupunem că numărul de restricții este
suficient de mare pentru dificultate în rezolvarea problemei. În aceste condiții rezolvarea acestei probleme
constă în relaxarea (adică elimina rea temporară) a unor restricții și considerarea unei probleme noi,
formată doar din restricțiile rămase . Dacă acesta are o soluție optimă care satisface și restricțiile eliminate,
atunci soluția va fi optimă și pentru problema inițială, iar dacă o parte d in restricțiile relaxate nu sunt
satisfacute, atunci un anumit număr dintre acestea vor fi luate în considerare pentru a defini o nouă
problemă și procedeul se repeta.

Geoffrion a formalizat acestă idee: Fie ℳ={1,2,…,𝑚}, se notează cu ℛ o submulțime a lui ℳ,
ℛ⊂ℳ, considerând problema redusă:

𝑖𝑛𝑓{𝑓(𝑥)|𝑔𝑖(𝑥)≤0,𝑖∈ℛ,𝑥∈𝑆} (𝑃𝑅)

Presupunem că poate fi gasită o mulțime inițială ℛ astfel încât problema redusă (𝑃𝑅) să aibă un minim
finit și să fie atins.

3.6 Agloritmul gene ral de part iționare și relaxare

Pasul 0 : Se ia 𝑓̅=−∞ și se alege o mulțime inițială ℛ⊂ℳ astfel f să fie inferior mărginită în raport
cu restricțiile problemei reduse (𝑃𝑅).

Pasul 1 : Se rezolvă problema (𝑃𝑅), dacă acesta admite soluții, atunci și pr oblema (P) este
neadmisibilă. STOP.

Pasul 2: Dacă 𝑔𝑖(𝑥̅ℛ) ≤0, pentru 𝑖 ∈ ℳ\ℛ, atunci soluția 𝑥̅ℛ este optimă și pentru problema
inițială (P). STOP.

Pasul 3 : În caz contrar vom avea: fie 𝒱⊆{𝑖 ∈ ℳ\ℛ| 𝑔𝑖(𝑥̅ℛ)>0} o submulțim e ce conține cel
puțin un indice al unei restricții nesatisfăcute și 𝒰={𝑖∈ℛ| 𝑔𝑖(𝑥̅ℛ)<0}.

Pasul 4 : Dacă 𝑓(𝑥̅ℛ) = f, atunci ℛ se înlocuiește prin ℛ′=ℛ∪ 𝒱 și se revine la Pasul 1.

Pasul 5 : Dacă 𝑓(𝑥̅ℛ) > f, atunci ℛ se înloc uiește prin ℛ′=ℛ∪ 𝒱\𝒰, f se înlocuiește cu 𝑓(𝑥̅ℛ) și se
revine la Pasul 1.

Acest algoritm adaugă una sau mai multe restricții întercalte și dacă 𝑓(𝑥̅ℛ) crește, atunci elimină aceste
restricții din ℛ care nu sunt active în 𝑥̅ℛ. Faptul că nu elimină nicio restricție în cazul în care 𝑓(𝑥̅ℛ)=
𝑓, garantează că rezolvarea problemei (P) se tremină într -un anumit număr finit de iterații.

41
Propoziția 1: Fie 𝑥̅ℛ o soluție optimă a problemei reduse (𝑃𝑅).
Dacă 𝑔𝑖(𝑥̅ℛ) ≤0 pentru orice 𝑖 ∈ ℳ\ℛ, atunci 𝑥̅ℛeste o soluție optimă și pentru problema (P).

Propozitia 2: Dacă 𝑥̅ℛ este o soluție optimă a problemei reduse (𝑃𝑅) și se elimină restricțiile din 𝒰,
atunci 𝑥̅ℛ este o soluție optimă și pentru pr oblema (𝑃𝑅\𝒰). În plus dacă 𝑥̅ℛ este unica soluție optimă a
lui (𝑃𝑅), atunci ea este unica soluție și pentru (𝑃𝑅\𝒰).

Propozitia 3: Dacă 𝑥̅ℛși 𝑥̅ℛ′sunt soluțiile optime a două subprobleme obținute prin relaxare, unde
ℛ′este determinat la Pasul 4 sau 5 al algoritmului, atunci vom avea:
𝑓(𝑥̅ℛ)≤𝑓(𝑥̅ℛ′).
Demonstrație:
Dacă ℛ′=ℛ∪𝒱, atunci propoziția este evidentă, însa pentru ℛ′=ℛ∪𝒱\𝒰, folosind Propoziția 2,
vom avea:
𝑓(𝑥̅ℛ)= 𝑓(𝑥̅ℛ\𝒰)≤𝑓(𝑥̅(ℛ\𝒰)∪𝒱),

ceea ce aveam de demonstrat.

Observație:
Convexitatea funcțiilor f și 𝑔𝑖, precum și cea a mulțimii S, permit eliminearea restricțiilor neactive. În
absența convexității restricțiilor 𝑔𝑖, Propoziția 3 rămâne adevărată numai dacă restricțiile se adaugă (
cazul ℛ′=ℛ∪ 𝒱 ), fară ca vreuna să fie eliminată.

Propoziția 4: Algoritmul se partiționare și relaxare se termină într -un număr finit de iterații.

Demonstrație:
Deoarece mulțimea ℳ este finită, ea are doar un număr finit de submulțimi distincte. Atâta timp cât
valorile optime 𝑓(𝑥̅ℛ) ale subproblemelor (𝑃𝑅) cresc de la iterație la alta, nici o submulțime de indici
nu se poate repeta. În cazul 𝑓(𝑥̅ℛ)=𝑓(𝑥̅ℛ′), nici o restricție nu se eli mină și se adaugă cel puțin una,
pentru un număr finit de iterații. Astfel, algoritmul se termină într -un număr finit de iterații, fie la Pasul
1, fie la Pasul 2 ( este posibil ca ℛ=ℳ ).

42
3.7 Algoritmul lui Ritter

Ritter a elaborat un procede u de partiționare pentru problemele de optimizare linară care au matricea
restricțiilor în formă bloc -giagonală, blocurile fiind unite atât prin restricții de cuplare cât și prin variabile
de cuplare. La fiecare iterație variabilele problemei se partițione ază în două submulțimi: o mulțime 𝑆1 în
care condițiile de nenegativitate sunt relaxate și o mulțime 𝑆2 în care acestea sunt impuse .

În momentul în care variabilele din 𝑆1 devin nenegative, soluția curentă este optimă. Procesul iterativ
pornește de la o partiție inițială care se modifică până când se găsește o partiție optimă.

Problema pe care o vom studia este:
inf{∑𝑐𝑖𝑇𝑥𝑖+𝑘
𝑖=1𝑐0𝑇𝑦} (15)

în raport cu:
∑𝐴𝑖𝑥𝑖+𝐺0 𝑦=𝑏0 (15.1)𝑘
𝑖=1
𝐷𝑖𝑥𝑖+𝐺𝑖 𝑦=𝑏𝑖,𝑖=1,𝑘̅̅̅̅̅ (15.2)
𝑥𝑖≥0,𝑖=1,𝑘̅̅̅̅̅,𝑦≥0 (15.3)

Datele problemei au următoarele dimensiuni:

𝐴𝑖∈ ℝ𝑚0𝑥 𝑛𝑖, 𝐷𝑖∈ ℝ𝑚𝑖 𝑥 𝑛𝑖,𝑖=1,𝑘̅̅̅̅̅

𝐺𝑖∈ ℝ𝑚𝑖𝑥 𝑛0, 𝑐𝑖∈ ℝ 𝑛𝑖, 𝑏𝑖∈ ℝ 𝑚𝑖,𝑖=0,𝑘̅̅̅̅̅.

Presupunem că 𝑟𝑎𝑛𝑔 (𝐷𝑖)=𝑚𝑖, pentru orice 𝑖=1,𝑘̅̅̅̅̅. Această ipoteză nu va restrange generealitatea
problemei, deoarece în cazul în care 𝑟𝑎𝑛𝑔 (𝐷𝑖)<𝑚𝑖, putem introduce variabile artif iciale pentru a obține
rangul dorit. Acestor variabile li se vor atribui în funcția obiectiv coeficienți de cost suficient de mari
astfel încât, în cazul unei soluții optime, valoarea tuturor variabilelor artificiale să fie zero.
De asemenea, presupunem cu noscut vectorul inițial 𝑦0∈ℝ𝑛0,𝑦0≥0, astfel încât pentru orice 𝑖=1,𝑘̅̅̅̅̅
sistemul:

𝐷𝑖𝑥𝑖=𝑏𝑖−𝐺𝑖 𝑦0
să fie compatibil (dacă nu exista un astfel de vector 𝑦0, atunci problema nu are soluții).
Pentru fiecare 𝑖=1,𝑘̅̅̅̅̅, vom considera subproblema:

inf {𝑐𝑖𝑇𝑥𝑖|𝐷𝑖𝑥𝑖=𝑏𝑖−𝐺𝑖 𝑦0,𝑥𝑖≥0 } (15.4)

Prin rezolvarea acestei subprobleme (15.4) se obține matricea de baza 𝐵𝑖 ( care poate fi cea optimă sau o
bază primal admisibilă care indică o direcție către −∞). Astfel coloanele matricei 𝐷𝑖 se pot partiționa în
două astfel : 𝐷𝑖=(𝐵𝑖⋮𝑅𝑖) și folosind notațiile din (15.2) vom obține:
𝑥𝐵𝑖=𝐵𝑖−1𝑏𝑖−𝐵𝑖−1𝑅𝑖𝑥𝑅𝑖−𝐺𝑖𝑦 (15.5)

43
Funcția obiectiv (15) și restricțiile de cuplare (15.1) se pot rescrie si ele în raport cu partiționarea
respectiva:
∑(𝑐𝐵𝑖𝑇𝑥𝐵𝑖+𝑘
𝑖=1𝑐𝑅𝑖𝑇𝑥𝑅𝑖)+𝑐0𝑇𝑦
∑(𝐴𝐵𝑖𝑘
𝑖=1𝑥𝐵𝑖+𝐴𝑅𝑖𝑥𝑅𝑖)+𝐺0𝑦=𝑏0

Dacă înlocuim pe 𝑥𝐵𝑖din relația (15.5) în relațiile de mai sus, vom obține problema redusă:

inf {∑𝛾𝑖𝑇𝑥𝑅𝑖+𝛾0𝑇𝑦𝑘
𝑖=1}+𝛼
în raport cu
∑𝑀𝑖𝑘
𝑖=1𝑥𝑅𝑖+𝑀0=𝛽
𝑥𝑅𝑖≥0,𝑖=1,𝑘̅̅̅̅̅,𝑦≥0 }
(𝑃𝑅)
unde am folosit notațiile:

𝛾𝑖𝑇=𝑐𝑅𝑖𝑇−𝑐𝐵𝑖𝑇𝐵𝑖−1𝑅𝑖
𝛾0𝑇= 𝑐0𝑇−∑𝑐𝐵𝑖𝑇𝑘
𝑖=1𝐵𝑖−1𝐺𝑖
𝛼=∑𝑐𝐵𝑖𝑇𝑘
𝑖=1𝐵𝑖−1𝑏𝑖
𝑀𝑖=𝐴𝑅𝑖−𝐴𝐵𝑖𝐵𝑖−1𝑏𝑖
𝑀0=𝐺0−∑𝐴𝐵𝑖𝐵𝑖−1𝐺𝑖𝑘
𝑖=1
𝛽=𝑏0−∑𝐴𝐵𝑖𝐵𝑖−1𝑏𝑖𝑘
𝑖=1

Numărul restricțiilor din problema redusa (𝑃𝑅) este 𝑚0, adică exact numărul restricțiilor de cuplare din
problema inițială. În problema redusă (𝑃𝑅), variabilele 𝑥ℬ𝑖,𝑖=1,𝑘̅̅̅̅̅, nu mai sunt supus e condițiilor de
nenegativitate, iar acestea sunt condiții relaxate. Drept urmare, mulțimea soluțiilor admisibile ale lui (𝑃𝑅)
le include pe cea a problemei (15) – (15.3 ) și astfel dacă problema redusă nu are soluții, atunci nici cea
ințiala nu poate avea soluții. Se poate întampla însă ca (𝑃𝑅) să aibe optim infint, chiar dacă problema
inițială are un optim finit . Pentru a evita o astfel de situație, la problema redusă se adaugă restricția de
marginire:

44
∑𝑒𝑖𝑇𝑥𝑅𝑖+𝑒0𝑇𝑦≤𝜇𝑘
𝑖=1
unde constanta 𝜇>0 are o valoare foarte mare, iar vectorii 𝑒𝑖 au toate componente le egale cu 1 și sunt
de dimensiuni în concordanță cu 𝑥𝑅𝑖.
Dacă 𝜇 este suficient de mare și la terminarea algoritmului acestă restricție este activă , atunci problema
inițială va avea optim infinit.

Fie (𝑥̅𝑅𝑖,⋯,𝑥̅𝑅𝑘,𝑦̅) o soluție optimă a problemei reduse (𝑃𝑅). Din relația (15.5) obținem:

𝑥̅𝐵𝑖=𝐵𝑖−1(𝑏𝑖−𝑅𝑖𝑥̅𝑅𝑖−𝐺𝑖𝑦̅), 𝑖=1,𝑘̅̅̅̅̅ (15.6)

Prin urmare (𝑥̅𝐵𝑖,𝑥̅𝑅𝑖,⋯,𝑥̅𝐵𝑘,𝑥̅𝑅𝑘,𝑦̅) va fi o soluție optimă și pentru problema inițială “modificat ă”, în
care condițiile 𝑥𝐵𝑖≥0 au fost eliminate.

Teorema de optimalitate

Dacă (𝑥̅𝑅𝑖,⋯,𝑥̅𝑅𝑘,𝑦̅) este o soluție optimă a problemei redus e (𝑃𝑅) și 𝑥̅𝐵 se determină din relația
(15.6), atunci (𝑥̅𝐵𝑖,𝑥̅𝑅𝑖,⋯,𝑥̅𝐵𝑘,𝑥̅𝑅𝑘,𝑦̅) este o soluție optimă pentru problema (15) – (15.3) dacă și numai
dacă 𝑥̅𝐵𝑖≥0 pentru orice 𝑖=1,𝑘̅̅̅̅̅.

Modi ficarea problemei reduse

Dacă testul de optimalitate nu este îndeplinit, atunci vom putea aplica principiul de relaxare prezentat
anterior. Vom forma o nouă problemă redusă, în care vom impune condiția de nenegativitate pentru unele
variabile din 𝐵𝑖 cu valori negative (vor intra în (𝑃𝑅)), în timp ce pentru anumite variabile din ℛ𝑖 cu valori
pozitive, acestă condiție va fi relaxată (vor ieși din (𝑃𝑅)).

Presupunem că după o eventuală reordonare a variabilelor din blocul i, că primle 𝑟≥1 componente ale
lui 𝑥̅𝐵𝑖 sunt negative:
(𝑥̅𝐵𝑖)𝑗<0,𝑗=1,𝑟̅̅̅̅
iar primele 𝑠≥0 componente ale lui 𝑥̅𝑅𝑖 sunt pozitive
(𝑥̅𝑅𝑖)𝑗>0,𝑗=1,𝑠̅̅̅̅

Legătura dinre 𝑥̅𝐵𝑖 și 𝑥̅𝑅𝑖 este dată de rela ția (15.5) care se poate rescrie astfel:
𝑥ℬ𝑖+𝐵𝑖−1𝑅𝑖𝑥𝑅𝑖=𝐵𝑖−1(𝑏𝑖−𝐺𝑖𝑦) (15.7)

Două cazuri sunt posibile:

45
CAZUL 1 : Matricea formată din primele r linii și primele s coloane ale lui 𝐵𝑖−1𝑅𝑖 conține cel puțin un
element diferit de zero. Considerăm că un astfel de element se află în poziția ( j, t ), unde 1≤𝑗≤𝑟 și
1≤𝑡≤𝑠, în relația (15.7) se poate efectua o operație de schimbare a bazei ( elementul ( j, t ) al
matricei lui 𝐵𝑖−1𝑅𝑖 va fi pivotul ), în care coloana 𝐷𝑖𝑗 este înlocuită de coloana 𝐷𝑖𝑡, astfel variabila (𝑥𝑅𝑖)𝑡
pentru care (𝑥̅𝑅𝑖 )𝑡>0, este înlocuită de variabila (𝑥ℬ𝑖)𝑗 pentru care (𝑥̅𝐵𝑖)𝑗<0. Astfel putem efectua
operația de schimbare a variabilei de mai multe ori în raport cu elementele nule din primele r linii și s
coloane ale lui 𝐵𝑖−1𝑅𝑖. Vom obține astfel pentru fiecare bloc i, o nouă matrice de bază 𝐵̌𝑖, cu ajutorul
acestor matri ce de bază, vom forma o nouă problemă redusă.

CAZUL 2: : Matricea formată din primele r linii și primele s coloane ale lui 𝐵𝑖−1𝑅𝑖 are toate elementele
egale cu zero, iar în acest caz nu mai putem efectua operații de schimbare a bazei, în sch imb, la problema
redusă se va adăuga una sau mai multe restricții care să impună condiția de nenegativitate încălcată.
Astfel dacă (𝑥ℬ𝑖)𝑗<0,1≤𝑗≤𝑟 pentru a impune condiția (𝑥ℬ𝑖)𝑗≥0, la problema (𝑃𝑅) se va adăuga
următoarea r estricție:
(𝐵𝑖−1)𝑗 (𝑏𝑖−𝑅𝑖𝑥𝑅𝑖−𝐺𝑖𝑦)≥0 (15.8)

care este de fapt linia j din relația (15.5). Operațiile descrise în cazurile 1 sau 2 se pot efectua pentru
fiecare bloc i, 1≤𝑖≤𝑘, pentru fiecare 𝑥̅𝐵𝑖 are comp onente negative. Dacă vom folosi matricele de bază
𝐵𝑖 rezultate la cazul 1 sau prin adăugarea restricțiilor din cazul 2, vom obține o nouă problemă redusă.

CAZUL 3: Dacă restricția (15.8) nu este activă pentru soluția optimă a problemei reduse
(𝐵𝑖−1)𝑗 (𝑏𝑖−𝑅𝑖𝑥𝑅𝑖−𝐺𝑖𝑦)>0, atunci aceasta poate fi eliminată.

CAZUL 4: Dacă restricția (15.8) este activă pentru soluția optimă a problemei reduse
(𝐵𝑖−1)𝑗 (𝑏𝑖−𝑅𝑖𝑥𝑅𝑖−𝐺𝑖𝑦)=0, iar în vect orul linie (𝐵𝑖−1)𝑗 𝑅𝑖 există un element nenul care permite
efectuarea unei schimbări de bază astfel încât (𝑥ℬ𝑖)𝑗 să fie înlocuită de o variabilă (𝑥𝑅𝑖)𝑡 pentru
care(𝑥̅𝑅𝑖 )𝑡>0, atunci restricția va fi eli minată.

CAZUL 5 : Dacă restricția (15.8) este activă și toate elementele din vectorul linie (𝐵𝑖−1)𝑗 𝑅𝑖 sunt nule,
atunci aceasta va fi menținută în problema redusă.

46
ALGORITM

Pasul 0: Prin rezolvarea subproblemelor (15 .4) se determină matricele de bază inițiale 𝐵𝑖 pentru fiecare
bloc 𝑖=1,𝑘̅̅̅̅̅ și se formează problema redusă (𝑃𝑅).

Pasul 1: Se rezolvă problema redusă, se obține soluția (𝑥̅𝑅𝑖,⋯,𝑥̅𝐵𝑘,𝑥̅𝑅𝑘,𝑦̅). Din relația (15 .6) se
calculează 𝑥̅𝐵𝑖,𝑖=1,𝑘̅̅̅̅̅. Dacă 𝑥̅𝐵𝑖≥0, pentru orice 𝑖=1,𝑘̅̅̅̅̅, atunci (𝑥̅𝐵𝑖,𝑥̅𝑅𝑖,⋯,𝑥̅𝐵𝑘,𝑥̅𝑅𝑘,𝑦̅) este o soluție
optimă a problemei (15) – (15.3). STOP.

Pasul 2: Pentru fiecare bl oc în care 𝑥̅𝐵𝑖 are componentele negative, dacă problema redusă conține
restricții suplimentare de tipul (15.8), atunci acestea vor fi prelucrate conform cazurilor 3 – 5.

Pasul 3: Pentru fiecare bloc în care 𝑥̅𝐵𝑖 are componentele ne gative, fie se efectuează operațiile de
schimbare a bazei corespunzătoare cazului 1 , fie se adaugă restricții pentru impunerea unor condiții de
nenegativitate din cazul 2 .

Pasul 4: Cu matricele de bază și restricțiile obținute din pașii 2 și 3 , se form ează o nouă problemă redusă
și se revine la pasul 1.

47

3.8 Algoritmul lui Rosen

Metoda de relaxare și partiționare a lui Rosen este o variantă a algoritmului lui Ritter, care se aplică la
problemele de optimizare liniară cu rest ricțiile bloc -unghiulare, adică au matricea restricțiilor în formă
bloc-diagonală, iar blocurile sunt unite doar prin restricții de cuplare. Acest algoritm nu mai necesită
adăugarea unor restricții suplimentare la problema redusă, se poate utiliza algoritm ul simplex dual,
deoarece baza optimă de iterație i, este înlocuită cu ușurință în iterația i+1 de una dual admisibilă.

Problema bloc -unghiulară este:

𝑖𝑛𝑓∑𝑐𝑖𝑇𝑥𝑖𝑘
𝑖=1 (16)
în raport cu:
∑𝐴𝑖𝑥𝑖=𝑏0𝑘
𝑖=1 (16.1)
𝐷𝑖𝑥𝑖=𝑏𝑖,𝑖=1,𝑘̅̅̅̅̅ (16.2)
𝑥𝑖≥0,𝑖=1,𝑘̅̅̅̅̅ (16.3)

cu următoarele dimensiuni:
𝐴𝑖∈ ℝ𝑚0𝑥 𝑛𝑖, 𝐷𝑖∈ ℝ𝑚𝑖 𝑥 𝑛𝑖,𝑖=1,𝑘̅̅̅̅̅

𝐺𝑖∈ ℝ𝑚𝑖𝑥 𝑛0, 𝑐𝑖∈ ℝ 𝑛𝑖, 𝑏𝑖∈ ℝ 𝑚𝑖,𝑖=0,𝑘̅̅̅̅̅.

Vom presupune, fără a infulența generalitatea problemei, că matricea restricțiilor (16.1) -(16.3) are rangul
egal cu
∑𝑚𝑖𝑘
𝑖=0.

De aici rezultă că rang ( 𝐷𝑖 )=𝑚𝑖 pentru orice 𝑖=1,𝑘̅̅̅̅̅. Pentru a detereminarea unor baze inițiale asociate
fiecărui bloc, se rezolvă subproblemele:

inf {𝑐𝑖𝑇𝑥𝑖|𝐷𝑖 𝑥𝑖=𝑏𝑖,𝑥𝑖≥0 },𝑖=1,𝑘̅̅̅̅̅ (16.4)

Dacă una din aceste subprobleme nu are soluție, atunci nici problema (16) -(16.3) nu va avea soluție. În
caz contrar, fie 𝐵𝑖 bazele obținute prin rezolvarea subproblemelor (16.4), acestea putând fi cele optime
sau cele care indică o direcție spre − ∞. Cu ajutorul acestor baze, partiționăm coloanele matricelor
𝐷𝑖=(𝐵𝑖⋮𝑅𝑖), sistemele (16.2) se pot rescrie astfel:

𝑥𝐵𝑖=𝐵𝑖−1𝑏𝑖−𝐵𝑖−1𝑅𝑖𝑥𝑅𝑖 (16.5)

48
Partiționăm și funcția obiectiv (16) și restricțiile de cuplare (16.1):

𝑖𝑛𝑓∑(𝑐𝐵𝑖𝑇𝑥𝐵𝑖+𝑐𝑅𝑖𝑇𝑥𝑅𝑖)𝑘
𝑖=1
∑(𝐴𝐵𝑖𝑘
𝑖=1𝑥𝐵𝑖+𝐴𝑅𝑖𝑥𝑅𝑖)=𝑏0
înlocuind aici pe 𝑥𝐵𝑖 din (16.5), obținem problema redusă:
𝑖𝑛𝑓∑𝛾𝑖𝑇𝑥𝑅𝑖+𝛼𝑘
𝑖=1
în raport cu:
∑𝑀𝑖𝑘
𝑖=1𝑥𝑅𝑖=𝛽
𝑥𝑅𝑖≥0,𝑖=1,𝑘̅̅̅̅̅}
(𝑃𝑅)

unde am folosit notațiile:

𝛾𝑖𝑇=𝑐𝑅𝑖𝑇−𝑐𝐵𝑖𝑇𝐵𝑖−1𝑅𝑖
𝛼=∑𝑐𝐵𝑖𝑇𝑘
𝑖=1𝐵𝑖−1𝑏𝑖
𝑀𝑖=𝐴𝑅𝑖−𝐴𝐵𝑖𝐵𝑖−1𝑏𝑖
𝛽=𝑏0−∑𝐴𝐵𝑖𝐵𝑖−1𝑏𝑖𝑘
𝑖=1

Problema redusă (𝑃𝑅) are doar 𝑚0 restricții. Deoarece restricțiile problemei reduse împreună cu (16.5)
fac parte din r estricțiile problemei inițiale, dacă (𝑃𝑅) nu are soluții, atunci nici problema (16) – (16.3) nu
va avea soluții. Există însă posibilitatea ca (𝑃𝑅) să aibă optim infinit, în timp ce problema inițială să aibă
optim finit. Pentru a evita această sit uație, adăugăm la problema redusă o restricție de mărginire de forma:
∑𝑒𝑖𝑇𝑥𝑅𝑖≤𝜇𝑘
𝑖=1
unde constanta 𝜇>0 are o valoare foarte mare, iar vectorii 𝑒𝑖 au toate componentele egale cu 1 și sunt
de dimensiuni în concordanță cu 𝑥𝑅𝑖. Dacă 𝜇 este suficient de mare și la terminarea algoritmului această
restricție este activă, atunci optimul problemei inițiale va tinde spre −∞.

Fie (𝑥̅𝑅𝑖,⋯,𝑥̅𝑅𝑘) o soluție optimă a problemei reduse (𝑃𝑅), iar din relația (16.5) obținem:

𝑥̅𝐵𝑖=𝐵𝑖−1𝑏𝑖−𝑅𝑖𝑥̅𝑅𝑖, 𝑖=1,𝑘̅̅̅̅̅ (16.6)

49
Prin urmare (𝑥̅𝐵1,𝑥̅𝑅1,⋯,𝑥̅𝐵𝑘,𝑥̅𝑅𝑘) va fi o soluție optimă și pentru problema inițială “modificat ă”, în care
condițiile 𝑥𝐵𝑖≥0 au fost relaxate.

Teorema de optimalitate

Dacă (𝑥̅𝑅1,⋯,𝑥̅𝑅𝑘) este o soluție optimă a problemei reduse (𝑃𝑅) și 𝑥̅𝐵𝑖 se determină din relația (16.6),
atunci (𝑥̅𝐵1,𝑥̅𝑅1,⋯,𝑥̅𝐵𝑘,𝑥̅𝑅𝑘) este o soluție optimă pentru problema (16) – (16.3) dacă și numai dacă
𝑥̅𝐵𝑖≥0,𝑖=1,𝑘.̅̅̅̅̅

Dacă testul de optimalitate nu este îndeplinit, se poate forma p nouă problemă redusă, în care se va
impune condiția de nenegativitate pentru cel putin o variabila din 𝐵𝑖 cu valori negative, în timp ce pentru
o anumită variabilă din 𝑅𝑖 cu valori pozitive, iar această condiție va fi relaxată. Problema (16) – (16.3) nu
conține variabile de cuplare, la problema r edusă nu mai trebuie să adăugăm restricții suplimentare, precum
am procedat în cazul algoritmului lui Ritter.

ALGORITM

Pasul 0: Prin rezolvarea subproblemelor (16.4) se determină matricele de bază inițiale 𝐵𝑖 pentru fiecare
bloc 𝑖=1,𝑘̅̅̅̅̅, iar da că una din subprobleme nu admite soluții rezultă că nici problema (16) – (16.3) nu are
soluții. STOP.
Altfel cu ajutorul bazelor 𝐵𝑖, 𝑖=1,𝑘̅̅̅̅̅ se formează problema redusă (𝑃𝑅).

Pasul 1: Se rezolvă problema redusă, dacă (𝑃𝑅) nu are soluție, atunci nici problema inițială nu are
soluție. STOP.
Altfel se obține soluția (𝑥̅𝑅1,⋯,𝑥̅𝑅𝑘).
Din relația (15.6) se calculează 𝑥̅𝐵𝑖,𝑖=1,𝑘̅̅̅̅̅. Dacă 𝑥̅𝐵𝑖≥0, pentru orice 𝑖=1,𝑘̅̅̅̅̅, atunci
(𝑥̅𝐵𝑖,𝑥̅𝑅𝑖,⋯,𝑥̅𝐵𝑘,𝑥̅𝑅𝑘,𝑦̅) este o soluție optimă a problemei (15) – (15.3). STOP.

Pasul 2: Se calculează 𝑥̅𝐵𝑖,𝑖=1,𝑘̅̅̅̅̅ din relația (16.6)

Pasul 3: Dacă 𝑥̅𝐵𝑖≥0, 𝑖=1,𝑘̅̅̅̅̅ atunci (𝑥̅𝐵1,𝑥̅𝑅1,⋯,𝑥̅𝐵𝑘,𝑥̅𝑅𝑘) este o soluție optimă a problemei (16) –
(16.3). STOP.
Pasul 4: Cu matricele de bază 𝐵𝑖 obținute la pasul anterior , se formează o nouă problemă redusă și se
revine la Pasul 1.

50

51

3.9 Metoda de descompunere a lui Benders

52
CAPITOLUL 4 – EXEMPLE NUMERICE