Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 63 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 65 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 67 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 69 Notice: Undefined variable: base in /home/misc/mst/public_html/lecture.php on line 36 Optymalizacja I – 1. Wiadomości wstępne – MIM UW

Zagadnienia

1. Wiadomości wstępne

1.1. Wprowadzenie

Rozpoczniemy od przedstawienia kilku charakterystycznych przykładów zadań optymalizacji liniowej.

Zagadnienie diety.

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:

\begin{array}[]{|c|c|c|c|c|}\hline&\text{węglowodany}&\text{białko}&\text{sole mineralne}&\text{cena}\\
\cline{1-5}\text{pszenica}&0,8&0,01&0,15&300~\text{zł/t}\\
\text{soja}&0,3&0,4&0,1&500~\text{zł/t}\\
\text{mączka}&0,1&0,7&0,2&800~\text{zł/t}\\
\hline\text{zapotrzebowanie}&0,3&0,7&0,1&\\
\hline\end{array}

Rozpoczynamy od zdefiniowania zmiennych. Niech x_{i} oznacza wagę i-tego składnika w mieszance.

Funkcją celu jest min\  x_{{0}}=300x_{{1}}+500x_{{2}}+800x_{{3}} - czyli koszt mieszanki.

Ograniczenia są dwojakiego typu

a) W mieszance musi być wystarczająco każdego ze składników:

0,8x_{{1}}+0,3x_{{2}}+0,1x_{{3}}\geq 0,3

0,01x_{{1}}+0,4x_{{2}}+0,7x_{{3}}\geq 0,7

0,15x_{{1}}+0,1x_{{2}}+0,2x_{{3}}\geq 0,1

b) Waga używanych składników jest nieujemna.

x_{{1}}\geq 0\qquad x_{{2}}\geq 0\qquad x_{{3}}\geq 0

Podsumowując. Szukamy najmniejszej wartości funkcji trzech zmiennych x_{0}\,:\mathbb{R}^{3}\rightarrow\mathbb{R} ograniczonej do podzbioru \mathbb{R}^{3} zwanego obszarem dopuszczalnym.

Zadanie to nazywamy liniowym, bo funkcja celu x_{{0}} zależy liniowo od zmiennych x_{{1}},x_{{2}},x_{{3}} 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.

\begin{array}[]{|c|ccccc|c|}\hline Koszt&S_{1}&S_{2}&S_{3}&S_{4}&S_{5}&\text{podaż}\\
\hline H_{1}&8&12&15&13&21&10\\
H_{2}&0&1&8&3&4&31\\
H_{3}&5&8&7&8&6&20\\
\hline\text{popyt}&10&10&20&10&11&\\
\hline\end{array}

Jak zorganizować transport, żeby koszt całkowity był minimalny?

Wprowadźmy zmienne x_{{ij}} opisujące ilość towaru przewożonego z i - tej hurtowni do j - tego sklepu.

Niech a_{{ij}} oznacza koszt przewiezienia jednostki towaru przewożonego z i - tej hurtowni do j - tego sklepu.

Jako funkcję celu przyjmijmy: min\  x_{{0}}\ =\sum _{{i=1}}^{{3}}\sum _{{j=1}}^{{5}}a_{{ij}}x_{{ij}}

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: \sum _{{j=1}}^{{5}}x_{{1j}}=10

analogicznie dla pozostałych hurtowni:

\sum _{{j=1}}^{{5}}x_{{2j}}=31,\ \sum _{{j=1}}^{{5}}x_{{3j}}=20,

Aby pierwszy sklep otrzymał cały zamówiony towar towar to: \sum _{{i=1}}^{{3}}x_{{i1}}=10,

analogicznie dla pozostałych sklepów

\sum _{{i=1}}^{{3}}x_{{i2}}=10,\ \sum _{{i=1}}^{{3}}x_{{i3}}=20,

\sum _{{i=1}}^{{3}}x_{{i4}}=10,\ \sum _{{i=1}}^{{3}}x_{{i5}}=11.

Ponadto nie można przewozić ujemnej liczby towarów - a więc:

\forall _{{i,j}}\; x_{{ij}}\geq 0

Czasami towary są podzielne jak prąd czy woda, ale często dodajemy warunek, że zmienne są liczbami całkowitymi - czyli dodajemy warunki:

\forall _{{i,j}}\; x_{{ij}}\in Z.

