Metoda soluției simplex. Metoda simplex pentru rezolvarea zlp. Metoda simplex pentru rezolvarea LPP

Iată o soluție manuală (nu un applet) a două probleme folosind o metodă simplex (asemănătoare cu rezolvarea unui applet) cu explicații detaliate pentru a înțelege algoritmul de rezolvare a problemelor folosind o metodă simplex. Prima problemă conține semne de inegalitate doar „≤” (o problemă cu o bază inițială), a doua poate conține semne „≥”, „≤” sau „=" (o problemă cu o bază artificială), acestea sunt rezolvate în moduri diferite .

Metoda simplex, rezolvarea unei probleme cu o bază inițială

1)Metoda simplex pentru o problemă cu o bază inițială (toate semnele de inegalitate-constrângeri „≤”).

Să scriem sarcina în canonic formă, adică constrângerile de inegalitate pot fi rescrise ca egalități prin adăugare bilanț variabile:

Acest sistem este un sistem cu o bază (baza s 1, s 2, s 3, fiecare dintre ele este inclusă într-o singură ecuație a sistemului cu coeficient 1), x 1 și x 2 sunt variabile libere. Problemele, în soluţia cărora se foloseşte metoda simplex, trebuie să aibă următoarele două proprietăţi: - sistemul de constrângeri trebuie să fie un sistem de ecuaţii cu bază; - termenii liberi ai tuturor ecuațiilor din sistem trebuie să fie nenegativi.

Sistemul rezultat este un sistem cu o bază și termenii săi liberi sunt nenegativi; prin urmare, putem aplica metoda simplex... Să compunem primul tabel simplex (Iterația 0) pentru a rezolva problema metoda simplex, adică un tabel de coeficienți ai funcției obiective și un sistem de ecuații pentru variabilele corespunzătoare. Aici „BP” înseamnă coloana variabilelor de bază, „Soluție” - coloana părților din dreapta ale ecuațiilor sistemului. Soluția nu este optimă pentru că există coeficienți negativi în rândul z.

iterația metodei simplex 0

							Atitudine

Pentru a îmbunătăți soluția, să trecem la următoarea iterație metoda simplex, obținem următorul tabel simplex. Pentru a face acest lucru, trebuie să alegeți coloană permisivă, adică o variabilă care va fi inclusă în bază la următoarea iterație a metodei simplex. Este selectat de cel mai mare coeficient negativ în valoare absolută din rândul z (în problema maximă) - în iterația inițială a metodei simplex, aceasta este coloana x 2 (coeficientul -6).

Este apoi selectat șir permisiv, adică variabila care va ieși din bază la următoarea iterație a metodei simplex. Este selectat după cel mai mic raport al coloanei „Decizie” la elementele pozitive corespunzătoare ale coloanei de rezolvare (coloana „Ratio”) - în iterația inițială, acesta este rândul s 3 (coeficientul 20).

Element permisiv este situat la intersecția coloanei de rezolvare și a rândului de rezoluție, celula sa este evidențiată, este egală cu 1. Prin urmare, la următoarea iterație a metodei simplex, variabila x 2 va fi înlocuită în baza s 1. Rețineți că relația nu este căutată în linia z; acolo este pusă o liniuță „-”. Dacă există relații minime identice, atunci se alege oricare dintre ele. Dacă în coloana de rezolvare toți coeficienții sunt mai mici sau egali cu 0, atunci soluția problemei este infinită.

Să completăm următorul tabel „Iterația 1”. O vom obține din tabelul „Iterație 0”. Scopul transformărilor ulterioare este de a transforma coloana de rezoluție x 2 într-una (cu unul în loc de elementul de rezolvare și cu zerouri în loc de alte elemente).

1) Calculul rândului x 2 al tabelului „Iterația 1”. În primul rând, împărțim toți membrii rândului de rezolvare s 3 din tabelul „Iterația 0” la elementul de rezolvare (în acest caz este egal cu 1) din acest tabel, obținem rândul x 2 în tabelul Iterația 1. pentru că elementul de rezolvare în acest caz este egal cu 1, apoi rândul s 3 din tabelul „Iterația 0” va coincide cu rândul x 2 din tabelul „Iterația 1”. Am primit rândul x 2 din tabelul „Iterația 1” 0 1 0 0 1 20, restul rândurilor din tabelul „Iterația 1” se vor obține din acest rând și rândurile tabelului „Iterația 0” după cum urmează:

2) Calculul rândului z al tabelului „Iterația 1”. În loc de -6 în primul rând (z-rând) din coloana x 2 din tabelul Iterația 0, ar trebui să fie 0 în primul rând al tabelului Iterația 1. Pentru a face acest lucru, înmulțim toate elementele rândului x 2 din tabelul „Iterația 1” 0 1 0 0 1 20 cu 6, obținem 0 6 0 0 6 120 și adăugăm acest rând cu primul rând (z - rând) din tabelul „Iterația 0” -4 -6 0 0 0 0, obținem -4 0 0 0 6 120. În coloana x 2, apare zero 0, scopul este atins. Elementele de coloană permisive x 2 sunt evidențiate cu roșu.

3) Calculul rândului s 1 din tabelul „Iterația 1”. În locul 1 în s 1 rând al tabelului „Iterația 0”, trebuie să existe 0 în tabelul „Iterația 1”. Pentru a face acest lucru, înmulțim toate elementele rândului x 2 din tabelul „Iterația 1” 0 1 0 0 1 20 cu -1, obținem 0 -1 0 0 -1 -20 și adăugăm acest rând cu s 1 - rândul tabelului „Iterația 0” 2 1 1 0 0 64, obținem rândul 2 0 1 0 -1 44. În coloana x 2 obținem 0 necesar.

4) Calculul rândului s 2 din tabelul „Iterația 1”. În locul 3 în rândul s 2 al tabelului „Iterația 0”, trebuie să existe 0 în tabelul „Iterația 1”. Pentru a face acest lucru, înmulțim toate elementele rândului x 2 din tabelul „Iterația 1” 0 1 0 0 1 20 cu -3, obținem 0 -3 0 0 -3 -60 și adăugăm acest rând cu s 1 - rândul tabelului „Iterația 0” 1 3 0 1 0 72, obținem rândul 1 0 0 1 -3 12. În coloana x 2 se obține 0 necesar. Coloana x 2 din tabelul „Iterația 1” are devine unul, conține unul 1 și restul 0.

Rândurile tabelului „Iterația 1” sunt obținute conform următoarei reguli:

Rând nou = Rând vechi - (Factor de coloană de rezoluție al rândului vechi) * (Rând de rezoluție nou).

De exemplu, pentru linia z avem:

Linie z veche (-4 -6 0 0 0 0) - (- 6) * Linie nouă de rezoluție - (0 -6 0 0 -6 -120) = Linie z nouă (-4 0 0 0 6 120).

Pentru următoarele tabele, recalcularea elementelor de tabel se face în același mod, așa că o omitem.

Iterația metodei simplex 1

							Atitudine

Permitând coloana x 1, rezolvând rândul s 2, s 2 părăsește baza, x 1 intră în bază. Exact în același mod, obținem restul tabelelor simplex până când obținem un tabel cu toți coeficienții pozitivi în rândul z. Acesta este un semn al unei mese optime.

iterația metodei simplex 2

							Atitudine

Coloana de rezoluție s 3, rândul de rezolvare s 1, s 1 părăsește baza, s 3 intră în bază.

Iterația metodei simplex 3

							Atitudine

În rândul z, toți coeficienții sunt nenegativi, prin urmare, soluția optimă este x 1 = 24, x 2 = 16, z max = 192.

Metoda simplex este un proces iterativ de rezolvare dirijată a unui sistem de ecuații pas cu pas, 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 regiunii soluției fezabile, care îmbunătățesc valoarea funcției obiectiv. până când 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 transformărilor Jordan); forma de bază de înregistrare;
metoda simplex modificată; sub formă de coloană; în formă de linie.

Instruire. Selectați numărul de variabile și numărul de linii (număr de constrângeri). Soluția rezultată este salvată într-un fișier Word și Excel. În acest caz, nu luați în considerare constrângerile de tip x i ≥0. Dacă în sarcină pentru unele x i nu există restricții, atunci LPP-ul trebuie adus la CLP sau utilizați acest serviciu. Soluția detectează automat utilizarea metoda M(metoda simplex pe bază artificială) și metoda simplex în două etape.

Următoarele sunt, de asemenea, utilizate cu acest calculator:
Metoda grafică de rezolvare a LPP
Rezolvarea problemei de transport
Soluție de joc Matrix
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, 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 de mărfuri vândute X și sunt prezentate în tabel.

Volumul mărfurilor X (în loturi)	Venitul G (X)
Volumul mărfurilor X (în loturi)	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:

Întocmirea primului plan de bază. Trecerea la forma canonică a problemei de programare liniară prin introducerea unor variabile de echilibru suplimentare nenegative.
Verificarea optimității planului... Dacă există cel puțin un coeficient de rând index mai mic decât zero, atunci planul nu este optim și trebuie îmbunătățit.
Definirea liniilor de coloană și rând... Dintre coeficienții negativi ai rândului index, este selectat cel mai mare în valoare absolută. Apoi elementele coloanei de membri liberi ai tabelului simplex sunt împărțite în elemente de același semn al coloanei principale.
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 de rezolvare a minimizării funcției) și a valorii maxime (F (x) → max , vezi exemplul de rezolvare a maximizării funcției)

Soluția 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 de bază a programării liniare... Dacă funcția obiectiv a LPP atinge o valoare extremă la un moment dat în regiunea soluțiilor fezabile, atunci aceasta ia această valoare în punctul de colț. Dacă funcția obiectiv a LPP atinge valoarea sa extremă în mai mult de un punct de colț, atunci ea 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 deplasarea de la un punct de colț la cel vecin, care este 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ă, prin urmare, trecerea de la un punct de colț la cel învecinat poate fi efectuată prin schimbarea în bază a unei singure variabile de bază la o variabilă din nonbază.
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 unei soluții optime.

Cum se utilizează 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, atunci va găsi planul optim.

Observația 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 unui ghid de linie. Este posibil să nu observați deloc degenerarea problemei dacă alegeți o altă linie ca ghid. În caz de ambiguitate, selectați rândul cu cel mai mic indice pentru a evita bucla.

Observația 2. Fie la un punct extrem, toate diferențele simplex să fie nenegative D k ³ 0 (k = 1..n + m), adică. se obține o soluție optimă și există un vector nonbazic А k pentru care D k = 0. Atunci maximul este atins 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 se găsește î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ă un vector cu cea mai mare diferență pozitivă simplex. În plus, se aplică același algoritm ca și pentru problema de maximizare.

Dacă condiția „Este necesar ca materia primă de tip III să fi fost consumată complet”, atunci condiția corespunzătoare este egalitatea.

O introducere analitică în metoda simplex

Metoda simplex este o metodă de programare liniară versatilă.

Deci, dacă rezolvăm LPP în forma canonică, atunci sistemul de constrângeri este sistemul obișnuit de ecuații liniare. La rezolvarea problemelor LP se obțin sisteme de ecuații liniare care, de regulă, au infinit de soluții.

De exemplu, să fie dat sistemul

Aici numărul de ecuații este 2, iar numărul de necunoscute este 3, sunt mai puține ecuații. Să exprimăm x 1 și x 2 în termeni de x 3:

Aceasta este soluția generală a sistemului. dacă atribuim valori numerice arbitrare variabilei x 3, atunci vom găsi soluții particulare ale sistemului. De exemplu, X 3 =1 → X 1 =1 → X 2 = 6. Avem (1, 6, 1) - o anumită soluție. Lasa X 3 =2 → X 1 =-3, X 2 = 1, (-3, 1, 2) este o altă soluție particulară. Există o infinitate de astfel de soluții particulare.

Variabile X 1 și X 2 sunt numite de bazăși variabila X 3 - nu de bază, gratuit.

O colecție de variabile X 1 și X 2 formează baza: B (X 1 , X 2). Dacă X 3 = 0, atunci soluția particulară obținută (5, 11, 0) se numește soluție de bază corespunzătoare bazei B (X 1 , X 2).

O soluție de bază este o soluție corespunzătoare valorilor zero ale variabilelor libere.
Alte variabile ar putea fi considerate de bază: ( X 1 , X 3) sau ( X 2 , X 3).
Cum să mergi de la o bază B(X 1 , X 2) pe o altă bază B(X 1 , X 3)?
Pentru aceasta aveți nevoie de o variabilă X 3 se traduce în bază, și X 2 - în nebază, adică în ecuații este necesar X 3 exprima prin X 2 și înlocuiți în primul:

B(X 1 , x 3) este după cum urmează: (-19/5; 0; 11/5).

