Acasă→design peisagistic→ Dual zlp online. Probleme duale de programare liniară. Rezultatele comparării problemelor directe și duale

Dual zlp online. Probleme duale de programare liniară. Rezultatele comparării problemelor directe și duale

Cu acest calculator online puteți obține:

rezolvarea problemei duale de programare liniara prin solutii ale problemei directe (prin metoda simplex, prin teorema dualitatii);
planul optim al problemei duale; estimări de resurse (estimare duale);
identificarea resurselor (excedente) rare și nedeficiente;
modificarea funcției obiectiv la modificarea parametrilor; fundamentarea eficacității planului optim;
analiza stabilității estimărilor duale (modificare limită b i , c i); analiza opțiunilor de plan suboptimal.

Instruire. Selectați numărul de variabile și numărul de constrângeri pentru problema de programare liniară directă, faceți clic pe Următorul. Soluția rezultată este salvată într-un fișier Word și Excel. În acest caz, restricții de tip x i ≥ 0 nu tine cont. Dacă problema LP directă nu are o soluție, dar este necesară face o problema dubla sau una dintre variabilele x i este nedefinită, atunci puteți utiliza acest calculator.

Ideea principală a teoriei dualității: pentru fiecare problemă de programare liniară (LP), există o problemă LP, a cărei soluție este strâns legată de linie. în care:

matricea de constrângeri a problemei duale (DZ) este matricea transpusă a problemei directe;
vectorul „prețurilor” pentru problema directă este vectorul părților corecte ale restricțiilor problemei de teledetecție și invers.

Reguli generale pentru compilarea unei probleme duale ():

Drept	dual
Funcția țintă (max)	Partea dreaptă a constrângerilor
Partea dreaptă a constrângerilor	Funcția țintă (min)
A - matricea constrângerii	A T - matricea constrângerii
i-a constrângere: ≤ 0, (≥ 0)	Variabila y i ≥ 0, (≤ 0)
i -a constrângere: = 0	Variabila y i ≠ 0
Variabila x j ≥ 0 (≤ 0)	j-a constrângere: ≤ 0 (≥ 0)
Variabila x j ≠ 0	j-a constrângere: = 0

Exemplu. Să definim valoare maximă funcția obiectiv F(X) = 3x 1 +5x 2 +4x 3 în următoarele condiții de constrângere.
0,1x1 + 0,2x2 + 0,4x3 ≤1100
0,05x1 + 0,02x2 + 0,02x3 ≤120
3x1 + x2 + 2x3 ≤8000

Să rezolvăm problema directă prin metoda simplex.
Pentru a construi primul plan de referință, reducem sistemul de inegalități la un sistem de ecuații prin introducerea de variabile suplimentare.
0,1x1 + 0,2x2 + 0,4x3 + 1x4 + 0x5 + 0x6 = 1100
0,05x1 + 0,02x2 + 0,02x3 + 0x4 + 1x5 + 0x6 = 120
3x1 + 1x2 + 2x3 + 0x4 + 0x5 + 1x6 = 8000
Variabilele de bază sunt variabile care sunt incluse într-o singură ecuație a sistemului de constrângeri și, în plus, cu un coeficient unitar.
Să rezolvăm sistemul de ecuații în raport cu variabilele de bază: x 4 , x 5 , x 6
Presupunând că variabilele libere sunt 0, obținem primul design de referință: X1 = (0,0,0,1100,120,8000)
Deoarece problema este rezolvată la maximum, coloana de început este aleasă după numărul maxim negativ și rândul index. Toate transformările sunt efectuate până când sunt obținute elemente pozitive în rândul index.
Să trecem la algoritmul principal al metodei simplex.

Plan	Bază	ÎN	x 1	x2	x 3	x4	x5	x6	min
1	x4	1100	0.1	0.2	0.4	1	0	0	5500
	x5	120	0.05	0.02	0.02	0	1	0	6000
	x6	8000	3	1	2	0	0	1	8000
Linie index	F(X1)	0	-3	-5	-4	0	0	0	0

Iterația #0
Linia de bază actuală nu este optimă deoarece există cote negative în rândul indexului
Vom alege ca principală coloana corespunzătoare variabilei x 2, deoarece modulo are cel mai mare coeficient.
Prin urmare, prima linie conduce. Elementul de rezoluție este 0,2 și este situat la intersecția coloanei principale și a rândului principal. Formăm următoarea parte a tabelului simplex. În loc de variabila x, planul 1 va include variabila x 2 . Linia corespunzătoare variabilei x 2 din planul 1 se obține prin împărțirea tuturor elementelor dreptei x 4 din planul 0 la elementul de activare RE=0,2. În locul elementului de rezoluție din planul 1, obținem 1. >În celulele rămase ale coloanei x 2 din planul 1, scriem zerouri.
Astfel, în noul plan se umple 1 rând x 2 și coloana x 2.
Toate celelalte elemente ale noului plan 1, inclusiv elementele rândului index, sunt determinate de regula dreptunghiului.
Pentru a face acest lucru, selectați patru numere din planul vechi, care sunt situate la vârfurile dreptunghiului și includ întotdeauna elementul de activare al RE.
NE \u003d SE - (A * B) / RE
STE - element din planul vechi, RE - element rezolutor (0,2), A și B - elemente din planul vechi, formând un dreptunghi cu elemente de STE și RE.

Plan	Bază	ÎN	x 1	x2	x 3	x4	x5	x6	min
2	x2	5500	0.5	1	2	5	0	0	11000
	x5	10	0.04	0	-0.02	-0.1	1	0	250
	x6	2500	2.5	0	0	-5	0	1	1000
Linie index	F(X2)	27500	-0.5	0	6	25	0	0	0

Iterația #1
Linia de bază actuală nu este optimă deoarece există coeficienți negativi în rândul indicelui. Ca lider, vom alege coloana corespunzătoare variabilei x 1, deoarece modulo are cel mai mare coeficient.
Calculați valorile lui D i pe rânduri ca coeficient de împărțire și alegeți cel mai mic dintre ele:
Prin urmare, a doua linie conduce. Elementul de rezolvare este 0,04 și este situat la intersecția coloanei principale și a rândului principal. Formăm următoarea parte a tabelului simplex. În loc de variabila x, planul 2 va include variabila x 1 . Linia corespunzătoare variabilei x 1 din planul 2 se obține prin împărțirea tuturor elementelor liniei x 5 din planul 1 la elementul de activare RE=0,04. În locul elementului de activare din planul 2, obținem 1. În celulele rămase ale coloanei x 1 din planul 2, scriem zerouri.
Astfel, în noul plan se completează 2 rând x 1 și coloana x 1.
Toate celelalte elemente ale noului plan 2, inclusiv elementele rândului index, sunt determinate de regula dreptunghiului.
Să prezentăm calculul fiecărui element sub forma unui tabel:

Exemplul #2. Pentru a finaliza sarcina, este necesar ca 50 AK de tipul 1, 30 AK de tipul 2 și 45 AK de tipul 3 să decoleze simultan. AK sunt situate pe aerodromurile I și II. Tabelul arată timpul mediu de decolare (în secunde) de pe aerodromul corespunzător al unei aeronave de acest tip.

Numărul aerodromului	Tastați AK
Numărul aerodromului	1	2	3
eu	4	10	10
II	6	8	20

Cum ar trebui plasat AK-ul pe aerodromuri astfel încât timpul pentru decolarea succesivă a întregii ținute AK să fie minim? În ce măsură se poate modifica timpul de decolare a fiecărui AK, astfel încât soluția optimă să rămână aceeași.

Soluţie. Se notează prin:
x 11 - AK primul tip la primul aerodrom,
x 12 - AK primul tip la al doilea aerodrom,
x 21 - AK al doilea tip la primul aerodrom,
x 22 - AK al doilea tip la al doilea aerodrom,
x 31 - AK al treilea tip la primul aerodrom,
x 32 - AK al treilea tip la al doilea aerodrom,

Restricții
4x11 + 6x12 = 50
10x21 + 8x22 = 30
10x31 + 20x32 = 45
x 11 , x 12 , x 21 , x 22 , x 31 , x 32 ≥ 0
x 11 , x 12 , x 21 , x 22 , x 31 , x 32 sunt numere întregi

funcție obiectivă
4x 11 + 6x 12 + 10x 21 + 8x 22 +10x 31 + 20x 32 → min

După soluția găsită, răspunsul la prima întrebare va fi valorile variabilelor x 11 , x 12 , x 21 , x 22 , x 31 , x 32 . Informațiile despre răspunsul la a doua întrebare vor fi găsite în secțiunea Intervale de stabilitate a coeficienților funcției obiective.

Deoarece există trei vectori unitari, atunci
puteți scrie imediat o linie de bază
X=(0,0,0,360,192,180).
Compuneți tabloul simplex nul

Verificăm linia de bază rezultată
pentru optimitate.
Se calculează valoarea funcției obiectiv și
diferențe simplex.
F0 c P0 0 360 0 192 0 180 0,
1 z1 c1 c P1 c1 9,
2 z2 c2 cP2 c2 10,...

După cum se poate vedea din tabelul 0 diferit de zero
sunt variabilele x4 , x5 , x6 și x , x , x
1
2
3
sunt egale cu zero, deoarece nu sunt de bază, ci gratuite.
Variabile suplimentare x4 , x5 , x6
ia-le valorile conform
restricții.
Aceste valori variabile corespund următoarelor
„plan” în care nu se produce nimic, materii prime
nu este utilizat și valoarea funcției obiectiv este
zero, adică costul produselor fabricate
absent.
Un astfel de plan, desigur, nu este optim.
Acest lucru poate fi văzut și de pe al 4-lea rând al tabelului, în care
există trei evaluări negative -9, -16 și -10.

10.

Numerele negative nu numai
indică posibilitatea de creștere
costul total de producție (în
coloane deasupra evaluărilor negative
sunt numere pozitive), dar de asemenea
arată cât de mult va crește această sumă
la introducerea unei unităţi a unuia sau altuia
Tip produs.
Deci, numărul -9 înseamnă că atunci când este inclus în
planul de producție pentru un produs A
crește costul
produse pentru CU 9

11.

Dacă este inclus în planul de producție pentru
un produs B și C, apoi costul total
produsele fabricate vor crește
de CU 10, respectiv 16. Prin urmare, cu
fezabil din punct de vedere economic
este includerea în plan a produselor C.
Același lucru trebuie făcut din acel punct
vedeți că -16 este cel mai mic
rating negativ. Deci, în bază
introducem vectorul P3 .

12.

Să găsim numărul Q.
360 192 180
Qmin
;
;
min 30; 24;60
3
12 8
Introduceți-l în ultima coloană a tabelului.
Numărul 24 corespunde vectorului P5 .
192/8=24 din punct de vedere economic
înseamnă câte produse
întreprinderea poate produce ţinând cont
ratele de consum și volumele disponibile de materii prime
de orice fel.

13.

Deoarece fiecare tip de materie primă este disponibil
respectiv 360, 192 și 180 kg, iar pentru unul
produsul C este necesar să cheltuiască materii prime din fiecare
speciile 12, 8 și 3 kg, apoi numărul maxim
produsele C, care pot fi fabricate
întreprinderea este egală cu
min(360/12.192/8.180/3)=192/8=24, i.e.
factor limitator pentru producție
produse C este volumul disponibil de materii prime
al 2-lea fel. Având în vedere întreprinderea sa poate
produce 24 de produse C. În același timp, materiile prime de al 2-lea tip vor fi utilizate integral și,
deci vectorul trebuie exclus din
P5
bază.

14.

Facem următorul tabel. In ea
permisiunea este a doua linie,
iar coloana de rezoluție este a treia. Pe
intersecția lor este elementul 8.
Împărțiți a doua linie la 8 și apoi
setată la zero prin metoda Jordan-Gauss
sau conform formulelor triunghiulare al treilea
coloană.

15.

16.

Să calculăm diferențele simplex și să completăm al 4-lea rând al tabelului.
Cu acest plan de producție
24 de produse C sunt fabricate și rămân
nefolosite 72 kg materii prime 1 si 108 kg
materii prime de al 3-lea tip. Al 2-lea tip de materie primă folosită
complet. Costul tuturor produselor
acest plan este CU 384. Specificat
numerele sunt scrise în coloana Plan. S-a terminat din nou
parametrii sarcinii, dar au fost supuși
schimbări. S-au schimbat și alte date.
coloane. Conținutul lor economic
devenit și mai dificil.

17.

Există o evaluare negativă -2.
Planul poate fi îmbunătățit. Introducem in baza
vectorul P2. Calcula
72 24 108
Q min;
;
min 8; 48;72 8.
9 1/ 2 3 / 2
.
Derivam din baza P4 .

18.

Permisiv va fi prima linie și a doua
coloană. Elementul permisiv 9.
Împărțiți cu 9 primul rând, completați
Primul rând al noului tabel, atunci
setați a doua coloană la zero. Pentru aceasta
înmulțiți primul rând cu (-1/2) și
se adaugă la al 2-lea și apoi se înmulțește pe primul
rând cu (-3/2) și adăugați la a treia linie.
Să completăm tabelul 2.

19.

20.

Suntem convinși de asta
calcularea diferenţelor simplex
1 cP1 c1 10 1 16 0,25 9 5,
2 cP2 c2 10 1 16 0 10 0,
3 cP3 c3 10 0 16 1 0 0 16 0,
4 cP4 c4 10 1/ 9 16 1/ 8 0 (1/ 6) 2/ 9,
5 cP5 -c5 =10 (-1/6)+16 5/24+0(-1/2)=5/3,
6 0.

21.

Planul optim de producție nu este
Se are în vedere o lansare a produsului.Introducere la
planul de producţie de tip A ar duce la
scăderea costului total menționat.
Acest lucru poate fi văzut de pe al 4-lea rând al coloanei, unde numărul 5
arată că pentru acest plan, includerea
în ea duce la ieşirea unei unităţi de produs A
doar pentru a reduce valoarea totală
cost pe CU5
Deci, planul prevede lansarea a 8 produse
B și 20 de produse C. Materii prime de tipurile 1 și 2
este folosit în întregime, iar tipul 3 rămâne nefolosit 96 kg.

22. PROBLEME DUAL DE PROGRAMARE LINEARĂ

Fiecare PLP poate fi asociat
problemă numită duală față de original
sarcină.
Luați în considerare problema utilizării
resurse. Să presupunem că compania A
produce n tipuri de produse, valoarea
a cărui ieșire este determinată de variabile
x1, x2, ..., xn
.
În producție, m diferit
tipuri de resurse, al căror volum este limitat
valorile b1, b2, ..., bn.

23.

Sunt cunoscute ratele de cost ale fiecărei resurse pe unitate
fiecare tip de produs, formând o matrice,
a11
a21
A
...
am1
a12
a22
...
sunt 2
...a1n
... a2 n
... ...
...amn
precum şi costul unei unităţi de producţie de fiecare tip
c1 , c2 , ..., cn
Se cere organizarea producţiei în aşa fel încât
firma A a fost asigurată cu maxim
profit.

24.

Sarcina este de a găsi
variabile nenegative
x1 , x2 , ..., xn ,
sub care consumul de resurse nu este
depășește numărul specificat și
costul tuturor produselor va ajunge
maxim.

25.

În formă matematică, problema
se scrie sub forma urmatoare:
F c1 x1 c2 x2 ... c j x j ... cn xn max
in conditii
a11 x1 a12 x2 ... a1 j x j ... a1n xn b1 ,
a21 x2 a22 x2 ... a2 j x j ... a2 n xn b2 ,
.
...............................................................,
a x a x ... a x ... a x b
mj j
mn n
m
m1 1 m 2 2
x j 0, j 1, n.

26.

Din aceeași sursă de date, poate fi
a formulat o altă sarcină.
Să presupunem că compania B decide să cumpere
toate resursele disponibile întreprinderii A.B
În acest caz, întreprinderea B trebuie să stabilească
preturi optime pentru aceste resurse, pe baza
urmatoarele conditii:
costul total al resurselor pentru întreprinderea B
ar trebui să fie minimă;
pentru fiecare tip de resursă, întreprinderea A are nevoie
plătiți cel puțin suma
întreprinderea poate primi în timpul procesării
acest tip de resursă produse terminate.

27.

Dacă este notat cu y1 , y2 , ..., yn
prețurile la care întreprinderea B
cumpără resurse de la întreprinderea A, atunci
Sarcina este de a găsi
astfel de valori ale variabilelor y1 , y2 , ..., yn ,
la care costul resurselor,
cheltuită pe unitate de orice fel
produse nu mai puțin decât profitul (prețurile)
pentru această unitate de producție și totalul
costul resurselor ajunge
minim

28.

adică care ar trebui să fie estimarea unității
fiecare dintre resursele y1 , y2 , ..., yn ,
astfel încât pentru volume date
resursele disponibile bi , date
costă c j (j 1, n) unități
produse si rate de cheltuieli aij
minimizați estimarea totală a costurilor
pentru toate produsele.

29. Mat. model cu dublă problemă

În formă matematică, problema
se scrie ca:
*
F b1 y1 b2 y2 ... bm ym min
sub restricții
a11 y1 a21 y2 ... am1 ym c1 ,
a da a ... a y c ,
m2 m
2
12 1 22 2
..................................................
a da a ... a y c ,
mn m
n
1n 1 2 n 2
yi 0, i 1, 2,..., m.

