Einführung in das Operations Research


Notes (de cours), 2003

61 Pages


Extrait


Inhaltsverzeichnis

Vorwort

0 Einfuhrunq

i Lineare Optimierunq
1.1 Beispiel
1.2 Graphische Losung
1.3 Der Simplex-Algorithmus
1.4 Das Simplex-Tableau
1.5 Der Allgemeine Simplex-Algorihtmus fur den Grundtypus
1.6 Beispiel bei mehrstufiger Kuppelproduktion
1.7 Aufgaben
Aufgabe 1
Aufgabe 2
Aufgabe 3
Augabe 4
Aufgabe 5
Losung Aufgabe
Losung Aufgabe

2 Heuristisches Verfahren am Beispiel des Travelling Salesman Problems
2.1 Das Travelling Salesman Problem
2.2 Heuristische Verfahren
2.2.1 Das Verfahren des „besten Nachfolgers"
2.2.2 „Die sukzessive Einbeziehung von Stationen"

3 Dvnamische Proqrammierunq am Beispiel des Travelling Salesman Problem
3.1 Erlauterung der Methode am Beispiel
3.2 Der Algorithmus der dynamischen Programmierung fur das Travelling Salesman Problem
3.3 Das allgemeine Prinzip der dynamischen Programmierung
3.4 Aufgaben

4 Die Methode ..Branch and Bound" am Beispiel des Travelling Salesman Problems
4.1 Die allgemeine Methode am Beispiel des „0-1 Rucksack Problems"
4.2 Anwendung des Prinzips ..Branch and Bound" auf das Travelling Salesman Problem
4.3 Aufgaben
Aufgabe 1
Aufgabe 2
Aufgabe 3
Aufgabe 4

Vorwort

Wahrend die vordergrundigen Handwerkszeuge des Informatikers Software, Hardware einem kaum greifbaren Wandel unterliegen - was heute gelernt wird, ist morgen schon wieder veraltet - stehen die zugrunde liegenden Strukturen als unverruckbare Invarianten fest.

Ihr Verstandnis stellt somit eine notwendige Bedingung sowohl fur tiefer gehende Einsichten, als auch fur einen verstandsgemaBen Gebrauch der Anwendungen dar.

In der Informatik sind diese Strukturen insbesondere die Logik und daran anknupfend der Algorithmus. Beide haben eine mehr als zweitausendjahrige Geschichte (vgl. den beruhmten Euklid’schen Divisionsalgorithmus!).

Wahrend diese Begriffe allgemein im Rahmen der Theoretischen Informatik abgehandelt werden, sollen hier nun darauf aufbauend, exemplarisch konkrete Algorithmen und insbesondere die fundamentalen Entwurfstechniken dargestellt werden. Diese wurden im Wesentlichen in den sechziger Jahren des vorigen Jahrhunderts entwickelt und gelten bis heute unverandert.

Entsprechend dem Studiengang Wirtschaftsinformatik, fur den diese Vorlesung konzipiert ist, werden beispielhaft einige okonomische Anwendungen aufgezeigt.

Die Monographie stellt die Grundlage einer dreiUigstundigen Vorlesung an der Berufsakademie Mosbach dar. Sie schlielit an die Vorlesung uber theoretische Informatik an und setzt deren Inhalte im Wesentlichen voraus (vgl. z.B.: Schlageter-Rauhut: „Einfuhrung in die Theoretische Informatik").

Entsprechend dem Charakter einer Einfuhrung beschrankt sie sich auf das Grundsatzliche. Wer sich intensiver mit dem Thema auseinander setzen mochte, sei auf die fundamentals Literatur verwiesen (z.B.: Dantzig, G.B.: „Lineare Programmierung und Erweiterungen" Berlin-Heidelberg-New York; Horowitz,E., Sahni, S.: „Algorithmen. Entwurf und Analyse" Berlin-Heidelberg-New York).

Fur Auswahl und Richtigkeit des Inhalts zeichnet Herr Dr. Schlageter verantwortlich. Die Ausarbeitung und das Layout ubernahmen Frau D. Raab und Herr O. Bertsch.

Mosbach im April 2003

0 Einfiihrung ..

Operations"

Operationalisierung, ursprunglich in den 30er Jahren des letzten Jahrhunderts von dem Wissenschaftstheoretiker Bridgeman eingefuhrter Begriff, der besagt, dass ein theoretischer Begriff durch Angabe eines Messverfahrens zu definieren ist. Im weiteren Sinne besagt der Begriff, dass ein Zielverfahren operationalisiert ist, wenn die zugrundeliegende Problemstellung eindeutig unter Angabe ihrer jeweiligen Nebenbedingung bestimmt ist.

..Research"

Untersuchung, Nachforschung

Aus der operationalisierten Struktur ergibt sich dann, dass der Losungsweg in einzelne Schritte zerlegt werden kann, mit anderen Worten algorithmisch durchgefuhrt werden kann.

Ziel der Vorlesung ist es, einerseits mit den typischen Algorithmen und den entsprechenden Entwurfstechniken vertraut zu machen, andererseits sollen exemplarisch einige okonomische Anwendungen aufgezeigt werden.

1 Lineare Optimierung

1.1 Beispiel

In einer Maschinenfabrik werden zwei Zubehorteile A und B auf den Automaten I,II und III gemaO) dem nachfolgenden Produktionsplan angefertigt:

Abbildung in dieser Leseprobe nicht enthalten

Bemerkunq:

Offenbar liegen lineare Grofien vor (d.h. die Variablen liegen nur in der ersten Potenz vor). Die Zielfunktion gibt das operationalisierte Endverhalten an, wobei die Restriktionen die jeweiligen eindeutig definierten Nebenbedingungen darstellen.

1.2 Graphische Losung:

Wir beziehen uns auf das Beispiel in 1.1

Abbildung in dieser Leseprobe nicht enthalten

Umformen der Zielfunktion (Z) in die Hauptform der Geradengleichung

Abbildung in dieser Leseprobe nicht enthalten

Fur konkrete Werte von z erhalt man dann beispielsweise foigende Geraden, die jeweils denselben Gewinn liefern (Isogewinnlinien):

Abbildung in dieser Leseprobe nicht enthalten

Allgemein erkennt man, dass der Gewinn so lange gesteigert werden kann, solange die Iso- Gewinnlinie der Zielfunktionsgeraden parallel verschoben werden kann und dabei noch Punkte des Definitionsbereichs erfasst.

Hieraus ergibt sich insbesondere:

„Der Losungspunkt befindet sich stets in einem Eckpunkt"

Bemerkuno:

In dem Fall, in dem die Zielfunktionsgerade parallel zu einer Begrenzungsgeraden verlauft, erhalten wir daruber hinaus eine Strecke als Losungspunkte.

Fur unsere Aufgabe ergibt sich speziell als Losung:

Es werden 50 Teile A und 40 Teile B produziert, der Gesamtgewinn betragt hierbei 160 Geldeinheiten.

Anmerkunq:

Bei Untersuchung von n Gutern benotigen wir n-Dimensionen!

1.3 Der Simplex-Algorithmus

Bemerkunqen:

1. Unter einem Simplex versteht man einen n-dimensionalen Raum, der von ( n -1 )- dimensionalen Raumen begrenzt ist (z.B. Wurfel, Dreieck...).
2. Der Simplex-Algorithmus ist ein systematisches Verfahren zum Absuchen der jeweiligen Eckpunkte eines Simplex, wobei dieses abgebrochen wird, wenn keine Leistungsverbesserung mehr moglich ist.

Wirformen das Problem aus 1.1. aquivalent in nachstehende Grundform urn.

(Beachte: a < b <=> ( s + a = b as > 0))

Abbildung in dieser Leseprobe nicht enthalten

Definition:

Die Si heiSen Schlupfvariable. Diejenigen Variablen, mit Ausnahme von z, die in der Zielfunktion vorkommen, heilien „Nicht-Basis-Variable“. Alle ubrigen Variablen heifien „Basis-Variablen“.

Dann gehen wir nach dem folgenden Schema vor ( vgl. bei den einzelnen Schritten jeweils das nachfolgende Beispiel):

Abbildung in dieser Leseprobe nicht enthalten

Waiter im Beispiel aus 1.1 (vgl. S. 9):

Die Abfrage nach Schritt 1 wird offenbar mit „ja“ beantwortet.

Wir bestimmen dann die Pivotspalte (Schritt 2).

Die Pivotzeile (Schritt 3) erhalten wir, indem wir die rechte Seite (RS) durch die Koeffizienten der Pivotspalte (neue Basisvariable!) dividieren (warum?).

Pivotspalte

Abbildung in dieser Leseprobe nicht enthalten

Nun fuhren wir mit Hilfe der Umformungsschritte des GauS’schen Algorithmus den Austauschschritt (Schritt 4) durch. Dabei wird Xi durch s2 ersetzt und umgekehrt. Es ergibt sich das folgende Gleichungssystem:

Abbildung in dieser Leseprobe nicht enthalten

Bemerkunq:

Nach diesem Schritt produzieren wir 70 Teile A und 0 Teile B. Der Gewinn betragt hierbei 140 GE, die Schlupfvariablen geben okonomisch die Restkapazitat der jeweiligen Automaten an (also: Automat 1 hat eine Restkapazitat von 40, Automat 2 lauft voll und bei Automat 3 betragt die Restkapazitat 120). Entsprechend unserer graphischen Losung haben wir somit ausgehend vom Ursprung (0/0) den Eckpunkt (70/0) erreicht. Man beachte wie durch das Austauschen der Nichtbasisvariablen mit negativem Koeffizient in der Tat der Gewinn gesteigert wurde.

Fortsetzunq des Verfahrens liefert:

Abbildung in dieser Leseprobe nicht enthalten

Bemerkunq:

Wird beispielsweise eine Schlupfvariable „0“ gesetzt, so gilt das Gleichheitszeichen der Restriktion, d.h. wir befinden uns auf einer Begrenzungsgeraden. Bei zwei derartigen Variablen also auf zwei Geraden, d.h. im Schnittpunkt.

1.4 Das Simplex-Tableau

Abbildung in dieser Leseprobe nicht enthalten

Dann fuhren wir fur oben aufgefuhrte Rechnung, die wir hier noch einma! wiederholen, folgende Schreibweise ein „Simplex-Tableau“

Pivotelement: Kreuzung von Pivot- Zeile und Pivotspalte

Abbildung in dieser Leseprobe nicht enthalten

1.5 Der allgemeine Simplex - Algorithmus fur den Grundtypus

Abbildung in dieser Leseprobe nicht enthalten

Bemerkunq:

Durch das obige Schema ist der Simplex-Algorithmus fur den Grundtypus definiert. Der Grundtypus besagt, dass wir Maximierungsprobieme unter ‘ Restriktionen behandeln.

Der allgemeine Fall der z.B. Minimierungsprobleme „>=“ Oder Gleichheitsrestriktionen zur Aufgabe hat, kann jedoch leicht auf diesen zuruckgefuhrt werden.

Beispielsweise fuhren wir eine Minimierungsaufgabe auf eine Maximierungsaufgabe zuruck, indem wir die Zielfunktion mit „-1“ durchmultiplizieren.

Definition:

Jeder Schritt zu einem neuen Tableau (d.h. jeder Schleifendurchlauf) heifit Simplex-Iteration! Hinreichende Bedingung:

... dass der Algorithmus nach endlich vielen Schritten terminiert ist, dass qmin > 0 bei der Bestimmung der Pivotzeile eindeutig bestimmt ist.

Penn:

In diesem Fall wird bei jedem Schritt eine Leistungsverbesserung erzielt. Dabei geht der Algorithmus zu einer benachbarten Ecke der zuletzt gepruften Ecke im Simplex uber. Wurde der Algorithmus nicht terminieren, so musste er schliettlich eine Ecke zweimal durchlaufen. Dies musste der Fall sein, da jeder Simplex nur endlich viele Ecken hat.

Wir wurden also fur einen Eckpunkt 2 verschiedene Zielfunktionswerte erhalten, dies widerspricht der Definition der Funktion.

Sonderfalle:

Solche ergeben sich:

a) Es existiert kein q > 0. Dann ist die Aufgabe nicht losbar. Dies bedeutet, dass die Restriktionen widerspruchlich formuliert sind.

b) qmin ist nicht eindeutig bestimmt. Man wahlt dann q zufallig aus. Geometrisch bedeutet dies im zweidimensionalen Fall, dass sich mehr als zwei Restriktionsgeraden in einem Eckpunkt schneiden.

Bemerkung:

In diesem Fall kann es dann vorkommen, dass der Algorithmus ins „kreiseln“ gerat.

c) Ein Zielfunktionskoeffizient = 0. In diesem Fall ist die Losung nicht eindeutig bestimmt. Geometrisch bedeutet dies im zweidimensionalen Fall, dass die Zielfunktionsgerade parallel zu einer Restriktionsgeraden verlauft.

1.6 Beispiel bei mehrstufiger Kuppelproduktion1

Ein Betrieb der Kuppelproduktion verarbeitet die Rohstoffe 1 und 2, die in den Mengen von maximal 50 000 bzw. 80 000 Mengeneinheiten (ME) beschafft werden konnen und 700,- bzw. 1000,- Geldeinheiten (GE) je ME kosten.

Bei der Verarbeitung zerfallt das erste Produkt zu genau 60% in das Zwischenprodukt 3 und zu 40% in das Zwischenprodukt 5. Aus dem zweiten Produkt entstehen bei der Verarbeitung zu 30% das Zwischenprodukt 4 und zu 70% das Zwischenprodukt 6. Die Produkte 3 und 4 rnussen veredelt werden, wodurch Kosten von 200,- bzw. 100,- GE je ME entstehen.

Nach der Veredelung werden sie zum Fertigprodukt 7 gemischt. Dieses kann in unbegrenzter Menge zum Preis von 900,- GE je ME abgesetzt werden. In dem Produkt 7 darf ein bestimmter Bestandteil (Verunreinigung), der in dem Zwischenprodukt 3 mit 7% und in 4 mit 4% enthalten ist, maximal mit 6% auftreten.

Schliefilich werden die Produkte 5 und 6 nach bestimmten Rezepturen zu den Fertigprodukten 8 und 9 verarbeiteO die in den Hochstmengen von 60 000 bzw. 40 000 ME fur 1200,- bzw. 1000,- GE je ME abgesetzt werden konnen.

Das Produkt 8 besteht zu 20% aus 5 und zu 80% aus 6. Dagegen setzt sich das Produkt 9 zu 40% aus 5 und zu 60% aus 6 zusammen.

Gesucht ist das gewinnmaximale Produktionsprogramm.

Formulierung der Problemstellung in der linearen Planungsrechnung: Xi := zu produzierende Mengen des Produktes i, i = 1,...,9

Dann:

Abbildung in dieser Leseprobe nicht enthalten

[...]

Fin de l'extrait de 61 pages

Résumé des informations

Titre
Einführung in das Operations Research
Université
University of Cooperative Education Mosbach
Cours
Operations Research
Auteur
Année
2003
Pages
61
N° de catalogue
V208600
ISBN (ebook)
9783656361671
ISBN (Livre)
9783656363439
Taille d'un fichier
14250 KB
Langue
allemand
Mots clés
einführung, operations, research
Citation du texte
Dr. Wolfgang Schlageter (Auteur), 2003, Einführung in das Operations Research, Munich, GRIN Verlag, https://www.grin.com/document/208600

Commentaires

  • Pas encore de commentaires.
Lire l'ebook
Titre: Einführung in das Operations Research



Télécharger textes

Votre devoir / mémoire:

- Publication en tant qu'eBook et livre
- Honoraires élevés sur les ventes
- Pour vous complètement gratuit - avec ISBN
- Cela dure que 5 minutes
- Chaque œuvre trouve des lecteurs

Devenir un auteur