Metoda simplex directă. Un exemplu de rezolvare a unei probleme. Metoda simplex pentru rezolvarea ZLP

Este necesar să se rezolve o problemă de programare liniară.

Funcția obiectivă:

2x 1 +5x 2 +3x 3 +8x 4 →min

Conditii limitative:

3x 1 +6x 2 -4x 3 +x 4 ≤12
4x 1 -13x 2 +10x 3 +5x 4 ≥6
3x 1 +7x 2 +x 3 ≥1

Să aducem sistemul de restricții în formă canonică pentru aceasta este necesar să trecem de la inegalități la egalități, cu adăugarea de variabile suplimentare.

Deoarece problema noastră este o problemă de minimizare, trebuie să o transformăm într-o problemă de căutare maximă. Pentru a face acest lucru, schimbăm semnele coeficienților funcției obiectiv cu cele opuse. Scriem elementele primei inegalități neschimbate, adăugând o variabilă suplimentară x 5 și schimbând semnul „≤” în „=". Deoarece a doua și a treia inegalități au semnele „≥”, este necesar să se schimbe semnele coeficienților lor cu cele opuse și să se introducă variabile suplimentare x 6 și, respectiv, x 7 în ele. Ca rezultat, obținem o problemă echivalentă:

3x 1 +6x 2 -4x 3 +x 4 +x 5 =12
-4x 1 +13x 2 -10x 3 -5x 4 +x 6 =-6
-3x 1 -7x 2 -x 3 +x 7 =-1

Se trece la formarea tabelului simplex inițial. Coeficienții funcției obiectiv cu semnul opus sunt introduși în rândul F al tabelului.

					Membru gratuit
F
X5
X6
X7

În tabelul pe care l-am compilat există elemente negative în coloana termenilor liberi, printre ele găsim maximul în modul - acesta este elementul: -6, stabilește rândul de început - X6. În această linie găsim și elementul negativ maxim în modul: -10 se află în coloana X3, care va fi coloana principală. Variabila din rândul principal este exclusă din bază, iar variabila corespunzătoare coloanei principale este inclusă în bază. Să recalculăm tabelul simplex:

	X1	X2	X6	X4	Membru gratuit
F	0.8	8.9	0.3	6.5	-1.8
X5	4.6	0.8	-0.4	3	14.4
X3	0.4	-1.3	-0.1	0.5	0.6
X7	-2.6	-8.3	-0.1	0.5	-0.4

În tabelul pe care l-am compilat există elemente negative în coloana termenilor liberi, printre ele găsim maximul în modul - acesta este elementul: -0,4, stabilește rândul de început - X7. În această linie găsim și elementul negativ maxim în modul: -8,3 este situat în coloana X2, care va fi coloana de conducere. Variabila din rândul principal este exclusă din bază, iar variabila corespunzătoare coloanei principale este inclusă în bază. Să recalculăm tabelul simplex:

	X1	X7	X6	X4	Membru gratuit
F	-1.988	1.072	0.193	7.036	-2.229
X5	4.349	0.096	-0.41	3.048	14.361
X3	0.807	-0.157	-0.084	0.422	0.663
X2	0.313	-0.12	0.012	-0.06	0.048

Deoarece nu există elemente negative în coloana termenilor liberi, s-a găsit o soluție admisibilă Rândul F conține elemente negative, ceea ce înseamnă că soluția rezultată nu este optimă. Să definim coloana principală. Pentru a face acest lucru, vom găsi în rândul F elementul negativ cu modulul maxim - acesta este -1,988 Rândul principal va fi cel pentru care raportul dintre termenul liber și elementul corespunzător al coloanei principale este minim. Rândul principal este X2 și elementul principal este: 0,313.

	X2	X7	X6	X4	Membru gratuit
F	6.351	0.31	0.269	6.655	-1.924
X5	-13.895	1.763	-0.577	3.882	13.694
X3	-2.578	0.152	-0.115	0.577	0.539
X1	3.195	-0.383	0.038	-0.192	0.153

Deoarece nu există elemente negative în șirul F, s-a găsit soluția optimă. Întrucât sarcina inițială a fost de a găsi minimul, soluția optimă va fi termenul liber al șirului F, luat cu semnul opus. F=1,924
cu valori variabile egale: x 3 = 0,539, x 1 = 0,153. Variabilele x 2 și x 4 nu sunt incluse în bază, deci x 2 =0 x 4 =0.

Metoda simplex este un proces iterativ de rezolvare direcționată a unui sistem de ecuații în pași, care începe cu o soluție de referință și, în căutarea celei mai bune opțiuni, se deplasează de-a lungul punctelor de colț ale zonei de soluție fezabilă, îmbunătățind valoarea funcției obiectiv până la funcția obiectiv atinge valoarea optimă.

Scopul serviciului. Serviciul este conceput pentru rezolvarea online a problemelor de programare liniară (LPP) folosind metoda simplex în următoarele forme de notație:

• sub forma unui tabel simplex (metoda de transformare Jordan); formular de înregistrare de bază;
• metoda simplex modificată; sub formă de coloană; în formă de linie.

Instrucţiuni. Selectați numărul de variabile și numărul de rânduri (număr de constrângeri). Soluția rezultată este salvată într-un fișier Word și Excel.

Numărul de variabile 2 3 4 5 6 7 8 9 10
Număr de rânduri (număr de restricții) 1 2 3 4 5 6 7 8 9 10

În acest caz, nu țineți cont de restricții precum x i ≥ 0. Dacă nu există restricții în sarcină pentru unele x i, atunci ZLP trebuie convertit în KZLP sau utilizați acest serviciu. Soluția determină automat utilizarea metoda M(metoda simplex pe bază artificială) și metoda simplex în două etape.

Următoarele sunt, de asemenea, utilizate cu acest calculator:
Metodă grafică de rezolvare a ZLP
Rezolvarea problemei transportului
Rezolvarea unui joc de matrice
Folosind serviciul online, puteți determina prețul unui joc matrice (limitele inferioare și superioare), puteți verifica prezența unui punct de șa, puteți găsi o soluție la o strategie mixtă folosind următoarele metode: minimax, metoda simplex, grafică (geometrică). ), metoda lui Brown.
Extremul unei funcții a două variabile
Probleme de programare dinamică
Distribuiți 5 loturi omogene de mărfuri între trei piețe astfel încât să obțineți venituri maxime din vânzarea acestora. Veniturile din vânzări pe fiecare piață G(X) depind de numărul de loturi vândute de produs X și sunt prezentate în tabel.

Volumul produsului X (în loturi)	Venitul G(X)
	1	2	3
0	0	0	0
1	28	30	32
2	41	42	45
3	50	55	48
4	62	64	60
5	76	76	72

Algoritmul metodei simplex include următorii pași:

1. Întocmirea primului plan de bază. Trecerea la forma canonică a problemei de programare liniară prin introducerea unor variabile de echilibru suplimentare nenegative.
2. Verificarea optimității planului. Dacă există cel puțin un coeficient de linie index mai mic decât zero, atunci planul nu este optim și trebuie îmbunătățit.
3. Determinarea coloanei și rândului de început. Din coeficienții negativi ai liniei indexului, este selectat cel mai mare în valoare absolută. Apoi, elementele coloanei membre libere a tabelului simplex sunt împărțite în elemente de același semn al coloanei principale.
4. Construirea unui nou plan de referință. Tranziția la un nou plan se realizează ca urmare a recalculării tabelului simplex folosind metoda Jordan-Gauss.

Dacă este necesar să găsim extremul funcției obiectiv, atunci vorbim despre găsirea valorii minime (F(x) → min, vezi exemplul unei soluții pentru minimizarea unei funcții) și a valorii maxime ((F(x) ) → max, vezi exemplul unei soluții pentru maximizarea unei funcții)

O soluție extremă se realizează la limita regiunii soluțiilor fezabile la unul dintre vârfurile punctelor de colț ale poligonului sau pe segmentul dintre două puncte de colț adiacente.

Teorema fundamentală a programării liniare. Dacă funcția obiectiv ZLP atinge o valoare extremă la un moment dat în regiunea soluțiilor fezabile, atunci ea ia această valoare în punctul de colț. Dacă funcția obiectiv ZLP atinge o valoare extremă la mai mult de un punct de colț, atunci ia aceeași valoare la oricare dintre combinațiile liniare convexe ale acestor puncte.