Dacă acum de la bază B(X 1 , X 3) vrem să mergem la bază B(X 2 , X 3), atunci

Soluție de bază corespunzătoare bazei B (X 2 , X 3): (0;19/4; 7/8).
Dintre cele trei soluții de bază găsite, soluția corespunzătoare bazei B (X 1 , X 3) - negativ X 1 < 0, нас в ЗЛП интересуют только неотрицательные решения.

Dacă problema LP are o soluție, atunci aceasta este atinsă pe mulțimea soluțiilor de bază nenegative ale sistemului de constrângeri de formă canonică.

Prin urmare, ideea metodei simplex constă într-o tranziție secvențială de la o bază la alta, mai bine din punctul de vedere al valorii funcției obiectiv.

Un exemplu. Rezolvați problema LP.

Funcţie F= X 2 - X 1 → min trebuie minimizat pentru un sistem dat de constrângeri:
-2X 1 + X 2 + X 3 = 2
X 1 + X 2 + X 5 = 5
X 1 - 2X 2 + X 4 = 12
X i ≥ 0, i = 1, 5

Aceste constrângeri pot fi văzute ca provenind din inegalități și variabile X 3 , X 5 , X 4 - ca suplimentar.
Să notăm constrângerile alegând o bază de variabile B{ X 3 , X 4 , X 5 }:

Această bază corespunde soluției de bază nenegative
X 1 = 0, X 2 = 0, X 3 = 2, X 4 = 2, X 5 = 5 sau (0, 0, 2, 2, 5).
Acum trebuie să te exprimi F prin variabile non-bazice, în cazul nostru acest lucru s-a făcut deja: F= X 2 - X 1 .
Verificați dacă funcția a ajuns F valoarea sa minima. Pentru această soluție de bază F= 0 - 0 = 0 - valoarea functiei este 0. Dar poate fi micsorata daca X 1 va crește, deoarece coeficientul din funcția at X 1 este negativ. Cu toate acestea, la creștere X 1 valori variabile X 4 , X 5 scădere (vezi a doua și a treia egalitate a sistemului de restricții). Variabil X 1 nu poate fi crescut la mai mult de 2, în caz contrar X 4 va deveni negativ (datorită egalității 2) și nu mai mult de până la 5, în caz contrar X 5 - negativ. Deci, din analiza egalităților rezultă că variabila X 1 poate fi crescut la 2, iar valoarea funcției va scădea.
Trecem la noua bază B 2, introducând variabila X 1 în bază în loc de X 4 .
B 2 {X 1 , X 3 , X 5 }.
Să exprimăm aceste variabile de bază în termeni de variabile nebazice. Pentru a face acest lucru, mai întâi ne exprimăm X 1 din a doua ecuație și înlocuiți-o în restul, inclusiv funcția.

Soluție de bază corespunzătoare bazei B 3 {NS 1 , NS 2 , NS 3), (4, 1, 9, 0, 0) este scris, iar funcția ia valoarea F= -3. Rețineți că valoarea F a scăzut, adică s-a îmbunătățit în comparație cu baza anterioară.
Privind punctul de vedere al funcției obiective , remarcăm că a îmbunătăți, adică a scădea valoarea F nu este posibil şi numai dacă X 4 = 0, X 5 = 0 valoare F= -3. o singura data X 4 , X 5 va deveni pozitiv, valoarea F va crește doar, deoarece coeficienții la X 4 , X 5 sunt pozitive. Prin urmare, funcția F a ajuns la valoarea optimă F* = -3. Deci cea mai mică valoare F, egal cu -3, se realizează la X 1 * = 4, X 2 * = 1, X 3 * = 9, X 4 * = 0, X 5 * = 0.

Acest exemplu demonstrează clar ideea metodei: trecând treptat de la bază la bază, acordând întotdeauna atenție valorilor funcției obiective care ar trebui să se îmbunătățească, ajungem la o bază în care valoarea funcției obiective nu poate fi îmbunătățit, este optim. Rețineți că există un număr finit de baze, deci numărul de pași pe care îi facem către acea bază necesară este finit.

Metoda simplex, rezolvarea unei probleme cu o bază inițială

1)Metoda simplex pentru o problemă cu o bază inițială (toate semnele de inegalitate-constrângeri „≤”).

Să scriem sarcina în canonic formă, adică constrângerile de inegalitate pot fi rescrise ca egalități prin adăugare bilanț variabile:

iterația metodei simplex 0

							Atitudine

Rândurile tabelului „Iterația 1” sunt obținute conform următoarei reguli:

Rând nou = Rând vechi - (Factor de coloană de rezoluție al rândului vechi) * (Rând de rezoluție nou).

De exemplu, pentru linia z avem:

Linie z veche (-4 -6 0 0 0 0) - (- 6) * Linie nouă de rezoluție - (0 -6 0 0 -6 -120) = Linie z nouă (-4 0 0 0 6 120).

Pentru următoarele tabele, recalcularea elementelor de tabel se face în același mod, așa că o omitem.

Iterația metodei simplex 1

							Atitudine

iterația metodei simplex 2

							Atitudine

Coloana de rezoluție s 3, rândul de rezolvare s 1, s 1 părăsește baza, s 3 intră în bază.

Iterația metodei simplex 3

							Atitudine

În rândul z, toți coeficienții sunt nenegativi, prin urmare, soluția optimă este x 1 = 24, x 2 = 16, z max = 192.

Se are în vedere un exemplu de rezolvare a problemei prin metoda simplex, precum și un exemplu de rezolvare a problemei duale.

Conţinut

Sarcina

Pentru vânzarea a trei grupe de mărfuri, o întreprindere comercială are trei tipuri de resurse materiale și bănești 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 resursei de primul tip se consumă î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 este cheltuită, respectiv, din resursa de primul tip în valoare de a 12 = 3, a 13 = 6 unități, resursa de al doilea tip în valoare de a 22 = 2, a 23 = 4 unități, resursă 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 astfel încât profitul întreprinderii comerciale să fie maxim.

Pentru sarcina directă de planificare a cifrei de afaceri, rezolvabil prin metoda simplex, machiaj sarcină dublă programare liniară.
Instalare perechi conjugate de variabile sarcini directe și duble.
După perechi conjugate de variabile, din rezolvarea problemei directe, se obține soluție dublă a problemei in care evaluarea resurselor cheltuită pentru vânzarea mărfurilor.

Rezolvarea problemei prin metoda simplex

Fie x 1, x 2, x 3 - numărul de bunuri vândute, în mii de ruble, 1, 2, 3 - grupele ei, respectiv. Atunci modelul matematic al problemei are forma:

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

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

Rezolvăm metoda simplex.

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

Luați ca bază x 4 = 240; x 5 = 200; x 6 = 160.

Introducem datele în tabel simplex

Tabelul Simplex numărul 1

Funcție obiectivă:

0 240 + 0 200 + 0 160 = 0

Calculăm scorurile 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ă evaluări negative, planul nu este optim. Nota cea mai mica:

Introducem variabila x 2 în bază.

Definim o variabilă care părăsește baza. Pentru a face acest lucru, găsiți cel mai mic raport nenegativ pentru coloana x 2.

= 26.667

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

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

Noi calculăm:

Primim un tabel nou:

Tabelul Simplex numărul 2

Funcție obiectivă:

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

Calculăm scorurile 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 părăsește baza. Pentru a face acest lucru, găsiți 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 al 3-lea rând la 2/3.
Din al 2-lea rând, scădeți al 3-lea rând, înmulțit cu 8/3

Noi calculăm:

Primim un tabel nou:

Tabelul Simplex numărul 3

Funcție obiectivă:

0 160 + 0 40 + 4 40 = 160

Calculăm scorurile 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.

Rezolvarea problemei:

x 1 = 40; x 2 = 0; x 3 = 0; x 4 = 160; x 5 = 40; x 6 = 0; F max = 160

Adică, este necesar să vindeți mărfurile de primul tip în valoare de 40 de mii de ruble. Nu este necesar să vindeți bunuri de tipul 2 și 3. În acest caz, profitul maxim va fi F max = 160 de mii de ruble.

Rezolvarea problemei duale

Problema dubla este:

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

Titlu = „(! LANG: delim (lbrace) (matrice (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))) (~)">!}

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

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

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

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

Y1 = 0; y 2 = 0; y 3 = 1; Z min = 160;

Metoda simplex- aceasta este o metoda de enumerare ordonata a planurilor de referinta (ordonarea este asigurata de modificari monotone ale valorii functiei obiectiv in timpul trecerii la planul urmator). În acest caz, este necesar să se respecte principiul: fiecare pas următor trebuie să îmbunătățească sau, în cazuri extreme, să nu înrăutățească valoarea funcției obiectiv.

Pentru a rezolva LPP metoda simplex se reduce la forma canonică, adică. din restricții – inegalități este necesar să se facă restricții – egalitate. Pentru aceasta, în fiecare constrângere este introdus unul suplimentar nenegativ. variabilă de echilibru cu semnul „+”, dacă semnul de inegalitate „£”, și cu semnul „-”, dacă semnul de inegalitate „³”.

Aceste variabile suplimentare sunt incluse în funcția obiectiv cu coeficienți zero, i.e. înregistrarea funcției obiectiv nu se va modifica. Fiecare variabilă care nu este supusă condiției de nonnegativitate poate fi reprezentată ca diferența a două variabile nenegative:.

Dacă constrângerile sarcinii reflectă disponibilitatea și consumul de resurse, atunci valoarea numerică a variabilei suplimentare din planul de sarcini, scrisă în forma canonică, este egală cu volumul resursei neutilizate.

Pentru a rezolva problema folosind metoda simplex, vom folosi tabele simplex trunchiate ale unui sistem de ecuații liniare și metoda de eliminare Jordan modificată.

1. Întocmim primul plan de bază

Sarcina rămâne aceeași. Să aducem forma standard a sistemului de inegalități (1) în forma canonică a sistemului de ecuații prin introducerea unor variabile de echilibru suplimentare X 3 , X 4 , X 5 ,X 6 .

În sens economic, valorile variabilelor suplimentare X 3 , X 4 , X 5 determină resturile de materii prime după vânzarea produselor.

Matricea sistemului de ecuații rezultat are forma:

Se vede ca in matrice A minorul de ordinul al patrulea de bază este un determinant compus din coeficienți unitari cu variabile suplimentare X 3 , X 4 , X 5 ,X 6, deoarece este diferit de zero și egal cu 1. Aceasta înseamnă că vectorii coloană pentru aceste variabile sunt liniar independenți; formă bază, și variabilele corespunzătoare X 3 , X 4 , X 5 ,X 6 sunt de bază(principal). Variabile X 1 , X 2 va fi chemat liber(non-mainstream).

Dacă variabile libere X 1 și X 2 pentru a seta valori diferite, apoi, rezolvând sistemul în raport cu variabilele de bază, obținem un set infinit de soluții particulare. Dacă variabilelor libere sunt atribuite numai valori zero, atunci se poate selecta din setul infinit de soluții particulare solutii de baza- planuri de bază.

Pentru a afla dacă variabilele pot fi de bază, este necesar să se calculeze determinantul format din coeficienții acestor variabile. Dacă determinantul dat nu este egal cu zero, atunci aceste variabile pot fi de bază.

Numărul de soluții de bază și numărul corespunzător de grupuri de variabile de bază nu poate fi mai mult decât, unde n Este numărul total de variabile, r- numărul de variabile de bază, r≤ m≤ n.

Pentru sarcina noastră r = 4; n= 6. Atunci, adică Sunt posibile 15 grupuri de 4 variabile de bază (sau 15 soluții de bază).

Să rezolvăm sistemul de ecuații pentru variabilele de bază X 3 , X 4 , X 5 ,X 6:

Presupunând că variabile libere X 1 = 0, X 2 = 0, obținem valorile variabilelor de bază: X 3 = 312; X 4 = 15; X 5 = 24;X 6 = –10, adică soluția de bază va fi = (0; 0; 312; 15; 24; –10).

Această soluție de bază este inacceptabil de cand X 6 = –10 ≤ 0, iar prin condiția restricțiilor X 6 ≥ 0. Prin urmare, în locul variabilei X 6 ca bază trebuie luată o altă variabilă din numărul de libere X 1 sau X 2 .

Soluția ulterioară va fi efectuată folosind tabele simplex scurtate, completând rândurile primului tabel cu coeficienții sistemului după cum urmează (Tabelul 1):

tabelul 1

F- se numește șirul index... Se umple cu coeficienții funcției obiectiv, luați cu semne opuse, deoarece ecuația funcției poate fi reprezentată sub forma F = 0 – (– 4X 1 – 3X 2).

