Eckenalgorithmus: eindeutige Lösung? f(x) = - 5x_{1} - 2x_{2} minimieren

Question

liebe Mathegenuis,

ich bin gerade dabei eine Aufgabe mit dem Eckenalgorithmus zu lösen.

Aufgabe:

 f(x) = - 5x₁ - 2x₂ -> min

unter den Nebenbedingungen

x₁ + x₂ ≤ 8
2x₁ + 3x₂ ≤ 18
x₁ ≥ 0
x₂  ≥ 0

Zugehörende begrenzende Geraden:
1) x₁ + x₂ = 8
2) 2x₁ + 3x₂ = 18
3) x₁ = 0
4) x₂ = 0

Nun kommen wir zum Rechenweg:

Ich rechne 4 über 2 = 6 Möglichkeiten, um begrenzende Geraden zu schneiden.

1. Frage: Rechne ich vier über zwei, wegen den vier Nebenbedingungen, oder wegen den Zugehörende begrenzende Geraden?

2. Frage: Wie gehe ich nun weiter vor? Habe die Lösungen vor mir liegen und sehe das ich von 1) und 2) die Schnittmenge bilde, also 1) ∩ 2). Wie weiß ich mit welcher zugehörende begrenzende Geraden die Schnittmenge bilden muss? Und wie komme ich auf die Lösung ? Die Lösung ist im ersten Schritt (x₁,x₂) = (6,2)

Es heißt zu dem: (6; 2) erfüllt die 3. NB und die 4. NB, deshalb liegt eine Ecke vor: (6; 2) mit Wert -34 .

Also wie weiß ich wann ich die Schnittmenge bilden muss und wie komme ich auf die Lösung?

Ich bin euch sehr dankbar und freue mich über Antworten!

Vielen Dank im Voraus und einen schönen Abend. :)

Answer 1

1. Frage: Rechne ich vier über zwei, wegen den vier Nebenbedingungen, oder wegen den Zugehörende begrenzende Geraden?

Sowohl als auch. Jede Nebenbedingung hat hier eine zugehörige begrenzende Grade.

4 Geraden können maximal (4 über 2) Schnittpunkte besitzen. Weil jeweis zwei Geraden maximal einen Schnittpunkt besitzen.

2. Frage: Wie gehe ich nun weiter vor? Habe die Lösungen vor mir liegen und sehe das ich von 1) und 2) die Schnittmenge bilde, also 1) ∩ 2). Wie weiß ich mit welcher zugehörende begrenzende Geraden die Schnittmenge bilden muss? Und wie komme ich auf die Lösung ? Die Lösung ist im ersten Schritt (x1,x2) = (6,2)

Im Zweifel berechnest du alle 6 möglichen Schnittpunkte. Meist kann man sich die Begrenzenden Geraden auch in ein Koordinatensystem einzeichnen und kann leicht erkennen, welche Schnittpunkte die wichtigen sind. Die kann man, wenn sie nicht ablesbar sind nochmals nachrechnen.

Comments

Guten Morgen,

vielen Dank für deine Antwort.

Habe noch zwei Fragen, ich sehe in den Lösungen das ich die Schnittmenge von

1 ∩  2

1 ∩  3

1 ∩  4

2 ∩  3

2 ∩  4

3 ∩  4

bilden muss. Das sind 6 Möglichkeien, aber wie komme ich jetzt drauf das ich genau mit z.B. 2 ∩  4 die Schnittmenge bilden muss?

Und wie komme ich auf die Lösung mit der Ecke?

Wäre sehr nett, wenn du mir da noch weiterhelfen könntest.

Wünsche dir einen schönen Tag.

---

Habe es jetzt eingezeichnet und sehe jetzt, wieso die 6. Möglichkeiten.

Wen ich den Geraden Schnittpunkt berechnen möchte, komme ich auf die (2,6).

Aber wie weiß ich nun, ob eine Ecke vorliegt, oder nicht?

Ich schaue mir die Nebenbedingungen an, und entscheide dann?

Aber wieso liegt dann z.B. bei (0,8) keine Ecke vor? NBs sagen ja nur Größer Gleich Null.

---

Ich erhalte (x₁,x₂) = (2,6), die Lösung sagt jedoch (6,2). Was mache ich falsch?

---

bilden muss. Das sind 6 Möglichkeien, aber wie komme ich jetzt drauf das ich genau mit z.B. 2 ∩  4 die Schnittmenge bilden muss?

Du musst jede Gerade mit jeder anderen Schneiden Also 2 mit 1, 2 mit 3 und 2 mit 4.  Da du 2 mit 1 schon geschnitten hast als du 1 mit 2 untersucht hast fällt das natürlich weg. Verstehst du das?

Ich glaube du hast dir nicht mal die Mühe gemacht dir das gleichzeitig mal zu skizzieren.

~plot~ x=0; 0; 8-x;(18-2x)/3;[[-1|10|-1|10]] ~plot~

Könntest du hier erkennen welches die wirklichen Ecken sind. Wirkliche Ecken erfüllen alle 4 Nebenbedingungen (Ungleichungen).

Ich habe es dir mal eingezeichnet wie es aussehen sollte:

~plot~ x=0; 0; 8-x;(18-2x)/3;{0|6};{6|2};{8|0};{0|0};[[-1|10|-1|10]] ~plot~

Answer 2

 Eckenalgorithmus, hm

Ist der Simplex Algorithmus damit gemeint? Der macht nämlich genau das. Grundsätzlich werden aus den Ungleichungen

den Nebenbedingungen

x1 + x2 ≤ 8
2x1 + 3x2 ≤ 18
x1 ≥ 0
x2  ≥ 0

Gleichungen durch Einführung von Schlupfvariablen

unter den Nebenbedingungen

x1 + x2 +s1= 8
2x1 + 3x2 +s2=18
x1 +s3= 0
x2  + s4= 0

Es gibt also 4 Kandidaten s1,s2,s3,s4 die am Optimum beteiligt sind. Am erfolgversprechendsten sind s1,s2, weil sich im Schnittpunkt beide auf 0 bringen lassen. Ansonsten geht entweder s3=0 oder s4=0 (xor). Also bleiben 3 Möglichkeiten zu testen, wenn man den Simplex nicht rechen kann oder will.