Esența metodei simplex. Deplasarea către punctul optim se realizează prin trecerea dintr-un punct de colț în cel vecin, ceea ce aduce mai aproape și mai rapid de X opt. O astfel de schemă de enumerare a punctelor, numită metoda simplex, sugerat de R. Danzig.
Punctele de colț sunt caracterizate de m variabile de bază, astfel încât tranziția de la un punct de colț la unul adiacent poate fi realizată prin schimbarea unei singure variabile de bază din bază la o variabilă dintr-o non-bază.
Implementarea metodei simplex, datorită diverselor caracteristici și formulări ale problemelor LP, are diverse modificări.

Construcția tabelelor simplex continuă până la obținerea soluției optime. Cum puteți utiliza un tabel simplex pentru a determina că soluția la o problemă de programare liniară este optimă?
Dacă ultima linie (valorile funcției obiective) nu conține elemente negative, va găsi planul optim.

Observație 1. Dacă una dintre variabilele de bază este egală cu zero, atunci punctul extrem corespunzător unei astfel de soluții de bază este degenerat. Degenerarea apare atunci când există ambiguitate în alegerea liniei de ghidare. Este posibil să nu observați deloc degenerarea problemei dacă alegeți o altă linie ca ghid. În caz de ambiguitate, rândul cu cel mai mic indice trebuie selectat pentru a evita bucla.

Observația 2. Fie într-un punct extrem ca toate diferențele simplex să fie nenegative D k ³ 0 (k = 1..n+m), adică. se obține o soluție optimă și există A k - un vector nebază pentru care D k = 0. Atunci maximul se atinge cel puțin în două puncte, adică. există o alternativă optimă. Dacă introducem această variabilă x k în bază, valoarea funcției obiectiv nu se va modifica.

Observația 3. Soluția problemei duale este în ultimul tabel simplex. Ultimele m componente ale vectorului diferențelor simplex (în coloanele variabilelor de echilibru) sunt soluția optimă a problemei duale. Valorile funcțiilor obiective ale problemelor directe și duale în punctele optime coincid.

Observația 4. La rezolvarea problemei de minimizare, se introduce în bază vectorul cu cea mai mare diferență pozitivă simplex. În continuare, se aplică același algoritm ca și pentru problema de maximizare.

Dacă este specificată condiția „Este necesar ca materiile prime de tip III să fie complet consumate”, atunci condiția corespunzătoare este o egalitate.

11.4. METODA DUAL SIMPLEX

Din rezultatele paragrafelor anterioare rezultă că pentru a obține o soluție la problema inițială, se poate trece la cea duală și, folosind estimări ale planului său optim, se poate determina soluția optimă a problemei inițiale.

Trecerea la problema duală nu este necesară, deoarece dacă luăm în considerare primul tabel simplex cu o bază suplimentară unitară, este ușor de observat că problema inițială este scrisă în coloane, iar cea duală este scrisă în rânduri.

După cum sa arătat, atunci când rezolvați o problemă directă la orice iterație, diferența, adică magnitudinea -coeficientul variabilei, este egală cu diferența dintre partea dreaptă și stângă a constrângerii corespunzătoare problemei duale. Dacă, la rezolvarea unei probleme directe cu o funcție obiectiv maximizată, iterația nu conduce la o soluție optimă, atunci cel puțin pentru o variabilă și numai la optim pentru toate diferenta.

Având în vedere această condiție ținând cont de dualitate, putem scrie

.

Astfel, dacă, Asta . Aceasta înseamnă că atunci când soluția problemei directe este suboptimă, soluția problemei duale nu este fezabilă. Pe cealaltă parte la . Rezultă că soluția optimă a problemei directe corespunde unei soluții admisibile a problemei duale.

Acest lucru a făcut posibilă dezvoltarea unei noi metode de rezolvare a problemelor de programare liniară, care produce mai întâi o soluție inacceptabilă, dar „mai bună decât optimă” (în metoda simplex obișnuită, se găsește mai întâi acceptabil, Dar suboptimal soluţie). Noua metodă, numită metoda dual simplex, asigură îndeplinirea condiţiilor pentru optimitatea soluţiei şi „aproximarea” sistematică a acesteia de regiunea soluţiilor fezabile. Când soluția rezultată se dovedește a fi fezabilă, procesul iterativ de calcule se încheie, deoarece această soluție este și optimă.

Metoda dual simplex face posibilă rezolvarea problemelor de programare liniară ale căror sisteme de constrângeri, cu o bază pozitivă, conțin termeni liberi de orice semn. Această metodă vă permite să reduceți numărul de transformări ale sistemului de constrângeri, precum și dimensiunea tabelului simplex. Să luăm în considerare aplicarea metodei dual simplex folosind un exemplu.