În coloana de membri liberi b i există un element negativ b 4 = –10, adică soluția de sistem este invalidă. Pentru a obține o soluție fezabilă (linia de bază), element b 4 trebuie făcut nenegativ.

Noi alegem X 6 este un rând cu o intersecție negativă. Această linie conține elemente negative. Alegem oricare dintre ele, de exemplu, „-1” în X 1 -coloană, și X 1 -coloana este acceptată ca coloană permisivă(va defini că variabila X 1 va trece de la gratuit la de bază).

Împărțiți membrii gratuiti b i asupra elementelor corespunzătoare a este coloană de rezolvare, obținem relație de valoareΘ i= = (24, 15, 12, 10). Alegem cel mai mic pozitiv (minΘ i= 10), care se va potrivi linie de rezolvare... Șirul permisiv definește variabila x j, care la pasul următor iese din bază și devine liberă. De aceea X 6 -string este un șir de rezolvare, iar elementul „-1” este element de autorizare... Îl încercuim. Variabile X 1 și X 6 sunt schimbate.

Relații de evaluare Θ iîn fiecare linie sunt determinate conform regulilor:

1) Θ i= dacă b iși a este au semne diferite;

2) Θ i= ∞ dacă b i= 0 și a este < 0;

3) Θ i= ∞ dacă a este = 0;

4) Θ i= 0 dacă b i= 0 și a este > 0;

5) Θ i= dacă b iși a este au aceleasi semne.

Facem pasul excluderii iordaniene modificate (SHME) cu un element de rezolvare și întocmim un nou tabel (Tabelul 2) conform următoarei reguli:

1) în locul elementului de rezoluție (RE), este setată o valoare care este inversa acesteia, adică ;

2) elementele liniei de autorizare sunt împărțite în RE;

3) elementele coloanei de rezolvare sunt împărțite în RE-uri și semnul se modifică;

4) restul elementelor se găsesc după regula dreptunghiului:

De la masă. 2 se vede că termenii liberi din b i-coloana sunt nenegative, prin urmare, se obține soluția fezabilă inițială - primul plan de bază= (10; 0; 182; 5; 4; 0). În acest caz, valoarea funcției F() = 40. Geometric aceasta corespunde vârfului F(10; 0) a poligonului soluție (Fig. 1).

masa 2

2. Verificarea optimității planului. Planul de bază nu este optim, ca în F-linia are un coeficient negativ „–4”. Îmbunătățirea planului.

3. Găsirea unui nou plan de referință

Selectăm elementul de autorizare conform regulii:

Alegem cel mai mic coeficient negativ din F-linia „–4”, care definește coloana de rezolvare - X 6; variabil X 6 traducem în de bază;

Găsirea relațiilor Θ i, dintre ele o alegem pe cea mai mică pozitivă, care corespunde liniei de rezolvare:

min Θ i = min(14, 5, 2, ∞) = 2, prin urmare X 5 linii - permisiv, variabil X 5 traducem în liber (variabile X 5 și X 6 sunt schimbate).

La intersecția rândului și coloanei de rezolvare se află elementul de rezolvare „2”;

Efectuăm pasul SHMZH, construim tabelul. 3 conform regulii de mai sus și obținem un nou plan de referință = (12; 0; 156; 3; 0; 2).

Tabelul 3

4. Verificarea optimității noului plan de bază

Nici planul de bază nu este optim, deoarece în F-linia are un coeficient negativ „-1”. Valoarea funcției F() = 48, care corespunde geometric vârfului E(12,0) poligon soluție (Fig. 1). Îmbunătățirea planului.

5. Găsirea unui nou plan de referință

X 2 -coloană - permisiv, întrucât în F-șir în care se află cel mai mic coeficient negativ „-1”. X 2 -coloană (Δ 2 = –1). Găsiți cel mai mic Θ i: min Θ i = min(≈ 9, 6, ∞, 24) = 6, prin urmare X 4 - linie - permisiv. Element permisiv „1/2”. Schimbarea variabilelor X 2 și X 4 . Efectuăm pasul SHMZH, construim tabelul. 4, obținem un nou plan de referință = (9; 6; 51; 0; 0; 5).

6. Verificarea optimității planului de suport

V F-Rând toți coeficienții sunt nenegativi, prin urmare, planul de referință este optim. Se potrivește geometric cu punctul D(9; 6) (vezi Fig. 1). Planul optim dă valoarea maximă a funcției obiectiv c.u.