Lineare Optimierung grafisch und analytisch

Question

ich habe als Aufgabe ein lineares Optimierungsproblem bekommen: max x₁ − 2x₂

Als Nebenbedingungen gibt es :
3x₁ + 2x₂ ≤ 6
x₁ + x₂ ≥ 1
x₁ ≤ 3x₂
x₁ ≥ 0
x₂ ≥ 0

Das soll ich nun graphisch und auch analytisch lösen. Allerdings weiß ich nicht wirklich wie ich dabei vorgehen soll.
Es wäre toll, wenn mir jemand helfen kann.

Freundliche Grüße

Linda

Answer 1

3x1 + 2x2 ≤ 6
x1 + x2 ≥ 1
x1 ≤ 3x2
x1 ≥ 0
x2 ≥ 0

setzen wir x2 erst einmal y ein und

für x1 - x . Das ist gewohnter

3x + 2y ≤ 6
x + y ≥ 1
x ≤ 3y
x ≥ 0
y ≥ 0 

umstellen
y ≤ ( 6 - 3x ) / 2
y ≥ 1 -x
y ≥ x / 3
x ≥ 0
y ≥ 0

und noch mal mit y = f ( x )
f ( x ) ≤ ( 6 - 3x ) / 2 ( unterhalb blau )
f ( x ) ≥ 1 -x ( über rot )
f ( x ) ≥ x / 3 ( über grün )
x ≥ 0 ( rechts der y-Achse )
f ( x ) ≥ 0 ( oberhalb der x-Achse )

Du kannst die Lösungsfläche ja schon
einmal einzeichnen.

Eckpunkte
( 0 | 3 )
schnittpunkt blau - grün
schnittpunkt grün - rot
( 0 | 1 )

Ich nehme jetzt erst einmal Abendbrot
zu mir.

Comments

Wäre das hier korrekt für die graphische Lösung oder ist da was falsch?

---

Die von mir in meiner Antwort eingestellte
Grafik ist verschwunden.
Ich stelle diese zunächst einmal wieder ein.

---

Als Eckpunkte ergeben sich
( 0 | 3 )
( 18/11 | 6 /11 )
( 3/4 | 1 / 4 )
( 0 | 1 )

max = ( x - 2*y )
-6
6/11
1/4
-2

Ergebnis
x1 = 18/11
x2 = 6 /11
max = 6 / 11

Alle Angaben ohne Gewähr.
Bei Bedarf weiterfragen.

---

Was gneau bringen mir die Dinge aus der letzten Antwort? Könnte man das noch ein wenig erläutern bitte?

---

Dies will ich gerne tun.

Alle Punkte innerhalb der schraffierten Fläche erfüllen
alle Bedingungen
Es gibt jetzt verschiedene Möglichkeiten
max ( x1 - 2 * x2 ) zu bestimmen.
Die einfachste ist : alle Eckpunkte der Fläche
zu bestimmen ( Schnittpunkte der Geraden )
und diese in die Funktion max einzusetzen.
Das habe ich gemacht z.B.
max ( 18/11  - 2 * 6 /11 ) = 6 / 11.
Dies muß für alle 4 Punkte gemacht werden.
Die Ergebnisse stehen oben.
Dann wird der maximalwert herausgefischt.

max Ergebnis
x1 = 18/11
x2 = 6 /11
max = 6 / 11

Ich müßte nochmals nachschauen warum dies
mit den Eckpunkten so ist.

---

Das Ergebnis ist richtig.

Zum Simplex-Algorithmus gibt es den Online-Rechner 

http://simplexrechner.matthias-priebe.de/start.php?template=projekte/simplex1.php

---

Ah ok, vielen dank für die Erklärung dazu.
Das würde dann auch als "analytisch lösen mit hilfe von der graphischen Darstellung" zählen?

Freundliche Grüße und vielen Dank nochmal.

---

Wenn nichts Weiters als "analytische Lösung" gesagt ist, ist das so.

Übungsleiter sind aber bei der Interpretation der Aufgabentexte oft sehr eigenwillig.

Das "mit Hilfe von der graphischen Darstellung" würde ich weglassen. Sie dient eigentlich nur zur Verdeutlichung der Rechnungen. Georgs Lösung wird davon unabhängig, wenn man

y ≤ ( 6 - 3x ) / 2
y ≥ 1 -x
y ≥ x / 3

als Geradengleichungen (mit = statt ≥)  auffasst und die Schnittpunkte nicht abliest sondern berechnet.

---

Hallo Linda,

meine Lösung ist so eine Mischung aus
graphisch und rechnerisch.

Eine graphische Lösung erhält man wenn man
die Zielfunktion einzeichnet
max = x1 − 2x2
max = x − 2 * y
soll den größtmöglichen Wert für max
annehmen:
Als Funktion geschrieben
x − 2 * y = max
2y = x - max
y = x/2 - max / 2
y = 1/ 2 * x - max / 2
Vorgehensweise
Du zeichnest in die Grafik eine x-beliebige
Gerade mit der Steigung  1/2 ein.
Dann verschiebst du diese Gerade parallel
bis das kleinste y erreicht ist. dann ist max
maximal.
So ungefähr.
Schaue im Internet einmal unter " Simplex
" nach.
Dies ist die grafische Lösung ohne Rechnerei.

Damit dürfte die Fragestellung beantwortet
werden können.

Ich bevorzuge die von mir hier dargestellte
Vorgehensweise.