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, la rezolvarea unei probleme directe 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 diferență .
Având în vedere această condiție ținând cont de dualitate, putem scrie
.
Astfel, dacă, Acea . 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. Variabila cea mai mare este selectată ca variabilă exclusă. valoare absolută variabilă de bază negativă (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ă.
Condiție 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 care urmează să fie incluse în bază și excluse, pentru a obține următoarea soluție, se efectuează operația obișnuită de conversie a rândurilor unui tabel 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ția 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ția X 4 - ecuație |
|||||
|
atitudine |
Dacă enunțul problemei conține restricții cu semnul ≥, atunci acestea pot fi reduse la forma ∑a ji b j prin înmulțirea ambelor părți ale inegalității cu -1. Să introducem m variabile suplimentare x n+j ≥0(j =1,m) și să transformăm restricțiile în formă de egalități
(2)
Să presupunem că toate variabilele inițiale ale problemei x 1 , x 2 ,..., x n sunt nebazice. Atunci variabilele suplimentare vor fi de bază, iar o anumită soluție a sistemului de constrângeri are forma
x 1 = x 2 = ... = x n = 0, x n+ j = b j , j =1,m. (3)
Deoarece în acest caz valoarea funcției obiectiv F 0 = 0, putem reprezenta F(x) după cum urmează:
F(x)=∑c i x i +F 0 =0 (4)
Tabelul simplex inițial (tabelul simplex 1) este compilat pe baza ecuațiilor (2) și (4). Dacă variabilele suplimentare x n+j sunt precedate de semnul „+”, ca în (2), atunci toți coeficienții din fața variabilelor x i și termenul liber b j sunt introduși în tabelul simplex fără modificări. La maximizarea funcției de obiectiv, coeficienții sunt introduși în rândul de jos al tabelului simplex cu semne opuse. Termenii liberi din tabelul simplex determină soluția problemei.
Algoritmul de rezolvare a problemei este următorul:
primul pas. Membrii coloanei de membri liberi sunt vizualizați. Dacă toate sunt pozitive, atunci a fost găsită o soluție de bază admisibilă și trebuie să treceți la pasul 5 al algoritmului, care corespunde găsirii soluției optime. Dacă tabelul inițial simplex are termeni liberi negativi, atunci soluția nu este validă și ar trebui să treceți la pasul 2.
al 2-lea pas. Pentru a găsi o soluție admisibilă, se efectuează și este necesar să se decidă care dintre variabilele nebazice să includă în bază și ce variabilă să se elimine din 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 |
Pentru a face acest lucru, alegeți oricare dintre elemente negative coloană de termeni liberi (fie acesta să fie b 2 conducător sau rezolvător. Dacă nu există elemente negative în rândul cu un termen liber negativ, atunci sistemul de constrângeri este inconsecvent și problema nu are soluție.
În același timp, variabila care este prima care își schimbă semnul atunci când NP x l selectat crește este exclusă din BP. Acesta va fi x n+r, al cărui indice r este determinat din condiție
acestea. variabila care are cel mai mic raport dintre termenul liber și elementul coloanei principale selectate. Această relație se numește relație simplex. Trebuie luate în considerare numai relațiile simplex pozitive.
Se numește linia corespunzătoare variabilei x n+r conduce sau permite. Elementul tabelului simplex a rl, situat la intersecția rândului principal și a coloanei principale, se numește element de conducere sau de rezoluție. Găsirea elementului conducător încheie munca cu fiecare tabel simplex obișnuit.
al 3-lea pas. Se calculează un nou tabel simplex, ale cărui elemente sunt recalculate din elementele tabelului simplex din pasul precedent și sunt marcate cu un prim, i.e. b" j , a " ji , c " i , F" 0 . Elementele sunt recalculate folosind următoarele formule:
Mai întâi, noul tabel simplex va completa rândul și coloana care conduceau în tabelul simplex anterior. Expresia (5) înseamnă că elementul a" rl în locul elementului conducător este egal cu reciproca elementului din tabelul simplex anterior. Elementele rândului a ri sunt împărțite la elementul conducător, iar elementele coloana a jl sunt, de asemenea, împărțite la elementul conducător, dar sunt luate din semnul opus. Elementele b" r și c" l se calculează după același principiu.
Restul formulelor pot fi scrise cu ușurință folosind .
Dreptunghiul este construit conform vechiului tabel simplex în așa fel încât una dintre diagonalele sale să fie formată din elementele recalculate (a ji) și conducătoare (a rl) (Fig. 1). A doua diagonală este determinată în mod unic. Pentru a găsi un nou element a" ji, produsul dintre elementele diagonalei opuse împărțit la elementul principal este scăzut din elementul a ji (acesta este indicat de semnul „-” de lângă celulă). Elementele b" j, (j≠r) și c" i sunt recalculate în același mod. (i≠l).
al 4-lea pas. Analiza noului tabel simplex începe cu primul pas al algoritmului. Acțiunea continuă până când se găsește o soluție de bază fezabilă, de ex. toate elementele coloanei flotante trebuie să fie pozitive.
al 5-lea pas. Considerăm că a fost găsită o soluție de bază admisibilă. Ne uităm la coeficienții dreptei funcției obiectiv F(x) . Un semn al optimității unui tabel simplex este nenegativitatea coeficienților pentru variabilele nebazice din rândul F.
Orez. 1. Regula dreptunghiulară
Dacă printre coeficienții rândului F există și negativi (cu excepția termenului liber), atunci trebuie să treceți la o altă soluție de bază. La maximizarea funcției obiectiv, baza include una dintre variabilele nebaze (de exemplu x l), a cărei coloană corespunde valorii absolute maxime a coeficientului negativ c l din rândul de jos al tabelului simplex. Acest lucru vă permite să selectați variabila a cărei creștere duce la o îmbunătățire a funcției de obiectiv. Coloana corespunzătoare variabilei x l se numește coloană principală. În același timp, acea variabilă x n+r este exclusă din bază, al cărei indice r este determinat de relația simplex minimă:
Rândul corespunzător lui x n+r se numește lider, iar elementul tabelului simplex a rl, care se află la intersecția rândului principal și coloanei principale, se numește element conducător.
al 6-lea pas. conform regulilor prezentate la pasul 3. Procedura continuă până când se găsește o soluție optimă sau se ajunge la concluzia că aceasta nu există.
În timpul optimizării soluției, dacă toate elementele din coloana principală sunt nepozitive, atunci rândul principal nu poate fi selectat. În acest caz, funcția din regiunea soluțiilor fezabile ale problemei nu este mărginită mai sus și F max ->&∞.
Dacă, la următorul pas de căutare a unui extremum, una dintre variabilele de bază devine egală cu zero, atunci soluția de bază corespunzătoare se numește degenerată. În acest caz, are loc o așa-numită ciclizare, caracterizată prin faptul că aceeași combinație de BP începe să se repete cu o anumită frecvență (valoarea funcției F este păstrată) și este imposibil să treci la o nouă soluție de bază fezabilă. . Loopingul este unul dintre principalele dezavantaje ale metodei simplex, dar este relativ rar. În practică, în astfel de cazuri, de obicei refuză să introducă în bază variabila a cărei coloană corespunde valorii absolute maxime a coeficientului negativ din funcția de obiectiv și selectează aleatoriu o nouă soluție de bază.
Exemplul 1. Rezolvați problema
max(F(x) = -2x 1 + 5x 2 | 2x 1 + x 2 ≤7; x 1 + 4x 2 ≥8; x 2 ≤4; x 1,2 ≥0)
Folosind metoda simplex și dați o interpretare geometrică a procesului de rezolvare.
O interpretare grafică a soluției problemei este prezentată în Fig. 2. Valoarea maximă a funcției obiectiv se realizează la vârful ODZP cu coordonatele . Să rezolvăm problema folosind tabele simplex. Să înmulțim a doua constrângere cu (-1) și să introducem variabile suplimentare pentru a aduce inegalitățile sub formă de egalități, apoi
Luăm variabilele inițiale x 1 și x 2 ca nebaze și considerăm x 3, x 4 și x 5 suplimentare ca fiind de bază și compunem un tabel simplex (tabelul simplex 2). Soluția corespunzătoare tabelului simplex. 2, nu este valabil; elementul conducător este conturat și selectat în conformitate cu pasul 2 al algoritmului anterior. Următorul tabel simplex. 3 definește o soluție de bază admisibilă, vârful ODZP din Fig. 1 îi corespunde. 2 Elementul de conducere este conturat și selectat în conformitate cu pasul 5 al algoritmului de rezolvare a problemelor. Masa 4 corespunde soluției optime a problemei, deci: x 1 = x 5 = 0; x 2 = 4; x 3 = 3; x 4 = 8; F max = 20.
Orez. 2. Soluție grafică sarcini
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 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. 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 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 rând index mai putin de 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 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 despre care 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 î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, 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.
Dacă ați înțeles deja metoda grafică de rezolvare a problemelor de programare liniară, este timpul să treceți la metoda simplex. Spre deosebire de primul, practic nu are restricții asupra problemei (orice număr de variabile, semne diferite etc.) și se modifică în funcție de tipul problemei (de exemplu, metoda M sau metoda bazei artificiale).
Când se rezolvă o problemă folosind metoda simplex, calculele sunt de obicei efectuate (pentru compactitate și claritate) în tabele (metoda simplex tabelar), iar ultimul tabel cu soluția optimă conține informații suplimentare importante: soluția problemei duale, resursele rămase , informații despre resursele limitate etc. , care permite o analiză economică a unei probleme de programare liniară (vezi exemplul 3 de mai jos).
Exemple de soluții la probleme folosind metoda simplex sunt postate gratuit pentru confortul dvs. - studiați, căutați altele similare, rezolvați. Dacă aveți nevoie de ajutor cu sarcini ca aceasta, accesați: Soluție de programare liniară personalizată.
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ță ar putea 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ă?
Întocmirea unui model matematic și rezolvarea ZLP folosind metoda simplex (pdf, 33 Kb)
Sarcina 2. Rezolvați o problemă de programare liniară folosind metoda simplex. 
Soluție folosind metoda simplex pe bază artificială (pdf, 45 Kb)
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.
- Câte articole de fiecare tip trebuie produse pentru a maximiza profitul?
- Determinați starea fiecărui tip de materie primă și valoarea sa specifică.
- 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.
- 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).
- 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.
Rezolvarea unei probleme de programare liniară cu analiză economică (pdf, 163 Kb)
Sarcina 4. Rezolvați o problemă de programare liniară folosind metoda simplex: 
Rezolvare folosind metoda tabelar simplex cu căutarea planului de referință (pdf, 44 Kb)
Sarcina 5. Rezolvați o problemă de programare liniară folosind metoda simplex: 
Rezolvare folosind metoda tabulară simplex (pdf, 47 Kb)
Sarcina 6. Rezolvați problema folosind metoda simplex, considerând ca plan de referință inițial planul dat în condiția: 
Rezolvare prin metoda manuală simplex (pdf, 60 Kb)
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.
Soluție folosind metoda simplex modificată (pdf, 67 Kb)
Sarcina 8. Găsiți soluția optimă folosind metoda dual simplex 
Soluție folosind metoda dual simplex (pdf, 43 Kb)
Exemple de soluții la probleme de programare liniară
Metode de rezolvare a problemelor de programare liniară
Soluții de referință la o problemă de programare liniară
Să fie dată o problemă de programare liniară în notație canonică
in conditii
Vom nota prin setul de soluții sisteme (2) – (3). Să presupunem că , unde este rangul matricei și este numărul de ecuații din sistemul (2).
Din sistemul de vectori coloană ai matricei, selectăm un subsistem de vectori liniar independent. Există pentru că . Acest sistem formează o bază în . Să notăm cu , . Hai sa sunăm set de valori de bază index, - submatrice de bază matrici Vom numi coordonatele vectorului de bază , dacă nebază in caz contrar.
Să scriem sistemul (2) sub forma . Să împărțim termenii din partea stângă în de bază și nebază, adică
Să definim o soluție particulară a acestui sistem după cum urmează. Să setăm toate variabilele non-bazice egale cu zero în (4). Apoi sistemul (4) va lua forma
Să sunăm (5) subsistem de bază sistem de ecuații (2). Să notăm cu un vector compus din coordonatele de bază ale vectorului . Apoi sistemul (2) poate fi rescris sub formă de matrice vectorială
Deoarece submatricea este de bază, aceasta
nedegenerat. Prin urmare, sistemul (6) are o soluție unică. Se va numi soluția particulară a sistemului (2) obținută în acest fel soluție de referință problema de programare liniară directă corespunzătoare bazei. (Uneori soluția de referință este numită și de bază ). După cum putem vedea, baza corespunde unei singure soluții de suport. Evident, numărul de soluții de suport este finit.
Pentru această bază, determinăm și soluția de referință pentru problema de programare liniară duală. Amintiți-vă că problema duală cu cea canonică are forma
in conditii
Să scriem sistemul (8) sub forma
Reamintim că setul de soluții ale sistemului (8) este notat cu .
Să definim vectorul variabilelor duale din condiția îndeplinirii constrângerilor de bază din sistemul (9) ca egalități. Obținem următorul sistem ecuatii lineare:
Să notăm printr-un vector compus din ba-
coordonatele zis ale vectorului. Apoi sistemul (10) poate fi rescris sub formă de matrice vectorială
Sistemul (11) are și o soluție unică.
Să-l sunăm de sprijin (de bază )decizie problema de programare liniară duală corespunzătoare bazei. Această soluție de referință este, de asemenea, determinată în mod unic.
Deci, orice bază corespunde la doi vectori - două soluții suport și, respectiv, probleme de programare liniară directă și duală.
Să definim în continuare următoarele tipuri de baze și soluții de sprijin. Dacă toate coordonatele soluției suport sunt nenegative, atunci se numește baza căreia îi corespunde această soluție suport acceptabil plan de referință problema de programare liniară directă și se numește soluția de referință corespunzătoare aceleiași baze pseudoplan dubla problema. De fapt, pentru ca baza să fie admisibilă, este suficientă nenegativitatea coordonatelor bazei. Rețineți că planul de referință este un vector fezabil al problemei de programare liniară înainte ().
Dacă soluția de referință satisface toate restricțiile (9) ale problemei duale, atunci baza căreia îi corespunde această soluție de referință se numește dublu valabil . În acest caz, vectorul este numit plan de referință problema de programare liniară duală și soluția de referință corespunzătoare aceleiași baze
se numeste pseudoplan sarcină directă.
Pentru admisibilitatea dublă a unei baze, este suficient să se satisfacă numai inegalitățile nebazice. Rețineți că planul de referință este un vector fezabil al problemei de programare liniară duală ().
Notăm diferențele dintre laturile stânga și dreapta ale inegalităților (9) prin , . Apoi admisibilitatea duală a unui temei poate fi stabilită prin verificarea nenegativității tuturor . Rețineți că, după cum rezultă direct din definiție, toate reziduurile de bază sunt egale cu zero ().
Un exemplu de rezolvare a unei probleme directe și duale folosind metoda simplex
Prin urmare, este suficient să ne asigurăm că inegalitățile sunt valabile pentru toată lumea.
Teorema 1. LăsaȘi– soluții de referință ale problemei de programare liniară corespunzătoare unei anumite baze, atunci egalitatea este valabilă .
Dovada . Din definițiile soluțiilor suport se obține ușor egalitățile
deci urmează validitatea teoremei.
Teorema 2. (Criteriul de optimizare pentru soluțiile de suport) Dacă bazăeste simultan admisibil și dual admisibil, apoi soluțiile de sprijin corespunzătoareȘisunt soluții, respectiv, ale problemelor de programare liniară directă și duală.
Dovada. Valabilitatea acestei afirmații rezultă din teoria dualității în programarea liniară și din Teorema 1.
Teorema 3. O soluție admisibilă a problemei (1) – (3) este un plan de referință al problemei dacă și numai dacă este vârful unei mulțimi poliedrice convexe.
Dovada. Lăsa – planul de referință al problemei (1) – (3). Să demonstrăm asta – partea de sus a setului . Prin definiție, un plan de referință – soluţie de referinţă admisibilă corespunzătoare unei anumite baze, adică – rezolvarea unui sistem de ecuații liniare în raport cu variabile
Este ușor de observat că acest sistem are o soluție unică. Aceasta înseamnă că planul de sprijin al feței care conține punctul , are dimensiunea 0. Prin urmare, – partea de sus a setului .
Înapoi. Lăsa – partea de sus a setului. Să demonstrăm asta – planul de referință al problemei (1) – (3). Deoarece este un vârf, este o față a mulțimii a cărei dimensiune este zero. Prin urmare, vectorul există cel puțin zero componente, mulțimea ale căror numere o notăm . Prin urmare, – singura soluție pentru sistem
Unde . Prin urmare, rămâne de demonstrat că sistemul de vectori este liniar independent. Să presupunem contrariul. Apoi există numere care nu sunt toate egale cu zero, astfel încât . De aceea
Aceasta înseamnă că sistemul (12) are o soluție diferită de , ceea ce contrazice unicitatea soluției sale. Astfel, este baza și vectorul – planul de referință corespunzător problemei (1) – (3). Asta se cerea.
Rețineți că o soluție admisibilă la problema (7), (8) (problema duală (1) – (3)) este, de asemenea, un plan de sprijin dacă și numai dacă este vârful mulțimii admisibile.
Data publicării: 2015-01-10; Citește: 695 | Încălcarea drepturilor de autor ale paginii
Studopedia.org - Studopedia.Org - 2014-2018 (0,005 s)...
Pentru certitudine, presupunem că problema care se rezolvă este găsirea minimului.
1. Reduceți problema de programare liniară la formă canonică.
După introducerea suplimentară sistem variabil ecuațiile și o funcție liniară sunt scrise într-o formă numită sistem extins:
Presupunem că toate variabilele suplimentare au același semn ca și termenii liberi; altfel folosim așa-numitul M– o metodă care va fi discutată mai jos.
2. Definiți variabilele de bază și libere.
3. Introducem sistemul original extins în primul simplex - tabel. Ultimul rând al tabelului, care oferă ecuația pentru funcție liniară obiectivele sunt numite evaluare. Indică coeficienții funcției obiectiv. În coloana din stânga tabelului notăm principalele variabile (bază), în coloanele ulterioare notăm coeficienții pentru variabilele libere. Penultima coloană conține membri liberi ai sistemului extins. Ultima coloană este pregătită pentru relațiile de estimare necesare pentru determinarea variabilei de bază pe baza relației (6.29).
4. Determinați posibilitatea rezolvării problemei prin valori conform teoremelor 6.7,…, 6.9.
5. Selectați elementul de rezolvare (referință).
Rezolvarea unei probleme de producție folosind metoda simplex tabelar
Dacă nu este îndeplinit criteriul de optimitate (nu sunt îndeplinite condițiile teoremei 6.7 sau 6.8), atunci cel mai mare coeficient negativ absolut din ultimul rând determină coloana de rezoluție (referință) 
.
Compunem rapoartele estimate ale fiecărei linii conform următoarelor reguli:
1 0) dacă toate și au semne diferite;
2 0) dacă toate și ;
3 0) dacă ;
4 0) 0 dacă și ;
5 0) dacă și au aceleași semne.
Să definim. Dacă nu există un minim final, atunci problema nu are un optim final (). Dacă minimul este finit, atunci selectați linia q, pe care se realizează (oricare, dacă sunt mai multe), și numiți-o linia de rezolvare (de referință). La intersecția rândului și coloanei de rezolvare există un element de rezolvare (de referință).
6 0) Mergeți la următorul tabel conform regulilor:
a) în coloana din stânga scriem o nouă bază: în locul variabilei principale - o variabilă, i.e. Să schimbăm variabilele și ;
b) se pune 1 în locul elementului de susținere;
c) lăsați elementele tabelului inițial în locurile rămase ale rândului de referință din noul tabel;
d) în locurile rămase din coloana de referință, se pun elementele corespunzătoare din tabelul inițial, înmulțite cu –1;
d) pentru restul locuri libere elementele , , în noul tabel notează numerele , , , care se regăsesc astfel:
Pentru a simplifica calculele folosind aceste formule, acestea pot fi formulate ca „Reguli dreptunghiulare”(Fig. 6.8): se înmulțesc elementele de pe diagonalele unui dreptunghi cu vârfuri (sau , , , , sau , , , ) (produsul care nu conține elementul de susținere se ia cu semnul minus) și produsele rezultate sunt adăugat;
f) împărțiți toate elementele primite ale noului tabel la elementul de referință.
7 0) Folosind valoarea elementului, determinați dacă a fost găsită valoarea optimă a funcției obiectiv. Dacă răspunsul este negativ, continuați decizia (reveniți la punctul 6).
Orez. 6.8. Regula dreptunghiulară pentru determinarea numerelor:
a − , b − , c − .
Se are în vedere un algoritm de conversie a tabelelor simplex pentru soluții de bază admisibile nedegenerate, i.e. situaţia descrisă de Teorema 6.9 a fost îndeplinită. Dacă problema inițială de programare liniară este degenerată, atunci în cursul rezolvării ei folosind metoda simplex, pot apărea soluții de bază degenerate. În acest caz, pașii inactivi ai metodei simplex sunt posibili, de exemplu. iterații în care f(X) nu se schimba. De asemenea, este posibilă efectuarea în buclă, adică o succesiune nesfârșită de pași inactiv. Pentru a o preveni, au fost dezvoltați algoritmi speciali - anticicline. Cu toate acestea, în majoritatea covârșitoare a cazurilor, pașii inactivi sunt înlocuiți cu pași cu o scădere a funcției obiective, iar procesul de rezolvare este finalizat ca urmare a unui număr finit de iterații.
Exemplul 6.8. Rezolvați problema dată în exemplul 6.7 folosind metoda simplex.
⇐ Anterior45678910111213Următorul ⇒
Data publicării: 23-01-2015; Citește: 174 | Încălcarea drepturilor de autor ale paginii
Studopedia.org - Studopedia.Org - 2014-2018 (0,002 s)...
Acasă >> Exemplul nr. 3. Metoda simplex. Găsirea celei mai mari valori a unei funcții (bază artificială)
Metoda simplex
| — | x 1 | + | x 2 | ≥ | 1 | |
| x 1 | + | 3 | x 2 | ≤ | 15 | |
| — | 2 | x 1 | + | x 2 | ≤ | 4 |
| O variabilă se numește bază pentru o anumită ecuație dacă este inclusă în ecuația dată cu un coeficient de unu și nu este inclus în ecuațiile rămase (cu condiția ca în partea dreaptă a ecuației să existe un număr pozitiv). Dacă fiecare ecuație are o variabilă de bază, atunci se spune că sistemul are o bază. Ideea metodei simplex este de a trece de la o bază la alta, obținând o valoare a funcției care este cel puțin nu mai mică decât cea existentă (fiecărei baze îi corespunde o singură valoare a funcției). Cum se realizează trecerea de la o bază la alta? |
| 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 | 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 |
Nu există coeficienți pozitivi printre coeficienții rândului selectați. Prin urmare găsit cea mai mare valoare funcțiile F.
Răspuns:
x 1 = 3 x 2 = 4
F max = 13
Mergeți la soluția problemei dvs
© 2010-2018, pentru orice întrebări vă rugăm să scrieți la [email protected]
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 . Profit din vânzarea a trei grupe de mărfuri la 1 mie.
Metoda simplex pentru rezolvarea ZLP
freca. 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 întreprindere comercială a fost maximul.
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, 3 - grupele ei, respectiv. Apoi model matematic sarcina are forma:
F = 4 x 1 + 5 x 2 + 4 x 3 ->max
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
Calculam:
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
Calculam:
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ă se vinde primul tip de mărfuri în valoare de 40 de mii.
freca. 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
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; y5 = A2 = 1; y 6 = Δ 3 = 4;
Răspuns
y 1 = 0; y2 = 0; y 3 = 1; Z min = 160;
Metoda simplex este o procedură de calcul bazată pe principiul îmbunătățirii secvențiale a soluțiilor la trecerea de la un punct de bază (soluție de bază) la altul. În acest caz, valoarea funcției obiectiv se îmbunătățește.
Soluția de bază este una dintre soluțiile admisibile situate la vârfurile regiunii valorilor admisibile. Prin verificarea optimității vârf după vârf al simplexului, se ajunge la optimul dorit. Metoda simplex se bazează pe acest principiu.
Un simplex este un poligon convex în spațiu n-dimensional cu n+1 vârfuri care nu se află în același hiperplan (hiperplanul împarte spațiul în două semi-spații).
De exemplu, linia constrângerilor bugetare împarte bunurile în disponibile și indisponibile.
S-a dovedit că, dacă există o soluție optimă, atunci cu siguranță va fi găsită după un număr finit de iterații (pași), cu excepția cazurilor de „ciclare”.
Algoritmul metodei simplex constă dintr-un număr de etape.
Primul stagiu. Se construiește un model inițial de optimizare. În continuare, matricea originală de condiții este transformată în forma canonică redusă, care, printre toate celelalte forme canonice, se distinge prin faptul că:
a) partea dreaptă a condițiilor (termeni liberi bi) sunt cantități nenegative;
b) condiţiile în sine sunt egalităţi;
c) matricea de condiții conține o submatrice unitară completă.
Dacă termenii liberi sunt negativi, atunci ambele părți ale inegalității sunt înmulțite cu - 1, iar semnul inegalității este inversat. Pentru a transforma inegalitățile în egalități, se introduc variabile suplimentare, care indică de obicei cantitatea de resurse subutilizate. Acesta este sensul lor economic.
În sfârșit, dacă, după adăugarea unor variabile suplimentare, matricea de condiții nu conține o submatrice identită completă, atunci se introduc variabile artificiale care nu au niciun sens economic. Ele sunt introduse numai pentru a obține submatricea de identitate și pentru a începe procesul de rezolvare a problemei folosind metoda simplex.
Într-o soluție optimă a problemei, toate variabilele artificiale (AI) trebuie să fie egale cu zero. Pentru a face acest lucru, în funcția obiectiv a problemei sunt introduse variabile artificiale cu coeficienți negativi mari (-M) la rezolvarea problemei la max, și cu coeficienți pozitivi mari (+M) când problema este rezolvată la min. În acest caz, chiar și o valoare nesemnificativă diferită de zero a variabilei artificiale va scădea (mărește) brusc valoarea funcției obiectiv. De obicei, M ar trebui să fie de 1000 de ori mai mare decât valorile coeficienților pentru variabilele principale.
Faza a doua. Se construiește un tabel inițial simplex și se găsește o soluție de bază inițială. Setul de variabile care formează submatricea identității este luat ca soluție de bază inițială. Valorile acestor variabile sunt egale cu termenii liberi. Toate celelalte variabile în afara bazei sunt zero.
A treia etapă. Verificarea optimității soluției de bază se realizează folosind estimări speciale ale coeficienților funcției obiectiv. Dacă toate estimările coeficienților funcției obiectiv sunt negative sau egale cu zero, atunci soluția de bază existentă este optimă. Dacă cel puțin o estimare a coeficientului funcției obiectiv este mai mare decât zero, atunci soluția de bază existentă nu este optimă și trebuie îmbunătățită.
Etapa a patra. Trecerea la o nouă soluție de bază. Evident, planul optim ar trebui să includă o variabilă care mărește funcția obiectiv în cea mai mare măsură. La rezolvarea problemelor pentru profit maxim, planul optim include produse a căror producție este cea mai profitabilă. Aceasta este determinată de maxim valoare pozitivă estimarea coeficientului funcţiei obiectiv.
Coloana tabelului simplex cu acest număr la această iterație se numește coloana generală.
Pentru a găsi rândul general, toți membrii liberi (resurse) sunt împărțiți în elementele corespunzătoare ale coloanei generale (rata de consum de resurse pe unitate de produs). Cel mai mic este selectat din rezultatele obținute. Linia corespunzătoare la o iterație dată se numește linie generală. Ea corespunde resursei care limitează producția la o anumită iterație.
Un element al unui tabel simplex situat la intersecția unei coloane generale și a unui rând se numește element general.
Apoi toate elementele șirului general (inclusiv membrul liber) sunt împărțite în elementul general. Ca urmare a acestei operații, elementul general devine egal cu unu. În continuare, este necesar ca toate celelalte elemente ale coloanei generale să devină egale cu zero, adică. coloana generală ar trebui să devină unică. Toate liniile (cu excepția celei generale) sunt convertite după cum urmează. Elementele rezultate ale noului rând sunt înmulțite cu elementul corespunzător al coloanei generale și produsul rezultat este scăzut din elementele rândului vechi.
Obținem valorile noilor variabile de bază în celulele corespunzătoare ale coloanei de termeni liberi.
Etapa a cincea. Soluția de bază rezultată este verificată pentru optimitatea (vezi a treia etapă). Dacă este optim, atunci calculele se opresc. În caz contrar, este necesar să se găsească o nouă soluție de bază (etapa a patra), etc.
Metoda simplex
Un exemplu de rezolvare a problemelor de optimizare a programării liniare folosind metoda simplex
Să fie necesar să se găsească planul optim pentru producția a două tipuri de produse (x1 și x2).
Date inițiale:
Să construim un model de optimizare
– limitarea resurselor A;
– limitarea resurselor B.
Să reducem problema la forma canonică redusă. Pentru a face acest lucru, este suficient să introduceți variabile suplimentare X3 și X4. Ca urmare, inegalitățile sunt transformate în egalități stricte.
Să construim tabelul simplex inițial și să găsim soluția de bază inițială. Acestea vor fi variabile suplimentare, deoarece corespund unei submatrici de unitate.
Prima iterație. Găsiți coloana generală și rândul general:
Elementul general este 5.
a 2-a iterație. Soluția de bază găsită nu este optimă, deoarece linia de rating (Fj-Cj) conține un element pozitiv. Găsiți coloana generală și rândul general:
max(0,0,3,-1,4,0) = 0,2
Soluția găsită este optimă, din moment ce totul evaluări speciale funcţiile obiectiv Fj – Cj sunt egale cu zero sau negative. F(x)=29 x1=2; x2=5.
| - | 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 |