Šaku ir ribu metodas


Pavyzdys- vagies uzdavinys:

\begin{eqnarray}\max_x \sum_{i=1}^m c_i x_i \\
\sum_{i=1}^m g_i x_i \le g,\ x_i =\{0,1\}.
\end{eqnarray}


Ribos gaunamos iš pagalbiniu LP uzdaviniu:

\begin{eqnarray}C_1=c_1 +\max_x \sum_{i=2}^m c_i x_i \\
g_1+\sum_{i=1}^m g_i x...
...
C_0=\max_x \sum_{i=2}^m c_i x_i \\
\sum_{i=2}^m g_i x_i \le g
\end{eqnarray}


"Kertam" šaka $0$, jei $C_0 < c_1$.
Šaka $0$ reiškia neimti 1-jo daikto,
šaka $1$- imti.



jonas mockus 2004-03-01