Transportoptimierung?

25.09.2006, 11:49

TRONIC

Transportoptimierung?

hi hab da ein problem mit einem aufgabentyp könnte mir jemand die aufgabe schritt für schritt erklären (vorrechnen)

Vier Kohlezechen beliefern vier Kraftwerke mit Kohle gleicher Güte. Das Aufkommen und der Bedarf je Woche (in t) sowie die Entfernung (in km) gehen aus folgendere Tabelle hervor.

(...............) K1 K2 K3 K4 () Aufkommen
Z1)(......) 2() 4() 2() 3(.......) 9
Z2)(......) 9() 5() 8() 6(.......) 11
Z3)(......) 8() 7() 7() 5(.......) 12
Z4)(......) 5()12() 4()9(........)10
Bedarf) 15()12()7() 8

Bestimmen Sie einen optimalen Transportplan! Welche Transportaufwendungen entstehen? Erläutern Sie Ihr Ergebnis! Geben Sie im Falle einer mehrdeutigen Lösung alle gefundenen Lösungen an!

ups sorry war etwas kompliziert das einzugeben ja die 8 gehört zum Bedarf von Kraftwerk 4

THX im vorraus

25.09.2006, 19:25

Abakus

Auf diesen Beitrag antworten »

RE: Transportoptimierung?
Willkommen im Forum, TRONIC Wink

Mit welchen Verfahren sollt ihr das optimieren ? Und was verstehst du daran nicht ?

In der letzten Zeile fehlt noch eine Bedarfsrestriktion (?).

Grüße Abakus smile

EDIT: jetzt sehe ich es erst: die 8 ist der Bedarf von Kraftwerk 4

26.09.2006, 00:58

TRONIC

Auf diesen Beitrag antworten »

hi

ich hab irgendwie keinen richtigen plan wie ich da anfangen soll

bei uns im skript stehen paar methoden aber da blicke ich irgenwie nicht durch

die eine vorgehungsweise ist

Bestimmeneiner ersten zulässigen Bassislösung (Anfangslösung)
Überprüfung der Lösung auf Optimalität
Erzeugung weiterer Basislösungen
Gehe zu 2

und dann wäre da noch die Potentialmethode
(MODI-modifizierte Distributionsmethode)

die soll so ablaufen

Ermittle Potentiale!
Ist die Basislösung optimal? (wenn ja dann 7 = Lösung) (wenn nein dann bei 3 weiter)
Wähle dasjenige unbelegte Feld mit der kleinsten Bewertung!
Konstruiere zu diesem Feld einen "Kreis" unter Berücksichtigung positiver und negativer Felder!
Bestimme das Minimum der Transportmenge der negativen Felder!
Bestimme die neue zulässige Basislösung (Addiere das Minimum zu den positiven Feldern und subtrahiere es von den negativen Feldern des Kreises) (danach geht es wieder zu 1 Ermittle Potentiale)
Lösung

ich bräuchte einfach ein beispiel wie dei einzelnen schritte aussehen also detailietes vorrechnen der aufgabe damit ich die nachvollziehen kann, weil bei uns ging das so schnell das ich jetzt nicht mehr weiss wie der Prof das gemacht hat

wenns geht wäre es nett die beiden verfahren vorgerechnet zu bekommen

Mfg

TRONIC

26.09.2006, 11:55

Abakus

Auf diesen Beitrag antworten »

Zitat:

Original von TRONIC
bei uns im skript stehen paar methoden aber da blicke ich irgenwie nicht durch

die eine vorgehungsweise ist

Bestimmeneiner ersten zulässigen Bassislösung (Anfangslösung)
Überprüfung der Lösung auf Optimalität
Erzeugung weiterer Basislösungen
Gehe zu 2

Welche Methoden sind denn das, die in deinem Skript stehen ? (die Methoden sollten alle spezifische Namen haben)

Hier geht es in einem ersten Schritt zunächst darum, überhaupt zulässige Transportlösungen (nicht notwendig optimal) zu bekommen. Eine (Standard-) Methode dazu ist zB die Nord-West-Ecken-Methode (NWE).

