Rezolvarea prin metoda simplex, exemple de soluții. Un exemplu de rezolvare a unei probleme directe și duale folosind metoda simplex

. Algoritmul metodei simplex

Exemplul 5.1. Rezolvați următoarea problemă programare liniară metoda simplex:

Soluţie:

eu repetare:

x3, x4, x5, x6 x1,x2. Să exprimăm variabilele de bază în termeni de cele libere:

Să reducem funcția țintă la următoarea vedere:

Pe baza problemei obținute, vom forma tabelul simplex inițial:

Tabelul 5.3

Tabel simplex original

				Relații evaluative

Conform definiției soluției de bază, variabilele libere sunt egale cu zero, iar valorile variabilelor de bază sunt egale cu valorile corespunzătoare ale numerelor libere, adică:

Etapa 3: verificarea compatibilității sistemului de restricții PAP.

La această iterație (în Tabelul 5.3), semnul de inconsecvență al sistemului de constrângeri (semnul 1) nu este identificat (adică nu există o linie cu un număr liber negativ (cu excepția liniei funcției obiectiv) în care să nu existe să fie cel puțin un element negativ (adică coeficient negativ pentru o variabilă liberă)).

La această iterație (în Tabelul 5.3), semnul de nemărginire al funcției obiectiv (semnul 2) nu a fost identificat (adică nu există nicio coloană cu un element negativ în rândul funcției obiectiv (cu excepția coloanei numerelor libere). ) în care nu ar exista cel puţin un element pozitiv) .

Deoarece soluția de bază găsită nu conține componente negative, este admisibilă.

Etapa 6: verificarea optimității.

Soluția de bază găsită nu este optimă, deoarece conform criteriului de optimitate (semnul 4) nu ar trebui să existe elemente negative în linia funcției obiectiv (numărul liber al acestei linii nu este luat în considerare la considerarea acestui criteriu). Prin urmare, conform algoritmului metodei simplex, trecem la etapa 8.

Întrucât soluția de bază găsită este admisibilă, vom căuta coloana de rezolvare după următoarea schemă: determinăm coloanele cu elemente negative din rândul funcției obiectiv (cu excepția coloanei numerelor libere). Conform Tabelului 5.3, există două astfel de coloane: coloana „ x1„și coloana” x2" Din astfel de coloane se selectează cel care conține cel mai mic element din rândul funcției țintă. Ea va fi cea permisivă. Coloana " x2" conține cel mai mic element (–3) în comparație cu coloana " x1

Pentru a determina linia de rezolvare, găsim rapoartele pozitive estimate ale numerelor libere la elementele coloanei de rezolvare; linia care corespunde celui mai mic raport de evaluare pozitivă este acceptată ca rezolvată.

Tabelul 5.4

Tabel simplex original

În tabelul 5.4, cea mai mică relație de evaluare pozitivă corespunde liniei „ x5„, prin urmare, va fi permisiv.

Elementul situat la intersecția coloanei de activare și a rândului de activare este acceptat ca activator. În exemplul nostru, acesta este elementul care se află la intersecția liniei „ x5„și coloane” x2».

Elementul de rezolvare arată o variabilă de bază și una liberă care trebuie schimbate în tabelul simplex pentru a trece la noua variabilă „îmbunătățită”. solutie de baza. ÎN în acest caz, acestea sunt variabile x5Și x2, în noul tabel simplex (Tabelul 5.5) le schimbăm.

9.1. Transformarea elementului rezolutiv.

Elementul de rezoluție din tabelul 5.4 este convertit după cum urmează:

Introducem rezultatul rezultat într-o celulă similară din Tabelul 5.5.

9.2. Conversie șir de rezoluție.

Împărțim elementele rândului de rezolvare a tabelului 5.4 la elementul de rezolvare al acestui tabel simplex, rezultatele se încadrează în celule similare ale noului tabel simplex (tabelul 5.5). Transformările elementelor șirului de rezoluție sunt date în Tabelul 5.5.

9.3. Conversia coloanei de rezoluție.

Împărțim elementele coloanei de rezoluție din tabelul 5.4 la elementul de rezoluție al acestui tabel simplex, iar rezultatul este luat cu semnul opus. Rezultatele obținute se încadrează în celule similare ale noului tabel simplex (Tabelul 5.5). Transformările elementelor coloanei de rezoluție sunt date în Tabelul 5.5.

9.4. Transformarea elementelor rămase ale tabelului simplex.

Transformarea elementelor rămase ale tabelului simplex (adică elementele care nu sunt situate în rândul de rezolvare și coloana de rezolvare) se efectuează conform regulii „dreptunghi”.

De exemplu, luați în considerare transformarea unui element situat la intersecția liniei " x3„ și coloanele „”, îl vom desemna condiționat „ x3" În tabelul 5.4, desenăm mental un dreptunghi, al cărui vârf se află în celula a cărei valoare o transformăm (adică în celula „ x3"), iar celălalt (vertex diagonal) este într-o celulă cu un element de rezoluție. Celelalte două vârfuri (ale celei de-a doua diagonale) sunt determinate în mod unic. Apoi valoarea transformată a celulei " x3" va fi egală cu valoarea anterioară a acestei celule minus fracția, în numitorul căreia se află elementul de rezoluție (din tabelul 5.4), iar în numărător este produsul altor două vârfuri neutilizate, adică:

« x3»: .

Valorile altor celule sunt convertite în mod similar:

« x3 x1»: ;

« x4»: ;

« x4 x1»: ;

« x6»: ;

« x6 x1»: ;

«»: ;

« x1»: .

Ca urmare a acestor transformări, a fost obținut un nou tabel simplex (Tabelul 5.5).

II repetare:

Etapa 1: întocmirea unui tabel simplex.

Tabelul 5.5

Tabel simplexII iterații

				Estimată relaţie

Etapa 2: determinarea soluției de bază.

Ca rezultat al transformărilor simplex, a fost obținută o nouă soluție de bază (Tabelul 5.5):

După cum puteți vedea, cu această soluție de bază valoarea funcției obiectiv = 15, care este mai mare decât cu soluția de bază anterioară.

Incoerența sistemului de restricții în conformitate cu caracteristica 1 din Tabelul 5.5 nu a fost identificată.

Etapa 4: verificarea mărginirii funcției obiectiv.

Nelimitarea funcției obiectiv în conformitate cu criteriul 2 din Tabelul 5.5 nu este dezvăluită.

Etapa 5: verificarea admisibilității soluției de bază găsite.

Soluția de bază găsită conform criteriului 4 nu este optimă, deoarece linia funcției obiectiv a tabelului simplex (Tabelul 5.5) conține un element negativ: –2 (numărul liber al acestei linii nu este luat în considerare atunci când se consideră acest lucru caracteristică). Prin urmare, trecem la etapa 8.

Etapa 8: determinarea elementului rezolutiv.

8.1. Definiția coloanei de rezoluție.

Soluția de bază găsită este acceptabilă; determinăm coloanele cu elemente negative în rândul funcției obiectiv (cu excepția coloanei numerelor libere). Conform Tabelului 5.5, există o singură astfel de coloană: „ x1" Prin urmare, îl acceptăm așa cum este permis.

8.2. Definiția unui șir de activare.

Conform valorilor obținute ale relațiilor evaluative pozitive din tabelul 5.6, minimul este relația corespunzătoare liniei „ x3" Prin urmare, îl acceptăm așa cum este permis.

Tabelul 5.6

Tabel simplexII iterații

				Estimată relaţie
				3/1=3 – min

Etapa 9: transformarea tabelului simplex.

Transformările tabelului simplex (Tabelul 5.6) sunt efectuate în același mod ca în iterația anterioară. Rezultatele transformărilor elementelor tabelului simplex sunt prezentate în Tabelul 5.7.

III repetare

Pe baza rezultatelor transformărilor simplex ale iterației anterioare, compilam un nou tabel simplex:

Tabelul 5.7

Tabel simplexIII iterații

				Estimată relaţie

Etapa 2: determinarea soluției de bază.

Ca rezultat al transformărilor simplex, a fost obținută o nouă soluție de bază (Tabelul 5.7):

Etapa 3: verificarea compatibilității sistemului de restricții.

Incoerența sistemului de restricții în conformitate cu caracteristica 1 din Tabelul 5.7 nu a fost identificată.

Etapa 4: verificarea mărginirii funcției obiectiv.

Nelimitarea funcției obiectiv în conformitate cu criteriul 2 din Tabelul 5.7 nu este dezvăluită.

Etapa 5: verificarea admisibilității soluției de bază găsite.

Soluția de bază găsită în conformitate cu criteriul 3 este acceptabilă, deoarece nu conține componente negative.

Etapa 6: verificarea optimității soluției de bază găsite.

Soluția de bază găsită conform criteriului 4 nu este optimă, deoarece linia funcției obiectiv a tabelului simplex (Tabelul 5.7) conține un element negativ: –3 (numărul liber al acestei linii nu este luat în considerare atunci când se consideră acest lucru). caracteristică). Prin urmare, trecem la etapa 8.

