Aufgabe zu Netzwerflüssen

14.06.2009, 18:06	steffilein	Auf diesen Beitrag antworten »
Aufgabe zu Netzwerflüssen Hallo =) Ich bin gerade dabei eine Aufgabe zum Thema verallgemeinerte Netzwerkflüssen zu beantworten... Leider steh ich im Moment auf dem Schlauch und komme nicht weiter Also kurz die Aufgabe: Jeden Tag ermöglicht ein Devisenbewirtschaftungsbüro Leuten, einen limi-tierten Betrag des Geldes von einer Währung in eine andere zu tauschen. Tabelle 1 zeigt die Wechselkurse und die Limits von verschiedenen Währungen. Einer Person stehen 1.000$ zur Verfügung. Nun soll die maximale Anzahl an Franken bestimmt werden, die mittels der gegebenen Wechselkurse erreicht werden kann. Dazu sind folgende Werte gegeben: (Wechselkurs an einem Tag) gegebene Währung, x erhaltene Währung, y Wechselkurs r Limit Dollar Pfund 0,56 1.000 Dollar Lira 1.241 500 Pfund Lira 2.200 160 Lira Pfund 0,00045 200.000 Gulden Pfund 3,37 400 Lira Yen 0,11 950.000 Yen Gulden 0,014 15.000 Gulden Yen 70,5 500 Gulden Franken 3,0 1.600 Yen Franken 0,042 80.000 (Ich hoffe ihr könnt erkennen was damit gemeint ist...) die Aufgabe soll mittels folgendem Schema gelöst werden... $\begin{eqnarray} \sum_{(i,j)\in A} c_{ij} x_{ij} \end{eqnarray}$ <<min s.t. $\begin{eqnarray} \sum_{(i,j)\in out(i)} x_{ij} - \sum_{(j,i)\in in(i)} \pi_{ji} x_{ji} = b(i) \end{eqnarray}$ $\begin{eqnarray} 0\leq x_{ij}\leq u_{ij} \end{eqnarray}$ Zielfunktion bin ich mir schon nicht 100%ig sicher.. meine Idee hier wäre: $\begin{eqnarray} 3,0x_{GF}+0,045x_{YF} \end{eqnarray}$ <<min (Indizes sind die Abkürzungen der Währungen, zwischen denen getauscht werden soll) Zu meinen Restirktionen: (Bei den Kapazitätsbegrenzungen bin ich mir zu 100% sicher das die Stimmen) $\begin{eqnarray} 0\leq x_{DP}\leq 1.000 \end{eqnarray}$ $\begin{eqnarray} 0\leq x_{DL}\leq 500 \end{eqnarray}$ $\begin{eqnarray} 0\leq x_{LP}\leq 200.000 \end{eqnarray}$ $\begin{eqnarray} 0\leq x_{PL}\leq 160 \end{eqnarray}$ $\begin{eqnarray} 0\leq x_{LY}\leq 950.000 \end{eqnarray}$ $\begin{eqnarray} 0\leq x_{YG}\leq 15.000 \end{eqnarray}$ $\begin{eqnarray} 0\leq x_{GY}\leq 500 \end{eqnarray}$ $\begin{eqnarray} 0\leq x_{GP}\leq 400 \end{eqnarray}$ $\begin{eqnarray} 0\leq x_{GF}\leq 1.600 \end{eqnarray}$ $\begin{eqnarray} 0\leq x_{YF}\leq 80.000 \end{eqnarray}$ Und nun zu den anderen Gleichungen der $\begin{eqnarray} x_{DP}+x_{DL}= \end{eqnarray}$ $\begin{eqnarray} (x_{LP}+x_{LY}) - (1.241x_{DL}+2.200x_{PL})= \end{eqnarray}$ $\begin{eqnarray} (x_{PL}) - (0,56x_{DP}+0,00045x_{LP}+3,37x_{GP})= \end{eqnarray}$ $\begin{eqnarray} (x_{GP}+x_{GF}+x_{GY}) - (0,014x_{YG})= \end{eqnarray}$ $\begin{eqnarray} (x_{YG}+x_{YF}- (0,11 x_{GY}+70,5x_{LY})= \end{eqnarray}$ So... nun zu meinen Fragen... Bei meiner Zielfunktion habe ich die Vermutung das sie eher zu den Restriktionen gehört... jedoch habe ich dann erst recht keine Ahnung wie meine Zielfunktion aussehen soll... Die nächste Frage: Wie wähle ich meine b(i)? setze ich die einfach alle auf 0? Viel Dank schonmal für eure Hilfe =) PS: hab mal noch den Graphen dazu gepackz, für die, die sich sowas lieber bildlich vorstellen ;-)
14.06.2009, 19:01	steffilein	Auf diesen Beitrag antworten »
Achso... vielleicht sei hier noch erwähnt, dass der Wechselkurs hier nicht als Kosten fungiert, sondern als Faktor an den Kanten des Graphen, welche den Fluss des Graphen verändern... Deshalb habe ich auch noch das algemeine Modell dazugeschriben, mit dem die Aufgabe gelöst werden soll...
14.06.2009, 20:49	steffilein	Auf diesen Beitrag antworten »
okay... ich habe jetzt den ganzen Nachmittag getüfftelt und bin (hoffentlich) auf die Lösung gekommen... Folgendes habe ich mir überlegt... Der Graph der meinem Problem zu Grunde liegt hat eine Quelle (Dollarknoten) und eine Senke (Frankenknoten). Somit Stellt der Dollarknoten einen Angebotsknoten dar und der Frankenknoten einen Bedarfsknoten. Der Rest fungiert als Umladeknoten. Das Angebot vom Angebotsknoten beträgt 1000$ (Ist ja laut Aufgabenstellung vorgegeben) und der Bedarf der Senke ist unbekannt (Somit dient mir dies als Zielfunktion). Nach der Balance-Gleichung des Flusserhaltungsgesetzes gilt: outflow - inflow = b Der outflow vom Frankenknoten ist Null (da dieser ja meine Senke ist) inflow ist: $\begin{eqnarray} 3,0 x_{GF} + 0,045 x_{YF} \end{eqnarray}$ und das muss nach meiner Aufgabenstellung maximal sein... Also vermute ich hier meine Zielfunktion $\begin{eqnarray} 3,0 x_{GF} + 0,045 x_{YF} \end{eqnarray}$ << max Zu meinen Restriktionen: Auch an den anderen Knoten muss die Balance-Gleichung gelten... Wie anfangs bereits erwähnt, ist der Dollarknoten meine Quelle. Hier gilt: inflow=0 ouflow= $\begin{eqnarray} x_{DP} + x_{DL} \end{eqnarray}$ Angebot dieses Knotens ist 1000$ Das alles zusammengepackt ergibt $\begin{eqnarray} x_{DP} + x_{DL}-0=1000 \end{eqnarray}$ Bei den restlichen Knoten ist der Bedarf(Angebot) gleich Null, da diese wie bereits erwähnt als Umladeknoten fungieren... $\begin{eqnarray} (x_{LP}+x_{LY}) - (1.241x_{DL}+2.200x_{PL})=0 \end{eqnarray}$ $\begin{eqnarray} (x_{PL}) - (0,56x_{DP}+0,00045x_{LP}+3,37x_{GP})=0 \end{eqnarray}$ $\begin{eqnarray} (x_{GP}+x_{GF}+x_{GY}) - (0,014x_{YG)}=0 \end{eqnarray}$ $\begin{eqnarray} (x_{YG}+x_{YF}) - (0,11 x_{GY}+70,5x_{LY})=0 \end{eqnarray}$ Die Kapazietätsbegrenzungen stehen in meinem ersten Post, deshalb lass ich die hier mal weg ;-) Mir stellt sich jetzt aber immer noch eine Frage: Meine Zielfunktion wird ja jetzt Maximiert... Um diese zu minimieren, kann ich da einfach ein Minus vor die Funktion setzen? LG

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »