Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
12
zaśrówność
dwiemanierównościami:
oraz
Problemprogramowanialiniowego
Σ
j=1
n
aijxj=bi
Σ
j=1
n
aijxj≤bi
Σ
j=1
n
aijxj≥bi
TakwięcmimożewcześniejzdefiniowaliśmyPPLwpostacinapozórszczególnej
(nazwaliśmyjąpostaciąstandardowąPPL),równiedobrzemożnapowiedzieć,
żePPLpoleganamaksymalizacjilubminimalizacjiformyliniowejwzbiorze,
któryjestrozwiązaniemukładunierównościirównańliniowychwRn.
Problememrozstrzyganianiesprzecznościirozwiązywaniaukładównierów-
nościirównańliniowychbędziemysięzajmowaćwrozdziale6.
1.1
Definicje
Niechbędziedanyproblemprogramowanialiniowego(wpostacistandardowej):
(
I
I
4
I
I
l
Ax
cx
x
→max
≤
≥
b
Θn
(1.4)
x=(x1j...jxn)(lub:xj(j=1j...jn))nazywamyrozwiązaniemdopusz-
czalnymPPL(1.4),jeśli:
x≥Θn(inaczej:xj≥0jdlaj=1j...jn),
Ax≤b(inaczej:Σ
n
j=1aijxj≤bijź=1j...jm).
RozwiązaniemoptymalnymPPL(1.4)(lub(1.3))nazywamytakierozwią-
zaniedopuszczalnex,dlaktóregofunkcjaf(x)=cxprzyjmujewartośćmaksy-
malną.
Oczywiście,możesięzdarzyć,żePPLwogóleniemarozwiązańdopuszczal-
nych,tzn.zbiór
{x∈Rn:x≥Θ
niAx≤b}
(1.5)
jestzbiorempustym.Mówimywówczas,żePPL(1.4)jestproblememsprze-
cznym(lubżewarunki:x≥ΘniAx≤bsąsprzeczne).
Jeślizbiór(1.5)jestniepustyifunkcjafwtymzbiorzeniemamaksimum,
tomówimy,żePPLjestproblememnieograniczonym.Wrzeczysamej,
zbiór(1.5)jestdomkniętywRn,afunkcjaf–ciągła.Jeśliwięczbiór(1.5)
jestniepustyifnieprzyjmujewtymzbiorzemaksimum,tofjestwzbiorze
nieograniczona(samzbiórtakżejestnieograniczony).
