Wie viele zulässige Basislösungen gibt es?

Question

Text erkannt:

3. Gegeben ist das folgende lineare Programm (LP):
\( x_{1}+4 x_{2} \rightarrow \max \)
u.d.NB
\( \begin{aligned} x_{1}+x_{2} & \leq 4 \\ x_{2} & \leq 1+2 x_{1} \\ x_{1} & \leq 3 \\ x_{1}, x_{2} & \geq 0 \end{aligned} \)
(a) Lösen Sie das Problem grafisch.
Wie viele zulässige Basislösungen gibt es?
(b) Lösen Sie das Problem mittels Simplexverfahren und markieren Sie die einzelnen Simplexschritte in Ihrer Grafik.
(c) Formulieren Sie das duale Programm und geben Sie dessen optimale Lösung an (inkl. optimalem Zielfunktionswert).
(d) Betrachten Sie folgende Änderungen des Programms (unabhängig voneinander):
i. Der Zielfunktionskoffizient von \( x_{2} \) ist 3 (statt 4).
ii. Die Restriktionskonstante der 1. Nebenbedingung ist 3.5 (statt 4).
iii. Die Restriktionskonstante der 3. Nebenbedingung ist 2 (statt 3).
Erklären Sie anhand Ihrer Grafik, ob die jeweilige Änderung zu einer Änderung der optimalen Basis führt oder nicht.
Können Sie ohne neuerliche Berechnung des optimalen Produktionsprogramms angeben, um wie viel sich jeweils der optimale Zielfunktionswert verändert?
Wenn ja, geben Sie diese Änderung an. Wenn nein, erklären Sie, warum nicht.

Aufgabe:Könnt ihr mir mit dem Rechenweg dieser Aufgabe helfen? Danke im Voraus!

Answer 1

a) Die Nebenbedingungen sind

y≤4-x und y≤1+2x und x≤3 und x≥0 und y≥0

Also ist das Planungsgebiet alles was im 1. Quadranten

durch die blaue , grüne und rote Gerade begrenzt wird.

~draw~ gerade(0|1 1|3);gerade(0|4 4|0);gerade(3|0 3|3);zoom(10) ~draw~

Jetzt die Zielfunktion betrachten als Geradengleichung in der Form

4y+x=b bzw. y = -0,25x + 0,25b

und diese Gerade z.B. erstmal mit b=0 einzeichnen (lila).

Diese Gerade parallel nach oben verschieben so, dass sie gerade

noch das Planungsgebiet berührt (hellblau) .

~draw~ gerade(0|1 1|3);gerade(0|4 4|0);gerade(3|0 3|3);gerade(0|0 4|-1);gerade(5|2 1|3);zoom(10) ~draw~

Dann auf der y-Achse ablesen 0,25b=3,25 also b=13. Das ist

das Maximum der Zielfunktion.

Wenn ich mich recht erinnere, entsprechen die zulässigen

Basislösungen immer den Ecken des Planungsgebietes.

Das wären hier (0;0), (3;0), (3;1), (1;3) und (0;1) also 5 Stück.