Metodă dual simplă.
Sentimentul metodei simplex simple constă în faptul că în locul problemei directe, dublul este rezolvat folosind metoda simplificată obișnuită.
Apoi, prin soluționarea problemei duble, se găsește o soluție optimă a liniei drepte. Pentru aceasta, se stabilește o corespondență unu-la-unu între variabilele liniei și problema dublă. Variabilele inițiale ale problemei directe sunt asociate cu variabile suplimentare duale, iar variabilele suplimentare ale problemei originale sunt mapate în variabilele inițiale ale problemei liniei.
Să presupunem că problema dublă este rezolvată și se obține o tabelă simplă optimă. Soluția optimă a problemei directe este determinată de coeficienții liniei F. Variabilele problemei directe sunt asimilate coeficienților pentru variabilele non-bază corespunzătoare din rândul F al tabelului simpl optim al problemei duale. Variabilele rămase sunt zero. Este foarte util să aplicăm metoda dual simplă în cazul în care numărul de constrângeri ale problemei directe este mult mai mare decât numărul de necunoscute și, de asemenea, în probleme de programare întreg.
Exemplul 1. Aplicând metoda dual simplă, rezolvați următoarea problemă:
Reducem inegalitățile problemei la semn ≥, înmulțind constrângerile 1, 2 și 4 cu (-1); atunci modelul problemei duale va avea forma:
Soluția corespunzătoare tabelului. 2, este optimă. Să scriem corespondența dintre variabilele liniei și problema dublă. Dacă constrângerile problemei directe conduc la forma egalității, atunci x3 va apărea ca și altele suplimentare. x4. x5. x6.
În linia F există coeficienți pentru variabilele non-variație y1. y2. Y5. Y4. Să găsim soluția optimă a problemei directe:
Variabila x5. corespunzătoare y3. și x2. corespunzător y6. sunt egale cu zero.
min F (y) = max F (x) = 6.
Astfel, rezolvând una din două probleme duble prin metoda simplex, obținem automat soluția celuilalt.
Articole similare
Trimiteți-le prietenilor: