Metoda Simplex în forma sa pură online. Un exemplu de rezolvare a unei probleme. Metoda simplex pentru rezolvarea ZLP
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.
Î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:
- Î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 linie index mai mic decât zero, atunci planul nu este optim și trebuie îmbunătățit.
- 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 de conducere.
- 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 vecin poate fi realizată prin schimbarea unei singure variabile de bază din bază la o variabilă dintr-o non-bază.
Implementarea metodei simplex, datorită diferitelor 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, prin urmare, 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.
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 de primul 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 duble.
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, din 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ț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ădem a 3-a linie înmulțită cu 2
Noi calculăm:
Primim un tabel nou:
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 = 160Adică, 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; y 5 = Δ 2 = 1; y 6 = Δ 3 = 4;
Scurtă teorie
Au fost propuse multe metode diferite pentru a rezolva probleme de programare liniară. Cu toate acestea, metoda simplex s-a dovedit a fi cea mai eficientă și universală dintre ele. Trebuie remarcat faptul că la rezolvarea unor probleme, alte metode pot fi mai eficiente. De exemplu, pentru un ZLP cu două variabile, metoda optimă este , iar pentru rezolvarea acesteia se folosește metoda potențială. Metoda simplex este de bază și aplicabilă oricărui PPL în formă canonică.
În legătură cu teorema principală a programării liniare, apare în mod natural gândul despre următoarea modalitate de a rezolva LLP cu orice număr de variabile. Găsiți într-un fel toate punctele extreme ale poliedrului de planuri (nu sunt mai multe decât ) și comparați valorile funcției obiective la ele. O astfel de soluție, chiar și cu un număr relativ mic de variabile și restricții, este practic imposibilă, deoarece procesul de găsire a punctelor extreme este comparabil ca dificultate cu rezolvarea problemei inițiale și, în plus, numărul de puncte extreme ale poliedrului de planuri poate se dovedesc a fi foarte mari. În legătură cu aceste dificultăți, s-a pus problema enumerarii raționale a punctelor extreme.
Esența metodei simplex este următoarea. Dacă sunt cunoscute un punct extrem și valoarea funcției obiectiv la acesta, atunci toate punctele extreme la care funcția obiectiv ia cea mai proastă valoare sunt evident că nu sunt necesare. Prin urmare, dorința naturală este de a găsi o modalitate de a trece de la un punct extrem dat la unul mai bun adiacent de-a lungul marginii, de la acesta la unul și mai bun (nu mai rău) etc. Pentru a face acest lucru, trebuie să aveți un semn că nu există puncte extreme mai bune decât un punct extrem dat. Aceasta este ideea generală a celei mai utilizate metode simplex în prezent (metoda de îmbunătățire secvențială a planului) pentru rezolvarea ZLP. Deci, în termeni algebrici, metoda simplex presupune:
- capacitatea de a găsi un plan de referință inițial;
- prezența unui semn de optimitate a planului de referință;
- capacitatea de a trece la un plan de referință care nu este cel mai rău.
Exemplu de rezolvare a problemei
Sarcina
Pentru a vinde trei grupe de bunuri, o întreprindere comercială are trei tipuri de resurse materiale și monetare limitate în valoare 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 consumă resursa de primul tip în numărul de unități, resursa de al doilea tip în numărul de unități, resursa de al treilea tip în numărul de unități. Pentru vânzarea a 2 și 3 grupuri de mărfuri pentru 1 mie de ruble. cifra de afaceri a mărfurilor este cheltuită în funcție de resursa de primul tip în valoare de , unități, resurse de al doilea tip în valoare de , unități, resurse de al treilea tip în valoare de , unități. Profitați din vânzarea a trei grupuri de mărfuri pentru 1 mie de ruble. cifra de afaceri este, respectiv, de mii de ruble.
- Determinați volumul planificat și structura cifrei de afaceri comerciale astfel încât profitul întreprinderii comerciale să fie maximizat.
- Pentru problema directă a planificării cifrei de afaceri, rezolvată prin metoda simplex, creați o problemă de programare liniară duală.
- Stabiliți perechi conjugate de variabile ale problemelor directe și duale.
- După perechi conjugate de variabile, din rezolvarea problemei directe, se obține o soluție a problemei duale, în care se estimează resursele cheltuite pentru vânzarea mărfurilor.
Dacă admiterea ta la sesiune depinde de rezolvarea unui bloc de probleme și nu ai nici timpul și nici dorința de a sta la calcule, folosește capacitățile site-ului. Comandarea sarcinilor durează doar câteva minute. Puteți citi în detaliu (cum depuneți o cerere, prețuri, termeni, modalități de plată) pe pagina Cumpărați soluții la problemele de programare liniară...
Rezolvarea problemei
Construirea modelului
Să notăm cifra de afaceri din primul, al doilea și, respectiv, al treilea tip de mărfuri.
Apoi funcția obiectiv care exprimă profitul primit:
Limitări ale resurselor materiale și monetare:
Mai mult, conform sensului sarcinii
Obținem următoarea problemă de programare liniară:
Reducerea la forma canonică a ZLP
Să aducem problema în formă canonică. Pentru a transforma inegalitățile în egalități, introducem variabile suplimentare. Variabilele sunt incluse în restricții cu un coeficient de 1. Introducem toate variabilele suplimentare în funcția obiectiv cu un coeficient egal cu zero.
Constrângerea are o formă preferabilă dacă, cu partea dreaptă nenegativă, partea stângă are o variabilă care intră cu un coeficient egal cu unu, iar restul constrângerilor de egalitate au un coeficient egal cu zero. În cazul nostru, restricțiile 1, 2, 3 au o formă preferată cu variabilele de bază corespunzătoare.
Rezolvare folosind metoda simplex
Completam tabelul simplex al celei de-a 0-a iterații.
| BP | Simplex relaţie |
8 | 6 | 4 | 0 | 0 | 0 | 0 | 520 | 16 | 18 | 9 | 1 | 0 | 0 | 65/2 | 0 | 140 | 7 | 7 | 2 | 0 | 1 | 0 | 20 | 0 | 810 | 9 | 2 | 1 | 0 | 0 | 1 | 90 | 0 | -8 | -6 | -4 | 0 | 0 | 0 |
Întrucât rezolvăm problema la maximum, prezența numerelor negative în linia index atunci când rezolvăm problema la maximum indică faptul că nu am obținut soluția optimă și că este necesar să trecem de la tabelul celei de-a 0-a iterații. la următorul.
Trecem la următoarea iterație după cum urmează:
Coloana principală corespunde .
Rândul cheie este determinat de raportul minim dintre termenii liberi și membrii coloanei principale (relații simple):
La intersecția coloanei de cheie și a rândului de chei găsim elementul de activare, adică 7.
Acum începem să compilam prima iterație. În loc de vectorul unitar, introducem vectorul .
În noul tabel, în locul elementului de activare scriem 1, toate celelalte elemente ale coloanei cheie sunt zerouri. Elementele șirului cheie sunt împărțite în elementul de activare. Toate celelalte elemente ale tabelului sunt calculate folosind regula dreptunghiului.
Obținem tabelul primei iterații:
| BP | Simplex relaţie |
8 | 6 | 4 | 0 | 0 | 0 | 0 | 200 | 0 | 2 | 31/7 | 1 | -16/7 | 0 | 1400/31 | 8 | 20 | 1 | 1 | 2/7 | 0 | 1/7 | 0 | 70 | 0 | 630 | 0 | -7 | -11/7 | 0 | -9/7 | 1 | - | 160 | 0 | 2 | -12/7 | 0 | 8/7 | 0 |
Coloana cheie pentru prima iterație corespunde .
Găsim linia cheie, pentru aceasta definim:
La intersecția coloanei de chei și a rândului de chei găsim elementul de activare, i.e. 31/7.
Vectorul este derivat de la bază și vectorul este introdus.
Obținem tabelul celei de-a doua iterații:
| BP | Simplex relaţie |
8 | 6 | 4 | 0 | 0 | 0 | 4 | 1400/31 | 0 | 14/31 | 1 | 7/31 | -16/31 | 0 | 8 | 220/31 | 1 | 27/31 | 0 | -2/31 | 9/31 | 0 | 0 | 21730/31 | 0 | -195/31 | 0 | 11/31 | -65/31 | 1 | 7360/31 | 0 | 86/31 | 0 | 12/31 | 8/31 | 0 |
În rândul index, toți termenii sunt nenegativi, deci se obține următoarea soluție a problemei de programare liniară (o scriem din coloana de termeni liberi):
Astfel, este necesar să vindeți 7,1 mii de ruble. mărfuri de primul tip și 45,2 mii de ruble. bunuri de al 3-lea tip. Nu este rentabil să vinzi un produs de al 2-lea tip. În acest caz, profitul va fi maxim și se va ridica la 237,4 mii de ruble. Dacă planul optim este implementat, resursa rămasă de tipul 3 va fi de 701 unități.
Problema cu dublu LP
Să scriem un model al problemei duale.
Pentru a construi o problemă dublă, trebuie să utilizați următoarele reguli:
1) dacă problema directă este rezolvată la maximum, atunci problema duală se rezolvă la minim și invers;
2) în problema maximului, constrângerile de inegalitate au sensul ≤, iar în problema de minimizare au sensul ≥;
3) fiecărei constrângeri a problemei directe corespunde unei variabile a problemei duale și invers, fiecărei constrângeri a problemei duale corespunde unei variabile a problemei directe;
4) matricea sistemului de restricții a problemei duale se obține din matricea sistemului de restricții a problemei inițiale prin transpunere;
5) termenii liberi ai sistemului de constrângeri ai problemei directe sunt coeficienți ai variabilelor corespunzătoare funcției obiective a problemei duale și invers;
6) dacă variabilei problemei directe i se impune o condiție de non-negativitate, atunci constrângerea corespunzătoare problemei duale se scrie ca o constrângere de inegalitate, dacă nu, atunci ca o constrângere de egalitate;
7) dacă orice constrângere a problemei directe este scrisă ca o egalitate, atunci condiția de non-negativitate nu este impusă variabilei corespunzătoare problemei duale.
Transpunem matricea problemei originale:
Să aducem problema în formă canonică. Să introducem variabile suplimentare. Introducem toate variabilele suplimentare în funcția obiectiv cu un coeficient egal cu zero. Adăugăm variabile suplimentare în partea stângă a restricțiilor care nu au o formă preferată și obținem egalități.
Rezolvarea problemei duble LP
Corespondența dintre variabilele problemei originale și ale problemei duale:
Pe baza tabelului simplex, a fost obținută următoarea soluție la problema de programare liniară duală (o scriem din linia de jos):
Astfel, resursa de primul tip este cea mai rară. Scorul său este maxim și egal cu . Resursa de al treilea tip este redundantă - valoarea sa duală este zero. Fiecare unitate suplimentară de mărfuri din a 2-a grupă vândută va reduce profitul optim cu
Este considerată o metodă grafică pentru rezolvarea unei probleme de programare liniară (LPP) cu două variabile. Folosind exemplul unei probleme, se oferă o descriere detaliată a construirii unui desen și găsirea unei soluții.
Rezolvarea problemei transportului
Problema transportului, modelul său matematic și metodele de rezolvare sunt analizate în detaliu - găsirea planului de referință prin metoda elementului minim și căutarea soluției optime prin metoda potențialului.
Luarea deciziilor în condiții de incertitudine
Rezolvarea unui joc de matrice statistică în condiții de incertitudine este considerată folosind criteriile Wald, Savage, Hurwitz, Laplace și Bayes. Folosind un exemplu de problemă, construcția unei matrice de plată și a unei matrice de risc este prezentată în detaliu.
Dacă trebuie să rezolvați o problemă de programare liniară folosind tabele simplex, atunci serviciul nostru online vă va fi de mare ajutor. Metoda simplex implică căutarea secvențială prin toate vârfurile intervalului de valori acceptabile pentru a găsi vârful în care funcția ia o valoare extremă. În prima etapă, se găsește o soluție, care este îmbunătățită la fiecare pas ulterior. Această soluție se numește de bază. Iată secvența de acțiuni atunci când se rezolvă o problemă de programare liniară folosind metoda simplex:
Primul pas. În tabelul compilat, în primul rând, trebuie să vă uitați la coloana cu membri liberi. Dacă există elemente negative în el, atunci este necesar să treceți la a doua etapă, dacă nu, atunci la a cincea.
Al doilea pas. La al doilea pas, este necesar să se decidă ce variabilă să se excludă din bază și pe care să se includă pentru a recalcula tabelul simplex. Pentru a face acest lucru, ne uităm prin coloana cu termeni liberi și găsim un element negativ în ea. Linia cu un element negativ se va numi lider. În el găsim elementul negativ maxim în modul, coloana corespunzătoare este cea slave. Dacă există valori negative printre termenii liberi, dar nu există niciunul în rândul corespunzător, atunci un astfel de tabel nu va avea soluții. Variabila din rândul de început situat în coloana de termeni liberi este exclusă din bază, iar variabila corespunzătoare coloanei de început este inclusă în bază.
Tabelul 1.
| variabile de bază | Membri gratuiti sub restricții | Variabile non-bazice | |||||
| x 1 | x 2 | ... | x l | ... | x n | ||
| x n+1 | b 1 | un 11 | un 12 | ... | un 1l | ... | un 1n |
| x n+2 | b 2 | un 21 | un 22 | ... | un 2l | ... | un 2n |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| x n+r | b2 | un r1 | un r2 | ... | un rl | ... | arn |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| x n+m | b m | un m1 | un m2 | ... | un ml | ... | un mn |
| F(x)max | F 0 | -c 1 | -c 2 | ... | -c 1 | ... | -c n |
Al treilea pas. În al treilea pas, recalculăm întregul tabel simplex folosind formule speciale;
Al patrulea pas. Dacă după recalculare au rămas elemente negative în coloana de termeni liberi, atunci treceți la primul pas, dacă nu există, apoi la a cincea;
Al cincilea pas. Dacă ați ajuns la al cincilea pas, atunci ați găsit o soluție acceptabilă. Cu toate acestea, acest lucru nu înseamnă că este optim. Va fi optim numai dacă toate elementele din șirul F sunt pozitive. Dacă nu este cazul, atunci este necesar să îmbunătățim soluția, pentru care găsim rândul și coloana de început pentru următoarea recalculare folosind următorul algoritm. Inițial, găsim numărul minim negativ în șirul F, excluzând valoarea funcției. Coloana cu acest număr va fi prima. Pentru a găsi rândul de început, găsim raportul dintre termenul liber corespunzător și elementul din coloana de început, cu condiția ca acestea să fie pozitive. Raportul minim vă va permite să determinați linia de conducere. Recalculam din nou tabelul folosind formulele, i.e. treceți la pasul 3.
| - | x 1 | + | x 2 | - | S 1 | = | 1 | ||||||||||
| x 1 | +3 | x 2 | + | S 2 | = | 15 | |||||||||||
| - | 2 | x 1 | + | x 2 | + | S 3 | = | 4 |
| - | x 1 | + | x 2 | - | S 1 | + | R 1 | = | 1 | |||||||||||
| x 1 | +3 | x 2 | + | S 2 | = | 15 | ||||||||||||||
| - | 2 | x 1 | + | x 2 | + | S 3 | = | 4 |
| x 1 = 0 x 2 = 0 S 1 = 0 S 2 = 15 S 3 = 4 R 1 = 1 |
=> W = 1 |
| x 1 | x 2 | S 1 | S 2 | S 3 | R 1 | Sf. membru | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | 1: 1 = 1 |
| 1 | 3 | 0 | 1 | 0 | 0 | 15 | 15: 3 = 5 |
| -2 | 1 | 0 | 0 | 1 | 0 | 4 | 4: 1 = 4 |
| 1 | -1 | 1 | 0 | 0 | 0 | W - 1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | |
| 4 | 0 | 3 | 1 | 0 | -3 | 12 | |
| -1 | 0 | 1 | 0 | 1 | -1 | 3 | |
| 0 | 0 | 0 | 0 | 0 | 1 | W - 0 |
| - | x 1 | + | x 2 | - | S 1 | = | 1 | ||||||||||
| 4 | x 1 | + | 3 | S 1 | + | S 2 | = | 12 | |||||||||
| - | x 1 | + | S 1 | + | S 3 | = | 3 |
| x 1 | x 2 | S 1 | S 2 | S 3 | Sf. membru | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 4 | 0 | 3 | 1 | 0 | 12 | 12: 4 = 3 |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F - 1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F - 1 | |
| 0 | 1 | -1/4 | 1/4 | 0 | 4 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| 0 | 0 | 7/4 | 1/4 | 1 | 6 | |
| 0 | 0 | -2 | -1 | 0 | F - 13 |
| S 1 = 0 S 2 = 0 x 1 = 3 x 2 = 4 S 3 = 6 |
=> F - 13 = 0 => F = 13 |
