www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Abiturvorbereitung" - Simplex-Algorithmus
Simplex-Algorithmus < Abivorbereitung < Oberstufe < Schule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Abiturvorbereitung"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Simplex-Algorithmus: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 23:33 Do 09.08.2012
Autor: rubi

Aufgabe
Auszug aus einer Abiaufgabe:

Ein lineares Maximierungsproblem führt auf folgendes Simplextableau:

[mm] \vmat{ x & y & z & u & v & w & Ergebnis \\ 1 & 1 & 0 & 1 & 0 & -2 & 20 \\ 0 & 0 & 0 & -1 & 1 & 3 & 70 \\ 0 & 0,2 & 1 & 0 & 0 & -2 & 5 \\ 0 & 0 & 0 & -3 & 0 & -1 & E-78000 } [/mm]

Es gilt x,y,z,u,v,w [mm] \ge [/mm] 0.
Erläutern Sie, warum das Optimierungsproblem mehrere Lösungen besitzt.
Bestimmen Sie alle ganzzahligen Werte von z, für die es optimale Lösungen gibt.

Hallo zusammen,

leider bin ich beim Simplex-Algorithmus nicht ganz so fit.

Folgendes weiß ich:
Die x, z und v sind Basisvariable und y,w und u sind Nicht-Basisvariable.
Aus dem Simplex-Tableau ergibt sich x = 20, z = 5 und v = 70.
Außerdem ist y = u = w =  0.
Als maximale Größe ergibt sich E = 78000.

Da in der letzten Zeile keine positiven Zahlen mehr stehen, ist ein weiterer Simplex-Schritt nicht notwendig.

Woher erkenne ich jedoch, dass es mehrere Lösungen gibt ?

Ich könnte mir folgenden Weg vorstellen, weiß aber nicht, ob das passt.
Aufgrund der letzten Zeile ergibt sich zwangsläufig u = w = 0, ansonsten würde mein E kleiner werden.

Es bleiben daher noch folgende Gleichungen stehen:
1.Zeile: x + y = 20
2.Zeile: v = 70
3.Zeile: 0,2y + z = 5

Da ich nun ein überbestimmtes LGS habe, gibt es mehrere Lösungen:
1.Fall: z = 5, y = 0 und x = 20
2.Fall: z = 4, y = 5 und x = 15
3.Fall: z = 3, y = 10 und x = 10
4.Fall: z = 2, y = 15 und x = 5
5.Fall: z = 1, y = 20 und x = 0
In allen Fällen wäre v = 70 und als Maximum ergäbe sich E = 78000.

Ist dies so richtig ?

Oder müsste ich mit dem Simplex-Tableau einen Simplexschritt durchführen ?
Falls ja, was wäre dann meine Pivotspalte bzw. Pivotzeile ?

Viele Grüße
Rubi

Ich habe diese Frage in keinem anderen Forum gestellt.



        
Bezug
Simplex-Algorithmus: Parametrische Lösungen
Status: (Antwort) fertig Status 
Datum: 09:40 Fr 10.08.2012
Autor: Marcel08

Hallo!


> Auszug aus einer Abiaufgabe:
>  
> Ein lineares Maximierungsproblem führt auf folgendes
> Simplextableau:
>  
> [mm]\vmat{ x & y & z & u & v & w & Ergebnis \\ 1 & 1 & 0 & 1 & 0 & -2 & 20 \\ 0 & 0 & 0 & -1 & 1 & 3 & 70 \\ 0 & 0,2 & 1 & 0 & 0 & -2 & 5 \\ 0 & 0 & 0 & -3 & 0 & -1 & E-78000 }[/mm]
>  
> Es gilt x,y,z,u,v,w [mm]\ge[/mm] 0.
> Erläutern Sie, warum das Optimierungsproblem mehrere
> Lösungen besitzt.
> Bestimmen Sie alle ganzzahligen Werte von z, für die es
> optimale Lösungen gibt.
>  Hallo zusammen,
>
> leider bin ich beim Simplex-Algorithmus nicht ganz so fit.
>
> Folgendes weiß ich:
> Die x, z und v sind Basisvariable und y,w und u sind
> Nicht-Basisvariable.
> Aus dem Simplex-Tableau ergibt sich x = 20, z = 5 und v =
> 70.
> Außerdem ist y = u = w =  0.
>  Als maximale Größe ergibt sich E = 78000.
>  
> Da in der letzten Zeile keine positiven Zahlen mehr stehen,
> ist ein weiterer Simplex-Schritt nicht notwendig.


