Metodă duală online. Metoda simplex pentru rezolvarea problemelor
Pagina 1
Metoda dual simplex nu face decât să schimbe ordinea în care se găsește elementul de rezolvare, astfel încât toate caracteristicile (incoerența sistemului, funcționalitate nelimitată) au aici aceleași caracteristici ca și în metoda simplex convențională. Vom lua în considerare doar depășirea degenerării, deoarece este cauzată de zero printre coeficienții rândului z și nu printre termenii liberi.
Metoda dual simplex începe cu o soluție dual fezabilă și o menține dual valabilă pe parcursul tuturor pașilor. Metoda dual simplex este implementată folosind aceleași tabele ca și metoda simplex direct. În primul rând, se determină ce variabilă trebuie eliminată din bază și apoi care ar trebui introdusă în bază. Metoda dual simplex pentru problema de minimizare constă din următorii pași.
Metoda dual simplex, ca și metoda simplex, este folosită pentru a găsi o soluție la problemă programare liniară, scrisă sub forma problemei principale, pentru care printre vectorii P /, compuși din coeficienți pentru necunoscute în sistemul de ecuații, se numără m uni.
Este convenabil să rezolvați probleme folosind metoda dual simplex folosind excepții modificate programare cu numere întregi(vezi cap.
Folosind metoda dual simplex, s-a obținut nu în trei pași, ci în doi.
Folosind metoda dual simplex, se găsește o soluție la problema rezultată din adăugarea unei constrângeri suplimentare.
Folosind metoda dual simplex, ei găsesc o soluție la problema rezultată din problema (32) - (34) ca urmare a adăugării unei constrângeri suplimentare.
Există, de asemenea, o metodă duală simplex, care este concepută pentru a rezolva probleme cu un numar mare constrângeri sau sarcini în care numărul de constrângeri crește. În plus, există metode rezolvarea problemelor cu modificarea parametrilor, când nu se adaugă neapărat numai rânduri sau numai coloane.
Aplicarea metodei dual simplex la o problemă de programare liniară poate întâmpina dificultăți dacă problema este degenerată. Geometric asta înseamnă că aceleasi valori funcție obiectivă sunt realizate la mai mult de un vârf al poliedrului dual de condiții.
Utilizarea metodei dual simplex pentru a rezolva o problemă de programare liniară este echivalentă cu utilizarea metodei simplex obișnuite pentru a rezolva problema duală corespunzătoare.
Să folosim metoda standard dual simplex pentru a rezolva problema de maximizare și a obține sistemul dorit de prețuri optime.
În metoda dual simplex, rezolvarea problemei se realizează în următoarea succesiune: mai întâi, coeficienții rândului z sunt nenegativi, iar apoi termenii liberi sunt nenegativi. Este necesar să se justifice regula de alegere a unui element de rezolvare pentru această comandă.
Dacă se folosește metoda dual simplex, atunci avem nevoie, având un y dual admisibil, să obținem o inegalitate pe care curentul y nu o satisface. Astfel, calculul constă din două părți. A doua parte este calculele auxiliare ale inegalităților (generate) utilizate în prima parte. Dacă utilizați curentul Y în graficul H (G, m), y), puteți găsi calea cea mai scurtă de la 0 la g0 de lungime yt Yo - Atunci inegalitatea yt To nu este valabilă. Această inegalitate se adaugă inegalităților primei părți. Inegalitatea trebuie modificată înainte de a o scrie la sfârșitul tabelului dual simplex.
Constă în construirea unui plan optim inacceptabil și apoi transformarea lui într-unul acceptabil fără a încălca optimitatea.
Algoritm pentru metoda dual simplex
1) selectați linia de rezoluție în funcție de cea mai mare valoare absolută elementul negativ al coloanei termeni liberi;
2) selectați coloana de rezoluție în funcție de cel mai mic raport de valoare absolută dintre elementele L ale rândului și elementele negative ale rândului de rezoluție;
3) recalculați tabelul simplex după regulile metodei simplex obișnuite;
4) se verifică optimitatea soluției. Un semn al obținerii unei soluții optime admisibile este absența elementelor negative în coloana cu membri liberi.
Note
1. Dacă nu există un singur element negativ în linia de rezoluție, problema este de nerezolvat.
2. Dacă constrângerile problemei sunt specificate prin inegalități de tip „≥”, metoda dual simplex elimină necesitatea introducerii variabilelor artificiale.
Exemplu. Rezolvați problema folosind algoritmul metodei dual simplex
L = x 1 + 4x 2 → min
Compilăm tabelul simplex inițial.
| Baz. | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | Sf. |
| x 4 | -2 | -3 | 1 | 0 | 0 | 0 | -20 | |
| x 5 | -5 | 1 | -2 | 0 | 1 | 0 | 0 | -12 |
| x 6 | 1 | 2 | -1 | 0 | 0 | 1 | 0 | 2 |
| x 7 | -1 | 4 | -2 | 0 | 0 | 0 | 1 | 1 |
| L | -1 | -4 | -1 | 0 | 0 | 0 | 0 | 0 |
Absența pe linia L evaluări pozitive indică optimitatea soluției inițiale, iar prezența elementelor negative în coloana cu membri liberi indică inadmisibilitatea acesteia. Conform algoritmului metodei dual simplex, selectăm rândul de rezoluție în funcție de cel mai mare element negativ în valoare absolută al coloanei de elemente libere. În exemplul nostru, linia de activare este prima. Coloana de activare este selectată în conformitate cu regula stabilită în paragraful 2 al diagramei algoritmului. Elementul de rezoluție este (-4). După recalculare, obținem următorul tabel
| Baz. | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | Sf. |
| x 3 | 1 | 0 | 0 | 0 | 5 | |||
| x 5 | 0 | 1 | 0 | 0 | -2 | |||
| x 6 | 0 | 0 | 1 | 0 | 7 | |||
| x 7 | 0 | 0 | 0 | 0 | 1 | 11 | ||
| L | 0 | 0 | 0 | 0 | 5 |
Raționând în mod similar, obținem un alt tabel
| Baz. | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | Sf. |
| x 3 | 0 | 1 | 0 | 0 | ||||
| x 1 | 1 | 0 | 0 | 0 | ||||
| x 6 | 0 | 0 | 1 | 0 | ||||
| x 7 | 0 | 0 | 0 | 0 | 1 | 11 | ||
| L | 0 | 0 | 0 | 0 |
Absența elementelor negative în coloana de membri liberi indică faptul că soluție optimă , 
.
cometariu. Dacă Decizia PPPși este inacceptabilă și neoptimală, atunci obținem mai întâi o soluție admisibilă folosind algoritmul metodei simplex dual, iar apoi, conform regulilor metodei simplex obișnuite, obținem soluția optimă.
Exemplu.
L = 5x 1 – x 2 – x 3 → max 
sau 
Compilarea tabelului simplex inițial
| x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | Sf. | |
| x 4 | 0 | -2 | 1 | 0 | 0 | 0 | -9 | |
| x 5 | 1 | -1 | 0 | 0 | 1 | 0 | 0 | -1 |
| x 6 | -1 | -1 | 3 | 0 | 0 | 1 | 0 | -8 |
| x 7 | 1 | 0 | -1 | 0 | 0 | 0 | 1 | 4 |
| L | -5 | 1 | 4 | 0 | 0 | 0 | 0 | 0 |
Soluția este invalidă, deoarece coloana inactivă are elemente negative și este suboptimă deoarece rândul L are un scor negativ (-5). Obținem mai întâi o soluție fezabilă folosind algoritmul metodei dual simplex. După recalculare obținem următorul tabel simplex
| Baz. | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | Sf. |
| x 2 | 0 | 1 | 2 | -1 | 0 | 0 | 0 | 9 |
| x 5 | 1 | 0 | 2 | -1 | 1 | 0 | 0 | 8 |
| x 6 | -1 | 0 | 5 | -1 | 0 | 1 | 0 | 1 |
| x 7 | 0 | -1 | 0 | 0 | 0 | 1 | 4 | |
| L | -5 | 0 | 2 | 1 | 0 | 0 | 0 | -9 |
Nu există elemente negative în coloana termenilor liberi, dar în rândul L există un scor negativ (-5), ceea ce înseamnă că soluția este acceptabilă, nu optimă.
Folosim metoda simplex obișnuită și obținem următoarele tabele
| Baz. | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | Sf. |
| x 2 | 0 | 1 | 2 | -1 | 0 | 0 | 0 | 9 |
| x 5 | 0 | 0 | 3 | -1 | 1 | 0 | -1 | 4 |
| x 6 | 0 | 0 | -1 | 0 | 1 | 1 | 5 | |
| x 1 | 1 | 0 | -1 | 0 | 0 | 0 | 1 | 4 |
| L | 0 | 0 | -3 | 1 | 0 | 0 | 5 | 11 |
Sa luam in considerare metoda simplex pentru rezolvarea problemelor de programare liniară (LP). Se bazează pe trecerea de la un plan de referință la altul, timp în care valoarea funcției obiectiv crește.
Algoritmul metodei simplex este următorul:
- Traducem problema inițială în vedere canonică prin introducerea unor variabile suplimentare. Pentru inegalitățile de forma ≤, variabilele suplimentare se introduc cu semnul (+), dar dacă de forma ≥, atunci cu semnul (-). În funcția obiectiv sunt introduse variabile suplimentare cu semne corespunzătoare cu un coeficient egal cu 0 , deoarece funcția țintă nu trebuie să-și schimbe sensul economic.
- Vectorii sunt scrisi P i din coeficienții variabilelor și coloana termenilor liberi. Această acțiune determină numărul de vectori unitari. Regula este că ar trebui să existe atâția vectori unitari câte inegalități există în sistemul de constrângeri.
- După aceasta, datele sursă sunt introduse într-un tabel simplex. În bază sunt introduși vectori unitari, iar prin excluderea lor din bază se găsește soluția optimă. Coeficienții funcției obiectiv se scriu cu semnul opus.
- Un semn de optimitate pentru o problemă LP este că soluția este optimă dacă există f– în rând toți coeficienții sunt pozitivi. Regula pentru găsirea coloanei de activare - vizualizată f– un șir și dintre elementele sale negative este selectat cel mai mic. Vector P i conținutul său devine permisiv. Regula pentru selectarea unui element de rezoluție - sunt compilate rapoartele elementelor pozitive ale coloanei de rezolvare și elementele vectorului P 0 iar numărul care dă cel mai mic raport devine elementul de rezolvare în raport cu care va fi recalculat tabelul simplex. Linia care conține acest element se numește linie de activare. Dacă nu există elemente pozitive în coloana de rezoluție, atunci problema nu are soluție. După determinarea elementului de rezolvare, se procedează la recalcularea unui nou tabel simplex.
- Reguli pentru completarea unui nou tabel simplex. Unitatea este pusă în locul elementului de rezolvare și se presupune că celelalte elemente sunt egale 0 . Vectorul de rezoluție este adăugat la bază, din care vectorul zero corespunzător este exclus, iar vectorii de bază rămași sunt scrieți fără modificări. Elementele liniei de rezoluție sunt împărțite la elementul de rezoluție, iar elementele rămase sunt recalculate conform regulii dreptunghiului.
- Acest lucru se face până când f– toate elementele șirului nu vor deveni pozitive.
Să luăm în considerare rezolvarea problemei folosind algoritmul discutat mai sus.
Dat:
Aducem problema la forma canonică:
Compunem vectorii:
Completați tabelul simplex:
:
Să recalculăm primul element al vectorului P 0, pentru care facem un dreptunghi de numere: și obținem: 
.
Efectuăm calcule similare pentru toate celelalte elemente ale tabelului simplex:
În planul primit f– linia conține un element negativ – (-5/3), vector P 1. Acesta conține în coloana sa un singur element pozitiv, care va fi elementul de activare. Să recalculăm tabelul cu privire la acest element:
Fără elemente negative în f– linie înseamnă găsit plan optim:
F* = 36/5, X = (12/5, 14/5, 8, 0, 0).
- Ashmanov S. A. Programare liniară, M: Nauka, 1998,
- Ventzel E.S. Cercetare operațională, M: Radio sovietică, 2001,
- Kuznețov Yu.N., Kuzubov V.I., Voloșenko A.B. Programare matematică, M: facultate, 1986
Soluție de programare liniară personalizată
Puteți comanda orice teme din această disciplină pe site-ul nostru. Puteți atașa fișiere și specifica termenele limită la
Metoda dual simplex se bazează pe teoria dualității (vezi soluția problemei duale) și este folosit pentru a rezolva probleme de programare liniară, ai căror termeni liberi b i pot lua orice valoare, iar sistemul de restricții este specificat prin inegalități de semnificație „≤”, „≥” sau egalitatea „=”.Scopul serviciului. Calculator online folosit pentru rezolvarea problemelor de programare liniară P-metodaîn următoarele forme de înregistrare: forma de înregistrare de bază a metodei simplex, sub formă de tabel simplex, în metoda simplex modificată.
Instructiuni pentru rezolvarea problemelor metoda dual simplex. Selectați numărul de variabile și numărul de rânduri (numărul de constrângeri), faceți clic pe Următorul. Soluția rezultată este stocată în Fișier Word(vezi un exemplu de soluție folosind metoda dual simplex).
În același timp, restricții precum x i ≥ 0 nu iei in calcul.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 |
În metoda P, planul optim se obține prin deplasarea de-a lungul pseudoplanurilor. Pseudoplan- un plan în care sunt îndeplinite condițiile de optimitate, iar printre valorile variabilelor de bază x i se numără numere negative. Algoritm pentru metoda dual simplex include următorii pași:
- Întocmirea unui pseudo-plan. Sistemul de restricții problema initiala conduce la un sistem de inegalități care înseamnă „≤”.
- Verificarea optimității planului. Dacă condiția de optimitate nu este satisfăcută în planul de referință rezultat, atunci problema este rezolvată folosind metoda simplex.
- Selectarea rândului și coloanei de început. Dintre valorile negative ale variabilelor de bază, sunt selectate cele mai mari în valoare absolută. Linia corespunzătoare acestei valori este cea din frunte.
- Calculul unui nou plan de referință. Plan nou se obţine prin recalcularea tabelului simplex folosind metoda Jordan-Gauss. Apoi, treceți la etapa 2.
Exemplu. Compania trebuie să producă unități A1, unități A2 și unități A3 conform planului de producție. Fiecare tip de produs poate fi produs pe două mașini.
Cum să distribuiți munca mașinilor astfel încât timpul total petrecut pentru executarea planului să fie minim? Sunt date matricea costurilor și resursele de timp ale fiecărei mașini. Notați modelul operației studiate într-o formă care să permită utilizarea metodei P.
Se știe că conținutul de n nutrienți A, B și C din dietă ar trebui să fie de cel puțin m1, m2, respectiv m3 unități. Trei tipuri de alimente conțin acești nutrienți. Conținutul de unități nutritive într-un kilogram din fiecare tip de produs este prezentat în tabel. determina dieta zilnica care ofera cantitatea necesară nutrienți la costuri minime.
Sarcină: Rezolvați problema utilizând algoritmul metodei dual simplex.
Să reducem sistemul de restricții la sistemul de inegalități de sens ≤ prin înmulțirea dreptelor corespunzătoare cu (-1).
Să determinăm valoarea minimă a funcției obiectiv F(X) = 4x 1 + 2x 2 + x 3 în următoarele condiții de constrângere.
- x 1 - x 2 ≤-10
2x 1 + x 2 - x 3 ≤8
Pentru a construi primul plan de referință, reducem sistemul de inegalități la un sistem de ecuații prin introducerea de variabile suplimentare (tranziție la forma canonică).
În prima inegalitate de sens (≤), introducem variabila de bază x 4 . În a doua inegalitate de sens (≤), introducem variabila de bază x 5 .
-1x 1 -1x 2 + 0x 3 + 1x 4 + 0x 5 = -10
2x 1 + 1x 2 -1x 3 + 0x 4 + 1x 5 = 8
Matricea de coeficienți A = a(ij) a acestui sistem de ecuații are forma:
| A= |
|
x 4, x 5,
Presupunând că variabilele libere sunt egale cu zero, obținem primul proiect de referință:
X1 = (0,0,0,-10,8)
| Bază | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 4 | -10 | -1 | -1 | 0 | 1 | 0 |
| x 5 | 8 | 2 | 1 | -1 | 0 | 1 |
| F(X0) | 0 | -4 | -2 | -1 | 0 | 0 |
Iterația #1
Planul 0 in tabel simplex este un pseudoplan, așa că determinăm rândul și coloana de început.
Linia principală va fi prima linie, iar variabila x 4 ar trebui derivată din bază.
3. Definirea unei noi variabile de bază. Valoarea minimaθ corespunde coloanei a 2-a, adică. variabila x 2 trebuie introdusă în bază.
| Bază | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 4 | -10 | -1 | -1 | 0 | 1 | 0 |
| x 5 | 8 | 2 | 1 | -1 | 0 | 1 |
| F(X0) | 0 | -4 | -2 | -1 | 0 | 0 |
| θ | 0 | -4: (-1) = 4 | -2: (-1) = 2 | - | - | - |
4. Recalcularea tabelului simplex. Efectuăm transformări ale tabelului simplex folosind metoda Jordano-Gauss.
| Bază | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 2 | 10 | 1 | 1 | 0 | -1 | 0 |
| x 5 | -2 | 1 | 0 | -1 | 1 | 1 |
| F(X0) | 20 | -2 | 0 | -1 | -2 | 0 |
Să prezentăm calculul fiecărui element sub forma unui tabel:
| B | x 1 | x 2 | x 3 | x 4 | x 5 |
| -10: -1 | -1: -1 | -1: -1 | 0: -1 | 1: -1 | 0: -1 |
| 8-(-10 1):-1 | 2-(-1 1):-1 | 1-(-1 1):-1 | -1-(0 1):-1 | 0-(1 1):-1 | 1-(0 1):-1 |
| 0-(-10 -2):-1 | -4-(-1 -2):-1 | -2-(-1 -2):-1 | -1-(0 -2):-1 | 0-(1 -2):-1 | 0-(0 -2):-1 |
Iterația #2
1. Verificarea criteriului de optimitate.
Planul 1 dintr-un tabel simplex este un pseudo-plan, așa că determinăm rândul și coloana de început.
2. Definirea unei noi variabile libere.
Dintre valorile negative ale variabilelor de bază, o selectăm pe cea mai mare în valoare absolută.
A doua linie va fi lider, iar variabila x 5 ar trebui derivată din bază.
3. Definirea unei noi variabile de bază. Valoarea minimă a lui θ corespunde celei de-a treia coloane, adică. variabila x 3 trebuie introdusă în bază.
La intersecția rândului și coloanei principale există un element de rezoluție (RE) egal cu (-1).
| Bază | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 2 | 10 | 1 | 1 | 0 | -1 | 0 |
| x 5 | -2 | 1 | 0 | -1 | 1 | 1 |
| F(X0) | 20 | -2 | 0 | -1 | -2 | 0 |
| θ | 0 | - | - | -1: (-1) = 1 | - | - |
4. Recalcularea tabelului simplex. Efectuăm transformări.
| Bază | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 2 | 10 | 1 | 1 | 0 | -1 | 0 |
| x 3 | 2 | -1 | 0 | 1 | -1 | -1 |
| F(X1) | 22 | -3 | 0 | 0 | -3 | -1 |
| B | x 1 | x 2 | x 3 | x 4 | x 5 |
| 10-(-2 0):-1 | 1-(1 0):-1 | 1-(0 0):-1 | 0-(-1 0):-1 | -1-(1 0):-1 | 0-(1 0):-1 |
| -2: -1 | 1: -1 | 0: -1 | -1: -1 | 1: -1 | 1: -1 |
| 20-(-2 -1):-1 | -2-(1 -1):-1 | 0-(0 -1):-1 | -1-(-1 -1):-1 | -2-(1 -1):-1 | 0-(1 -1):-1 |
În coloana de bază, toate elementele sunt pozitive. Să trecem la algoritmul principal al metodei simplex.
Iterația #3
1. Verificarea criteriului de optimitate.
Nu există valori pozitive printre valorile șirului de index. Prin urmare, acest tabel determină planul optim pentru problemă.
| Bază | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 2 | 10 | 1 | 1 | 0 | -1 | 0 |
| x 3 | 2 | -1 | 0 | 1 | -1 | -1 |
| F(X1) | 22 | -3 | 0 | 0 | -3 | -1 |
Planul optim poate fi scris astfel: x 1 = 0, x 2 = 10, x 3 = 2
F(X) = 2 10 + 1 2 = 22
Deci, treceri succesive de la unul bază conjugată altuia îl efectuează până când obțin o soluție a problemei sau stabilesc insolubilitatea acesteia. Fiecare tranziție de la un pseudoplan la altul este o iterație (un pas).
Fiecare iterație conține două etape. În prima etapă, ei află dacă pseudo-planul este plan optim problemă directă, iar dacă nu, atunci dacă problema este rezolvabilă. Pentru a face acest lucru, este necesar să se calculeze și să se stabilească semnele acestora. A doua etapă este implementarea transformare elementară- (o iterație) metoda excluderii complete Jordan-Gauss, conducând la un nou pseudo-plan cu o valoare mai mică a funcției obiectiv.
Descrierea algoritmului. Problema LP trebuie specificată în forma canonică (1.1), (1.2) sau redusă la ea. Căuta bază conjugată dubla problema
si desemneaza-l 
. Să extindem A 0 în vectorii de bază A i1 ,.,A іm în conformitate cu (1.9) și să găsim pseudoplanul 
sarcină directă.
Să explorăm semnele (x i0). Dacă apare cazul, atunci pseudoplanul inițial este plan optim sarcină directă. Dacă există componente negative (x i0), calculăm coeficienții descompuneri vectoriale A j prin vectori bază conjugată(х ij) în conformitate cu (1.8).
Dacă pentru un r astfel încât x r0<0 , все то задача не разрешима (второй случай), и на этом процесс вычислений заканчивается.
Dacă apare al treilea caz (adică pentru fiecare r astfel încât x r0<0 , по крайней мере одна из компонент х rj <0 ), то переходим к второму этапу. С этой целью составляют таблицу k -й итерации (аналогичную tabel simplex), care constă din (m+2) rânduri și (n+1) coloană (Tabelul 6.1).
Coloana B x a tabelului, ca de obicei, conține vectorii (A i) ai bazei pseudoplanului xk, iar coloana A 0 - componentele de bază ale pseudoplanului (x i0 (k)). Linia indicelui (m+1) este umplută cu parametrii care sunt estimări ale vectorilor A j:
valoare - valoarea funcției obiectiv pentru un pseudoplan
Iterația k este finalizată prin completarea părții principale a tabelului (de la primul la (m+1) rândurile al-lea).
| C | C 1 | C 2 | . | Cj | . | Cn | ||
| Bx | A 0 | A 1 | A 2 | . | A j | . | A n | |
| C 1 | X 1 | X 10 | X 11 | X 12 | . | X 1j | . | X 1n |
| C 2 | X 2 | X 20 | X 21 | X 22 | . | X 2j | . | X2n |
| . | . | . | . | . | . | . | . | . |
| C i | X i | Xi0 | Xi1 | Xi2 | . | X ij | . | Xin |
| . | . | . | . | . | . | . | . | . |
| Cm | Xm | X m0 | X m1 | X m2 | . | X mj | . | X mn |
| . | . | |||||||
| . | . |
În prima etapă (k+1) - iar iterațiile află dacă apare primul, al doilea sau al treilea caz.
În al treilea caz, trecem la a doua etapă. În primul rând, se determină vectorul A r, care trebuie derivat din bază. Indicele său r este determinat din condiție
Doar acele poziții pentru care x rj sunt completate în linie<0 . Вектор А l , который должен быть введен в базис, находят из условия
După ce s-au determinat rândul de ghidare r și coloana l, elementele părții principale a tabelului a (k+1)-a iterație sunt calculate folosind relații de recurență
 |
(1.15) |
Unde x ri este elementul de ghidare a transformării.
Schema de calcul a algoritmului metoda dual simplex similar cu schema de calcul a metodei simplex. Formele tabelelor sunt similare.
Diferența dintre metode este că prin metoda simplex se face o tranziție secvențială de la o soluție de bază fezabilă (plan de referință) a problemei la alta și cu metoda simplă duală- trecerea de la un pseudoplan la altul.
Diferența formală dintre schemele de calcul ale acestor metode se manifestă numai în regulile de tranziție de la o bază la alta, precum și în semnele de optimitate și insolubilitate ale problemei. În metoda simplex, se determină mai întâi vectorul introdus în bază, apoi se determină vectorul exclus din bază, iar în metoda dual simplex această ordine este inversă.
Să notăm câteva proprietăți importante metoda dual simplex.
Spre deosebire de direct