30. Sensul economic al variabilelor problemei duale

Variabilele yi ale problemei duale în literatură
poate avea denumiri diferite: contabilitate, implicit,
evaluări în umbră, determinate obiectiv,
evaluări duale sau „preţuri” resurselor.
Aceste două sarcini formează o pereche reciprocă
sarcini duble, dintre care oricare poate
fi considerat original. O singura solutie
sarcina oferă planul optim de producție
produse, iar soluția celuilalt este cea optimă
sistem de evaluare a materiilor prime utilizate pentru
producerea acestui produs.

31.

Probleme duale de liniare
se numește programare
simetrice dacă satisfac
urmatoarele proprietati:
numărul de variabile în problema duală
este egal cu numărul de constrângeri din problema inițială și
numărul de constrângeri duble ale problemei
este egal cu numărul este egal cu numărul de variabile din
original;
intr-o problema se cauta maximul tinta
funcții, în celălalt - un minim;
coeficienți pentru variabilele din țintă
funcțiile unei sarcini sunt gratuite
membri ai sistemului de constrângeri ai unei alte sarcini;

32.

în fiecare sarcină, sistemul de restricții este specificat în
sub forma inegalităţilor, mai mult, în problema găsirii
maxim, toate inegalitățile de forma „≤”, iar în problema pe
găsirea minimului, toate inegalitățile de forma „≥”;
matricea coeficientului de constrângere
unul se obține din celălalt prin transpunere;
fiecărei constrângeri a unei sarcini îi corespunde
variabilă a unei alte sarcini, număr variabil
se potrivește cu numărul de restricție;
condiţii pentru non-negativitatea variabilelor
salvat în ambele sarcini;

33. Rezolvarea problemelor duale simetrice

Prima teoremă a dualității.
Dacă una dintre sarcinile duale
are o soluție optimă, atunci
solutia optima are alta
sarcină, în timp ce valorile țintei
funcțiile sarcinii sunt egale.
Dacă funcţia obiectivă a unuia dintre
sarcinile nu sunt limitate, apoi o altă sarcină
nici o solutie deloc

34. Conținutul economic al primei teoreme a dualității

Dacă problema determinării planului optim,
care maximizează producția este solubil, atunci
problema determinării estimărilor de resurse este de asemenea rezolvabilă.
Mai mult, prețul produsului obținut ca urmare
implementarea planului optim, coincide cu
estimarea resurselor totale.
Coincidența valorilor funcției obiective pentru
soluții corespunzătoare ale unei perechi de probleme duale
suficient pentru ca aceste decizii să fie
optim.
Rezolvând LLP prin metoda simplex, vom simultan
Rezolvăm atât problemele originale, cât și cele duale.

35. Metoda de rezolvare simultană a unei perechi de probleme duale

Problemă inițială: Problemă dublă:
F c1x1 c2 x2 ... c j x j ... F * b1 y1 b2 y2 ...
cn xn max
a11 x1 a12 x2 ... a1n xn xn 1 b1 ,
a21 x1 a22 x2 ... a2 n xn xn 2 b2 ,
..........................................................
a x a x ... a x x b ,
mn n
n m
m
m1 1 m 2 2
x j 0, j 1, 2,..., n m.
bm ym min,
a11 y1 a21 y2 ... am1 ym ym 1 c1 ,
a da a ... a a y c ,
m2 m
m2
2
12 1 22 2
.............................................................
a da a ... a a y c ,
mn m
m n
n
1n 1 2 n 2
yi 0, i 1, 2,..., m n.

36.

Numărul de variabile din sarcini este același
și este egal cu m + n. În problema inițială
variabilele de bază sunt

variabile xn 1 , xn 2 , ..., xn m
,
iar în problema duală
auxiliar nenegativ
variabile yn 1 , yn 2 , ..., yn m .
Variabilele de bază ale unei sarcini
corespund variabilelor libere
altă sarcină și invers.

37.

38.

La rezolvarea LLP prin metoda simplex tabulară, soluția problemei duale
cuprinse în ultimul rând al tabelului.
Acesta este j.
Mai mult, principalele variabile ale dualului

suplimentare relevante
variabilele problemei inițiale și
variabile suplimentare duale
sarcinile sunt cuprinse în coloane,
major relevant
(original) variabile ale originalului
sarcini.

39. Exemplu.

Să formulăm un model al problemei duale
la problema din exemplul 2 (începutul prelegerii):
Găsiți maximul unei funcții

40.

41.

Variabilele sarcinii originale x1 , x2 , x3 sunt numărul produsele A, Bși C. Să introducem
variabile ale problemei duale y1 , y2 , y3
Găsiți minimul unei funcții
F * 360 y1 192 y2 180 y3 min
sub restricții
18 y1 6 y2 5 y3 9,
15 y1 4 y2 3 y3 10,
12 și 8 și 3 și 16,
2
3
1
y1, y2, y3 0.

42. Luați în considerare ultimul tabel al problemei inițiale

43.

Valoarea lui y1 din ultimul rând al coloanei P4,
acestea. y1 2 ;
9y5
valoarea 2 3 în ultimul rând al coloanei P5,
valoarea y3 0 în ultimul rând al coloanei P6 .
Valorile rămase se găsesc în coloanele 1,2,3.
2 5
Y (; ;0;5;0;0)
9 3
în care
2
5
F 360 192 180 0 0 5 0 0 0 0 400
9
3
*
Acesta este costul minim pentru toate produsele.
2/9 și 5/3 sunt prețurile umbră ale materiilor prime de 1 și 2
tipuri, respectiv.

x 1

+x2

+x 3

x 1

+x2

+x 3

x 1

+x2

+x 3

≤ = ≥

Avertizare

Ștergeți toate celulele?

