Beweisen Sie, dass jeder Strahl ein Polyeder ist

Ich lese ein Buch über lineare Optimierung und stecke bei folgendem Problem fest:

Beweisen Sie, dass jeder Strahl hereinkommt R N ist ein Polyeder.

Das Buch definiert einen Strahl wie folgt:

Für einen Punkt X 0 ∈ R N und ein Vektor D ∈ R N , ein Strahl ist die Menge

{ X 0 + λ D ∣ ∀ λ ∈ R so dass λ ≥ 0 }

Es definiert auch ein Polyeder als eine Menge von Lösungen für ein System linearer Ungleichungen.

Meine Idee ist, eine lineare Transformation zu finden A , dessen Kern der von aufgespannte Unterraum ist D . Folglich die Menge der Lösungen der Gleichung A X = A X 0 wird eine Linie sein, die den Strahl enthält. Aber es gibt zwei Probleme. Zuerst weiß ich nicht, wie man so etwas findet A . Zweitens weiß ich nicht, was ich als nächstes tun soll.

Jede Hilfe ist willkommen.

Sind Sie sicher, dass ein Polyeder nicht als Lösungsmenge eines Systems linearer Ungleichungen definiert ist, sondern nur als eine lineare Ungleichung? Weil alles, was Sie von einer Ungleichung bekommen, Halbräume sind.
@coffeemath Eigentlich verwendet das Buch die Notation der Vektorungleichheit, aber ich werde meine Frage bearbeiten. Danke.
@coffeemath Durch Vektornotation meine ich A X ≤ B Wo A Ist N × N Matrix und X Und B sind beide N -dimensionale Vektoren. Die Ungleichheit bedeutet, dass jede Komponente von A X kleiner als die entsprechende Komponente von ist B . Ich glaube also, dass dies einem System linearer Ungleichungen entspricht. Es ist auch gleichbedeutend mit dem Schnittpunkt einer endlichen Anzahl von Halbräumen. Sie bestimmt also in allen drei Definitionen ein Polyeder.
Ich bin mir ziemlich sicher, dass ein Satz linearer Ungleichungen nur konvexe Polyeder ergeben kann.
@Arthur Das Buch betrachtet Polyeder als eine Teilmenge konvexer Mengen.
Okay, dann ist das in Ordnung. Ich bin nur daran gewöhnt, dass Polyeder nicht unbedingt als implizite Annahme konvex sind.

Antworten (1)

Lass den Strahl sein R = { X 0 + T D } T ≥ 0 . Lassen D 2 , . . . , D N Grundlage sein für { D } ⊥ , Dann R = { X | D k T ( X − X 0 ) = 0 , D T ( X − X 0 ) ≥ 0 } .

Beweisen Sie, dass jeder Strahl ein Polyeder ist
AntwortenHierDatenschutz-Bestimmungen1y, 0v