Post on 05-Apr-2015
transcript
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Operations Research
Vorlesung/Übung im SS 2008
Professor Dr. Egbert Kahle
Veranstaltungsbeginn ab 7.4. : 16.15 Uhr
Klausur: wird noch bekannt gegeben
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Inhalt1. Einführung (Begriff und Inhalt von OR)2. Lineare Programmierung -Simplex Algorithmus3. Sonderfälle4. Postoptimale Rechnungen5. Mehrzielprobleme6. Dualität7. Netzplantechnik8. Tourenplanung
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
1. EinführungBegriff und Inhalt von Operations Research
Der Begriff wurde im 2. Weltkrieg in den USAfür die Analyse von Wirkungen militärischerOperationen geprägt und dann auf wirtschaft-liche Probleme übertragen.In UK oft als Operational Research und inDeutschland auch als Unternehmensforschung,Optimalplanung oder Optimierungsrechnungbezeichnet.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Definition:Anwendung mathematischer Methoden zur Vorbereitung optimaler Entscheidungen
Voraussetzung:Schaffung eines formalen Modells, das dieEinflußgrößen der Wirkungen sachgerechtabbildet.
Ökonomisches Prinzip:Gegebenes Ziel - minimaler MitteleinsatzGegebener Mitteleinsatz - Maximale Zielerr.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Daraus folgen Anforderungen für die Formu-lierung mathematischer Modelle
reale Entscheidungs- mathematischessituation Entsch.modell
reale Entscheidung mathematischeModellösung
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Fehlerquellen
- Abbildungsfehler- Modellorientiertheit ( Unterdrückung von Problemeigenschaften oder -variablen, die nicht ins Modell passen)- Fehlerhafte Algorithmenanwendung- Abweichungen bei der Rückinterpretation
Modellorientierung vs. Problemorientierung
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Problemtypen von OR
- Kombinatorische Probleme = Reihenfolgeprobleme = Transportprobleme = Optimierung von Produktionsprogrammen- Lagerhaltungsprobleme- Ersatzprobleme- Wartezeitprobleme- Konkurrenzprobleme
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Verfahren des OR
- Statische Programmierung = Lineare Programmierung = Nicht-lineare Programmierung = Ganzzahlige Programmierung- Dynamische Programmierung- Entscheidungsbaumverfahren- Netzplantechnik- Warteschlangentheorie- Spieltheorie- Simulation
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
2. Lineare Programmierung - Simplex Algo-rithmusAlgorithmusSystem von Rechenregeln, die - eindeutig formuliert und tatsächlich aus= führbar sind - nach endlich vielen Schritten zum Ergebnis führen - für eine ganzen Klasse von Entscheidungs= aufgaben geeignet sind - nach Anwendung eine Lösung garantieren oder die Unmöglichkeit der Lösung er= weisen
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
2.1 Grundmodell des Simplex-Algorithmus
Charakteristika:- Linearität von Zielfunktionen und Neben- bedingungen- Statische Betrachtung- Deterministische Daten- Stetige Größen, d.h. keine Ganzzahligkeits- erfordernisse, auch nicht teilweise
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
2.2. Praktisches BeispielDie Studenten der Vorlesung Operations Re-search (Sie) überlegen, wie sie einen möglichst optimalen Lernerfolg innerhalb des Teils “Line-are Optimierung” erhalten. Sie haben die Mög-lichkeit, Ihr Wissen aus Vorlesungen oder ausBüchern zu beziehen. Auf Grund der Erfahrun-gen “leidgeprüfter” Vorgänger wissen Sie, daß das Erfolgsverhältnis von Vorlesungsbesuch und Literaturarbeit 7 : 5 beträgt. Angeboten werden zu diesem Thema 6 Bücher in der Bibliothek.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Sie planen für dieses Semester höchstens 42 Arbeitstage (à 2,5 Stunden) ein, wobei einVorlesungstermin incl. Vor- und Nachbereitung6 Tage und die Beschäftigung mit einem Buch1 Tag in Anspruch nimmt. Wenn Sie davon aus-gehen, daß Sie während eines Semesters höch-stens 12 neue Freunde gewinnen können, so können Sie während einer Vorlesung jeweils 2kennenlernen, während die Beschäftigung mit einem Fachbuch dazu führen kann, daß Sie 3Freunde verlieren.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Für wichtige geschäftliche Anrufe planen Siemaximal 12 Telefonate ein, wobei Sie schätzen,daß Sie während einer Vorlesung 2 Anrufe ver-passen (Handyverbot), beim Lesen eines Bucheszu Hause aber drei Anrufe entgegennehmenkönnen.
Was ist zu tun ?
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Aufstellen des Problems in Ungleichungsform
6 xV + 1xB + xT = 42
2xV - 3xB + xF = 12
-2xV + 3xB + xH = 12
xB + xBS = 6
7 xV + 5 xB ---> Max!-2 xv + 3xB ---> Max! (und analog für die Freunde
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Umwandlung der Ungleichungen in Gleichungen
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Graphische Lösung
x2
x1
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Ein weiteres Beispiel
Die kurzfristige Produktionsprogrammplanunggeht von gegebenen variablen Kosten kvj für jedes Produkt j aus. Der Preis am Marktpj ist gegeben ; bei diesem Preis kann eine Absatzhöchstmenge x^j verkauft werden.So weit keine Produktionsbeschränkungen vorliegen, wird alles produziert, was einenpositiven Deckungsbeitrag dbj bringt.
dbj = pj - kvj > 0 !
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Bei der Überprüfung der Bedingung, ob dieProdukte einen positiven Deckungsbeitragbringen, ist die marktliche Verbundenheit zubeachten; Tasse und Untertasse, die als einGedeck verkauft werden, sind in diesem Sinnnur ein Produkt !Für den Betrieb als Ganzes muß noch gelten,daß er keinen Verlust macht (langfristig).
G = (pj - kvj) * xj - Kf >= 0 !
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Bei Vorliegen einer Kapazitätsbeschränkungwären die Produkte der Höhe des Deckungs-beitrags nach zu ordnen und es würde zuerstdas Produkt mit dem höchsten, dann das mitdem zweithöchsten Deckungsbeitrag usw.gefertigt, bis die Kapazität erschöpft ist.Eine solche Vorgehensweise würde aber keine optimale Nutzung der knappen Kapazitätbewirken: Der Deckungsbeitrag pro Einheitder knappen Kapazität, der relative Deckungs-beitrag, muß als Auswahlkriterium gelten.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Wenn mit vij der Faktorverbrauch des Faktorsi für die Produktion des Produkts j bezeich-net wird und von dem Faktor i nur die MengeVi zur Verfügung steht, muß gelten: vij * xj <= Vi
D.h. man kann nicht mehr verbrauchen als daist. Der relative Deckungsbeitrag dbrel ist:
dbreli, j = (pj - kvj) : vij
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Der relative Deckungsbeitrag wurde von Schmalenbach (1930) als optimale Geltungszahlbezeichnet.Beispiel: Produkt 1 Produkt 2 Produkt 3Preis 160 100 80kvj 60 50 40Absatz - 40 90 300höchstmengeVerbrauch 8 2 1Bestand 480
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Nach den Deckungsbeiträgen ergäbe sich eine Produktion von 40 P1 und 80 P2, dannwäre der Faktorbestand verbraucht. DieSumme der Deckungsbeiträge ist 8000.Nach den relativen Deckungsbeiträgen sieht es so aus: Produkt 1 Produkt 2 Produkt 3dbrel 12,5 25 40Menge - 90 300Verbrauch- 180 300DB - 4500 12000
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Der Deckungsbeitrag steigt auf 16500 anWenn nun ein zweiter Engpaßfaktor auftritt,mit einem Bestand von 350 und Verbrauchs-werten v21 = 5, v22= 2 und v23 = 4, dann ist eine andere Reihenfolge optimal: Produkt 1 Produkt 2 Produkt 3dbrel 20 25 10Menge 34 90 -Verbrauch 170 180 -DB 3400 4500DBgesamt = 7900
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Allgemeiner Ansatz für LP
G = (pj - kvj) * xj - Kf --> Max !
vij * xj </= Vi
xj </= Xj
xj >/= 0
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Ansatz für das Beispiel
(160 - 60) x1+(100- 50)x2 + (80 - 40) x3 -> Max!
8 x1 + 2 x2 + x3 </= 4805 x1 + 2 x2 + 4x3 </= 350 x1 </= 40 x2 </= 90 x3 </= 300
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
8 x1 + 2 x2 + x3 + x4 = 4805 x1 + 2 x2 + 4 x3 + x5 = 350 x1 +x6 = 40 x2 + x7 = 90 x3 + x8 = 300
100x1+ 50 x2 + 40 x3 ----> Max!
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
x1 x2 x3 x4 x5 x6 x7 x8 by4 8 2 1 1 0 0 0 0 480y5 5 2 4 0 1 0 0 0 350y6 1 0 0 0 0 1 0 0 40y7 0 1 0 0 0 0 1 0 90y8 0 0 1 0 0 0 0 1 300
Z -100 -50 -40 0 0 0 0 0 0 (ggf. - KF)
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
x1 x2 x3 x4 x5 x6 x7 x8 by4 0 2 1 1 0 - 8 0 0 160y5 0 2 4 0 1 - 5 0 0 150x1 1 0 0 0 0 1 0 0 40y7 0 1 0 0 0 0 1 0 90y8 0 0 1 0 0 0 0 1 300
Z 0 -50 -40 0 0 100 0 0 4000
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
x1 x2 x3 x4 x5 x6 x7 x8 by4 0 0 -3 1 -1 -3 0 0 10x2 0 1 2 0 1/2 -5/2 0 0 75x1 1 0 0 0 0 1 0 0 40y7 0 0 -2 0 -1/2 5/2 1 0 15y8 0 0 1 0 0 0 0 1 300
Z 0 0 60 0 25 -25 0 0 7750
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
x1 x2 x3 x4 x5 x6 x7 x8 by4 0 0 -27/5 1 -8/5 0 6/5 0 28x2 0 1 0 0 0 0 1 0 90x1 1 0 4/5 0 1/5 0 -2/5 0 34y6 0 0 -4/5 0 -1/5 1 2/5 0 6y8 0 0 1 0 0 0 0 1 300
Z 0 0 40 0 20 0 10 0 7900
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Verschiedene Auswahlregeln für die Pivot-Spalte
SUA - Steepest Unit AscentRichtet sich nach dem Zielfunktionszuwachs proEinheit z. B. Deckungsbeitrag pro Stück
-Standardverfahren
GC - Greatest ChangeSucht den nächsten Eckpunkt mit der größten Verschiebung der ZielfunktionVor allem sinnvoll bei mehreren nach SUA gleich-wertigen Spalten oder kleinen SUA- Unterschieden
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Anwendung von GC auf das zweite Beispiel
x1 x2 x3 x4 x5 x6 x7 x8 by4 8 0 1 1 0 0 -2 0 300y5 5 0 4 0 1 0 -2 0 170y6 1 0 0 0 0 1 0 0 40x2 0 1 0 0 0 0 1 0 90y8 0 0 1 0 0 0 0 1 300
Z -100 0 -40 0 0 0 50 0 4500
Neue Pivot-Spalte x1 mit DB 3400; bei x3 :1700
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
x1 x2 x3 x4 x5 x6 x7 x8 b
y4 0 0 -27/5 1 -8/5 0 6/5 0 28 x1 1 0 4/5 0 1/5 0 -2/5 0 34y6 0 0 -4/5 0 -1/5 1 2/5 0 6x2 0 1 0 0 0 0 1 0 90y8 0 0 1 0 0 0 0 1 300
Z 0 0 40 0 20 0 10 0 7900
Das Lösungstableau entspricht dem bei SUA,jedoch sind die Zeilen anders angeordnet.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Weitergehende Schritte:- Probe nach jedem Schritt möglich, am Ende wichtig- Interpretation der Ergebnisse = Lösungswerte in der b - Spalte (RHS) = Lösungswerte in der Z - Zeile (Schatten- preise)Wichtig: Der Unterschied in der Interpretationvon Schattenpreisen der Basisvariablen undder Schlupfvariablen
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Ein weiteres Beispiel (modifiziertes Bsp.Paschka-Skript, Aufgabe 2)
Vier Produkte A,B,C und D werden zu folgendenPreisen in folgenden Mengen verkauft:A 200 zu 80; B 50 zu 120; C 100 zu 70; D 200 zu 30.Die variablen Kosten sind kA = 60, kB = 20, kC = 20 und kD = 25.Der Rohstoffverbrauch beträgt bei Stoff 1 v1A =2,v1B = 4, v1C = 6 und v1D = 1; es sind 1000 V1 da.Bei Stoff 2 gilt : v2A = 3, v2B = 6, v2C = 1, v2D = 1und 550 vorhanden. Fixkosten betragen 200.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
xA xB xC xD y1 y2 y3 y4 y5 y6 * b
y1 2 4 6 1 1 0 0 0 0 0 1000y2 3 6 1 1 0 1 0 0 0 0 550y3 1 0 0 0 0 0 1 0 0 0 200y4 0 1 0 0 0 0 0 1 0 0 50 y5 0 0 1 0 0 0 0 0 1 0 100y6 0 0 0 1 0 0 0 0 0 1 200
Z -20 -100 -50 -5 0 0 0 0 0 0 -200
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Auswahl:SUA -- xB/y4
GC -- xC/y5 gleichwertig
Optimale Lösung nach drei Schritten:xA = 50, xB = 50, xC = 100
Methodenwahl unerheblich.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
2.4. Probleme mit unzulässiger Ausgangs- lösung
Typischerweise handelt es sich hier um Probleme, die gleichzeitig kleiner-gleich und größer-gleich Bedingungen oder auchGleich-Bedingungen enthalten.Beispiel: Es werden Stühle für 2 GE und Hocker für 1 GE hergestellt. Ein Hocker benö-tigt 4 h und ein Stuhl 2 h. 20 h sind verfügbar.Zwei Hocker müssen mindestens gefertigtwerden.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Ansatz:
2 x1 + 4 x2 </= 20 x2 >/= 2
2 x1 + x2 ---> Max!
Der einfachste Weg ist die Multiplikation dergrößer-gleich Bedingung mit -1; dann ist sieeine kleiner-gleich-Bedingung.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
x1 x2 x3 x4 b
y1 2 4 1 0 20y2 0 -1 0 1 -2
Z -2 -1 0 0 0
Hier wird die Auswahlregel verändert. Zuerstwerden die negativen Elemente der b-Spalteberücksichtigt und auf diese SUA oder GCangewendet. In Betracht kommen nur Spaltenmit negativen Koeffizienten. (y2/x2)
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
1. Iterationx1 x2 x3 x4 b
y1 2 0 1 4 12x2 0 1 0 -1 2
Z -2 0 0 -1 2
Diese Lösung ist zulässig, aber nicht optimal.SUA oder GC führt hier zu keinem Unterschied.Pivot-Element: y1/x1
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
2. Iterationx1 x2 x3 x4 b
x1 1 0 1/2 2 6x2 0 1 0 -1 2
Z 0 0 1 3 14Optimale Lösung. Es werden 6 Stühle und zweiHocker gefertigt. Eine Erhöhung der Kapazitätum eine Einheit erhöht den Umsatz um 1 GE. Eine Verringerung der Mindestmenge Hockerum 1 würde den Umsatz um 3 GE erhöhen.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Vorgehensweise bei mehreren größer-gleichBedingungen.Bei Vorliegen mehrerer größer-gleich-Bedin-gungen in einem Maximierungsproblem gibtes zwei mögliche Vorgehensweisen:Will man alle effizienten Punkte des Lösungs-raums bestimmen, dann werden die größer-gleich Bedingungen nach dem üblichen Aus-wahlkriterium bestimmt, d.h. Min ( bj/vij).Will man hingegen auf kürzestem Weg in denRaum zulässiger Lösungen wird Max (bj/vij)gewählt.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Beispiel (ohne Textvorgabe)
x1 x2 x3 x4 x5 x6 x7 x8 b
y1 8 2 1 1 0 0 0 0 480y2 1 0 0 0 1 0 0 0 40y3 -1 0 0 0 0 1 0 0 -20y4 -1 0 -1 0 0 0 1 0 -30y5 0 1 1 0 0 0 0 1 50
Z -100 -80 -50 0 0 0 0 0 0
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Iterationx1 x2 x3 x4 x5 x6 x7 x8 b
y1y2y3y4y5
Z
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Für die 1. Iteration kommen jetzt in Frage:
y3 oder y4; als Spalten mit entsprechendennegativen Koeffizienten liegen x1 und x3 vor.x1 hat den größeren Zielzuwachs (SUA), aberauch GC.Die beiden Vorgehensweisen verglichen:Min (bj(vij) führt zu Pivot-Element y3/x1Max (bj/vij) zu y4/x1
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Iteration 1ax1 x2 x3 x4 x5 x6 x7 x8 b
y1 0 2 1 1 0 8 0 0 320y2 0 0 0 0 1 1 0 0 20x1 1 0 0 0 0 -1 0 0 20y4 0 0 -1 0 0 -1 1 0 -10y5 0 1 1 0 0 0 0 1 50
Z 0 -80 -50 0 0 -100 0 0 2000
Lösung noch nicht zulässig. Weiter mit y4/x6
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Iteration 2ax1 x2 x3 x4 x5 x6 x7 x8 b
y1 0 2 -7 1 0 0 8 0 240y2 0 0 -1 0 1 0 1 0 10 x1 1 0 1 0 0 0 1 0 30x3 0 0 1 0 0 1 -1 0 10y5 0 1 1 0 0 0 -1 1 50
Z 0 -80 50 0 0 0 -100 0 3000
Zulässig, aber nicht optimal. Wie 1b.SUA führt zu y2/x7; GC zu y5/x2.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Iteration 1bx1 x2 x3 x4 x5 x6 x7 x8 b
y1 0 2 -7 1 0 0 8 0 240y2 0 0 -1 0 1 0 1 0 10y3 0 0 1 0 0 1 -1 0 10x1 1 0 1 0 0 0 -1 0 30y5 0 1 1 0 0 0 0 1 50
Z 0 -80 50 0 0 0 -100 0 3000
Zulässig, aber nicht optimal; SUA führt zu y2/x7GC zu y5/x2; hier wird GC verfolgt.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Iteration 2bx1 x2 x3 x4 x5 x6 x7 x8 b
y1 0 0 -9 1 0 0 8 -2 140 y2 0 0 -1 0 1 0 1 0 10y3 0 0 1 0 0 1 -1 0 10x1 1 0 1 0 0 0 -1 0 30x2 0 1 1 0 0 0 0 1 50
Z 0 0 130 0 0 0 -100 80 7000
Noch nicht optimal. Nächstes Pivot-Elementy2/x7
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Iteration 3bx1 x2 x3 x4 x5 x6 x7 x8 b
y1 0 0 -1 1 -8 0 0 -2 60x7 0 0 -1 0 1 0 1 0 10y3 0 0 0 0 1 1 0 0 20x1 1 0 0 0 1 0 0 0 40x2 0 1 1 0 0 0 0 1 50
Z 0 0 30 0 100 0 0 80 8000
Optimale Lösung. Probe.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
M - MethodeDas ist die zweite Lösungsmethode bei Vor-liegen unzulässiger Ausgangslösungen,beschrieben in Angermann, A., Entscheidungs-modelle, Frankfurt 1963, S. 213 ff.Da sie meines Erachtens komplizierter ist alsder vorherige Rechenweg, wird sie nur formalbeschrieben:Es werden für jede größer-gleich und gleich-Bedingung zusätzliche Hilfsvariable eingeführtund diese in der Zielfunktion mit einem Koeffi-zienten M versehen.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Zur Gewinnung einer zulässigen Ausgangs-lösung wird dann das M-fache der Zeilen mitentsprechenden Bedingungen von der Ziel-funktion abgezogen. Danach wird dann das üblicher Iterations-verfahren durchgeführt.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Darstellung am Hocker-Beispiel:
x1 x2 x3 x4 h1 b
y1 2 4 1 0 0 20y2 0 1 0 1 1 2
Z -2 -1 0 0 M 0
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Umgewandelt
x1 x2 x3 x4 h1 b
y1 2 4 1 0 0 20y2 0 1 0 1 1 2
Z -2 -1-M 0 -M -M -2M
Pivot-Element y2/x2
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
1. Iteration
x1 x2 x3 x4 h1 b
y1 2 0 1 -4 -4 12x2 0 1 0 1 1 2
Z -2 0 0 1 1 2
Diese Lösung ist zulässig, aber nicht optimal.Sie unterscheidet sich von der Lösung S. 7 unten durch die Vorzeichen in Spalten x4,h1.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Minimierungsaufgaben
Minimierungsaufgaben bei kleiner-gleich Bedin-gungen sind trivial. (xi = 0 für alle i)Bei Vorhandensein von größer-gleich (gleich und kleiner-gleich dürfen auch da sein) Bedin-gungen kann man am einfachsten die Ziel-funktion mit - 1 multiplizieren.Das hat nur Konsequenzen für die Interpretation.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Übungsaufgaben:a)
2 x1 - 3 x2 ---> Max
x1 + x2 >/= 22x1 - x2 </=102x1 +5x2 </= 15
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
x1 x2 x3 x4 x5 b-1 -1 1 0 0 -2 * 2 -1 0 1 0 10 2 5 0 0 1 15-2 3 0 0 0 0* 1 1 -1 0 0 2 0 -3 2 1 0 6 * 0 3 2 0 1 11 0 5 -2 0 0 4
*
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
b) 20 x1 + 25 x2 ---> Min! 2 x1 + 3 x2 = 50 5 x1 - x2 >/= 120 6 x1 + x2 </= 150
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
x1 x2 x3 x4 x5 x6 b-2 -3 1 0 0 0 -50 * 2 3 0 1 0 0 50-5 1 0 0 1 0 -120 6 1 0 0 0 1 15020 25 0 0 0 0 0* 1 3/2 -1/2 0 0 0 25 25:3/2 = 16 2/3 0 0 1 1 0 0 0 0:0 nicht betr. 0 17/2 -5/2 0 1 0 5 5: 17/2 = 10/17 0 -8 3 0 0 1 0 0:-8 nicht bes. 0 -5 10 0 0 0 -500
*
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Allgemeine Merkregeln für den Umgang mitverschiedenen Nebenbedingungen
1. Gleichheitsbedingungen müssen erfüllt werden. Das wird technisch so gelöst, daß eine Kleiner/gleich und eine Größer/gleich- Bedingung angesetzt werden, die dann beide erfüllt werden müssen.2. Alle Zeilen mit negativen Werten auf der rechten Seite müssen als Pivotzeilen heran- gezogen werden, bevor auf die Zielfunktions- zeile geachtet wird.(vgl. S.8)
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
3. Erst wenn die Bedingungen 1 und 2 erfüllt sind, wird normal” weiter innerhalb des Lösungsraumes optimiert.
Sobald auf der rechten Seite ein negativer Wertvorliegt oder wieder auftaucht, befindet mansich außerhalb des Lösungraums !!
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
3. SonderfälleDie Sonderfälle lassen sich wie folgt gliedern:
- Degeneration = Duale Degeneration = Primale Degeneration == Überbestimmter Punkt == Unbegrenzte Lösungen- Redundanz- Kein Lösungsraum
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Duale Degeneration
Die Zielfunktion “liegt” auf einer Nebenbedin-gung, d.h. gleiche Steigung beider .Sie wird erkennbar am Auftauchen des Wertes0 im Schattenpreis einer Nichtbasisvariablen.Es ergeben sich zwei optimale Ecken, derenLinearkombination beliebig viele Optimal-lösungen ergeben.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Beispiel
x1 + x2 ---> Max!
x1 + x2 </= 5 - x1 + 3x2 </= 9 3 x1 - x2 </= 9
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
x1 + x2 ---> Max!
x1 + x2 + x3 = 5 -x1 + 3x2 + x4 = 93x1 - x2 + x5 = 9
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
x1 x2 x3 x4 x5 b**
y1 1 1 1 0 0 5y2 -1 3 0 1 0 9y3 3 -1 0 0 1 9Z -1 -1 0 0 0 0
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
x1 x2 x3 x4 x5 b
y1 0 4/3 1 0 -1/3 2y2 0 8/3 0 1 1/3 12x1 1 -1/3 0 0 1/3 3
Z 0 -4/3 0 0 1/3 3
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
x1 x2 x3 x4 x5 b
x2 0 1 3/4 0 -1/4 3/2y2 0 0 -2 1 1 8x1 1 0 1/4 0 1/4 7/2
Z 0 0 1 0 0 5
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
x1 x2 x3 x4 x5 b
x2 0 1 1/4 1/4 0 7/2x5 0 0 -2 1 1 8x1 1 0 3/4 -1/4 0 3/2
Z 0 0 1 0 0 5
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Weiteres Beispiel (Übung):
12 x1 + 2 x2 ---> Max !
- 2 x1 + 3 x2 </= 12 6 x1 + x2 </= 42 x2 </= 6
2 x1 - 3 x2 </= 12
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Lösung I
x1 x2 x3 x4 x5 x6 b
y1 0 0 1 0 0 1 24x2 0 1 0 1/10 0 - 3/10 6/10x6 0 0 0 -1/10 1 3/10 54/10x1 1 0 0 3/20 0 1/20 69/10
Z 0 0 0 2 0 0 84
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Lösung II
x1 x2 x3 x4 x5 x6 b
y1 0 0 1 1/3 -10/3 0 6x2 0 1 0 0 1 0 6x6 0 0 0 -1/3 10/3 1 18x1 1 0 0 1/6 -1/6 0 6
Z 0 0 0 2 0 0 84
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Primale Degeneration
Sie liegt vor, wenn ein Eckpunkt überbestimmtist, d.h. mehr als zwei Gerade durch einen Eckpunkt laufen. Das bedeutet, daß bei derWahl zwischen den Beschränkungen mehrereMöglichkeiten bestehen. Nach Durchführungder Iteration wird dann der andere - ggf. die anderen - Wert in der RHS zu 0.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Beispiel
4 x1 + x2 ---> Max!
3 x1 - x2 </= 9 - x1 + 3 x2 </= 9 3 x1 - 3 x2 </= 9
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
x1 x2 x3 x4 x5 b
y1 3 - 1 1 0 0 9y2 - 1 3 0 1 0 9y3 3 - 3 0 0 1 9
Z - 4 -1 0 0 0 0
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Iteration 1a
x1 x2 x3 x4 x5 b
x1 1 -1/3 1/3 0 0 3y2 0 8/3 1/3 1 0 12y3 0 -2 -1 0 1 0
Z 0 -7/3 4/3 0 0 12
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Iteration 2a
x1 x2 x3 x4 x5 b
x1 1 0 3/8 1/8 0 9/2x2 0 1 1/8 3/8 0 9/2y3 0 0 -3/4 3/4 1 9
Z 0 0 13/8 7/8 0 45/2
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Iteration 1b
x1 x2 x3 x4 x5 b
y1 0 2 1 0 -1 0y2 0 2 0 1 1/3 12x1 1 -1 0 0 1/3 3
Z 0 -5 0 0 4/3 12
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Iteration 2 b
x1 x2 x3 x4 x5 b
x2 0 1 1/2 0 -1/2 0y2 0 0 -1 1 4/3 12x1 1 0 1/2 0 -1/6 3
Z 0 0 5/2 0 -7/6 12
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Iteration 3b
x1 x2 x3 x4 x5 bx2 0 1 1/8 3/8 0 9/2x5 0 0 -3/4 3/4 1 9x1 1 0 1/8 3/8 0 9/2
Z 0 0 13/8 7/8 0 45/2
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Mögliche Folgen primaler Degeneration:
1. Dualwerte lassen sich nicht mehr inter- pretieren.2. Es kann zu einem “Cycling” kommen, d.h., der Tausch von Nichtbasisvariablen zu Basisvariablen führt nicht mehr von dem bestehenden Punkt weg. Hier muß ein anderes Verfahren gewählt werden, indem suboptimale Zwischenschritte gewählt werden, d.h. eine andere Pivot-Spalte bestimmt wird.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Unbegrenzte Lösungen
Die Lösungsmenge ist unendlich.Man erkennt sie daran, daß in der Pivotspaltebei positiver RHS nur negative Koeffizientenvorhanden sind.Das muß nicht im Ausgangstableau sichtbarsein, sondern kann sich später ergeben.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Beispiel:
100 x1 + 50 x2 ---> Max!
- 30 x1 + 5 x2 </= 600 20 x1 - 100x2 </= 1000 x1 - x2 </= 100
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Ansatz
x1 x2 x3 x4 x5 b
y1y2 y3
Z
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
1. Iteration
x1 x2 x3 x4 x5 b
y1y2 y3
Z
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
2. Iteration
x1 x2 x3 x4 x5 b
y1xx
Z
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Iteration 3
x1 x2 x3 x4 x5 b
y1 0 0 1 -5/16 145/4 7825/2x1 1 0 0 -1/80 5/4 225/2x2 0 1 0 -1/80 1/4 25/2
Z 0 0 0 -15/8 275/2 11875
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Kein Lösungsraum
Dieser Fall kann nur eintreten, wenn dieNebenbedingungen widersprüchlich formu-liert sind und wenn es sich dabei sowohl umkleiner-gleich als auch größer-gleich odergleich-Bedingungen handelt.Auch das ist im Ausgangstableau nicht immergleich zu erkennen.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Beispiel
x1 + x2 ---> Max !
- 2 x1 + 2 x2 >/= 83/2x1 + 3 x2 </= 30 2 x1 - 6 x2 >/= 6
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Ausgangstableau
x1 x2 x3 x4 x5 b
y1 2 -2 1 0 0 -8y2 3/2 3 0 1 0 30y3 -2 6 0 0 1 -6
Z -1 -1 0 0 0 0
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Iteration I
x1 x2 x3 x4 x5 b
x2 -1 1 -1/2 0 0 4y2 9/2 0 3/2 1 0 18y3 4 0 3 0 1 -30
Z -2 0 -1/2 0 0 4
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Redundanz
Eine Nebenbedingung ist dann redundant, wenn sie keinen Einfluß auf die Struktur deraktuellen Lösung hat. Sie kann deshalb auchbei gegebenem Lösungsraum vernachlässigtwerden.Nur bei postoptimalen Rechnungen muß siebeibehalten werden, da sie dann relevantwerden kann.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
4. Postoptimale Rechnungen
Bei diesem Arbeitsschritt geht es darum, dieunter den Grundannahmen - Statik, Deter-minismus, Linearität - erarbeitete Lösungauf ihre Stabilität (Robustheit) und Reich-weite zu überprüfen. Dazu dienen:
- Sensitivitätsanalyse (Sensibilitätsanalyse)
- Parametrische Optimierung
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Bei der Sensitivitätsanalyse wird überprüft,inwieweit sich einzelne Parameter änderndürfen, ohne daß sich an der Lösung etwasqualitativ ändert. Eine qualitative Änderungliegt danach dann vor, wenn die Strukturvon Basis- und Nicht-Basisvariablen sichändert, d.h eine bisherige Nicht-Basisvari-able Basisvariable wird und vice versa.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Die parametrische Programmierung ist durcheine schrittweise Variation einzelner Ausgangs-daten gekennzeichnete, wobei die Schritt-länge durch die Vorgabe der Parameter be-stimmt wird. Es werden dann die Veränderungender Lösungen durch diese Vorgaben berechnet. Es ergeben sich praktisch Streuungsbereichefür die Eingangsdaten.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
x1 x2 x3 x4 x5 x6 x7 x8 by4 0 0 -27/5 1 -8/5 0 6/5 0 28x2 0 1 0 0 0 0 1 0 90x1 1 0 4/5 0 1/5 0 -2/5 0 34y6 0 0 -4/5 0 -1/5 1 2/5 0 6y8 0 0 1 0 0 0 0 1 300
Z 0 0 40 0 20 0 10 0 7900
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Ermittlung für das ProduktionsbeispielSensitivität der Zielfunktion:Für Produkt 1 gilt:In der Spalte x3 ist der Koeffizient 4/5,in der Spalte x5 1/5 und in der Spalte x7 -2/5.Die zugehörigen Werte in der Zielzeile werden nun durch die jeweiligen Koeffizienten dividiert und mit - 1 multiplziert; für dieBestimmung der Untergrenze werden nur posi-tive Koeffizienten verwendet und für dieObergrenze nur negative. Es ergibt sich:
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
max( -40 : 4/5; -20 : 1/5) </= p </= min (- 10: -2/5)d.h.max (-50;-100) </= p </= min (25) (bei min gibt es
nur einen Wert)Der Deckungsbeitrag von Produkt 1 kann um50 nach unten (-50) und 25 nach oben schwankenohne daß sich die optimale Lösung ändert, d.h.zwischen (100- 50 und 100 + 25), 50 und 125schwanken.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Allgemein lautet die Formel
max(- c*jk :a*jk; ajk>0) </= p </= min(-c*jk :a*jk;a*jk<0)
Für Produkt 2 gibt es nur einen Wert fürdie linkeSeite der Formel, d.h. es istmax (-10 : 1) </= p.Das bedeutet, daß der Deckungsbeitrag von Produkt 2 nach unten um 10 € sinken darf, bis sich die optimale Lösung ändert; nach oben gibtes keine Beschränkung.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Produkt 3 ist nicht im optimalen Produktions-programm. Der Schattenpreis von 40 € besagt, daß das Produkt erst produziert
würde,wenn der Deckungsbeitrag um 40 € auf 80 €
steigen würde. Es gibt keine untere Beschrän-kung.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Für die Beschränkungen oder Restriktionengelten folgende Sensitivitätsüberlegungen:
Erste Beschränkung:Es sind Leerkapazitäten von 28 Einheiten vor-handen; wenn die Beschränkung von 480 um28 Einheiten auf 452 sinkt, verändert sich dieStruktur der Lösung. Es gibt keine Beschrän-kung nach oben, weil schon im Optimum etwas über ist.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Zweite Beschränkung:
max ( - 34 : 1/5) </= p </= min (-28 : -8/5; -6: -1/5)
-170 </= p </= min (17,5; 30)
Die Restriktion kann um 170 nach unten und 17,5 nach oben schwanken, bevor sich dieStruktur der Lösung verändert.Kapazität 2: 180 - 367,5
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Dritte Beschränkung:Auch hier bestehen Leerkapazitäten; erst wenndie Absatzkapazität um mehr als 6, d.h. unter34 sinkt, verändert sich die Lösung. Nach obengibt es keine Beschränkung.
Fünfte Beschränkung:Es gilt im Prinzip das für die dritte Beschrän-kung Gesagte; die Beschränkung kann auf 0sinken, ohne daß sich etwas ändert; nach obengibt es ebenfalls keine Beschränkung.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Vierte Beschränkung:
max (-28: 6/5; -90 :1;-6:2/5) </= p </= min(-34:-2/5)
max ( - 23,3; -90; -15) </= p </= min (85)
-15 </= p </= 85
Die Absatzkapazität kann um 15 nach unten undum 85 nach oben, d.h. von 75 bis 175 schwanken,ohne daß sich die Lösung ändert.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
BeispielAusgangstableau
x1 x2 x3 x4 x5 x6 by1 0 1 1 0 0 0 5y2 1 0 0 1 0 0 7y3 1 1 0 0 1 0 10y4 -1 -2 0 0 0 1 -4
Z -2 -1 0 0 0 0 0
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Endtableau
x1 x2 x3 x4 x5 x6 by1 0 0 1 1 -1 0 2y4 0 0 0 -1 2 1 9x2 0 1 0 -1 1 0 3x1 1 0 0 1 0 0 7
Z 0 0 0 1 1 0 17
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Sensitivität der Zielfunktion:
Variable 1 : In der Zeile x1 sind nur zwei posi-tive Werte; es gibt nur eine Untergrenze :max (-1 : 1) = -1. Der Zielfunktionswert derVariablen 1 darf um 1 nach unten schwanken, bevor sich die Lösung ändert; nach oben gibtes keine Beschränkung.Variable 2: Hier gibt es eine Unter- und eineObergrenze: Sie kann um 1 nach unten undoben schwanken, d.h. zwischen 0 und 2, bissich etwas ändert.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Für die Beschränkungen gilt:
Die erste Beschränkung hat noch eine Rest-kapazität von 2; wenn die Ausgangsbeschrän-kung von 5 um diesen Wert unterschrittenwird, d.h. 3 unterschreitet, verändert sich dieLösung. Nach oben gibt es keine Beschränkung.Die zweite Beschränkung ist ausgeschöpft; es istmax ( -2:1; -7:1) </= p </= min (-9: -1; -3:-1)
-2 </= p </= 3Die Beschränkung 2 kann um 2 nach unten und um 3 nach oben, d.h von 5 bis 10 schwanken.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
6. DualitätHier erfolgt eine Veränderung der Gliederung,weil die parametrische Programmierung nurauf dem Hintergrund der Dualität erläutertwerden kann.Der Grundgedanke des Dualitätstheorems:Zu jedem (primalen) linearen Planungsproblemgibt es ein duales Problem; dabei wird dieKoeffizientenmatrix gestürzt und die Zielfunktiondes primalen Problems wird zu der RHS des dualen und die RHS des primalen zur Zielfunktionder dualen mit Gegentendenz (Min statt Max !)
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Wenn das primale Problem eine optimaleLösung hat, besitzt auch das duale Problemeine. Es gilt : Z max = f min.
Wenn das primale Problem keine endlicheoptimale Lösung hat, besitzt die duale Lösungkeine zulässige Lösung.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Beispiel:Primalproblem Dualproblem
2x1 + 4 x2 </= 20 2 y1 + y3 >/= -2 x2 >/= 2 4 y1 - y2 - 4y3 >/= -1- x1 + 4 x2 >/= 12
-2x1 - x2 ---> Max! 20 y1 - 2y2 -12 y3 --->Min!Das Primalproblem hat eine unzulässige Ausgangslösung;die größer-gleich Bedingungen werden mit - 1multipliziert. Das ergibt folgende Tableaus:
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Primalproblem
x1 x2 y1 y2 y3 by1 2 4 1 0 0 20y2 0 -1 0 1 0 -2y3 1 -4 0 0 1 -12
Z 2 1 0 0 0 0
Diese Lösung wäre optimal, ist aber wegen dernegativen Werte in der b-Spalte unzulässig. Eswird -12/-4 als Pivot-Element gewählt.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Dualproblem
y1 y2 y3 x1 x2 bx1 -2 0 -1 1 0 2x2 -4 1 4 0 1 1
ZD 20 -2 -12 0 0 0
Diese Lösung ist zulässig, aber nicht optimal. Es wird weiter iteriert. Es wird für die SUA (-12)das Pivot-Element 1/4 bestimmt.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Lösung Primalproblem
x1 x2 y1 y2 y3 by1 3 0 1 0 1 8y2 -1/4 0 0 1 -1/4 1x2 -1/4 1 0 0 -1/4 3
Z 9/4 0 0 0 1/4 -3
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Lösung Dualproblem
y1 y2 y3 x1 x2 bx1 -3 1/4 0 1 1/4 9/4y3 -1 1/4 1 0 1/4 1/4
ZD 8 1 0 0 3 3
Auf dieser Dualitätsbeziehung beruht auch dasVorgehen bei Vorliegen unzulässiger Ausgangs-lösungen ohne Einführen weiterer Hilfsvari-ablen (M-Methode).
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Vor allem bei nichtquadratischen Problemen,z.B. bei 2 Variablen und 4 Nebenbedingungenkann die Anwendung der dualen Methode, d.h.die Lösung des dualen Problems statt des primalen, die Zahl der Rechenschritte deutlichverkürzen.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Parametrische Optimierung
Hier gibt es mehrere Varianten: Man kann skalarparametrisch oder vektorparametrischoptimieren; im zweiten Fall können unterschied-liche Veränderungen gleichzeitig vorgenommenwerden, was aber sehr aufwendig ist. Hierwerden nur skalarparametrische Optimierungenbetrachtet, bei denen eine oder mehrere Restrik-tionen oder die Zielfunktionen mit dem gleichenParameter p modifiziert werden.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Bezugsbeispiel (Müller-Merbach, S. 106 ff.)Ausgangstableau
x1 x2 y1 y2 y3 by1 1 2 1 0 0 170y2 1 1 0 1 0 150y3 0 3 0 0 1 180
Z -300 -500 0 0 0 -36000
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Endtableaux1 x2 y1 y2 y3 b
x2 0 1 1 -1 0 20x1 1 0 -1 2 0 130y3 0 0 -3 3 1 120Z 0 0 200 100 0 13000
Hier soll nun die Beschränkung y2 von 40 bis150 variiert werden. Die Sensibilitätsanalyseergibt, daß bis zu einer Reduktion auf y2 = 110die Lösung stabil ist. (max -130/2;-120/3) = 40
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Es ergibt sich nun eine optimale Lösung von
x1 x2 y1 y2 y3 bx2 0 1 1 -1 0 60x1 1 0 -1 2 0 50y3 0 0 -3 3 1 0
Z 0 0 200 100 0 9000
Eine weitere Reduktion von y2 ist nur möglich,wenn y3 in die Lösung kommt. Dafür scheidetx1 aus (x1 = 0). y2 sinkt auf 60.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Das modifizierte Tableau lautet
x1 x2 y1 y2 y3 by1 0 0 1 -1 -1/3 50x1 1 0 0 1 -1/3 0x2 0 1 0 0 1/3 60
Z 0 0 0 300 200/3 -6000
Eine weitere Reduktion von y2 auf 40 geht nur,wenn x1 aus der Lösung ausscheidet und x2reduziert wird.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Es ergibt sich:
x1 x2 y1 y2 y3 by1 -1 0 1 -2 0 90x2 1 1 0 1 0 40y3 -3 0 0 -3 1 60Z 200 0 0 500 0 -16000
Man sieht im Vergleich der Lösungen, wie sichin jedem Reduktionsschritt die Lösungs- undZielfunktionswerte, d.h. Primal- und Dualwerteändern.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
5. MehrzielproblemeGrundproblemeProbleme multipersonaler Entscheidungen
- Zieldifferenzen = Koordination von Zielen = Legitimation von Zielen = Rationalität von Kollektivzielen- Informationsdifferenzen- Gleichzeitiges Auftreten von Ziel- und Informationsdifferenzen
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Triviale oder perfekte Lösung
Alle Ziele erreichen ihre Optimalausprägungin der gleichen Ecke des Beschränkungs-raums.Eine solche Lösung ist nur selten zu finden.Im allgemeinen werden Kompromisse nötigsein.Phase 1: Kompromißfindung für einstufige ProblemePhase 2: Kompromißfindung für LP-Probleme
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Probleme der materiellen Zusammenführungvon mehreren Zielen
1. Die jeweils verfügbaren Alternativen be- stimmen den Lösungsraum (nicht die Wunschvorstellung des ET !)Beispiel: Alternativen P,H,S P schlecht 1,- 0 100 100H sehr mäßig 1,20 50 60 110S mäßig 1,50 100 0 100
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Im Beispiel tritt die Alternative K hinzu:
K sehr gut 2,-
Neue BewertungsmatrixP 0 100 100H 30 80 110S 40 50 90K 100 0 100
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
2. Punktezuordnung zu Kriterien
Wenn die Kriterien gleichgewichtet sein sollen,muß die Höchstpunktzahl gleich sein, nicht dieSumme der vergebenen Punkte.Beispiel:
K1 K2 HPZ PunktSumA1 sehr gut schlecht 100 25A2 schlecht sehr gut 100 100A3 sehr gut schlecht 100 25A4 sehr gut schlecht 100 25A5 sehr gut schlecht 100 25
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
3. Nichtlineare Präferenzen
Die Linearität der Nutzenzuordnung zur Aus-prägung der Kriterien ist nicht immer gegeben.Beispiel:Dezibel (db) ist eine Meßzahl, bei der 3 Ein-heiten Differenz die Verdoppelung der Geräusch-empfindung ausdrücken. Die Funktion muß umgerechnet werden, z.B.db 68 69 70 71 72 73 74 75 76% 10 12 15 20 24 31 40 48 63
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Wir kaufen ein Auto :5 Alternativen, 6 Kriterien
K1 K2 K3 K4 K5 K6 max min min min max blau
A1 160 10 30000 70 gut grünA2 170 11 32000 72 sehr gut blauA3 150 9 25000 74 mäßig rotA4 180 11 35000 68 gut gelbA5 190 13 34000 76 sehr gut schwarz
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Rangplatzverfahren für das Beispiel
K1 K2 K3 K4 K5 K6
A1 4 2 2 2 3,5 3,5 17A2 3 3,5 3 3 1,5 1 15A3 5 1 1 4 5 3,5 19,5A4 2 3,5 5 1 3,5 3,5 18,5A5 1 5 4 5 1,5 3,5 20
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Rangziffernverfahren (Punktebewertung)Das Schlechteste erhält 0, das Beste 100 Pkt.
K1 K2 K3 K4 K5 K6
A1 25 75 50 89 50 0 289A2 50 50 30 71 100 100 401A3 0 100 100 43 0 0 243A4 75 50 0 100 50 0 275A5 100 0 10 0 100 0 210
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Es gibt im wesentlichen zwei Erscheinungs-formen von Mehrzielproblemen:- Eine gegebene Entscheidungsmatrix mit mehreren Alternativen mit gegebenen Ausprä- gungen für mehrere Kriterien- Ein lineares Entscheidungsproblem mit mehreren Zielen, bei dem ein Raum konfliktärer Ziele ermittelt wird
Beide Formen können von Unsicherheit, Dyna-mik, Fuzziness und Rationaler Indeterminiert-heit überlagert werden.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Mehrzielprogrammierung
Es folgen zwei Beispiele zur Mehrziel-Programmierung
1. 2 Variable, 3 Nebenbedingungen, 2 Ziele
2. 6 Variable, 8 Nebenbedingungen, 7 Ziele
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Beispiel 14x1 + x2 ---> Max x2 ---> Max2x1 + x2 </= 205/6 x1 + x2 </= 10x1 + x2 >/= 5
( x2 >/= 6)
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
x1 x2 y1 y2 y3y4 b
y1 2 1 1 0 0 20
y2 5/6 1 0 1 0 10
y3 -1 -1 0 0 1 -5
y4 0 1 0 0 0 1 6
z1 -4 -1 0 0 0 0
z2 0 -1 0 0 0 0
z1+z2 -4 -2 0 0 0 0
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Erster Zwischenschritt zur Erzeugung
einer zulässigen Lösung
x1 x2 y1 y2 y3 b
y1 0 -1 1 0 2 10
y2 0 1/6 0 1 5/6 35/6
x1 1 1 0 0 -1 5
z1 0 3 0 0 -4 20
z2 0 -1 0 0 0 0
z1+z2 0 2 0 0 -4 20
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
x1 x2 y1 y2 y3 b
y1 1 1/2 1/2 0 0 10
y2 0 7/12 -5/12 1 0 10/6
y3 0 -1/2 1/2 0 1 5
z1 0 1 2 0 0 40
z2 0 -1 0 0 0 0
z1+z2 0 0 2 0 0 40
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
x1 x2 y1 y2 y3 b
y1 1 0 6/7 -6/7 0 60/7
y2 0 1 -5/7 12/7 0 20/7
y3 0 0 1/7 6/7 1 45/7
z1 0 0 19/7 -12/70 260/7
z2 0 0 -5/7 12/7 0 20/7
z1+z2 0 0 2 0 0 40
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
x1 x2 y1 y2 y3 b
y1 7/6 0 1 -1 0 10
y2 5/6 1 0 1 0 10
y3 -1/6 0 0 1 1 5
z1 -19/6 0 0 1 0 10
z2 5/6 0 0 1 0 10
z1+z2 -14/6 0 0 2 0 20
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Lösungen:
z1 max: x1=10 x2=0 z1=40 z1+z2=40
z 2 max: x1=0 x2=10 z1=10 z1+z2=20 z2=10
z1 und z2 max:2 Lösungen
a) x1=10 x2=0 z1=40 z2= 0 z1+z2=40
b) x1=60/7 x2= 20/7 z1=260/7 z2=20/7 z1+z2= 40
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Kompromißfindung:
Idealziel: z1=40 z2=10 (beide max)
Einführung einer zusätzlichen NB:
x2 6 für z1 max
Lösung: x1=4,82 x2=6 z1=25,27
z1 ist 63,2% vom Idealziel (bei absoluter
Betrachtung, relativ = 50%)
z2 ist 60% vom Idealziel
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Iterativ x2 anheben bei:x1=4,58 x2 6,2 z1=24,51ergeben sich Unterschiede der relativen Zielerreichung unter 1%Abbruch der RechnungStatt des relativen Abstandes zum Idealziel könnte man auch ein Gleichgewicht zwischen beiden Variablen x1,x2 anstreben und über Nebenbedingungen einführen. Das ist aber nicht zielkonform.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Eine Unternehmung kann 6 verschiedene Produkte A, B, C, D, E und F produzieren. Von jeden Produkt können max. 200 Stück verkauft werden; die Preise und variablen Kosten gestalten sich wie folgt:
A B C D E F
p 80 100 120 140 160 180
kv 30 40 60 70 90 100
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Es wird auf 3 Maschinen gefertigt, deren Kapazitätverbrauch und Kapazität wie folgt auszudrücken ist:
A B C D E F Kap
M1 5 4 6 10 7 20 2000
M2 2 6 5 7 15 10 2400
M3 10 5 12 14 5 8 3000
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Bei der Produktion werden 2 Schadstoffe s1,s2 freigesetzt, sowie 3 knappe Ressourcen R1,R2,R3 verbraucht, deren Ausstoß bzw. Verbrauch minimiert werden soll. Diese Faktoren lauten wie folgt:
A B C D E F
S1 3 4 5 6 7 8
s2 4 2 6 3 8 1
R1 4 3 5 7 2 4
R2 8 4 6 2 7 5
R3 6 9 3 4 5 8
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Die Firma strebt nach Max. von Umsatz und Gewinn sowie nach min. Umweltbelastung und -inanspruchnahme. Für die rechnerische Lösung werden die Umweltfaktoren willkürlich Emissionsobergrenzen auferlegt.
s12000 s2 1000 R12000 R23000 R33000
Dann wird das Problem rechnerisch für Gmax und Umax gelöst. Es ergeben sich 2 Lösungen
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Gmax: xa=96 xb=200 xd=72 xc,e,f=0
Gmax=21840 U=37760
S1=1520 S2=1000 R1=1488 R2=1712 R3=2664
Umax: xb=200 Xd=90,72 xe=35,01 xc=7,96
xa,f=0
G=21278 Umax=39257,29
S1=1629,18 S2=1000
R1=1344,83 R2=1274,27 R3=2361,8
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Für die Berechnung der Minimierungslösungen für S1, S2, R1, R2, R3 benötigt man Mindestwerte für Umsatz und Gewinn. Hier werden ausgehend von den jeweiligen Minima Abschläge von ca.25% Gewinn und 33%Umsatz gemacht.
U 25000 G 15000 Es ergeben sich folgende Lösungen:
S1min:xa=200 xb=90 xc,d,e,f=0
G=15400 U=25000 S1=960 S2=980 R1=1070
R2=1960 R3=2010
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
S2 min: xb=159 xf=68 xa,c,d,e=0
G=15000 U=28181 S1=1182 S2=386
R1=750 R2=977 R3=1977
R1min: xb=72 xe=101 xf=45 Xa,c,d=0
G=15000 U=31473 S1=1355 S2=598
R1=1406 R2=500 R3=1031
R2min: xc=31 xd=188 Xa,b,e,f=0
G=15000 U=29375 S1=1250 S2=625
R1=1406 R2=500 R3=1031
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
R3min: xc=104 xd=125 Xa,b,e,f=0
G=15000 U=30000 S1=1271 S2=1000
R1=1396 R2=875 R3=813
Jedes Optimum hat eine andere Lösungsmenge und -soweit nicht durch NB erzeugt- andere Werte für ihre Zielgrößen. Es ergibt sich folgende Ideallösung:
G=21840 U=39257
S1=960 S2=386 R1=598 R2=500 R3=813
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Alle 7 Teiloptima sind effiziente Lösungen:
G U S1 S2 R1 R2 R3
Gmax 21840 37760 1520 1000 1488 1712 2664
Umax 21278 39257 1629 1000 1345 1274 2362
S1min15400 25000 960 980 1070 1960 2010
S2min15000 28181 1182 386 750 977 1977
R1min 15000 31473 1355 1000 598 1222 1514
R2min 15000 29375 1250 625 1406 500 1031
R3 min 15000 30000 1271 1000 1396 875 813
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Lösungsansatz für einen Kompromiß, relative Erreichung des Idealziels in %:
G U S1 S2 R1 R2 R3 Summe
Gmax 100 89 16 0 0 17 0 223
Umax 92 100 0 0 16 47 16 271
S1min 6 0 100 3 47 0 35 191
S2min 0 22 67 100 83 67 37 376
R1min 0 45 41 0 100 51 62 299
R2min 0 31 57 61 9 100 88 346
R3 min 0 35 54 0 10 74 100 273
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Im Durchschnitt am günstigsten liegen die Lösungen von S2 min mit einer durchschnittlichen Zielerreichung von 54% bis 55%. Die Ursache für die O-Werte für G, U, S2 und R1 liegt aber in der willkürlichen Setzung der Grenzwerte. Dabei sind besonders die Größen G und S2 Engpässe, in zwei Fällen sogar simultan. Hier könnte man die Opportunitätsgrößen abrufen, um den „trade-off“ zwischen den Werten zu bestimmen, oder man müßte Lösungen für einen Grenzwert G 0 und für S2 nahe unendlich ermitteln, um dann die relative Bedeutung der Lösungen festzulegen.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Im vorliegenden Beispiel sind die Werte fürS2 min recht gut, wenn man berücksichtigt,daß der Gewinn, der hier mit 0 bewertet ist,ja bereits mit der Mindestfestlegung auf 75%des absoluten Maximums gut bedient ist.Es wäre zu prüfen, ob es eine Lösung gibt,die bei Festlegung von Nebenbedingungenmit 60 - 65 % der Ausgangswerte eine zulässige Lösung erzeugt.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Arbeitsschritte für das Mehrziel-programmieren- Erstellen aller "technischen" Nebenbe- dingungen- Erstellen aller Zielfunktionen- Einsetzen der Zielfunktionen als zusätz- liche Nebenbedingungen mit "offenen" Restriktionen-- Durchrechnen für alle Einzeloptima
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
- Überprüfen der Lösungswerte im Ausgangsproblem- Abschätzung von Konfliktbereichen = Wie weit liegen Lösungen auseinander = Gibt es eine "ausgezeichnete" Lösung ? = Ist die Punktesumme oder der kleinste relative Abstand aller Ziele das geeignete Maß an "Gerechtigkeit" ?
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
- Bewertung der Einzeloptima in Prozent- punkte und Wahl der Punktesumme (Problem der Gerechtigkeit)- Minimierung des Abstandes der Ergebnisse vom Idealziel für alle Zielfunktionen (für zwei Zielfunktionen gut darstellbar, bei drei und mehr sehr konfliktären Zielfunktionen z.T. nicht ermittelbar; noch kein Algorithmus verfügbar)
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Ergänzung Bei der Suche nach einem Kompromiß, z.B.zwischen den sieben Zielvariablen gibt eszwei Möglichkeiten:- In Anlehnung an die Rangziffernmethode die Summe der relativen Abstände zum Ideal zu minimieren; das ist eine "Gesamt- lösung" , aber kein individueller Kompromiß- Bestimme den geometrischen Ort des gleichen relativen Abstands vom Ideal; bei2 Zielen ein Punkt, bei 3 Zielen eine Gerade,...das ist der "echte" Kompromiß
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Die Möglichkeiten der Kompromißfindungbei mehreren Zielen :- Addition der Zielfunktionen (bringt verdeckte Gewichtung)- Addition normierter Zielfunktionen (Problem unterschiedlicher Vorzeichen der Zielvariablen und der Summe der Zielvari- ablen; führt häufig nur zu einer Ecke, kann aber einen Kompromiß aufzeigen)- Einführung zusätzlicher Nebenbedingungen aus den Zielfunktionen (aufwendig, Höhe der Beschränkung willkürl.)
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
- Bewertung der Einzeloptima in Prozent- punkte und Wahl der Punktesumme (Problem der Gerechtigkeit)- Minimierung des Abstandes der Ergebnisse vom Idealziel für alle Zielfunktionen (für zwei Zielfunktionen gut darstellbar, bei drei und mehr sehr konfliktären Zielfunktionen z.T. nicht ermittelbar; noch kein Algorithmus verfügbar)
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Bei der Frage nach der Rationalität eines Kom-promisses steht zuerst die der Konfliktaus-tragung an (-> Orga II) (Rationalität und Ethik).
Wenn man sich für die Austragungsform“Kompromiß” entschieden hat, sind drei Aspekte zu beachten:- Effizienz- Gerechtigkeit- Solidarität
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
- Die Anforderung der Effizienz bedeutet, daß kein Beteiligter “unnötig” schlechter gestellt wird (Pareto- Optimalität)- Die Anforderung der Gerechtigkeit verlangt, daß die inhaltliche Lösung und das Verfahren fair sind, d.h. von allen als fair empfunden werden.(Lit.: Rawls,J., Eine Theorie der Gerechtigkeit, Frankfurt/M. 1979)- Solidarität verlangt von allen Beteiligten, daß sie die Interessen der Unternehmung und der anderen Beteiligten berücksichtigen
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Für die Berücksichtigung dieser Anforderungenkommen in den typischen Fällen verschiedeneHilfs-Zielfunktionen zum Tragen:- Maximierung der Gesamtzielerreichung, z.B. die Summe der Punkte- Minimierung der relativen Abweichung vom Einzelideal für alle Ziele mit gleicher Abwei- chungsverteilung- Minimierung der absoluten Abweichungen vom Einzelideal für alle Ziele
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Probleme der Kompromißregeln:- Legitimation unterschiedlicher Abweichungen- Ausprägungsabhängige Präferenz- Bedeutung der relativen Abweichung bei unterschiedlich hohen Ausprägungen- Verhältnis von Gerechtigkeit und Solidarität- Kommunikation der Präferenzen und ihrer Änderungen über den Lösungsraum- Inkonsistenz von Präferenzen
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Ein weiteres Beispiel:Eine Firma stellt zwei Produkte her; von Produkt 1 müssen mindestens 20 und höchstens 180 , von Produkt 2 höchstens 250 hergestellt werden. Es bestehen zwei Produk-tionsbeschränkungen; die Koeffizienten lautenfür Produkt 1 : 2 für B1 und -10 für B2 undfür Produkt 2 : 3 für B1 und 10 für B2.Die Beschränkung B1 beträgt 900, B2 ist 1400.Die Preise betragen 100,- DM pro Stück, dievariablen Kosten p1 = 30 und p2 = 200 DM/St.Die Produkte verursachen Schadstoff von 4 kgje Stück (P1) und 2 kg (P2).
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Der Ansatz für Umsatz und Gewinnmaxi-mierung:
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Wie verändert sich der Ansatz , wenn Schad- stoffminimierung als weiteres Ziel hinzutritt ?
Lösungswerte:Gmax : x1 = 180, X2 =0, U 18000 G12600 S 720Smin : x1= 20, x2 = 0, U = 2000 G = 1400 S 80Umax: x1 = 180,x2 = 180, U= 36000 G = -5400
S = 1080
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
X1 x2 y1 y2 y3 y4 y5 b
y1 -1 0 1 0 0 0 0 -20y2 1 0 0 1 0 0 0 180y3 0 1 0 0 1 0 0 250y4 2 3 0 0 0 1 0 900y5 -10 10 0 0 0 0 1 1400U -100 -100 0 0 0 0 0 0G -70 100 0 0 0 0 0 0S 4 2 0 0 0 0 0 0
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Netzplantechnische Grundbegriffe
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Ein Netzwerk wird durch Knoten und Kantenbestimmt
1
2
3
4
A
B
C
D
Gerichteter Graph der Aktivitäten A,B,C,D
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Die Elemente eines Netzes können durchAktivitäten oder Ereignisse beschriebenwerden.Im allgemeinen werden Aktivitäten durchKanten und Ereignisse durch Knoten abgebildet, es gibt aber auch Verfahren,in denen Aktivitäten durch Knoten abgebildetwerden.Den Aktivitäten werden Zeiten (Zeit pro Akti-vität), den Ereignissen Zeitpunkte zugeordnet.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Für die Aktivitäten im Beispiel gilt folgendeBeziehung: A (muß) vor C (fertig sein) B vor D
Regeln:Ein Pfeil geht immer von einem Knoten miteiner niedrigen Ordnungszahl zu einemmit einer höheren.Zwei Pfeile können nicht den gleichenAnfangs- und Endpunkt haben.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Modifikation des Beispiels: A und B vor C
A
B
C
D
1
2
3
4
Die Numerierung der Knoten muß verändertwerden. Die Aktivität 2 - 3 wird als Schein-aktivität bezeichnet.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Den Aktivitäten werden Zeiten zugeordnet.A 7, B 9, C 6, D2.Gesamtdauer des “Projekts A - D” bei derersten Fassung :Max ( A + C, D + B ) = 13
Gesamtdauer bei der zweiten Fassung:Max ( A + C, B + C, B + D) = 15Der kritische Weg ist hier 1, 2, 3, 4.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Netzplantechnik - Beispiel
Aktivitäten Vorrang DauerA vor D 6B vor E,F,J 5C vor H und L 5D vor I 3E vor I 6F vor K 4H vor K 5I vor M 4J vor M 7K 3L vor N 6M 4N 4
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
A,6
B,5
C,5
D,3
E,6
F,4
H,5
I,4
J,7
K,3
L,6
M,4
N,4
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
0
1
2
3
4
5
6
7
8
A,6
B,5
C,5
D,3
E,6
F,4
H,5
I,4
J,7
K,3
L,6
M,4
N,4
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUSTermine und kritischer WegKnoten FMS SEZ Puffer 0 0 0 0 1 6 8 2 2 5 5 0 3 5 9 4 4 11 11 0 5 10 16 6 6 11 15 4 7 15 15 0 8 19 19 0Kritischer Weg : 0 - 2 - 4 - 7 - 8/ B,E,I,M. Dauer 19
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUSNetzplanverkürzung - Kelley-Algorithmus
VerkürzungsmöglichkeitenAktivität Verkürzung KostenA von 6 auf 4 je 500B von 5 auf 4 1000H von 5 auf 3 je 200I von 4 auf 3 3000K von 3 auf 2 2000M von 4 auf 3 4000
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Verkürzungsschritte
Nur auf dem kritischen Weg (0 - 2 - 4- 7 - 8)1. Schritt : B von 5 auf 4 10002. Schritt : I von 4 auf 3 + 30003. Schritt : M von 4 auf 3 + 4000
Mehr geht nicht; ein anderer Weg ist nicht kritisch geworden.Crash Time 16 bei 8000 Kosten.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Weiteres Beispiel als Word Programme
Semester-OR-Klausur 2003 und SemORnetzplan
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
4.4 TourenplanungTourenplanung kann in verschiedenen Formen geschehen: Als Linienplan, Fahrplan oder mit der Planung einzelner Touren von einem odermehreren Zentrallägern.Betrachtet wird der Fall mit einem Zentrallagerund vorgegebenen Liefermengen. Die Orte sind durch ihre Koordinaten gegeben; die geometrische Entfernung wird über den Satzdes Pythagoras ermittelt. Sie muß für realeStrecken um einen Faktor 1,2 bis 1,4 korrigiertwerden.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Die Koordinaten seien zum Beispiel:
Punkt 1 : 60/60 Punkt 2 : 50/70 Punkt 3: 70/90
... ZL: 20/100
14 33 ... 57
28 ... 42
... 51
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
nach 2 3 4 5 6 7 8 9 10 ZLvon 1 14 33 11 32 14 15 45 22 36 57 2 - 28 21 41 10 18 54 28 28 42 3 - - 20 5 40 32 18 25 62 51 4 - - - 21 21 14 34 15 43 52 5 - - - - 40 30 14 22 61 36 6 - - - - - 11 51 22 22 73 7 - - - - - - 40 11 30 65 8 - - - - - - - 30 70 36 9 - - - - - - - - 40 5810 - - - - - - - - - 95
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Weitere Randbedingungen
- Räumliche Barrieren- Fahrzeit und Geschwindigkeit- Ladezeiten- Zeitfenster- Teillieferungen (möglich oder unmöglich)- Mehrere Lager
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Beispiel
StandortkoordinatenA: 30/30 B: 60/50 C: 40/80 D: 20/120E: 70/140 F: 90/150 G: 120/145 H: 140/100I: 130/70 K: 110/40 Z: 90/90
TransportmengenA: 8t B: 6t C: 5t D: 7t E: 9t F: 4t G:6tH: 8t I: 5t K: 7tKapazität: 4 LKW à 18t
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Entfernungstabellenach B C D E F G H I K ZvonA 36 51 91 117 134 146 130 108 81 85B - 36 81 91 104 112 94 73 51 50C - - 45 67 86 103 102 91 81 51D - - - 54 76 103 122 121 120 76E - - - - 22 50 81 92 108 54F - - - - - 30 71 89 112 60G - - - - - - 49 76 105 63H - - - - - - - 32 67 51I - - - - - - - - 36 45K - - - - - - - - - 54
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
TourenplanungSavingsmethodeAusgangspunkt sind lauter einzelne Pendel-touren. Die Tour mit der höchsten Lademengewird mit der oder den Touren, die die größteErsparnis (Savings) bringen, aufgefüllt.Die Savings ergeben sich aus D(ZL/P1)+D(ZL/P2)- D(P1/P2)Sie werden in einer Savingsmatrix ausgewiesen.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Savingsmatrix B C D E F G H I KA 99 85 70 22 11 2 6 22 58B - 65 45 13 6 1 7 22 53C - - 82 38 25 11 0 5 24D - - - 76 60 36 5 0 10E - - - - 92 67 24 7 0F - - - - - 93 40 16 2G - - - - - - 65 32 12H - - - - - - - 64 38I - - - - - - - - 63
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
1. Z - E - Z; 9t; 108 km
2. Z - E - F - Z;13t; 54 + 22 + 60 = 136 km
(Ersparnis 228 -136 = 92 km)
3. Es passen mengenmäßig nur noch C oder I
Z - E - F - I - Z; 18t;54+22+89+45=210km
Z - C - E - F - Z;18t; 51+67+22+60 =200km. (!)
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
4. Z - A - Z; 8t;170 kmZ - A - B - Z; 14t;171 km; Ersparnis 99km;Kapazität erschöpft5. Z - H - Z; 8t; 102 kmZ - H - I - Z; 13t;128 km ; Ersparnis 64 km oderzur besseren MengenauslastungZ - H - K - Z; 15 t; 172 km; Ersparnis 38 km6. Z - D - G - Z; 13 t; 242 km; Ersparnis 36 kmZ - D - G - I - Z; 18 t; 300 km, wenn bei 5. die zweite Alternative gewählt wurde, sonst7. Z - K - Z; 7t 108 km
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Gesamtstrecke I IIZ-C-E-F-Z 200km 200kmZ-A-B-Z 171km 171kmZ-H-I-Z 128km Z-H-K-Z 172kmZ-D-G-Z 242km Z-D-G-I-Z 300kmZ-K-Z 108km _______ _______Summe 849km 843km
Summe Pendeltouren 1178km
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Eine dritte Variante wäre
1. Z - C - E - F - Z 200km2. Z - A - B - Z 171km3. Z - H - G - Z 163km4. Z - K - I - Z 135km5. Z - D - Z 152km _______Summe 821 km
Das ist deutlich besser als I und II
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Sweepmethode
Es werden im Uhrzeigersinn, bei 12 begin-nend, Touren gebildet, bis die Kapazitäts-grenze erreicht ist.
1. F-G-H;18t;190 km2. I-K-B ; 18t;182 km3. A-C;13t;187 km4. D-E;16t;184 kmSumme 743 km
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Jetzt wird bei G gestartet
1. G-H; 14t; 163 km2. I-K-B; 18t; 182 km3. A-C; 13t;187 km4. D-E; 16t; 184 km5. F;4t;120 km Summe 836 km
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Jetzt wird bei H gestartet
1. H-I; 13t; 128 km2. K-B;13t; 155 km3. A-C; 13t; 187km4. D-E; 16t; 184 km5. F-G; 10 t; 153 km Summe 807 km
Als nächstes würde bei I gestartet. Das ergibtaber den zweiten Plan. 743 km ist die nachdiesem Verfahren günstigste Lösung.
Forschungsgruppe Kybernetische Unternehmens-Strategie der Universität Lüneburg
Universität Lüneburg • 21332 Lüneburg • Institut für Betriebswirtschaftslehre, insb. Entscheidung und Organisation • Prof. Dr. Egbert Kahle
FOKUS
Verfahrensvergleich
Es gibt keine eindeutige Überlegenheit einesVerfahrens. Umfangreiche Erfahrungenhaben ergeben, daß die Sweepmethode gutgeeignet ist, wenn das Lager zentral liegtund das Verhältnis der Zahl der Touren zurZahl der anzufahrenden Stellen recht klein,etwa <2 ist. Bei dem Depot in Randlage undvielen Stellen pro Tour ist die Savings-methode besser.