Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


43. Lineare Programmierung



Übungen

  1. Skizzieren Sie das Simplex, das durch die Ungleichungen x1 >= 0, x2 >= 0, x3 >= 0, x1 + 2x2 <= 20 und x1 + x2 + x3 <= 10 definiert ist.
  2. Geben Sie die Matrizen-Folge an, die für das Beispiel in diesem Kapitel erzeugt wird, wenn die ausgewählte Pivotspalte das größte q ist, für das a[0,q] negativ ist.
  3. Geben Sie die Matrizen-Folge an, die für das Beispiel in diesem Kapitel erzeugt wird, wenn die Zielfunktion x1 + 5x2 + x3 lautet.
  4. Beschreiben Sie, was geschieht, wenn der Simplex-Algorithmus auf eine Matrix angewandt wird, in der eine Spalte nur Nullen enthält.
  5. Führt der Simplex-Algorithmus die gleiche Anzahl von Schritten aus, wenn die Zeilen der eingegebenen Matrix vertauscht werden?
  6. Geben Sie eine Formulierung des Beispiels für das Rucksack-Problem aus Kapitel 42 als lineare Optimierungsaufgabe an.
  7. Wie viele Pivot-Schritte sind erforderlich, um die lineare Optimierungsaufgabe »Maximiere x1 + ... + xM unter Berücksichtigung der Nebenbedingungen x1, ..., xM <= 1 und x1, ..., xM >= 0« zu lösen?
  8. Konstruieren Sie eine lineare Optimierungsaufgabe, die N Ungleichungen mit zwei Variablen enthält und für die der Simplex-Algorithmus wenigstens N/2 Pivot-Schritte benötigt.
  9. Geben Sie ein dreidimensionales lineares Optimierungsproblem an, welches den Unterschied zwischen der Methode des größten Zuwachses und der Methode des steilsten Abstiegs für die Auswahl der Spalten verdeutlicht.
  10. Modifizieren Sie die in diesem Kapitel angegebene Implementation dahingehend, daß die Koordinaten des der optimalen Lösung entsprechenden Punktes ausgegeben werden.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]