Heuristik von Konno für bilineare Programme (Konno's heuristic for bilinear programs)
\(\large
(\text{BLP})~~\left\{~~
\begin{align*}
& \begin{aligned}
& \rlap{\text{Max.}}\phantom{\text{u. d. N.}} && \sum_{j=1}^n d_j\cdot\pi_j\cdot v_j+\sum_{j=1}^n c_j\cdot\pi_j+\sum_{j=1}^n \bar{c}_j{}\cdot v_j \\
\end{aligned} \\
& \begin{aligned}
& \text{u. d. N.} && \sum_{j=1}^n a_{ij}\cdot\pi_j \ge b_i && (i=1, \ldots, m)\\
& && \sum_{j=1}^n \bar{a}_{ij}{}\cdot v_j \ge{} \bar{b}_i && (i=1, \ldots, \bar{m})\\
& && \pi_j,~v_j \ge 0 && (j=1, \ldots, n)
\end{aligned}
\end{align*}\right.
\)
In Vektorschreibweise: \(\large (\text{BLP})~~\left\{~~ \begin{align*} & \text{Max.} && \pi^\top D\,v+c^\top\pi +\bar{c}^\top\pi\\ & \text{u. d. N.} && A\pi \ge b \\ & && \bar{A}v \ge \bar{b} \\ & && \pi,~v\ge 0 \end{align*}\right. \) |
\(\ast\) | \(\pi_j\) | \(j\)-te Variable vom Typ \(\pi\), z. B. Transferpreis für Lieferbeziehung \(j\) |
\(b_i\) | Rechte Seite der \(i\)-ten Nebenbedingung in \(\pi\)-Variablen | |
\(\bar{b}_i\) | Rechte Seite der \(i\)-ten Nebenbedingung in \(v\)-Variablen | |
\(c_j\) | Zielfunktionskoeffizient von Variable \(\pi_j\) | |
\(\bar{c}_j\) | Zielfunktionskoeffizient von Variable \(v_j\) | |
\(d_j\) | Zielfunktionskoeffizient von Produkt \(\pi_j\cdot v_j\) | |
\(m\) | Anzahl der Nebenbedingungen in \(\pi\)-Variablen | |
\(\bar{m}\) | Anzahl der Nebenbedingungen in \(v\)-Variablen | |
\(n\) | Anzahl der \(\pi\)- bzw. Anzahl der \(v\)-Variablen | |
\(\ast\) | \(v_j\) | \(j\)-te Variable vom Typ \(v\), z. B. Liefermenge für Lieferbeziehung \(j\) |
Heuristische Lösung des bilinearen Programms:
Für fixierte Werte der \(v\)- bzw. \(\pi\)-Variablen erhält man lineare Programm
\( (\text{BLP}(v))~~\left\{~~ \begin{align*} & \text{Max.} && (c^\top +v^\top D^\top)\,\pi\\ & \text{u. d. N.} && A\pi \ge b \\ & && \pi\ge 0 \end{align*}\right. \) |
und
\( (\text{BLP}(\pi))~~\left\{~~ \begin{align*} & \text{Max.} && (\bar{c}^\top +\pi^\top D)\,v\\ & \text{u. d. N.} && \bar{A}v \ge \bar{b} \\ & && v\ge 0 \end{align*}\right. \) |