Dylemat stolarza

Stolarz ma zamówienie na 11 półek o kształcie jak na rysunku:

\par
Rys. 1.1. .

Ile desek o długości 220 cm potrzebuje na wykonanie zamówienia?

Na początku ustalamy sposoby cięcia desek:

\begin{array}[]{|c|c|c|}\hline i&60\, cm&40\, cm\\
\hline 1&3&1\\
2&2&2\\
3&1&4\\
4&0&5\\
\hline\end{array}

Wprowadzamy zmienne: x_{{i}} - liczba desek ciętych i-tym sposobem.

Teraz matematyczny model zagadnienia wygląda następująco:

min\  x_{{0}}=x_{{1}}+x_{{2}}+x_{{3}}+x_{{4}}

3x_{{1}}+2x_{{2}}+x_{{3}}\geq 11

x_{{1}}+2x_{{2}}+4x_{{3}}+5x_{{4}}\geq 22

\forall _{i}\  x_{{i}}\geq 0, x_{{i}}\in Z

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ść \sum _{{i=1}}^{n}\  a_{i}x_{i}\,=\, b można zastąpić układem nierówności.

\left\{\begin{array}[]{c}\sum _{{i=1}}^{n}\  a_{i}x_{i}\,\geq b\\
\sum _{{i=1}}^{n}\  a_{i}x_{i}\,\leq b\end{array}\right.

lub równoważnie:

\left\{\begin{array}[]{ll}\sum _{{i=1}}^{n}\  a_{i}x_{i}&\geq b\\
\sum _{{i=1}}^{n}\ -a_{i}x_{i}&\geq-b\end{array}\right.

Podobnie nierówność a_{1}x_{1}+a_{2}x_{2}+\ldots+a_{n}x_{n}\leq b

można zastąpić układem:

\left\{\begin{array}[]{l}a_{1}x_{1}+a_{2}x_{2}+\ldots+a_{n}x_{n}+x_{{n+1}}=b\\
x_{{n+1}}\geq 0\end{array}\right.

Podobnie warunki minimum i maksimum w funkcji celu można stosować wymiennie gdyż: min\{ x_{0}\;=f(x)\;|\; x\in S\}=max\{ y_{0}=-x_{0}\;=-f(x)\;|\; x\in 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\times 50 można wykonać z 9 desek długości 130 cm.?

\par
Rys. 1.2. .

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\rightarrow\mathbb{R}, gdzie X jest podzbiorem \mathbb{R}^{n} 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\subset R^{{n}} 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 \varepsilon>0 taki, że kula o środku p i promieniu \varepsilon jest rozłączna z A. Symbolami zapisujemy to: p\not\in A\ \Rightarrow\ \exists _{{\varepsilon>0}}\  K(p,\varepsilon)\cap A=\emptyset.

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\subset R^{{n}} nazywamy zbiór

\overline{A}=\bigcap\{ B\ |\  A\subset B\,\wedge\, 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\subset R^{{n}} jest wypukły jeśli wraz z każdymi dwoma punktami zawiera odcinek łączący je, czyli:

\forall _{{p,q\in A}}\overline{pq}\subset A

Odcinek \overline{pq} możemy zapisać jako

\overline{pq}=\{ p+r\overrightarrow{pq}\,|\, r\in[0,1]\}=\{ p+r(q-p)\,|\, r\in[0,1]\}=\newline=\{ p+rq-rp\,|\, r\in[0,1]\}=\{(1-r)p+rq\,|\, r\in[0,1]\}.

Ostatni zapis czytamy: \overline{pq} jest zbiorem kombinacji wypukłych punktów p i q.

Definicja 1.4

Brzegiem zbioruA\subset\mathbb{R}^{n} nazywamy zbiór \partial A=\{ p\in\mathbb{R}^{n}\,|\,\forall _{{\varepsilon>0}}\ \exists _{{q_{1},q_{2}}}\, q_{1}\in K(p,\varepsilon)\cap A,\, q_{2}\in K(p,\varepsilon)\setminus A\}.

Twierdzenie 1.2

Podzbiór A\subset R^{{n}} jest domknięty wtedy i tylko wtedy gdy zawiera swój brzeg, czyli:

A=\overline{A}\ \Leftrightarrow\ \partial A\subset A.

\Rightarrow Niech p\not\in A. Wtedy istnieje \varepsilon>0 taki, że K(p,\varepsilon)\cap A=\emptyset. Stąd p\not\in\partial A.

\Leftarrow Niech p\not\in A. Ponieważ p\not\in\partial A więc istnieje \varepsilon>0 taki, że K(p,\varepsilon)\cap A=\emptyset. Stąd A=\overline{A}.

Definicja 1.5

Półprzestrzenią w R^{{n}} nazywamy zbiór rozwiązań nietrywialnej nierówności liniowej, a zatem zbiór postaci:

H=\{(x_{{1}},...x_{{n}})\in\mathbb{R}^{n}\,|\, a_{{1}}x_{{1}}+a_{{2}}x_{{2}}+...+a_{{n}}x_{{n}}\leq b\}

Twierdzenie 1.3

Brzegiem \partial H półprzestrzeni

H=\{(x_{{1}},...x_{{n}})\in\mathbb{R}^{n}\,|\, a_{{1}}x_{{1}}+a_{{2}}x_{{2}}+...+a_{{n}}x_{{n}}\leq b\}

jest hiperprzestrzeń

\partial H=\{(x_{{1}},...,x_{{n}})\in\mathbb{R}^{n}\,|\, a_{{1}}x_{{1}}+a_{{2}}x_{{2}}+...+a_{{n}}x_{{n}}=b\}

Niech D=\{(x_{{1}},...,x_{{n}})\in\mathbb{R}^{n}\,|\, a_{{1}}x_{{1}}+a_{{2}}x_{{2}}+...+a_{{n}}x_{{n}}=b\} i p\in D. Ponieważ D\subset H więc \forall _{{\varepsilon>0}}\  p\in K(p,\varepsilon)\cap H. Ponadto jeśli p=(p_{1},p_{2}....,p_{n}) i a_{j}\neq 0 to \forall _{{\varepsilon>0}}\  p+(0,0,...,\frac{\varepsilon|a_{j}|}{2a_{j}},0,...,0)\in K(p,\varepsilon)\setminus H. Zatem D\subset\partial H.

Niech teraz p\not\in D. Wtedy, stosując wzór z algebry liniowej na odległość punktu od hiperprzestrzeni opisanej równaniem, otrzymujemy: \varrho(p,D)=\frac{|a_{1}p_{1}+a_{2}p_{2}+...+a_{n}p_{n}-b|}{\sqrt{a_{1}^{2}+a_{2}^{2}+...+a_{n}^{2}}}>0,

więc dla 0<\varepsilon<\varrho(p,D), K(p,\varepsilon)\cap H=\emptyset gdy p\not\in H i K(p,\varepsilon)\subset H,

gdy p\in H. Stąd \partial H\subset 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=(p_{{1}},p_{{2}},...p_{{n}}) i q=(q_{{1}},q_{{2}},...q_{{n}})\in H

Niech r\in[0,1].

Pokażemy, że rp+(1-r)q\in H

\sum _{{i=1}}^{{n}}a_{{i}}~p_{{i}}\leq b\quad\Rightarrow\sum _{{i=1}}^{{n}}a_{{i}}~(rp_{{i}})\leq rb

\sum _{{i=1}}^{{n}}a_{{i}}~q_{{i}}\leq~b\quad\Rightarrow\sum _{{i=1}}^{{n}}a_{{i}}((1-r)q_{{i}})\leq(1-r)b

\sum _{{i=1}}^{{n}}a_{{i}}~[rp_{{i}}+(1-r)q_{{i}}]\leq b\Rightarrow rp+(1-r)q\in H

Twierdzenie 1.5

Część wspólna zbiorów wypukłych jest zbiorem wypukłym .

Niech A=\cap _{i}A_{i} będzie przecięciem zbiorów wypukłych. Weźmy dwa punkty p i q ze zbioru A. Wówczas \forall _{i}\, p\in A_{i} oraz q\in A_{i}. Z wypukłości wynika, że odcinek \overline{pq}\subset A_{i}. Zatem, wobec dowolności wyboru indeksu i, odcinek \overline{pq}\subset 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\in R^{{n}}\backslash A.

Wtedy istnieje taki punkt q\in A, że odległość \varrho(p,q)=\varrho(p,A)=\underset{q\in A}{inf}\ \varrho(p,q)

Weźmy dowolny punkt x\in A. Rozpatrujemy A\cap K~(p,~\varrho(p,x))=A^{{\prime}}. Wtedy \varrho(p,A)=\varrho(p,A^{{\prime}}). Zatem bez zmniejszenia ogólności możemy przyjąć, że zbiór A jest zwarty.

Niech q_{{1}}, q_{{2}},… będzie takim ciągiem punktów \in A że \underset{i\rightarrow\infty}{lim}\varrho(p,q_{i})=\varrho(p,A).

Jeśli A jest zwarty to z q_{n} możemy wybrać podciąg q_{{i_{1}}}, q_{{i_{2}}}, … zbieżny do pewnego punktu q. Wtedy \varrho(p,q)=\underset{i\rightarrow\infty}{lim}\varrho(p,q_{{i_{j}}})=\varrho(p,A).

Twierdzenie 1.6

Jeśli A jest zbiorem wypukłym i domkniętym zaś p\not\in A to istnieje półprzestrzeń H, taka że A\subset H i p\not\in H

Niech q\in A będzie takim punktem, że \varrho(p,A)=\varrho(p,q).

Wiemy, że (p-q)\bullet(p-q)>0, gdzie x\bullet y oznacza standardowy iloczyn skalarny. Zatem:

p\bullet p-2q\bullet p+q\bullet q>0

\frac{1}{2}p\bullet p-q\bullet p+q\bullet q-\frac{1}{2}q\bullet q>0

\frac{1}{2}p\bullet p-\frac{1}{2}q\bullet q>q\bullet p-q\bullet q=q\bullet(p-q)

analogicznie -\frac{1}{2}p\bullet p+p\bullet p-q\bullet p+\frac{1}{2}q\bullet q>0

-\frac{1}{2}p\bullet p+\frac{1}{2}q\bullet q>-p\bullet p+p\bullet q=-p\bullet(p-q)

Przyjmijmy H=\{ x\in R^{{n}}\,|\, x\bullet(p-q)\ \leq\frac{1}{2}\left(p\bullet p\right)-\frac{1}{2}\left(q\bullet q\right)\}. H jest półpłaszczyzną zawierającą q i nie zawierającą p. Jej brzeg \partial H=\{ x\in R^{{n}}\,|\, x\bullet(p-q)=\frac{1}{2}\left(p\bullet p\right)-\frac{1}{2}\left(q\bullet q\right)\}, jak łatwo policzyć, jest symetralną odcinka \overline{pq}.

Przypuśćmy teraz, że istnieje punkt q_{1}\in A\setminus H. Wtedy na odcinku \overline{q_{1}q} istnieje punkt q_{2}\in\partial H. Trójkąt q,p,q_{2} jest równoramienny a ponieważ q_{2}\in A, z wypukłości, to jego najkrótszym bokiem jest \overline{pq}. Zatem wysokość opuszczona z wierzchołka p ma spodek q_{3} na boku \overline{q_{1}q}. Otrzymaliśmy sprzeczność bo q_{3}\in A oraz \varrho(p,q_{3})<\varrho(p,q). Zatem A\subset H.

Twierdzenie 1.7

Każdy zbiór wypukły i domknięty w R^{{n}} jest częścią wspólną półprzestrzeni.

Niech A będzie zbiorem wypukłym i domkniętym. Z każdym punktem p\not\in A związujemy pewną półprzestrzeń półprzestrzeń H_{p} taką, że A\subset H_{p} i p\not\in H_{p}. Teraz A=\bigcap _{{p\not\in A}}H_{p}.

Więcej wiadomości na ten temat można znaleźć w [11].

Zadania

Ćwiczenie 1.3

Opisać wypukłe podzbiory prostej \mathbb{R}^{1}.

Ćwiczenie 1.4

Niech S będzie zbiorem wypukłym w \mathbb{R}^{n}.

a) Pokazać, że jego domknięcie \overline{S} też jest zbiorem wypukłym.

b) Pokazać, że jego wnętrze S\setminus\partial S też jest zbiorem wypukłym.

Ćwiczenie 1.5

Niech S będzie zbiorem wypukłym w \mathbb{R}^{n}. Pokazać, że jeżeli domknięcie \overline{S}=\mathbb{R}^{n} to i S=\mathbb{R}^{n}.

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

Projekt współfinansowany przez Unię Europejską w ramach Europejskiego Funduszu Społecznego.

Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.