Cercetări operaţionale

Lorena Popa

Arad
26.09.2023

Lorena Popa Cercetări operaţionale Arad 26.09.2023 1 / 49

CE ÎNŢELEGEM PRIN CERCETĂRI
OPERAŢIONALE?

CO au ca obiect de studiu problemele de optimizare rezultate din

modelarea matematică a unor fenomene şi procese din domeniul
economic, ştiinţific, tehnic sau militar.

Lorena Popa Cercetări operaţionale Arad 26.09.2023 2 / 49

Exemplu

Compania X importă componente electronice şi asamblează două

tipuri de computere PC1 şi PC2. Vânzarea unui PC1 (respectiv PC2)
aduce un profit de 50 euro (respectiv 40 euro). Un PC1 are nevoie de
3 ore pentru asamblare iar un PC2 necesită 5 ore. Pentru următoarea
săptămână sunt disponibile 150 ore pentru asamblare. Compania are
ı̂n stoc numai 20 monitoare PC2; altfel spus, ı̂n următoarea
săptămână ea nu poate produce mai mult de 20 unităţi PC2. Pentru
depozitare un PC1 are nevoie de8 u.a. (unităţi de arie) iar un PC2 de
5 u.a. Spaţiul disponibil pentru depozitarea producţiei din următoarea
săptămână ı̂nsumează 300 u.a. Cererea este suficient de mare pentru
ca ı̂ntreaga producţie să fie vândută. Conducerea companiei este
interesată ı̂n elaborarea unui program de producţie pentru următoarea
săptămână care să-i aducă un profit maxim.

Lorena Popa Cercetări operaţionale Arad 26.09.2023 3 / 49

“...determinarea valorii maxime sau minime a unei funcţii liniare, ı̂n
care mai multe variabilele de optimizare sunt supuse unor
restricţii.”
O problemă de programare liniară este o “problemă care necesită
minimizarea unei funcţii ce are o expresie liniară ı̂n prezenţa unor
restricţii liniare...” (Dantzig)

Lorena Popa Cercetări operaţionale Arad 26.09.2023 4 / 49

ISTORIA PROGRAMĂRII LINIARE

A apărut la mijlocul secolului trecut, primele lucrări fiind publicate de L.

Kantorovici (1939) şi F. Hitchcock (1941).

Primele probleme rezolvate se refereau la organizarea optimă a

transporturilor maritime, necesităţile de aprovizionare a frontului,
planificarea misiunilor aviaţiei de bombardament.

În 1947 G. Dantzig şi J. Von Newmann creează metoda simplex care
sta la baza rezolvării problemelor de programare liniară. Ulterior
programarea liniară a cunoscut un mare avânt prin lucrările unor
matematicieni şi economia̧ti ca T. Koopmans, L. Ford, D. Fulkerson, W.
Cooper, H. Kuhn, găsindu-şi un câmp foarte larg de aplicaţii ı̂n
economie.

Lorena Popa Cercetări operaţionale Arad 26.09.2023 5 / 49

Necesităţile reale din economie au condus la apariţia dezvoltarea şi a
altor tipuri de programări, ca de exemplu:
programarea pătratică,
programarea convexă,
programarea ı̂n numere ı̂ntregi,
programarea stohastică,
programarea dinamică,
toate acestea fiind ı̂nglobate ı̂n termenul generic de programare
matematică.

Lorena Popa Cercetări operaţionale Arad 26.09.2023 6 / 49

IMPORTANŢA PROGRAMĂRII LINIARE

O gamă surprinzător de largă de probleme din diverse domenii pot fi

aduse la o formă corespunzătoare programării liniare.
Inginerie
Agricultură
Marketing
Economie
Finant, e (investiţii)
Publicitate

Lorena Popa Cercetări operaţionale Arad 26.09.2023 7 / 49

Ce este o problemă de programare liniară

O problemă de programare liniară (PL) este o problemă de optimizare

ı̂n care:
1. Se ı̂ncearcă maximizarea(sau minimizarea) unei funcţii ce are o
expresie liniară (numită funcţia obiectiv) dependentă de variabilele
de optimizare;
2. Valorile variabilelor de optimizare trebuie să satisfacă o mulţime
de restriicţii;
3. Fiecare restricţie de egalitate sau inegalitate trebuie să aibă o
expresie liniară;
4. O restricţie de semn este asociată fiecărei variabile de optimizare.
Pentru fiecare variabilă xi , avem (xi ≥ 0).

Lorena Popa Cercetări operaţionale Arad 26.09.2023 8 / 49

MODELUL MATEMATIC AL PROBLEMELOR DE
PROGRAMARE LINIARĂ

FORMA GENERALĂ

max(min)(c1 x1 + c2 x2 + · · · + cn xn )
ı̂n prezenţa restricţiilor:
 Pn
 j=1 aij xj 6 (>, =)bi
xj > 0
j = 1, n, i = 1, m.


Lorena Popa Cercetări operaţionale Arad 26.09.2023 9 / 49

EXEMPLU



 max(2x1 + x2 ) funcţia obiectiv
 3x1 + 2x2 6 3


x1 + x2 6 5 restricţiile specifice
4x1 + 5x2 6 8




x1 > 0, x2 > 0 restricţiile de ne-negativitate.


Observaţie
Programarea liniară permite numai expresii liniare

ax1 + bx2 + cx3 6 4 expresie corectă (1)

x13 + x2 + log2 x3 > 5 expresie incorectă (2)

Lorena Popa Cercetări operaţionale Arad 26.09.2023 10 / 49

MODELUL MATEMATIC AL PROBLEMELOR DE
PROGRAMARE LINIARĂ
FORMA CANONICĂ

max(c1 x1 + c2 x2 + · · · + cn xn )


 a11 x1 + a12 x2 + · · · + a1n xn 6 b1
 a21 x1 + a22 x2 + · · · + a12n xn 6 b2

.. .. ..


 . . .
am1 x1 + am2 x2 + · · · + amn xn 6 bn

sau

min(c1 x1 + c2 x2 + · · · + cn xn )


 a11 x1 + a12 x2 + · · · + a1n xn > b1
 a21 x1 + a22 x2 + · · · + a12n xn > b2

.. .. ..


 . . .
am1 x1 + am2 x2 + · · · + amn xn > bn

Lorena Popa Cercetări operaţionale Arad 26.09.2023 11 / 49
MODELUL MATEMATIC AL PROBLEMELOR DE
PROGRAMARE LINIARĂ

FORMA STANDARD

max(min)(c1 x1 + c2 x2 + · · · + cn xn )
ı̂n prezenţa restricţiilor:


 a11 x1 + a12 x2 + · · · + a1n xn = b1
 a21 x1 + a22 x2 + · · · + a12n xn = b2

.. .. ..


 . . .
am1 x1 + am2 x2 + · · · + amn xn = bn


Lorena Popa Cercetări operaţionale Arad 26.09.2023 12 / 49

VARIABILE DE COMPENSARE

Forma standard se obţine prin adăugarea de variabile pentru

forma inegalităţilor 6, s, i prin eliminarea de variabile forma
inegalităţilor >;
Variabilele suplimentare de compensare reprezintă diferenţa
dintre partea stângă şi cea dreaptă a restricţiilor;
În expresia funcţiei obiectiv, variabilele de compensare au
coeficienţii egali cu 0.

Lorena Popa Cercetări operaţionale Arad 26.09.2023 13 / 49

MODELUL MATEMATIC AL PROBLEMELOR DE
PROGRAMARE LINIARĂ

FORMA VECTORIALĂ
Se obţine prin partiţionarea matricei A după coloanele sale a1 , a2 , ...an

max(min)(Cx)

a1 x1 + a2 x2 + · · · + an xn = b
X >0

a - coloanele matricei A corespunzătoare sistemului de restricţii;

b - vectorul coloană al termenilor liberi;
x - cele n necunoscute
C - vectorul coeficienţilor funcţiei obiectiv.

Lorena Popa Cercetări operaţionale Arad 26.09.2023 14 / 49

DEFINIŢII

Osoluţie admisibilă a problemei de programare liniară este un

