Zagadnienia

1.1 Wprowadzenie
- Zadania
1.2 Zbiory wypukłe i zbiory domknięte
- Zadania

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 zbioru $A\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}$ .

∎