Lineare Probleme anschaulich
Über diese App
Lineare Probleme graphisch verstehen und lösen — Zielfunktion, Nebenbedingungen und zulässige Region interaktiv erkunden.
Worum es geht
Ein lineares Programm sucht das Maximum oder Minimum einer linearen Zielfunktion z = c₁x₁ + c₂x₂ unter linearen Nebenbedingungen wie a₁x₁ + a₂x₂ ≤ b und x₁, x₂ ≥ 0. Mit zwei Variablen lässt es sich in der Ebene lösen. Jede Nebenbedingung ist eine Gerade, die die Ebene in eine zulässige und eine unzulässige Hälfte teilt. Der Durchschnitt aller zulässigen Hälften ist der zulässige Bereich, ein konvexes Vieleck. Die Punkte mit gleichem Zielwert liegen auf parallelen Geraden. Ist das Problem lösbar, wird das Optimum immer auch in einer Ecke des zulässigen Bereichs angenommen.
Was die App zeigt
Im Modell-Panel gibst du die Zielfunktion mit max oder min und beliebig viele Nebenbedingungen ein, mit „+ NB“ und „− NB“ fügst du welche hinzu oder entfernst sie. Jede Nebenbedingung erscheint als farbige Gerade, der zulässige Bereich ist schattiert, die optimale Ecke markiert. Über den F-Wert schiebst du die gestrichelte Zielfunktionsgerade parallel durch die Ebene. Das Formel-Panel zeigt das Modell in mathematischer Schreibweise. Ist der zulässige Bereich leer, meldet die App das Problem als unzulässig.
Selbst ausprobieren
Erhöhe den F-Wert, bis die Zielfunktionsgerade den zulässigen Bereich gerade noch berührt: Dort liegt das Optimum, und es ist eine Ecke. Ändere dann die Koeffizienten der Zielfunktion und beobachte, wie das Optimum von Ecke zu Ecke springt. Wird die Zielfunktion parallel zu einer Kante, sind alle Punkte dieser Kante optimal. Füge eine Nebenbedingung hinzu, die den Bereich leer macht, und sieh, wie die App reagiert.
Häufige Fragen
- Wie löst man ein lineares Optimierungsproblem grafisch?
- Man zeichnet jede Nebenbedingung als Gerade und schattiert den zulässigen Bereich. Dann verschiebt man eine Gerade der Zielfunktion parallel, bis sie den Bereich gerade noch berührt. Der Berührpunkt, meist eine Ecke, ist die optimale Lösung.
- Warum liegt das Optimum eines linearen Programms in einer Ecke?
- Die Zielfunktion ist linear, ihre Höhenlinien sind parallele Geraden. Schiebt man sie in Richtung besserer Werte, verlässt sie den konvexen zulässigen Bereich zuletzt an einer Ecke oder entlang einer ganzen Kante. In beiden Fällen ist mindestens eine Ecke optimal.
- Was bedeutet es, wenn ein lineares Programm unzulässig ist?
- Dann gibt es keinen Punkt, der alle Nebenbedingungen gleichzeitig erfüllt, der zulässige Bereich ist leer. Ein solches Problem hat keine Lösung. Davon zu unterscheiden ist ein unbeschränktes Problem, bei dem der Zielwert beliebig groß werden kann.
- Kann ich in der App eigene Aufgaben eingeben?
- Ja. Du legst die Zielfunktion mit max oder min fest und gibst Nebenbedingungen mit Koeffizienten und rechter Seite ein. Nebenbedingungen lassen sich hinzufügen und entfernen, die Grafik passt sich sofort an.
Fach: Operations Research
Mehr aus Operations Research
- Big M: Nebenbedingungen an- und ausschalten
- Dijkstra-Algorithmus
- Ganzzahlig ist anders: LP gegen IP
- Konvexe Mengen, Hülle und Ecken
- Nebenbedingungen verschärfen (Tightening)
- Simplex im Raum
- Simplex-Algorithmus
- Tabu Search am kleinen TSP
Eine VisuApp von heyprof: interaktiv, kostenlos im Browser, ohne Anmeldung. Was ist eine VisuApp? · Alle Apps