Închide Clear

Instrucțiuni de introducere a datelor. Numerele sunt introduse ca numere întregi (exemple: 487, 5, -7623 etc.), numere zecimale (de ex. 67, 102,54 etc.) sau fracții. Fracția trebuie scrisă sub forma a/b, unde a și b (b>0) sunt numere întregi sau numere zecimale. Exemplele 45/5, 6.6/76.4, -7/6.7 etc.

Metoda simplex

Exemple de rezolvare a metodei simplex LLP

Exemplul 1. Rezolvați următoarea problemă de programare liniară:

Partea dreaptă a constrângerilor sistemului de ecuații are forma:

Să scriem linia de bază curentă:

Această linie de bază nu este optimă deoarece există elemente negative în ultimul rând. Cel mai mare element negativ modulo (-3), prin urmare, baza include un vector X la . min(40:6, 28:2)=20/3 corespunde rândului 1. Vectorul părăsește baza X 3 . Să facem o excepție gaussiană pentru coloană X 2 , având în vedere că elementul principal corespunde rândului 1. Setați toate elementele acestei coloane la zero, cu excepția elementului principal. Pentru a face acest lucru, adăugați rândurile rândului 2, 3, 4 cu rândul 1 înmulțit cu -1/3, 1/6, respectiv 1/2. Apoi, împărțim șirul cu elementul conducător la elementul principal.

Acest plan de bază nu este optim, deoarece ultimul rând conține un element negativ (-3), prin urmare, baza include vectorul X 1 . Determinăm care vector părăsește baza. Pentru asta calculăm la . min(44/3:11/3, 62/3:5/3)=4 corespunde rândului 2. Vectorul părăsește baza X 4 . Să facem o excepție gaussiană pentru coloană X 1 , având în vedere că elementul principal corespunde rândului 2. Setați toate elementele acestei coloane la zero, cu excepția elementului principal. Pentru a face acest lucru, adăugați liniile liniei 1, 3, 4 cu linia 2, înmulțite cu 1/11, -5/11, respectiv 9/11. Apoi, împărțim șirul cu elementul conducător la elementul principal.

Tabelul simplex va arăta astfel:

Linia de bază actuală este optimă, deoarece în rândurile 4 sub variabile fără elemente negative.

Soluția poate fi scrisă astfel: .

Valoarea funcției obiectiv la un punct dat: F(X)=.

Exemplul 2. Găsiți maximul unei funcții

Soluţie.

Vectori de bază X 4 , X 3, deci toate elementele din coloane X 4 , X 3 sub linia orizontală ar trebui să fie zero.

Scoateți la zero toate elementele unei coloane X 4, cu excepția elementului conducător. Pentru a face acest lucru, adăugați rândul 3 cu rândul 1 înmulțit cu 4. Setați toate elementele coloanei la zero X 3, cu excepția elementului conducător. Pentru a face acest lucru, adăugați rândul 3 cu rândul 2 înmulțit cu 1.

Tabelul simplex va lua forma:

Acest plan de referință nu este optim, deoarece ultimul rând conține un element negativ (-11), prin urmare, baza include vectorul X 2. Determinăm care vector părăsește baza. Pentru asta calculăm la . Prin urmare, funcția obiectiv este nelimitată de sus. Acestea. problema de programare liniară este de nerezolvat.

Exemple de rezolvare a LLP prin metoda bazei artificiale

Exemplul 1. Găsiți maximul unei funcții

Soluție Deoarece numărul de vectori de bază ar trebui să fie 3, adăugăm o variabilă artificială și adăugăm această variabilă înmulțită cu −M la funcția obiectiv, unde M este un număr foarte mare:

Matricea de coeficienți a sistemului de ecuații are forma:

Vectori de bază, prin urmare, toate elementele din coloanele de sub linia orizontală trebuie să fie zero.

Scoateți la zero toate elementele coloanei, cu excepția elementului principal. Pentru a face acest lucru, adăugați rândul 5 cu rândul 3 înmulțit cu -1.

Tabelul simplex va lua forma:

Această linie de bază nu este optimă deoarece există elemente negative în ultimul rând. Cel mai mare element negativ modulo (-5), prin urmare, vectorul intră în bază.Determinați care vector părăsește baza. Pentru asta calculăm la corespunde rândului 3. Un vector părăsește baza Să facem o excepție gaussiană pentru coloană, având în vedere că elementul de conducere corespunde rândului 3. Setați toate elementele acestei coloane la zero, cu excepția elementului principal. Pentru a face acest lucru, adăugați liniile liniei 5 cu linia 3, înmulțite cu 1. Apoi, împărțim linia cu elementul principal la elementul principal.

Tabelul simplex va arăta astfel:

Această linie de bază nu este optimă deoarece există elemente negative în ultimul rând. Cel mai mare element negativ modulo (-3), prin urmare, vectorul intră în bază.Determinați care vector părăsește baza. Pentru asta calculăm la corespunde liniei 1. Vectorul părăsește baza X 2. Să facem o excepție gaussiană pentru coloană X 1 , având în vedere că elementul principal corespunde rândului 1. Setați toate elementele acestei coloane la zero, cu excepția elementului principal. Pentru a face acest lucru, adăugați liniile liniei 2, 3, 4 cu linia 1 înmulțită cu 3/2, -1/10, respectiv 3/2. Apoi, împărțim șirul cu elementul conducător la elementul principal.

Tabelul simplex va arăta astfel:

Această linie de bază nu este optimă deoarece există elemente negative în ultimul rând. Cel mai mare element negativ modulo (-13/2), prin urmare, baza include vectorul X 3 . Determinăm care vector părăsește baza. Pentru asta calculăm la corespunde liniei 3. Vectorul părăsește baza X 5 . Să facem o excepție gaussiană pentru coloană X 3 , având în vedere că elementul principal corespunde rândului 3. Setați toate elementele acestei coloane la zero, cu excepția elementului principal. Pentru a face acest lucru, adăugați liniile liniei 1, 2, 4 cu linia 3, înmulțite cu 5/3, 25/9, respectiv 65/9. Apoi, împărțim șirul cu elementul conducător la elementul principal.

Tabelul simplex va arăta astfel:

Linia de bază actuală este optimă deoarece nu există elemente negative sub variabilele din liniile 4-5.

Soluția problemei inițiale poate fi scrisă după cum urmează:

Exemplul 2. Găsiți planul optim pentru problema de programare liniară:

Matricea de coeficienți a sistemului de ecuații are forma:

Vectori de bază X 4 , X 5 , X 6, deci toate elementele din coloane X 4 , X 5 , X 6, sub linia orizontală ar trebui să fie zero.

Scoateți la zero toate elementele unei coloane X 4, cu excepția elementului conducător. Pentru a face acest lucru, adăugați rândul 4 cu rândul 1, înmulțit cu -1. Scoateți la zero toate elementele unei coloane X 5, cu excepția elementului conducător. Pentru a face acest lucru, adăugați rândul 5 cu rândul 2 înmulțit cu -1. Scoateți la zero toate elementele unei coloane X 6, cu excepția elementului conducător. Pentru a face acest lucru, adăugați rândul 5 cu rândul 3 înmulțit cu -1.

Tabelul simplex va lua forma:

În rândul 5, elementele corespunzătoare variabilelor X 1 , X 2 , X 3 , X 4 , X 5 , X 6 sunt nenegative, iar numărul de la intersecția rândului și coloanei date X 0 negativ. Atunci problema inițială nu are un plan de bază. Prin urmare, este indecidabil.

Cursul 6. Teoreme de dualitate. Estimări duale și semnificația lor.

4.3. Prima teoremă a dualității

Legătura dintre soluțiile optime ale problemelor duale se stabilește cu ajutorul teoremelor de dualitate.

Un semn suficient de optimitate.

Dacă Și
sunt soluţii admisibile ale problemelor reciproc duale pentru care egalitatea

Acea
– rezolvarea optimă a problemei inițiale eu A – dubla problema II.

Pe lângă un criteriu suficient pentru optimitatea problemelor reciproc duale, între soluțiile lor există și alte relații importante. În primul rând, apar întrebări: există întotdeauna o soluție optimă simultană pentru fiecare pereche de probleme duale; este posibil ca una dintre problemele duale să aibă o soluție și cealaltă nu. La aceste întrebări se răspunde prin următoarea teoremă.

Prima (principală) teoremă a dualității. Dacă una dintre problemele reciproc duale are o soluție optimă, atunci are și cealaltă, iar valorile optime ale funcțiilor lor liniare sunt:

sau
.

Dacă funcția liniară a uneia dintre probleme nu este limitată, atunci condițiile celeilalte probleme sunt contradictorii (problema nu are soluție).

Cometariu. Afirmația opusă celei de-a doua părți a teoremei principale a dualității nu este adevărată în cazul general, i.e. din faptul că condițiile problemei inițiale sunt contradictorii, nu rezultă că funcția liniară a problemei duale nu este mărginită.

Sensul economic al primei teoreme a dualității.

Plan de productie
și un set de prețuri (estimări) resurse
se dovedesc a fi optime dacă și numai dacă profitul (venitul) din produs se găsește la prețuri „externe” (cunoscute dinainte)
, este egal cu costul resurselor la prețuri „interne” (determinate doar din soluționarea problemei)
. Pentru toate celelalte planuri XȘi Y ambele sarcini, profitul (venitul) din produs este întotdeauna mai mic decât (sau egal cu) costul resurselor.

Semnificația economică a primei teoreme a dualității poate fi interpretată și astfel: întreprinderii nu îi pasă dacă să producă produse conform planului optim.
și obțineți profitul (venitul) maxim
sau vinde resurse la cele mai bune prețuri
și să recupereze din vânzare egal cu costul minim al resurselor
.

4.4. A doua teoremă a dualității

Să fie date două probleme reciproc duble. Dacă fiecare dintre aceste probleme este rezolvată prin metoda simplex, atunci este necesar să le reducem la o formă canonică, pentru care sistemul de constrângeri al problemei I (pe scurt notație
) trebuie introdus T variabile nenegative, dar în sistemul de constrângeri al problemei II (
) – n variabile nenegative, unde
este numărul inegalității în care este introdusă variabila suplimentară
.

Sistemele de constrângeri pentru fiecare dintre problemele reciproc duale vor lua forma:

Să stabilim o corespondență între variabilele inițiale ale uneia dintre problemele duale și variabilele suplimentare ale celeilalte probleme (tabel).

Teorema. Componentele pozitive (diferite de zero) ale soluției optime a uneia dintre problemele reciproc duale corespund componentelor zero ale soluției optime a celeilalte probleme, adică. pentru orice
u
: Dacă
, Acea
; Dacă
, Acea
, și în mod similar,

Dacă
, Acea
; Dacă
, Acea
.

Din această teoremă rezultă o concluzie importantă că corespondența introdusă între variabilele problemelor reciproc duale la atingerea optimului (adică, la ultimul pas de rezolvare a fiecărei probleme prin metoda simplex) reprezintă o corespondență între principal(de regulă, nu egal cu zero) variabile ale uneia dintre problemele duale și non-core(egale cu zero) variabile ale unei alte probleme atunci când formează soluții de bază admisibile.

A doua teoremă a dualității. Componentele soluției optime a problemei duale sunt egale cu valorile absolute ale coeficienților pentru variabilele corespunzătoare funcție liniară problema inițială exprimată în termeni de variabile nebazice ale soluției sale optime.

Cometariu. Dacă într-una dintre problemele reciproc duale este încălcată unicitatea soluției optime, atunci soluția optimă a problemei duale este degenerată. Acest lucru se datorează faptului că, dacă este încălcată unicitatea soluției optime a problemei inițiale, cel puțin una dintre variabilele principale lipsește în exprimarea funcției liniare a soluției sale optime în ceea ce privește variabilele nebazice.

4.5. Aprecieri determinate obiectiv și semnificația lor

Componentele soluției optime a problemei duale se numesc estimări optime (duale) ale problemei inițiale. Le-a numit academicianul L.V. Kantorovich conditionat obiectiv estimări (în literatură se mai numesc și venit ascuns) .

Variabile suplimentare ale problemei inițiale I, reprezentând diferența dintre stocuri resurse
iar consumul lor, expres resursele rămase , și variabile suplimentare ale problemei duale II, reprezentând diferența dintre costurile resurselor pentru producerea unei unități de producție din acestea și prețuri produse
, expres cost în exces față de preț.

Astfel, estimări ale resurselor determinate obiectiv determină gradul de deficit al resurselor: conform planului optim de producție, resursele limitate (adică, utilizate pe deplin) primesc estimări non-zero, iar nerare - estimări zero. Valoare este o estimare -a resursă. Cu cât valoarea ratingului este mai mare , cu atât este mai mare deficitul de resurse. Pentru o resursă rară
.

Deci, numai tipurile de produse rentabile, neprofitabile pot intra în planul optim de producție (deși criteriul de rentabilitate aici este deosebit: prețul unui produs nu depășește costurile resurselor consumate la fabricarea sa, ci este exact egal lor).

A treia teoremă a dualității . Componentele soluției optime a problemei duale sunt egale cu valorile derivatelor parțiale ale funcției liniare
conform argumentelor corespondente, i.e.

Estimările de resurse determinate obiectiv arată câte unități monetare se va modifica profitul (venitul) maxim din vânzarea produselor atunci când stocul resursei corespunzătoare se va modifica cu o unitate.

Estimările duale pot servi ca instrument de analiză și luare a deciziilor corecte într-o industrie în continuă schimbare. Deci, de exemplu, cu ajutorul estimărilor de resurse determinate obiectiv, este posibil să se compare costurile condiționate optime și rezultatele producției.

Estimările determinate obiectiv ale resurselor fac posibilă aprecierea efectului nu al oricăror, ci doar al modificărilor relativ mici ale resurselor. Cu schimbări bruște, estimările în sine pot deveni diferite, ceea ce va duce la imposibilitatea utilizării lor pentru analiza eficienței producției. În funcție de rapoartele estimărilor determinate obiectiv, se pot determina normele calculate de substituire a resurselor, în baza cărora înlocuirile în curs în cadrul stabilității estimărilor duale nu afectează eficiența planului optim. Concluzie. Scorurile duble sunt:

Un indicator al deficitului de resurse și produse.

Un indicator al influenței restricțiilor asupra valorii funcției obiectiv.

Un indicator al eficienței producției anumitor tipuri de produse din punctul de vedere al criteriului optimității.

Un instrument pentru compararea costurilor contingente totale și a rezultatelor.

Fiecare sarcină LP corespunde unei alte sarcini, numită dualîn raport cu originalul.

2.9.1 Interpretare economică

Anterior a fost formulată problema planificării producției. Luați în considerare acum problema cumpărării resurselor. Lasă o organizație să decidă să achiziționeze resurse și este necesar să se stabilească prețurile optime pentru aceste resurse. Este evident că organizația de achiziții este interesată de faptul că costurile tuturor resurselor în cantități sunt minime, adică .

Pe de altă parte, o întreprindere care vinde resurse este interesată de faptul că veniturile nu sunt mai mici decât suma pe care o poate primi întreprinderea la procesarea resurselor în produse finite. Producția unei unități de producție de tip consumă unități de resurse la un preț, unități de resurse la un preț, unități de resurse la un preț, unități de resurse la un preț. Prin urmare, pentru a satisface cerințele vânzătorului, costul resurselor consumate în fabricarea unei unități de producție nu trebuie să fie mai mic decât prețul acesteia, adică

Raportul dintre problemele LP directe și duale este prezentat în tabel:

Problemă directă

Problemă dublă

Găsiți un astfel de plan producție, la care profitul (venitul) din vânzarea produselor va fi maxim, cu condiția ca consumul de resurse pentru fiecare tip de produs să nu depășească stocurile disponibile.

Găsiți un astfel de preț stabilit pe resurse, la care costul total al resurselor va fi minim, cu condiția ca costul resurselor în producția fiecărui tip de produs să nu fie mai mic decât profitul (venitul) din vânzarea acestui produs.

Prețurile resurselor din literatura economică au primit diverse denumiri: contabilitate, implicit, umbrită. Sensul acestor nume este că acestea sunt prețuri condiționate, „false”. Spre deosebire de prețurile „externe” la produse, care sunt cunoscute, de regulă, înainte de începerea producției, prețurile resurselor sunt interne, deoarece nu sunt stabilite din exterior, ci sunt determinate direct ca urmare a rezolvării problemei. .

2.9.2 Probleme duale și proprietățile lor

Luați în considerare problemele duble în formă generală.

Sarcina directă:

Sarcină dublă:

Problema duală cu privire la linia dreaptă este compusă după cum urmează:

1. Funcția obiectivă a problemei inițiale este setată la maxim, iar în problema duală, la minim.

2. Matricele de coeficienți ale problemelor directe și duale se obțin una de la alta prin înlocuirea rândurilor cu coloane, iar coloanelor cu rânduri (operație de transpunere):

3. Numărul de variabile din problema duală este egal cu numărul de constrângeri din problema originală (și invers).

4. Coeficienții necunoscutelor din funcția obiectivă a problemei duale sunt termenii liberi din constrângerile problemei inițiale, iar părțile din dreapta din constrângerile problemei duale sunt coeficienții necunoscutelor din funcția obiectiv a problemei inițiale.

