UVOD
Koncept dualiteta predstavlja jedno od najvažnijih otkrića u LP. Prema tom konceptu
svaki problem LP ima sa sobom povezan jedan drugi problem nazvan dual. Uzajamni odnosi
između originalnog problema i njegovog duala pokazuju se ekstremno značajnim, naročito u
analizi osjetljivosti.
Analiza osjetljivosti je važan dio gotovo svake studije LP, budući da je većina
vrijednosti parametara originalnog modela samo procjena budućih uvjeta. Pored toga,
određene vrijednosti parametara mogu predstavljati menadžerske odluke, a u tom slučaju
izbor vrijednosti parametara može biti ključni problem, koji treba obraditi kroz analizu
osjetljivosti.
Teorija dualiteta zasnovana je na analzi simpleks tablica (od početne do optimalne).
Analitički se može pokazati da se u retku z-c mogu pročitati vrijednosti dualnih varijabli
(ispod vrijednosti dopunskih, odnosno umjetnih varijabli koje čine početno bazično rješenje).
2
Prema tome, te dvije osobine impliciraju da je za moguća rješenja, ako jedno ili oba od
njih nisu optimalni za dani problem, a jednakost važi kad su oba optimalni. Osobina slabe
dualnosti opisuje uzajamni odnos između bilo kojeg para rješenja za primarne i dualne
probleme gdje su oba rješenja moguća za njihove posebne probleme.
U svakoj iteraciji, simpleks metoda nalazi specifični par rješenja za dva problema,
gdje je primarni problem moguć, a dualni je nemoguć (izuzev u konačnoj iteraciji).
(3)
Osobina komplementarnosti rješenja
: U svakoj iteraciji, simpleks metoda istovremeno
identificira kutno moguće rješenje x za primarni problem i komplementarno rješenje y za
dualni problem (u retku z-c koeficijenti dopunskih varijabli), gdje je
cx = yb
Ako x nije optimalno za primarni problem, onda y nije moguće za dualni problem (narušava
ograničenja dualnog problema).
(4)
Osobina komplementarnosti optimalnih rješenja:
U svakoj konačnoj iteraciji, simpleks
metoda istovremeno identificira optimalno rješenje x* za primarni problem i komplementarno
optimalno rješenje y* za dualni problem, gdje je
cx*=x*b
y
i
*
su cijene u sjeni za primarni problem.
(5)
Osobina simetričnosti.
Za bilo koji primarni problem i njegov dualni problem, svi
uzajamni odnosi između njih moraju biti simetrični, budući da je dual dualnog problem
primarni problem. Prema tome simpleks metoda se može primijeniti ili na primarni ili na
dualni problem.
Teorem dualiteta glasi:
Ako jedan problem ima moguća rješenja i ograničenu ciljnu funkciju, onda i njegov
dual ima moguća rješenja.
Ako jedan problem ima moguća rješenja i neograničenu ciljnu funkciju (nema
optimalno rješenje), onda njegov dual nema moguća rješenja.
Ako jedan problem nema moguća rješenja, tada drugi problem ili nema moguća
rješenja ili ima neograničenu ciljnu funkciju.
4
