1.1. Wprowadzenie
Rozpoczniemy od przedstawienia kilku charakterystycznych
przykładów zadań optymalizacji liniowej.
Jak wymieszać pszenicę, soję i mączkę rybna by uzyskać
najtańszą mieszankę zapewniającą wystarczającą zawartość
węglowodanów, białka i soli mineralnych dla kurcząt.
Zapotrzebowanie, zawartość składników i ceny przedstawia
następująca tabela:
węglowodanybiałkosole mineralnecenapszenica0,80,010,15300zł/tsoja0,30,40,1500zł/tmączka0,10,70,2800zł/tzapotrzebowanie0,30,70,1
Rozpoczynamy od zdefiniowania zmiennych. Niech xi oznacza wagę i-tego składnika w mieszance.
Funkcją celu jest
minx0=300x1+500x2+800x3 - czyli koszt mieszanki.
Ograniczenia są dwojakiego typu
a) W mieszance musi być wystarczająco każdego ze składników:
0,01x1+0,4x2+0,7x3≥0,7
0,15x1+0,1x2+0,2x3≥0,1
b) Waga używanych składników jest nieujemna.
Podsumowując. Szukamy najmniejszej wartości funkcji trzech zmiennych x0:R3→R ograniczonej do podzbioru R3 zwanego obszarem dopuszczalnym.
Zadanie to nazywamy liniowym, bo funkcja celu x0 zależy
liniowo od zmiennych x1,x2,x3 i obszar dopuszczalny
opisany jest zbiorem nierówności liniowych.
Zagadnienie transportowe:
Mamy 3 hurtownie i 5 sklepów. Koszt transportu jednostki towaru
z i - tej hurtowni do j - tego sklepu przedstawia tabela.
KosztS1S2S3S4S5podażH181215132110H20183431H35878620popyt1010201011
Jak zorganizować transport, żeby koszt całkowity był minimalny?
Wprowadźmy zmienne xij opisujące ilość towaru przewożonego z
i - tej hurtowni do j - tego sklepu.
Niech aij oznacza koszt przewiezienia jednostki towaru przewożonego z
i - tej hurtowni do j - tego sklepu.
Jako funkcję celu przyjmijmy: minx0=∑i=13∑j=15aijxij
Rozpatrzmy przypadek gdy zadanie jest zbilansowane, czyli gdy
podaż = popyt.
Wtedy warunkami ograniczającymi są:
Aby pierwsza hurtownia wysłała cały towar to: ∑j=15x1j=10
analogicznie dla pozostałych hurtowni:
∑j=15x2j=31,∑j=15x3j=20,
Aby pierwszy sklep otrzymał cały zamówiony towar towar to: ∑i=13xi1=10,
analogicznie dla pozostałych sklepów
∑i=13xi2=10,∑i=13xi3=20,
∑i=13xi4=10,∑i=13xi5=11.
Ponadto nie można przewozić ujemnej liczby towarów - a więc:
Czasami towary są podzielne jak prąd czy woda, ale często dodajemy warunek, że zmienne są liczbami całkowitymi - czyli dodajemy
warunki:
Stolarz ma zamówienie na 11 półek o kształcie jak na rysunku:
Ile desek o długości 220 cm potrzebuje na wykonanie
zamówienia?
Na początku ustalamy sposoby cięcia desek:
i60cm40cm131222314405
Wprowadzamy zmienne: xi - liczba desek ciętych i-tym
sposobem.
Teraz matematyczny model zagadnienia wygląda następująco:
Zadania tego typu występują często w realnym życiu gdyż huty dostarczają do fabryk pręty określonej długości, które trzeba oszczędnie pociąć lub taśmę, z której trzeba wykroić detale.
Jak widzimy w zadaniach optymalizacji liniowej opisujące obszar
dopuszczalny są równaniami lub nierównościami liniowymi. Do
pewnego stopnia te typy warunków są wymienne.
Równość ∑i=1naixi=b można zastąpić układem nierówności.
∑i=1naixi≥b∑i=1naixi≤b
∑i=1naixi≥b∑i=1n-aixi≥-b
Podobnie nierówność a1x1+a2x2+…+anxn≤b
a1x1+a2x2+…+anxn+xn+1=bxn+1≥0
Podobnie warunki minimum i maksimum w funkcji celu można stosować
wymiennie gdyż:
minx0=fx|x∈S=maxy0=-x0=-fx|x∈S
Jako uzupełniające podręczniki do wykładu polecamy [2], [1], [6] i [12]
Zadania
Ćwiczenie 1.1
Ile półek o wymiarach 30×50 można wykonać z 9 desek długości 130 cm.?
Rozwiąż zadanie graficznie.
Ćwiczenie 1.2
Przy warunkach zadania 1.1 wylicz ile desek potrzeba na wykonanie 11 półek.
1.2. Zbiory wypukłe i zbiory domknięte
Zagadnienie optymalizacji polega na znalezieniu minimum lub maksimum funkcji f:X→R, gdzie X jest podzbiorem Rn zwanym obszarem dopuszczalnym. Od zbioru X wymagamy by był domknięty i wypukły.
Zaczniemy od opisania najważniejszych własności zbiorów wypukłych i domkniętych.
Definicja 1.1
Podzbiór A⊂Rn nazywamy domkniętym jeżeli granica każdego zbieżnego ciągu punktów z A należy do zbioru A. Lub równoważnie: Jeżeli punkt p nie należy do A to istnieje ε>0 taki, że kula o środku p i promieniu ε jest rozłączna z A. Symbolami zapisujemy to: p∉A⇒∃ε>0Kp,ε∩A=∅.
Będziemy też używać znanego twierdzenia o zbiorach domkniętych.
Twierdzenie 1.1
Część wspólna zbiorów domkniętych jest zbiorem domkniętym.
Definicja 1.2
Domknięciem zbioru A⊂Rn nazywamy zbiór
A¯=⋂{B|A⊂B∧B domknięty}
czyli najmniejszy zbiór domknięty zawierający A.
Jedną z najważniejszych własności obszaru dopuszczalnego jest
wypukłość.
Definicja 1.3
Wypukłość
Podzbiór A⊂Rn jest wypukły jeśli wraz z każdymi dwoma
punktami zawiera odcinek łączący je, czyli:
∀p,q∈Apq¯⊂A
Odcinek pq¯ możemy zapisać jako
pq¯=p+rpq→|r∈0,1=p+rq-p|r∈0,1=
=p+rq-rp|r∈0,1=1-rp+rq|r∈0,1.
Ostatni zapis czytamy: pq¯ jest zbiorem
kombinacji wypukłych punktów p i q.
Definicja 1.4
Brzegiem zbioruA⊂Rn nazywamy zbiór
∂A=p∈Rn|∀ε>0∃q1,q2q1∈Kp,ε∩A,q2∈Kp,ε∖A.
Twierdzenie 1.2
Podzbiór A⊂Rn jest domknięty wtedy i tylko wtedy gdy zawiera swój brzeg, czyli:
A=A¯⇔∂A⊂A.
⇒ Niech p∉A. Wtedy istnieje ε>0 taki, że Kp,ε∩A=∅. Stąd p∉∂A.
⇐ Niech p∉A. Ponieważ p∉∂A więc istnieje ε>0 taki, że Kp,ε∩A=∅. Stąd A=A¯.
∎
Definicja 1.5
Półprzestrzenią w Rn nazywamy zbiór rozwiązań nietrywialnej
nierówności liniowej, a zatem zbiór postaci:
H=x1,…xn∈Rn|a1x1+a2x2+…+anxn≤b
Twierdzenie 1.3
Brzegiem ∂H półprzestrzeni
|
H=x1,…xn∈Rn|a1x1+a2x2+…+anxn≤b |
|
jest hiperprzestrzeń
|
∂H=x1,…,xn∈Rn|a1x1+a2x2+…+anxn=b |
|
Niech D=x1,…,xn∈Rn|a1x1+a2x2+…+anxn=b i p∈D.
Ponieważ D⊂H więc ∀ε>0p∈Kp,ε∩H. Ponadto jeśli p=(p1,p2….,pn) i aj≠0 to ∀ε>0p+0,0,…,εaj2aj,0,…,0∈Kp,ε∖H. Zatem D⊂∂H.
Niech teraz p∉D. Wtedy, stosując wzór z algebry liniowej na odległość punktu od hiperprzestrzeni opisanej równaniem, otrzymujemy: ϱp,D=a1p1+a2p2+…+anpn-ba12+a22+…+an2>0,
więc dla 0<ε<ϱp,D, Kp,ε∩H=∅ gdy p∉H i Kp,ε⊂H,
gdy p∈H. Stąd ∂H⊂D.
∎
Twierdzenie 1.4
Półprzestrzeń jest zbiorem wypukłym i domkniętym.
Dowód domkniętości otrzymujemy jako wniosek z dwóch ostatnich twierdzeń.
Dowód wypukłości
Niech p=p1,p2,…pn i q=q1,q2,…qn∈H
Niech r∈0,1.
Pokażemy, że rp+1-rq∈H
∑i=1naipi≤b⇒∑i=1nairpi≤rb
∑i=1naiqi≤b⇒∑i=1nai1-rqi≤1-rb
∑i=1nairpi+1-rqi≤b⇒rp+1-rq∈H
∎
Twierdzenie 1.5
Część wspólna zbiorów wypukłych jest zbiorem wypukłym .
Niech A=∩iAi będzie przecięciem zbiorów wypukłych. Weźmy
dwa punkty p i q ze zbioru A. Wówczas ∀ip∈Ai oraz q∈Ai. Z wypukłości wynika, że odcinek
pq¯⊂Ai. Zatem, wobec dowolności wyboru indeksu i, odcinek
pq¯⊂A
∎
Przedstawimy teraz szereg faktów o rozdzielaniu zbiorów domkniętych.
Lemat 1.1
Niech A będzie zbiorem wypukłym i domkniętym i p∈Rn\A.
Wtedy istnieje taki punkt q∈A, że odległość ϱp,q=ϱp,A=infq∈Aϱp,q
Weźmy dowolny punkt x∈A. Rozpatrujemy A∩Kp,ϱp,x=A′. Wtedy ϱp,A=ϱp,A′. Zatem bez zmniejszenia ogólności możemy przyjąć, że zbiór A jest
zwarty.
Niech q1, q2,… będzie takim ciągiem punktów ∈A że
limi→∞ϱp,qi=ϱp,A.
Jeśli A jest zwarty to z qn możemy wybrać podciąg qi1, qi2, … zbieżny do pewnego punktu q. Wtedy ϱp,q=limi→∞ϱp,qij=ϱp,A.
∎
Twierdzenie 1.6
Jeśli A jest zbiorem wypukłym i domkniętym zaś p∉A to istnieje
półprzestrzeń H, taka że A⊂H i
p∉H
Niech q∈A będzie takim punktem, że ϱp,A=ϱp,q.
Wiemy, że p-q∙p-q>0, gdzie x∙y oznacza standardowy iloczyn skalarny. Zatem:
p∙p-2q∙p+q∙q>0
12p∙p-q∙p+q∙q-12q∙q>0
12p∙p-12q∙q>q∙p-q∙q=q∙p-q
analogicznie -12p∙p+p∙p-q∙p+12q∙q>0
-12p∙p+12q∙q>-p∙p+p∙q=-p∙p-q
Przyjmijmy H=x∈Rn|x∙p-q≤12p∙p-12q∙q. H jest półpłaszczyzną zawierającą q i nie zawierającą p. Jej brzeg ∂H=x∈Rn|x∙p-q=12p∙p-12q∙q, jak łatwo
policzyć, jest symetralną odcinka pq¯.
Przypuśćmy teraz, że istnieje punkt q1∈A∖H. Wtedy na odcinku q1q¯ istnieje punkt q2∈∂H. Trójkąt q,p,q2 jest równoramienny a ponieważ q2∈A, z wypukłości, to jego najkrótszym bokiem jest pq¯. Zatem wysokość opuszczona z wierzchołka p ma spodek q3 na boku q1q¯. Otrzymaliśmy sprzeczność bo q3∈A oraz ϱp,q3<ϱp,q. Zatem A⊂H.
∎
Twierdzenie 1.7
Każdy zbiór wypukły i domknięty w Rn jest częścią wspólną
półprzestrzeni.
Niech A będzie zbiorem wypukłym i domkniętym. Z każdym punktem p∉A związujemy pewną półprzestrzeń
półprzestrzeń Hp taką, że A⊂Hp i
p∉Hp. Teraz A=⋂p∉AHp.
∎
Więcej wiadomości na ten temat można znaleźć w [11].
Zadania
Ćwiczenie 1.3
Opisać wypukłe podzbiory prostej R1.
Ćwiczenie 1.4
Niech S będzie zbiorem wypukłym w Rn.
a) Pokazać, że
jego domknięcie S¯ też jest zbiorem wypukłym.
b) Pokazać, że
jego wnętrze S∖∂S też jest zbiorem wypukłym.
Ćwiczenie 1.5
Niech S będzie zbiorem wypukłym w Rn. Pokazać, że
jeżeli domknięcie S¯=Rn to i S=Rn.
