Uni-Mathe Beispiel — duales lineares Programm Schritt für Schritt mit KI gelöst

Logo
milkyway.chat
Beispiel-Chat · Uni-Level Mathematik · nur LesenEnglishZurück

Löse diese Aufgabe!

GPT-5.6 Sol

Hinweis zur Aufgabenstellung

In der zweiten Nebenbedingung steht am Ende offenbar versehentlich −2y2-2y_2. Da der Term in der y4y_4-Spalte steht, ist sehr wahrscheinlich

−y1−y2−y3−2y4≥−3-y_1-y_2-y_3-2y_4\geq -3

gemeint. Zunächst wird diese beabsichtigte Variante gelöst. Die wörtliche Variante mit −2y2-2y_2 wird am Ende angegeben.

1. Umformung in ein Maximierungsproblem

Durch Multiplikation der Zielfunktion und der Nebenbedingungen mit −1-1 erhält man das äquivalente Problem

max⁡10y1+6y2+12y3+8y4sodass2y1+y2+3y3+y4≤4,y1+y2+y3+2y4≤3,y1,y2,y3,y4≥0.\begin{aligned} \max\quad &10y_1+6y_2+12y_3+8y_4\\ \text{sodass}\quad &2y_1+y_2+3y_3+y_4\leq4,\\ &y_1+y_2+y_3+2y_4\leq3,\\ &y_1,y_2,y_3,y_4\geq0. \end{aligned}

Der optimale Wert des ursprünglichen Minimierungsproblems ist das Negative des optimalen Werts dieses Maximierungsproblems.

2. Das Dualproblem

Zu jeder der beiden Nebenbedingungen gehört eine Dualvariable x1x_1 beziehungsweise x2x_2. Das Dualproblem lautet

min⁡4x1+3x2sodass2x1+x2≥10,x1+x2≥6,3x1+x2≥12,x1+2x2≥8,x1,x2≥0.\begin{aligned} \min\quad &4x_1+3x_2\\ \text{sodass}\quad &2x_1+x_2\geq10,\\ &x_1+x_2\geq6,\\ &3x_1+x_2\geq12,\\ &x_1+2x_2\geq8,\\ &x_1,x_2\geq0. \end{aligned}

Die zulässige Menge liegt jeweils oberhalb der dargestellten Geraden.

Graphische Lösung des Dualproblems

Die relevanten Randpunkte und Zielfunktionswerte sind

(x1,x2)4x1+3x2(0,12)36(2,6)26(4,2)22(8,0)32\begin{array}{c|c} (x_1,x_2)&4x_1+3x_2\\ \hline (0,12)&36\\ (2,6)&26\\ (4,2)&22\\ (8,0)&32 \end{array}

Somit ist die optimale Duallösung

x∗=(4,2)\boxed{x^*=(4,2)}

mit optimalem Wert

4x1∗+3x2∗=22.\boxed{4x_1^*+3x_2^*=22}.

3. Anwendung des komplementären Schlupfs

Da

x1∗=4>0,x2∗=2>0,x_1^*=4>0,\qquad x_2^*=2>0,

müssen beide primalen Nebenbedingungen aktiv sein:

2y1+y2+3y3+y4=4,y1+y2+y3+2y4=3.\begin{aligned} 2y_1+y_2+3y_3+y_4&=4,\\ y_1+y_2+y_3+2y_4&=3. \end{aligned}

Nun betrachten wir die Schlupfvariablen der dualen Nebenbedingungen:

2x1∗+x2∗−10=0,x1∗+x2∗−6=0,3x1∗+x2∗−12=2,x1∗+2x2∗−8=0.\begin{aligned} 2x_1^*+x_2^*-10&=0,\\ x_1^*+x_2^*-6&=0,\\ 3x_1^*+x_2^*-12&=2,\\ x_1^*+2x_2^*-8&=0. \end{aligned}

Die dritte duale Nebenbedingung besitzt positiven Schlupf. Der Satz vom komplementären Schlupf liefert daher

y3∗=0.\boxed{y_3^*=0}.

Damit bleiben die Gleichungen

2y1+y2+y4=4,y1+y2+2y4=3.\begin{aligned} 2y_1+y_2+y_4&=4,\\ y_1+y_2+2y_4&=3. \end{aligned}

Setzen wir y4=ty_4=t, so folgt

y1=1+t,y2=2−3t,y3=0.y_1=1+t,\qquad y_2=2-3t,\qquad y_3=0.

Aus der Nichtnegativität ergibt sich

0≤t≤23.0\leq t\leq\frac23.

Es gibt also nicht nur eine, sondern eine ganze Strecke optimaler Lösungen:

y∗(t)=(1+t,  2−3t,  0,  t),0≤t≤23.\boxed{ y^*(t)= \left(1+t,\;2-3t,\;0,\;t\right), \qquad 0\leq t\leq\frac23 }.
Menge der optimalen Primallösungen in der (y₄,y₂)-Ebene

Beispielsweise kann man die besonders einfache Lösung

y∗=(1,2,0,0)\boxed{y^*=(1,2,0,0)}

wählen. Ihr ursprünglicher Zielfunktionswert ist

−10⋅1−6⋅2−12⋅0−8⋅0=−22.-10\cdot1-6\cdot2-12\cdot0-8\cdot0=-22.

Damit lautet das Ergebnis für die beabsichtigte Aufgabenfassung:

min⁡=−22.\boxed{\min=-22}.

Falls tatsächlich −2y2-2y_2 gemeint ist

Dann lautet die zweite umgeformte Nebenbedingung

y1+3y2+y3≤3.y_1+3y_2+y_3\leq3.

Das Dualproblem enthält dann insbesondere die Bedingung

x1≥8.x_1\geq8.

Seine optimale Lösung ist

x∗=(8,0),4x1∗+3x2∗=32.x^*=(8,0),\qquad 4x_1^*+3x_2^*=32.

Durch komplementären Schlupf folgt

y∗=(0,0,0,4),\boxed{y^*=(0,0,0,4)},

und der ursprüngliche minimale Zielfunktionswert wäre in dieser wörtlichen Lesart

min⁡=−32.\boxed{\min=-32}.

Alternative bei wörtlicher Lesart mit −2y₂
Eingabe im Beispiel deaktiviert. Starte einen eigenen Chat, um selbst zu rechnen.