Nun, solange sich in der F-Zeile noch negative Eintragungen befinden, liegt noch keine optimale Basislösung vor.



> Woher erkenne ich jedoch, dass es mehrere Lösungen gibt ?


Im Tableau mit der erhaltenen optimalen Lösung ist für mindestens eine Nichtbasisvariable der Eintrag in der F-Zeile gleich 0. Würde man diese Variable in die Basis aufnehmen, so erhielte man eine weitere optimale Basislösung. Mit zwei optimalen Basislösungen [mm] x_{1} [/mm] und [mm] x_{2} [/mm] sind auch alle durch Konvexkombinationen

[mm] x=\lambda*x_{1}+(1-\lambda)*x_{2}, [/mm] mit [mm] \lambda\in(0,1) [/mm]


erhältlichen Nichtbasislösungen optimal. Diesen Fall bezeichnet man auch als duale Degeneration, da eine Basisvariable des dualen Problems den Wert 0 besitzt.



> Ich könnte mir folgenden Weg vorstellen, weiß aber nicht,
> ob das passt.
> Aufgrund der letzten Zeile ergibt sich zwangsläufig u = w
> = 0, ansonsten würde mein E kleiner werden.
>
> Es bleiben daher noch folgende Gleichungen stehen:
> 1.Zeile: x + y = 20
>  2.Zeile: v = 70
>  3.Zeile: 0,2y + z = 5
>  
> Da ich nun ein überbestimmtes LGS habe, gibt es mehrere
> Lösungen:
> 1.Fall: z = 5, y = 0 und x = 20
>  2.Fall: z = 4, y = 5 und x = 15
>  3.Fall: z = 3, y = 10 und x = 10
>  4.Fall: z = 2, y = 15 und x = 5
>  5.Fall: z = 1, y = 20 und x = 0
>  In allen Fällen wäre v = 70 und als Maximum ergäbe sich
> E = 78000.
>
> Ist dies so richtig ?
>
> Oder müsste ich mit dem Simplex-Tableau einen
> Simplexschritt durchführen ?


s.o.



> Falls ja, was wäre dann meine Pivotspalte bzw. Pivotzeile
> ?


Pivotspalte t: Nun, du suchst diejenige Spalte t mit dem kleinsten (negativen) Wert in der F-Zeile.

Pivotzeile s: Bestimme eine Zeile s für die gilt: [mm] \bruch{b_{s}'}{a_{st}'}=min\vektor{\bruch{b_{i}'}{a_{it}'}|i=1,...,m; {mit:} {a_{it}'}>0} [/mm]



> Viele Grüße
>  Rubi
>  
> Ich habe diese Frage in keinem anderen Forum gestellt.





Viele Grüße, Marcel

Bezug
                
Bezug
Simplex-Algorithmus: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 19:09 Fr 10.08.2012
Autor: rubi

Hallo zusammen,

was ist denn eine "optimale Basislösung" ?

Bisher habe ich gedacht (und auch in Schulbüchern so nachgelesen), dass der Simplexalgorithmus bei einem Maximieriungsproblem sein Optimum erreicht hat, wenn in der letzten Zeile (damit ist vermutlich die "F-Zeile" gemeint) keine positiven Zahlen mehr stehen.
Und da dies in dem Tableau der Fall ist, bin ich der Meinung, dass E = 78000 bereits schon das Maximum darstellt.

Ist dies falsch ??

Wenn ich in einem nächsten möglichen Pivotschritt die 2.Spalte (Also y) zur Pivotspalte mache und die erste Zeile als Pivotzeile erhalte ich folgendes Tableau:

[mm] \vmat{ x & y & z & u & v & w & Ergebnis \\ 1 & 1 & 0 & 1 & 0 & -2 & 20 \\ 0 & 0 & 0 & -1 & 1 &3 & 70 \\ 1 & 0 & -5 & 1 & 0 & 8 & -5 \\ 0 & 0 & 0 & -3 & 0 & -1 & E-78000 } [/mm]

Daraus würde sich ergeben: x = u = w = 0
y = 20, z = 1, v = 70
Und diese Lösung habe ich ja als 5.Fall in meiner ursprünglichen Frage auch gehabt.

Also gibt es für z = 1,2,3,4,5  optimale Lösungen, die jeweils E = 78000 ergeben.  

Stimmt das ?

Viele Grüße
Rubi


Bezug
                        
Bezug
Simplex-Algorithmus: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 15:07 Sa 11.08.2012
Autor: rubi

kann mir niemand helfen ?

Bezug
                                
Bezug
Simplex-Algorithmus: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 21:58 Di 14.08.2012
Autor: rubi

kann mir jemand helfen ?

Bezug
                                        
Bezug
Simplex-Algorithmus: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 21:58 Di 14.08.2012
Autor: rubi

das ganze nochmals als Frage, da ich noch keine Antwort bekommen habe.

Bezug
                        
Bezug
Simplex-Algorithmus: Antwort
Status: (Antwort) fertig Status 
Datum: 15:50 Mi 15.08.2012
Autor: Stoecki

hallo ruby,

deine lösung ist in ordnung. du kannst das aber auch direkt ohne berechnung im ersten tableau sehen, dass es weitere lösungen geben muss.

die letzte zeile in deinem tableau gibt dir die sog reduzierten kosten an. ist der wert einer nicht basisvariable 0, so weißt du, dass du diese immer ans pivotspalte verwenden kannst, ohne den zielfunktionswert zu ändern. du kannst dann natürlich die expliziten lösungen so ausrechneen, wie du es gemacht hast.

der kommentar von marcel, dass für optimalität alle eintraäge der letzten zeile nichtnegativ sein müssen stimmt im übrigen nur, wenn man minimiert. von daher ist dein gegebenes tableau optimal.

gruß bernhard

Bezug
                                
Bezug
Simplex-Algorithmus: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 15:41 Do 16.08.2012
Autor: rubi

Hallo Bernhard,

danke, deine Antwort hilft mir deutlich weiter.

Ich habe nur noch eine Frage:
Du schreibst
"ist der wert einer nicht basisvariable 0, so weißt du, dass du diese immer ans pivotspalte verwenden kannst, ohne den zielfunktionswert zu ändern"

Ist es nich so, dass die Nicht-Basisvariablen sowieso = 0 gesetzt werden.
Im ersten Tableau sind y = u = w = 0, da sie Nicht-Basisvariable sind.
Kann ich jetzt einfach eine dieser Variablen als Pivotspalte wählen und es bleibt beim optimalen Wert ?

Woher weiß ich dann, dass es unendlich viele Lösungen gibt ?

Viele Grüße
Rubi

Bezug
                                        
Bezug
Simplex-Algorithmus: Antwort
Status: (Antwort) fertig Status 
Datum: 08:56 Fr 17.08.2012
Autor: Stoecki


> Hallo Bernhard,
>  
> danke, deine Antwort hilft mir deutlich weiter.
>
> Ich habe nur noch eine Frage:
> Du schreibst
>  "ist der wert einer nicht basisvariable 0, so weißt du,
> dass du diese immer ans pivotspalte verwenden kannst, ohne
> den zielfunktionswert zu ändern"
>  
> Ist es nich so, dass die Nicht-Basisvariablen sowieso = 0
> gesetzt werden.

du missverstehst mich hier. ich meinte in der unteren zeile in deinem tableau. die werte die dort stehen geben die sog. reduzierten kosten an. sind diese null, weißt du dass ein basiswechsel die zielfunktion nicht beeinflusst. du hingegen meintest die werte der entscheidungsvariablen und in dem punkt hast du recht. ws nicht in der basis steht wird auf 0 gesetzt.

> Im ersten Tableau sind y = u = w = 0, da sie
> Nicht-Basisvariable sind.
> Kann ich jetzt einfach eine dieser Variablen als
> Pivotspalte wählen und es bleibt beim optimalen Wert ?
>  
> Woher weiß ich dann, dass es unendlich viele Lösungen
> gibt ?
>  
> Viele Grüße
>  Rubi

gruß bernhard

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Abiturvorbereitung"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de