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: