SS 2008EK Produktion & LogistikKapitel 3/1 Kapitel 3 Design und Analyse von Transportnetzwerken

  • Published on
    06-Apr-2015

  • View
    102

  • Download
    0

Embed Size (px)

Transcript

<ul><li> Folie 1 </li> <li> SS 2008EK Produktion &amp; LogistikKapitel 3/1 Kapitel 3 Design und Analyse von Transportnetzwerken </li> <li> Folie 2 </li> <li> SS 2008EK Produktion &amp; LogistikKapitel 3/2 3.1 Motivierendes Beispiel: Transportproblem Eine Firma hat 3 Produktionsstandorte i (Fabriken) und 4 Verkaufsstellen j (Abnahmezentren). Transportkosten pro Stck von i zu j: Verkaufsstelle ProduktionsstandortV1V2V3V4 F1105611 F21274 F39148 Nachfrage15203035 </li> <li> Folie 3 </li> <li> SS 2008EK Produktion &amp; LogistikKapitel 3/3 Minimierung der Transportkosten Whle in jeder Spalte den gnstigsten Standort um die Kosten zu minimieren! Verkaufsstelle ProduktionsstandortV1V2V3V4Kapazitts= verbrauch F1 105611 F2 1274 F3 9148 Nachfrage15203035 15 20 30 35 15 + 35 = 50 20 + 30 = 50 Gesamtkosten =15 * 1 + 20 * 1 + 30 * 4 + 35 * 4 = 295 </li> <li> Folie 4 </li> <li> SS 2008EK Produktion &amp; LogistikKapitel 3/4 Kapazittsrestriktionen I Jeder Standort hat eine gewisse Produktionskapazitt! Achtung: Gesamtnachfrage = Gesamtkapazitt (ansonsten mssen Dummy-Verkaufsstellen eingefhrt werden siehe 3.4) Es knnen nicht mehr alle Verkaufsstellen vom gnstigsten Produktionsstandort beliefert werden! </li> <li> Folie 5 </li> <li> SS 2008EK Produktion &amp; LogistikKapitel 3/5 Kapazittsrestriktionen II Kapazittsrestriktionen: Verkaufsstelle ProduktionsstandortV1V2V3V4Kapazitt F1 105611 25 F2 1274 25 F3 9148 50 Nachfrage15203035100 </li> <li> Folie 6 </li> <li> SS 2008EK Produktion &amp; LogistikKapitel 3/6 3.2 Lsung mittels Heuristiken Heuristiken: einfache Lsungsverfahren (geringer Aufwand, leicht zu verstehen) gute Lsungen Optimalitt der Lsung ist nicht gesichert Beispiele: 3.2.1 Spaltenminimim- &amp; Matrixminimummethode (= Greedy Verfahren) 3.2.2 Vogel-Approximation (= Regret Verfahren) </li> <li> Folie 7 </li> <li> SS 2008EK Produktion &amp; LogistikKapitel 3/7 3.2.1 Die Spaltenminimummethode 0. Ausgangslage: Transporttableau wobei jeweils links oben klein die Kosten eingetragen sind. Zunchst sind keine Zeilen oder Spalten gestrichen. 1.Von links beginnend suche man die erste noch nicht gestrichene Spalte 2.In dieser Spalte whle das kleinste noch nicht gestrichene Kostenelement c ij und mache die zugehrige Transportmenge x ij maximal. 3.Ist die Spaltenressource aufgebraucht streiche Spalte j, ODER ist die Zeilenressource aufgebraucht streiche Zeile i. 4.Ist nur mehr eine Zeile oder eine Spalte nicht gestrichen trage bei allen nicht-gestrichenen Zellen dieser Zeile oder Spalte die maximal mgliche Transportmenge x ij ein. ansonsten weiter mit 1. </li> <li> Folie 8 </li> <li> SS 2008EK Produktion &amp; LogistikKapitel 3/8 Die Spaltenminimummethode II i / j 1234Angebot 1 105611 25 2 1274 3 9148 50 Nachfrage15203035100 15 20300 10 25 30 10 0 0 0 Gesamtkosten = 15 * 1 + 20 * 1 + 30 * 4 + 25 * 11 + 10 * 4 + 0 * 8 = 470 Nur mehr eine Spalte nicht gestrichen </li> <li> Folie 9 </li> <li> SS 2008EK Produktion &amp; LogistikKapitel 3/9 Die Matrix-Minimum-Methode i / j 1234Angebot 1 105611 25 2 1274 3 9148 50 Nachfrage15203035100 Hier ist anstelle von Schritt 1 und 2 das kleinste noch nicht gestrichene Kostenelement c ij der gesamten Matrix zu suchen! 15 20300 10 25 10 30 250 0 Gesamtkosten =470 Nur mehr eine Spalte nicht gestrichen (zufllig gleich wie bei Spaltenminimummethode) </li> <li> Folie 10 </li> <li> SS 2008EK Produktion &amp; LogistikKapitel 3/10 3.2.2 Die Vogel-Approximation 0.Ausgangslage: Tableau wie bei der Spaltenminimummethode wobei zunchst keine Zeile oder Spalte gestrichen ist. 1.In jeder noch nicht gestrichenen Zeile bzw. Spalte berechne man die Differenz (Opportunittskosten, regret-value) zwischen dem kleinsten und dem zweitkleinsten noch nicht gestrichenen c ij. 2.In jener Zeile oder Spalte, wo diese Differenz am grten ist, whle man das kleinste noch nicht gestrichene Kostenelement c ij und mache die zugehrige Transportmenge x ij maximal. 3.Ist die Spaltenressource aufgebraucht streiche Spalte j, ist die Zeilenressource aufgebraucht streiche Zeile i. 4.Ist nur mehr eine Zeile oder eine Spalte nicht gestrichen, trage bei allen nicht-gestrichenen Zellen dieser Zeile oder Spalte die maximal mgliche Transportmenge x ij ein. ansonsten weiter mit 1. </li> <li> Folie 11 </li> <li> SS 2008EK Produktion &amp; LogistikKapitel 3/11 Die Vogel-Approximation II i / j 1234Angebot 1 105611 25 2 1274 3 9148 50 Nachfrage15203035100 15 20 5 25 10 25 821 3 1 1 4 10 2 25 43 30 4 5 5 Gesamtkosten = 15 * 1 + 20 * 1 + 25 * 6 + 5 * 4 + 10 * 4 + 25 * 8 = 445 Wenn Spalte gestrichen Zeilen- Differenzen neu berechnen Wenn Zeile gestrichen Spalten-Differenzen neu berechnen Nur mehr eine Spalte nicht gestrichen (besser als 470 zuvor) </li> <li> Folie 12 </li> <li> SS 2008EK Produktion &amp; LogistikKapitel 3/12 3.3 Modell als LP Eine allgemeine Formulierung eines Transportproblems lautet: m Produzenten mit dem Angebot s i, i = 1, , m n Abnehmer mit der Nachfrage d j, j = 1, , n Transportk. c ij pro Stck von i nach j, i = 1, , m; j = 1, , n LP-Problem: Zur mathematischen Modellformulierung definiert man x ij als die pro Zeiteinheit transportierte Menge von i nach j. Transportkosten Angebot i = 1, , m Nachfrage j = 1, , n. Nichtnegativitt i = 1, , m; j = 1, , n. = </li> <li> Folie 13 </li> <li> SS 2008EK Produktion &amp; LogistikKapitel 3/13 Beispiel K = (10x 11 + 5x 12 + 6x 13 + 11x 14 ) + (x 21 + 2x 22 + 7x 23 + 4x 24 ) + (9x 31 + x 32 + 4x 33 + 8x 34 ) min Angebotsnebenbedingungen: x 11 + x 12 + x 13 + x 14 = 25 (i=1) x 21 + x 22 + x 23 + x 24 = 25 (i=2) x 31 + x 32 + x 33 + x 34 = 50 (i=3) Nachfragenebenbedingungen: x 11 + x 21 + x 31 = 15 (j=1) x 12 + x 22 + x 32 = 20 (j=2) x 13 + x 23 + x 33 = 30 (j=3) x 14 + x 24 + x 34 = 35 (j=4) Nichtnegativitt: x ij 0 fr i = 1, , 3; j = 1, , 4 </li> <li> Folie 14 </li> <li> SS 2008EK Produktion &amp; LogistikKapitel 3/14 3.4 Kapazittsberschsse i / j 1234Angebot 1 105611 50 2 1274 3 9148 Nachfrage15203035100 Es sei nun allgemein mehr Kapazitt vorhanden als Nachfrage! 150 100 </li> <li> Folie 15 </li> <li> SS 2008EK Produktion &amp; LogistikKapitel 3/15 Einfhrung eines Dummy-Kunden i / j1234DummyAngebot 1 1056110 50 2 12740 3 91480 Nachfrage1520303550 150 100 = 50 Da wir Gleichheit von Gesamtkapazitt und Gesamtnachfrage annehmen, mssen wir einen knstlichen oder Dummy-Kunden einfhren (c ij = 0) 15 2030 35 00 50 8241 1 1 5 0 35 2 Gesamtkosten =295 3 Lsung Mittel Vogel-Approximation Auch die 0 in der Dummyspalte muss bercksichtigt werden (besser als 445 zuvor) </li> <li> Folie 16 </li> <li> SS 2008EK Produktion &amp; LogistikKapitel 3/16 LP-Formulierung Im Rahmen der LP- Formulierung ndert sich nur die Angebotsnebenbedingung: Angebot i = 1, , m </li> <li> Folie 17 </li> <li> SS 2008EK Produktion &amp; LogistikKapitel 3/17 3.5 Zusammenhang mit der Standortplanung I Standortproblem: Gegeben: n Kunden deren Nachfrage d j jeweils zu befriedigen ist. Gegeben: m potentielle Standorte fr Produktionsstellen mit Kapazitten s i und Fixkosten f i Es sollen jene Standorte realisiert werden, dass die Summe des Kapazittsangebotes die Gesamtnachfrage mindestens erreicht. Gesucht: optimale Auswahl der realisierten Standorte, sodass die Summe aus Transport- und Fixkosten minimal wird (warehouse location problem, WLP KFK) </li> <li> Folie 18 </li> <li> SS 2008EK Produktion &amp; LogistikKapitel 3/18 3.5 Zusammenhang mit der Standortplanung II LP: Transportkosten Angebot i = 1, , m Nachfrage j = 1, , n Nichtnegativitt i = 1, , m; j = 1, , n Ganzzahligkeit y i {0, 1} binre Variablen, i = 1, , m </li> </ul>

Recommended

View more >