Simplexalgorithmus HILFE

Simplexalgorithmus HILFE !!!!

Habe ein Problem mit folgender Aufgabe:
Minimieren Sie !!! Zielfunktion: x= -40x1 +110x2 - 110x3 + 170x4

Nebenbedingungen
x >= 0 und Ax <=b

A=

0 1 0 1
-1 1 -1 1
-1 0 -1 1
0 0 -1 1

b=
20
15
8
15


aufgrund der vielen (-1) in der Matriz und der Aussage minimieren sie komme ich irgendwie nicht klar.

Wer kann mir helfen ???

Assi

Assi,
wo hast du die Aufgabe her?
Ich gehe davon aus, mit x >= 0 meinst du nicht den Zielwert x0>=0 (es ist ein wenig verwirrend, da du den Zielwert auch mit "X" bezeichnest).

Mein Vorschlag:
In der minimierenden Zielfunktion ist zu erkennen, dass der Zielwert bei steigendem Wert von X1 bzw. X3 sinkt.
In den Nebenbedingungen i.F.v. Ax <=b, x >= 0, b>0, haben alle Aktivitätenkoeffiziente in den Spalten X1 und X3 den Wert "-1" oder "0", d.h. x1 und X3 können beliebig großen Wert annehmen.
Die Folge: es gibt keine endliche Lösung!

Man kann das min.-Problem auch in ein max.-Problem unwandeln und formal argumentieren, wo der zielfunktionskoeffiziente negativ sind, gibt es keine positive Koeffizient in der Aktivitätenmatrix, es gibt also keine endliche Lösung.

Grüße

die Aufgabe stammt aus einer Uniklausur.

Dort steht als Zielfunktion 0(x1,x2,x3,x4) = -40x1 +110x2 -110x3 + 170x4
und Nebenbedingung

x>=0 und Ax <= b

Dementsprechend habe ich dann die Anfangstabelle aufstellt und kam nicht weiter, weil ich rechts nur positive Werte und bei den entsprechenden Zeilen der positiven Spalten dazu nur negative Werte (eben -1) hatte.

Das fand ich dann doch sehr merkwürdig, kann das wirklich in einer Prüfungsklausur gemeint sein ??? !!!!

Was meinst Du denn bzw. wie geht es mit der Umwandlung in ein max.-Problem ?

Habe bei einem Simplexrechner hier im Internet die Aufgabe 1x als minimiere (dabei kam wie auch von uns festgestellt heraus, dass es keine endliche Lösung gibt), und eben 1 mal als maximiere eingegeben, dabei kommt der Rechner zu folgender Lösung x1=7 x2=5 x4=14
Zielfunktionswert: 2820.

Irgendwie versteh ich das jetzt nicht.

:-(((( Gruß Astrid

Min x0= -40x1 +110x2 - 110x3 + 170x4
Umwandlung in ein max.-Problem:
Max -x0= 40x1 -110x2 + 110x3 - 170x4

Warum diese Aufgabe keine endliche Lösung gibt habe ich bereits erklärt.

Bei der max. Aufgabe sieht es natürlich anders aus:
Max x0= -40x1 +110x2 - 110x3 + 170x4

X1 X2 X3 X4 S1 S2 S3 S4 b
Max 40 -110 110 -170 0 0 0 0 0
0 1 0 1 1 0 0 0 20
-1 1 -1 1 0 1 0 0 15
-1 0 -1 1 0 0 1 0 8
0 0 -1 1 0 0 0 1 15

X1 X2 X3 X4 S1 S2 S3 S4 b
Max -130 -110 -60 0 0 0 170 0 1360
1 1 1 0 1 0 -1 0 12
0 1 0 0 0 1 -1 0 7
-1 0 -1 1 0 0 1 0 8
1 0 0 0 0 0 -1 1 7

X1 X2 X3 X4 S1 S2 S3 S4 b
Max 0 -110 -60 0 0 0 40 130 2270
0 1 1 0 1 0 0 -1 5
0 1 0 0 0 1 -1 0 7
0 0 -1 1 0 0 2 -1 15
1 0 0 0 0 0 -1 1 7

X1 X2 X3 X4 S1 S2 S3 S4 b
Max 0 -50 0 0 60 0 40 70 2570
0 1 1 0 1 0 0 -1 5
0 1 0 0 0 1 -1 0 7
0 1 0 1 1 0 2 -2 20
1 0 0 0 0 0 -1 1 7

X1 X2 X3 X4 S1 S2 S3 S4 b
Max 0 0 50 0 110 0 40 20 2820
0 1 1 0 1 0 0 -1 5
0 0 0 0 0 1 -1 0 2
0 0 0 1 1 0 2 -2 15
1 0 0 0 0 0 -1 1 7

Die Lösung ist nun optimal, da alle Zielkoefiziente nicht negativ sind.
X0*=2820
X*= (X1, X2, X3, X4, S1, S2, S3, S4)T
=( 7, 5, 0, 15, 0, 2, 0, 0)T

Grüße

Ja, mit einer Maxierung wäre ich auch zurecht gekommen.

Allerdings stand ja in der Aufgabe eindeutig miniere drin.
Also mir ist es wirklich schleierhaft ..... so etwas als Prüfungsaufgabe ist ja dann ganz schön irritierend.

Trotzdem möchte ich mich bei dir für deine nette Unterstützung
bedanken.

Also VIELEN, VIELEN DANK 🙂)))

Assi