Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
2I
10PROGRAMOWANIELINIOWE
RYSo1040Punktzjakoliniowakombinacjawypukła
punktówmiy
RozpatrzmywielościanU(rys.1.4)?któryjestzbioremrozwiązańukładu
nierówności?(1:23)1(1:25):U1{m:[A]m<bg.Ustalmydowolnepunkty
m7yEUirozważmyichwypukłąkombinacjęliniową
z1Am+(11A)y70<A<1:
(1:28)
wówczas
[A]m<boraz[A]y<b7astąd
[A]z1[A][Am+(11A)y]1A[A]m+(11A)[A]y<
(1:29)
<Ab+(11A)b1b:
ZatemzEU?awięc[m7y]CU.
Prowadzitodowniosku?iżwielościanU1{m:[A]m<bg?będącyzbiorem
rozwiązańukładunierówności(1:23)1(1:25)jestwypukły.Tostwierdzenie
jestjednymzpodstawowychwteoriizadańprogramowanialiniowegoizna-
lazłozastosowaniepraktycznewalgorytmachrozwiązywaniazadańprogra-
mowanialiniowego.
1l1l2lEkstremumwarunkowefunkcjiliniowej
Rozpatrzmyukładnierówności[A]m<b?któregozbioremrozwiązańjest
wielościanwypukłyUorazfunkcjęliniową
Q(m)1C
Tm7gdzieCT1[C1:::Ci:::Cn]:
(1:30)
Zbadamy?wjakichpunktachmEUfunkcjaQ(m)możemiećminimum.Niech
{m
kg?gdziek117:::7r?będziezbioremwierzchołkówwielościanuwypu-
kłegoU?amEUpunktemwewnętrznymtegowielościanu.Punktmmożna
wyrazićjakowypukłąkombinacjęliniowąwierzchołkówmk.Przypadekr12
(Ujestodcinkiem)wykorzystaliśmypoprzednio(rys.1.4?(1.28)).Przyj-
mijmyr13(Ujesttrójkątemutworzonymprzezwierzchołkim
17m27m3)
orazliczbyAl7AbE(071>?Al>Ab.Zrysunku1.5mamy
m1m
2+l+b1m2+Al(m11m2)+Ab(m31m1)1
1(Al1Ab)
\\rJ
A1
m
1+(11Al)
\\rJ
A2
m
2+Ab
\\rJ
A3
m
3:
