1. Tovarna proizvaja srajce, hla\v{c}e in obleke. Pri delu uporabljajo
tri stroje. Za izdelavo ene srajce potrebujejo 10 min dela na prvem
stroju, 30 min na drugem in 10 min na tretjem. Za hla\v{c}e so \v{c}asi 
20, 0 in 40 minut, za obleko pa 10, 20 in 0 minut. Prvi in tretji stroj 
smeta dnevno delati najve\v{c} 360 minut, drugi pa 400 minut. 
Pri vsaki srajci tovarna zaslu\v{z}i 300 tolarjev (po odbitju vseh 
stro\v{s}kov), pri enih hla\v{c}ah ima 200 tolarjev \v{c}istega dobi\v{c}ka, 
pri obleki pa 500. Vse izdelke brez te\v{z}av prodajo.

a) Dolo\v{c}i optimalno dnevno proizvodnjo.

b) Poi\v{s}\v{c}i re\v{s}itev dualne naloge. 



2. Oceni, kako te\v{z}ak je naslednji problem (ali je polinomski ali ne,
ali je NP-poln ali ne):

``Dan je graf $G$ in celo \v{s}tevilo $k\le |E(G)|$. Ali v grafu
$G$ obstaja taka mno\v{z}ica povezav $U\subseteq E(G)$, da je
$|U|\le k$ in vsaka povezava $e\in E(G)\backslash U$ ima vsaj
eno kraji\v{s}\v{c}e skupno z neko povezavo iz $U$?''



3. Trgovski potnik mora obiskati 21 mest, 
ki so razporejena kot to\v{c}ke na celo\v{s}tevilski mre\v{z}i velikosti 
$4\times 4$ (to\v{c}ke $(i,j)$, $0\le i\le 4$, $0\le j\le 4$, 
$(i,j)\ne (3,2),(2,3),(0,2),(1,1)$). 
S Christofidesovim pribli\v{z}nim postopkom
poi\v{s}\v{c}i pribli\v{z}ek za najkraj\v{s}i obhod trgovskega potnika.