vector X = [x1 , x2 , . . . , xn ]t care satisface sistemul de ecuaţii al
restricţiilor, respectiv condiţia de nenegativitate;
O soluţie admisibilă de bază este o soluţie admisibilă care conţine
cel puţin (n–m) componente xj care au valoarea zero, ı̂n care m
este numărul restricţiilor iar n reprezintă numărul variabilelor de
optimizare;
O soluţie admisibilă de bază nedegenerată are exact m
necunoscute xj cu valoare pozitivă (> 0);
O soluţie optimală este o soluţie admisibilă pentru care funcţia
obiectiv atinge valori extreme (min sau max).

Lorena Popa Cercetări operaţionale Arad 26.09.2023 15 / 49

TEOREME ÎN PROGRAMAREA LINIARĂ

Teorema 1

Funcţia obiectiv ı̂şi realizează optimul ı̂ntr-un punct extrem al mulţimii

restricţiilor. Dacă ı̂şi realizează optimul ı̂n mai mult decât un punct
extrem, atunci funcţia obiectiv ia aceeaşi valoare ı̂n fiecare punct de pe
segmentul de dreaptă care uneşte oricare două puncte optimale.

Teorema 2

Un vector X = [x1 , x2 , ..., xn ]t este un punct extrem al mulţimii

restricţiilor unei probleme de programare liniară dacă şi numai dacă X
este o soluţie admisibilă de bază.

Lorena Popa Cercetări operaţionale Arad 26.09.2023 16 / 49

METODA GRAFICĂ DE REZOLVARE A PROBLEMELOR DE
PROGRAMARE LINIARĂ ÎN DOUĂ VARIABILE

Lorena Popa Cercetări operaţionale Arad 26.09.2023 17 / 49

Noţiuni matematice utile

Orice dreaptă ı̂mparte planul ı̂n două semiplane: unul pozitiv,

celălalt negativ;
Soluţia unui sistem de inecuaţii liniare ı̂n două variabile este
suprafaţa obţinută din intersecţia tuturor semiplanelor care sunt
soluţii ale inecuaţiilor sistemului;
Mulţimea tuturor punctelor care ı̂ndeplinesc toate restricţiile
modelului matematic se numeştemulţime admisibilă.
O funct, ie liniară (neconstantă) admite valori extreme (min sau
max) ı̂n vârfurile unei suprafeţe poligonale (mulţime admisibilă).

Lorena Popa Cercetări operaţionale Arad 26.09.2023 18 / 49

Etapele de rezolvare

I Modelarea matematică a problemei

- identificarea variabilelor, a restricţiilor şi a funcţiei obiectiv
II Rezolvarea propriu-zisă
- Determinarea mulţimii admisibile
- Calcularea valorilor funcţiei obiectiv ı̂n vârfurile poligonului
restricţiilor
- Determinarea valorilor optime
III Interpretarea datelor şi a soluţiei optime

Lorena Popa Cercetări operaţionale Arad 26.09.2023 19 / 49

Problema 1

Un fermier deţine 100 ha de teren agricol pe care poate cultiva grâu şi
lucernă. Este necesar să cultive cel puţin 10 ha cu grâu şi cel puţin 20 ha cu
lucernă, dispunând de 6000 euro pentru investiţia iniţială. Ştiind că pentru 1
ha de grâu se cheltuie 100 euro şi se obţin 125 euro iar pentru 1 ha de lucernă
se cheltuie 50 euro şi se obţin 60 euro, să se calculeze: investiţia minimă,
respectiv profitul maxim.

Lorena Popa Cercetări operaţionale Arad 26.09.2023 20 / 49

Problema 2

O firmă de construcţii trebuie să realizeze un complex de locuinţe ı̂nsumând

cel puţin 900 garsoniere, 2100 apartamente cu 2 camere şi 1400 apartamente
cu 3 camere. Se preconizează două tipuri de blocuri: primul tip cuprinde 40
apartamente cu 3 camere,30 apartamente cu 2 camere şi 10 garsoniere şi
costă 40 milioane lei, iar al doilea tip este format din 20 apartamente cu 3
camere, 50 apartamente cu 2 camere şi 30 garsoniere având costul de 50
milioane lei. Să se stabilească câte blocuri de fiecare tip trebuie construite
astfel ı̂ncât cheltuielile de construcţii să fie minime.

Lorena Popa Cercetări operaţionale Arad 26.09.2023 21 / 49

Problema 3

Un nutriţionist trebuie să conceapă o salată de legume cu brânzeturi care să

cântărească cel mult 400 g şi cel puţin 200 g. Pentru ca salata să fie
sănătoasă, cantitatea de legume trebuie să depăşească de cel puţin 3 ori
cantitatea de brânzeturi, iar nutriţionistul vrea să adauge cel puţin 25 g de
brânzeturi. Calculaţi numărul minim şi numărul maxim de kcal pe care ı̂l
poate avea salata, ştiind că brânzeturile au ı̂n medie 300 kcal iar legumele au
ı̂n medie20 kcal. Dintre combinaţiile obţinute, care este cea mai dietetică (cu
cel mai mic nr de calorii la 100 g)?

Lorena Popa Cercetări operaţionale Arad 26.09.2023 22 / 49

Problema 4

Aprovizionarea oraşului M cu un anumit produs de larg consum se face din

trei centre: A1 , A2 , A3 . Cantitatea totală din acel produs, solicitată de oraşul
M este de 120 vagoane. Cele trei centre dispun de 72, 36, respectiv 96
vagoane din produsul respectiv. Timpul necesar de ı̂ncărcare şi descărcare a
unui vagon diferă de la un centru la altul, funcţie de gradul de mecanizare,
astfel: 7 ore, 4 ore, respectiv 8 ore. Timpul total alocat lucrărilor de ı̂ncărcare
şi descărcare a vagoanelor este limitat la cel mult 912 ore. Costul
transportului unui vagon din cele trei centre ı̂n oraşul M este de 3, 5, 1 u.m.
Câte vagoane trebuie trimise din fiecare centru ,ı̂ncât oraşul M să primească
ı̂ntreaga cantitate de 120 vagoane de care are nevoie, iar costul total al
transportului sa fie minim.

Lorena Popa Cercetări operaţionale Arad 26.09.2023 23 / 49

 ALGORITMUL SIMPLEX

Lorena Popa Cercetări operaţionale Arad 26.09.2023 24 / 49

FORMA TABELARĂ A PROBLEMELOR DE
PROGRAMARE LINIARĂ

Se consideră o problemă de programare liniară adusă la forma

standard.
Dacă scriind matricea ataşată sistemului de restricţii A de tipul m × n,
aceasta conţine submatricea unitate de rang m, atunci problema este
sub formă tabelară.
Coloanelor submatricii unitate Im li se atribuie vectorii bazei canonice
u1 , u2 , ..., um , iar celorlalte coloane a matricii sistemului, vectorii
a1 , a2 , ....
Variabilele ce corespund vectorilor u se numesc variabile de bază, iar
variabilele corespunzătoare vectorilor a se numesc variabile
secundare.

Lorena Popa Cercetări operaţionale Arad 26.09.2023 25 / 49

TABLOUL SIMPLEX - tabelul de pornire

O problemă de programare liniară sub formă tabelară poate fi scrisă

ı̂ntr-un tablou astfel:
- Deasupra vectorilor ce corespund coloanelor matricii asociate
sistemului restricţiilor se scriu coeficienţii funcţiei obiectiv;
- În stânga tabelului se scriu vectorii bazei canonice şi coeficienţii
corespunzători din funcţia obiectiv;
- Se completează linia criterială (linia evaluării nete) astfel: se
multiplică elementele de pe fiecare coloană cu coeficienţii din
funcţia obiectiv corespunzător vectorilor din bază, fiecare element
cu coeficientul aflat pe linia lui, după care se ı̂nsumează, iar din
valarea obţinută se scade coeficientul din funţia obiectiv,
corespunzătoare coloanei.

Lorena Popa Cercetări operaţionale Arad 26.09.2023 26 / 49

TABLOUL SIMPLEX- stabilirea pivotului

- Se stabileşte coloana pivotului: corespunde celei mai negative

valori de pe linia criterială;
n o
coloana b
- Se stabileşte linia pivotului: se determină min coloana pivot , luând
ı̂n considerare doar valoarile pozitive de pe coloana pivotului;
- La intersecţia coloanei pivot cu linia pivot se găseşte elementul
pivot.