Zitat:

und dann wäre da noch die Potentialmethode
(MODI-modifizierte Distributionsmethode)

die soll so ablaufen

Ermittle Potentiale!
Ist die Basislösung optimal? (wenn ja dann 7 = Lösung) (wenn nein dann bei 3 weiter)
Wähle dasjenige unbelegte Feld mit der kleinsten Bewertung!
Konstruiere zu diesem Feld einen "Kreis" unter Berücksichtigung positiver und negativer Felder!
Bestimme das Minimum der Transportmenge der negativen Felder!
Bestimme die neue zulässige Basislösung (Addiere das Minimum zu den positiven Feldern und subtrahiere es von den negativen Feldern des Kreises) (danach geht es wieder zu 1 Ermittle Potentiale)
Lösung

Das hier ist eine Iterationsmethode, die versucht eine schon bestehende Lösung zu verbessern. Auch hier gibt es verschiedene Methoden dazu.

Euer spezielles Vorgehen müsstest du schon an eurem Beispiel angeben. Es macht wenig Sinn, wenn ich das mit meinen Bezeichnungen usw. versuche.

Eine Notation könnte so aussehen (die Entfernung steht oben rechts, die Transportmenge unten):

$\begin{eqnarray*} \begin{matrix} & K_1 & K_2 & K_3 & K_4 & \\ Z_1 & 9^2 & 0^4 & 0^2 & 0^3 & 9 \\ Z_2 & 6^9 & 5^5 & 0^8 & 0^6 & 11 \\ Z_3 & 0^8 & 7^7 & 5^7 & 0^5 & 12 \\ Z_4 & 0^5 & 0^{12} & 2^4 & 8^9 & 10 \\ & 15 & 12 & 7 & 8 & \end{matrix} \end{eqnarray*}$

Hier ist mit der NWE-Methode bereits eine zulässige Transportlösung erzeugt: angefangen wird oben links (im "Nordwesten") mit der max. Menge (=9), weiter geht es dann in der ersten Spalte mit dem max. Möglichen (hier =6) usw. bis zum Feld unten rechts.

Grüße Abakus smile

26.09.2006, 12:19

kurellajunior

Auf diesen Beitrag antworten »

Sehe ich das richtig, dass dies eine Frage nach einem Algorithmus ist? *hehe*
Dafür haben iwr ja jetzt endlich ein ordentliches Infoboard (fürs nächste Mal). Wenn dies eine reine Mathefrage ist - sorry für den Spam.

Kleine Frag am Rande: wodurch zeichnet sich ein optimaler Transportplan aus? In welchen Einheiten können die Mengen sinnvoll transportiert werden? Wie groß sind die LKW? steigen die Kosten rein linear? Gibt es einen Kostenfaktor unabhängig von der Entfernung (Wartung des LKW/Eisenbahn)? etc.

Was also ist zu optimieren? nur die Gesamtwegstrecke?

26.09.2006, 15:37

Abakus

Auf diesen Beitrag antworten »

Zitat:

Original von kurellajunior
Sehe ich das richtig, dass dies eine Frage nach einem Algorithmus ist? *hehe*
Dafür haben iwr ja jetzt endlich ein ordentliches Infoboard (fürs nächste Mal). Wenn dies eine reine Mathefrage ist - sorry für den Spam.

Naja, nicht jeder Algorithmus gehört automatisch in die Informatik Big Laugh

. Das hier ist Wirtschaftsmathematik, Optimierung, oder auch OR.

Zitat:

Kleine Frag am Rande: wodurch zeichnet sich ein optimaler Transportplan aus? In welchen Einheiten können die Mengen sinnvoll transportiert werden? Wie groß sind die LKW? steigen die Kosten rein linear? Gibt es einen Kostenfaktor unabhängig von der Entfernung (Wartung des LKW/Eisenbahn)? etc.

