Tischlermeister H. plant sein kommendes Arbeitsjahr. Maximal 1200 Stunden will er sich der Erzeugung von Tischen bzw. Sesseln widmen, den Rest der Zeit reserviert er für Reparaturarbeiten.

• Die Produktion eines Tisches dauert 2 Stunden und benötigt 0.8 Einheiten Holz.
• Für die Fertigung eines Sessels benötigt er 4 Stunden und verbraucht 0.4 Einheiten Holz.

Es stehen ihm maximal 282 Einheiten Holz pro Jahr zur Verfügung.

Der Deckungsbeitrag eines Tisches beträgt EUR 90, der Deckungsbeitrag eines Sessels beträgt EUR 60. (Darin sind alle Kosten - z.B. für Holz - berücksichtigt.)

Erstellen Sie ein Lineares Programm, mit dem Ziel, durch einen optimalen Produktmix den gesamten Deckungsbeitrag zu maximieren.

Wir bezeichnen mit \(x_t\) die Anzahl der produzierten Tische und mit \(x_c\) die Anzahl der Sessel.
Das Ziel ist es, den Gesamtdeckungsbeitrag zu maximieren:

\(f(x_t,x_c)=90\, x_t + 60\, x_c\to\max_{x_t,x_c}\)

Die Optimierung unterliegt den folgenden Nebenbedingungen:

\(\begin{array}{rccr} {\small\text{ Zeitbeschränkung:}}&2.0\, x_t + 4.0\, x_c &\leq& 1200\\ {\small\text{Holzbeschränkung:}}&0.8\, x_t + 0.4\, x_c &\leq& 282 \end{array}\)

Wir bezeichnen mit \(\lambda_Z\) die Bewertung einer Einheit Zeit [EUR/h] und mit \(\lambda_H\) die Bewertung einer Einheit Holz [EUR/EH].
Das Ziel ist es, die Gesamtbewertung der verfügbaren Ressourcen zu minimieren:

\(f(\lambda_Z,\lambda_H)=1200 \lambda_Z + 282 \lambda_H\to\min_{\lambda_Z, \lambda_H}\)

Die Optimierung unterliegt den folgenden Nebenbedingungen:

\(\begin{array}{rccr} {\small\text{Ressourcenverbrauch Tisch:}}&2.0\,\lambda_Z + 0.8\,\lambda_H&\geq& 90\\ {\small\text{Ressourcenverbrauch Sessel:}}&4.0\,\lambda_Z + 0.4\,\lambda_H&\geq& 60 \end{array}\)

Wir betrachten die Lagrange-Funktion des ursprünglichen Optimierungsproblems (des primalen Problems),

\(L(\lambda_Z,\lambda_H,x_t,x_c)=90 x_t + 60 x_c +\lambda_Z(1200-2x_t-4x_c) + \lambda_H(282-0.8x_t-0.4x_c)\)

Aus dem Lagrange-Formalismus wissen wir, dass wir auf der Suche nach einem Sattelpunkt der Lagrange-Funktion sind. Bei einem Maximierungsproblem ist das ein Maximum bezüglich der Variablen \(x_t, x_c\) und ein Minimum bezüglich der Lagrange-Multiplikatoren \(\lambda_Z, \lambda_H\).

Weil es sich um ein lineares Problem handelt (die Zielfunktion und alle Nebenbedingungen sind linear), ist auch das Minimierungsproblem bezüglich der \(\lambda\)s ein lineares Problem.

Umformung der Lagrange-Funktion des primalen Problems:

\(\begin{array}{rcl} L(\lambda_Z,\lambda_H,x_t,x_c)&=&90 x_t + 60 x_c +\lambda_Z(1200-2x_t-4x_c) + \lambda_H(282-0.8x_t-0.4x_c)\\ &=& 1200\lambda_Z + 282 \lambda_H + x_t(90-2\lambda_Z-0.8\lambda_H) + x_c(60-4\lambda_Z-0.4\lambda_H) \end{array}\)

Das sieht schon sehr nach der Lagrange-Funktion einer Optimierung bezüglich der dualen Variablen \(\lambda_Z, \lambda_H\) aus. Mit der Zielfunktion \(f_D= 1200\lambda_Z + 282 \lambda_H \) und mit den ursprünglichen Variablen \(x_t,x_c\) als Lagrange-Multiplikatoren dieses dualen Problems.

Aber: Wir wissen von Kuhn-Tucker, dass die Lagrange-Multiplikatoren eines Minimierungsproblems nicht-positiv sind. Es gilt aber \(x_t,x_c\geq 0\).

Wir machen daher die Substitution

\(\begin{array}{l} \kappa_t = -x_t \leq 0,\ \kappa_c = -x_c \leq 0, \end{array}\)

und erhalten folgende Darstellung der Lagrange-Funktion:

\(L(\lambda_Z,\lambda_H,x_t,x_c) = 1200\lambda_Z + 282 \lambda_H + \kappa_t(-90+2\lambda_Z+0.8\lambda_H) + \kappa_c(-60+4\lambda_Z+0.4\lambda_H).\)

Dies entspricht der Lagrange-Funktion folgender Minimierung unter Ungleichheitsbedingungen:

\(f(\lambda_Z,\lambda_H)=1200 \lambda_Z + 282 \lambda_H\to\min_{\lambda_Z, \lambda_H}\)

\(\begin{array}{rcl} 2.0\,\lambda_Z + 0.8\,\lambda_H&\geq& 90\\ 4.0\,\lambda_Z + 0.4\,\lambda_H&\geq& 60 \end{array}\)

Dieses Problem ist das sogenannte duale Problem zum ursprünglichen, primalen Problem.