Lorena Popa Cercetări operaţionale Arad 26.09.2023 27 / 49

TABLOUL SIMPLEX - etapele metodei pivot

- Vectorul de pe coloana pivotului ia locul vectorului de pe linia

pivotului;
- Elementele de pe linia pivotului se ı̂mpart la pivot;
- Coloana pivotului se completează cu zero;
- Restul elementelor se calculează cu regula dreptunghiului.

Se completează din nou linia criterială şi procedura se reia până când
pe linia criterială nu mai sunt valori negative, ceea ce indică obţinerea
unei soluţii optime.

Lorena Popa Cercetări operaţionale Arad 26.09.2023 28 / 49

OBSERVAŢII

1. Procedura descrisă se aplică problemelor de maximizare. Pentru

problemele de minimizare se procedează astfel:
- se multiplică funcţia obiectiv cu −1 şi se maximizează,
sau
- se alege coloana pivotului după cel mai mare număr pozitiv de pe
linia criterială, iar algoritmul se ı̂ncheie când pe linia criterială nu
mai sunt valori pozitive;
2. La algoritmul simplex, pivotul nu poate fi negativ.

Lorena Popa Cercetări operaţionale Arad 26.09.2023 29 / 49

OBSERVAŢII

n o
coloana b
1. Dacă raportul min coloana pivot care indică elementul pivot, nu
este unic, atunci soluţia este degenerată şi deci problema de
programare liniară este degenerată.
2. Dacă aplicând algoritmul simplex se ajunge ı̂n imposibilitatea de a
alege pivot (de pe coloana pivotului niciun element nu poate fi
pivot, toate valorile fiind negative sau zero), atunci problema are
optim infinit.
3. Dacă la ı̂ncheierea algoritmul simplex se obţin pe linia criterială şi
alte zerouri faţa de cele corespunzătoare vectorilor bazei, atunci
problema are optim finit multiplu.

Lorena Popa Cercetări operaţionale Arad 26.09.2023 30 / 49

PROBLEMA 1

O societate produce produsele P1 , P2 , P3 utilizând materiile prime M1 şi M2

ı̂n cantităţi limitate, conform tabelului:

P1 P2 P3 Cantitatea disponib.
M1 2 3 1 11
M2 1 2 2 6
Beneficiu 3 5 2

Din cauza lipsei spaţiului de depozitare, producţia nu depăşeşte 20 de unităţi.

Să se determine un plan de producţie astfel ı̂ncât beneficiul să fie maxim.

Lorena Popa Cercetări operaţionale Arad 26.09.2023 31 / 49

PROBLEMA 2

Fabrica de cut, ite ”Taie-bine” pune ı̂n vânzare seturi de cuţite de bucătărie.
Setul de bază conţine 2 cuţite utilitare şi un cuţit de bucătar. Setul regular
conţine 2 cuţite utilitare, un cuţit de bucătar şi un feliator iar setul deluxe
conţine 3 cuţite utilitare, un cuţit de bucătar şi un feliator. Profiturile obţinute
sunt: 30 USD la setul de bază, 40 USD la setul regular şi 60 USD la setul
deluxe. Fabrica are un stoc de 800 cuţite utilitare, 400 cuţite de bucătar şi
200 de feliatoare. Dacă sunt vândute toate seturile constituite, să se
folosească algoritmul simplex pentru a determina câte seturi din fiecare fel se
pot constitui pentru a maximiza profitul. Care este valoarea maximă rezultată?

Lorena Popa Cercetări operaţionale Arad 26.09.2023 32 / 49

PROBLEMA 3

Pentru a fabrica rochiţe, pantaloni şi sacouri o fabrică utilizează maşini de

vopsit, de tăiat şi de cusut. Pentru producerea unei rochiţe se utilizează maşina
de vopsit 1 oră, maşina de tăiat 1 oră şi maşina de cusut 1 oră. Pentru un
pantalon se utilizează maşina de vopsit 2 ore, maşina de tăiat 1 oră şi maşina
de cusut 2 ore. Pentru un sacou se utilizează maşina de vopsit 1 oră, maşina
de tăiat 2 ore şi maşina de cusut 3 ore. Maşina de vopsit poate fi utilizată 20
de ore, maşina de tăiat 12 ore şi maşina de cusut 22 ore. Toate produsele
fabricate se vând şi se obţine un profit de 4 euro pentru fiecare rochiţă, 5 euro
pentru fiecare pantalon şi 8 euro pentru fiecare sacou. Utilizând algoritmul
simplex, ı̂ntocmiţi un plan de producţie pentru un profit maxim.

Lorena Popa Cercetări operaţionale Arad 26.09.2023 33 / 49

METODA PENALIZĂRII sau METODA BAZEI ARTIFICIALE

Lorena Popa Cercetări operaţionale Arad 26.09.2023 34 / 49

METODA PENALIZĂRII
Se aplică atunci când problema de programare liniară adusă la forma
standard nu este sub formă tabelară (matricea A a sistemului de
restricţii nu conţine submatricea unitate).
În acest caz, se poate proceda astfel:
- se adaugă coloanele lipsă din submatricea unitate, pentru a avea
toţi vectorii bazei canonice din Rm şi se obţine matricea extinsă Ā;
- coloanele adăugate corespund unor variabile artificiale, notate xa ;
- se scrie problema echivalentă matricei extinse, ı̂n care ı̂n funcţia
obiectiv se trec şi variabilele artificiale multiplicate cu −M (M se
numeşte coeficient de penalizare, are valoare pozitivă foarte
mare);
- pentru problema astfel obţinută se aplică algoritmul simplex.
Dacă algoritmul se ı̂ncheie şi ı̂n bază se mai află vectori ce provin de
la variabilele artificiale xa , atunci problema nu are soluţii.

Lorena Popa Cercetări operaţionale Arad 26.09.2023 35 / 49

PROBLEMA 1

min(x1 + 2x2 + 2x3 + x4 )



 x1 + x2 + 2x3 + x4 = 10
2x1 + x2 + 2x3 + 2x4 = 12

x + 3x2 + 2x3 + 2x4 = 16
 1


x1 , x2 , x3 , x4 > 0.

Lorena Popa Cercetări operaţionale Arad 26.09.2023 36 / 49

PROBLEMA 2

max(2x1 + x2 − x3 )

 3x1 + 2x2 − x3 > 4
x − x2 + 2x3 6 8
 1
x1 , x2 , x3 > 0.

Lorena Popa Cercetări operaţionale Arad 26.09.2023 37 / 49

PROBLEMA 3

max(2x1 − 3x2 − x3 + 4x4 )


 x1 − x2 + 2x3 + 2x4 > 3
3x1 + x2 + x3 − x4 6 −2
x1 , x2 , x3 , x4 > 0.


Lorena Popa Cercetări operaţionale Arad 26.09.2023 38 / 49

PROBLEMA 4

max(x1 + x2 + x3 )

 3x1 + x2 − x3 = 5
3x1 + 2x2 + x3 = 7
x1 , x2 , x3 > 0.


Lorena Popa Cercetări operaţionale Arad 26.09.2023 39 / 49

 PROBLEMA DUALĂ

Lorena Popa Cercetări operaţionale Arad 26.09.2023 40 / 49

TIPURI DE RESTRICŢII

i) O restricţie se numeşte concordantă dacă este de tipul:

ai1 x1 + ai2 x2 + · · · + ain xn > bi ı̂ntr-o problemă de minim;
ai1 x1 + ai2 x2 + · · · + ain xn 6 bi ı̂ntr-o problemă de maxim.
ii) O restricţie se numeşte neconcordantă dacă este de tipul:
ai1 x1 + ai2 x2 + · · · + ain xn 6 bi ı̂ntr-o problemă de minim;
ai1 x1 + ai2 x2 + · · · + ain xn > bi ı̂ntr-o problemă de maxim.
iii) O restricţie de tipul ai1 x1 + ai2 x2 + · · · + ain xn = bi nu este nici
concordantă nici neconcordantă.

Lorena Popa Cercetări operaţionale Arad 26.09.2023 41 / 49

Problema primală - Problema duală

Duala va fi o problemă de minim dacă primala este de maxim şi

