Kostenlose Nachhilfe ? (Könnt ihr mir weiterhelfen?)

15/11/2013 - 00:19 von Peter Prestige | Report spam
Wenn einer auf www.matheplanet.de eine Frage stellt, dann checkt der Besitzer und Administrator dieser Homepage erst mal ab wieviel Geld der Fragende besitzt, und dann gibt er möglicherweise kostenlose Nachhilfe.


etwa :



Hallo,

ich habe folgenden Graph gegeben:
V=\left\{1,\ldots ,4ight\}
E=\left\{e_1,\ldots ,e_4ight\}=\left\{(1,2),(1,3),(2,4),(3,4)
wobei der Kante e_i die Kapazitàt k_i zugewiesen sei.

Jetzt möchte ich das Optimierungsproblem
\text{max }x_1+x_2
-x_1+x_3=0
-x_2+x_4=0
0\le x_i\le k_i
betrachten. Zu diesem suche ich das entsprechende Netzwerkflussproblem. Dies ist kein Problem; dafür nehmen wir die Inzidenzmatrix
A=\begin{pmatrix} 1&1&0&0\\-1&0&1&0\\0&-1&0&1\\0&0&-1&-1 \end{pmatrix}
her und schreiben das Problem um zu:
\text{max }x_1+x_2 , sodass Ax=\begin{pmatrix} 1\\0\\0\\-1 \end{pmatrix}=:b , 0\le x\le <math>\begin{pmatrix} k_1\\k_2\\k_3\\k_4 \end{pmatrix}=:u</math>

So, nun suche ich das duale Problem. Das hat ja irgendwie die Form
\text{min }y_1-y_4
y_1-y_2=1
y_1-y_3=1
y_2-y_4=0
y_3-y_4=0
das ist NICHT das korrekte duale Problem. Aber was genau ist falsch? Irgendwie muss ich ja noch die Information 0\le x\le u verwursten ... aber ich weiß nicht wie ...

Am Ende möchte ich darauf hinaus, dass für die zulàssigen Basislösungen y gilt, dass y_i\in \left\{0,\pm 1ight\} ist.

Könnt ihr mir weiterhelfen? Ich hànge jetzt schon ein paar Stunden an dieser Aufgabe und habe viel dazu gelesen, aber weiter komme ich einfach nicht. Ich bin mir auch nicht 100% siche, ob ich den "Bedarf" bzw. "Vorrat" b korrekt bestimmt habe.

Liebe Grüße
Toasten
 

Lesen sie die antworten

#1 wernertrp
15/11/2013 - 08:36 | Warnen spam
On Friday, November 15, 2013 12:19:43 AM UTC+1, Peter Prestige wrote:
Wenn einer auf www.matheplanet.de eine Frage stellt, dann checkt der Besitzer und Administrator dieser Homepage erst mal ab wieviel Geld der Fragende besitzt, und dann gibt er möglicherweise kostenlose Nachhilfe.





etwa :







Hallo,



ich habe folgenden Graph gegeben:

V=\left\{1,\ldots ,4ight\}

E=\left\{e_1,\ldots ,e_4ight\}=\left\{(1,2),(1,3),(2,4),(3,4)

wobei der Kante e_i die Kapazitàt k_i zugewiesen sei.



Jetzt möchte ich das Optimierungsproblem

\text{max }x_1+x_2

-x_1+x_3=0

-x_2+x_4=0

0\le x_i\le k_i

betrachten. Zu diesem suche ich das entsprechende Netzwerkflussproblem. Dies ist kein Problem; dafür nehmen wir die Inzidenzmatrix

A=\begin{pmatrix} 1&1&0&0\\-1&0&1&0\\0&-1&0&1\\0&0&-1&-1 \end{pmatrix}

her und schreiben das Problem um zu:

\text{max }x_1+x_2 , sodass Ax=\begin{pmatrix} 1\\0\\0\\-1 \end{pmatrix}=:b , 0\le x\le <math>\begin{pmatrix} k_1\\k_2\\k_3\\k_4 \end{pmatrix}=:u</math>



So, nun suche ich das duale Problem. Das hat ja irgendwie die Form

\text{min }y_1-y_4

y_1-y_2=1

y_1-y_3=1

y_2-y_4=0

y_3-y_4=0

das ist NICHT das korrekte duale Problem. Aber was genau ist falsch? Irgendwie muss ich ja noch die Information 0\le x\le u verwursten ... aber ich weiß nicht wie ...



Am Ende möchte ich darauf hinaus, dass für die zulàssigen Basislösungen y gilt, dass y_i\in \left\{0,\pm 1ight\} ist.



Könnt ihr mir weiterhelfen? Ich hànge jetzt schon ein paar Stunden an dieser Aufgabe und habe viel dazu gelesen, aber weiter komme ich einfach nicht. Ich bin mir auch nicht 100% siche, ob ich den "Bedarf" bzw. "Vorrat" b korrekt bestimmt habe.



Liebe Grüße

Toasten






Das mit dem Abchecken würde mich schon interessieren.
Haben die alle Staatlichen und Finanzamt und NSA und CD-Schweitzer Datenzugànge
aller Nummernkonten ?
Wie werden Börsenspekulanten behandelt.
Und wie 1000 Hektar Waldbesitzer usw.

Ähnliche fragen