Exemplu. Găsiți minimul unei funcții

sub restricții

.

Să trecem la forma canonică:

sub restricții

Tabelul inițial simplex are forma

De bază variabile	x 1	x 2	x 3	x 4	x 5	Soluţie
x 3 x 4 x 5	–3 –4	–1 –3				–3 –6
	–2	–1

Soluție de bază inițialăoptim, dar inacceptabil.

La fel ca metoda simplex obișnuită, metoda soluției luată în considerare se bazează pe utilizarea condițiilor de admisibilitate și optimitate.

Condiție de admisibilitate. Cea mai mare variabilă de bază negativă în valoare absolută este selectată ca variabilă exclusă (dacă există alternative, alegerea se face în mod arbitrar). Dacă toate variabilele de bază sunt nenegative, procesul de calcul se încheie, deoarece soluția rezultată este fezabilă și optimă.

Stare optimitatea. Variabila inclusă în bază este selectată dintre variabilele care nu sunt de bază, după cum urmează. Se calculează rapoartele coeficienților din stânga-ecuații la coeficienții corespunzători ai ecuației asociate cu variabila exclusă. Nu se iau în considerare rapoartele cu numitor pozitiv sau zero. În problema de minimizare, variabila de intrare trebuie să corespundă celui mai mic dintre rapoartele specificate, iar în problema de maximizare, raportul care este cel mai mic în valoare absolută (dacă există alternative, alegerea se face arbitrar). Dacă numitorii tuturor rapoartelor sunt zero sau pozitivi, problema nu are soluții fezabile.

După selectarea variabilelor incluse în bază și excluse pentru a obține următoarea soluție, se efectuează operația obișnuită de conversie a rândurilor tabelului simplex.

În acest exemplu, variabila exclusă este. Rapoartele calculate pentru determinarea noii variabile de bază sunt date în următorul tabel:

Variabile	x 1	x 2	x 3	x 4	x 5
Ecuaţie x 4 - ecuație	–2 –4	–1 –3
Atitudine

Variabila inclusă este selectată x 2. Conversia ulterioară a șirurilor are ca rezultat un nou tabel simplex:

De bază variabile	x 1	x 2	x 3	x 4	x 5	Soluţie
x 3 x 2 x 5						–1 –1

Soluție nouă de asemenea, optim, dar încă inacceptabil. Ca o nouă variabilă exclusă alegem (arbitrar) x 3. Să definim variabila care trebuie inclusă.

Variabile	x 1	x 2	x 3	x 4	x 5
Ecuaţie x 4 - ecuație
atitudine

Pasul 0. Etapa pregătitoare.

Reducem problema LP la o formă specială (15).

Pasul 1. Compilarea tabel simplex, corespunzătoare formei speciale:

Rețineți că acest tabel corespunde unei soluții de bază admisibile
probleme (15). Valoarea funcției obiectiv pe această soluție

Pasul 2. Verificarea optimității

Dacă printre elementele rândului index există tabele simplex
atunci nu există un singur element pozitiv
, soluția optimă la problema LP se găsește:. Algoritmul se termină.

Pasul 3. Verificarea indecidibilității

Dacă printre
există un element pozitiv
, și în coloana corespunzătoare
nu există un singur element pozitiv
, apoi funcția obiectiv L este nemărginită de jos pe mulţimea admisibilă. În acest caz, nu există o soluție optimă. Algoritmul se termină.

Pasul 4. Selectarea unei coloane principale q

Printre elemente
alege elementul pozitiv maxim
.Declarăm această coloană ca fiind coloana principală (permisivă).

Pasul 5. Selectarea liniei de conducere p

Printre elementele pozitive ale coloanei
găsiți elementul
, pentru care egalitatea este valabilă

.

Şir p Declarăm că este lider (permite). Element
Declarăm că este liderul (permițând).

Pasul 6. Conversie tabel simplex

Creăm un nou tabel simplex în care:

a) în locul variabilei de bază notează , în loc de o variabilă nebază notează ;

b) elementul conducător se înlocuiește cu valoarea inversă
;

c) toate elementele coloanei principale (cu excepția
) înmulțiți cu
;

d) toate elementele liniei de conducere (cu excepția
) înmulțiți cu ;

e) elementele rămase ale tabelului simplex se transformă după următoarea schemă „dreptunghi”.

Produsul a trei factori se scade din elementul:

primul este elementul corespunzător al coloanei principale;

al doilea este elementul corespunzător al liniei de conducere;

a treia este reciproca elementului conducător
.

Elementul transformat și cei trei factori corespunzători acestuia sunt tocmai vârfurile „dreptunghiului”.

Pasul 7 Tranziția la următoarea iterație se realizează prin revenirea la pasul 2.

2.3. Algoritmul metodei simplex pentru problema maximă

Algoritmul metodei simplex pentru problema maximă diferă de algoritmul pentru problema minimă doar în semnele liniei index a coeficienților din funcția obiectiv
, si anume:

La pasul 2:
:

La pasul 3
. Funcția obiectiv este nemărginită de sus pe mulțimea admisibilă.

La pasul 4:
.

2.4. Un exemplu de rezolvare a unei probleme folosind metoda simplex

Rezolvați problema scrisă sub forma (15).

Să creăm un tabel simplex:

Deoarece coeficienții dreptei funcției obiectiv sunt nenegativi, soluția de bază inițială nu este optimă. Valoarea funcției obiectiv pentru această bază L=0.

Selectați coloana principală - aceasta este coloana corespunzătoare variabilei .

Selectați linia principală. Pentru a face asta găsim
. Prin urmare, linia de conducere corespunde variabilei .

Transformăm tabelul simplex prin introducerea unei variabile în bază și scoaterea variabilei de la bază. Obținem tabelul:

O iterație a metodei este finalizată. Să trecem la o nouă iterație. Tabelul rezultat nu este optim. Soluția de bază corespunzătoare tabelului are forma . Valoarea funcției obiectiv pe această bază L= -2.

Coloana principală aici este coloana corespunzătoare variabilei . Linia principală – linia corespunzătoare variabilei . După efectuarea transformărilor, obținem un tabel simplex:

Încă o iterație finalizată. Să trecem la o nouă iterație.

Linia funcției obiectiv nu conține valori pozitive, ceea ce înseamnă că soluția de bază corespunzătoare este optimă, iar algoritmul se termină.

Este luat în considerare un exemplu de rezolvare a unei probleme folosind metoda simplex, precum și un exemplu de rezolvare a unei probleme duale.

Stare problematica

Pentru a vinde trei grupe de bunuri, o întreprindere comercială are trei tipuri de resurse materiale și monetare limitate în valoare de b 1 = 240, b 2 = 200, b 3 = 160 de unități. În același timp, pentru vânzarea unui grup de mărfuri pentru 1 mie de ruble. cifra de afaceri a mărfurilor, resursa de primul tip este consumată în valoare de 11 = 2 unități, resursa de al doilea tip în valoare de 21 = 4 unități, resursa de al treilea tip în valoare de 31 = 4 unitati. Pentru vânzarea a 2 și 3 grupuri de mărfuri pentru 1 mie de ruble. cifra de afaceri se consumă în funcție de resursa primului tip în valoare de a 12 = 3, a 13 = 6 unități, resursa de al doilea tip în cantitate de a 22 = 2, a 23 = 4 unități, resursa de al treilea tip în valoare de a 32 = 6, a 33 = 8 unități . Profitați din vânzarea a trei grupuri de mărfuri pentru 1 mie de ruble. cifra de afaceri este respectiv c 1 = 4, c 2 = 5, c 3 = 4 (mii de ruble). Determinați volumul planificat și structura cifrei de afaceri comerciale astfel încât profitul întreprinderii comerciale să fie maximizat.

La problema directă a planificării cifrei de afaceri, rezolvate prin metoda simplex, compune dubla problema programare liniară.
Instala perechi conjugate de variabile probleme directe și duale.
După perechi conjugate de variabile, din soluția problemei directe obținem rezolvarea problemei duale, în care este produs evaluarea resurselor, cheltuită pentru vânzarea de bunuri.

Rezolvarea problemei folosind metoda simplex

Fie x 1, x 2, x 3 numărul de mărfuri vândute, în mii de ruble, 1, 2, respectiv 3 grupuri. Atunci modelul matematic al problemei are forma:

F = 4 x 1 + 5 x 2 + 4 x 3 ->max

0)))(~)" title="delim(lbrace)(matrice(4)(1)((2x_1 + 3x_2 + 6x_3= 0)))(~)">!}

Rezolvăm metoda simplex.

Introducem variabile suplimentare x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0 pentru a transforma inegalitățile în egalități.

Să luăm ca bază x 4 = 240; x 5 = 200; x 6 = 160.

Introducem datele în tabel simplex

Tabel simplex nr. 1

Funcția obiectivă:

0 240 + 0 200 + 0 160 = 0

Calculăm estimări folosind formula:

Δ 1 = 0 2 + 0 4 + 0 4 - 4 = - 4
Δ 2 = 0 3 + 0 2 + 0 6 - 5 = - 5
Δ 3 = 0 6 + 0 4 + 0 8 - 4 = - 4
Δ 4 = 0 1 + 0 0 + 0 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 0 0 - 0 = 0
Δ 6 = 0 0 + 0 0 + 0 1 - 0 = 0

Deoarece există estimări negative, planul nu este optim. Cel mai mic scor:

Introducem variabila x 2 în bază.

Definim o variabilă care reiese din bază. Pentru a face acest lucru, găsim cel mai mic raport nenegativ pentru coloana x2.

= 26.667

Cel mai mic nenegativ: Q 3 = 26,667. Deducem variabila x 6 din bază

Împărțiți a treia linie la 6.
Din prima linie, scădeți a treia linie, înmulțită cu 3
Din a 2-a linie, scădeți a 3-a linie, înmulțită cu 2

Calculam:

Primim un tabel nou:

Tabel Simplex nr. 2

Funcția obiectivă:

0 160 + 0 440/3 + 5 80/3 = 400/3

Calculăm estimări folosind formula:

Δ 1 = 0 0 + 0 8/3 + 5 2/3 - 4 = - 2/3
Δ 2 = 0 0 + 0 0 + 5 1 - 5 = 0
Δ 3 = 0 2 + 0 4/3 + 5 4/3 - 4 = 8/3
Δ 4 = 0 1 + 0 0 + 5 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 5 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1)/3 + 5 1/6 - 0 = 5/6

Deoarece există o estimare negativă Δ 1 = - 2/3, planul nu este optim.

Introducem variabila x 1 în bază.

Definim o variabilă care reiese din bază. Pentru a face acest lucru, găsim cel mai mic raport nenegativ pentru coloana x 1.

Cel mai mic nenegativ: Q 3 = 40. Deducem variabila x 2 din bază

Împărțiți a treia linie la 2/3.
Din a 2-a linie, scădeți a 3-a linie, înmulțită cu 8/3

Calculam:

Primim un tabel nou:

Tabel simplex nr. 3

Funcția obiectivă:

0 160 + 0 40 + 4 40 = 160

Calculăm estimări folosind formula:

Δ 1 = 0 0 + 0 0 + 4 1 - 4 = 0
Δ 2 = 0 0 + 0 (-4) + 4 3/2 - 5 = 1
Δ 3 = 0 2 + 0 (-4) + 4 2 - 4 = 4
Δ 4 = 0 1 + 0 0 + 4 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 4 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1) + 4 1/4 - 0 = 1

Deoarece nu există evaluări negative, planul este optim.

Soluția problemei:

Răspuns

x 1 = 40; x2 = 0; x 3 = 0; x 4 = 160; x 5 = 40; x6 = 0; F max = 160

Adică, este necesar să vindeți primul tip de mărfuri în valoare de 40 de mii de ruble. Produsele de tipurile 2 și 3 nu trebuie vândute. În acest caz, profitul maxim va fi F max = 160 de mii de ruble.

Rezolvarea problemei duale

Problema duală are forma:

Z = 240 y 1 + 200 y 2 + 160 y 3 ->min

Title="delim(lbrace)(matrix(4)(1)((2y_1 + 4y_2 + 4y_3>=4) (3y_1 + 2y_2 + 6y_3>=5) (6y_1 + 4y_2 + 8y_3>=4) (y_1, y_2, y_3>= 0)))(~)">!}

Introducem variabile suplimentare y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0 pentru a transforma inegalitățile în egalități.

Perechile conjugate de variabile ale problemelor directe și duale au forma:

Din ultimul tabel simplex nr. 3 al problemei directe, găsim soluția problemei duale:

Z min = F max = 160;
y 1 = Δ 4 = 0; y 2 = Δ 5 = 0; y 3 = Δ 6 = 1; y 4 = Δ 1 = 0; y5 = A2 = 1; y 6 = Δ 3 = 4;