Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Beweis Ecke Basis Polyeder

Beweis Ecke Basis Polyeder

Universität / Fachhochschule

Sonstiges

Tags: Lineare Optimierung, Sonstiges

anonymous

09:47 Uhr, 02.12.2014

Guten Morgen,

ich stehe wieder mal bei einem Beweis an und würde mich freuen, wenn mir jemand weiterhelfen kann.

Ein Punkt

x \in P

ist eine Ecke von

P

genau dann, wenn die zu

x

gehörende Basis von A linear unabhängig ist.
Wobei

P = {x | A x = b, x \geq 0}

der zulässige Bereich von dem linearen Programm

max c^{T} \cdot x,

so dass

A \cdot x = b, x \geq 0

ist.

Beweis: Sei

x

eine Ecke von

P

und I

= {i | x_{i} > 0}

. Angenommen,

{a^{(i)} | i \in I}

wäre lin. abhängig. Dann gibt es Zahlendi,

i \in I,

die nicht alle gleich Null sind, so dass

\sum_{i \in I} d_{i} a^{(i)} = 0

. Setzen wir

d_{j} = 0

für alle

j \in {1, ... . ., n} \ I,

dann ist

A \cdot d = 0

für

d = {(d_{1}, ..., d_{n})}^{T}

.
Wir zeigen, dass

y = x - θ \cdot d

und

z = x + θ \cdot d \in P

liegen, wobei

θ = min {\frac{x_{i}}{| d_{i} |} | i \in I, d_{i}

ungleich null

}

> 0

.

Wg.

A \cdot d = 0

ist

A \cdot y = b = A \cdot z

. Sei

1 \leq I \leq n

. Ist

i \notin I,

dann ist

d_{i} = 0

und somit

y_{i} = 0 = z_{i}

. Ist

i \in I

und

d_{i} = 0,

so ist

y_{i} = x_{i} = z_{i}

. Ist

i \in I

und

d_{i} \neq,

dann ist

θ \cdot | d_{i} | \leq \frac{x_{i}}{| d_{i} |} \cdot | d_{i} | = x_{i}

und deshalb

y_{i} = x_{i} - θ \cdot d_{i} \geq 0

und

z_{i} = x_{i} + θ \cdot d_{i} \geq 0

. Also liegen

y

und

z \in P

. Die Punkte

y

und

z

sind wg

θ > 0

von

x

verschieden und es gilt

x = \frac{1}{2} \cdot y + \frac{1}{2} \cdot z

. Also ist

x

widersprüchlicherweise keine Ecke von

P

.

Das ist der erste Teil des Beweises.

Zu meinen Fragen:

Zuerst wird

d

mit 0 Komponenten erweitert um im

R^{n}

zu sein, damit eine Multiplikation mit A möglich ist, oder?

A \cdot d = 0

ist so, weil es lin. abhängig ist, oder? Also wir gehen davon aus..

Wieso definiert man dann

θ

so?
Und bei dem

y

und

z

schaut man sich einfach Punkte in der näheren Umgebung von

x

an, ob diese in

P

liegen, denn dann ist

x

keine Ecke?

Dann zu

y_{i} :

Woher kommt das überhaupt? Wie kommen wir darauf, dass das null ist?

Wäre super, wenn mir wer helfen könnte!
Zerbreche mir schon lang den Kopf darüber..

Liebe Grüße, sunday

Hierzu passend bei OnlineMathe:
Exponentialfunktion (Mathematischer Grundbegriff)
Potenzregeln (Mathematischer Grundbegriff)

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1202405

	Status: nicht eingeloggt	Noch nicht registriert?