Sarcina 7. Scrieți o problemă care este duală cu următoarea problemă:

Deoarece problema maximă directă, reducem toate inegalitățile sistemului de constrângeri la forma „£” (ambele părți ale primei și celei de-a patra inegalități sunt înmulțite cu -1):

Să compunem matricea extinsă a sistemului:

Matrice transpusă:

Formulăm o problemă dublă:

2.9.3 Teoreme de dualitate

Mai întâi formulăm inegalitatea principală a teoriei dualității.

Să fie o pereche de probleme duble. Pentru orice soluții fezabile Și probleme directe și duale, inegalitatea

sau sub formă de coordonate

Acum formulăm semn suficient de optimitate.

Dacă și sunt soluții admisibile la problemele primale și, respectiv, duale, pentru care egalitatea

atunci este soluția optimă a problemei directe și este soluția optimă a problemei duale.

Legătura dintre soluțiile optime ale problemelor duale se stabilește cu ajutorul teoremelor de dualitate.

Prima teoremă a dualității.Dacă una dintre problemele reciproc duale are o soluție optimă,apoi o are altul, iar valorile optime ale funcțiilor lor obiective sunt egale cu:

Sau .

Dacă funcţia obiectivă a uneia dintre sarcini nu atinge optimul, atunci condiţiile celeilalte probleme sunt contradictorii.

Sensul economic al primei teoreme a dualității constă din următoarele.

Planul de producție și setul de prețuri la resurse sunt optime dacă și numai dacă profitul (venitul) din produse găsite la prețuri „externe” (cunoscute dinainte) este egal cu costul resurselor la „intern” (determinat doar din soluție). a problemei) preţurile.

Legătura dintre problemele duale se manifestă nu numai în egalitatea valorilor optime ale funcțiilor lor obiective (prima teoremă a dualității).

Să fie date probleme duble.

Drept:

Dual:

Dacă fiecare dintre aceste probleme este rezolvată prin metoda simplex, atunci este necesar să le reduceți la o formă canonică, pentru care sistemul de constrângeri

problema directă ar trebui să introducă variabile non-negative, iar în sistemul de restricții

problema duală ar trebui să introducă variabile nenegative, unde este numărul inegalității în care este introdusă variabila suplimentară. Sistemele de constrângeri pentru fiecare dintre sarcini vor lua forma, respectiv:

sarcina directa -

sarcina dubla -

Corespondența dintre variabilele problemelor duale este ilustrată de tabelul:

Variabile directe ale sarcinii

Iniţială

Adiţional

Iniţială

Variabile cu sarcini duble

Teorema 16. pozitiv(diferit de zero) componentele soluției optime a uneia dintre problemele reciproc duale corespund componentelor zero ale soluției optime a celeilalte probleme, adică pentru orice și: Dacă, Acea; Dacă, Acea; si la fel, Dacă, Acea; Dacă, Acea.

A doua teoremă a dualității. Pentru ca soluțiile fezabile, perechile de probleme duale să fie optime, este necesar și suficient ca următoarele condiții să fie îndeplinite:

Consecinţă. Dacă în soluția optimă a uneia dintre problemele duale orice variabilă nu este egală cu zero, atunci restrângerea problemei duale care îi corespunde pe soluția optimă este satisfăcută ca egalitate, și invers, dacă pe soluția optimă a uneia. dintre problemele duale orice restricție este satisfăcută ca o inegalitate strictă, atunci variabila corespunzătoare în soluția optimă a problemei duale este egală cu zero.

Dacă într-una dintre problemele reciproc duale este încălcată unicitatea soluției optime (geometric, aceasta înseamnă că se ajunge pe marginea/fața poligonului/poliedrului), atunci soluția optimă a problemei duale este degenerată.

Sarcina 8. După rezolvarea problemei prin metoda simplex

primim: , .

Să trecem la inegalități precum „”:

Sarcină dublă:

Corespondența dintre variabile (vezi tabelul de mai sus):

La soluția optimă a problemei directe, avem:

Deoarece constrângerile a treia și a patra sunt valabile ca inegalități stricte, atunci, conform corolarului, , , și ambele constrângeri ale problemei duale sunt îndeplinite ca egalități:

Înlocuind aici și rezolvând sistemul, soluția optimă a problemei duale .

2.9.4 Evaluări determinate obiectiv

Se numesc componentele soluției optime a problemei duale optim (dual) estimări sarcină directă. Kantorovich i-a sunat evaluări obiective.

Depășirea costului resurselor

peste prețul de vânzare

Estimări de resurse condiționate obiectiv

(prețuri condiționate la resurse)

Componentele soluției optime a problemei duale

În tabel, valorile variabilelor suplimentare problema directă reprezintă diferența dintre stocuri resurse iar consumul lor, adică exprimă resursele rămase, iar valorile variabilelor suplimentare ale problemei duale reprezintă diferența dintre costurile resurselor pentru producerea unei unități de producție din acestea și prețurile produselor , adică ele exprimă cost în exces față de preț.

Resurse utilizat pe deplin conform planului optim ( ), iar estimările obiectiv determinate ale acestor resurse sunt nenule (și în acest caz, conform planului optim, să producă produse nu ar fi trebuit.

Astfel, numai tipurile de produse rentabile, neprofitabile pot intra în planul optim de producție (deși criteriul de rentabilitate aici este deosebit: prețul unui produs nu depășește costurile resurselor consumate la fabricarea lui, ci este exact egal). lor).

Întrebări de control

1. Formulați conceptul de problemă reciproc duală.

2. Oferiți o interpretare economică a unei perechi de probleme reciproc duale.

3. Formulați proprietățile unei perechi de probleme reciproc duale.

4. Formulați prima teoremă a dualității și conținutul ei economic.

5. Formulați a doua teoremă a dualității și conținutul ei economic.

5. Definiți conceptul de evaluări determinate obiectiv.