McCormick-Ungleichungen

Wir betrachten die Funktion

f(x1,x2):=x1x2f(x_1,x_2):=x_1x_2

mit f:Q:=[x‾1,xˉ1]×[x‾2,xˉ2]→Rf:Q:=\left[\underline{x}_{1}, \bar{x}_{1}\right] \times\left[\underline{x}_{2}, \bar{x}_{2}\right] \rightarrow \mathbb{R} .

Wobei x‾\underline{x} die unteren Schranken und xˉ\bar{x} die oberen Schranken darstellen.

Die McCormick-Ungleichungen sind:

  1. w≥x‾2x1+x‾1x2−x‾1x‾2w\geq\underline{x}_2x_1+\underline{x}_1x_2-\underline{x}_1\underline{x}_2
  2. w≥xˉ2x1+xˉ1x2−xˉ1xˉ2w\geq \bar{x}_2x_1+\bar{x}_1x_2-\bar{x}_1\bar{x}_2
  3. w≤x‾2x1+xˉ1x2−xˉ1x‾2w\leq\underline{x}_2x_1+\bar{x}_1x_2-\bar{x}_1\underline{x}_2
  4. w≤xˉ2x1+x‾1x2−x‾1xˉ2w\leq \bar{x}_2x_1+\underline{x}_1x_2-\underline{x}_1\bar{x}_2

Wir können damit also konvexe Hüllen von bilinearen Ausdrücken durch Ungleichungen darstellen.

Bildschirmfoto 2022-07-29 um 09.37.43.png

Beweis: Berechnung durch verschiedene Kombinationen von

0≤(x1−x‾1)(x2−x‾2)0\leq(x_1-\underline{x}_1)(x_2-\underline{x}_2)