reciproc;
Duala va avea m variabile,u T = (u1 , u2 , . . . , um ) număr egal cu
numărul de restricţii al primalei, fiecare variabilă ui fiind asociată
unei restricţii i a primalei;
Coeficienţii funcţiei obiectiv a dualei sunt termenii liberi ai
restricţiilor primalei;
Termenii liberi din restricţiile dualei sunt coeficienţii funcţiei
obiectiv a primalei;

Lorena Popa Cercetări operaţionale Arad 26.09.2023 42 / 49

Problema primală - Problema duală

Restricţiile dualei se obţin ı̂nmulţind fiecare coloană a matricei

primalei cu vectorul variabilelor dualei;
Restricţia j a dualei va fi:
- concordantă, dacă xj > 0
- neconcordantă, dacă xj 6 0
- egalitate, dacă xj oarecare.
Variabila ui va fi:
- ui > 0, dacă restricţia corespunzătoare din primală este
concordantă
- ui 6 0, dacă restricţia corespunzătoare din primală este
neconcordantă
- ui oarecare, dacă restricţia corespunzătoare din primală este
egalitate.

Lorena Popa Cercetări operaţionale Arad 26.09.2023 43 / 49

Exemplu

Problema primală - Problema duală


max(2x1 − 5x2 + 4x3 ) 

 min(7u1 + 6u2 + 3u3 + 8u4 )

 x1 − x2 + 4x3 > 7 

 u1 − 5u2 + u3 + 2u4 6 2

 

−5x1 + x2 + 3x3 = 6

−u1 + u2 − 5u4 = −5
x1 + 2x3 6 3
4u 1 + 3u2 + 2u3 − u4 > 4

 

2x 1 − 5x2 − x3 > 8

 

u1 6 0, u2 oarecare, u3 > 0, u4 > 0

 
x1 6 0, x2 oarecare, x3 > 0,


Lorena Popa Cercetări operaţionale Arad 26.09.2023 44 / 49

Teorema fundamentală a dualităţii

Dacă una din cele două probleme are soluţie optimă finită atunci
şi cealaltă are soluţie optimă finită şi valorile funcţiilor obiectiv
corespunzătoare celor două soluţii sunt egale;
Dacă una din cele două probleme are optim infinit atunci cealaltă
nu are soluţii admisibile;
Dacă una din cele două probleme nu are soluţii admisibile atunci
cealaltă are optim infinit sau nu are soluţii admisibile.

Lorena Popa Cercetări operaţionale Arad 26.09.2023 45 / 49

Motivele studierii problemei duale

În unele cazuri, rezolvarea dualei este mult mai uşoară decât
rezolvarea primalei, de exemplu când numărul de restricţii al
primalei este mai mare decât numărul de variabile al acesteia sau
când primala necesită mai multe variabile suplimentare decât
duala;
În cele mai multe probleme economice, a căror rezolvare se face
printr-un model de programare liniară, soluţia dualei aduce o serie
de informaţii suplimentare despre problema studiată. Semnificaţia
economică a soluţiei dualei depinde de specificul problemei şi
trebuie găsită de la caz la caz;
Dacă una din cele două probleme nu are soluţii admisibile atunci
cealaltă are optim infinit sau nu are soluţii admisibile.

Lorena Popa Cercetări operaţionale Arad 26.09.2023 46 / 49

Observaţii

Intr-o problemă economică, nenegativitatea variabilelor primalei

(xj > 0) impune ca ı̂n duală toate restricţiile să fie concordante;
Duala problemei duale este problema primală;
Dacă o problemă este la forma canonică atunci şi duala sa este o
problema la forma canonică;
Dacă o problemă este la forma standard atunci duala sa nu este
la forma standard.

Lorena Popa Cercetări operaţionale Arad 26.09.2023 47 / 49

PROBLEMA 1

min(8x1 + 16x2 )

 x1 + 5x2 > 9
2x1 + 2x2 > 10
x1 , x2 > 0.


Lorena Popa Cercetări operaţionale Arad 26.09.2023 48 / 49

PROBLEMA 2

min(4x1 + 5x2 + 8x3 )


 3x1 + 2x2 + 2x3 > 10
4x1 + 5x2 > 25
x1 , x2 , x3 > 0.


Lorena Popa Cercetări operaţionale Arad 26.09.2023 49 / 49