Was also ist zu optimieren? nur die Gesamtwegstrecke?

Ja, hier ist nur die Gesamtwegstrecke zu minimieren. Diese wird als direkt proportional zu den Transport-Kosten angenommen. Transportiert werden kann jede notwendige Menge, Fixkosten werden vernachlässigt.

Das Problem ist demzufolge ein Spezialfall von Linearer Optimierung. Da jedoch viele Größen 0 sind, gibt es statt dem Simplex-Verfahren o.ä. einfachere bzw. speziellere Verfahren.

Grüße Abakus smile

EDIT: Gut, dass es jetzt dieses InfoBoard gibt. Ich bin dabei.

27.09.2006, 17:11

TRONIC

Auf diesen Beitrag antworten »

Transportoptimierung

Klassische Transportproblem

Formalisierung:
In m verschiedenen Aufkommensorten $\begin{eqnarray*} A_i \end{eqnarray*}$ stehen Aufkommensmengen $\begin{eqnarray*} a_i \end{eqnarray*}$ (i=1,...,m) eines einheitlichen Gutes zur Verfügung, die in verschiedenen Bedarfsorten $\begin{eqnarray*} B_j \end{eqnarray*}$ mit den Bedarfsmengen $\begin{eqnarray*} b_j \end{eqnarray*}$ benötigt werden (j=1,..,n). Die Aufwendungen für den Transport einer Einheit des Gutes vom Aufkommensort $\begin{eqnarray*} A_i \end{eqnarray*}$ zum Bedarfsort $\begin{eqnarray*} B_j \end{eqnarray*}$ betragen $\begin{eqnarray*} c_{ij} \end{eqnarray*}$ . Die Transportaufwendungen werden als zu den Transportmengen proportional angenommen. Das Gut ist so zu verteilen, dass die Transportaufwendungen ein Minimum annehmen. Die Menge des Gutes, die vom Aufkommensort $\begin{eqnarray*} A_i \end{eqnarray*}$ zum Bedarfsort $\begin{eqnarray*} B_j \end{eqnarray*}$ transportiert wird sei $\begin{eqnarray*} x_{ij} \end{eqnarray*}$ .

Z= $\begin{eqnarray*} \sum_{i=1}^m \sum_{j=1}^n~c_{ij} x_{ij} \end{eqnarray*}$ ---->Min!

$\begin{eqnarray*} \sum_{j=1}^n~x_{ij}=a_i \end{eqnarray*}$ (i=1,...,m) Zeilensumme

$\begin{eqnarray*} \sum_{i=1}^m~x_{ij}=b_j \end{eqnarray*}$ (i=1,...,n) Spaltensumme

$\begin{eqnarray*} x_{ij}\geq0 \end{eqnarray*}$ (i = 1,...,m; j = 1,..,n)

Voraussetzungen:
$\begin{eqnarray*} a_ i \end{eqnarray*}$ > 0 (i=1,...,m)
$\begin{eqnarray*} b_ j \end{eqnarray*}$ > 0 (j=1,…,n)

außerdem vorerst:

$\begin{eqnarray*} \sum_{i=1}^m~a_i = \sum_{j=1}^n~b_j \end{eqnarray*}$

Bemerkungen:
1. Die klassische Transportaufgabe stellt ein spezielles LOP dar und läßt sich als solches mit der Simplexmethode lösen.
2. Die spezielle Modellstruktur gestattet eine modifizierte Vorgehensweise zur Bestimmung des Optimums.

generelle Vorgehensweise:

1. Bestimmeneiner ersten zulässigen Bassislösung (Anfangslösung)
2. Überprüfung der Lösung auf Optimalität
3. Erzeugung weiterer Basislösungen
4. Gehe zu 2

und dann wäre da noch die Potentialmethode
(MODI-modifizierte Distributionsmethode)

Voraussetzung: Erfüllung der Saturationsbedingung

Vorgehensweise:
(1) Bestimmung der Potentiale $\begin{eqnarray*} u_i \end{eqnarray*}$ (i = 1,...,m) und $\begin{eqnarray*} v_j \end{eqnarray*}$ (j = 1,..,n) für alle Reihen des Schemas derart, daß gilt $\begin{eqnarray*} u_i+v_j =c_{ij} \end{eqnarray*}$ .
(Ein Potential, z.B. das für die erste Zeile ist frei wählbar, also $\begin{eqnarray*} u_1=0 \end{eqnarray*}$ .

(2) Bewrtung der nicht belegten Felder: $\begin{eqnarray*} \Delta k_{ij} = c_{ij} - (u_i +v_j) \end{eqnarray*}$ .

(3) Sind alle Kostenänderungswerte $\begin{eqnarray*} \Delta k_{ij} \end{eqnarray*}$ nichtnegativ, so ist ein Optimum erreicht (Falls $\begin{eqnarray*} \Delta k_{ij} = 0 \end{eqnarray*}$ existieren, so gibt es mehrere optimale Lösungen). Ansonsten ist die gefundene Lösung gemäß (4) zu verbessern.

(4) Das in Ergebnis (2) ermittelte nicht belegte Feld mit dem kleinsten Kostenänderungswert ist zu belegen. Der Wert (die Höhe) der Belegung entspricht dem kleinsten Wert eines negativen Feldes eines zugehörigen Kreises. Die Umverteilung ist entlang des Kreises vorzunehmen. Dabei ist der Wert von den negativen Feldern zu subtrahieren und zu den positiven Feldern zu addieren.

Ermittle Potentiale!
Ist die Basislösung optimal? (wenn ja dann 7 = Lösung) (wenn nein dann bei 3 weiter)
Wähle dasjenige unbelegte Feld mit der kleinsten Bewertung!
Konstruiere zu diesem Feld einen "Kreis" unter Berücksichtigung positiver und negativer Felder!
Bestimme das Minimum der Transportmenge der negativen Felder!
Bestimme die neue zulässige Basislösung (Addiere das Minimum zu den positiven Feldern und subtrahiere es von den negativen Feldern des Kreises) (danach geht es wieder zu 1 Ermittle Potentiale)
Lösung

hier drunter gehören die letzten Tabellen in meinem anhang

hoffe mal das reicht aus um mir das zu erklären weil mehr finde ich zurzeit nicht mehr in meinen Unterlagen (glaube aber auch nicht das es mehr war zu dem Thema)

28.09.2006, 00:14

Abakus

Auf diesen Beitrag antworten »

Erstmal danke für die ausführliche Beschreibung.

Ich habe einmal die Beispielrechnungen im doc-File kommentiert (die Tabellen alle in Latex übersetzen, dauert vermutlich ewig). Dazu könntest du ggf. weitere Fragen stellen.

Grüße Abakus smile

28.09.2006, 09:33

TRONIC

Auf diesen Beitrag antworten »

Danke für die schnelle Antwort und die detailierte beschreibung hat schon etwas licht ins DUNKLE gebracht.

ja der Prof war etwas zu schnell und hat sich anscheinen verschrieben und keiner hats gemerkt (naja passiert halt)

aber könntest du man die blauen Zahlen (die Potentiale) genauer ausrechnen also mit zahlen (also mit formel und mit zahlen) wäre nett

weil bei manchen komme ich da nicht weiter, wie du geschrieben hast

Zitat:

Du hast sofort: v_1 = 9, v_2 = 5, v_4 = 6

wieso nur die drei wieso hat man nicht die v_3 und v_5 gleich

ist die Formel so richtig $\begin{eqnarray*} c_{ij}=u_i+v_j \end{eqnarray*}$ oder geht die anders rum

das wärs mal für den anfang vielleicht fällt mir noch etwas ein bisjetzt klingt es einleuchtend geschockt

28.09.2006, 21:57

Abakus

Auf diesen Beitrag antworten »

Es geht um folgenden Transportplan:

$\begin{eqnarray*} \begin{tabular} {|r|c||l@{\quad}r|l@{\quad}r|l@{\quad}r|l@{\quad}r|l@{\quad}r||c|} \hline & $v_j$ $->$ & 9& & 5& & 4& & 6& & 4& & \\ \hline $u_i$ & & B1& & B2& & B3& & B4& & B5& & Aufkommen \\ \hline \hline -2 & Z1 & & $^6$ & 6 & $^3$ & & $^9$ & & $^5$ & 3 & $^2$ & 9 \\ \hline 1 & Z2 & & $^{11}$ & & $^7$ & 15 & $^5$ & & $^{10}$ & 4 & $^5$ & 19 \\ \hline 0 & Z3 & 2 & $^{9}$ & 2 & $^5$ & & $^9$ & 7 & $^{6}$ & & $^8$ & 11 \\ \hline -4 & Z4 & 10 & $^{5}$ & & $^4$ & & $^{10}$ & & $^{8}$ & & $^6$ & 10 \\ \hline \hline & Bedarf & 12& & 8& & 15& & 7& & 7& & 49 \\ \hline \end{tabular} \end{eqnarray*}$

Zu berechnen sind die 9 Potentiale. Dazu hast du 8 Gleichungen, nämlich:

$\begin{eqnarray*} u_1 + v_2 = 3 \end{eqnarray*}$
$\begin{eqnarray*} u_1 + v_5 = 2 \end{eqnarray*}$
$\begin{eqnarray*} u_2 + v_3 = 5 \end{eqnarray*}$
$\begin{eqnarray*} u_2 + v_5 = 5 \end{eqnarray*}$
$\begin{eqnarray*} u_3 + v_1 = 9 \end{eqnarray*}$
$\begin{eqnarray*} u_3 + v_2 = 5 \end{eqnarray*}$
$\begin{eqnarray*} u_3 + v_4 = 6 \end{eqnarray*}$
$\begin{eqnarray*} u_4 + v_1 = 5 \end{eqnarray*}$

Da du eine Variable mehr hast als Gleichungen (was bei dem Verfahren immer so ist), darfst du eine Variable frei setzen. Hier ist nun $\begin{eqnarray*} u_3 := 0 \end{eqnarray*}$ gesetzt worden, weil diese Variable am häufigsten vorkommt und das deshalb praktisch ist.

Das kannst du jetzt in die obigen Gleichungen einsetzen und siehst sofort:
$\begin{eqnarray*} v_1 = 9,~v_2 = 5,~v_4 = 6 \end{eqnarray*}$

Damit kannst du jetzt weiterrechnen, aus der letzten Gleichung folgt zB $\begin{eqnarray*} u_4 + 9 = 5~\Rightarrow u_4 = -4 \end{eqnarray*}$

Die anderen Potentiale kriegst du genauso raus.

Grüße Abakus smile

28.09.2006, 23:27

voessli

Auf diesen Beitrag antworten »

Das optimalste wäre die Kohle zurück ins Loch zu schütten und den veralteten Lehrplan gleich hinterher!

(ist mir einfach zu sehr Co2 lastig)

29.09.2006, 11:51

Abakus

Auf diesen Beitrag antworten »

Zitat:

Original von voessli
... und den veralteten Lehrplan gleich hinterher!

@ voessli: wenn du ein besseres Verfahren zur Lösung von Transportproblemen kennst, kannst du es zB anhand dieses Beispiels gerne vorstellen.

Grüße Abakus smile

21.03.2013, 09:55

Hanz

Auf diesen Beitrag antworten »

Hallo, ich weiß, dass dieses Thema schon alt ist, aber ich hätte ne Frage zur Modifizierten Distributionsmethode und zwar verstehe ich dort alles, bis auf wie man diese sogenannten "Kreise" oder "Zyklen" bestimmt, wenn ein nichtbelegetes Feld eine negatiev Wert aufweist?

Kann mir das jemand erklären?

Neue Frage »

Antworten »

Transportoptimierung?

Verwandte Themen