\documentclass[12pt,a4paper]{amsart}
\usepackage[czech]{babel}
\usepackage[utf8]{inputenc}

\textwidth=154mm
\hoffset=-14mm
\voffset=-20mm
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage[T1]{fontenc}
\usepackage{graphicx}
\usepackage{float}

\usepackage{times}


\newenvironment{zad}{\smallskip\par\noindent {\bf Příklad}.$\,$}{} 
\newenvironment{res}{\smallskip\par\noindent {\it Řešení}.$\,$}{\hbox{}\hfill $\Box$}
\newenvironment{navod}{\smallskip\par\noindent {\it Návod}.$\,$}{\hbox{}\hfill $\Box$}
\newenvironment{otazka}{\smallskip\par\noindent {\it Otázka}.$\,$\it}{}
\newenvironment{poznamka}{\smallskip\par\noindent {\it Poznámka}.$\,$\it}{}

\def\brem{\begin{poznamka}\rm}
\def\erem{\end{poznamka}}

\def\bot{\begin{otazka}}
\def\eot{\end{otazka}}

\def\ind #1{{\it #1}{\index{#1}}}

\def\R{\mathbb R}
\def \C{\mathbb C}
\def \Z{\mathbb Z}
\def\N{\mathbb N}
\def\K{\mathbb K}
\def\vect #1{{\overrightarrow{#1}}}
\def\d{\operatorname{dist}}
\def\i{\operatorname{i}}
\def\A{\mathcal A}
\def\B{\mathcal B}
\def\P{\mathcal P}
\newcommand\myeq{\mathrel{\overset{\makebox[0pt]{\mbox{\normalfont\tiny\sffamily def}}}{=}}}

\begin{document}
 
\parindent=0pt
\begin{center}
{\bf  7. cvičení z M3110 - lineární programování - simplexová metoda, podzim 2024}
\end{center}

\bigskip
\begin{zad}{\bf 1.\ }  V $\R^3$ najděte minimum funkce 
$c(x)=-2x_1+3x_2-x_3$ za podmínky, že
$$\begin{pmatrix}1&1&1\\
4&-3&1\\
2&1&-1
\end{pmatrix} \cdot \begin{pmatrix} x_1\\x_2\\x_3\end{pmatrix}\le \begin{pmatrix}10\\3\\10\end{pmatrix}, \quad x_1,x_2,x_3\ge 0.$$
\end{zad}

\begin{res} Úlohu $\min \{c(x), \ Ax\le b, \ x\ge 0\}$ převedeme na úlohu   
$$\min \{c(x), \ Ax+Es=b, \ x\ge 0\, \ s\ge 0\}$$ 
s jednotkovou maticí $E$ tvaru $3\times 3$ a pomocnými neznámými $s_1, s_2, s_3\ge 0$.  Simplexovou metodu začneme proto na vrcholu
$(x_1,x_2,x_3,s_1,s_2,s_3)=(0,0,0,10,3,10)$.
\end{res}

\bigskip
\begin{zad}{\bf 2.\ }  Simplexovou metodou řešte nalezení minima funkce $c(x)=2x_1+4x_2+7x_3+2x_4+5x_5$ za podmínek, že
$$\begin{pmatrix}
  1&1&2&1&2\\
1&2&3&1&1\\
1&1&1&2&1
\end{pmatrix} \cdot x= \begin{pmatrix}7\\6\\4\end{pmatrix}, \quad x\ge 0.$$
\end{zad}

\begin{res}  Abychom mohli najít vrchol, kde začneme simplexovou metodu, tak hledáme
$$\{\min (t_1+t_2+t_3); Ax+Et=b,\ x\ge 0, \ t\ge 0\}.$$
\end{res}

\bigskip
\begin{zad}{\bf 3.\ }  Simplexovou metodou řešte nalezení minima funkce $c(x)=15x_2+30x_3+15x_5$ za podmínek, že
$$\begin{pmatrix}
  1&1&0&0&0\\
1&0&2&1&0\\
0&1&0&2&3
\end{pmatrix} \cdot x\ge \begin{pmatrix}120\\80\\110\end{pmatrix}, \quad x\ge 0.$$
\end{zad}


\bigskip
\begin{zad}{\bf 4.\ }  Simplexovou metodou nalezněte minimum funkce $c(x)=-x_1-x_2$ za podmínek, že
$$\begin{pmatrix}
  -1&2\\
2&-1\\
\end{pmatrix} \cdot x\ge \begin{pmatrix}1\\0\end{pmatrix}, \quad x\ge 0.$$
\end{zad}




\bigskip
\begin{zad}{\bf 5.\ }  Firma Defekt vyrábějící jízdní kola chce naplánovat optimální měsíční výrobu. Produkuje tři typy kol: silniční, horská a zimní. Výroba je rozdělená na montáž a testování kvality, přičemž firma má k dispozici 520 hodin provozu montážní linky a 100 hodin testovací laboratoře za jeden měsíc. Pro výrobu silničního kola jsou potřeba 4 hodiny montáže, pro výrobu jednoho horského kola 5 hodin montáže a pro výrobu jednoho zimního kolka 6 hodin montáže. Pro každé kolo je potřeba 1 hodina testování. Firma chce, aby zimní kola tvořila maximálně polovinu měsíční produkce všech kol.  Zisk z prodeje jednoho silničního kola je 4000 Kč, z prodeje jednoho horského kola 6000 Kč a z prodeje jednoho zimního kola 7000 Kč. Firma vždy prodá všechna vyrobená kola.

Při jakém počtu vyrobených silničních, horských a zimních kol za jeden měsíc maximalizuje firma svůj zisk? A jaký tento zisk bude? Zformulujte problém jako úlohu lineární optimalizace a úlohu vyřešte.
\end{zad}

\begin{res}    Chceme maximalizovat funkci $4x_1+6x_2+7x_3$ za podmínek tvaru $Ax\le b$ a $x\ge 0$. To je totéž jako za stejných podmínek minimalizovat funkci
$c(x)=-4x_1-6x_2-7x_3$. Postupujeme jako v 1. úloze.

\begin{gather*}\left(
\begin{array}{rrrrrr|r}
4&5&6&1&0&0&520\\
\bold{1}&1&1&0&1&0&100\\
{-1}&-1&1&0&0&1&0\\
{-4}&-6&-7&0&0&0&0
\end{array}\right)
\sim
\left(
\begin{array}{rrrrrr|r}
0&1&2&1&-4&0&120\\
1&\bold{1}&1&0&1&0&100\\
0&0&2&0&1&1&100\\
0&-2&-3&0&4&0&400\\
\end{array}\right)
\sim
\\
\sim
\left(
\begin{array}{rrrrrr|r}
{-1}&0&\bold{1}&1&-5&0&20\\
1&1&1&0&1&0&100\\
0&0&2&0&1&1&100\\
2&0&-1&0&6&0&600\\
\end{array}\right)
\sim
\left(
\begin{array}{rrrrrr|r}
{-1}&0&1&1&-5&0&20\\
2&1&0&-1&6&0&80\\
2&0&0&-2&11&1&60\\
1&0&0&1&1&0&620
\end{array}\right)
\end{gather*}
První číslo v záhlaví je kladné, proto $x_1=0$. Dále odečteme $x_2=80, x_3=20$. Zisk je 620 tisíc Kč.                        
\end{res}

\bigskip
\begin{zad}{\bf 6.\ }   Květinářství odebírá každý týden květiny od dvou stálých dodavatelů Anny a Boba. Pro tento týden má smysl brát nejvýše jednu dodávku od Anny a jednu od Boba. Při jedné dodávce doveze Anna maximálně 50 svazků květin, přičemž nabízí dovoz růží a tulipánů. Také Bob doveze při jedné dodávce nejvýše 50 svazků květin a nabízí rovněž růže a tulipány. Květinářství může uskladnit maximálně 70 svazků růží a 60 svazků tulipánů. vedoucí ví, že prodá všechny dodané květiny. Zisk z jednoho svazku růží od Anny je 60 Kč, z jednoho svazku tulipánů od Anny 80 Kč, z jednoho svazku růží od Boba je 100 Kč a z jednoho svazku tulipánů od Boba 110 Kč. 

Kolik a jakých svazků má vedoucí pro tento týden objednat, aby maximalizoval svůj zisk? A jaký tento zisk bude? Zformulujte problém jako úlohu lineární optimalizace a pak úlohu vyřešte. 
\end{zad}
\begin{res}
Maximální zisk je  9100 Kč pro $x_1=0$, $x_2=50$, $x_3=40$ a $x_4=10$..   
\end{res}
\end{document}

