\documentclass{article}

% Set some reasonable page dimensions
\textheight=240mm
\textwidth=170mm
\topmargin=-15mm
\oddsidemargin=-6mm
\evensidemargin=\oddsidemargin

\usepackage{graphicx}
\usepackage{amsmath,amssymb,verbatim}

% Czech language
\usepackage[czech]{babel}
%\usepackage{czech}
\usepackage[latin2]{inputenc}

% Definition of new commands
\newcommand{\argmax}{\mathop{\rm argmax}}
\newcommand{\argmin}{\mathop{\rm argmin}}
\newcommand{\aff}{\mathop{\rm aff}}
\newcommand{\conv}{\mathop{\rm conv}}
\newcommand{\rank}{\mathop{\rm rank}}
\newcommand{\diag}{\mathop{\rm diag}}
\newcommand{\sgn}{\mathop{\rm sgn}}
\newcommand{\Null}{\mathop{\rm null}}
\newcommand{\Rng}{\mathop{\rm rng}}

% Boldface vectors. Example: \_x
\def\_#1{\protect\mathchoice
    {\mbox{\boldmath $\displaystyle\bf#1$}}
    {\mbox{\boldmath $\textstyle\bf#1$}}
    {\mbox{\boldmath $\scriptstyle\bf#1$}}
    {\mbox{\boldmath $\scriptscriptstyle\bf#1$}}}

% Blackboard letters. Example: \bb R
\def\bb#1{\mathbb{#1}} 

\title{Příklad dokumentu v jazyce \LaTeX}
\author{Tomáš Werner}

\begin{document}

\maketitle

Dokument sestává z náhodně vybraných částí skript.


\section{Matematické značení}
\label{sec:znaceni}

\subsection*{Množiny}

\noindent
\begin{tabular}{ll}
$\{a_1,\ldots,a_n\}$ & množina s prvky $a_1,\ldots,a_n$ \\
$a\in A$ & prvek $a$ patří do množiny $A$ (neboli $a$ je prvkem $A$) \\
$A\subseteq B$ & množina $A$ je podmnožinou množiny $B$ (každý prvek z $X$ patří do $Y$) \\
$A=B$ & množina $A$ je rovna množině $B$, platí zároveň $A\subseteq B$ a $B\subseteq A$ \\
$\{\, a \in A \mid \phi(a) \,\}$ & množina prvků z $A$ s vlastností $\phi$. Někdy zkracujeme na $\{\, a \mid \phi(a) \,\}$. \\
$A\cup B$ & sjednocení množin, množina $\{\, a \mid a\in A\; \mbox{nebo} \;a\in B \,\}$ \\
$A\cap B$ & průnik množin, množina $\{\, a \mid a\in A\; \mbox{a zároveň} \;a\in B \,\}$ \\
$(a_1,\ldots,a_n)$ & uspořádaná $n$-tice prvků $a_1,\ldots,a_n$ \\
$A\times B$ & kartézský součin množin, množina $\{\, (a,b) \mid a\in A, \; b\in B \,\}$ \\
$A^n$ & kartézský součin $n$ stejných množin, $A^n=A\times\cdots\times A$ ($n$-krát).
\end{tabular}


\subsection*{Zobrazení} 

Zápisem $f{:}\ A\to B$ rozumíme zobrazení z množiny $A$ (zvané {\bf
  definiční obor}) do množiny $B$. Formální
definice je tato: podmnožina $f$ kartézského součinu $A\times B$ (tedy
{\em relace\/}) se nazývá zobrazení, platí-li $(a,b)\in f, \;
(a,b')\in f \;\Rightarrow\; b=b'$. Neformálně si představujeme
zobrazení jako černou skříňku (např.\ počítačovou funkci), která
přiřadí každému prvku $a\in A$ jediný prvek $b=f(a)\in B$. Přísně
vzato, `zobrazení' ({\em mapping, map\/}) znamená přesně to samé jako
`funkce' ({\em function\/}), ovšem slovo `funkce' se obvykle používá
pouze pro zobrazení do číselných množin (tedy $B=\bb R$, $\bb Z$, $\bb
C$ apod.).

Pro množinu obrazů všech vzorů s vlastností $\phi$ se používá zkratka
$\{\, f(a) \mid a\in A, \, \phi(a) \,\} = \{\, b \in B \mid b=f(a), \,
a\in A, \, \phi(a) \,\}$ nebo pouze $\{\, f(a) \mid \phi(a) \,\}$,
pokud je $A$ jasné z kontextu.  Např.\ množina $\{\, x^2 \mid -1<x<1
\,\}$ je polouzavřený interval $\langle 0,1)$.  Obraz množiny $A$
v zobrazení $f$ budeme často značit $f(A)=\{\,f(a) \mid a\in A\,\}$.

Zobrazení se nazývá:
\begin{itemize}
\item {\bf injektivní} (neboli prosté) pokud každý vzor má jiný obraz, tj.\ $f(a)=f(a') \;\Rightarrow\; a=a'$,
\item {\bf surjektivní} (neboli $A$ na $B$) pokud každý obraz má vzor,
tj.\ $f(A)=B$, tj.\ pro každé $b\in B$ existuje $a\in A$ tak, že
$b=f(a)$,
\item {\bf bijektivní} (neboli vzájemně jednoznačné) pokud je zároveň
injektivní a surjektivní.
\end{itemize}


\subsection*{Číselné množiny}

\noindent
\begin{tabular}{ll}
$\bb N$ & množina přirozených čísel \\
$\bb Z$ & množina celých čísel \\
$\bb Q$ & množina racionálních čísel \\
$\bb R$ & množina reálných čísel \\
$\bb R_+$ & množina nezáporných reálných čísel \\
$\bb R_{++}$ & množina kladných reálných čísel \\
%$\overline{\bb R}$ & množina rozšířených reálných čísel $\bb R\cup\{-\infty,+\infty\}$ \\
$\langle x_1,x_2 )$ & polouzavřený interval reálných čísel, $\{\,x\in \bb R \mid x_1\le x<x_2\,\}$ \\
$\bb C$ & množina komplexních čísel
\end{tabular}


\subsection*{Vektory a matice}

\noindent
\begin{tabular}{ll}
$\bb R^{m\times n}$ & množina reálných matic rozměru $m\times n$ (tedy s $m$ řádky a $n$ sloupci) \\
$\bb R^n$ & množina sloupcových vektorů, ztotožněná s množinou $\bb R^{n\times1}$ jednosloupcových matic \\
$\bb R^{1\times n}$ & množina řádkových vektorů \\
$\_x\cdot\_y$ & skalární součin vektorů \\
$\|\_x\|_p$ & $p$-norma vektoru $\_x$ \\
$\|\_x\|$ & norma vektoru $\_x$, bez dalšího upřesnění eukleidovská norma $\|\_x\|_2$
\end{tabular}

Vektory a matice značíme {\bf tučně}, skaláry {\it kurzívou}.

Symbol $f{:}\ \bb R^n\to\bb R$ značí funkci $n$ proměnných, která
vektoru $\_x=(x_1,\ldots,x_n)\in\bb R^n$ přiřadí skalár
$f(\_x)=f(x_1,\ldots,x_n)\in\bb R$. Jméno funkce píšeme kurzívou,
neboť její hodnoty jsou skaláry.


\subsection*{Extrém funkce na množině}
Pro minimum funkce $f{:}\ X\to\bb R$ na množině $X$ se užívá
značení
\[
\min_{x\in X} f(x) = \min\{\, f(x) \mid x\in X\,\} .
\]
Pro množinu prvků $X$, ve kterých se minimum nabývá, se používá symbol
{\bf argument minima}:
\[
\argmin_{x\in X} f(x) = \{\, x^*\in X \mid f(x^*)=\min_{x\in X} f(x) \,\} .
\]
Pro maximum je to analogické. Minima a maxima se souhrnně nazývají
{\bf extrémy} nebo {\bf optima}.



\section{Cvičení}
\begin{enumerate}

\item Najděte (úvahou) co nejjednodušší popis následujících množin:
\begin{enumerate}
\item $\{\, x^2 \mid x\in\bb R \,\}$
\item $\{\, 1/x \mid x\ge1 \,\}$
\item $\{\, {\rm e}^{-x^2} \mid x\in\bb R \,\}$
\item $\{\, x+y\mid x^2+y^2<1\,\}$
\item $\{\, x+y\mid x^2+y^2=1\,\}$
\item $\{\, |x|+|y| \mid x^2+y^2=1\,\}$
\item $\{\, x_1+\cdots+x_n \mid \_x\in\bb R^n, \; \|\_x\|=1\,\}$
\item $\{\, |x-y| \mid x\in\langle 0,1\rangle, \; y\in(1,2\rangle \,\}$
\end{enumerate}

\item Mějme množinu bodů v rovině $X=\langle -1,1\rangle\times\{0\}=\{\,(x,0)\mid
-1\le x\le 1\,\}$.  Načrtněte následující množiny:
\begin{enumerate}
\item $\displaystyle \big\{\,\_y\in\bb R^2 \,\big|\, \min_{\_x\in X} \|\_x-\_y\|\le 1 \,\big\}$
\item $\displaystyle \big\{\,\_y\in\bb R^2 \,\big|\, \max_{\_x\in X} \|\_x-\_y\|\le 2 \,\big\}$
\end{enumerate}

\item Formulujte (ale neřešte) následující úlohy ve tvaru
$\min\{\,f(\_x)\mid\_x\in X\,\}$.
%Dále udejte co nejjednodušší popis množiny $Y=f(X)=\{\,f(\_x)\mid\_x\in X\,\}$.
\begin{enumerate}
\item Najdi dvojici bodů v rovině, z nichž jeden je uvnitř čtverce se
středem v počátku a jednotkovou stranou a druhý je uvnitř kruhu se
středem v bodě $(2,2)$ a jednotkovým poloměrem, tak aby si tyto dva
body byly nejblíže.
\item Najdi dvě přirozená čísla se součtem $7$ a nejmenším součinem.
\item Nechť $\_A$ je matice rozměru $m\times n$, kde $m<n$, a $\_b$ je
vektor délky $m$. Předpokládejte, že matice má hodnost $m$. Najdi
řešení $\_x$ soustavy $\_A\_x=\_b$ tak, že délka vektoru $\_x$ je
minimální.
\item Ve vesnici je $n$ chalup o daných souřadnicích.  Najdi
souřadnice pošty tak, aby pošťák měl k nejvzdálenější (měřeno vzdušnou
čarou) chalupě co nejblíže.
\item Ve vesnici je $n$ chalup o daných souřadnicích.  Najdi
souřadnice $m$ pump tak, aby vzdálenost (vzdušnou čarou) od libovolné
chalupy k nejbližší pumpě byla minimální.
% \item Je dáno $m$ bodů v rovině. Najdi kružnici (s libovolným středem
% a poloměrem) tak, aby součet druhých mocnin vzdáleností bodů od
% kružnice byl minimální.
\end{enumerate}

\item Vyřešte následující úlohy:
\begin{enumerate}
\item $\min\{\, x^2+y^2 \mid x>0, \; y>0, \; xy\ge1 \,\}$
\item $\min\{\, (x-2)^2+(y-1)^2 \mid x^2\le1, \; y^2\le1 \,\}$
\item $\max\{\, \_x\cdot\_y \mid \_x\in\bb R^n, \; \_x\cdot\_x\le1
\,\}$ pro daný vektor $\_y\in\bb R^n$ ($\_x\cdot\_y$ značí skalární
součin). Zkuste nejprve pro $n=1$, pak pro $n=2$, pak zobecněte na libovolné $n$.
\item Najdi rozměry krabice bez víka o jednotkovém objemu a
nejmenším povrchu.
\item Hledá se $n$-tice čísel $x_1,\ldots,x_n\in\{-1,+1\}$ tak, že
jejich součin je kladný a jejich součet minimální. Jako výsledek
napište hodnotu tohoto minimálního součtu v závislosti na $n$.
\end{enumerate}

\end{enumerate}


\section{Matice}

Reálná {\bf matice} rozměru $m\times n$ je zobrazení $\_A{:}\
\{1\,\ldots\,m\}\times\{1\,\ldots\,n\}\to\bb R$. Hodnoty tohoto zobrazení značíme
$a_{ij}$.  Matici pomocí výčtu prvků zapisujeme tabulkou
\[
\_A = [a_{ij}] =
\begin{bmatrix}
a_{11} & \cdots & a_{1n} \\
\vdots & \ddots & \vdots \\
a_{m1} & \cdots & a_{mn}
\end{bmatrix} .
\]
Množinu všech reálných matic rozměru $m\times n$ (tj.\ s $m$ řádky a
$n$ sloupci) značíme $\bb R^{m\times n}$. 

Na množině $\bb R^{m\times n}$ zavedeme operace $+$ a $\cdot$ `po
prvcích'. Tím se tato množina stane lineárním prostorem dimenze $mn$.
{\bf Nulovou matici} (její všechny prvky jsou nuly) pak značíme $\_0$.

Pro $m=n$ se matice nazývá {\bf čtvercová}, pro $m \neq n$ {\bf
  obdélníková}. Pro $m<n$ nazveme matici {\bf širokou}, pro $m>n$ {\bf
  úzkou} (toto názvosloví není standardní).

Čtvercová matice je {\bf diagonální}, když má všude mimo hlavní
diagonálu nuly, tedy $a_{ij}=0$ pro $i\neq j$. {\bf Jednotková} matice
má na diagonále jedničky a mimo diagonálu nuly, značíme ji $\_I$.

{\bf Transpozici} matice $\_A=[a_{ij}]\in\bb R^{m\times n}$ značíme
$\_A^T=[a_{ji}]\in\bb R^{n\times m}$. Platí $(\_A+\_B)^T=\_A^T+\_B^T$.
Čtvercová matice se nazývá {\bf symetrická}, když $\_A^T=\_A$, a {\bf
  antisymetrická}, když $\_A^T=-\_A$.

{\bf Součin matic} $\_A\in\bb R^{m\times p}$
a $\_B\in\bb R^{p\times n}$ je matice $\_C\in\bb R^{m\times
  n}$ s prvky
\[
c_{ij} = \sum_{k=1}^p a_{ik} b_{kj} ,
\]
což značíme $\_C=\_A\_B$. Vlastnosti maticového součinu:
\begin{itemize}
\item $(\alpha\_A)\_B=\_A(\alpha\_B)=\alpha(\_A\_B)$
\item $(\_A\_B)\_C=\_A(\_B\_C)$
\item $(\_A+\_B)\_C=\_A\_C+\_B\_C$ a $\_A(\_B+\_C)=\_A\_B+\_A\_C$
\item $(\_A\_B)^T=\_B^T\_A^T$
\end{itemize}
Čtvercové matice obecně nekomutují, $\_A\_B\neq\_B\_A$.

Někdy je nutné sestavit matici z několika jejích podmatic (zvaných též
{\em bloky\/}), což značíme
\[
\begin{bmatrix} \_A & \_B \end{bmatrix} , \quad
\begin{bmatrix} \_A & \_B \\ \_C & \_D \end{bmatrix} , \quad
\begin{bmatrix} \_A & \_I \\ \_0 & \_D \end{bmatrix} .
\]
Rozměry jednotlivých bloků musí být kompatibilní.  Všimněte si, že ve
třetím příkladě jsou rozměry jednotkové matice $\_I$ a nulové matice
$\_0$ určeny rozměry matic~$\_A$ a~$\_D$. Pro násobení matic
sestavených z bloků platí podobné pravidlo jako pro matice sestavené
ze skalárů:
\[
\begin{bmatrix} \_A & \_B \\ \_C & \_D \end{bmatrix} 
\begin{bmatrix} \_X \\ \_Y \end{bmatrix} =
\begin{bmatrix} \_A\_X+\_B\_Y \\ \_C\_X+\_D\_Y \end{bmatrix} .
\]


\subsection{Hodnost a inverze}

{\bf Hodnost} matice je maximální počet jejich lineárně nezávislých
sloupců, což je totéž jako dimenze lineárního obalu sloupců matice.
Hodnost značíme $\rank\_A$. Platí $\rank\_A=\rank\_A^T$, tedy místo
pomocí sloupců jsme mohli hodnost definovat pomocí řádků.  Obecně je
vždy
\begin{equation}
\rank\_A\le\min\{m,n\} .
\label{eq:rank<min}
\end{equation}
Pokud je $\rank\_A=\min\{m,n\}$, říkáme, ža matice má {\bf plnou
  hodnost}. Čtvercová matice s plnou hodností se nazývá {\bf
  regulární}, jinak je {\bf singulární}. Pro hodnost součinu matic
platí
\begin{equation}
\rank(\_A\_B)\le\min\{\rank\_A,\rank\_B\} .
\label{eq:rank<minrank}
\end{equation}

Pokud matice $\_A\in\bb R^{n\times m}$ a $\_B\in\bb R^{m\times n}$
splňují
\begin{equation}
\_A\_B=\_I ,
\label{eq:AB=I}
\end{equation}
nazývá se matice $\_B$ {\bf pravá inverze} matice $\_A$ a matice $\_A$
{\bf levá inverze} matice $\_B$. Pravá či levá inverze nemusí
existovat nebo nemusí být jediná. Např.\ pro $m<n$
rovnost~(\ref{eq:AB=I}) nikdy nenastane (proč?). Pravá inverze
matice~$\_A$ existuje, právě když její řádky jsou lineárně nezávislé.
Levá inverze matice $\_B$ existuje, právě když její sloupce jsou
lineárně nezávislé.

Pro $m=n$ (čtvercové matice) pravá inverze matice $\_A$ existuje právě
tehdy, když $\_A$ je regulární (proto se regulární matici říká také
{\bf invertovatelná}). V tom případě je jediná a je rovna levé inverzi
matice $\_A$. Pak mluvíme pouze o {\bf inverzi} matice $\_A$ a značíme
ji $\_A^{-1}$. Máme tedy $\_A\_A^{-1}=\_I=\_A^{-1}\_A$. Pro regulární
matice $\_A$ a $\_B$ platí $(\_A\_B)^{-1}=\_B^{-1}\_A^{-1}$.


\section{Gradient funkce}
\label{sec:gradient}

Často se používá zvláštní název pro {\em transpozici\/} totální
derivace funkce $f{:}\ \bb R^n\to\bb R$, říká se jí {\bf gradient} a
značí se
\[
f'(\_x)^T = \nabla f(\_x)
\]
(čteme `nabla'). Jelikož $f'(\_x)$ je řádkový vektor, je gradient {\em
  sloupcový vektor\/} parciálních derivací. Zavedení nového slova pro
transpozici derivace se zdá zbytečné -- nicméně derivace je {\em
  lineární funkce\/}, kdežto gradient je {\em vektor}.

Literatura ovšem není jednotná v rozlišování gradientu a (totální)
derivace. Někdy se obojí ztotožňuje a značí $\nabla f(\_x)$.  To ale
vede k nekonzistenci, protože derivace funkce $\bb R^n\to\bb R$ pak
není speciálním případem derivace zobrazení $\bb R^n\to\bb R^m$ (tedy
Jacobiho matice) pro $m=1$, což je řádkový vektor. Dále se budeme
symbolu $\nabla f(\_x)$ spíše vyhýbat a místo něj používat
$f'(\_x)^T$.

Zkoumejme směrovou derivaci~$f'(\_x)\_s$ v pevném bodě~$\_x$ pro různé
{\em normalizované\/} směry $\_s$ (tedy $\|\_s\|=1$). Je jasné, že:
\begin{itemize}
\item Směrová derivace je největší ve směru $\_s=\nabla f(\_x) /
\|\nabla f(\_x)\|$, tedy když je $\_s$ rovnoběžný s gradientem a
stejně orientovaný. Tedy směr gradientu je {\em směr největšího
  růstu\/} funkce.
\item Velikost gradientu $\|\nabla f(\_x)\|$ je velikost strmosti
  funkce ve směru největšího růstu.
  \item Směrová derivace ve směru kolmém na gradient je nulová.
  Jelikož směrová derivace je nulová ve směru vrstevnice, gradient je
  vždy {\em kolmý k vrstevnici\/}.
\end{itemize}
Obrázek ukazuje tři vrstevnice funkce $f{:}\ \bb R^2\to\bb R$ a její
gradienty v několika bodech:
\begin{center}
\includegraphics[scale=.75]{gradient} % extension (eps, pdf, png, jpg) is chosen automatically
\end{center}


\section{Simplexová metoda}

Zde popíšeme algoritmus na řešení úloh lineárního programování zvaný
{\bf simplexová metoda}.

Zapomeňme prozatím na účelovou funkci a zkoumejme množinu přípustných
řešení LP ve standardním tvaru
\begin{equation}
X = \{\, \_x\in\bb R^n \mid \_A\_x=\_b, \; \_x\ge\_0 \,\} ,
\label{eq:simplex:X}
\end{equation}
kde $\_A\in\bb R^{m\times n}$ je široká ($m<n$) matice s hodností $m$,
tedy její řádky jsou lineárně nezávislé.

Soustava $\_A\_x=\_b$ má nekonečně mnoho řešení. Položíme-li však
$n-m$ složek vektoru $\_x$ rovno nule, soustava může mít jediné
řešení. Tato úvaha vede k následujícím definicím:
\begin{itemize}
\item Množina $L\subseteq\{1,2,\ldots,n\}$ se nazývá {\bf báze} úlohy,
pokud $|L|=m$ a sloupce matice $\_A$ s~indexy $L$ jsou lineárně
nezávislé. Tedy sloupce $L$ tvoří regulární matici $m\times m$.
\item Vektor $\_x$ se nazývá {\bf bázové řešení} příslušné bázi $L$,
pokud $\_A\_x=\_b$ a $x_j=0$ pro $j\notin L$.
\item Bázové řešení $\_x$ se nazývá {\bf přípustné}, pokud
$\_x\ge\_0$.
\item Bázové řešení $\_x$ se nazývá {\bf degenerované}, pokud má méně
než $m$ nenulových složek.
\item Dvě báze se nazývají {\bf sousední}, pokud mají $m-1$
společných prvků.
\end{itemize}

Protože $\_A$ má hodnost $m$, existuje aspoň jedna báze. Je jasné, že
báze určuje jednoznačně bázové řešení. Bázové řešení však může
odpovídat více než jedné bázi, což se stane právě tehdy, když je toto
bázové řešení degenerované.

Jako příklad uvažujme soustavu $\_A\_x=\_b$ danou tabulkou
\[
[\,\_A\,|\,\_b\,] = 
\left[\begin{array}{rrrrrr|r}
 -1 &   1 &   3 &   1 &   0 &   2 &  1 \\
  1 &   0 &   4 &   0 &   1 &   4 &  4 \\
 -1 &   0 &   4 &   1 &   1 &   4 &  2
\end{array}\right] .
\]
\begin{itemize}
\item $L=\{2,3,5\}$ není báze, protože sloupce $2,3,5$ matice $\_A$ jsou
  lineárně závislé.
\item $L=\{1,2,4\}$ je báze, protože tyto sloupce jsou lineárně
  nezávislé. Bázové řešení $\_x=(x_1,x_2\,\ldots\,x_6)$ příslušné bázi $L$ se
  najde řešením soustavy
\[
\begin{bmatrix}
 -1 &   1 &   1 \\
  1 &   0 &   0 \\
 -1 &   0 &   1 
\end{bmatrix}
\begin{bmatrix}
x_1 \\ x_2 \\ x_4
\end{bmatrix}
=
\begin{bmatrix}
1 \\ 4 \\ 2
\end{bmatrix}
\]
a položením $x_3=x_5=x_6=0$. Dostaneme $\_x=(4,-1,0,6,0,0)$. Toto
bázové řešení je nepřípustné, protože $x_2<0$. Není degenerované,
protože má $m=3$ nenulových složek.
\item $L=\{1,2,6\}$ je báze. Bázové řešení je
$\_x=(1,{1\over2},0,0,0,{3\over4})$. Je přípustné, protože $\_x\ge\_0$.
\item $L=\{3,4,5\}$ je báze. Bázové řešení je
$\_x=(0,0,1,-2,0,0)$. Je nepřípustné. Navíc je degenerované, protože
má méně než $m-1=3$ nenulových složek. 
\item Stejné bázové řešení $\_x=(0,0,1,-2,0,0)$ dostaneme volbou báze
$L=\{3,4,6\}$. Vidíme, že bázové řešení odpovídá více než jedné bázi,
protože je degenerované.
\item Báze $\{2,3,5\}$ a $\{3,4,5\}$ jsou sousední, protože mají
společné dva prvky $\{3,5\}$. Báze $\{2,3,5\}$ a $\{1,2,4\}$ nejsou
sousední, protože mají společný jen jeden prvek.
\end{itemize}


\end{document}