| Autor |
Beitrag |
    
Henry
| | Veröffentlicht am Donnerstag, den 22. Juni, 2000 - 14:11: | 
|
Linares Optimieren
In dieser Semesterarbeit stelle ich einige Lösungsverfahren aus der linearen Optimierung vor. Diese Arbeit ist so geschrieben, daß sie nur mathematische Vorkenntnisse aus der Sekundarstufe voraussetzt. Dieses Einleitungskapitel (1.1-1.3)erläutert die Ziele der linearen Optimierung und was die Definition von Optimierung ist, geendet wird mit einem historischen Abschluß. Zur Einführung in die lineare Optimierung, im zweiten Teil, werden Beispiele zum grafischen Lösungsverfahren und Grundvoraussetzungen zur Berechnung des Transportproblems dargestellt, und das Verfahren daran beschrieben und gelöst. Am Ende des zweiten Teils werden die Verfahren gegenübergestellt und verglichen. Das grafische Lösungsverfahren wird zum Erklären des Prinzips der linearen Optimierung bei zwei Variablen benutzt, um dann im dritten Teil mit dem Simplex-Verfahren, mit dem man n Variable(n) berechnen kann, fortzufahren. Dasselbe Vorgehen gilt auch für das Grundlagen des Transportproblemberechnung. Parallel dazu werden im zweiten Teil simple Vorgehensweisen aufgestellt und beschrieben, um darauf dann im dritten Teil der Semesterarbeit, das Potentiale-1 und Stepping-Stone Verfahren aufzubauen. Der vierte Teil behandelt eine Problembearbeitung aus der Odenwaldschule, die sich teilweise auf die im dritten Teil behandelten Verfahren bezieht und mit den Verfahren arbeiten. Im Schlußteil werden dann kurz die nicht behandelten Verfahren der linearen Optimierung angeschnitten, und offen gebliebene Fragen behandelt. Warum ich über lineare Optimierung schreibe? Ich schreibe über dieses Thema, weil ich über ein Gebiet aus dem Wirtschaftsbereich arbeiten wollte. Ich kam zu diesem Thema über meinen Mathelehrer, der mir die lineare Optimierung vorschlug. Die lineare Optimierung, die ja das besterforschte Gebiet der Wirtschaftsmathematik ist, gefiel mir ganz gut und da ich mich auch in Zukunft damit beschäftigen will (und höchstwahrscheinlich auch tun werde), hab ich mich entschieden, darüber zu schreiben. Ich hoffe, daß sie mir bei meinem Studium auch eine kleine Hilfestellung sein wird. Meine zweite Hoffnung ist, daß sie den Lesenden gefällt oder ihn anspricht. 1.2 Was ist lineare Optimierung In der Wirtschaft benutzt man neben dem Begriff lineare Optimierung auch die Begriffe Planungsoptimierung oder Programmieroptimierung. Bei der Planungsoptimierung kommen z.B. vor: Produktionsplanung, Transportplanung, Mischungs- und Zuschnittsberechnung. Die Programmieroptimierung wird in der Datenverarbeitung zum Beispiel zur Anpassung eines speziellen Programmes an einen speziellen Computer ohne inhaltliche Änderungen verwendet Die lineare Optimierung ist ein Teilgebiet der Optimierungsrechnung. Diese ist ein wichtiges Hilfsmittel zur optimalen Entscheidungsfindung bei komplizierten Problemen. Man kann sich merken: Die lineare Optimierung umfaßt diejenigen mathematischen Verfahren, die das Maximum oder das Minimum einer linearen Funktion unter einschränkenden Bedingungen für die Variablenbelegung ermitteln . Wie schon angesprochen wird die lineare Optimierung zum größten Teil in der Wirtschaft als mathematisches Verfahren zur Maximierung oder Minimierung einer linearen Funktion eingesetzt. Die zu maximierende Funktion ist meist die Gleichung für den Gewinn, die zu minimierende Funktion die Gleichung für die Kosten eines Unternehmens . Um das Maximum oder das Minimum zu bestimmen, muß man die einschränkenden Bedingungen, die Einfluß auf das Ergebnis haben, herausfinden und in Verbindung setzten mit dem zu erreichenden Maximum oder Minumum. Diejenigen Bedingungen zu bestimmen , die eine Wirkung auf das Optimierungsergebnis haben, ist eine wichtige Aufgabe, die vor der eigentlichen Optimierungsrechnung gelöst werden muß. Diese Aufgabe besteht in der exakten Formulierung der Aufgabenstellung. Bei der Formulierung der Aufgabenstellung muß man beachten, daß jede Optimierungsaufgabe aus zwei Teilen besteht, nämlich 1. Aus der Bestimmung des Ziels, das durch die Optimierung erreicht werden soll und 2. aus den Bedingungen, die die Lösung zu 1. beeinflussen. Die lineare Optimierung hat sich aus der linearen Algebra herausgebildet. Genau so wie bei der linearen Algebra benutzt man bei linearen Optimierung der Theorie des linearen Vektorraums einschließlich der Martixrechnung, und der Grundgedanken der Theorie der Lösungs linearen Gleichungssysteme. Die Bestimmung eines Extremwertes ist aus der Differentialrechnung bekannt. Sie wird dort auf nichtlineare Funktionen einer oder mehrerer unabhängiger Variabler angewendet. Für die Extremwertberechnungen linearer Funktionen versagen die Methoden der Differentialrechnung. Lineare Funktion sind zwar differenzierbar , da aber ihre erste Ableitung stets konstant ist, kann die für einen Extremwert bestehende notwendige Bedingung nicht erfüllt werden. Die Frage nach dem Extremwert einer lineare Funktion geht bei den Problemen der Linearoptimierung von wesentlich anderen Gesichtspunkten aus als bei der Differentialrechnung. Sie wird erst sinnvoll durch die stets mit auftretenden Nebendingungen, die die Form von linearen Ungleichungen oder Gleichungen haben . 1.3 Historische Hintergründe der linearen Optimierung Die lineare Optimierung gehört zu den jüngeren Anwendungsgebieten der Mathematik. Vor einem halben Jahrhundert begann der richtige Durchbruch der linearen Optimierung mit der Simplexmethode die von G. B. Dantzig entwickelt worden war. Die ersten Arbeiten der linearen Optimierung wurden im Jahre 1939 von dem russischen Mathematiker Leonid W. Kantorowicz in diesem Gebiet veröffentlicht. In der Einleitung seines Buches "Mathematischen Methoden in der Organisation und Planung der Produktion" schreibt er (nach [3], S. 26) : Es gibt zwei Wege die Rentabilität der Arbeit eines Geschäftes eines Unternehmers oder eines ganzen Industriezweiges zu vergrößern. Ein Weg besteht in verschieden Verbesserungen der Technik, z. B. neuem Zubehör für die einzelnen Maschinen, Änderungen der technischen Prozesse und der Entdeckung neuerer, besserer Arten von Rohmaterial. Der andere Weg der bisher viel weniger benutzt wurde, steht in der Verbesserung der Organisation, der Planung und Produktion. Das schließt solche Fragen ein wie die Arbeitsteilung zwischen den einzelnen Maschinen des Unternehmers oder zwischen Meschanismen , Auftrags- Erteilung zwischen den Unternehmen, die richtige Verteilung zwischen Rohstoffen, Brennstoffen und anderen Faktoren. Kontorowicz, geboren 1912, erhielt für seine erfolgreichen Arbeiten auf diesem Gebiet im Jahre 1941, nämlich über das Transportproblem von dem Amerikaner F. L. Hitchcock. Diese Arbeiten wurden jedoch zunächst für zwei Jahrzehnte kaum be- achtet und sie blieben daher weitgehend unbekannt. Besonders in den USA wurden am Ende des zweiten Weltkrieges neue Lösungsmöglichkeiten für Probleme der mathematischen Optimierung, die für den militärischen Bereich von Bedeutung waren, entwickelt. Wie schon angesprochen erfolgte der Durchbruch der linearen Optimierung mit der Simplexmethode, die im Jahre 1947 von G. B. Dantzig entwickelt worden war. Die im Rahmen eines Forschungsauftrages der amerikanischen Luftwaffe entdeckt wurde. Diese Methode, mit der alle linearen Optimierungsprobleme gelöst werden können, ist bis heute das wichtigste Verfahren zur Lösung aller Probleme. J. von Neumann und O. Morgenstern gelang es schon kurze Zeit später wichtige Ergebnisse und Methoden der Spieltheorie in dem Gebiet der linearen Optimierung zu verwenden und sie damit beträchtlich weiter zu entwickeln. Seit dem Beginn der 50ger Jahre erlebte eine rapide Aufwärtsentwick- lung. Für diesen großen Aufschwung wirkte sich Großrechenanlagen besonders günstig Berechnungen nach dem Simplexverfahren in einer angemessen Zeit bewältigt werden konnte. Schon im Jahre 1956 konnte mit einer IBM - Maschine Probleme der linearen Optimierung mit mehr als 200 Gleichungen Stunden mit großer Genauigkeit gelöst werden. Die ersten wichtigen Anwendung auf wirtschaftlichen Problemen erfolgten bei der Planung und Entwicklung von Erdölraffinerieren. Im Jahre 1979 hat der Russe Khashian einen neuen Algorithmus entwickelt, mit dem bei linearen Optimierungsproblemen mit einer großen Anzahl von Variablen und einschränkenden Bedingungen die optimale Lösung schneller bestimmt werden kann. Der wesentliche Vorteil dieses Verfahrens liegt darin, daß der Rechenaufwand geringer als beim Simplexverfahren sein soll. Heute gehört die lineare Optimierung zu den best erforschenden Gebiete der Wirtschaftsmathematik. 2. Einführung in die Lineare Optimierung In diesem Teil werden mehrere Beispiele für das grafische Lösungsverfahren und das Transportproblem beschrieben und als Grundlage für das nächste Kapitel benutzt. Am Ende dieses Teils werden die Verfahren einander gegenübergestellt, die jeweiligen Eigenschaften erläutert und ein Ablaufdiagramm zu jeder Methode erstellt. 2.1 Das grafische Lösungsverfahren Das grafische Lösungsverfahren der linearen Optimierung dient hauptsächlich zur Veranschaulichung und zur Einführung in die lineare Optimierung. In der Praxis wird es so gut wie kaum benutzt, weil die dort auftretenden Probleme häufig Hunderte oder Tausende Variable haben. Das grafische Verfahren zur Lösung von Aufgaben der linearen Optimierung beruht darauf, daß ein Punkt in der Ebene, etwa im kartesischen Koordinatensystem, durch zwei Koordinaten x und y dargestellt und bestimmt werden kann. So kann jedes Produktionsprogramm, das aus den Mengen x des Erzeugnisses Ex und y des Erzeugnisses Ey besteht, durch einen Punkt im Koordinatensystem angegeben werden. Aus dieser Menge von Punkten die durch verschiedene Bedingungen eingeschränkt wird, entsteht ein Raum mit zulässigen Lösungen. Aus diesem Raum wird dann mit Hilfe der Zielfunktion, die aus bestimmten Kriterien besteht, die beste Lösung, die optimale Lösung ermittelt. Für eine Maximum-Aufgabe nehmen wir zunächst ein Anschaffungsproblem. Eine Jugendgruppe beschließt, Zelte einzukaufen. In einem Sonderangebot werden zwei verschiedene Sorten von Zelten für jeweils 10 und 15 Personen preiswert angeboten. Von den 10-Personenzelten sind noch 5 und von den 15-Personenzelten nur noch 4 vorrätig. Die Zelte für 10 Personen kosten 200 DM je Stück und diejenigen für 15 Personen 400DM je Stück. Die Jugendgruppe kann insgesamt höchstens 1800 DM für die Zelte ausgeben. Wie viele 10- und 15-Personenzelte kann die Jugendgruppe kaufen, damit eine möglichst große Anzahl von Jugendliche in den Zelten untergebracht werden kann? Um dieses - zunächst etwas schwierig aussehende - Problem zu lösen, stellen wir es mit Hilfe der mathematischen Sprache übersichtlich dar. x sei die Anzahl der 10-Personenzelte und y sei die Anzahl der 15-Personenzelte, die angeschafft werden sollen . Dann gilt: Es gibt nun verschiedene Möglichkeiten, um dieses einfache Problem zu lösen. Die einfachste ist in diesem Fall, daß man solange alle zulässigen x- und y-Werte einsetzt und die in Zielfunktion eingibt, die Z-Werte dadurch bestimmt und dann durch Vergleich der Z-Werte die günstigste Lösung herauszufindet. Zulässige Lösungen sind alle Lösungen, die die Bedingungen a), b), c) erfüllen und die natürlich ganzzahlig sowie nicht negativ sind. Bei diesem Verfahren stellt man Tabellen auf, woraus man dann die beste Kombination der zwei Variablen entnehmen kann. Es ist nur gut anzuwenden, wenn ganzzahlige Werte für x und y zugelassen sind. Dieses Verfahren wird aber sehr umständlich, wenn schon einbißchen komplizierter wird. Ein anderes Verfahren ist das grafische Verfahren, das man hier anwenden kann, weil mit zwei Variablen (x/y) gerechnet wird. Die Bedingungen a), b) und c) müssen dazu in ein Koordinatensystem umgesetzt werden. Die Bedingung c) 200x + 400y R 1800 formen wir, zur bessern Handhabung, in x + 2y R 9 um. Zur Veranschaulichung zeichnen wir jede Bedingung einzeln ein um zu zeigen welchen Raum abgrenzt. Dabei gilt außerdem für alle Graphen: x S 0, y S 0 und x, y i Z Die Bedingungen werden als Geraden in das Koordinatensystem eingetragen nur mit einem kleinen Unterschied, man schraffiert die Flächen, in die Bedingung möglich ist (siehe Bild 1,2,3). Wenn alle Bedingungen oder auch Ungleichungen in ein Koordinatensystem zusammengefügt werden, dann erhält man den Raum, der alle möglichen Lösungen enthält. Dieser Raum ist auch die Schnittmenge der Punktmengen. Von der Menge der so bestimmten zulässigen Lösungen ist das Wertepaar (x/y) zubestimmen, für das die Funktion 10x+15y =Z}Max erreicht. Die Gleichung 10x + 15y = Z ist eine Gleichung mit drei Variablen. Daher können wir den Graphen für diese Gleichung in einem dreidimensionalen Koordinatensystem darstellen, indem wir zu jedem zulässigen Wertepaar (x/y) den zugehörigen Z-Wert abtragen. Diese Darstellung wählen wir nicht, weil man es genau so gut im zweidimensionalen Koordinatensystem darstellen kann. Es zeigt aber, warum man nur mit zwei Variablen im grafischen Verfahren arbeiten kann , weil die dritte Variable oder auch Raumachse z, für die Zielfunktion benötigt wird und man einen Vierdimensionalen Raum nicht mehr zeichnen kann . Um die Zielfunktion in einer ebenen Darstellung einzuzeichnen, müssen wir die Steigung dieser Geraden ermitteln. Man kann sich dazu merken: Die Lösungsmenge der Gleichung der Zielfunktion für einen bestimmen Z-Wert entspricht der Menge aller Punkte einer Geraden. Durch Umstellen der Zielfunktion erhalten wir aus 10x + 15y = Z die Funktion y = -2/3x + Z/15. Diese Gleichung ist die Gleichung für eine "Schar" von parallelen Geraden, die alle die Steigung -2/3 haben und für die die Verschiebung auf der y-Achse Z/15 beträgt.(siehe Bild 5) Wie man sieht wird der Wert für Z um so größer, je größer der Achsenabschnitt auf der y-Achse wird. Wir erhalten also den größten Wert für Z, wenn wir aus der parallelen Geraden diejenige wählen, für die der Achsenabschnitt möglichst groß wird und die noch einen Punkt mit der Menge der zulässigen Lösungen gemeinsam hat. Die so bestimmte zulässige Lösung ist dann die optimale Lösung1. Das Ergebnis unserer Rechnung lautet: 80 Jugendliche können in 2 von den 15-Personenzelten und 5 von den 10-Personenzelten maximal unterkommen. Wenn man jetzt den Preis, in der Bedingung c) (siehe Seite), für die 15-Personenzelte auf 300DM heruntersetzt, lautet die Ungleichung x + 3/2y R 9. Die neue Ungleichung wird jetzt statt x + 2y R 9 in das Koordinatensystem einsetzt. Wie man in Bild 6 sehen kann, wird dadurch der Raum der möglichen Lösung größer und die Grenzwerte der Ungleichung liegen auf der Geraden der Zielfunktion. In solch einem Zustand kann es unendlich viele Lösungen für Z Maximum geben. Da man nur ganze Zelte kaufen kann, benutzt man in diesem Fall nur die ganzzahligen Werte unfähig. Dieses Verfahren wird die ganzzahlige Optimierung genannt. Bei Gütern, die man z. B. abwiegt, können auch nicht ganzzahlige Werte sinnvoll Ergebnisse bringen. Bei der linearen Optimierung kommen öfters auch Bedingungen vor die überflüssig sind. Für Anwender können sie aber durchaus aussagekräftig, sein deshalb sondert man sie im allgemeinen nicht aus. Wir können uns aber merken: Eine Ungleichung eines Systems, die keinen Einfluß auf die Bildung der Lösungsmenge hat und die zu den anderen Ungleichungen nicht im Widerspruch steht, heißt überflüssig. Man kann sie ohne Änderung der Lösungsmenge aus dem System aussondern . Siehe dazu Bild 7, wo wir die Ungleichung x + 3/2y R 9, als Sonderangebot, das erst nach der geplanten Freizeit eintritt, zusätzlich in die erste Problemstellung einbauen. Der Anwender kann Bild7 entnehmen, daß es eventuell ob es nicht besser wäre die Freizeit zu verschieben, um mehr Zelte einkaufen und damit mehr Jugendliche mitzunehmen. Beispiel für leere und unbegrenzte Lösungsmengen Bei einer unbegrenzten Lösungsmenge, ist die Punktmenge nach oben nicht begrenzt. Es kann kein optimales Ergebnis gefunden werden (siehe Bild 8). Die Konstruktion enthält diese Bedingungen : (1)-1/8x + y S 6 (2) 3x + 2y S 15 (3) -3x + 2y S 0 (4) x S 0 (5) y S 0 Bei der leeren Lösungsmenge gibt es keinen Punkt, der alle Bedingungen gleichzeitig erfüllt, d.h. es gibt keinen Raum mit einer Menge möglicher Lösungen. Wenn eine leere Lösungsmenge auftaucht, ist entweder das mathematische Modell falsch aufgestellt oder dieses Problem ist nicht lösbar mit den Mitteln der linearen Optimierung (siehe Bild 9). Die Bedingungen sind : (1) x R 6 (2) -x + 3y R 3 (3) -x + y S 2 (4) x S 0 (5) y S 0 Wie man dem Bild entnehmen kann, gibt es zwei Räume, die keinen Punkt gemeinsam haben, die Zielfunktion kann also keinen gemeinsamen Punkt finden. Bild 9 Beispiel für eine Minimumaufgabe Ein Mischungsproblem. Ein Hüttenwerk bezieht zwei Erzmischungen E1und E2. Aus diesen beiden Mischungen soll für die Erzeugung eines besonderen Stahls eine neue Mischung hergestellt werden. Die notwendigen Angaben sind der Tabelle zusammengefaßt. Wie viel Tonnen sind von jeder Erzsorte notwendig, wenn die Gesamtkosten für die neue Mischung möglichst niedrig sein sollen ? x ist die Anzahl der Tonnen, die von Erzsorte E1 und y ist die Anzahl der Tonnen, die von Erzsorte E2 notwendig sind. Dann gilt: (1) x S 0; y S 0 (2) 0,1x + 0,2y S 10 0,3x + 0,1y S 12 0,1x + 0,1y S 8 (3) 12x + 16y = Z } Min. Die Firma muß 60 Tonnen von E1 und 20 Tonnen von der Mischung E2 nehmen, um eine möglichst preiswerte neue Mischung für die Herstellung des Stahls zu erhalten. Wie man sieht ist auch bei der Minimierung die Nichtnegativitätsbedingung (1) enthalten. Anders als bei der Maximum-Berechnung sind die Bedingungen (2) nicht mehr R sondern S. Auch die Zielfunktion ändert sich. Im Gegensatz zur Maximumfunktion verschiebt sie sich nicht möglichst weit weg vom 0 Punkt sondern möglichst nah zum Nullpunkt. Bild 10 Allgemeines Verfahren zur Maximum- und Minimumaufgaben Das mathematische Modell für die Minimum- und Maximumaufgabe mit zwei Variablen kann man so zusammenfassen: Maximum Minimum (1) Die Nichtnegativitätsbedingungen x S0 ; y S 0 (2) Die einschränkenden Bedingungen a1x + b1y R C1 mit C1 S 0 a1x + b1y S C1 mit C1 S 0 a2x + b2y R C2 mit C2 S 0 a2x + b2y S C2 mit C2 S 0 x x x x x x x x x x Max. + bmy R Cm mit Cm R 0 amx + bmy S Cm mit Cm S 0 (3) Zielfunktion dx + ey = Z } Max. dx + ey = Z } Min. y = -dx/e + Z/e mit e @ 0 Die Bedingung (1) und (2) begrenzen den Raum der möglichen Lösungen, wo man dann durch die Zielfunktion Z das optimale Ergebnis erreicht. Durch das Umstellen der Zielfunktion erhält man die Steigung der Zielfunktion, m = -d/e und denn Achsenabschnitt den sie nach oben- oder unten wandert auf der y-Achse, n = Z/e
FORTSETZUNG in:
Lineares Optimieren 2 |
Henry
| | Veröffentlicht am Donnerstag, den 22. Juni, 2000 - 14:13: |
|
FORTSETZUNG von:
Lineares Optimieren
Den Wert der Zielfunktion für die optimale Lösung erhalten wir aus der Gleichung der Zielfunktion . 2.2 Grundlagen des Transportproblems Das Transportproblem ist das am meisten angewandte Gebiet in der linearen Optimierungsrechnung. In der USA werden z.B. etwa 85% aller linearen Optimierungsprobleme mit dem Transportproblem- Verfahren gelöst. Mit dem Transportproblem berechnet man nur Minimierungsaufgaben, wie zum Beispiel die Kostenminimierung bei Transportkosten. Dabei ist zwar zu beachten, daß zu den Transportproblemen nicht nur Probleme aus dem Transportwesen gehören, sondern auch Probleme aus vielen anderen Gebieten. Transportprobleme sind durch ein bestimmtes mathematisches Modell gekennzeichnet, und alle Probleme, die durch dieses Modell beschrieben werden können, werden als Transportprobleme bezeichnet. Beispiel zum Transportproblem Die Firma Truck&CO. stellt in ihren Betrieben in Hannover, Köln und Frankfurt Schlepper her, die an vier Großhändler in Hamburg, Dortmund, Stuttgart und Regensburg geliefert werden. Die Angebotsmenge sind in Hannover 40, in Köln 80 und in Frankfurt 30 Schlepper. Die Bedarfsmengen sind in Hamburg 35, in Dortmund 30, in Stuttgart 25 und Regensburg 60 Schlepper. Die Transportkosten sind proportional den Entfernungen. Sie betragen in DM pro Schlepper: Insgesamt werden 150 Schlepper angeboten und nachgefragt . Wir sollen nun die günstigsten Transportkosten ausrechnen! Um das Problem besser zu erfassen, stellen wir dazu die Mathematische Formulierung auf: Siehe Tabelle 2 A1, A2, A3 sind die Angebotsmenge und B1, B2, B3, B4 sind die Bedarfsmengen (1) Angebotsbedingungen (2) Bedarfsbedingungen x11 + x12 + x13 + x14 = 40 x11 + x21 + x31 = 35 x21 + x22 + x23 + x24 = 80 x12 + x22 + x32 = 30 x31 + x32 + x33 + x34 = 30 x13 + x23 + x33 = 25 x14 + x24 + x34 = 60 Da die Variablen größergleich Null sein müssen und ein Minimalwert gesucht wird, können wir die Aufgabe als lineares Optimierungsproblem auffassen. Obwohl es ein einfaches und kleines Problem ist, erhalten wir ein mathematisches Modell mit bereits 12 Variablen. Die Bedingungen müssen auch hier die Nichtnegativitätsbedingungen erfüllen. Daraus ergibt sich für jede geordnete Menge von 12 Zahlen (x11, x12, ..., x34), die die Nichtnegativitätsbedingungen und die einschränkenden Bedingungen erfüllen, eine zulässige Lösung. Eine solche geordnete Menge von 12 Zahlen bezeichnet man als 12-Tupel. Hat eine solche geordnete Menge n Zahlen, so heißt sie n-Tupel . Wir fügen jetzt die Tabelle mit den Variablen in die Tabelle mit den Kosten ein. Die Werte in Klammer sind die Transportkosten. Die Menge der zulässigen Lösungen ist die Definitionsmenge für die Zielfunktion. Aus der Definitionsmenge ist die optimale Lösung zu bestimmen, das ist das 12-Tupel, für das die Zielfunktion ihren minimalen Wert erhält. Durch Probieren können einfache zulässige Lösungen für das Transportproblem finden. Um beim Probieren das Finden einer zulässigen Lösung zu erleichtern, gibt es verschiedene Verfahren. Wenn man bei ihrer Anwendung eine Grundregel befolgt Spaltenzahl n und Zeilenzahl m werden addiert und von der Summe die Zahl 1 subtrahiert, dann erhält man die ideale Zahl der zu belegenden Felder. Auf die Herführung der Formel möchte ich in dieser Arbeit verzichten. Sie gilt aber immer bis auf die Ausnahmefälle, die man als "entartete Fälle" bezeichnet. Bei solchen Fällen kann es vorkommen, daß auch vor Belegung des letzten Feldes gleichzeitig eine Zeilen- und Spaltenbedingung erfüllt wird, weil die Angebotsmenge zufällig so gewählt ist. In diesem Fall kommen wir mit einer kleineren Anzahl von belegten Feldern für eine zulässige Lösung aus, als mit m+n - 1 . Damit diese Anwendung in das allgemeine Lösungsverfahren paßt, belegen wir in solchen Fällen ein Feld mit 0 Mengeneinheiten und erhalten damit rein formal dann auch eine Lösung mit m + n - 1 belegten Feldern. Das Nordwestecken-Verfahren Bei diesem Verfahren beginnt man mit der Belegung der Felder in dem linken oberen Feld und belegt dann das rechts daneben oder darunter liegende Feld und fährt so fort, bis alle Bedingungen erfüllt sind. Da bei einer Landkarte die linke obere Ecke die Nordwestecke ist, nennt man dieses Verfahren das "Nordwestecken-Verfahren". Wie wir jetzt wissen, muß jedes Feld mit dem Maximalen Wert belegt werden, damit nicht mehr als m + n - 1 Felder belegt werden . Wie wir aus der Tabelle entnehmen können betragen die Transportkosten für diese Ausgangslösung Z = 35*160 + 5*370 + 25*100 + 25*380 + 30*510 + 30*320 =44350 Das Zeilenminimum-Verfahren Im Gegensatz zum Nordwestecken-Verfahren, bei dem keine Rücksicht auf die Transportkosten Minimierung genommen wird, wird bei diesem Verfahren auch auf die Kosten geachtet. Beim Zeilenminimum-Verfahren gehen wir zeilenweise von oben nach unten vor und belegen in der Zeile zuerst das Feld, für das die Transportkosten je Mengeneinheit am niedrigsten sind, dann das Feld mit den zweitniedrigsten Kosten usw. Treten einmal bei einem Problem gleich günstige Felder auf, so belegen wir davon ein beliebiges Feld . Wie wir sehen unterscheidet sich das Zeilenminimum-Verfahren bei diesem Beispiel nicht vom Nordwestecken-Verfahren; es kommt wieder raus für Z: Z = 35*160 + 5*370 + 25*100 + 25*380 + 30*510 + 30*320 =44350 Das Spaltenminimum-Verfahren So wie wir bei dem Zeilenminimum-Verfahren zeilenweise vorgegangen sind, so gehen wir jetzt bei diesem Verfahren spaltenweise vor . Das Ergebnis lautet in diesem Fall. Z = 35*160 + 30*100 + 25*210 + 5*580 + 50*510 + 5*320 = 43850 Wie wir sehen konnten haben durch dieses Verfahren jetzt den Betrag von 500DM einsparen können. Das Matrixminimum-Verfahren Es liegt nahe, die Ausgangslösung von vorneherein so zu bestimmen, daß wir mit der Belegung des günstigsten Feldes beginnen, dann das nächst günstigste usw., ohne auf Zeilen und Spalten Rücksicht zu nehmen. Sind zwei Felder gleich günstig, so belegen wir wiederum ein beliebiges davon. Dieses Verfahren nennt man "Matrixminimum-Verfahren", weil man die Zusammenfassung von Zahlen in einem rechteckigen Schema auch "Matrix" nennt . Durch das Matrixminimum-Verfahren hat sich das Ergebnis zum Spaltenminimum-Verfahren nicht verbessert, der Wert ist: Z = 35*160 + 30*100 + 25*210 + 5*580 + 50*510 + 5*320 = 43850 Im Allgemeinen ist aber das Matrixminimum-Verfahren das auf Anhieb ein gutes Ergebnis bringt. 2.3 Vergleich der Verfahren Das grafische Verfahren ist im Gegensatz zum Transportproblem- Verfahren einfach durchzuführen und ist sehr genau, dafür kann man es nur mit zwei Variablen rechnen. Das Transportproblem kann nur Minimierungsaufgaben lösen und erst mit dem Potential- oder Steppingstone-Verfahren kann das optimalste Ergebnis berechnen werden, kann dafür n-Variablen in sein Schema aufnehmen. 3. Methoden für alle Problemstellungen In diesem Teil der Arbeit werden wir uns dem Steppingstone- und Potential-Verfahren, die zum Transportproblem-Verfahren gehören, widmen. Daraufhin behandeln wir das Simplex-Verfahren, mit dem man alle Arten von linearen Optimierungsproblemen lösen kann. Am Ende von diesem Teil der Arbeit werden die Vorzüge und Nachteile der verschiedenen Verfahren gegenübergestellt. 3.1 Das Steppingstone Verfahren Das Steppingstone-Verfahren baut sich auf eine Ausgangslösung der Feldbelegungs-Verfahren des Transportproblems auf, die entweder vom Nordwestecken-Verfahren, dem Zeilenminimum-Verfahren, dem Spaltenminimum-Verfahren oder dem Matrixminimum-Verfahren kommt. Man nimmt im Grund immer das Verfahren, das die günstigste Ausgangslösung für das Steppingstone-Verfahren bietet, sonst hat man nur ein paar unnötige Rechnungen mehr. Im Allgemeinen ist dies das Matrixminimum-Verfahren wie wir aus dem Teil 2.2 dieser Arbeit entnehmen können. Das Prinzip des Steppingstone-Verfahren ist, daß man solange die Felder umlegt bis man auf das günstigste Ergebnis kommt. Beispiel zum Steppingstone-Verfahren Wir übernehmen das Beispiel von Teil 2.2 und zwar mit der Feldbelegung vom Matrixminimum-Verfahren, wir könnten auch die Ausgangslösung vom Spaltenminimum-Verfahren nehmen, weil sie ja in diesem Fall gleich waren. Der Ausgangsbertrag beträgt hier: Z = 35*160 + 30*100 + 25*210 + 5*580 + 50*510 + 5*320 = 43850 Nun versuchen wir durch eine Umbelegung der Feldbelegung einen besseren güngstigeren Wert zu erhalten. Wird zum Beispiel das Feld (A2/B1) belegt, so muß ein anderes Feld freigemacht werden, da jede Basislösung genau m + n - 1 besetzte Felder (Basisvariablen) hat. Bei der Umbelegung der Felder muß man immer auf die Zeilen- und Spaltenwerte achten, damit die Feldbelegung nicht im Widerspruch zu ihnen steht. Um zu zeigen und herauszubekommen, ob durch Umbelegung der Felder ein besserer Wert erreicht werden kann, bezeichnen wir das belegte Feld mit "k". An dem Buchstaben "k" können wir, in der Tabelle 2 nachverfolgen, wie die Verschiebung der Werte in der Tabelle ist und welche Auswirkung die Feldumbelegung hat. Tabelle 2 Der Gesamtwert der neuen Feldbelegung ergibt jetzt: Z = 35*420 + 30*100 + 15*510 + 40*580 + 25*210 + 5*320 =56450 Wie man dem Ergebnis entnehmen kann, ist keine Verbesserung eingetreten, man läßt also alles wie es ist. Nachdem bei diesem Feld keine Verbesserung eingetreten ist probiert man das nächste Feld aus. Man probiert jetzt alle Felder aus, ist der Wert besser übernimmt man und wenn er schlechter ist fährt man mit dem nächten Feld fort, bis man beim optimalen Ergebnis ist. Das Ausprobieren, das wie das Überqueren eines Baches ist, in dem man von Stein zu Stein schreitet, um über den Bach zu kommen, gab dem Verfahren den Namen. Das Ausprobieren jedes einzelnen Feldes wollen wir jetzt überspringen und schauen uns die Endumstellung in Tabelle 4 an. Wenn wir dieTabelle 3 mit 4 vergleichen, sehen wir, daß nur doch eine Feldumbelegung notwendig war, um von der Matrixminimumbelegung das optimale Ergebnis zu erhalten. |
Fern
| | Veröffentlicht am Donnerstag, den 22. Juni, 2000 - 15:31: |
|
Ist dies alles oder folgt noch weiterer Text? |
|
