Konvexe Mengen, Hülle und Ecken
Über diese App
Die Grundbegriffe hinter der linearen Optimierung in 2D und 3D: konvexe Menge (Sehnenregen findet Gegenbeispiele, Ring und Stern gegen Dreieck und Halbebene), konvexe Hülle (Gummiband und Schrumpffolie), konvexe Linearkombination (Gewichte als Massen, alle Kombinationen füllen die Hülle, negative Gewichte führen hinaus), konvexes Polyeder als Schnitt von Halbräumen (Produktionsplanung, Werkstatt-LP) und Ecke als Extrempunkt (Speichen durch einen Probepunkt; Kreis und Kugel mit unendlich vielen Extrempunkten). Dazu die Zielgerade, die in einer Ecke oder auf einer ganzen Kante hängen bleibt.
Mit Erklärmodus: Ein KI-Tutor führt dich durch die App, zeigt in der Szene, worauf es ankommt, und beantwortet deine Fragen.
Worum es geht
Eine Menge heißt konvex, wenn mit zwei Punkten auch die ganze Verbindungsstrecke in ihr liegt. Konvexe Linearkombinationen sind gewichtete Mittelwerte mit nichtnegativen Gewichten, die sich zu eins summieren; alle zusammen bilden die konvexe Hülle. Ein konvexes Polyeder ist der Durchschnitt endlich vieler Halbräume, also genau das zulässige Gebiet eines linearen Programms. Seine Ecken oder Extrempunkte liegen auf keiner Strecke der Menge im Inneren. Daraus folgt der Hauptsatz der linearen Optimierung: Eine lineare Zielfunktion nimmt ihr Optimum in einer Ecke an.
Was die App zeigt
Sechs Begriffe, jeweils in der Ebene und im Raum. Ein Sehnenregen prüft Formen wie Ellipse, Stern, Ring, Torus oder zwei Kugeln auf Konvexität. Ein Gummiband und eine Schrumpffolie legen sich als konvexe Hülle um Punkte. Gewichte erscheinen als Massen, deren Schwerpunkt die Kombination ist. Halbebenen und Ebenen schneiden das zulässige Gebiet der Produktionsplanung bzw. eines Werkstatt-LP aus. Speichen durch einen Probepunkt zeigen, ob er eine Ecke ist. Zum Schluss schiebt sich die Zielgerade bis zur optimalen Ecke.
Selbst ausprobieren
Zieh die Punkte A und B in den Stern und such eine Strecke, die hinausführt. Verschieb einen inneren Punkt nach außen, bis er die Hülle verändert. Erlaube negative Gewichte und sieh, wie x die Hülle verlässt. Schalte Nebenbedingungen ab und beobachte, wann das Polyeder unbeschränkt wird. Führe den Probepunkt in eine Ecke, auf eine Kante oder an den Kreisrand. Dreh die Zielrichtung, bis zwei Ecken gleich gut sind und eine ganze Kante optimal wird.
Häufige Fragen
- Was ist eine konvexe Menge?
- Eine Menge X ist konvex, wenn für je zwei Punkte x und y aus X auch jeder Punkt λx + (1 − λ)y mit 0 ≤ λ ≤ 1 in X liegt, also die ganze Verbindungsstrecke. Kreisscheiben, Dreiecke und Halbebenen sind konvex, ein Ring oder ein Stern nicht. Der Durchschnitt konvexer Mengen ist wieder konvex.
- Was ist ein Extrempunkt oder eine Ecke?
- Ein Punkt x einer konvexen Menge X heißt Extrempunkt, wenn er sich nicht als λy + (1 − λ)z mit zwei verschiedenen Punkten y, z aus X und 0 < λ < 1 schreiben lässt. Bei einem Polyeder sind das genau die Ecken. Bei einer Kreisscheibe ist jeder Randpunkt extrem, eine Halbebene hat gar keinen Extrempunkt.
- Warum liegt das Optimum eines linearen Programms in einer Ecke?
- Das zulässige Gebiet eines LP ist ein konvexes Polyeder, und jeder Punkt eines beschränkten Polyeders ist eine konvexe Kombination seiner Ecken. Eine lineare Funktion kann auf einer konvexen Kombination nicht größer sein als auf der besten beteiligten Ecke. Darum genügt es, die endlich vielen Ecken zu prüfen; bei Gleichstand ist eine ganze Kante oder Fläche optimal.
- Kann ich in der App zwischen 2D und 3D wechseln?
- Ja. Jeder der sechs Begriffe hat eine Ansicht in der Ebene und eine im Raum, zum Beispiel Gummiband und Schrumpffolie, Dreieck und Tetraeder oder Zielgerade und Zielebene. Die Lupe erklärt jedes Teil der Szene in drei Stufen.
Fach: Operations Research: DP & Heuristiken
Mehr aus Operations Research: DP & Heuristiken
Eine VisuApp von heyprof: interaktiv, kostenlos im Browser, ohne Anmeldung. Was ist eine VisuApp? · Alle Apps