Etapa 8: determinarea elementului rezolutiv.

8.1. Definiția coloanei de rezoluție.

Soluția de bază găsită este acceptabilă; determinăm coloanele cu elemente negative în rândul funcției obiectiv (cu excepția coloanei numerelor libere). Conform Tabelului 5.7, există o singură astfel de coloană: „ x5" Prin urmare, îl acceptăm așa cum este permis.

8.2. Definiția unui șir de activare.

Conform valorilor obținute ale relațiilor evaluative pozitive din tabelul 5.8, minimul este relația corespunzătoare liniei „ x4" Prin urmare, îl acceptăm așa cum este permis.

Tabelul 5.8

Tabel simplexIII iterații

				Estimată relaţie
				5/5=1 – min

Etapa 9: transformarea tabelului simplex.

Transformările tabelului simplex (Tabelul 5.8) sunt efectuate în același mod ca în iterația anterioară. Rezultatele transformărilor elementelor tabelului simplex sunt prezentate în Tabelul 5.9.

IV repetare

Etapa 1: construirea unei noi mese simplex.

Pe baza rezultatelor transformărilor simplex ale iterației anterioare, compilam un nou tabel simplex:

Tabelul 5.9

Tabel simplexIV iterații

				Estimată relaţie
			–(–3/5)=3/5
			–(1/5)=–1/5
			–(9/5)=–9/5
			–(–3/5)=3/5

Etapa 2: determinarea soluției de bază.

Ca urmare a transformărilor simplex s-a obținut o nouă soluție de bază; conform tabelului 5.9, soluția este următoarea:

Etapa 3: verificarea compatibilității sistemului de restricții.

Incoerența sistemului de restricții în conformitate cu caracteristica 1 din Tabelul 5.9 nu a fost identificată.

Etapa 4: verificarea mărginirii funcției obiectiv.

Nelimitarea funcției obiectiv în conformitate cu criteriul 2 din Tabelul 5.9 nu este dezvăluită.

Etapa 5: verificarea admisibilității soluției de bază găsite.

Soluția de bază găsită în conformitate cu criteriul 3 este acceptabilă, deoarece nu conține componente negative.

Etapa 6: verificarea optimității soluției de bază găsite.

Soluția de bază găsită în conformitate cu caracteristica 4 este optimă, deoarece nu există elemente negative în linia funcției obiectiv a tabelului simplex (Tabelul 5.9) (numărul liber al acestei linii nu este luat în considerare atunci când se ia în considerare această caracteristică) .

Etapa 7: verificarea alternativei soluției.

Soluția găsită este unică, deoarece nu există elemente zero în linia funcției obiectiv (Tabelul 5.9) (numărul liber al acestei linii nu este luat în considerare atunci când se ia în considerare această caracteristică).

Răspuns: valoare optimă funcţia obiectivă a problemei luate în considerare =24, care se realizează la.

Exemplul 5.2. Rezolvați problema de programare liniară de mai sus, cu condiția ca funcția obiectiv să fie minimizată:

Soluţie:

eu repetare:

Etapa 1: formarea tabelului simplex inițial.

Problema originala programarea liniară este dată în formă standard. Să-l aducem la formă canonică prin introducerea în fiecare dintre constrângerile de inegalitate a unei variabile suplimentare nenegative, i.e.

În sistemul de ecuații rezultat, luăm ca variabile permise (de bază). x3, x4, x5, x6, atunci variabilele libere vor fi x1,x2. Să exprimăm variabilele de bază în termeni de cele libere.

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

Sarcina

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ă.
Instalare 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. Apoi model matematic sarcina 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ție 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

Noi calculăm:

Primim masa noua:

Tabel Simplex nr. 2

Funcție 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

Noi calculăm:

Primim un tabel nou:

Tabel simplex nr. 3

Funcție 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.

Rezolvarea 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. Nu este nevoie 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 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; y2 = Δ5 = 0; y 3 = Δ 6 = 1; y 4 = Δ 1 = 0; y 5 = Δ 2 = 1; y 6 = Δ 3 = 4;

Ți-a plăcut? Adăugați la marcaje

Rezolvarea problemelor folosind metoda simplex: exemple online

