beweis polyeder beschränkt

14.11.2009, 18:27

chow

beweis polyeder beschränkt

hi,

wie groß muss die anzahl der ungleichungen (=m)

$\begin{eqnarray*} a_{11}*x_1 + a_{12}*x_2+...+a_{1n}*x_n \leq b_1 ... a_{m1}*x_1 + a_{m2}*x_2+...+a_{mn}*x_n \leq b_m \end{eqnarray*}$

mindestens sein, damit die lösungsmenge (=zulässiger bereich eines LP) beschränkt ist. (lösungsmenge nicht leer)

intuitiv habe ich mir überlegt dass m > n gelten muss, da ich anschaulich im R² mindestens drei geraden (edit: halbräume) benötige um einen beschränkten bereich zu definieren.

sitze jetzt schon einige zeit daran und mir fällt nicht ein wie ich das zeigen könnte. habe bereits das ungleichungssystem in ein gleichungssystem (mit $\begin{eqnarray*} x \in R^{n+m}, x \geq 0 \end{eqnarray*}$ ) überführt. aber daraus konnte ich dann auch keine aussagen über die beschränktheit herleiten. ^^

würde mich über ein paar tips freuen wie man da am besten heran geht. danke! Tanzen

14.11.2009, 18:57

Mystic

Auf diesen Beitrag antworten »

RE: beweis polyeder beschränkt
Kann es sein, dass du vergessen hast, dass du bei deinem LP von vornherein schon n Beschränkungen durch die Nichtnegativitätsbedingungen hast? verwirrt

Es geht also hier um die Frage, wieviele Bedingungen von deiner Sorte brauchst du noch zusätzlich, damit der zulässige Bereich dann garantiert beschränkt ist?

14.11.2009, 19:13

chow

Auf diesen Beitrag antworten »

ok, nochmal anders formuliert:

ich hab meinen zulässigen bereich gegeben als

$\begin{eqnarray*} X=\{x | A*x \leq b\} x \in \mathbb{R}^n, A \in \mathbb{R}^{m x n}, b \in \mathbb{R}^m \end{eqnarray*}$

unter der vorraussetzung $\begin{eqnarray*} X \neq \{\} \end{eqnarray*}$ und $\begin{eqnarray*} X \end{eqnarray*}$ beschränkt muss jetzt eine untere schranke für m gefunden werden. nicht negativitätsbedingungen sind in der aufgabenstellung keine gegeben.

oder anders: wieviel ungleichungen (halbraumschnitte) benötige ich mindestens um einen beschränkten polyeder zu definieren.

14.11.2009, 19:20

Mystic

Auf diesen Beitrag antworten »

RE: beweis polyeder beschränkt

Zitat:

Original von chow
sitze jetzt schon einige zeit daran und mir fällt nicht ein wie ich das zeigen könnte. habe bereits das ungleichungssystem in ein gleichungssystem (mit $\begin{eqnarray*} x \in R^{n+m}, x \geq 0 \end{eqnarray*}$ ) überführt. aber daraus konnte ich dann auch keine aussagen über die beschränktheit herleiten. ^^

Kannst du mir dann den Sinn von $\begin{eqnarray*} x \ge 0 \end{eqnarray*}$ oben erläutern? verwirrt

14.11.2009, 19:30

chow

Auf diesen Beitrag antworten »

RE: beweis polyeder beschränkt

Zitat:

Kannst du mir dann den Sinn von $\begin{eqnarray*} x \ge 0 \end{eqnarray*}$ oben erläutern?

ich hab das ungleichungssystem
$\begin{eqnarray*} A*x \leq b, A \in R^{m x n}, x \in R^n, b \in R^m \end{eqnarray*}$
in ein gleichunggsystem
$\begin{eqnarray*} A'*x' = b', x' \geq 0, A' \in R^{mx(m+n)}, x' \in R^{m+n}, b \in R^m \end{eqnarray*}$
überführt, um zu sehen ob sich damit vllt. argumentieren lässt. edit: das hab ich mir allerdings überlegt und hat mit der aufgabenstellung nichts zu tun. ><

14.11.2009, 19:47

Mystic

Auf diesen Beitrag antworten »

Glaub mir einfach, dass auch für das Ungleichungssystem bereits $\begin{eqnarray*} x \ge 0 \end{eqnarray*}$ gelten muss, andernfalls eine Überführung in ein Gleichungssystem in der von dir genannten Art i. allg. gar nicht möglich wäre...

Unter dieser Bedingung kommt man dann mit einer einzigen weiteren Ungleichung vom Typ $\begin{eqnarray*} \le \end{eqnarray*}$ aus, allerdings nur, wenn darin auch alle $\begin{eqnarray*} x_i \end{eqnarray*}$ , i=1,2,...,n, mit einem Koeffizienten > 0 wirklich vorkommen... Ist die letztere Bedingung nicht erfüllt, braucht man weitere... Insofern ist die Aufgabe gar nicht klar zu beantworten...

Edit: Ok, es war die Mindestanzahl gefragt, und die wäre dann eben 1 zusätzlich zu den NNB, bei meiner Interpretation der Aufgabe... Hat man keine NNB muss man diese durch mindestens die gleiche Anzahl von Unglechungen ersetzen...

14.11.2009, 19:54

chow

Auf diesen Beitrag antworten »

Zitat:

jo, sorry du hast recht. die überführung ungleichungssystem -> gleichungssystem die ich vollzogen habe ist einfach falsch.

es muss per aufgabenstellung allerdings _nicht_ $\begin{eqnarray*} x \geq 0 \end{eqnarray*}$ gelten.

14.11.2009, 20:02

Mystic

Auf diesen Beitrag antworten »

Sorry, da muss ich dann passen, obwohl ich noch immer anzweifle, ob dies nicht eine Voraussetzung ist, die einfach weggelassen wurde, weil sie selbstverständlich ist...

Edit: Habe oben noch was reineditiert für den Fall ohne NNB, vielleicht kannst ja damit was anfangen...

Neue Frage »

Antworten »

beweis polyeder beschränkt

Verwandte Themen