Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
28
10PROGRAMOWANIELINIOWE
OstatniaznierównościjestspełnionadlawszystkichpunktówmEU?stąd
wpunkcie^
mnależącymdozbioruwierzchołków{m
kgfunkcjaQ(m)mami-
nimum.Innymisłowy?funkcjaQ(m)osiągaminimumwjednymzwierz-
chołkówwielościanuwypukłegoU.Podobnerozumowaniemożnaprzepro-
wadzićdlamaksimumfunkcjiQ(m).Ostateczniewykazaliśmy?żefunkcja
Q(m)maekstremumwarunkowewzbiorzeokreślonymukłademnierówności
U1{m:[A]m<bgwwierzchołkachwielościanuwypukłegoU.Tostwierdze-
niemarównieżdużeznaczeniepraktycznewrozwiązywaniuzadańprogra-
mowanialiniowego.Zadanieposzukiwaniaekstremumwarunkowegowzbio-
rzerozwiązańUsprowadzasiębowiemdoprzeszukaniaskończonegozbioru
wierzchołkówtegozbioru.
1l1l3lSprzecznościiniejednoznacznościrozwiązańzadania
poszukiwaniaekstremumwarunkowego
Zoczywistychwzględówwarunkiemkoniecznymdorozwiązaniazadaniapo-
szukiwaniaekstremumwarunkowegojestistnieniezbioruU1{m:[A]m<
<bg1o.Półprzestrzeniebędącezbioramirozwiązańkażdejznierówności
lT
j^
m<bjmogąniemiećczęściwspólnejŹwtedyU1oizadanieniema
rozwiązania.
JeśliistniejezbiórU1o?toekstremumwarunkowe^
mwtymzbio-
rzeleżywjednymzwierzchołkówtegozbioru:^
m1ext({m
rg)?będących
przecięciemhiperpłaszczyznlT
j^
m1bj.
Zadaniedegenerujesię?jeżeliwwierzchołku^
mprzecinasięj>nhiper-
płaszczyzn?przyczymnoznaczawymiarprzestrzeni?wktórejzawierasię
zbiórUCR
n(rys.1.6a).
RYSo1060Niejednoznacznościrozwiązańzadaniaposzukiwaniaekstremumwarunkowego
wzbiorzeU
ZdefiniujmypółprostąPwychodzącązpunktum
OEUokierunkuwek-
torad:P1{m:m1mO+td7t>0g.PółprostaPzawierasięwzbiorze
U1{m:[A]m<bg?jeślidlawszystkichnieujemnychtzachodzizależność
m
O+td<b:
