Lineares Ungleichungssystem < Sonstiges < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:50 Sa 11.04.2009 | | Autor: | Novum |
| Aufgabe | Gegeben sei ein allgemeines lineares Ungleichungssystem der Form Ax <= 0 beliebiger Dimension.
Bestimme ob eine Lösungmenge existiert. |
Kennt jemand dafür einen effizienten Algorithmus? Ich brauche nicht die exakte Lösung, sondern will wirklich nur wissen ob eine Lösung existiert.
Das ganze ist auch ein geometrisches Problem, nämlich zu bestimmen, ob der durch die Ungleichungen (Halbräume) definierte konvexer Polyeder, der die Lösungsmenge repräsentiert existiert oder nicht.
Die lineare Programmierung beschäftigt sich mit solchen Problemen, aber dort wird immer von einer unteren Schranke für alle Elemente von x ausgegangen (>=0), was bei mir aber nicht der Fall ist.
Der Simplex-Algorithmus der LP erzeugt z.B. eine initiale Lösung, aber ich verstehe nicht ob diese auch gefunden wird, wenn die Vorbedingung x>=0 nicht gilt.
Grüße,
Axel
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
> Gegeben sei ein allgemeines lineares Ungleichungssystem der
> Form Ax <= 0 beliebiger Dimension.
>
> Bestimme ob eine Lösungmenge existiert.
> Kennt jemand dafür einen effizienten Algorithmus? Ich
> brauche nicht die exakte Lösung, sondern will wirklich nur
> wissen ob eine Lösung existiert.
Der Aufgabentext, so wie Du ihn wiedergegeben hast, verlang eigentlich nur zu bestimmen, ob die Lösungsmenge existiere - und die existiert natürlich immer: gegebenenfalls mag sie leer sein...
Dass für [mm] $Ax\leq [/mm] 0$ eine Lösung existiert ist sicher, Du kannst ja $x=0$ nehmen.
>
> Das ganze ist auch ein geometrisches Problem, nämlich zu
> bestimmen, ob der durch die Ungleichungen (Halbräume)
> definierte konvexer Polyeder, der die Lösungsmenge
> repräsentiert existiert oder nicht.
>
> Die lineare Programmierung beschäftigt sich mit solchen
> Problemen, aber dort wird immer von einer unteren Schranke
> für alle Elemente von x ausgegangen (>=0), was bei mir aber
> nicht der Fall ist.
>
> Der Simplex-Algorithmus der LP erzeugt z.B. eine initiale
> Lösung, aber ich verstehe nicht ob diese auch gefunden
> wird, wenn die Vorbedingung x>=0 nicht gilt.
Wie gesagt: der Aufgabentext verlangt entweder eine Trivialität zu zeigen (dass die Lösungsmenge existiert: und in diesem Falle lautet die Antwort ja, und zwar ganz unabhängig von der genauen Form des Ungleichungssystems) oder etwas sehr Simples (dass die Lösungsmenge nicht leer ist, und für [mm] $Ax\leq [/mm] 0$ lautet die Antwort wohl auch "ja", weil $x=0$ eine Lösung ist).
Aber vielleicht hast Du nur den Aufgabentext nicht richtig wiedergegeben.
|
|
|
|