Sarcina 1. Compania produce rafturi pentru baie în două dimensiuni - A și B. Agenții de vânzări estimează că pe piață pot fi vândute până la 550 de rafturi pe săptămână. Fiecare raft de tip A necesită 2 m2 de material, iar fiecare raft de tip B necesită 3 m2 de material. Compania poate primi până la 1200 m2 de material pe săptămână. Pentru fabricarea unui raft de tip A sunt necesare 12 minute de timp de mașină, iar pentru fabricarea unui raft de tip B - 30 de minute; Aparatul poate fi folosit 160 de ore pe săptămână. Dacă profitul din vânzarea de rafturi de tip A este de 3 unități monetare, iar din rafturi de tip B - 4 unități monetare. unități, atunci câte rafturi de fiecare tip ar trebui să fie produse pe săptămână?

Sarcina 2. Rezolvați o problemă de programare liniară folosind metoda simplex.

Sarcina 3. Compania produce 3 tipuri de produse: A1, A2, A3, folosind două tipuri de materii prime. Sunt cunoscute costurile fiecărui tip de materie primă pe unitate de producție, rezervele de materii prime pentru perioada de planificare, precum și profitul dintr-o unitate de producție de fiecare tip.

1. Câte articole de fiecare tip trebuie produse pentru a maximiza profitul?
2. Determinați starea fiecărui tip de materie primă și valoarea sa specifică.
3. Să se determine intervalul maxim de modificare a stocurilor pentru fiecare tip de materie primă, în cadrul căruia structura planului optim, i.e. Nomenclatura de producție nu se va modifica.
4. Determinați cantitatea de produse produse și profitul din producție atunci când creșteți stocul unuia dintre tipurile rare de materii prime la valoarea maximă posibilă (în intervalul dat de producție).
5. Determinați intervalele de modificare a profitului dintr-o unitate de producție de fiecare tip la care planul optim rezultat nu se va modifica.

Sarcina 4. Rezolvați o problemă de programare liniară metoda simplex:

Sarcina 5. Rezolvați o problemă de programare liniară folosind metoda simplex:

Sarcina 6. Rezolvați problema folosind metoda simplex, considerând ca plan de referință inițial planul dat în condiția:

Sarcina 7. Rezolvați problema folosind metoda simplex modificată.
Pentru a produce două tipuri de produse A și B, se folosesc trei tipuri de echipamente tehnologice. Pentru a produce o unitate de produs A, echipamentele de primul tip folosesc a1=4 ore, echipamente de al doilea tip a2=8 ore, iar echipamentele de al treilea tip a3=9 ore. Pentru a produce o unitate de produs B, echipamentele de primul tip folosesc b1=7 ore, echipamente de al doilea tip b2=3 ore, iar echipamentele de al treilea tip b3=5 ore.
Echipamentele de primul tip pot lucra pentru producerea acestor produse timp de cel mult t1=49 ore, echipamentele de al doilea tip nu mai mult de t2=51 ore, echipamentele de al treilea tip nu mai mult de t3=45 de ore.
Profitul din vânzarea unei unități de produs finit A este ALPHA = 6 ruble, iar produsul B este BETTA = 5 ruble.
Întocmește un plan de producție pentru produsele A și B, asigurând profit maxim din vânzarea acestora.

Sarcina 8. Găsi soluție optimă metoda dual simplex

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

Scopul serviciului. Serviciul este destinat soluții online Probleme 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 stocată în 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. La rezolvare, utilizarea este determinată automat 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 în modul online puteți determina prețul unui joc matrice (limitele inferioare și superioare), verificați disponibilitatea punct de șa, găsiți o soluție la o strategie mixtă folosind următoarele metode: minimax, simplex, grafică (geometrică), metoda 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. Dintre coeficienții negativi ai liniei index, este selectat cel mai mare 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 despre care vorbim despre căutare valoarea minima(F(x) → min , vezi un exemplu de soluție pentru minimizarea unei funcții) și valoarea maximă ((F(x) → max , vezi un exemplu de soluție 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 învecinat poate fi realizată prin schimbarea unei singure variabile de bază din bază la o variabilă dintr-o non-bază.
Implementarea metodei simplex în vigoare diverse caracteristiciși declarații de problemă, LP are diverse modificări.

Construcția tabelelor simplex continuă până la obținerea soluției optime. Cum puteți folosi 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, prin urmare, 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 ultima tabel simplex. Ultimele m componente ale vectorului diferențelor simplex (în coloanele variabilelor de echilibru) sunt soluția optimă a problemei duale. Sens funcții țintă Problemele directe și duale coincid în puncte optime.

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.