<reponame>juresternad/or-zbirka<filename>naloge/lobisti.tex
\begin{naloga}{<NAME>}{Izpit OR 29.8.2017}
\begin{vprasanje}
V veliki multinacionalni korporaciji želijo,
da bi se zakonodaja spremenila v njihov prid.
V ta namen so najeli $m$ lobistov,
ki se bodo pogajali z $n$ političnimi strankami,
da pridobijo njihovo podporo pri spremembi zakonodaje.
Vsak lobist se bo pogajal s samo eno stranko;
k vsaki stranki lahko pošljejo več lobistov.
Naj bo $p_{ij}$ ($0 \le i \le m$, $1 \le j \le n$) verjetnost,
da pridobijo podporo stranke $j$,
če se z njo pogaja $i$ lobistov
(lahko predpostaviš $p_{i-1,j} \le p_{ij}$ za vsaka $i, j$).
Verjetnosti za različne stranke so med seboj neodvisne.
Maksimizirati želijo verjetnost,
da bodo lobisti pridobili podporo vseh $n$ političnih strank.

\begin{enumerate}[(a)]
\item Zapiši rekurzivne enačbe za reševanje danega problema.
\item Naj bo $m = 6$ in $n = 3$.
K vsaki stranki želijo poslati vsaj enega lobista
(tj., $p_{0j} = 0$ za vsak $j$),
vrednosti $p_{ij}$ za $i \ge 1$ pa so podane v spodnji tabeli.
$$
\begin{array}{c|ccc}
p_{ij} & 1 & 2 & 3 \\ \hline
1 & 0.2 & 0.4 & 0.3 \\
2 & 0.5 & 0.5 & 0.4 \\
3 & 0.7 & 0.5 & 0.8 \\
4 & 0.8 & 0.6 & 0.9 \\
\end{array}
$$
Za dane podatke reši problem z zgoraj zapisanimi enačbami.
\end{enumerate}
\end{vprasanje}

\begin{odgovor}
\begin{enumerate}[(a)]
\item Naj bo $q_{ij}$ največja verjetnost, ki jo lahko dosežejo,
da pridobijo podporo prvih $j$ strank,
če k njim pošljejo $i$ lobistov.
Določimo začetne pogoje in rekurzivne enačbe.
\begin{align*}
q_{i1} &= p_{i1} && (1 \le i \le m) \\
q_{ij} &= \max\set{q_{h,j-1} p_{i-h,j}}{0 \le h \le i}
&& (2 \le j \le n, 0 \le i \le m)
\end{align*}
Vrednosti $q_{ij}$ računamo v leksikografskem vrstnem redu glede na $(j, i)$.
Največjo verjetnost, da pridobijo podporo vseh $n$ strank,
dobimo kot $q^* = q_{mn}$.

\item Ker velja $p_{0j} = 0$ za vsak $j$,
bo veljalo $q_{ij} = 0$ za vse $i < j$.
Tako lahko v zgornji rekurzivni enačbi
upoštevamo le primere z $j-1 \le h \le i-1$.
Izračunajmo torej vrednosti $q_{i2}$ ($2 \le i \le 5$) in $q^* = q_{63}$.
\begin{alignat*}{2}
q_{22} &= 0.2 \cdot 0.4 &&= 0.08 \\
q_{32} &= \max\{0.2 \cdot 0.5, \underline{0.5 \cdot 0.4}\} &&= 0.2 \\
q_{42} &= \max\{0.2 \cdot 0.5, 0.5 \cdot 0.5, \underline{0.7 \cdot 0.4}\} &&= 0.28 \\
q_{52} &= \max\{0.2 \cdot 0.6, 0.5 \cdot 0.5, \underline{0.7 \cdot 0.5}, 0.8 \cdot 0.4\} &&= 0.35 \\
q_{63} &= \max\{0.08 \cdot 0.9, \underline{0.2 \cdot 0.8}, 0.28 \cdot 0.4, 0.35 \cdot 0.3\} &&= 0.16
\end{alignat*}
Največja verjetnost je torej $q^* = q_{63} = 0.16$.
Poiščimo še optimalno razporeditev lobistov.
\begin{align*}
q_{63} &= q_{32} p_{33} && \text{$3$ lobisti k tretji stranki} \\
q_{32} &= q_{21} p_{12} && \text{$1$ lobist k drugi stranki} \\
q_{21} &= p_{21}        && \text{$2$ lobista k prvi stranki}
\end{align*}
\end{enumerate}
\end{odgovor}
\end{naloga}
