\documentstyle[12pt]{letter}
\setlength{\textwidth}{14.7cm}
\setlength{\textheight}{24.5cm}
\setlength{\oddsidemargin}{0.5cm}
\setlength{\evensidemargin}{0.5cm}
\setlength{\topmargin}{-1.7cm}
\def\RR{\hbox{\boldmath{$R$}}}
\def\NP{\hbox{\bf NP}}
\def\PP{\hbox{\bf P}}

\begin{document}

\begin{center}
1. KOLOKVIJ IZ RA\v{C}UNALNI\v{S}TVA III \\[2mm]
12. sve\v{c}an 1994
\end{center}

\bigskip

{\bf 1.} \ 
Na kmetiji gojijo \v{z}ivino. Vsaka krava mora dnevno dobiti med 16.000
in 18.000 kalorijami hrane. Pri tem mora dobiti vsaj 2kg proteinov in
3g vitaminov. Kmet ima na voljo tri vrste hrane: Kravlin, Govedogriz in
Zadovoljni hlev. Posamezne vrste hrane imajo naslednje
zna\v{c}ilnosti:

\begin{center}
\begin{tabular}{l|r|r|r|r|} 
Hrana:  & Cena & Kalorije & Proteini & Vitamini \\[1mm] \hline
Kravlin & 80 SIT & 3600 & 250g & 0,7g \\ \hline
Govedogriz & 60 SIT & 2000 & 350g & 0,4g \\ \hline
Zadovoljni hlev & 20 SIT & 1600 & 150g & 0.25g \\ \hline
\end{tabular}
\end{center}

Kmet \v{z}eli minimizirati stro\v{s}ke prehrane svoje \v{z}ivine.
Pomagaj mu!

\bigskip

{\bf 2.} \ Poi\v{s}\v{c}i najcenej\v{s}i razvoz v naslednjem omre\v{z}ju:

\vskip 5cm

Za\v{c}etni razvoz lahko ugane\v{s}, vendar naj bo neni\v{c}eln na
povezavah ~~~~, ~~~~ in ~~~~.

\bigskip

{\bf 3.} \ Naj $A\in\RR^{m,n}$ in $b\in\RR^m$. Poka\v{z}i, da velja
naslednji izrek. Sistem linearnih neena\v{c}b
$$
  Ax\le b\,,\quad x\ge 0
$$
ima re\v{s}itev natanko tedaj, ko za vsak $y\in\RR^m$, za katerega velja:
$$
   A^Ty\ge0\,,\quad y\ge 0\,,
$$
sledi: $b^Ty\ge 0$.

Nasvet: Zapi\v{s}i dani sistem neenakosti kot nalogo
linearnega programiranja.

\bigskip

{\bf 4.} \ Zanima nas naslednji problem. Dan je graf $G$. Spra\v{s}ujemo pa,
ali $G$ vsebuje dva cikla, ki skupaj pokrijeta vse to\v{c}ka grafa $G$.

a) Ali je ta problem v \NP\ ali v co-\NP?

b) Ali je v \PP, je \NP--poln, co\NP--poln ali ni\v{c} od tega? 

\end{document}