Combined

Produktion und Logistik

PW / OR WS 06/07

0-1

Produktionswirtschaft und Operations Research Dr. Rainer Kleber Fakultät für Wirtschaftswissenschaft Lehrstuhl für Produktion und Logistik [email protected] Sprechstunde: Donnerstag 10.00-12.00 Uhr in G22-E016 Kurzbeschreibung: Die Vorlesung vermittelt einen Überblick über den Gegenstand der industriellen Produktionswirtschaft und gibt eine Übersicht über Grundlagen der Produktionstheorie und wesentliche Aufgaben des Produktionsmanagements. Im Rahmen der Behandlung von Planungsinstrumenten zur Lösung solcher Managementaufgaben wird auf wichtige Verfahren des Operations Research eingegangen. Hierbei werden sowohl die Modellierungstechnik als auch grundlegende Optimierungsmethoden des Operations Research vermittelt.

Produktion und Logistik

PW / OR WS 06/07

Gliederung 1 Einführung 1.1

Einführung in die Produktionswirtschaft (PW)

1.2

Einführung in Operations Research (OR)

2 Produktionstheorie 2.1

Aufgaben der Produktionstheorie

2.2

Produktionstheorie auf Objektebene

2.3

Produktionstheorie auf Ergebnisebene

2.4

Produktionstheorie auf Erfolgsebene

3 Lineare Optimierung 3.1

Grundlagen der Linearen Optimierung

3.2

Der Simplex-Algorithmus

3.3

Dualität

3.4

Sensitivitätsanalyse

3.5

Lineare Optimierungsproblem mit spezieller Struktur

3.6

Lösung von linearen Optimierungsproblemen in der Praxis

0-2

Produktion und Logistik

PW / OR WS 06/07

0-3

4 Produktionsmanagement 4.1

Aufgaben des Produktionsmanagements

4.2

Nachfrageprognosen

4.3

Produktionsprogrammplanung

4.4

Materialbedarfsplanung

4.5

Losgrößenplanung

5 Ganzzahlige Optimierung 5.1

Grundlagen der Ganzzahligen Optimierung

5.2

Branch & Bound-Verfahren

5.3

Heuristische Lösungsverfahren

6 Weitere Anwendungen und Gebiete des Operations Research

Literaturempfehlungen [1] Domschke und Drexl, Einführung in Operations Research, 6. Auflage, Springer, 2005 [2*] Dyckhoff, Produktionstheorie, 5. Auflage, Springer, 2006 [3*] Günther und Tempelmeier, Produktion und Logistik, 6. Auflage, Springer, 2005 [4] Hillier und Lieberman, Introduction to Operations Research, 8. Auflage, McGraw, 2005 [5] Thonemann, Operations Management, Pearson, 2005

(* alternativ auch vorherige Auflage bzw. bei Dyckhoff Grundzüge der Produktionswirtschaft, 4. Auflage)

Produktion und Logistik

PW / OR WS 06/07

0-4

Literaturhinweise Gliederungspunkt 1.1 PW-Einführung 1.2 OR-Einführung

Textstellen (2) 1-9 (1) 1-12

Vorherige Auflage (2*) 1-8

2.1 2.2 2.3 2.4

Aufgaben der PT PT auf Objektebene PT auf Ergebnisebene PT auf Erfolgsebene

(2) (2) (2) (2)

9-12 19-106 119-155, 162-176 189-200, 212-252

(2*) (2*) (2*) (2*)

9-12 20-106 119-155, 164-176 189-200, 212-252

3.1 3.2 3.3 3.4 3.5

Grundlagen der Linearen Optimierung Simplex-Algorithmus Dualität Sensitivitätsanalyse Allg. und spezielle LOP‘s

(1) (1) (1) (1) (1)

12-20 20-27, 34-35 35-40 44-49 74-77, 83-86

4.1 4.2 4.3 4.4 4.5

Aufgaben des PM Nachfrageprognosen Produktionsprogrammplanung Materialbedarfsplanung Losgrößenplanung

(2) (3) (3) (2) (2)

367-372, (3) 1-10 142-151, (4) 35-75 139-142, 151-1162 270-280, 340-346 314-320, (3) 192-208

(2*) (3*) (3*) (2*) (2*)

367-372, (3*) 1-10 138-147 135-138, 147-155 270-280, 340-346 314-319, (3*) 187-200

(1) (1) (1)

110-117 121-126 117-121

5.1 Überblick und Grundlagen 5.2 Branch & Bound-Verfahren 5.3 Heuristische Verfahren

Produktion und Logistik

PW / OR WS 06/07

0-1

Produktionswirtschaft und Operations Research Dr. Rainer Kleber Fakultät für Wirtschaftswissenschaft Lehrstuhl für Produktion und Logistik [email protected] Sprechstunde: Donnerstag 10.00-12.00 Uhr in G22-E016 Kurzbeschreibung: Die Vorlesung vermittelt einen Überblick über den Gegenstand der industriellen Produktionswirtschaft und gibt eine Übersicht über Grundlagen der Produktionstheorie und wesentliche Aufgaben des Produktionsmanagements. Im Rahmen der Behandlung von Planungsinstrumenten zur Lösung solcher Managementaufgaben wird auf wichtige Verfahren des Operations Research eingegangen. Hierbei werden sowohl die Modellierungstechnik als auch grundlegende Optimierungsmethoden des Operations Research vermittelt.

Produktion und Logistik

PW / OR WS 06/07

Gliederung 1 Einführung 1.1

Einführung in die Produktionswirtschaft (PW)

1.2

Einführung in Operations Research (OR)

2 Produktionstheorie 2.1

Aufgaben der Produktionstheorie

2.2

Produktionstheorie auf Objektebene

2.3

Produktionstheorie auf Ergebnisebene

2.4

Produktionstheorie auf Erfolgsebene

3 Lineare Optimierung 3.1

Grundlagen der Linearen Optimierung

3.2

Der Simplex-Algorithmus

3.3

Dualität

3.4

Sensitivitätsanalyse

3.5

Lineare Optimierungsproblem mit spezieller Struktur

3.6

Lösung von linearen Optimierungsproblemen in der Praxis

0-2

Produktion und Logistik

PW / OR WS 06/07

0-3

4 Produktionsmanagement 4.1

Aufgaben des Produktionsmanagements

4.2

Nachfrageprognosen

4.3

Produktionsprogrammplanung

4.4

Materialbedarfsplanung

4.5

Losgrößenplanung

5 Ganzzahlige Optimierung 5.1

Grundlagen der Ganzzahligen Optimierung

5.2

Branch & Bound-Verfahren

5.3

Heuristische Lösungsverfahren

6 Weitere Anwendungen und Gebiete des Operations Research

Literaturempfehlungen [1] Domschke und Drexl, Einführung in Operations Research, 6. Auflage, Springer, 2005 [2*] Dyckhoff, Produktionstheorie, 5. Auflage, Springer, 2006 [3*] Günther und Tempelmeier, Produktion und Logistik, 6. Auflage, Springer, 2005 [4] Hillier und Lieberman, Introduction to Operations Research, 8. Auflage, McGraw, 2005 [5] Thonemann, Operations Management, Pearson, 2005 (* alternativ auch vorherige Auflage bzw. bei Dyckhoff Grundzüge der Produktionswirtschaft, 4. Auflage)

Produktion und Logistik

PW / OR WS 06/07

0-4

Literaturhinweise Gliederungspunkt 1.1 PW-Einführung 1.2 OR-Einführung

Textstellen (2) 1-9 (1) 1-12

Vorherige Auflage (2*) 1-8

2.1 2.2 2.3 2.4

Aufgaben der PT PT auf Objektebene PT auf Ergebnisebene PT auf Erfolgsebene

(2) (2) (2) (2)

9-12 19-106 119-155, 162-176 189-200, 212-252

(2*) (2*) (2*) (2*)

9-12 20-106 119-155, 164-176 189-200, 212-252

3.1 3.2 3.3 3.4 3.5

Grundlagen der Linearen Optimierung Simplex-Algorithmus Dualität Sensitivitätsanalyse Allg. und spezielle LOP‘s

(1) (1) (1) (1) (1)

12-20 20-27, 34-35 35-40 44-49 74-77, 83-86

4.1 4.2 4.3 4.4 4.5

Aufgaben des PM Nachfrageprognosen Produktionsprogrammplanung Materialbedarfsplanung Losgrößenplanung

(2) (3) (3) (2) (2)

367-372, (3) 1-10 142-151, (4) 35-75 139-142, 151-1162 270-280, 340-346 314-320, (3) 192-208

(2*) (3*) (3*) (2*) (2*)

367-372, (3*) 1-10 138-147 135-138, 147-155 270-280, 340-346 314-319, (3*) 187-200

(1) (1) (1)

110-117 121-126 117-121

5.1 Überblick und Grundlagen 5.2 Branch & Bound-Verfahren 5.3 Heuristische Verfahren

Produktion und Logistik

PW / OR WS 06/07

1 Einführung

1-1

Produktion und Logistik

PW / OR WS 06/07

1-2

1.1 Einführung in die Produktionswirtschaft (PW) 1.1.1 Grundbegriffe Produktionswirtschaftslehre betrachtet Phänomene der Produktion (insbes. in Unternehmungen) aus wirtschaftlicher Perspektive. Produktion ist die zielgerichtete Herstellung von Produkten unter Einsatz von sog. Produktionsfaktoren. (= Kombination von Produktionsfaktoren und Transformation in Produkte, s. BWL A) Produkte sind insbes. Sachgüter und Dienstleistungen. Produktionsfaktoren sind insbes. Arbeitsleistungen, Betriebsmittel, Werkstoffe und Informationen. Die wirtschaftliche Perspektive bezieht sich auf den Prozess der (Netto-) Wertschöpfung im Transformationsprozess. Der Produktionsvorgang ist allg. darstellbar als wertschöpfendes Input-Output-System:

Input

Objekte

Qualitative Transformation

Objekte

Output

Produktion und Logistik

PW / OR WS 06/07

1.1.2 Grundzusammenhänge Produktion zum Zweck der Wertschöpfung ist die Kernfunktion jeder Unternehmung. Charakterisierung von Produktion nach → Objekten

→ Transformation

• • • •

Sachen Dienste Rechte Informationen

• Primärer Sektor • Sekundärer Sektor • Tertiärer Sektor

• einstufig • mehrstufig

• divergierend • konvergierend

1-3

Produktion und Logistik

PW / OR WS 06/07

1-4

Produktionssysteme sind geordnete Zusammenfassungen von Input-Output-Systemen mit Innenbeziehungen (z.B. Materialflüsse) und Außenbeziehungen (z.B. Umweltbelastungen).

Das Produktionssystem in seiner Umwelt [Quelle : Dyckhoff : 3. Aufl., S. 5]

Produktion und Logistik

PW / OR WS 06/07

Hauptbetrachtungsgegenstand der PW :

Industriebetriebe

Systematik der Betriebe im gesamtwirtschaftlichen Leistungszusammenhang [Quelle: Zahn/Schmid : Produktionswirtschaft I, S. 57

1-5

Produktion und Logistik

PW / OR WS 06/07

1-6

Abgrenzungen von Produktion und Produktionssystemen:

• Produktion = Wertschöpfung • Konsumtion = Wertvernichtung

• Produktion - VWL • Produktion - BWL

Wirtschaftseinheiten und ihre Umwelten [Quelle: Dyckhoff, 3. Aufl., S. 2]

• Produktion :

qualitative Transformation

• Logistik

raum-zeitliche Transformation

:

• Beschaffung /Absatz

:

Markt-Transaktionen

Produktion und Logistik

PW / OR WS 06/07

1-7

1.1.3 Teilaspekte der Produktionswirtschaftslehre PW-Lehre befasst sich mit den (Technik-orientierten) Ausführungssystemen und den (Management-orientierten) Führungssystemen der Produktion.

Produktionsfaktoren

Absatz

Güterstrom

Produkte

Unternehmensführung Plang. Kontr. Organisation

Auszahlung

Geldstrom

Absatzmarkt

Beschaffungsmarkt

Beschaffung Produktion

Einzahlung

Finanzierung

Finanzmarkt

Im Ausführungssystem läuft der Wertschöpfungsprozess als physischer Transformationsprozess der Produktion ab. Im Führungssystem spielt sich der informationsverarbeitende Managementprozess zur zielkonformen Gestaltung und Lenkung des Transformationsprozesses ab.

Produktion und Logistik

PW / OR WS 06/07

1-8

Hauptgebiete der PW-Lehre: PW-Lehre Produktionstheorie

Produktionsmanagement-Lehre

• Hauptbezug: Ausführungssystem

• Hauptbezug: Führungssystem

• Beschreibungs- und Erklärungsmodelle für Transformationsprozesse

• Entscheidungsmodelle für Managementprozesse

Produktionstheorie (= Theorie der betrieblichen Wertschöpfung) untersucht die allgemeinen Zusammenhänge und Gesetzmäßigkeiten in Bezug auf Transformationsprozesse in Produktionssystemen. Produktionsmanagement befasst sich mit der Organisation von Produktionssystemen und der Planung und Kontrolle von Produktionsprozessen zur Erreichung betrieblicher Ziele. • Planung : zielgerichtete Festlegung zukünftigen Handelns (zur Vorbereitung und Auswahl von Entscheidungen) • Kontrolle: Feststellen und Korrigieren von Planungsfehlern und Mängeln bei der Umsetzung von Entscheidungen

Produktion und Logistik

PW / OR WS 06/07

1-9

1.2 Einführung in Operations Research (OR) 1.2.1 Grundbegriffe im OR Operations Research (OR) dient der Entscheidungsvorbereitung im Rahmen komplexer (ökonomischer) Planungsprobleme auf Basis quantifizierbarer Informationen und unter Zuhilfenahme mathematisch-statistischer Verfahren. Anwendungsbedingungen für OR • • • •

Hinreichende Quantifizierbarkeit aller wesentlichen Problembestandteile Möglichkeit zur Gewinnung aller relevanten Informationen Hinreichende Komplexität des Entscheidungsproblems Beschränkter Umfang des Entscheidungsproblems

→ Mathematische Modellierbarkeit (als Entscheidungsmodell) → Rechnerische Lösbarkeit (durch Algorithmen)

Produktion und Logistik

PW / OR WS 06/07

1-10

Prozess-Phasen der Anwendung von OR:

(1)

Problemanalyse

Modellbildung

Implementierung

Lösungsfindung

Problemanalyse: • Erkennen und Abgrenzung des Problems • Analyse der Problembestandteile (Handlungsmöglichkeiten, Planungsziel, Rahmenbedingungen)

(2)

Modellbildung: • Umsetzung : Spezifisches Problem → Mathematisches Modell ƒ Handlungsmöglichkeiten → Entscheidungsvariable ƒ Ziel → Zielgröße und Zielfunktion ƒ Rahmenbedingungen → Restriktionen • Datengewinnung (Quantifizierung: einwertige Daten, Wahrscheinlichkeitsverteilungen)

Produktion und Logistik

(3)

PW / OR WS 06/07

Lösungsfindung • Anwendung von OR-Rechenverfahren (OR-Algorithmen, OR-Verfahren) • Einsatz von DV-Hilfsmitteln (z.B. Standardsoftware)

(4)

Implementierung • Validierung der Modellergebnisse • Interpretation bzgl. Realproblem • Anpassung der Entscheidungsvorschläge und Umsetzung

1-11

Produktion und Logistik

PW / OR WS 06/07

1-12

1.2.2 OR-Verfahren Modelle im Rahmen von OR-Anwendungen sind im wesentlichen Optimierungsmodelle (zur Maximierung oder Minimierung einer Zielgröße unter verschiedenen Nebenbedingungen). Allgemeines Optimierungsmodel l Entscheidungsvariablen: x1 , x2 , ..., xn

Z = F ( x1 , x2 , ..., xn )

Maximiere

unter den Nebenbedingungen ⎧≥ ⎫ ⎪ ⎪ gi ( x1 , x2 , ..., xn ) ⎨= ⎬ 0 ⎪≤ ⎪ ⎩ ⎭

und x1 , x2 , ..., xn

für

i = 1, 2, ..., m

reellwertig oder ganzzahlig

Produktion und Logistik

PW / OR WS 06/07

1-13

Für verschiedene Modelltypen stehen verschiedene OR-Verfahren zur Lösung zur Verfügung:

Ganzzahlige Optimierung

Lineare Optimierung

Graphentheorie

Nichtlineare Optimierung

Dynamische Optimierung

Netzplantechnik

Simulation

Warteschlangentheorie

Produktion und Logistik

PW / OR WS 06/07

1.2.3 OR-Anwendungsgebiete

• Produktionswirtschaft • Logistik • Dienstleistungsmanagement • Marketing • Finanzwirtschaft • Banken/Versicherungen • etc.

• Produktionsplanungsproblem • Verschnittproblem • Transport- und Versorgungsproblem • Auslieferung von Gütern • Kürzeste Wege in Verkehrsnetzen • Personaleinsatzplanung • Warteschlangenproblem • Flugtarifplanung • und viele, viele mehr

1-14

Produktion und Logistik

PW / OR WS 06/07

2 Produktionstheorie

2-1

Produktion und Logistik

PW / OR WS 06/07

2-2

2.1 Aufgaben der Produktionstheorie Produktionstheorie untersucht allgemeine Zusammenhänge und Gesetzmäßigkeiten in Bezug auf Transformationsprozesse in Produktionssystemen (= Wertschöpfungsprozesse) Methodik Abstraktion von realen Produktionsprozessen und Modellierung allg. Produktionszusammenhänge durch • Beschreibungsmodelle Produktionssystemen

zur

Darstellung

von

Elementen

und

Beziehungen

in

und • Erklärungsmodelle zur Wiedergabe von Abhängigkeiten zwischen Systemelementen und von Wirkungszusammenhängen in Produktionssystemen

Produktion und Logistik

PW / OR WS 06/07

Eine systemorientierte Sichtweise ermöglicht • die schrittweise Zerlegung komplexer Systemstrukturen in einfache Bestandteile (→ Systemanalyse) bzw. • die sukzessive Erzeugung derartiger Strukturen durch Zusammenfügen einfacher Bausteine (→ Systemsynthese)

Abbildung 1 : Gegenstand der Theorie betrieblicher Wertschöpfung [Quelle : Dyckhoff : Grundzüge der Produktionswirtschaft, 3. Aufl., S. 8]

2-3

Produktion und Logistik

PW / OR WS 06/07

2-4

Betrachtungsebenen der Produktionstheorie Die Produktionstheorie untersucht Transformationsprozesse auf 3 Ebenen, die sich durch zunehmende Information über die Wahrnehmung und Präferenzen des Systembetrachters unterscheiden lassen. [1]

Objektebene

Basis:

nur Unterscheidung zwischen relevanten und nicht-relevanten Objekten (Inputs bzw. Outputs) des Transformationsprozesses

Grundbegriffe: Objekte, Aktivität, Technologie, Produktionsmöglichkeiten [2]

Ergebnisebene

Basis:

auch Unterscheidung zwischen erwünschten und nicht-erwünschten Objekten des Transformationsprozesses

Grundbegriffe: realer Aufwand/Ertrag (mehrdimensional), Effizienz, Produktionsfunktion [3]

Erfolgsebene

Basis:

quantitative Bewertung aller Objekte in Höhe ihres Wertschöpfungsbeitrags möglich

Grundbegriffe: Kosten/Erlöse/Erfolg (eindimensional), Erfolgsfunktion

Produktion und Logistik

PW / OR WS 06/07

2.2 Produktionstheorie auf Objektebene 2.2.1 Input-Output-Beziehungen 2.2.1.1 Klassifikation von Objekten • nach Bedeutung aus Sicht des Systembetrachters ƒ relevante Objekte ƒ nicht-relevante Objekte • nach körperlicher Erscheinungsform ƒ materielle Objekte (Stoffe, Energie) ƒ immaterielle Objekte (Dienste, Rechte, Informationen)

2-5

Produktion und Logistik

PW / OR WS 06/07

2-6

Objekte • nach Stellung im Transformationsprozess (Input/Output) ƒ Einsatzobjekte ƒ Ausbringungsobjekte Einsatzobjekte Ausbringungs• nach Stellung zum Betriebszweck objekte (Erzeugung bzw. Reduktion von Objekten) Einsatz(Haupt-) (Haupt-) Nebenƒ Hauptprodukte bzw. produkte faktoren Redukte Produkte Nebenprodukte auf Outputseite Dispositiver ƒ Redukte bzw. Einsatzfaktoren Faktor auf Inputseite • nach Faktortyp auf Inputseite ƒ Dispositiver Faktor (Managementtätigkeit) ƒ Elementarfaktoren (ausführende Tätigkeit, Betriebsmittel, Werkstoffe) ¾ Potentialfaktoren (Arbeitskräfte, Maschinen, Lizenzen, etc.) ¾ Repetierfaktoren (Roh-, Hilfs- und Betriebsstoffe, Zwischenprodukte) ƒ Zusatzfaktoren (externe Dienste, Umweltnutzung, etc.)

Elementarfaktoren Potentialfaktoren Repetierfaktoren Zusatzfaktoren

Produktion und Logistik

PW / OR WS 06/07

2-7

Objekte produktionstheoretischer Modelle sind Gegenstände im Rahmen von Transformationsprozessen, die qualitativ unterschiedlich und bzgl. Einsatz und Ausbringung quantitativ messbar sind. Qualitativ gleiche bzw. ähnliche Objekte können zu Objektarten zusammengefasst werden. Zum Zweck der Modellbildung werden Objektarten geeignet nummeriert: • allg. Objektindex :

k = 1, 2, ..., κ

( κ : Gesamtzahl der Objektarten)

spezielle Indexverwendung für reine Input- bzw. Outputobjekte: • für Inputs:

i = 1, 2, ..., m

( m : Gesamtzahl der Input-Outputarten)

• für Outputs:

j = m + 1, m + 2, ..., m + n

( n : Gesamtzahl der Output-Objektarten)

Beispiele: • Lederwarenherstellung • Müllverbrennung

(Erzeugungssystem) : (Reduktionssystem) :

Fa. LederLotte Fa. MüllMax

Produktion und Logistik

PW / OR WS 06/07

2-8

• Beispiel Erzeugungsbetrieb : LederLotte

• Beispiel Reduktionsbetrieb : MüllMax

Objektarten

Objektarten

Bei LederLotte sind im Rahmen der mittelfristigen Planung zweier neuer Kollektionen von Schuhen und Taschen beispielsweise nur die folgenden sechs Objektarten von Interesse:

Um die materiellen Objekte bei MüllMax zu erfassen, werden in einem ersten Schritt folgende neun Objekte definiert und in den angegebenen Einheiten gemessen:

(1) (2) (3) (4) (5) (6)

Arbeit [min] Nähmaschine [min] Leder [m²] Schuhe [Anzahl Paar] Taschen [Stückzahl] Lederreste [g].

(1) (2) (3) (4) (5) (6) (7) (8) (9)

Müll [kg] Schrott [kg] Schlacke [kg] Rohwasser [l] Abwasser [l] Luft [m³] Abgase [m³] Strom [kWh] Abwärme [kWh]

Produktion und Logistik

PW / OR WS 06/07

2-9

2.2.1.2 Produktions-Aktivitäten Eine Produktions-Aktivität (oder kurz: Aktivität) ist eine zielgerichtete wertschöpfende Transformation von Produktionsinput in Produktionsoutput während einer Produktionsperiode. x1 y1 Transformation y2 x2 mit # # Prozessparametern yκ xκ (λ, σ) Produktionsperiode

Zeit

Innenbezüge einer Aktivität : λ : Disponible Steuergröße beim Betreiben des Transformationsprozesses σ : Nicht-beeinflussbare Umweltparameter mit Wirkung auf den Transformationsprozess Außenbezüge einer Aktivität: xk : Bruttomenge der Objektart k, die für den Transformationsprozess von außen zur Verfügung gestellt wird (mit xk ≥ 0 ) yk : Bruttomenge der Objektart k, die im Rahmen des Transformationsprozesses nach außen abgegeben wird (mit yk ≥ 0 )

Produktion und Logistik

PW / OR WS 06/07

Beschreibungsformen von Input/Output-Mengen • Bruttomengen • Nettomengen

: :

(k = 1, ..., κ) (k = 1, ..., κ)

xk und yk zk = yk − xk

mit zk : Netto-Ausbringungsmenge der Objektart k → ohne Bestandsveränderungen und ohne Berücksichtigung von Handelswaren gilt: yk = z k

und

xk = − zk

für k = 1, ..., κ

2-10

Produktion und Logistik

PW / OR WS 06/07

2-11

Darstellung von Aktivitäten (1)

Vektor-Darstellung

(brutto bzw. netto) :

⎡ x1 ⎤ ⎢x ⎥ x = x = ⎢ 2⎥ ⎢#⎥ ⎢ ⎥ ⎣⎢ xκ ⎦⎥

⎡ y1 ⎤ ⎢y ⎥ y = y = ⎢ 2⎥ ⎢# ⎥ ⎢ ⎥ ⎣⎢ yκ ⎦⎥

und

bzw.

⎡ z1 ⎤ ⎢z ⎥ z = z = ⎢ 2⎥ ⎢#⎥ ⎢ ⎥ ⎣⎢ zκ ⎦⎥

Kompakteste Darstellungsweise durch Vektor z : κ Aktivität = Punkt im κ -dimensionalen, reellwertigen Zahlenraum \ (2)

Input-Output-Tabelle (vollständig bzw. vereinfacht)

(3)

Input-Output-Graph

(4)

Praxisdarstellungen: Stücklisten, Rezepturen, Arbeitspläne, Mengenflussbilder, Produktbilanzen, etc

Produktion und Logistik

PW / OR WS 06/07

2-12

• Beispiel MüllMax Vektor-Darstellung:

Brutto

Netto

Input-Output-Tabelle

Vollständig

Vereinfacht

Produktion und Logistik

Input-Output-Graph (I/O-Graph)

PW / OR WS 06/07

2-13

Produktion und Logistik

• Beispiel LederLotte Vereinfachte Input-Output-Tabelle

Input-Output-Graph (I/O-Graph)

PW / OR WS 06/07

2-14

Produktion und Logistik

PW / OR WS 06/07

2-15

2.2.1.3 Technologie und Technologieeigenschaften Eine Technologiemenge T (oder kurz: Technologie, bei Dyckhoff: Technik) beschreibt die Menge aller Aktivitäten, die in einem Produktionssystem im Prinzip technisch möglich sind.

{

}

Formal:

T = z ∈ \κ z ist eine prinzipiell mögliche Aktivität

Beispiel:

LederLotte, Beschränkung auf Schuhherstellung

⎧ ⎡ 0 ⎤ ⎡ −50 ⎤ ⎡ −100 ⎤ ⎡ −150 ⎤ ⎫ ⎧ ⎪⎢ ⎥ ⎢ ⎪ ⎪ ⎥ ⎢ ⎥ ⎢ ⎥ ⎪ ⎢ 0 ⎥ ⎢ −40 ⎥ ⎢ −80 ⎥ ⎢ −120 ⎥ ⎪ ⎪ ⎪⎪ ⎢ 0 ⎥ ⎢ −0,15⎥ ⎢ −0,30 ⎥ ⎢ −0, 45⎥ ⎪⎪ ⎪⎪ 6 T = ⎨⎢ ⎥ , ⎢ , , , ... ⎬ = ⎨z ∈ \ z = λ ⋅ ⎥ ⎢ ⎥ ⎢ ⎥ ⎪⎢0⎥ ⎢ 1 ⎥ ⎢ 2 ⎥ ⎢ 3 ⎥ ⎪ ⎪ ⎪⎢0⎥ ⎢ 0 ⎥ ⎢ 0 ⎥ ⎢ 0 ⎥ ⎪ ⎪ ⎪⎢ ⎥ ⎢ ⎪ ⎪ ⎥ ⎢ ⎥ ⎢ ⎥ ⎪⎭ ⎩⎪ ⎩⎪ ⎣ 0 ⎦ ⎣ 30 ⎦ ⎣ 60 ⎦ ⎣ 90 ⎦

⎫ ⎡ −50 ⎤ ⎪ ⎢ −40 ⎥ ⎪ ⎥ ⎢ ⎪⎪ ⎢ −0,15⎥ mit λ ` ∈ ⎢ ⎥ 0⎬ ⎪ ⎢ 1 ⎥ ⎪ ⎢ 0 ⎥ ⎪ ⎢ ⎥ ⎣ 30 ⎦ ⎭⎪

Zur Technologie gehören i. d. R. auch Aktivitäten mit Faktorverschwendung, wie z. B. ⎡ −100 ⎤ ⎢ −40 ⎥ ⎢ ⎥ ⎢ −0,15⎥ ⎢ ⎥ 1 ⎢ ⎥ ⎢ 0 ⎥ ⎢ ⎥ 30 ⎣ ⎦

oder

⎡ −50 ⎤ ⎢ −40 ⎥ ⎢ ⎥ ⎢ 0 ⎥ ⎢ ⎥ 0 ⎢ ⎥ ⎢ 0 ⎥ ⎢ ⎥ 0 ⎣ ⎦

Produktion und Logistik

PW / OR WS 06/07

2-16

Technologieeigenschaften beschreiben idealtypische Merkmale, durch die sich allgemeine Technologien auf bestimmte Technologieformen einschränken lassen. [1]

Größenproportionalität

beschreibt eine Eigenschaft, die sich auf eine Skalenvariation (Niveauvariation) von Produktionsaktivitäten bezieht. Eine größenproportionale (oder auch: linear-homogene) Technologie liegt vor, wenn für jede beliebige Aktivität z gilt:

z∈T ⇒ λ ⋅ z ∈ T Voraussetzungen : Beispiel:

mit Niveaufaktor

Beliebige Teilbarkeit aller Objekte! Keine Lerneffekte bei Niveauerhöhung!

λ≥0

Produktion und Logistik

[2]

PW / OR WS 06/07

2-17

Additivität

beschreibt eine Eigenschaft, die sich auf die gemeinsame Durchführung von Aktivitäten bezieht. Eine additive Technologie liegt vor, wenn für beliebige Aktivitäten z1 und z² gilt:

z1 ∈ T und z 2 ∈ T

⇒

z1 + z 2 ∈ T

Voraussetzung : Keine Synergie- und Störeffekte zwischen Aktivitäten! Beispiel:

Produktion und Logistik

[3]

PW / OR WS 06/07

2-18

Linearität

beschreibt eine Eigenschaft, die sich auf Linear-Kombinationen von Aktivitäten bezieht. Eine lineare Technologie liegt vor, wenn gilt:

z1 ∈ T und z 2 ∈ T

⇒

λ1 ⋅ z1 + λ2 ⋅ z 2 ∈ T

mit λ1 ≥ 0 , λ2 ≥ 0

Voraussetzung: Eine Technologie ist linear, wenn sie additiv und größenproportional ist! Beispiel:

T

Produktion und Logistik

[4]

PW / OR WS 06/07

2-19

Konvexität

beschreibt eine Eigenschaft, die sich auf Konvex-Kombinationen von Aktivitäten bezieht. Eine konvexe Technologie liegt vor, wenn gilt:

z1 ∈ T und z 2 ∈ T

⇒

λ1 ⋅ z1 + λ2 ⋅ z 2 ∈ T

mit λ1 ≥ 0 , λ2 ≥ 0 und λ1 + λ2 = 1

Konsequenz: Die lineare Technologie ist ein Spezialfall konvexer Technologie! Beispiel für eine konvexe, jedoch nicht lineare Technologie (mit zwei Beispielaktivitäten z1 und z2): z1

T

z2

Hinweis: Sowohl bei linearer als auch bei konvexer Technologie ist die Möglichkeit der Verschwendung zugelassen.

Produktion und Logistik

PW / OR WS 06/07

2-20

Graphische Darstellung von Technologien Beispiel Cobb/Douglas-Technologie Τ = {( z1 , z2 , z3 ) ∈ \ 3 | z1 ≤ 0, z2 ≤ 0, 0 ≤ z3 ≤ 5( − z1 )1,5 ( − z 2 ) 0,5 } (1)

Vollständiges Technologie-Diagramm (siehe auch oben)

Dreidimensionale Technik (Ertragsgebirge) [Quelle : Dyckhoff : Grundzüge der Produktionswirtschaft, 3. Aufl., S. 56]

Produktion und Logistik

(2)

PW / OR WS 06/07

2-21

Partielles Faktor/Produkt-Diagramm

Partielles Faktor/Produkt-Diagramm mit zunehmenden Grenzerträgen [Quelle : Dyckhoff, 3. Aufl., S. 68]

Partielles Faktor/Produkt-Diagramm mit abnehmenden Grenzerträgen [Quelle : Dyckhoff, 3. Aufl., S. 67]

Produktion und Logistik

(3)

PW / OR WS 06/07

Faktordiagramm

Faktordiagramm für landwirtschaftliche Technik [Quelle : Dyckhoff, 3. Aufl., S. 69]

(4)

Produktdiagramm

2-22

Produktion und Logistik

PW / OR WS 06/07

2-23

2.2.1.4 Produktionsmöglichkeiten Größenproportionale, additive und lineare Technologien beschreiben Produktionssysteme mit einer unbeschränkten Menge von Aktivitäten. In der Realität bestehen Beschränkungen für Produktionsaktivitäten, insbes. in Form von Mindest- und Höchstmengen für Faktoreinsatz und Erzeugnisausbringung (z.B. durch Marktengpässe und vertragliche Verpflichtungen). Das Restriktionsfeld R ∈ \κ beschreibt die Menge der aufgrund solcher externen Beschränkungen zulässigen Aktivitäten. Häufig wird das Restriktionsfeld R durch absolute Schranken gebildet: R = z ∈ \κ z ≤ z ≤ z , d.h. z k ≤ zk ≤ z k für k = 1,2,..., κ z2 Beispiel: 4

{

}

3

R

2 1 -8

-7

-6

-5

-4

-3

-2

-1

z1

Produktion und Logistik

PW / OR WS 06/07

2-24

In der Praxis finden sich auch relative Schranken der Form:

zk ≤ α ⋅ z j für bestimmte k und j Die Menge der effektiven Produktionsmöglichkeiten wird durch das Produktionsfeld Z ∈ IR κ beschrieben, für das gilt:

Z = T∩R

Beispiel:

T

z2 4 3

Z

2

R

1 -8

-7

-6

-5

-4

-3

-2

-1

z1

Produktion und Logistik

PW / OR WS 06/07

2-25

Beispiel LederLotte : Produktionsfeld Das Beispiel des Unternehmens "LederLotte" kann dazu dienen, die Begriffe Technologie und Produktionsmenge zu illustrieren. Die Technologie sei wie folgt bestimmt: ⎧ ⎛ −50 ⎞ ⎛ −50 ⎞ ⎪ ⎜ ⎟ ⎜ ⎟ ⎪ ⎜ −40 ⎟ ⎜ −15 ⎟ ⎪⎪ ⎜ −0,15 ⎟ 2 ⎜ −0, 4 ⎟ 1 2 T = ⎨z ∈ \ 6 z = λ1 ⋅ ⎜ ⎟ + λ ⋅⎜ ⎟ mit λ ≥ 0, λ ≥ 0 ⎜ 1 ⎟ ⎜ 0 ⎟ ⎪ ⎜ 0 ⎟ ⎜ 1 ⎟ ⎪ ⎜⎜ ⎟⎟ ⎜⎜ ⎟⎟ ⎪ ⎪⎩ ⎝ 30 ⎠ ⎝ 25 ⎠

⎫ ⎪ ⎪ ⎪⎪ ⎬ ⎪ ⎪ ⎪ ⎪⎭

Dabei stellen die beiden Vektoren jeweils den Input/Output-Vektor für die Erstellung eines Paar Schuhe bzw. einer Tasche dar. In der betrachteten Periode stehen der Unternehmung maximal 5000 Arbeitsminuten zur Verfügung. Die Nähmaschine kann bis zu 3000 Minuten genutzt und maximal 30 m2 Leder können verarbeitet werden. Gleichzeitig bestehen Lieferverpflichtungen für mind. 50 Paar Schuhe und 10 Taschen, die unbedingt eingehalten werden sollen. Die Restriktionsmenge R ist also durch folgende absolute Schranken definiert: ⎛ −5000 ⎞ ⎜ ⎟ ⎜ −3000 ⎟ ⎜ −30 ⎟ z =⎜ ⎟ 50 ⎟ ⎜ ⎜ 10 ⎟ ⎜⎜ ⎟ 0 ⎟⎠ ⎝

⎛ 0⎞ ⎜ ⎟ ⎜ 0⎟ ⎜ 0⎟ z =⎜ ⎟ ⎜ +∞ ⎟ ⎜ +∞ ⎟ ⎜⎜ ⎟⎟ ⎝ +∞ ⎠

Produktion und Logistik

PW / OR WS 06/07

2-26

Daraus resultiert folgendes Produktionsfeld: ⎧ ⎫ ⎛ −50 ⎞ ⎛ −50 ⎞ ⎛ -5000 ⎞ ⎪ ⎪ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎪ ⎪ ⎜ −40 ⎟ ⎜ −15 ⎟ ⎜ -3000 ⎟ ⎪⎪ ⎪⎪ ⎜ −0,15 ⎟ 2 ⎜ −0, 4 ⎟ ⎜ -30 ⎟ 1 2 + λ ⋅ ≥ λ λ ≥ Z = ⎨z ∈ \ 6 z = λ1 ⋅ ⎜ ; , 0 ⎟ ⎜ ⎟ ⎜ ⎟ ⎬ ⎜ 1 ⎟ ⎜ 0 ⎟ ⎜ 50 ⎟ ⎪ ⎪ ⎜ 0 ⎟ ⎜ 1 ⎟ ⎜ 10 ⎟ ⎪ ⎪ ⎜⎜ ⎟⎟ ⎜⎜ ⎟⎟ ⎜⎜ ⎟⎟ ⎪ ⎪ ⎪⎩ ⎪⎭ ⎝ 30 ⎠ ⎝ 25 ⎠ ⎝ 0 ⎠

Produktionsfeld im Produktdiagramm:

z5=y5

(2)

(4)

(3)

Z

(1) (5)

(6)

z4=y4

Produktion und Logistik

PW / OR WS 06/07

2-27

2.2.2 Lineare Technologie Die lineare Technologie (LT) ist die für den industriellen Anwendungsbereich wichtigste Technologieform. Die LT beinhaltet allerdings aus Anwendersicht auch problematische Eigenschaften: ¾ ¾ ¾ ¾ ¾

Unbeschränktheit keine Behinderungseffekte keine Synergieeffekte keine Lerneffekte beliebige Objektteilbarkeit

: : : : :

durch R zu berücksichtigen durch R zu berücksichtigen kurzfristig akzeptabel kurzfristig akzeptabel bei Stückobjekten problematisch, u. U. als Approximation akzeptabel, sonst Beschränkung auf Additive Technologie

Allgemein gilt bei Linearität einer Technologie für p beliebige Aktivitäten:

Wenn

( z ,..., z ) ∈ T 1

p

und λ ,..., λ ≥ 0, 1

p

p

dann gilt : z = ∑ λ r ⋅ z r ∈ T r =1

Produktion und Logistik

PW / OR WS 06/07

2-28

2.2.2.1 Endlich generierbare lineare Technologien Im Rahmen einer LT (entsprechendes gilt für eine Additive Technologie) liegt eine endlich generierbare Technologie vor, wenn sich die gesamte Technologiemenge T durch Linearkombinationen einer endlichen Anzahl von Aktivitäten darstellen lässt. Formal :

Es existieren π Aktivitäten (mit π < ∞ ), so dass gilt: π ⎧ ⎫ T = ⎨ z = ∑ λρ ⋅ z ρ λρ ≥ 0 für ρ = 1,..., π⎬ ρ =1 ⎩ ⎭

Die Menge der generierenden Aktivitäten z1, z2,..., zπ bildet insgesamt die so genannte ˆ . Technologiematrix M Es existieren auch Produktionssysteme, die sich nicht durch eine endliche Zahl von Grundaktivitäten (oder elementaren Prozessen) beschreiben lassen. Derartige Technologien, die als nicht endlich generierbar bezeichnet werden, treten typischerweise dann auf, wenn disponible Prozessparameter zur Steuerung der Transformationsprozesse kontinuierlich variiert werden können. Beispiele: • Gutenberg-Technologien mit Prozessparameter : kontinuierlich variierbare Einsatzintensität von Potentialfaktoren mit Wirkung auf Verbrauchskoeffizienten für Repetierfaktoren • Technologien für Mischungsprozesse mit Prozessparameter : kontinuierlich variierbare Materialanteile von zu mischenden Stoffen Approximationsmöglichkeit: Nicht endlich generierbare Technologien können in der Regel durch Basis Technologien mit einer (hinreichend großen) endlichen Anzahl von Grundaktivitäten gut approximiert werden.

Produktion und Logistik

PW / OR WS 06/07

2-29

ˆ heißt Basis M der Technologie T, wenn sie keine überflüssigen Eine Technologiematrix M Aktivitäten enthält. Überflüssig sind solche Aktivitäten, die sich durch Linearkombinationen aus anderen Aktivitäten bilden lassen. Beispiel :

z2 4

T z3

ˆ = ⎡ −2 −3 M ⎢ 1 3 ⎣

z2

3

−5 ⎤ ⎡ −2 −3⎤ = M und ⎢ 1 3⎥ 3⎥⎦ ⎣ ⎦

2 1

z1 Konsequenz:

-8

-7

-6

-5

-4

-3

-2

-1

Endlich generierbare LT’n lassen sich allein durch die Angabe ihrer Basis (und damit in äußerst kompakter Weise) vollständig beschreiben! Endlich generierbare LT’n bilden (geometrisch) sog. konvexe polyedrische Kegel, jede Aktivität der Basis M erzeugt eine Kante des Kegels.

z1

Produktion und Logistik

PW / OR WS 06/07

2-30

Normierungsproblematik Die Aktivitäten [z1, ..., zπ] in der Basis M einer LT sind wegen der Eigenschaft der Größenproportionalität nicht eindeutig definiert.

Zur Normierung bezieht man diese Aktivitäten auf ein spezifiziertes Aktivitätsniveau, z.B. den Verbrauch einer bestimmten Inputeinheit oder die Produktion einer bestimmten Outputeinheit. Häufig wird als Bezugspunkt die einmalige Durchführung einer Aktivität (z.B. in der diskreten Fertigungsindustrie) oder die Durchführung der Aktivität für die Dauer 1 Zeiteinheit (z.B. in der Prozessindustrie) gewählt. Derartig normierte Aktivitäten werden Grundaktivitäten zρ (ρ=1,...,π) genannt. Das Skalenniveau jeder Grundaktivität beträgt: λρ = 1 ! Konsequenzen: Durch Änderung des Skalenniveaus lässt sich bei LT’n aus jeder Grundaktivität zρ ein elementarer Produktionsprozess Pρ generieren:

{

Pρ = z

}

z = λ ⋅ zρ , λ ≥ 0

Die gesamte Technologiemenge einer LT setzt sich zusammen aus elementaren Prozessen (reine Prozesse) und deren Linearkombinationen (gemischte Prozesse) bzw. ist bei gegebener Basis M durch Variation des Skalenniveaus der Grundaktivitäten generierbar:

⎧ ⎡ λ 1 ⎤ ⎡0⎤ ⎫ ⎪ ⎪ T = ⎨ z | z = M ⋅ λ und λ = ⎢ # ⎥ ≥ ⎢ # ⎥ ⎬ ⎢ π⎥ ⎢ ⎥ ⎪ ⎪ ⎣⎢λ ⎦⎥ ⎣0 ⎦ ⎭ ⎩

Produktion und Logistik

PW / OR WS 06/07

2-31

Beispiel LederLotte : Technologiematrix Das Beispiel von LederLotte kann dazu dienen, die Begriffe Technologie und Produktionsmenge zu illustrieren. Die Technologie sei wie folgt bestimmt:

Die oben definierte lineare Technologie bei LederLotte ist ebenfalls endlich generiert, und zwar durch die folgende (normierte) Basis, bestehend aus zwei Aktivitäten:

Jeder der beiden Aktivitäten in der Basis stellt die notwendigen Einsatzquantitäten der drei Inputarten Arbeit, Nähmaschine und Leder sowie die zwangsläufig anfallende Quantität an Lederresten dar, wenn genau ein Paar Schuhe bzw. genau eine Tasche hergestellt werden.

Produktion und Logistik

PW / OR WS 06/07

2-32

Darstellungsformen endlich generierbarer linearer Technologien Algebraisches Produktionsmodell als Umsetzung der Grundgleichung: z=M·λ ρ in z-Schreibweise (in Nettogrößen) mit zk : Nettomenge der Objektart k in Grundaktivität ρ

⎡ z11 ⎢ 1 z M=⎢ 2 ⎢# ⎢ 1 ⎢⎣ zκ

z12 " z1π ⎤ ⎥ z22 " z2π ⎥ ⇒ # % #⎥ ⎥ zκ2 " zκπ ⎥⎦

π

z k = ∑ z kρ ⋅ λρ für k = 1,..., κ ρ=1

in (x, y)-Schreibweise (in Bruttogrößen) unter Verwendung spezifischer (nicht-negativer) ρ ρ Input- ai und Outputkoeffizienten b j für die jeweiligen Objektarten mit

aiρ = − ziρ > 0

⎡ − a11 ⎢ ⎢ # ⎢ − am1 M=⎢ 1 ⎢ bm +1 ⎢ # ⎢ 1 ⎢⎣bm + n

und

b ρj =

z ρj > 0

− a12 " − a1π ⎤ ⎥ # % # ⎥ − am2 " − amπ ⎥ ⎥ bm2 +1 " bmπ +1 ⎥ # % # ⎥ ⎥ bm2 + n " bmπ + n ⎥⎦

π

⇒

xi = ∑ aiρ ⋅ λρ

für i = 1 ,..., m

ρ =1 π

y j = ∑ bρj ⋅ λρ ρ =1

für j = m + 1 ,..., m + n

Produktion und Logistik

PW / OR WS 06/07

2-33

Allgemeiner Input/Output-Graph (Beispiel LederLotte)

Grundaussage der sog. Aktivitätstheorie: Die Grundaktivitäten einer endlich generierbaren Technologie sind exogen gegebene Daten, die die Nutzung eines Produktionssystems durch die Wahl der Aktivitätsniveaus festlegen. Es sind also die Aktivitäten, welche die Input- und Outputmengen determinieren! Es besteht somit keine allgemeine Outputabhängigkeit vom Input oder umgekehrt.

Produktion und Logistik

PW / OR WS 06/07

2-34

2.2.2.2 Strukturtypen von Technologien Strukturtypen von Technologien

einstufig

mehrstufig

zyklisch

elementar

glatt

konvergierend

outputseitig determiniert

nicht-elementar

divergierend

inputseitig determiniert

umgruppierend

Verfahrenswahl bei OutputHerstellung

Verfahrenswahl bei InputNutzung

allgemein nichtelementar

nicht-zyklisch

Produktion und Logistik

[1]

PW / OR WS 06/07

2-35

Einstufige Technologien zeichnen sich dadurch aus, dass die Objektarten ihrer Grundaktivitäten sich eindeutig in Input- und Output einteilen lassen. Keine Objektart ist zugleich Output einer bestimmten und Input einer anderen Grundaktivität.

[1.1]

Elementare einstufige Technologien basieren nur auf einer einzigen Grundaktivität und bestehen somit aus einem einzigen elementaren Prozess (d.h. π = 1). Unter Weglassen des Aktivitätsindexes ρ (wegen ρ =1) gilt damit für das algebraische Modell:

xi = ai ⋅ λ

für i = 1 ,..., m

y j = bj ⋅ λ

für j = m + 1 ,..., m + n

Bei elementaren Technologien lassen sich folgende Formen der Produktion unterscheiden: (a) (b) (c) (d)

Glatte Produktion Konvergierende Produktion Divergierende Produktion Umgruppierende Produktion

(1 Input/1 Output) (mehrere Inputs/1 Output) (1 Input/mehrere Outputs) (mehrere Inputs/mehrere Outputs)

Produktion und Logistik

PW / OR WS 06/07

2-36

(a)

glatt

(b)

konvergierend

(c)

divergierend

(d)

umgruppierend

Elementare Produktionsstrukturtypen [Quelle : Dyckhoff, 3. Aufl., S. 92]

Anmerkung: Diese spezifischen Formen der Produktion lassen sich auch auf nicht-elementare Technologietypen übertragen.

Produktion und Logistik

PW / OR WS 06/07

2-37

Beispiel einer elementaren Technologie

Input/Output-Graph für Punsch Royal [Quelle : Dyckhoff, 3. Aufl., S. 90]

Als Beispiel sei die Herstellung von Punsch Royal angeführt. Der I/O-Graph der Technologie ist in der Abbildung dargestellt. Die zugehörige Basisaktivität entspricht folgendem Rezept:

Produktion und Logistik

[1.2]

PW / OR WS 06/07

2-38

Nicht-elementare einstufige Technologien zeichnen sich durch das Vorhandensein mehrerer Grundaktivitäten aus. Ihr algebraisches Modell lautet allgemein: π

xi = ∑ aiρ ⋅ λρ

für i = 1 ,..., m

ρ =1 π

y j = ∑ bρj ⋅ λρ

für j = m + 1 ,..., m + n

ρ =1

Bei nicht-elementaren Technologien lassen sich als weitere Strukturtypen je nach Verknüpfung von Input/Output und Grundaktivitäten folgende Formen der Produktion unterscheiden:

Produktion und Logistik

(a)

PW / OR WS 06/07

2-39

Outputseitig determinierte Produktion liegt vor, wenn bei jeder Grundaktivität genau eine Outputart erzeugt wird (→ π = n ) . Für das algebraische Modell bedeutet dies:

y j = b jj ⋅ λ j

so daß :

j = m + 1 ,..., m + n

für m+ n

∑a

xi =

j

i

⋅λ =

j = m +1

⇒

xi =

m+n

∑a

ij

j

m+n

∑a

i

j

/ b jj ⋅ y j

j = m +1

⋅ yj

für

i = 1 ,..., n

i = m +1

j j mit aij = ai / b j

als sog. Produktionskoeffizienten

Konsequenz: Bei outputseitig determinierter Produktion lassen sich die Inputmengen als eindeutige Funktion der Outputmengen beschreiben!

Produktion und Logistik

(b)

PW / OR WS 06/07

2-40

Inputseitig determinierte Produktion liegt vor, wenn bei jeder Grundaktivität genau eine Inputart eingesetzt wird (→ π = m) . Für das algebraische Modell bedeutet dies:

xi = aii ⋅ λ i

i = 1 ,..., m

für m

m

so dass : y j = ∑ b ⋅ λ = ∑ bij / aii ⋅ λ i i j

i =1

m

⇒

y j = ∑ b ji ⋅ xi

i =1

für

j = m + 1 ,..., m + n

i =1

i i mit b ji = b j / ai

Konsequenz:

i

als sog. Ausbeutekoeffizienten

Bei inputseitig determinierter Produktion lassen sich die Outputmengen als eindeutige Funktion der Inputmengen beschreiben!

Produktion und Logistik

(c)

PW / OR WS 06/07

2-41

Verfahrenswahl bei Outputherstellung liegt vor, wenn nur eine einzige Outputart existiert (d.h. n = 1), die alternativ mit π verschiedenen Grundaktivitäten (auch elementare Verfahren genannt) unter Einsatz von m Inputarten hergestellt werden kann. ρ Bei entsprechender Normierung der Grundaktivitäten (mit bm+1 = 1 ) lautet das algebraische Modell unter Benutzung verfahrensspezifischer Produktionskoeffizienten aiρ (ρ = 1 ,..., π) folgendermaßen: π

ym +1 = ∑ ymρ +1 ρ =1 π

xi = ∑ aiρ ⋅ ymρ +1

für

i = 1 ,..., m

ρ =1

ρ ρ mit y m+1 = λ (Outputmenge auf Basis von Verfahren ρ)

Konsequenz: Bei Produktion mit Verfahrenswahl bei Outputherstellung lassen sich die Inputmengen nicht als eindeutige Funktion der Outputmenge beschreiben!

Produktion und Logistik

(d)

PW / OR WS 06/07

2-42

Verfahrenswahl bei Inputnutzung liegt vor, wenn nur eine einzige Inputart existiert (d.h. m=1), die alternativ mit π verschiedenen Grundaktivitäten (elementaren Verfahren) zur Herstellung von n Outputarten verwendet werden kann. ρ Bei entsprechender Normierung der Grundaktivitäten (mit a1 = 1) lautet das algebraische Modell unter Benutzung verfahrensspezifischer Ausbeutekoeffizienten b ρj (ρ = 1 ,..., π) folgendermaßen: π

x1 = ∑ x1ρ ρ =1 π

y j = ∑ bρj ⋅ x1ρ

für

ρ = 2, 3 ,..., n + 1

ρ =1

ρ ρ mit x1 = λ (Inputmenge auf Basis von Verfahren ρ)

Konsequenz: Bei Produktion mit Verfahrenswahl bei Inputnutzung lassen sich die Outputmengen nicht als eindeutige Funktion der Inputmenge beschreiben!

Produktion und Logistik

(e)

PW / OR WS 06/07

2-43

Allgemein nicht-elementare Technologien liegen immer vor, wenn die Spezialfälle (a) bis (d) nicht gegeben sind.

Beispiel für allgemein nicht-elementare Technologien

Basisaktivitäten & Input/Output-Graph einer einstufigen Technologie [Quelle: Dyckhoff, 3. Aufl., S. 94]

In der (x, y)-Darstellungsweise ergibt sich daraus folgendes algebraische Modell, das äquivalent zu dem I/O-Graph der obigen Abbildung ist :

Produktion und Logistik

PW / OR WS 06/07

Beispiel für mehrstufige Technologie

zweistufige Betrachtet wird eine Technologie mit acht Objektarten und fünf Grundaktivitäten, die auf nebenstehender Technologiematrix basiert :

⎛ −1 0 0 0 0 ⎞ ⎜ ⎟ 0 1 0 0 0 − ⎜ ⎟ ⎜ 3 0 −1 0 0 ⎟ ⎜ ⎟ 1 2 0 −1 0 ⎟ ⎜ M= ⎜ 0 3 0 0 −1 ⎟ ⎜ ⎟ 0 0 4 0 0 ⎜ ⎟ ⎜ 5 0 2 4 2⎟ ⎜⎜ ⎟⎟ 0 0 0 6 3 ⎝ ⎠

2-44

Originäre Faktoren Zwischenprodukte oder derivative Faktoren Endprodukte

Zweistufige, inputseitig determinierte Technik [Quelle : Dyckhoff, 3. Aufl., S. 99]

Produktion und Logistik

[2]

PW / OR WS 06/07

2-45

Mehrstufige Technologien zeichnen sich dadurch aus, dass es mindestens zwei Grundaktivitäten mit einer in beiden vorkommenden Objektart gibt, die Output der einen und zugleich Input der anderen Aktivität ist. Derartige Objektarten heißen Zwischenprodukte (oder auch: derivate Faktoren) im Unterschied zu den reinen Inputs (= originäre Faktoren) und den reinen Outputs (= Endprodukte).

Das algebraische Modell lautet auch bei mehrstufiger Technologie in z-Schreibweise allgemein: z = M⋅λ Können Zwischenprodukte k nicht auch von außen bezogen werden (zk < 0 : Primärinput) bzw. nach außen abgegeben werden (zk > 0 : Primäroutput), so lässt sich das algebraische Modell bei Nettodarstellung von Zwischenproduktmengen in einer (x, y, z)-Schreibweise formulieren: π

xi = ∑ − ziρ ⋅ λ ρ

für

i ∈ {originäre Faktoren}

für

i ∈ {Endprodukte}

für

l ∈ {Zwischenprodukte}

ρ=1 π

y j = ∑ z ρj ⋅ λ ρ ρ=1 π

zl = ∑ zlρ ⋅ λ ρ ρ=1

Produktion und Logistik

PW / OR WS 06/07

2-46

Zur Brutto-Darstellung von Produktmengen (auch für Zwischenprodukte) kann auch eine (x, y)-Darstellung für das algebraische Modell unter Nutzung der fundamentalen Mengenbilanz für den Durchsatz rk jeder Objektart angegeben werden. Primärinput + Sekundärinput = Durchsatz = Sekundäroutput + Primäroutput Gesamtinput

Gesamtoutput

Das algebraische Modell lautet dann in (x, r, y)-Schreibweise: π

π

xk + ∑ b ⋅ λ = rk = ∑ akρ ⋅ λ ρ + yk ρ =1

ρ k

ρ

ρ =1

für alle Objektarten

mit prozessspezifischen Input- und Outputmengen

akρ

⎧− zkρ =⎨ ⎩ 0

wenn zkρ < 0 sonst

und

bkρ

⎧ zkρ wenn zkρ > 0 =⎨ ⎩ 0 sonst

Die Stufenzahl einer mehrstufigen Technologie entspricht der Anzahl der Grundaktivitäten der längsten Produktionskette. Als Produktionskette wird eine Folge unmittelbar durch Zwischenprodukte verbundener Grundaktivitäten bezeichnet, so dass jeweils ein Output einer Aktivität als Input in der nachfolgenden Aktivität der Kette wieder eingesetzt wird. Auch mehrstufige Technologien können durch die speziellen Strukturtypen wie bei einstufiger Technologie näher charakterisiert sein!

Produktion und Logistik

PW / OR WS 06/07

2-47

Algebraische Modelle für mehrstufige Technologien (obiges Beispiel) (x, y, z)-Darstellung (netto) x1 x2 z3 z4

= λ1 = = 3λ1 = λ1

z5 y6 y7 y8

= = = 5λ1 =

λ2 − λ3 +2λ 2

− λ4

3λ 2

− λ5 4λ 3 +2λ 3

+4λ 4 6λ 4

⎛ −1 0 0 0 0 ⎞ ⎜ ⎟ ⎜ 0 −1 0 0 0 ⎟ ⎜ 3 0 −1 0 0 ⎟ ⎜ ⎟ 1 2 0 1 0 − ⎟ M=⎜ ⎜ 0 3 0 0 −1 ⎟ ⎜ ⎟ ⎜ 0 0 4 0 0⎟ ⎜ 5 0 2 4 2⎟ ⎜⎜ ⎟⎟ 0 0 0 6 3 ⎝ ⎠

+2λ 5 +3λ 5

(x, r, y)-Darstellung (brutto), alternativ auch kurz: (x, y)-Darstellung x1 x2 x3 + 3λ1 x4 + λ1 + 2λ2 x5 + 3λ2 4λ + 2λ3 + 4λ4 + 2λ5 6λ4 + 6λ5 3

5λ

1

= r1 = λ1 λ2 = r2 = λ3 + = r3 = λ4 + = r4 = λ5 + = r5 = = r6 = = r7 = = r8 =

y3 y4 y5 y6 y7 y8

Originäre Faktoren Zwischenprodukte oder derivative Faktoren Endprodukte

Produktion und Logistik

[3]

PW / OR WS 06/07

2-48

Zyklische Technologien zeichnen sich dadurch aus, dass mindestens eine Grundaktivität existiert, deren Output direkt oder indirekt wieder als Input in dieselbe Aktivität eingeht. Eine zyklische Technologie weist mindestens eine geschlossene Produktionskette (Zyklus) auf.

Das algebraische Modell lautet auch bei zyklischer Technologie allgemein

z = M⋅λ Auch bei zyklischer Technologie muss die fundamentale Mengenbilanz für den Durchsatz jeder Objektart gelten, so dass das entsprechende algebraische Modell für mehrstufige Technologien in (x, r, y)-Schreibweise Anwendung finden kann.

Hinweis: Die Existenz eines (mehrstufigen) Zyklus lässt sich an der Basis M einer Technologie daran erkennen, dass es nicht gelingt, die Zeilen der Technologiematrix so zu vertauschen (d. h. die Objektarten so umzunummerieren), dass in jeder Spalte oben nur Inputarten (negative Einträge) und weiter unter nur Outputarten (positive Einträge) stehen.

Produktion und Logistik

PW / OR WS 06/07

2-49

Beispiel für mehrstufige zyklische Technologie

Technologie mit Verfahrenswahl und zweistufigem Zyklus [Quelle : Dyckhoff, 3. Aufl., S. 103]

Algebraisches Modell in (x, r, y)-Darstellung

x4 +

+ y4

Produktion und Logistik

PW / OR WS 06/07

2-50

2.3 Produktionstheorie auf Ergebnisebene ⇒ Produktionstheorie im engeren Sinne! 2.3.1 Ergebnisorientierte Produktionsanalyse

Ausgangspunkt: Charakterisierungsmöglichkeit aller Objekte in einem Produktionssystem nach ihrer Erwünschtheit (→ Güter, Übel, Neutra) Güter sind nützliche Objekte mit relativer Knappheit, denen ein positiver Wert beigemessen wird. Übel sind schädliche Objekte mit relativem Überschuss, denen ein negativer Wert beigelegt wird. Neutra sind Objekte ohne Wert, denen gegenüber Indifferenz besteht. Die Charakterisierung von Objekten nach der Eigenschaft der Erwünschtheit ist in starkem Maße subjektiv und situationsabhängig!

Konsequenz: Die Ergebnisse der Produktion lassen sich im Zusammenhang mit ihrer Erwünschtheit in positive Ergebnisse (= realer Ertrag), in negative Ergebnisse (= realer Aufwand) und in neutrale Ergebnisse aufteilen.

Produktion und Logistik

PW / OR WS 06/07

2-51

Realer Ertrag entsteht durch Output von Gütern bzw. Input von Übeln und beinhaltet eine Werterhöhung im Transformationsprozess. Realer Aufwand entsteht durch Input von Gütern bzw. Output von Übeln und bedeutet einen Wertverzehr in der Produktion

Realer Aufwand und realer Ertrag sind mehrdimensionale Größen, die in Mengeneinheiten der betreffenden Objektarten gemessen werden. Neutrale Ergebnisse tragen nicht zum realen Aufwand und Ertrag bei! Produktion auf der Ergebnisebene realer Ertrag

realer Aufwand

neutrales Ergebnis

Output von Gütern

Input von Gütern

Input von Neutra

Input von Übeln

Output von Übeln

Output von Neutra

Achtung: Realer Aufwand und Ertrag in der Produktionstheorie dürfen nicht verwechselt werden mit dem (wertmäßigen) Aufwand und Ertrag des Rechnungswesens!

Produktion und Logistik

PW / OR WS 06/07

2-52

Weitere Objektcharakterisierung: Entsprechend ihrer Erwünschtheit (+,-,0) werden Inputobjekte als Faktoren (+), Redukte (-) und Beifaktoren (0) sowie Outputobjekte als Produkte (+), Abprodukte (-) und Beiprodukte (0) bezeichnet.

Ergebniskategorien Realer Ertrag

Prozessbezug

Input

Output

Zweckertrag

(Haupt-)Redukt

(Haupt-)Produkt

Nebenertrag

Reduktfaktor

Gutes Nebenprodukt

(Haupt-)Faktor

Abprodukt

Beifaktor

Beiprodukt

Realer Aufwand Ergebnisneutraler Input bzw. Output Legende:

Gut

Übel

Neutrum

Ergebniskategorien [Quelle : Dyckhoff, 3. Aufl., S. 126]

Produktion und Logistik

PW / OR WS 06/07

2-53

Auf Ergebnisebene lassen sich vier Grundeigenschaften formulieren, die für alle praktisch relevanten Technologien gelten: (1) (2) (3) (4)

Kein Ertrag ohne Aufwand! Irreversibilität der Produktion Möglichkeit ertragreicher Produktion Abgeschlossenheit der Technologie

Beispiel MüllMax: Transformation Input/Output ⇒ Aufwand/Ertrag

Ergebnisse der Müllverbrennung [Quelle : Dyckhoff, 3. Aufl., S. 126]

Produktion und Logistik

PW / OR WS 06/07

2-54

2.3.2 Effizienz und Produktionsfunktion 2.3.2.1 Effizienz von Aktivitäten Bei Kenntnis der Erwünschtheit aller Objektarten ist es möglich, die gesamte Technologiemenge durch sog. Effizienzanalyse in aus Ergebnissicht akzeptable und nichtakzeptable Aktivitäten aufzuteilen.

Eine Aktivität ist nicht-akzeptabel, wenn sie von mindestens einer anderen Aktivität dominiert wird, d. h. wenn es eine andere Aktivität gibt, deren Ertrag nicht kleiner und deren Aufwand nicht größer ist, wobei bzgl. mindestens einer Objektart eine strenge Vorteilhaftigkeit bzgl. Aufwand/Ertrag existiert.

Formal gilt für die Eigenschaft der Dominanz einer Aktivität z1 ggü. einer Aktivität z2, dass für alle Objektarten k (k=1, ... , κ) folgende Ungleichungen gelten müssen: für jede Güterart k, z 1k ≥ z k2 für jede Übelart k, z1k ≤ zk2 wobei für mindestens eine Objektart eine echte Ungleichung gegeben sein muss. Eine Aktivität ist akzeptabel, wenn sie von keiner anderen Aktivität aus der gesamten Technologiemenge dominiert wird, d. h. wenn sie effizient ist. Die Effizienzanalyse hat zur Aufgabe, aus einer Technologiemenge die Menge der effizienten Aktivitäten herauszufiltern (z. B. durch paarweise Prüfung auf Dominanz)

Produktion und Logistik

PW / OR WS 06/07

2-55

Graphisch betrachtet bilden die effizienten Aktivitäten im zweidimensionalen Fall den nordöstlichen Rand einer reinen Gütertechnologie bzw. den südwestlichen Rand einer reinen Übeltechnologie.

Zweidimensionale Gütertechnologien [Quelle : Dyckhoff, 3. Aufl., S. 131]

Produktion und Logistik

PW / OR WS 06/07

2-56

2.3.2.2 Schwaches Erfolgsprinzip und Produktionsfunktion Für rationale produktionswirtschaftliche Entscheidungen ist es geboten, sich auf die Betrachtung der Menge der effizienten Aktivitäten einer Technologie zu beschränken (→ Verzicht auf mengenmäßige Verschwendung).

Das sog. schwache Erfolgsprinzip besagt, dass zum Betreiben von Produktionssystemen nur effiziente Produktionsweisen herangezogen werden sollten. Zur Beschreibung effizienter Produktionsweisen dient die Produktionsfunktion (PF), die den funktionalen Zusammenhang zwischen Input- und Outputmengen aller Objektarten bei effizienter Produktion im Rahmen einer gegebenen Technologie wiedergibt. Die PF charakterisiert den sog. effizienten Rand einer Technologie Teff in funktionaler Form, z. B. im zweidimensionalen Fall durch z2=f2(z1) bzw. z1=f1(z2) (explizite PF)

oder durch

f(z1,z2)=0 (implizite PF).

Teff lässt sich für jede Technologie durch eine implizite PF beschreiben: f(z1,z2, ... , zκ)=0. Dagegen ist eine Darstellung von Teff in Form einer eindimensionalen expliziten PF der Art zk=fk (z1, ... , zk-1, zk+1, ... , zκ) im Allg. nicht möglich! Für das Beispiel von LederLotte lässt sich die PF in x1 = 50 ⋅ y4 + 50 ⋅ y5 expliziter Form nur mehrdimensional durch x2 = 40 ⋅ y4 + 15 ⋅ y5 Teilfunktionen (hier: Faktorfunktionen) beschreiben: x3 = 0,15 ⋅ y4 + 0, 40 ⋅ y5

mit y4 ≥ 0,

y5 ≥ 0

Produktion und Logistik

PW / OR WS 06/07

2-57

2.3.2.3 Eigenschaften von Produktionsfunktionen

Eine PF besitzt die Eigenschaft der Limitationalität, wenn bei effizienter Produktion die Einsatz- und Ausbringungsmengen einer Gruppe G1 von Objektarten für jede vergebene Mengenkombination der Komplementärgruppe G2 eindeutig festliegen. Handelt es sich bei G1 um die Inputobjekte, so spricht man von Inputlimitationalität, handelt es sich um die Outputobjekte, so liegt Outputlimitationalität vor. Eine PF besitzt die Eigenschaft der Variabilität, wenn bei effizienter Produktion die Mengenkombination einer Gruppe von Objektarten durch vorgegebene Mengen der Komplementärgruppe nicht festgelegt ist. Substitutionalität liegt vor, wenn bei zwei variablen Objektarten unter Effizienzbedingungen die Mengensteigerung der einen mit einer Mengenreduzierung der anderen Objektart verbunden ist. Ist dabei die eine Objektart vollständig durch die andere ersetzbar, so spricht man von totaler Substitutionalität, andernfalls von partieller Substitutionalität. Komplementärität liegt vor, wenn bei effizienter Produktion die Mengenänderung variabler Objektarten gleichgerichtet ist.

Produktion und Logistik

PW / OR WS 06/07

2-58

Eine Isoquante stellt den geometrischen Ort aller Mengenkombinationen einer Gruppe G1 von Objektarten dar, die bei vorgegebener Menge der Objektarten der Komplementärgruppe G2 zu einer effizienten Produktion führen. Handelt es sich bei G1 um die Inputobjekte, so spricht man (im Fall reiner Gütertechnologie) von einer Produkt-Isoquante. Bei Inputlimitationalität besteht die Produkt-Isoquante nur aus einem einzigen Punkt! Zur Messung der Ausprägung einzelner Eigenschaften von PF’n werden Messgrößen herangezogen, insbesondere die

• • • •

Grenzrate der Substitution, Grenzproduktivität, Produktionselastizität, Skalenelastizität.

Produktion und Logistik

PW / OR WS 06/07

2-59

Für den Fall einer Gütertechnologie mit Substitutionalität der Faktoren und einer differenzierbaren expliziten PF der Form y3 = f ( x1 , x2 )

gelten für diese Messgrößen folgende Definitionen:

Grenzrate der Substitution zweier Faktoren σ 21 =

dx2 dx1

Grenzproduktivität eines Faktors

π31 =

∂y 3 ∂y bzw. π32 = 3 ∂x1 ∂x 2

Produktionselastizität eines Faktors

ε31 =

∂y 3 y3

Skalenelastizität

ε=

∂x1 ∂y bzw. ε32 = 3 x1 y3

∂x 2 x2

dy3 λ ⋅ y = f (λx1 , λx2 ) y3 dλ (wobei hier 3

Bei Limitationalität der Faktoren sind Grenzwerte der Substitution, Grenzproduktivität und Produktionselastizität nicht definiert!

Produktion und Logistik

PW / OR WS 06/07

2-60

2.3.3 Lineare Produktionstheorie Die Lineare Produktionstheorie befasst sich mit den Eigenschaften von PF’n bei Linearer Technologie (LT), die ggf. auch durch lineare Restriktionen zu einem entsprechenden Produktfeld eingeschränkt sein kann. Die weiteren Betrachtungen beschränken sich auf endlich generierbare LT’n. 2.3.3.1 Effizienz von Grundaktivitäten In Anwendung des schwachen Erfolgsprinzips kann man sich bei der Analyse endlich generierbarer LT’n auf die Betrachtung der effizienten Grundaktivitäten beschränken.

In diesem Zusammenhang gelten die folgenden fünf Aussagen:

Produktion und Logistik

PW / OR WS 06/07

2-61

(1)

Eine Grundaktivität (GA) ist nicht-effizient, wenn sie von einer anderen GA oder einer Linearkombination von GA’n dominiert wird.

(2)

Jede effiziente Aktivität einer Technologiemenge lässt sich als Linearkombination effizienter GA’n darstellen.

Beispiel:

Faktordiagramm mit dominierter Grundaktivität [Quelle : Dyckhoff, 3. Aufl., S. 172]

Produktion und Logistik

PW / OR WS 06/07

2-62

(3)

Echte Linearkombinationen nicht-effizienter GA’n können keine effizienten Aktivitäten erzeugen.

(4)

Echte Linearkombinationen effizienter GA’n können allerdings zu nicht-effizienten Aktivitäten führen.

(5)

Sofern auch nur eine echte Linearkombination mehrerer effizienter GA’n eine effiziente Aktivität erzeugt, so gilt dies auch für alle anderen Kombinationen.

Beispiel:

Linearkombination dreier Grundaktivitäten [Quelle : Dyckhoff, 3. Aufl., S. 168]

Produktion und Logistik

PW / OR WS 06/07

2.3.3.2 Limitationalität und Variabilität Die Eigenschaften der PF bei LT hängen vom Strukturtyp der Technologie ab.

Elementare sowie einseitig (d.h. input- bzw. outputseitig) determinierte nicht-elementare LT’n sind immer limitational. Eine outputseitig determinierte LT ist immer inputlimitational bzw. (bei reiner Gütertechnologie) aufwandslimitational. Eine inputseitig determinierte LT ist immer outlimitational bzw. ertragslimitational. Die PF lässt sich bei Limitationalität explizit durch mehrere sog. Faktorfunktionen bzw. Produktfunktionen (siehe algebraisches Modell) beschreiben. Eine PF bei LT und Limitationalität wird auch als linearlimitational bezeichnet. Im Fall einer inputlimitationalen Gütertechnologie spricht man auch von einer Leontief-PF.

2-63

Produktion und Logistik

PW / OR WS 06/07

Nicht-elementare LT’n, die nicht einseitig determiniert sind, lassen eine Variabilität bei Faktoreinsatz und/oder Produkterzeugung zu. LT’n mit Verfahrenswahl bei Outputherstellung zeichnen sich durch Substitutionalität der Faktoren, solche mit Verfahrenswahl bei Inputnutzung durch Substitutionalität der Produkte aus. Bei variabler LT besteht die Produktisoquante aus linearen Teilstücken. Grenzraten der Substitution und Grenzproduktivitäten sind in diesem Fall definiert und messbar.

2-64

Produktion und Logistik

PW / OR WS 06/07

2-65

2.4 Produktionstheorie auf Erfolgsebene Die Produktionstheorie auf Erfolgsebene versucht auf Basis eines eindimensionalen Erfolgsmaßstabs zu einer vollständigen Vergleichbarkeit aller Aktivitäten einer Technologie zu kommen, was auf Ergebnisebene i. d. R. nicht möglich ist. 2.4.1 Erfolgsmessung und Erfolgsfunktion 2.4.1.1 Grundlagen der Erfolgsmessung Unter Erfolg wird der eindimensional Produktionsweise verstanden.

messbare

Wertschöpfungsbeitrag

einer

Grundannahme der Produktionstheorie auf Erfolgsebene ist, dass der Erfolg jeder Produktions-Aktivität z durch eine reellwertige Zahl w gemessen werden kann, die deren Wertschöpfungsbeitrag aus der (subjektiven) Sicht des Betrachters des Produktionssystems wiedergibt. Die sog. Erfolgsfunktion

w(z ) = w( z1 , z2 , ... ,zκ ) ∈ \

für alle

z ∈T

erlaubt einen direkten Vergleich aller Aktivitäten und gewährleistet damit eine vollständige Präferenzordnung.

Produktion und Logistik

PW / OR WS 06/07

Grundeigenschaften der Erfolgsfunktion ¾ Normierung für erfolgsneutrale Aktivitäten z :

w(z)=0

¾ Kompatibilität von Erfolg und Erwünschtheit: ⎧ > 0 für jede Güterart k ∂w(z) ⎪ ⎨ < 0 für jede Übelart k ∂z k ⎪ ⎩ = 0 für jede neutrale Objektart k

Bewertungsbasis für die Erfolgsfunktion w(z) -

Marktpreis für Objektarten staatlich festgesetzte Preise innerbetriebliche Verrechnungspreise subjektive präferenzabhängige Wertgrößen

bei rein ökonomischer Betrachtung

2-66

Produktion und Logistik

PW / OR WS 06/07

2-67

Ökonomische Erfolgsfunktionen

⎧ > 0 : Gewinn w(z) : Reinvermögensänderung durch Aktivität z mit w(z ) ⎨ ⎩ < 0 : Verlust Bei Erfolgsaufspaltung nach Richtung der Vermögensänderung erhält man - als positiven Erfolgsanteil (bewerteter realer Ertrag) : Erlöse E(z), Kosten K(z), - als negativen Erfolgsanteil (bewerteter realer Aufwand) :

w(z) = E(z) – K(z).

so dass insgesamt gilt:

Bei Abspaltung von fixen Erfolgsanteilen

wfix = w(z = 0) erhält man den variablen (d.h. mengenabhängigen) Produktionserfolg wvar, der auch als Deckungsbeitrag D bezeichnet wird:

D(z)

=

wvar(z) = w(z) – wfix

=

Evar(z) – Kvar(z)

Der Deckungsbeitrag ist ein angemessenes Erfolgskriterium bei Entscheidungen zur laufenden Nutzung eines gegebenen Produktionssystems, allerdings nicht bei Entscheidungen zu dessen Um- oder Neugestaltung.

Produktion und Logistik

PW / OR WS 06/07

Beispiel MüllMax : Produktionserfolg

GE

Produktionserfolg der dargestellten Aktivität : E (z ) =

300 + 75, 2 + 97 = 472, 2

K (z ) = 20 + 175 + 35 + 60 = 290 W (z ) =

472, 2 − 290 = 182, 2 I/O-Graph einer Müllverbrennungsanlage mit Wertflüssen [Quelle :Dyckhoff, 3. Aufl., S. 196]

2-68

Produktion und Logistik

PW / OR WS 06/07

Eigenschaften der Erfolgsfunktion Erfolgsfunktionen können durch eine Ausprägungen haben:

Hierarchie

2-69

von

Eigenschaften

spezifische

Erfolgsfunktion separabel additiv linear

nicht-separabel nicht-additiv

nicht-linear

¾ Separabilität einer Erfolgsfunktion liegt vor, wenn der Gesamterfolg in getrennte Erfolgsbeiträge einzelner Objektarten aufgespaltet werden kann:

w(z) = W(w1(z1), w2(z2), ... wκ(zκ)) → Voraussetzung: Isolierbarkeit objektspezifischer Erfolgseinflüsse

Produktion und Logistik

PW / OR WS 06/07

2-70

¾ Additivität einer separablen Erfolgsfunktion liegt vor, wenn sich die objektspezifischen Erfolgsbeiträge additiv zum Gesamterfolg verknüpfen lassen:

w(z) = w1(z1) + w2(z2) + ... + wκ(zκ) → Voraussetzung: Präferenzunabhängigkeit der Objektarten ¾ Linearität einer additiv-separablen Erfolgsfunktion liegt vor, wenn alle objektbezogenen Grenzerfolge konstant sind:

∂w( z ) = const. ∂z k → Voraussetzung: Keine Mengenabhängigkeit von Preisen bei Beschaffung oder Absatz von Objekten. w( z ) = p1 ⋅ z1 + p 2 ⋅ z 2 + ... + p κ ⋅ z κ

mit p k =

Produktion und Logistik

PW / OR WS 06/07

2-71

2.4.1.2 Starkes Erfolgsprinzip Das sog. starke Erfolgsprinzip besagt, dass beim Betreiben von Produktionssystemen als optimale nur die erfolgsmaximale(n) Produktionsweise(n) z0 herangezogen werden sollten! Für z0 gilt dabei: w( z 0 ) = max {w( z ) z ∈ T}

Bei Konsistenz von Präferenzen auf Ergebnis- und Erfolgsebene muss eine Kompatibilität von schwachem und starkem Erfolgsprinzip existieren, d. h. z0 ∈ Teff Existenz optimaler Aktivitäten : Größenproportionale Technologieformen zeichnen sich durch unbeschränkte Aktivitätsmengen aus, so dass i. d. R. eine erfolgsmaximale Produktionsweise mit endlicher Faktoreinsatz- bzw. Produktausbringungsmenge nicht existiert. Im Zusammenhang mit externen Beschränkungen der Produktionsmöglichkeiten durch ein Restriktionsfeld R ist die Anwendung des starken Erfolgsprinzips in der Praxis auf das Produktionsfeld Z bezogen, so dass im Prinzip von der Existenz erfolgsmaximaler Produktionsweisen ausgegangen werden kann, wobei für die optimale Aktivität gilt:

w( z 0 ) = max {w( z) z ∈ Z = T ∩ R}

Produktion und Logistik

PW / OR WS 06/07

2-72

Beispiel: Annahmen • z1 und z2 sind Güter • lineare additiv-separable Erfolgsfunktion, die zu einem Gewinn bei effizienten Produktionsweisen führt

erfolgsmaximale Produktionsweise

T

z2 4

effiziente Produktionsweisen

3

Z R

2 1

-8

-7

-6

-5

-4

-3

-2

-1

z1

Produktion und Logistik

PW / OR WS 06/07

2-73

2.4.1.3 Erfolgsmaximierung bei beschränktem Produktionsfeld Beispiel: Linear-limitationale Technologie mit outputseitig determinierter Güterproduktion → LederLotte mit Produktionsfeld aus U 2-26 Produktionsfeld Z:

⎧ ⎫ ⎛ −50 ⎞ ⎛ −50 ⎞ ⎛ -5000 ⎞ ⎪ ⎪ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎪ ⎪ ⎜ −40 ⎟ ⎜ −15 ⎟ ⎜ -3000 ⎟ ⎪⎪ ⎪⎪ ⎜ −0,15 ⎟ 2 ⎜ −0, 4 ⎟ ⎜ -30 ⎟ 1 2 Z = ⎨z ∈ \ 6 z = λ1 ⋅ ⎜ + λ ⋅ ≥ ; λ , λ ≥ 0 ⎟ ⎜ ⎟ ⎜ ⎟ ⎬ ⎜ 1 ⎟ ⎜ 0 ⎟ ⎜ 50 ⎟ ⎪ ⎪ ⎜ 0 ⎟ ⎜ 1 ⎟ ⎜ 10 ⎟ ⎪ ⎪ ⎜⎜ ⎟⎟ ⎜⎜ ⎟⎟ ⎜⎜ ⎟⎟ ⎪ ⎪ ⎪⎩ ⎪⎭ ⎝ 30 ⎠ ⎝ 25 ⎠ ⎝ 0 ⎠

Ersetzen von Aktivitätsniveaus durch Produktionsmengen y4=λ1 und y5=λ2: Produktionsfeld : 0 ≤ x1 = 50·y4 + 50·y5 ≤ 5000 (1) 0 ≤ x2 = 40·y4 + 15·y5 ≤ 3000 (2) 0 ≤ x3 = 0,15·y4 + 0,40·y5 ≤ 30 (3) y4 ≥ 50 (4) y5 ≥ 10 (5) 0 ≤ y6 = 30·y4 + 25·y5 Erfolgsfunktion :

Additiv-separabel und linear mit Objektbewertungen: p1 = 1 , p2 = 2 , p3 = 500 , p4 = 200 , p5 = 400 , p6 = 0

⇒ D = D(x1 , x2 , x3 , y4 , y5 , y6) = -1·x1-2·x2-500·x3 +200·y4+400·y5+0·y6 = D(y4 , y5) = (-50-80-75+200)·y4 + (-50-30-200+400)·y5 = -5·y4 + 120·y5 mit produktspezifischen Deckungsbeiträgen: d4 = -5, d5 = 120

Produktion und Logistik

PW / OR WS 06/07

y5

2-74

Produktionsfeld Z (2) (4)

erfolgsmaximale Produktionsweise (3)

Z

(1) (5)

y4 (6) Erfolgsmaximum 0 aus Mindestmenge für Produkt 4 : y4 = 50 und Maximalmenge für Produkt 5 (beschränkt durch Engpass-Faktor 1): y50 aus : 50 ⋅ y40 + 50 ⋅ y50 = 5000 → y50 = (5000 − 50 ⋅ 50) / 50 = 50 Optimale Aktivität z 0 = (−5000; − 2750; − 27,5; 50; 50; 2750) → D 0 = − 5 ⋅ 50 + 120 ⋅ 50 = 5750

Produktion und Logistik

PW / OR WS 06/07

2-75

Engpassanalyse bei Erfolgsmaximierung Einzelne Restriktionen aus dem Restriktionsfeld R (in Form von Mindest- oder Höchstmengen einzelner Objektarten) können zu Erfolgsbeschränkungen führen. Verhinderte Erfolgsverbesserungen durch derartige Restriktionen werden als Opportunitätskosten der Objektart bezeichnet. Sie sind positiv, wenn eine Objektart einen Engpass für eine Erfolgsverbesserung darstellt, ansonsten sind sie gleich Null! Die marginalen Opportunitätskosten pro Engpasseinheit werden als Schattenpreis der entsprechenden Objektart bezeichnet. Beispiel LederLotte: Schattenpreis der Objektart 1 (verfügbare Arbeitsminuten) : ΔD0 = D0(x1=5001) - D0(x1=5000) 0

Für x1 = 5001 gilt : y5 = (5001 − 50 ⋅ 50) / 50 = 50, 02 → D0(x1 = 5001) = -5·50 + 120·50,02 = 5752,4 → ΔD0 = 5752,4-5750 = 2,4 (Schattenpreis der Arbeit) Schattenpreis der Objektart 4 (Schuhe) : ΔD0 = D0(y4=49)-D0(y4=50) Für y4 = 49 gilt : y5 = (5000-50·49)/50 = 51 → D0(y4 = 49) = -5·49 + 120·51 = 5875 → ΔD0 = 5875-5750 = 125 (Schattenpreis der Lieferverpflichtung Schuhe) Schattenpreis für die anderen Objektarten (2,3 und 5) : → ΔD0 = 0

Produktion und Logistik

PW / OR WS 06/07

2-76

Erfolgsmaximierung bei einem einzigen Engpass

• Optimale Engpassfaktorzuteilung nach engpassspezifischen (d. h. relativen) Deckungsbeiträgen Erfolgsmaximierung bei mehreren Engpässen

• Engpassspezifische Deckungsbeiträge können erst bei Kenntnis der optimalen Aktivität ermittelt werden. • Notwendigkeit zur Lösung eines umfassenden Optimierungsproblems z.B. in Form eines LOP (Lineares Optimierungsproblem).

Produktion und Logistik

PW / OR WS 06/07

2-77

2.4.2 Lineare Erfolgstheorie 2.4.2.1 Grundlagen der linearen Erfolgstheorie Die lineare Erfolgstheorie bezieht sich auf Produktionssysteme mit folgenden Komponenten: (1) (2) (3)

Lineare Technologie T Restriktionsfeld R mit absoluten Schranken Lineare, additiv-separable Erfolgsfunktion w(z)

→ Aus (1) und (2) folgt, dass das Produktionsfeld Z = T ∩ R ein konvexes Polyeder darstellt.

Produktion und Logistik

PW / OR WS 06/07

2-78

Erfolgsfunktion bei endlich generierbarer Technologie: π ⎛ π ρ ρ⎞ κ π ⎞ ⎛ κ ρ ρ w( z ) = ∑ pk ⋅ zk = ∑ pk ⋅ ⎜⎜ ∑ λ ⋅ zk ⎟⎟ = ∑∑ pk ⋅ λ ⋅ zk = ∑ ⎜ ∑ pk ⋅ zkρ ⎟ ⋅ λρ k =1 k =1 ρ=1 ⎝ k =1 ⎠ ⎝ ρ=1 ⎠ k =1 ρ=1 κ

κ

Definiert man als prozessspezifische Deckungsbeiträge der Grundaktivitäten:

d ρ = p1 ⋅ z1ρ + p2 ⋅ z2ρ + , ... , + pκ ⋅ zκρ

für

ρ = 1 , ... , π ,

so gilt allgemein für die Erfolgsfunktion:

w( z) = w( λ ) = d 1 ⋅ λ1 + d 2 ⋅ λ2 + ... + d π ⋅ λπ Konsequenz : Der Gesamterfolg eines Produktionssystems ist eine lineare Funktion des Aktivitätsniveaus der einzelnen Grundaktivitäten! Hinweis

: Die prozessspezifischen Deckungsbeiträge kennzeichnen den Überschuss objektbezogener Erlöse über die variablen Kosten bei Betreiben einer Grundaktivität. Eine Zurechnung derartiger Deckungsbeiträge zu einzelnen Objektarten ist i. d. R. nicht möglich!

Produktion und Logistik

PW / OR WS 06/07

2-79

2.4.2.2 Erfolgsfunktionen bei spezifischen Technologiestrukturtypen

Definition: Im Zusammenhang mit der (x, y)-Schreibweise werden die Erfolgsbeiträge je ME (pk) für Inputgüter i mit ci (= Stückkosten) und für Outputgüter j mit ej (= Stückerlöse) bezeichnet. Unter Nutzung der jeweiligen algebraischen Produktionsmodelle lassen sich für unterschiedliche Strukturtypen linearer Technologien die jeweiligen Erfolgsfunktionen detailliert angeben und auswerten. Für prozessspezifische Deckungsbeiträge gilt damit im Zusammenhang mit dem allgemeinen algebraischen Modell für jeden Strukturtyp xi = ∑ aiρ ⋅ λρ und yi = ∑ bρj ⋅ λρ : ρ

d ρ = ∑ e j ⋅ bρj − ∑ ci ⋅ aiρ j

i

für ρ = 1, ... , π

ρ

Produktion und Logistik

PW / OR WS 06/07

2-80

• Elementare Technologie (π = 1)

w( x, y) = ∑ e j ⋅ y j − ∑ ci ⋅ xi = ∑ e j ⋅ b j ⋅ λ − ∑ ci ⋅ ai ⋅ λ = w(λ ) j

i

→ prozessspezifischer Deckungsbeitrag :

j

i

d = ∑e j ⋅ bj − ∑ci ⋅ ai j

i

→ Deckungsbeitrag d kann auch einem einzelnen Produkt- oder einem einzelnen Faktor zugerechnet werden: d d dj = bzw. d i = bj ai (Annahme: Die anderen Produkte und Faktoren erhalten keinen Erfolgsbeitrag zugerechnet.)

Produktion und Logistik

PW / OR WS 06/07

2-81

• Outputseitig determinierte Produktion Im Zusammenhang mit

xi = ∑ aij ⋅ y j gilt hier: j

⎞ ⎛ w( x, y ) = ∑ e j ⋅ y j − ∑ ci ⋅ xi = ∑ ⎜ e j − ∑ ci ⋅ aij ⎟⎟ ⋅ y j = w( y ) j i j ⎝ i ⎠

k j = ∑ ci ⋅ aij

Unter Definition produktspezifischer Stückkosten lassen sich produktspezifische Deckungsbeiträge

i

d j = ej − k j

formulieren, so dass gilt:

w( x , y ) = w( y ) = ∑ d j ⋅ y j j

Ergebnis: Bei outputseitig determinierter Produktion Deckungsbeiträgen auf die jeweiligen Produkte möglich!

ist

die

Zurechnung

von

Produktion und Logistik

PW / OR WS 06/07

2-82

• Inputseitig determinierte Produktion Im Zusammenhang mit

y j = ∑ b ji ⋅ xi

gilt hier:

i

⎞ ⎛ w( x, y ) = ∑ e j ⋅ y j − ∑ ci ⋅ xi = ∑ ⎜⎜ ∑ e j ⋅ bij − c j ⎟⎟ ⋅ xi = w( x ) j i i ⎝ j ⎠ li = ∑ e j ⋅ bij Unter Definition faktorspezifischer Stückerlöse j

lassen sich faktorspezifische Deckungsbeiträge

d i = li − ci

formulieren, so dass gilt:

w( x, y ) = w( x ) = ∑ d i ⋅ xi i

Ergebnis: Bei inputseitig determinierter Produktion Deckungsbeiträgen auf die jeweiligen Faktoren möglich!

ist

die

Zurechnung

von

Produktion und Logistik

PW / OR WS 06/07

2-83

• Verfahrenswahl bei Produktherstellung ρ ρ ρ Im Zusammenhang mit ym+1 = ∑ ym+1 und xi = ∑ ai ⋅ y m+1 ρ

gilt hier:

i

⎞ ⎛ w( x, ym +1 ) = em +1 ⋅ ym +1 − ∑ ci ⋅ xi = ∑ ⎜ em +1 − ∑ ci ⋅ aiρ ⎟⎟ ⋅ ymρ +1 ρ ⎝ i i ⎠ k ρ = ∑ ci ⋅ aiρ Unter Definition verfahrenspezifischer Stückkosten i

verfahrensspezifische Produkt-Deckungsbeiträge

d ρ = em+1 − k ρ

lassen sich

formulieren, so dass gilt:

w( x, ym +1 ) = ∑ d ρ ⋅ ymρ +1 = ∑ d ρ ⋅ λρ = w( λ ) ρ

ρ

Ergebnis: Im Rahmen von Verfahrenswahl bei Produktherstellung ist eine eindeutige Zurechnung des Deckungsbeitrags auf das Endprodukt nur bei vorheriger Festlegung der jeweiligen Produktionsverfahren möglich.

Produktion und Logistik

PW / OR WS 06/07

2-84

• Verfahrenswahl bei Faktornutzung Hier gelten die obigen Zusammenhänge in umgekehrter Formulierung:

w( x1 , y ) = ∑ d ρ ⋅ x1ρ = ∑ d ρ ⋅ λρ = w( λ ) mit ρ

ρ

d ρ = ∑ e j ⋅ bρj − c1

als verfahrensspezifische

j

Faktor-Deckungsbeiträge Hinweis : Ohne Faktor- oder Produktbeschränkungen würde bei Verfahrenswahl-Systemen gemäß dem starken Erfolgsprinzip als einziges Produktionsverfahren nur das erfolgsmaximale Verfahren zum Zuge kommen. Damit würden sich Systeme mit Verfahrenswahl bei Produktion auf Systeme mit einseitig determinierter Produktion reduzieren.

Produktion und Logistik

PW / OR WS 06/07

2-85

2.4.2.3 Erfolgsmaximierung bei Faktor- und Produktbeschränkungen Für einstufige Produktionssysteme mit gegebenem Restriktionsfeld R der Art R= z z≤z≤z

{

}

führt die Suche nach der erfolgsmaximalen Produktionsweise zur Optimierungsaufgabe: Maximiere

w(λ1 , ... , λπ)

=

d1⋅λ1 + ... + dπ⋅λπ

unter den Nebenbedingungen z1k ⋅ λ1 + ... + zkπ ⋅ λ π ≤ z k für

k = 1 , ... , κ

1 1 π π und zk ⋅ λ + ... + zk ⋅ λ ≥ z k

k = 1 , ... , κ

bei Linearer Technologie: bzw. bei Additiver Technologie:

für

λi , ... , λπ ≥ 0 λi , ... , λπ ≥ 0 und ganzzahlig

Die Aufgabe besteht in der Festlegung der Niveaus aller Grundaktivitäten der Technologie in der Art, dass der Gesamterfolg maximiert und alle externen Restriktionen eingehalten werden. Die Aktivitätsniveaus λρ (ρ=1,...,π) sind Entscheidungsvariablen des Optimierungsproblems. Bei der Erfolgsmaximierung im Rahmen der linearen Erfolgstheorie handelt es sich um ein Lineares Optimierungsproblem (LOP) ohne bzw. mit ganzzahligen Variablen. Aus der Lösung des LOP erhält man neben den optimalen Aktivitätsniveaus auch (im Fall ohne Ganzzahligkeit) die Schattenpreise für die einzelnen Restriktionen.

Produktion und Logistik

PW / OR WS 06/07

2-86

Beispiel: Erfolgsmaximierung bei Faktorbeschränkungen Strukturtyp: Verfahrenswahl bei Produktherstellung

Prozessstrahlen im Faktordiagramm:

⇒ Verfahren (4) wird dominiert

Stückkosten der Faktoren: c1=2 und c2=1 Ergebnis: Verfahrensspezifische Stückkosten: 2⋅100 + 1⋅20 = k1 = 2 = 2⋅50 + 1⋅30 = k 3 = 2⋅30 + 1⋅60 = k

220 130 120 ⇒ Erfolgsmaximales Verfahren ist Verfahren (3)

Produktion und Logistik

PW / OR WS 06/07

2-87

Faktorbeschränkungen: x1≤800

und

x2≤360

Ergebnis: Auch dominierte Verfahren müssen bei erfolgsmaximaler Produktion unter Umständen herangezogen werden. Darstellung des Expansionspfades (outputabhängige kostenminimale Produktionsweise) im Faktordiagramm:

400

120 120

Expansionspfad bei Faktorbeschränkungen

140

Grenzkostenverlauf auf dem Expansionspfad

Produktion und Logistik

PW / OR WS 06/07

Überblick

Algebraisches Produktionsmodell in (x, y)-Schreibweise (in Bruttogrößen) unter ρ ρ Verwendung spezifischer (nicht-negativer) Input- ai und Outputkoeffizienten b j für die ρ ρ jeweiligen Objektarten mit ai = − zi > 0 outputseitig determiniert ( π = n ) ⎡ − a11 − a12 " − a1π ⎤ ⎢ ⎥ # # % # ⎢ ⎥ 1 2 π ⎢ − a − am " − am ⎥ M=⎢ 1m ⎥ 0 0 b " ⎢ m +1 ⎥ ⎢ # # % # ⎥ ⎢ ⎥ 0 " bmπ + n ⎥⎦ ⎢⎣ 0

und

Verfahrenswahl bei Outputherstellung (n=1), normiert ⎡ − a11 − a12 " − a1π ⎤ ⎢ ⎥ # # % # ⎥ M=⎢ 1 2 π ⎢ − am − am " − am ⎥ ⎢ ⎥ 1 1 1 " ⎣ ⎦

b ρj =

z ρj > 0

outputseitig determiniert ( π = m ) ⎡ − a11 0 " 0 ⎤ ⎢ ⎥ # # % # ⎢ ⎥ π ⎢ 0 0 " − am ⎥ M=⎢ 1 2 π ⎥ b b b " ⎢ m +1 m +1 m +1 ⎥ ⎢ # # % # ⎥ ⎢ 1 ⎥ 2 π ⎢⎣bm + n bm + n " bm + n ⎥⎦ Verfahrenswahl bei Inputnutzung (m=1), normiert −1 " −1 ⎤ ⎡ −1 ⎢ b1 2 π ⎥ " b b + 1 + 1 +1 ⎥ m m m M=⎢ ⎢ # # % # ⎥ ⎢ 1 2 π ⎥ ⎣bm + n bm + n " bm + n ⎦

Produktion und Logistik

(a)

PW / OR WS 06/07

2-39

Outputseitig determinierte Produktion liegt vor, wenn bei jeder Grundaktivität genau eine Outputart erzeugt wird (→ π = n ) . Für das algebraische Modell bedeutet dies:

y j = b jj − m ⋅ λ j − m

so daß :

⇒

xi =

xi =

j = m + 1 ,..., m + n

für m+ n

∑a

j = m +1

m+ n

∑

j = m +1

j −m

i

aij ⋅ y j

⋅λ

j −m

=

m+n

∑a

j = m +1

für

i

j −m

/ b jj − m ⋅ y j

i = 1 ,..., m

j −m j −m mit aij = ai / b j als sog. Produktionskoeffizienten

Konsequenz: Bei outputseitig determinierter Produktion lassen sich die Inputmengen als eindeutige Funktion der Outputmengen beschreiben!

Produktion und Logistik

[2]

PW / OR WS 06/07

2-45

Mehrstufige Technologien zeichnen sich dadurch aus, dass es mindestens zwei Grundaktivitäten mit einer in beiden vorkommenden Objektart gibt, die Output der einen und zugleich Input der anderen Aktivität ist. Derartige Objektarten heißen Zwischenprodukte (oder auch: derivate Faktoren) im Unterschied zu den reinen Inputs (= originäre Faktoren) und den reinen Outputs (= Endprodukte).

Das algebraische Modell lautet auch bei mehrstufiger Technologie in z-Schreibweise allgemein: z = M⋅λ Produktmengen von Produkt k, die nach außen abgegeben werden (zk > 0), heißen Primäroutput; Produkte, die von außen bezogen werden (zk < 0) nennt man Primärinput. In gemischter Nettodarstellung von Zwischenproduktmengen lässt sich das algebraische Modell in einer (x, y, z)-Schreibweise formulieren: π

xi = ∑ − ziρ ⋅ λ ρ

für

i ∈ {originäre Faktoren}

für

i ∈ {Endprodukte}

für

l ∈ {Zwischenprodukte}

ρ=1 π

y j = ∑ z ρj ⋅ λ ρ ρ=1 π

zl = ∑ zlρ ⋅ λ ρ ρ=1

Produktion und Logistik

PW / OR WS 06/07

3 Lineare Optimierung

3-1

Produktion und Logistik

PW / OR WS 06/07

3-2

3.1 Grundlagen der Linearen Optimierung 3.1.1 Grundbegriffe und Grundzusammenhänge Unter einem (Allgemeinem) Linearen Optimierungsproblem (LOP) versteht man ganz allgemein die folgende Aufgabenstellung LOP-A: Wähle p Variable x1 ,..., xp derart, dass eine lineare Zielfunktion (A.1.)

Z ( x1 , ... , x p ) = c1A ⋅ x1 + ... + c pA ⋅ x p

maximiert oder minimiert wird, wobei zugleich lineare Nebenbedingungen der Form (A.2)

aiA1 ⋅ x1 + ... + aipA ⋅ x p ≤ biA

für

i = 1 ,..., m1

(A.3)

aiA1 ⋅ x1 + ... + aipA ⋅ x p ≥ biA

für

i = m1 + 1 ,..., m2

(A.4)

aiA1 ⋅ x1 + ... + aipA ⋅ x p = biA

für

i = m2 + 1 ,..., m A

beachtet werden und zusätzlich Nichtnegativitätsbedingungen für die Variablen gelten können (A.5.)

xj ≥ 0

für (einige oder alle)

j=1 ,..., p

Produktion und Logistik

PW / OR WS 06/07

3-3

Einen Vektor x = ( x1 ,..., x p )T ∈ \ p , der alle Nebenbedingungen (A.2)-(A.4) erfüllt, nennt man eine Lösung des LOP. Einen Lösungsvektor x, der zusätzlich die Nichtnegativitätsbedingungen (A.5) erfüllt, heißt zulässige Lösung des LOP. Eine zulässige Lösung x * = ( x1* ,..., x *p )T heißt optimale Lösung des LOP, wenn es keine zulässige Lösung x mit einem besseren (größeren bzw. kleineren) Zielfunktionswert als Z(x*) gibt. Die Menge der zulässigen Lösungen wird mit X, die Menge der optimalen Lösungen mit X* bezeichnet.

Produktion und Logistik

PW / OR WS 06/07

3-4

Beispiel LederLotte : Erfolgsmaximierung bei mehreren Faktorengpässen Erfolgsmaximierung für das Unternehmen LederLotte Max Z = 60x1 + 120x2

x2 (2)

u.d.N.

mit x1 : x2 : Z :

50x1 + 50x 2 ≤ 5000

(1)

40x1 + 15x 2 ≤ 3000

(2)

0,15x1 + 0, 4x 2 ≤ 30

(3)

x1 ≥ 50

(4)

x 2 ≥ 10 x1 ≥ 0, x2 ≥ 0

(5)

(4)

Erfolgsmaximum

(3) Produktionsmenge Schuhe (bisher y4) Produktionsmenge Taschen (bisher y5) Gesamtdeckungsbeitrag (bisher D)

(1) (5) x1

Produktion und Logistik

PW / OR WS 06/07

3-5

Jedes LOP der allgemeinen Form LOP-A lässt sich in eine äquivalentes LOP in Standardform LOP-S transformieren: p

Z ( x1 ,..., x p ) = ∑ c Sj ⋅ x j

j =1 Maximiere unter den Nebenbedingungen (u.d.N.)

p

∑a

S ij

⋅ x j ≤ biS

für i = 1 ,..., m

j =1

xj ≥ 0

für j = 1 ,..., p

Für die Transformation lassen sich folgende Äquivalenzbeziehungen (=ˆ ) nutzen:

[1]

Min Z ( x1 ,..., x p ) =ˆ Max − Z ( x1 ,..., x p )

[2]

∑a

⋅ x j ≥ bi

∑a

⋅ x j = bi

ij

=ˆ

j

[3]

ij

∑ (−a ) ⋅ x ij

j

≤ −bi

j

=ˆ

j

[4] x j ∈ \

∑a

ij

⋅ x j ≤ bi und

j

=ˆ

∑a

ij

⋅ x j ≥ bi

j

+ j

xj = x − x

− j

+ j

und x , x −j ≥ 0

Produktion und Logistik

PW / OR WS 06/07

3-6

Jedes LOP-S lässt sich durch Einführung von sog. Schlupfvariablen xp+1 ,..., xp+m in eine äquivalentes LOP in Normalform LOP-N überführen: n

Maximiere

Z ( x1 ,..., xn ) = ∑ c j ⋅ x j

mit ( n = p + m )

j =1

u.d.N. n

∑a

ij

⋅ x j = bi

für i = 1 ,..., m

j =1

xj ≥ 0

für alle j = 1 ,..., n

dabei besitzt das LOP-N folgende spezifische Struktur: p

Max

Z ( x1 ,..., x p , x p+1 ,..., xn ) = ∑ c ⋅ x j + S j

j =1

n

∑0⋅ xj

j = p +1

u. d. N. p

∑a j =1

S ij

⋅ x j + x p +i = biS

xj ≥ 0

für alle

für i = 1 ,..., m

j = 1 ,..., n

Die p ursprünglichen Variablen x1, ..., xp werden Strukturvariablen genannt. Die m zusätzlichen Schlupfvariablen xp+1, ..., xn nutzt man, um die m Ungleichungen in Gleichungen zu transformieren. Das LOP-N enthält also (ohne Nichtnegativitätsbedingungen) m Nebenbedingungen und n = p + m > m Variablen.

Produktion und Logistik

PW / OR WS 06/07

In Matrixschreibweise lässt sich das LOP-N folgendermaßen formulieren: Max Z ( x ) = c u. d. N. A·x=b x≥0

T

⋅x

In diesem haben die Vektoren b (Dimension: m) und c (Dimension: n) sowie die (m x n) Matrix A folgende Struktur (sog. LOP in kanonischer Form):

⎡ c1 ⎤ ⎡ a11 " a1,n−m 1 0 " 0 0 ⎤ ⎢ # ⎥ ⎢ # ⎥ # % ⎡ b1 ⎤ ⎢c ⎥ ⎢ ⎥ b = ⎢ # ⎥ , c = ⎢ n−m ⎥ , A = ⎢ # # % ⎥ ⎢b ⎥ ⎢ 0 ⎥ # % ⎢ # ⎥ ⎣ m⎦ ⎢ # ⎥ ⎢ am,1 " am,n−m 0 0 " 0 1 ⎥ ⎢ 0 ⎥ ⎣ ⎦ ⎣ ⎦

3-7

Produktion und Logistik

PW / OR WS 06/07

3-8

3.1.2 Eigenschaften von Linearen Optimierungsproblemen Betrachtet wird ein LOP in Normalform (LOP-N). Es wird davon ausgegangen, dass alle Gleichungen im Gleichungssystem A · x = b linear unabhängig sind (bzw. dass die linear abhängigen Gleichungen des ursprünglichen LOP-N eliminiert wurden), so dass rg A = m < n gilt und das Gleichungssystem bzw. das LOP eine nicht-leere Lösungsmenge besitzt. Für die relevanten Lösungsmengen gelten folgende Eigenschaften: x [1] Die Menge X aller zulässigen Lösungen des 2 LOP-N stellt ein (u.U. unbeschränktes) Polyeder dar und besitzt endlich viele Eckpunkte [2] Die lineare Zielfunktion Z nimmt ihr Optimum, sofern ein solches existiert (was bei unbeschränkter Lösungsmenge X nicht der Fall sein muss), in mindestens einem Eckpunkt des X-Polyeders an. [3] Die Menge X* aller optimalen Lösungen des LOP-N ist ebenfalls konvex.

(2)

(4)

Erfolgsmaximum

(3) (1) (5) x1

Produktion und Logistik

PW / OR WS 06/07

3-9

Begriff der Basislösung: ¾ Eine Lösung x ∈ X heißt Basislösung des LOP-N, wenn p = n – m der Variablen xi gleich Null sind und für die zu den restlichen m Variablen xj gehörenden Spaltenvektoren aj lineare Unabhängigkeit vorliegt. ¾ Die gleich Null gesetzten Variablen xi werden als Nichtbasisvariablen (NBV), die anderen Variablen xj als Basisvariablen (BV) bezeichnet. ¾ Die Menge aller Basisvariablen xj einer Basislösung nennt man Basis. ¾ Eine Basislösung, die alle Nichtnegativitätsbedingungen erfüllt (d.h. xj ≥ 0 für j ∈ Basis) heißt zulässige Basislösung. Eigenschaften von Basislösungen: [1] Eine Lösung x ∈ X ist genau dann eine zulässige Basislösung eines LOP-N, wenn sie einen Eckpunkt des X-Polyeders darstellt. [2] Jeder Eckpunkt der Menge der zulässigen Lösungen X eines LOP-N entspricht mindestens einer zulässigen Basislösung. Konsequenz der LOP-Eigenschaften: ¾ Bei der Suche nach der optimalen Lösung x* (bzw. der Menge der optimalen Lösungen X*) eines LOP-N kann man sich auf die Untersuchung der Eckpunkte des zulässigen Bereichs X beschränken. ¾ Unter der Menge der optimalen Lösungen X* befindet sich mindestens eine zulässige Basislösung.

Produktion und Logistik

PW / OR WS 06/07

3-10

LOP-Beispiel Lederlotte : Normalform LOP-N und Basislösungen (zunächst beschränkt auf Restriktionen (1)-(3)) Maximiere Z(x1 ,..., x 5 ) = 60x1 + 120x 2 u. d. N. 50x1 + 50x 2 + x 3 40x1 + 15x 2 + x4 0,15x1 + 0,4x 2 + x5 x1 ,..., x 5

= 5000 (NB1) = 3000 (NB2) =

30 (NB3)

≥ 0

Alle zulässigen Basislösungen sind aus der folgenden Tabelle ersichtlich. Jeder Eckpunkt wird dabei durch die Basisvariablen (BV) und Nichtbasisvariablen (NBV) beschrieben.

Eckpunkt A = ( 0; 0) B = ( 0; 75) C = (40; 60) D = (60; 40) E = (75; 0)

BV NBV Basislösung (x1,...,x5) x3,x4,x5 x1,x2 ( 0; 0; 5000; 3000; 30) x2,x3,x4 x1,x5 ( 0; 75; 1250; 1875; 0) 0; 500; 0) x1,x2,x4 x3,x5 (40; 60; 0; 0; 5) x1,x2,x5 x3,x4 (60; 40; 0; 18,75) x1,x3,x5 x2,x4 (75; 0; 1250;

(NB2)

•B •C (NB3)

•D

(NB1)

•A

•E

Produktion und Logistik

PW / OR WS 06/07

3-11

3.2 Der Simplex-Algorithmus 3.2.1 Der primale Simplex-Algorithmus Bedingung für die Anwendung des primalen Simplex-Algorithmus zur Lösung eines LOP ist, dass eine bekannte zulässige Basislösung existiert. Wenn der Beschränkungsvektor b des LOP nur nicht-negative Werte enthält (d.h. b ≥ 0), besteht eine zulässige Basislösung immer darin, dass die Schlupfvariablen als BV und Strukturvariablen des LOP als NBV gewählt werden. Der Simplex-Algorithmus besteht in der systematischen Lösung des LOP durch iteratives Absuchen jeweils benachbarter Eckpunkte des polyedrischen Lösungsbereichs X so lange, bis keine Lösungsverbesserung mehr erzielbar ist. Jedes Fortschreiten von Ecke zu Ecke im Rahmen der Iterationen erfolgt, indem jeweils genau eine NBV neu in die Basis aufgenommen und dafür genau eine bisherige BV aus der Basis eliminiert wird (Basistausch).

Produktion und Logistik

PW / OR WS 06/07

3-12

Die zugehörigen Rechenoperationen lassen sich (von Hand) mit Hilfe des sog. Simplextableaus durchführen, das im ersten Lösungsschritt die Koeffizienten des LOP-N (in kanonischer Form) enthält. BV

x n − m+1 # xn Z Bedeutung der Z-Zeile:

x1

NBV " x n−m

BV xn+ m−1 "

xn

bi

1

"

0

a m1 " a m,n − m

# 0

% "

# 1

b1 # bm

− c1

0

"

0

Z-Wert

a11 #

" a1,n − m # − c n−m

Z - c1·x1 - … - cn-m · xn-m = (aktueller) Z-Wert

Produktion und Logistik

PW / OR WS 06/07

3-13

Beispiel Lederlotte : Simplexalgorithmus bei bekannter zulässiger Basislösung Wählt man die Schlupfvariablen als Basisvariablen und die Variablen x1 und x2 als Nichtbasisvariablen, so erhält man als erste zulässige Basislösung: x3 = 5000, x4 = 3000, x5 = 30, x1 = x2 = 0 mit Z=0 Diese ist durch Isolierung der Basisvariablen in den jeweiligen Nebenbedingungen auch wie folgt darstellbar: x 3 = 5000 − 50x1 − 50x 2

x 4 = 3000 − x5 = 30 − Z = 0 +

40x1 3 x 20 1 60x1

− 15x 2 2 x − 5 2 + 120x 2

Zweite zulässige Basislösung: Man erhält sie durch Einsetzen von x2 = 75 – 3/8 x1 – 5/2 x5 in die Gleichungen der ersten zulässigen Basislösung: x 3 = 1250 − 125 4 x1 + 125x 5

x4

= 1875 −

x2 = 75 − Z = 9000 +

275

8

x1

x1 15x1 3

8

+

75

2

x5

5 x − 2 5 − 300x 5

Dritte zulässige Basislösung: Man erhält sie durch Einsetzen von x1 = 40 – 4/125 x3 + 4 x5 in die Gleichungen der ersten zulässigen Basislösung: x1 = 40 − 4125 x 3 + 4x 5

x4

=

500 +

11 10

x3

− 100x 5

x2 = 60 + 3 250 x 3 − 4x 5 Z = 9600 − 12 25 x 3 − 240x 5 Diese Basislösung mit x1 = 40, x2 = 60, x4 = 500, x3 = x5 = 0, Z=9600 ist optimal (eine Erhöhung von x3 bzw. x5 würde zu einer Verminderung des Gewinns führen).

Produktion und Logistik

PW / OR WS 06/07

3-14

Iterationsschritte des primalen Simplex-Algorithmus: [1] Wahl der Pivotspalte t

Suche Spalte t mit

(→ neu aufzunehmende BV)

ct = min { c j | c j < 0 } j

(kleinster Wert in Z-Zeile)

⇒ Die zu Spalte t zugehörige NBV wird in die Basis aufgenommen! Wenn für alle j gilt: cj ≥ 0 , dann ist die aktuelle Basislösung optimal und das Verfahren kann abgebrochen werden. [2] Wahl der Pivotzeile s

Suche Zeile s mit

(→ zu eliminierende BV)

⎧⎪ bi bs = min ⎨ i ast ⎩⎪ ait

⎫⎪ ait > 0 ⎬ ⎭⎪

(kleinster Quotient)

⇒ Die zu Zeile s zugehörige BV wird aus der Basis entfernt! Das zu Pivotzeile s und Pivotspalte t gehörende Element ast heißt Pivotelement. Wenn für alle i gilt: ait ≤ 0 , so besitzt das LOP keine optimale Lösung (der Lösungsbereich X muss unbeschränkt sein) und das Verfahren muss abgebrochen werden. [3] Transformation des Simplextableaus Das LOP wird für die neue Basis nach Variablentausch in kanonische Form gebracht, indem durch lineare Transformationen des Gleichungssystems unter der neuen BV ein Einheitsvektor mit ast = 1 geschaffen wird.

Produktion und Logistik

PW / OR WS 06/07

3-15

Regeln zur Umformung des Simplextableaus im Rahmen von Schritt [3] Alt Alt Alt Gegeben: bisherige Werte aij , bi , c j

mit i : Zeilenindex und j : Spaltenindex

Alt Alt sowie das Pivotelement a st und der Zielfunktionswert Z-Wert

Gesucht:

neue Werte:

aijNeu , biNeu , c Neu , Z-Wert Neu j

Neu (1) ast =1

(3)

(5)

(7)

a

Neu sj

Neu ij

a

c

Neu j

=

(2)

asjAlt

für alle j ≠ t

astAlt

Alt ij

=a

=c

Alt j

(4)

aitNeu = 0

Neu s

b

für alle i ≠ s

bsAlt = Alt a st

aitAlt Alt aitAlt Alt Neu Alt − Alt ⋅ asj für alle i ≠ s und j ≠ t (6) bi = bi − Alt ⋅ bs für alle i ≠ s ast ast

−

asjAlt astAlt

Alt t

⋅c

für alle j

(8)

Z-Wert

Neu

= Z-Wert

Alt

bsAlt Alt − Alt ⋅ ct ast

Produktion und Logistik

PW / OR WS 06/07

3-16

LOP-Beispiel LederLotte: Der primale Simplexalgorithmus Der Verfahrensablauf kann anhand der folgenden Tabelle nachvollzogen werden. Das jeweilige Pivotelement ist durch eckige Klammern hervorgehoben. Fehlende Eintragungen besitzen den Wert 0. x2 x3 BV x1 x3 50 50 1 x4 40 15 3 x5 /20 [2/5] Z -60 -120 0 x3 [125/4] 1 x4 275/8 3 x2 /8 1 Z -15 0 0 4 x1 1 /125 x4 -11/10 x2 1 -3/250 12 Z 0 0 /25

x4

x5

1 0 1 0 1 0

1 0 -125 -75/2 5 /2 300 -4 100 4 240

bi 5000 3000 30 0 1250 1875 75 9000 40 500 60 9600

Erste Basislösung : x3 = 5000, x4 = 3000, x5 = 30, x1 = x2 = 0, Z=0

Zweite Basislösung : x2 = 75, x3 = 1250, x4 = 1875,

x1 = x5 = 0, Z=9000

Optimale Basislösung : x1 = 40, x2 = 60, x4 = 500,

x3 = x5 = 0, Z = 9600

Produktion und Logistik

PW / OR WS 06/07

3-17

3.2.2 Der duale Simplex-Algorithmus Für den Fall, dass keine zulässige Basislösung bekannt ist (z.B. negative Elemente in b), lässt sich durch den dualen Simplex-Algorithmus, ausgehend von einer bekannten unzulässigen Basislösung, iterativ eine zulässige Basislösung finden. Als (unzulässige) Startlösung kann man z.B. die Basislösung mit Schlupfvariablen als BV und Strukturvariablen als NBV wählen. Iterationsschritte des dualen Simplex-Algorithmus

[1] Wahl der Pivotzeile s (→ zu eliminierende BV)

{ bi | bi < 0 } Suche Zeile s mit bs = min i

(„größte“ Unzulässigkeit)

⇒ Die zu Zeile s zugehörige BV wird aus der Basis entfernt! Wenn für alle i gilt: bi ≥ 0, dann kann zum primalen Simplex-Algorithmus übergegangen werden. [2] Wahl der Pivotspalte t

(→ neu aufzunehmende BV)

⎫⎪ ⎧⎪ c j ct a = max < 0 ⎬ ⎨ sj Suche Spalte t mit a j ⎪⎭ ⎪⎩ a sj st

(kleinste Z-Verschlechterung)

⇒ Die zu Spalte t zugehörige BV wird in die Basis aufgenommen! Wenn für alle j gilt: asj ≥ 0, dann existiert keine zulässige Basislösung [3] Transformation des Simplextableaus wie beim primalen Simplex-Algorithmus

Produktion und Logistik

PW / OR WS 06/07

3-18

LOP-Beispiel LederLotte : Der duale Simplexalgorithmus Unter Berücksichtigung der Mindestabsatzmengen ist das folgende LOP zu lösen: max Z(x1,x2) = 60x1 + 120x2 u. d. N.:

x2

50x1 + 50x 2 ≤ 5000

(1)

40x1 + 15x 2 ≤ 3000

(2)

0,15x1 + 0, 4x 2 ≤ 30

(3)

≥ 50

(4)

x 2 ≥ 10

(5)

x1

(2)

(4)

(3) (1) (5) x1

Produktion und Logistik

PW / OR WS 06/07

Das erste Tableau mit nicht zulässiger Basislösung lautet wie folgt: BV x3 x4 x5 x6 x7 Z

x2 50 15 2 /5

x3 x4 x5 x6 x7 bi 1 5000 1 3000 1 30 1 -50 -1 1 -10 -120 0 0 0 0 0 0

x1 50 40 3 /20 [-1] -60

Startlösung: x3 = 5000, x4 = 3000, x5 = 30, x6 = -50, x7 = -10, x1 = x2 = 0, Z=0

Wir wenden den dualen Simplexalgorithmus auf das obige Beispiel an und erhalten: BV x7 x4 x5 x1 x2 Z

x1 x2

1 1

x3 x4 x5 /50 3 - /10 1 -2/250 1 1

1

/50 12 /5

0

0

x6 1 25 -1/4 -1 1 60

x7 bi 1 40 250 5 /2 50 50 9000

Optimale Basislösung: x1 = 50, x2 = 50, x4 = 250, x5 = 5/2, x7 = 40, x3 = x6 = 0, Z=9000

3-19

Produktion und Logistik

BV x3 x4 x5 x1 x7 Z

x1

1

x2 50 15 2 /5

x3 x4 x5 1 1 1

[-1] -120

0

0

0

PW / OR WS 06/07

x6 x7 50 40 3 /20 -1 1 -60 0

bi 2500 1000 45 /2 50 -10 3000

3-20

„Erste“ Basislösung:

x1 = 50, x3 = 2500, x4 = 1000, x5 = 45/2, x7 = -10, x2 = x6 = 0, Z=3000

Das Tableau enthält noch immer keine zulässige Basislösung; nach einer weiteren Iteration mit dem dualen Simplexalgorithmus ergibt sich: BV x3 x4 x5 x1 x2 Z

x1 x2 x3 x4 x5 x6 x7 bi 1 50 [50] 2000 1 40 15 850 3 2 37 1 /20 /5 /2 1 -1 50 1 -1 10 0 0 0 -60 -120 4200

„Zweite“ Basislösung:

x1 = 50, x2 = 10, x3 = 2000, x4 = 850, x5 = 37/2, x6 = x7 = 0, Z=4200

Das Tableau enthält eine zulässige, aber noch nicht optimale Basislösung; nach einer weiteren Iteration mit dem primalen Simplexalgorithmus ergibt sich: BV x7 x4 x5 x1 x2 Z

x1 x2

1 1

x3 x4 x5 /50 3 - /10 1 -2/250 1 1

1

/50 12 /5

0

0

x6 1 25 -1/4 -1 1 60

x7 bi 1 40 250 5 /2 50 50 9000

Optimale Basislösung:

x1 = 50, x2 = 50, x4 = 250, x5 = 5/2, x7 = 40, x3 = x6 = 0, Z=9000

Produktion und Logistik

PW / OR WS 06/07

3.2.3 Interpretation der LOP-Lösung und Sonderfälle Interpretation der Ergebnisse im Schlusstableau ¾ Ergebnisse in der b-Spalte → für Strukturvariable : Lösungswerte der Entscheidungsvariablen → für Schlupfvariable : nicht ausgeschöpfte Restriktionseinheiten ¾ Ergebnisse in der Z-Zeile → für Strukturvariable : Schattenpreis der Variablenbeschränkung → für Schlupfvariable : Schattenpreis der Restriktionseinheit LOP-Beispiel LederLotte : Ergebnisinterpretation BV x7 x4 x5 x1 x2 Z

x1 x2

1 1

x3 x4 x5 /50 3 - /10 1 -2/250 1 1

1

/50 12 /5

0

0

x6 1 25 -1/4 -1 1 60

x7 bi 1 40 250 5 /2 50 50 9000

Optimale Basislösung:

x1 = 50, x2 = 50, x4 = 250, x5 = 5/2, x7 = 40, x3 = x6 = 0, Z=9000

3-21

Produktion und Logistik

PW / OR WS 06/07

3-22

Sonderfälle bei LOP-Lösung ¾ In Schritt 2 des dualen Simplexalgorithmus gilt für alle Elemente j der Pivotzeile s: asj ≥ 0. ⇒ Das LOP hat keine zulässige Lösung! ¾ In Schritt 2 des primalen Simplexalgorithmus gilt für alle Elemente i der Pivotspalte t: ait ≤ 0 ⇒ Das LOP hat keine optimale Lösung! ¾ Im Simplextableau ergibt sich, dass eine NBV einen Schattenpreis von Null besitzt. ⇒ Das LOP besitzt mehrere gleich gute Basislösungen! ¾ Im Simplextableau ergibt sich, dass eine BV einen Wert von Null besitzt. ⇒ Der Lösungsbereich X des LOP‘s besitzt überbestimmte Eckpunkte !

Produktion und Logistik

PW / OR WS 06/07

3-23

Sonderfälle bei LOP-Lösung: Graphische Beispiele • keine zulässige Lösung • keine optimale Lösung x2

x2

X X=∅

x1

x1 •

x2

mehrere gleich gute Lösungen

X

•

x2

überbestimmte Lösungen

X Z x1

x1

Produktion und Logistik

PW / OR WS 06/07

3-24

3.3 Dualität Zu jedem LOP-S mit Max-ZF und gegebenen Problemdaten A, b und c existiert ein korrespondierendes duales LOP mit Min-ZF und denselben Problemdaten, welches eine äquivalente Lösung hat. Das Ausgangsproblem nennt man das primale Problem, das korrespondierende Problem heißt duales Problem. Das mit dem dualen Problem korrespondierende duale Problem ist wiederum das primale Problem. Der formale Zusammenhang zwischen primalem und dualem LOP stellt sich wie folgt dar: Primales LOP

Duales LOP

Max Z(x) = cT ⋅ x

Min ZD(w) = bT ⋅ w

u. d. N

A⋅x≤b x≥0

mit c , x ∈ Rp

,

b , w ∈ Rm

AT w ≥ c w≥0

u. d. N.

,

Am,p ,

ATp,m

Produktion und Logistik

PW / OR WS 06/07

3-25

Mit jeder Nebenbedingung des primalen Problems korrespondiert genau eine Variable des dualen Problems (sog. Dualvariable), so dass das duale LOP gerade m Strukturvariable wi (i = 1, ... , m) besitzt. Mit jeder Strukturvariablen xj (j = 1, ... , p) des primalen Problems korrespondiert genau eine Nebenbedingung des dualen Problems, so dass das duale LOP gerade über p Nebenbedingungen verfügt. Die Ungleichheitsbeziehungen des dualen Problems sind umgekehrt zu denjenigen des primalen Problems. Für die zulässigen Lösungen des primalen und dualen LOP gilt der folgende Einschließungssatz:

Z(x) ≤ Z(x*) = ZD(w*) ≤ ZD(w) Ist der Zielfunktionswert des primalen Problems nicht nach oben beschränkt (so dass keine optimale Lösung existiert), so besitzt das duale Problem keine zulässige Lösung und umgekehrt.

Produktion und Logistik

PW / OR WS 06/07

3-26

Bringt man primales und duales LOP-S durch die Einführung von Schlupfvariablen jeweils in Normalform eines LOP-N mit folgenden Variablen

primales LOP duales LOP

Strukturvariable x1, ... , xp w1, ... , wm

Schlupfvariable xp+1 , ... , xp+m wm+1 , ... , wm+p

so gelten im Optimum folgende Bedingungen (sog. komplementärer Schlupf): x *j ⋅ w m* + j = 0 für j = 1, ... , p

wi* ⋅ x *p +i

= 0 für i = 1, ... , m

Generell gilt folgender Zusammenhang im Optimum: ¾ Die Schlupfvariablen des primalen LOP korrespondieren mit den Strukturvariablen des dualen LOP und umgekehrt. ¾ Im Optimaltableau des primalen LOP liegen in Form der Schattenpreise der Restriktionen auch die optimalen Werte der Strukturvariablen des dualen LOP vor. ¾ Umgekehrtes gilt für das Optimaltableau des dualen LOP.

Ergebnis: Zur Lösung eines vorgegebenen LOP kann man sowohl auf die Formulierung des primalen wie des dualen Problems zurückgreifen. Zweckmäßigerweise geht man von derjenigen Formulierung aus, die sich numerisch am einfachsten lösen lässt.

Produktion und Logistik

PW / OR WS 06/07

3-27

Dualität: Graphisches Beispiel Max Z(x1,x2) = x1 + 2x2 ≤ 10 ≤ 6 ≥ 0

2x1 + x2 x2 x 1, x 2

Min ZD(w1,w2) = 10w1 + 6w2

[w1] [w2]

≥ 1 [x1] ≥ 2 [x2] ≥ 0

2w1 w1 + w 2 w1, w2

x2

w2

10

2 x1* = 2, x2* = 6

w1* = 0,5

6

w2* = 1,5

1 Z* = 14

ZD* = 14

0

5

10

x1

0

1

2

w1

Produktion und Logistik

PW / OR WS 06/07

3-28

Dualität: Ökonomische Bedeutung

Primales Problem:

Wähle bei gegebenen Produktdeckungsbeiträgen die Produktmengen so, dass der Gesamtdeckungsbeitrag maximiert wird, wobei der Ressourcenverbrauch die vorgegebenen Mengen je Ressource nicht übersteigen darf!

Duales Problem:

Wähle bei gegebenen Ressourcenmengen deren Schattenpreise (Gewinnbeiträge der Ressourcen) so, dass die Gesamtopportunitätskosten (Gesamtwert aller verbrauchten Ressourcen) minimiert werden, wobei die produkt-spezifischen Opportunitätskosten (Gewinnbeiträge der Ressourcen pro produzierter Produkteinheit) die jeweiligen Produktdeckungsbeiträge übersteigen müssen!

Produktion und Logistik

PW / OR WS 06/07

3-29

Dualität am Beispiel Lederlotte : (ohne Mindestabsatz)

Primales LOP Max Z(x1 , x 2 ) = 60x1 + 120x 2 u.d.N. 50x1 + 40x1 +

50x 2 15x 2

0,15x1 + 0,4x 2

≤ 5000 [w1 ] ≤ 3000 [w 2 ] ≤

30 [w 3 ]

Duales LOP Min ZD(w1 , w 2 , w 3 ) = 5000w1 + 3000w 2 + 30w 3 u.d.N. 50w1 + 40w 2

+ 0,15w 3 ≥

50w1 + 15w 2

+

60 [x1 ]

0,4w 3 ≥ 120 [x 2 ] w1 , w 2 , w 3 ≥ 0

x1 , x 2 ≥ 0

Ausgangstableau: BV x1 x2 x3 x4 x5 bi x3 50 50 1 5000 x4 40 15 1 3000 x5 3/20 2/5 1 30 Z -60 -120 0 0 0 0

Ausgangstableau: BV w1 w2 w3 w4 w5 bi w4 -50 -40 -3/20 1 -60 2 w5 -50 -15 - /5 1 -120 -ZD 5000 3000 30 0 0 0

Produktion und Logistik

PW / OR WS 06/07

Optimaltableau: BV x1 x2 x3 x4 x5 bi 4 x1 1 /125 -4 40 x4 -11/10 1 100 500 x2 1 -3/250 4 60 Z 0 0 12/25 0 240 9600

Optimaltableau: BV w1 w2 w3 w4 w5 bi w1 1 11/10 -4/125 3/250 12/25 w3 -100 1 4 -4 240 -ZD 0 500 0 40 60 -9600

Korrespondenzen: Z( x* ) = ZD( w* ) = 9600 x1* x*2

= SP(w 4 ) = = SP(w 5 ) =

w1*

=

SP(x 3 )

= 12 / 25

w *2 w *3

= =

SP(x 4 ) SP(x 5 )

= =

SP : Schattenpreis

40 60 0 240

⎫ ⎪ ⎪⎪ ⎬ ⎪ ⎪ ⎪⎭

x1* ⋅ w *4 x*2 ⋅ w *5

= 0 = 0

w1* ⋅ x*3

= 0

w *2 ⋅ x*4 w *3 ⋅ x*5

= 0 = 0

3-30

Produktion und Logistik

PW / OR WS 06/07

3-31

3.4 Sensitivitätsanalyse Unter Sensitivitätsanalyse versteht man die Untersuchung, wie und inwieweit die optimale Lösung eines LOP auf Veränderungen in den Ausgangsdaten des Problems reagiert. Damit lassen sich die Auswirkungen von Datenänderungen oder Fehleinschätzung von Daten auf die LOP-Lösung analysieren. Im Weiteren wird folgende Notation benutzt: ¾ aij , bi , cj

:

Daten (Koeffizienten) des Ausgangsproblems

¾ a0ij , b0i , c0j

:

Daten (Koeffizienten) im Optimaltableau

Die Fragestellung der Sensitivitätsanalyse lautet: In welchem Intervall können die einzelnen Koeffizienten des Ausgangsproblems (aij , bi , cj) schwanken, ohne dass die Struktur der optimalen Basis bei Lösung des Problems wechselt. Die weiteren Ausführungen beschränken sich auf die Analyse der Koeffizienten in b und c.

Produktion und Logistik

PW / OR WS 06/07

3-32

3.4.1 Sensitivität bzgl. der Restriktionskoeffizienten in b Aufgabe: Ermittlung der höchstzulässigen Veränderung der Restriktionskoeffizienten bi (i = 1, ..., m) nach unten ( λ i ) und nach oben ( λ i ) und damit Ermittlung des zulässigen Schwankungsintervalls ⎡⎣bi − λ i , bi + λ i ⎤⎦ ohne Basiswechsel.

Hinweis: Eine Veränderung des i-ten Restriktionskoeffizienten bi beeinflusst die zugehörige Schlupfvariable xq (mit q =p+i) der i-ten Nebenbedingung. Fall [1] :

x q ist BV

⇒

Fall [2] :

λ i = xq

und

⇒

λi = ∞

x q ist NBV

⇒

⎧⎪ ∞ λi = ⎨ 0 bk0 / akq0 | akq >0 ⎪⎩min k

{

wenn alle

}

akq0 ≤ 0

sonst

und

⇒

⎧⎪ ∞ λi = ⎨ 0 −bk0 / akq0 | akq <0 ⎪⎩min k

{

}

wenn alle sonst

akq0 ≥ 0

Produktion und Logistik

PW / OR WS 06/07

3-33

3.4.2 Sensitivität bzgl. der ZF-Koeffizienten in c Aufgabe: Ermittlung der höchstzulässigen Veränderung der ZF-Koeffizienten cj (j = 1,..., p) nach unten ( v j ) und nach oben ( v j ) und damit des zulässigen Schwankungsintervalls ⎡⎣c j − v j , c j + v j ⎤⎦ .

Hinweis: Eine Veränderung des j-ten ZF Koeffizienten cj beeinflusst die zugehörige Strukturvariable in der Zielfunktion. Fall [1] :

x j ist NBV

⇒

Fall [2] :

⇒

v j = c 0j

⎧ ∞ ⎪ vj = ⎨ ck0 / a 0jk | a 0jk > 0 ⎪⎩min k≠ j

wenn alle

vj = ∞

und

x j ist BV

⇒

{

}

a 0jk ≤ 0 mit k ≠ j

sonst

und

⎧ wenn alle a 0jk ≥ 0 mit k ≠ j ∞ ⎪ ⇒ v j = ⎨min −c 0 / a 0 | a 0 < 0 sonst jk jk k ⎪⎩ k ≠ j ~ mit j : Nummer der Zeile im Optimaltableau, in der die BV xj steht

{

}

Produktion und Logistik

PW / OR WS 06/07

3-34

Sensitivitätsanalyse am Beispiel LederLotte (ohne Mindestabsatz) Wir wollen die optimale Lösung des Problems hinsichtlich ihrer Reaktion auf Datenänderungen untersuchen. Hierzu sei das Problem nochmals graphisch veranschaulicht und Ausgangs- und Optimaltableau angegeben. Max Z( x1 , x2 ) = 60 x1 + 120 x2 Ausgangstableau: BV x1 x2 x3 x4 x5 bi x3 50 50 1 5000 x4 40 15 1 3000 (NB2) x5 3/20 2/5 1 30 •B Z -60 -120 0 0 0 0 •C Optimaltableau: (NB3) D • BV x1 x2 x3 x4 x5 bi 4 x1 1 /125 -4 40 11 (NB1) x4 - /10 1 100 500 •A •E x2 1 -3/250 4 60 Z

0 0

12

/25 0 240 9600 Optimale Basislösung (Punkt C) x1 = 40, x2 = 60, x4 = 500, x3 = x5 = 0, Z=960

Produktion und Logistik

PW / OR WS 06/07

3-35

Wir erhalten • in Restriktion 1 (x3 ist Nichtbasisvariable): λ1 = 1250 , λ1 = 5000 /11 Reduziert man b1 um mehr als λ1 = 1250 , so würde x5 für x1 in die Basis gelangen; erhöht man b1 um mehr als λ1 = 5000 /11 , so würde x3 für x4 in die Basis kommen. • in Restriktion 2 (x4 ist Basisvariable): λ 2 = 500 , λ 2 = ∞ • in Restriktion 3 (x5 ist Nichtbasisvariable): λ 3 = 5 , λ 3 = 10 Reduziert man b3 um mehr als λ 3 = 5 , so würde x3 für x4 in die Basis gelangen; erhöht man b3 um mehr als λ 3 = 10 , so würde x5 für x1 in die Basis kommen. Für das Beispiel LederLotte erhält man als Spielraum für die Zielfunktionskoeffizienten der Strukturvariablen x1 und x2 (beide sind in der optimalen Lösung Basisvariablen): • Für c1: ν1 = 15 , ν1 = 60 . • Für c2: ν 2 = 60 , ν2 = 40 .

Produktion und Logistik

PW / OR WS 06/07

3-36

3.5 Lineare Optimierungsproblem mit spezieller Struktur Jedes LOP lässt sich prinzipiell mit dem Simplex-Algorithmus lösen. Im Einzelnen hängt der numerische Lösungsaufwand (Anzahl der Iterationen) ab von • der Anzahl der Strukturvariablen (p), • der Anzahl der Nebenbedingungen (m), • der Anteil der Koeffizienten aij ungleich Null (Besetzungsdichte von A). Spezielle Lösungsverfahren für Spezielle LOPs • Es gibt spezielle LOPs, die eine spezifische Problemstruktur aufweisen, welche die Lösbarkeit dieser Probleme erleichtert. Für solche speziellen Probleme lassen sich oft spezielle Lösungsalgorithmen entwickeln, die noch wesentlich schneller sind als der (immer mögliche) Einsatz des Simplex-Algorithmus. • Drei dieser speziellen LOPs sind das Klassische Transportproblem, das Zweistufige Transportproblem und das Lineare Zuordnungsproblem.

Produktion und Logistik

PW / OR WS 06/07

3.5.1 Das Klassische Transportproblem Problemstellung Es gibt m Angebotsorte, in denen jeweils ai (i = 1, ..., m) ME eines bestimmten Gutes verfügbar sind. Weiter gibt es n Nachfrageorte, die jeweils bj (j = 1 ,..., n) ME diese Gutes benötigen. Das Gesamtangebot an Gütern reicht gerade zur Deckung der Gesamtnachfrage aus ∑ a i = ∑ b j . i

j

Die Transportkosten sind proportional zur Transportmenge und betragen für den Transport von Angebotsort i zu Nachfrageort j genau cij GE/ME. Die Aufgabenstellung besteht in der Festlegung, welche Gütermengen von den einzelnen Angebotsorten zu den einzelnen Nachfrageorten zu transportieren sind ( =ˆ Transportplan), so dass alle Bedarfe befriedigt werden und die gesamten Transportkosten minimiert werden. Strukturdarstellung

[Quelle : Domschke/Drexl : Einführung in Operations Research, 5. Aufl., S. 74]

3-37

Produktion und Logistik

PW / OR WS 06/07

3-38

Modellierung: Zur einfacheren Modellierung ist es zweckmäßig, zweifach indizierte Variable zu benutzen, die sich auf je einen Angebotsort und einen Nachfrageort beziehen.

Variable :

xij : Transportmenge von Angebotsort i zu Nachfrageort j m

n

Min Z(x11 , ... , x mn ) = ∑∑ cij ⋅ x ij

Zielfunktion :

(Gesamt-Transportkosten)

i =1 j=1

Nebenbedingungen : (1)

Vollständige Ausschöpfung der Angebotsmengen n

∑x

ij

= ai

j =1

(2)

i = 1, ... , m

Vollständige Befriedigung der Nachfragemengen m

∑x i =1

(3)

für

ij

= bj

für

j = 1, ... , n

Nichtnegativität der Transportmengen xij ≥ 0 für i = 1 ,..., m und j = 1 ,..., n

Die spezielle Struktur der Nebenbedingungen (NB) des TPPs wird anhand eines Beispiels mit zwei Anbietern und drei Nachfragern deutlich erkennbar.

[Quelle : Domschke/Drexl, 5. Aufl., S. 75]

Produktion und Logistik

PW / OR WS 06/07

3-39

Lösung des Klassischen Transportproblems: Die Lösung erfolgt in zwei Phasen:

Phase 1 : Bestimmung einer (guten) zulässigen Basislösung durch ein sog. Eröffnungsverfahren. Phase 2 : Bestimmung der optimalen Basislösung durch ein Optimierungsverfahren bei gegebener zulässiger Lösung. Eröffnungsverfahren: Es existieren verschiedene Eröffnungsverfahren zum klassischen Transportproblem, die sich bezüglich Lösungsgüte und Lösungsaufwand unterscheiden. Ein besonders einfaches Eröffnungsverfahren besteht in der sog. Nordwestecken–Regel. Hierbei werden die Basisvariablen mit Hilfe eines Transporttableaus sukzessiv (von links oben nach rechts unten) ermittelt, indem Angebotsmengen von Angebotsorten jeweils so lange zu Transportmengen in Nachfrageorte zusammengefasst werden, bis Angebots- oder Nachfragemenge ausgeschöpft sind.

Optimierungsverfahren: Es existieren verschiedene Optimierungsverfahren (wie z. B. die sog. MODI-Methode), die -ausgehend von einer zulässigen Basislösung- die spezifische Struktur der Nebenbedingungen ausnutzen und mit weniger Aufwand als beim generellen Simplexverfahren in einer endlichen Zahl von Iterationen auf die optimale Basislösung führen.

Produktion und Logistik

PW / OR WS 06/07

3-40

Beispiel zum Lösungsverfahren Zur Beschreibung der genannten Verfahren und für „Handrechnungen“ ist es vorteilhaft, ein Transporttableau der folgenden Art zu verwenden:

Nordwesteckenregel

[Quelle : Domschke/Drexl, 5. Aufl., S. 76]

Beispiel: Gegeben sei ein Problem mit drei Anbietern, vier Nachfragern, der Angebotsmengen a = (10, 8, 7), den Nachfragemengen b = (6, 5, 8, 6). Mit der Nordwesteckenregel erhalten wir dafür die nebenstehende zulässige Basislösung mit den Basisvariablen x11 = 6, x12 = 4, x22 = 1, x23 = 7, x33 = 1 x34 = 6 (in Kästchen) und Nichtbasisvariablen xij = 0 sonst. [Quelle : Domschke/Drexl, 5. Aufl., S. 77]

Produktion und Logistik

PW / OR WS 06/07

3-41

3.5.2 Das Zweistufige Transportproblem Problemstellung: Das Problem ist identisch mit dem Klassischen Transportproblem (m Angebotsorte mit jeweiligen Angebotsmengen ai und Nachfragemengen bj) bis auf die Erweiterung, dass die Güter an vorgegebenen Orten (Umschlagpunkte) umgeladen werden, um durch Güterbündelung Transportkosten zu sparen.

Zusätzliche Daten : p

cikA

: :

Anzahl der Umschlagpunkte (k=1,…,p) Kosten (GE/ME) für Transport von Angebotsort i zu Umschlagpunkt k

ckjB

:

Kosten (GE/ME) für Transport von Umschlagpunkt k zu Nachfrageort j

Modellierung:

Variable : xikA

:

Transportmenge von Angebotsort i zu Umschlagpunkt k

xkjB

:

Transportmenge von Umschlagpunkt k zu Nachfrageort j

Zielfunktion : A 11

A mp

B p1

B pn

Min Z ( x ,..., x , x ,..., x ) =

m

p

∑∑ c i =1 k =1

A ik

p

n

⋅ x + ∑∑ ckjB ⋅ xkjB A ik

k =1 j =1

Produktion und Logistik

PW / OR WS 06/07

3-42

Nebenbedingungen : (1)

Vollständige Ausschöpfung der Angebotsmengen p

∑x

A ik

= ai

k =1

(2)

∑x

B kj

= bj

k =1

für

j = 1,..., n

Gleichheit von Zu- und Abfluss in den Umschlagpunkten m

n

∑ x =∑ x

für

Nichtnegativität der Transportmengen B xikA ≥ 0 und xkj ≥ 0 für

i = 1,..., m; k = 1,..., p;

i =1

(4)

i = 1,..., m

Vollständige Befriedigung der Nachfragemengen p

(3)

für

A ik

B kj

j =1

Lösung: wie Klassisches Transportproblem (nach Umformung)

k = 1,..., p

j = 1,..., n

Produktion und Logistik

PW / OR WS 06/07

3-43

3.5.3 Das Lineare Zuordnungsproblem Problemstellung: Es gibt n Objekte aus einer Gruppe A, die (ebenfalls) n Objekten aus einer Gruppe B jeweils paarweise zugeordnet werden sollen. Jede Zuordnung eines Objekts i (i = 1, ... , n) aus Gruppe A zu einem Objekt j (j = 1, ... , n) aus Gruppe B ist mit einem spezifischen Erfolgsbeitrag cij verbunden. Die Aufgabenstellung besteht in der Festlegung, wie die Zuordnung zu erfolgen hat, so dass alle Objekte aus beiden Gruppen genau eine paarweise Zuordnung erfahren und dabei der Gesamterfolg aus allen Zuordnungen maximiert wird. Beispiele:

Gruppe A Arbeitnehmer Schulklassen Vorlesungen Gebäude

Gruppe B Tätigkeiten Lehrer Wochenzeiten Betriebsflächen

Erfolgsgrößen Einarbeitungszeit Zufriedenheit Zufriedenheit Transportwege

Produktion und Logistik

PW / OR WS 06/07

3-44

Modellierung: Eine Zuordnungsentscheidung kann durch eine zweifach indizierte Variable (sog. Zuordnungsvariable) beschrieben werden, die als sog. binäre Variable nur zwei Ausprägungen (0 oder 1) hat.

Variable: ⎧1 : wenn Objekt i aus Gruppe A dem Objekt j aus Gruppe B zugeordnet wird x ij = ⎨ sonst ⎩0 : Zielfunktion: n

n

Max Z ( x11 , ... , x nn ) = ∑∑ cij ⋅ xij i =1 j =1

(Gesamt-Zuordnungserfolg)

Nebenbedingungen: (1)

Vollständige Zuordnung aller Objekte aus Gruppe A n

∑x

ij

=1

für

i = 1, ... , n

j =1

(2)

Vollständige Zuordnung aller Objekte aus Gruppe B n

∑x

ij

=1

für

j = 1, ... , n

i =1

(3)

Ganzzahligkeitsbedingungen (hier : Binärbedingungen) für Variable

xij ∈ {0,1} für

i = 1, ... , n

und j =1 , ... , n

Produktion und Logistik

PW / OR WS 06/07

3-45

Hinweis: Wegen der Ganzzahligkeitsbedingungen in (3) stellt das hier formulierte Zuordnungsproblem kein LOP-A dar! Wegen der speziellen Struktur der Nebenbedingungen in (1) und (2) mit Koeffizienten ausschließlich in Form von Null und Eins ist aber eine schwächere Formulierung der Variablenbedingungen in (3) zulässig: (3a)

xij ≥ 0

für i =1 , ... , n

Lösung des Linearen Zuordnungsproblems : Mit den Nebenbedingungen (1), (2) und (3a) entspricht das Lineare Zuordnungsproblem einem Spezialfall des Klassischen Transportproblems mit

m = n, ai = 1 und bj = 1 für alle i und j. Zur Lösung eignen sich damit alle Lösungsverfahren des Transportproblems. Darüber hinaus existieren spezielle Lösungsverfahren des Linearen Zuordnungsproblems, welche die spezifische Struktur der Koeffizienten ausnutzen.

Produktion und Logistik

PW / OR WS 06/07

3-46

Spezielle Struktur der Koeffizienten beim linearen Zuordnungsproblem ¾ Beispiel : n=2 Arbeitskräfte : { A1, A2 } Jobs : { J 1 , J2 }

ZF-Koeffizienten cij : A1 A2

⇒

ZF

:

¾ NB – Struktur

Max Z

=

x11 1

x12 1

1

¾ Lösung : x*21 = 1, x*22 = 0

5·x11 + 8·x12 + 6·x21 + 4·x22

: NB A1 A2 J1 J2

* * x11 = 0 , x12 =1

J1 5 6

⇒ Z * = 14

1

x21

x22

1 1

1 1

RS 1 1 1 1

J2 8 4

Produktion und Logistik

PW / OR WS 06/07

3-47

3.6 Lösung von linearen Optimierungsproblemen in der Praxis Der Simplex-Algorithmus geht auf Georg Dantzig (1947) zurück und ist alternativen Verfahren zur LOP-Lösung (wie der sog. Ellipsoid-Methode oder der projektiven Methode) in praktisch allen relevanten Anwendungsfällen überlegen und bildet die Grundlage für alle kommerziellen Software-Pakete zur Lösung von LOPs. Kleinere Probleme (wie z.B. Übungsaufgaben) lassen sich mit dem Solver in EXCEL lösen. Zur Lösung größerer Probleme aus der Unternehmenspraxis existiert leistungsfähige LOPSoftware wie z.B. X-PRESS oder CPLEX. Mit kommerziellen Software-Paketen lassen sich allgemeine LOPs in der Größenordnung von über einer Millionen Variablen und mehreren Hunderttausend Nebenbedingungen in wenigen Minuten Rechenzeit lösen. Moderne Software zur LOP-Lösung enthält zahlreiche Weiterentwicklungen des StandardSimplex-Algorithmus, z.B. in Form - des sog. revidierten Simplex-Algorithmus - von Methoden der Spaltengenerierung - von sog. Dekompositionsverfahren

Produktion und Logistik

PW / OR WS 06/07

3-48

Fortschritte bei der Lösbarkeit von LOPs • Start in 1947 LOP mit 77 Variablen und 9 Nebenbedingungen → Lösungszeit : 120 Mann-Tage • Laufende Verkürzung von Lösungszeiten - durch verbesserte Algorithmen - durch leistungsfähigere Computer • Durchschnittliche Verbesserungen 1988-2003 - durch Algorithmen : um das 2.360-fache - durch Computer : um das 800-fache → insgesamt : um das 1.900.000-fache • Beispiel : Produktionsplanungs-Modell mit 1.584.000 Variablen, 401.640 Nebenbedingungen und Besetzungsdichte von 1,5 % Lösungszeiten (2,0 GHz P4 und CPLEXSoftware) - 1988 (CPLEX 1.0) : 29,8 Tage → 1x - 1997 (CPLEX 5.0) : 1,5 Stunden → 480 x - 2003 (CPLEX 9.0) : 59 Sekunden → 44.000 x

Produktion und Logistik

PW / OR WS 06/07

Überblick

Vorgehensweise des Simplex-Algorithmus:

Initialisierung:

bekannte zulässige Basislösung

Optimalitätstest:

Ist die augenblickliche Lösung schlechter als die Nachbarlösungen?

Wenn nein | Wenn ja

Iteration:

Ende: Basislösung ist optimal.

Nimm bessere Nachbarlösung als neue Basislösung, „Pivotieren“

Nachbarlösungen sind Lösungen, bei denen exakt eine Variable die Basis verlässt (=0 wird) und eine andere in die Basis aufgenommen wird (>0 wird).

Produktion und Logistik

PW / OR WS 06/07

4 Produktionsmanagement

4-1

Produktion und Logistik

PW / OR WS 06/07

4-2

4.1 Aufgaben des Produktionsmanagements Produktionsmanagement befasst sich mit der Organisation und Gestaltung von Produktionssystemen und der Planung und Kontrolle von Produktionsprozessen zur Erreichung betrieblicher Ziele. 4.1.1 Entscheidungsebenen des Produktionsmanagements Eigenschaften der Entscheidungen • • • •

Planungshorizonte und Realisierungszeiträume Bedeutung für das Gesamtunternehmen Aggregationsgrad der verwendeten Daten verantwortliche Managementebene

Produktion und Logistik

Entscheidungsebenen

PW / OR WS 06/07

4-3

Beispiele • Standortwahl • Festlegung der technologie

Produktions-

• Layoutplanung • Festlegung der Fertigungskapazität

• Aufstellung des Produktionsprogramms • Ermittlung des Materialbedarfs

[Quelle: Günther und Tempelmeier S.26]

Produktion und Logistik

PW / OR WS 06/07

4-4

• Strategisches Produktionsmanagement dient der Schaffung und Sicherung langfristigen Rahmenbedingungen für den Untersuchungserfolg durch grundsätzliche Festlegungen der Ausrichtung des Produktionsbereichs im Hinblick auf Produktfelder, Märkte, Technologien und Organisationsformen. • Taktisches Produktionsmanagement dient dem Aufbau und der Ausgestaltung der produktionswirtschaftlichen Infrastruktur im Rahmen der Dimensionierung, räumlichen Verteilung und inneren Strukturierung der betrieblichen Produktiveinheiten. • Operatives Produktionsmanagement dient der Vorbereitung und Durchführung des Produktionsvollzugs im Rahmen der vorhandenen Infrastruktur durch Festlegung des Produktionsprogramms und des Einsatzes der Produktionsfaktoren nach Art, Menge und Zeit. Die Managementaufgaben richten sich auf verschiedene produktionswirtschaftliche Entscheidungsfelder.

Produktion und Logistik

PW / OR WS 06/07

4-5

Produktionswirtschaftliche Entscheidungsfelder

Produktionsstruktur

Produktionsvollzug

Produkte

Prozesse

Produktfelder

Technologie

Fertigungstiefe

Produkttypen

Materialeinsatz

Märkte

Organisationsform

Kapazität

Hauptprodukte

Personaleinsatz

Produktpolitik

Konfiguration

Standorte

Produktvarianten

Betriebsmitteleinsatz

Potenziale

Produktionsprogramm

Faktoreinsatz

Strategisch – taktische Planung Operative Planung Disposition / Steuerung

Produktion und Logistik

PW / OR WS 06/07

4.1.2 Operatives Produktionsmanagement Das operative Produktionsmanagement befasst Produktionsplanung und -steuerung (PPS).

4-6

sich

mit

den

Aufgaben

der

Aufgaben der Produktionsplanung • Produktionsprogrammplanung ¾ Langfristige Programmplanung Langfristige Festlegung des Fertigungsprogramms an Endprodukten nach Produkttyp und -menge (auf 1-2 Jahre) ¾ Beschäftigungsglättung und Hauptproduktionsprogrammplanung Mittelfristige Festlegung der (monatlichen / wöchentlichen) Produktionsmengen aller Produkttypen/Hauptprodukte (auf 1-12 Monate) ¾ Produktvariantenplanung Kurzfristige Festlegung der (wöchentlichen oder täglichen) Herstellungsmengen einzelner Produktvarianten (auf 1-4 Wochen) Ergebnis: Terminierte Fertigproduktmengen

Produktion und Logistik

PW / OR WS 06/07

4-7

• Mengenplanung ¾ Materialbedarfsplanung Mittelfristige/kurzfristige Festlegung des Bedarfs an selbst erstellten und fremdbezogenen Repetierfaktoren (d.h. Zwischenerzeugnisse und Kaufmaterialien) nach Menge und Zeit (i.d.R. auf Wochenbasis) ¾ Losgrößenplanung Mittelfristige/kurzfristige Zusammenfassung von Materialbedarfen gleicher Erzeugnisse zu größeren Produktions- und Beschaffungslosen. • Termin- und Kapazitätsplanung ¾ Terminplanung Zeitliche Feinplanung der Termine für einzelne Fertigungsaufträge (i.d.R. auf Tagesbasis) ¾ Kapazitätsplanung Zeitliche Einsatzplanung von Personal- und Betriebsmittelkapazitäten unter Planung von Ausgleichsmaßnahmen bei Kapazitätsdisparitäten. Ergebnis von Mengen-, Termin- und Kapazitätsplanung: Terminierte Betriebs- und Beschaffungsaufträge

Produktion und Logistik

PW / OR WS 06/07

4-8

Aufgaben der Produktionssteuerung ¾ Kurzfristige Freigabe von geplanten Fertigungsaufträgen zur operativen Durchführung der Fertigungsprozesse an den Arbeitsplätzen (i.d.R. auf 1-10 Tage) ¾ Laufende Festlegung von detaillierten Fertigungsreihenfolgen und -terminen der freigegebenen Aufträge an den einzelnen Arbeitsplätzen ¾ Laufende Kontrolle der Produktionsdurchführung und Reaktion auf Plan-Ist-Abweichungen

Produktion und Logistik

PW / OR WS 06/07

4-9

4.2 Nachfrageprognosen Grundlage der Produktionsplanung sind Daten über die zukünftige Entwicklung der Nachfrage. Prognoseverfahren versuchen auf Basis von Erfahrungen oder Vergangenheitsdaten diese Entwicklung zu ermitteln. Prognosen sind in der Regel falsch - dies umso stärker, je länger der Prognosehorizont. 4.2.1 Prognoseverfahren • qualitative Verfahren (subjektiv auf Basis von Erfahrungen) - Vertriebsschätzung und Kundenbefragungen: kurz- bis mittelfristig gut - Expertenschätzung: mittel- bis langfristig gut - Delphi-Methode: langfristig gut Einsatz bei fehlenden oder ungeeigneten Vergangenheitsdaten ⇒ Subjektivität, Anreizproblematik, Aufwand • quantitative Verfahren (auf Basis von Vergangenheitsdaten und Extrapolation in die Zukunft) - Kausalprognosen, z.B. Schätzung der Parameter des Produktlebenszyklus mittels einer Regressionsanalyse - univariate Verfahren (Zeitreihenanalyse)

Produktion und Logistik

PW / OR WS 06/07

4-10

4.2.2 Zeitreihenanalyse Beispiel einer Zeitreihe

Nachfrage

Monat 1 Nachfrage 48

2 36

3 49

4 65

5 54

6 60

7 48

8 51

9 62

10 66

2

3

4

5

6

7

8

9

10

70 65 60 55 50 45 40 35 30 1

Monat

Produktion und Logistik

PW / OR WS 06/07

Verfahrensschritte bei Prognosebildung mittels Zeitreihenanalyse (1) Typisierung des Nachfrageverlaufs (2) Spezifizierung eines Prognosemodells (3) Schätzung der unbekannten Modellparameter (4) Modellanwendung : Berechnung der Prognosewerte (5) Beobachtung und Analyse der Prognosegenauigkeit

4-11

Produktion und Logistik

PW / OR WS 06/07

(1) Typisierung des Nachfrageverlaufs

[Quelle: Thonemann S. 53]

4-12

Produktion und Logistik

PW / OR WS 06/07

4-13

(2) Beispiele für Prognosemodelle Annahme Nachfragewerte einzelner Perioden t ( ~y t ) sind stochastische Größen, die vom Zeitverlauf (t) ~ und von unregelmäßigen Zufallsschwankungen Ι abhängen können.

Typen von Zeitreihenverläufen unregelmäßig stark schwankend

regelmäßig

sporadisch

konstant

trendförmig

~ • Konstantes Modell : ~yt = a + Ι

• Trendmodell :

~ ~ yt = a + b ⋅ t + Ι (linearer Trend)

• Saisonmodell :

yt = a + b ⋅ t + St + Ι bzw. (a + b ⋅ t ) ⋅ ( st + Ι )

saisonal

Produktion und Logistik

PW / OR WS 06/07

4-14

~ (3) Schätzung der Modellparameter im konstanten Modell ~yt = a + Ι Daten : Schätzzeitpunkt : t vergangene Nachfragewerte = yt, yt-1, yt-2, ...

Gesucht: Schätzung des Modellparameters a im Zeitpunkt t : aˆ t Mögliche Schätzverfahren • Gleitende Durchschnitte (Moving Average) aˆt =

1 ⋅ ( y t + yt −1 + … + yt − n + 1 ) n

mit Modellparameter : n

• Exponentielle Glättung 1.Ordnung (Single Exponential Smoothing) aˆt = yt(1)

mit

yt(1) = α ⋅ yt + (1 - α ) ⋅ yt(1)−1

mit Modellparameter : 0 < α ≤ 1

Problematik • Wahl des Glättungsparameters α , Empfehlung 0, 05 ≤ α ≤ 0,30 • Ermittlung von Startwerten • Anwendung bei Fehlspezifikation des Modells (4) Berechnung der Prognosewerte im konstanten Modell pt +1 = pt +1 ( y t , y t −1 , y t − 2 , …) = aˆ t Ein-Schritt-Prognose : pt +τ = pt +τ ( yt , yt −1 , yt −2 , …) = aˆ t Mehr-Schritt-Prognosen :

Produktion und Logistik

PW / OR WS 06/07

(5) Beobachtung und Analyse der Prognosegenauigkeit • periodenbezogener Prognosefehler εt ε t = pt − yt • Mittlere absolute Abweichung (MAD):

1 n MAD= ⋅ ∑ ε t n t =1

• Mittlere quadratische Abweichung (MSE): 1 n 2 MSE = ⋅ ∑ ε t n t =1

4-15

Produktion und Logistik

PW / OR WS 06/07

4-16

Beispiel GD mit n = 3 t 0 1 2 3 4 5 6 7 8 9 10 11

yt

ât

48 36 49 65 54 60 48 51 62 66

44,3 50,0 56,0 59,7 54,0 53,0 53,7 59,7

EG mit α = 0,3

pt

εt

εt 2

44,3 50,0 56,0 59,7 54,0 53,0 53,7 59,7

-20,7 -4,0 -4,0 11,7 3,0 -9,0 -12,3

427,1 16,0 16,0 136,1 9,0 81,0 152,1

MAD 9,2

MSE 119,6

ŷt 48,0 48,0 44,4 45,8 51,5 52,3 54,6 52,6 52,1 55,1 58,4

pt

εt

εt 2

45,8 51,5 52,3 54,6 52,6 52,1 55,1 58,4

-19,2 -2,5 -7,7 6,6 1,6 -9,9 -10,9

369,4 6,0 59,6 43,5 2,6 97,4 119,0

MAD 8,3

MSE 99,6

Produktion und Logistik

PW / OR WS 06/07

4-17

4.3 Produktionsprogrammplanung Zentrale Aufgabe der Produktionsprogrammplanung ist die vorausschauende Festlegung der Herstellungsmengen der wesentlichen Endprodukte bzw. Gruppen von Endprodukten eines Unternehmens zur Erzielung eines maximalen Erfolgsbeitrags unter Berücksichtigung von (im Wesentlichen) nicht beeinflussbaren Restriktionen hinsichtlich ¾ der Einsatzmöglichkeiten von Faktoren (Werkstoffe, Betriebsmittel, Personal) und ¾ der Ausbringungsmöglichkeiten von Produkten (durch beschränkte Nachfragen)

Produktion und Logistik

PW / OR WS 06/07

4-18

4.3.1 Langfristige Programmplanung Planungsaufgabe Bestimmung der Gesamtproduktionsmengen aller Produkttypen über einen vorgegebenen Planungszeitraum in der Weise, dass der gesamte Deckungsbeitrag maximiert wird und vorhandene personelle, technische und beschaffungsbezogene Kapazitäten sowie marktbedingte Absatzhöchstgrenzen nicht überschritten werden. Planungsinformationen ¾ Aufteilung des gesamten Endproduktspektrums in (aggregierte) Produkttypen ¾ Langfristige Marktprognosen über zu erwartende Kundennachfragen nach Produkttypen ¾ Daten über die Kapazitäten personeller, technischer und beschaffungsbezogener Ressourcen ¾ Produkttypbezogene Koeffizienten spezifischer Kapazitätsbeanspruchung ¾ Produkttypbezogene Erlös- und Kostendaten

Produktion und Logistik

PW / OR WS 06/07

4-19

Grundmodell zur langfristigen Programmplanung Variable: xk : Gesamtproduktionsmenge von Produkttyp k im Planungszeitraum mit k ∈ K = {Menge aller Produkttypen} Daten: Nk : Nachfrage nach Produkttyp k im Planungszeitraum (in ME) dk : Stückdeckungsbeitrag für Produkttyp k (pro ME) ark : Kapazitätsbeanspruchung von Ressource r für 1 ME von Produkttyp k mit r ∈ R = {Menge der Ressourcentypen} (z. B. Personal, Maschinen, Material) Kr : verfügbare Kapazität für Ressource r im Planungszeitraum Entscheidungsmodell:

D = ∑ d k ⋅ xk

Maximiere

k∈K

u. d. N. (1) (2) (3)

⇒

∑a

rk

xk

≤ Nk

für

k∈K

Nachfragebeschränkungen für alle Produkttypen

⋅ xk

≤ Kr

für

r∈R

Kapazitätsbeschränkungen für alle Ressourcentypen

für

k∈K

Nichtnegativität der Produktionsmengen

k∈K

xk ≥ 0

Typ des Optimierungsproblems :

LOP

Produktion und Logistik

PW / OR WS 06/07

4-20

4.3.2 Beschäftigungsglättung 4.3.2.1 Planungsproblematik bei Beschäftigungsglättung Planungsaufgabe Zeitliche Detaillierung des (vorgegebenen) Produktionsprogramms unter Berücksichtigung von (saisonalen) Schwankungen des Kapazitätsbedarfs und -angebots. Planungsziel Kostenminimale zeitliche Abstimmung von Produktions- und Nachfragemenge (nach Produkttypen) unter Einbeziehung von Produktion auf Lager und von Anpassungsmaßnahmen im Kapazitätsbereich. Planungsinformationen ¾ Zeitlich differenzierte mittelfristige Nachfrageprognosen nach Produkttypen und Teilperioden ¾ Daten zur zeitlichen Verfügbarkeit von Grundkapazitäten personeller, technischer und beschaffungsbezogener Art ¾ Informationen zu Möglichkeit und Grenzen der Heranziehung kurzfristig einsetzbarer Zusatzkapazitäten ¾ Produkttypbezogene Kapazitätsbeanspruchungskoeffizienten ¾ Produkttypbezogene Kosten der Lagerhaltung ¾ Ressourcentypbezogene Kosten der Kapazitätsanpassung

Produktion und Logistik

PW / OR WS 06/07

4-21

Kostenkonflikt bei Beschäftigungsglättung ¾ Kosten der Kapazitätsanpassung bei Synchronisation von Produktion und Nachfrage versus ¾ Kosten der Lagerhaltung bei Emanzipation der Produktion von der Nachfrage Synchronisation von Produktion und Nachfrage

vollständige Emanzipation der Produktion von der Nachfrage

[Quelle : Günther und Tempelmeier S. 152]

[Quelle: Günther und Tempelmeier S. 153]

Produktion und Logistik

PW / OR WS 06/07

4-22

4.3.2.2 Planungsverfahren bei Beschäftigungsglättung Alternative Planungsmethoden ¾ Einfache Anpassung der Produktion an die Nachfrage einzelner Perioden und nachträgliche Prüfung auf kapazitive Realisierbarkeit und Einsatznotwendigkeit von Anpassungsmaßnahmen. ¾ Simultane Produktionsprogrammplanung über alle Berücksichtigung von Nachfrageschwankungen, Kapazitätsanpassungsmöglichkeiten

Perioden unter gleichzeitiger Ressourcenverfügbarkeit und

Produktion und Logistik

PW / OR WS 06/07

Grundmodell zur Beschäftigungsglättung Variablen:

xkt ykt

:

Produktionsmenge von Produkttyp k in Periode t (t = 1, 2 ,..., T)

:

Lagerbestand von Produkttyp k am Ende der Periode t

zrt

:

Inanspruchnahme von Zusatzkapazität des Ressourcentyps r in Periode t mit k ∈ K = Menge der Produkttypen r ∈ R = Menge der Ressourcentypen

Daten:

T

: Planungshorizont

Nkt lk

: Nachfrage nach Produkttyp k in Periode t (in ME)

y ko

: Anfangslagerbestand von Produkttyp k zu Planungsbeginn

ark

: Kapazitätsbeanspruchung von Ressource r durch 1 ME von Produkttyp k

Krtmax

: verfügbare Grundkapazität für Ressource r in Periode t

Zrtmax grt

: maximale Zusatzkapazität für Ressource r in Periode t

(= Anzahl der Teilperioden)

: Lagerkostensatz pro Periode und pro ME des Produkttyps k

: Kosten einer Einheit zusätzlicher Kapazität für Ressource r in Periode t

4-23

Produktion und Logistik

PW / OR WS 06/07

4-24

Entscheidungsmodell :

⇒

Minimiere die Gesamtkosten K aus Lagerhaltung und Kapazitätsanpassung unter Berücksichtigung von Lagerbilanzgleichungen (1), Kapazitätsrestriktionen (2), Zusatzkapazitätsbeschränkungen (3) und Nichtnegativitätsbedingungen (4) T

T

t =1 k∈K

t =1 r∈R

K = ∑ ∑ lk ⋅ ykt + ∑∑ g rt ⋅ zrt

Minimiere u. d. N.

(1) ( 2)

∑a

rk

ykt

=

yk ,t −1 + xkt − N kt

für k ∈ K

und t = 1,..., T

⋅ xkt

≤

K rtmax + zrt

für r ∈ R

und t = 1,..., T

≤ Z rtmax

für r ∈ R

und t = 1,..., T

≥ 0

für k ∈ K , r ∈ R und t = 1,..., T

k∈K

(3)

zrt

(4) xrt , ykt , zrt ⇒

Typ des Optimierungsproblems :

LOP

Produktion und Logistik

PW / OR WS 06/07

4-25

Beispiel zur Beschäftigungsglättung

Problemdaten : Zwei Produkttypen : Zwei Ressourcentypen : Vier Teilperioden :

A B

P

M

k ∈ {A,B} r ∈ {P,M} t = 1 ,..., T = 4

Prognostizierte Nachfrage in Anfangslager- Lagerkostenbestand satz t=1 t=2 t=3 t=4 100 110 90 100 36 4 200 190 210 200 220 4 Produktionskoeffizient für GrundMaximale Kostensatz für A B kapazität Zusatzkapazität Zusatzkapazität 1,0 0,5 160 100 5 0,5

1,0

200

-

-

Produktion und Logistik

PW / OR WS 06/07

4-26

LOP-Modellierung des Beispiels zur Beschäftigungsglättung

Variable :

xAt , xBt , yAt , yBt , zPt Min K =

Zielfunktion :

(t = 1 ,..., 4)

4 ⋅ y A1 + 4 ⋅ y B1

+ 4 ⋅ yA 2 + 4 ⋅ y B2

+ 4 ⋅ y A3 + 4 ⋅ y B3

+ 4 ⋅ yA 4 + 4 ⋅ y B4

+ 5 ⋅ z P1

+ 5 ⋅ z P2

+ 5 ⋅ z P3

+ 5 ⋅ z P4

Nebenbedingungen : = = = =

36 y A1 y A2 y A3

1,0 ⋅ x At 0,5 ⋅ x At

+ +

0,5 ⋅ xBt 1,0 ⋅ xBt

zPt

≤

100

x At , xBt ,

y At ,

y Bt , zPt

y A1 y A2 y A3 y A4

+ + + +

x A1 x A2 x A3 x A4

− − − −

y B1 yB 2 yB 3 yB 4

100 110 90 100

≤ 160 ≤ 200

+

zPt

= 220 + = y B1 + = yB 2 + = yB 3 +

x B1 xB 2 xB 3 xB 4

für t = 1,...,4 für t = 1,...,4 für t = 1,...,4

≥ 0

für t = 1,...,4

− − − −

200 190 210 200

Produktion und Logistik

PW / OR WS 06/07

Optimale Problemlösung : Periode Produktion Lager Produktion Lager ZusatzA A B B kapazität 0 36 220 1 94 30 115 135 0 2 80 0 160 105 0 3 90 0 155 50 7,5 4 100 0 150 0 15 Kapazitätsnutzung Periode Personalkapazität Zusatzkapazität Maschinenkapazität 1 160 0 162 2 160 0 200 3 160 7,5 200 4 160 15 200 Problematik der LOP-Modellierung : ¾ Bedingung der Linearität aller funktionalen Zusammenhänge ¾ Keine direkte Berücksichtigung von Datenunsicherheit ¾ Abhängigkeit von LOP-Software

4-27

Produktion und Logistik

PW / OR WS 06/07

4-28

4.3.2.3 Hauptproduktionsprogrammplanung Planungsaufgabe Zeitliche und produktbezogene Detaillierung des Produktionsprogramms aus der Beschäftigungsglättung durch Verfeinerung der Zeitperioden und durch Disaggregation der Produkttypen in Hauptprodukte Zusammenhang mit Beschäftigungsglättung

[Quelle: Günther und Tempelmeier S. 163]

Alternative Planungsmethoden ¾ Einfache Aufschlüsselung der produkttypbezogenen Planmengen auf Hauptprodukte unter Berücksichtigung kurzfristiger Nachfrageschwankungen. ¾ Simultane Programmplanung unter Beachtung kurzfristiger Nachfrageschwankungen und Berücksichtigung von Beschränkungen der Grund- und Zusatzkapazitäten einzelner Ressourcen analog der Vorgehensweise bei Beschäftigungsglättung (LOP-Modellierung)

Produktion und Logistik

PW / OR WS 06/07

4-29

4.4 Materialbedarfsplanung Planungsaufgabe Festlegung von Art, Menge und Bereitstellungstermin aller Materialien (d. h. selbst erstellte Zwischenprodukte und fremdbezogene Kaufmaterialien), die für die Erstellung des geplanten Hauptproduktionsprogramms benötigt werden. Formen der Materialbedarfsplanung ¾ Verbrauchsorientierte Bedarfsplanung Unabhängige Bedarfsplanung für jedes einzelne Material auf der Basis von Bedarfsprognosen, die aus dem jeweiligen Materialverbrauch der Vergangenheit abgeleitet werden. ¾ Programmorientierte Bedarfsplanung Zusammenhängende Bedarfsplanung für alle Materialien auf Basis des Hauptproduktionsprogramms und unter Berücksichtigung der materialbezogenen Bedarfszusammenhänge auf der Grundlage bekannter Erzeugnisstrukturen Verfahren der programmorientierten Materialbedarfsplanung ¾ Matrizenverfahren auf Basis von Gozinto-Graphen zur Bedarfsrechnung ohne Berücksichtigung von Zeitzusammenhängen ¾ Dispositionsstufenverfahren auf Basis von Stücklisten zur Bedarfsrechnung mit Berücksichtigung von Zeitzusammenhängen

⇒

Gängige Verfahren beziehen sich auf outputseitig determinierte, linear-limitationale Produktionssysteme (= Leontief-Systeme)

Produktion und Logistik

PW / OR WS 06/07

4-30

4.4.1 Matrizenverfahren auf Basis von Gozinto-Graphen Beim Matrizenverfahren wird durch Lösen eines linearen Gleichungssystems unter Verwendung aller in einem sog. Gozinto-Graphen dargestellten Input-Output-Beziehungen in einem Produktionssystem aus vorgegebenen Bedarfen aller Endprodukte die davon abhängigen Bedarfsmengen aller Zwischenprodukte und Kaufmaterialien (originäre Faktoren) abgeleitet. 4.4.1.1 Der Gozinto-Graph Der Gozinto-Graph ist ein auf den Fall outputseitig determinierter Produktion bezogener Input/Output-Graph, in dem auf gesonderte Darstellung von Grundaktivitäten verzichtet wird.

Abstrakter Input/Output-Graph zu den Beispielen der LederLotte [Quelle: Dyckhoff, S. 90]

Gozinto-Graph der Lederwarenherstellung [Quelle : Dyckhoff, S. 271]

Produktion und Logistik

PW / OR WS 06/07

4-31

Die gerichteten Kanten des Gozinto-Graphen beschreiben die direkten Input-OutputBeziehungen zwischen den Erzeugnissen in einem Produktionssystem. Die Kantenbewertungen (= Produktionskoeffizienten) beinhalten den Mengenverbrauch an Inputerzeugnissen bezogen auf eine Mengeneinheit des betreffenden Outputerzeugnisses. Der Gozinto-Graph beschreibt damit die komplette Erzeugnisstruktur eines ein- oder mehrstufigen Produktionssystems bzw. einzelner Subsysteme. Alle Strukturtypen von Materialzusammenhängen (= Erzeugnisstrukturtypen) lassen sich durch Gozinto-Graphen darstellen: ¾ glatt (= linear) ¾ konvergierend

¾ divergierend ¾ umgruppierend (= generell)

Gozintographendarstellungen für lineare, konvergierende, divergierende und generelles Erzeugnisstrukturen [Quelle: Günther/Tempelmeier : Produktion und Logistik, 4. Aufl., S. 186]

Produktion und Logistik

PW / OR WS 06/07

4-32

4.4.1.2 Matrizenverfahren zur einperiodigen Materialbedarfsrechnung Betrachtungszeitraum: 1 abgeschlossene Produktionsperiode (ohne Lagerhaltung) Bedarfsrechnung bei einstufiger Produktion

Produktionsmodell

(einstufiges Leontief-Modell)

xi =

m+ n

∑a

ij

⋅ yj

für

i = 1,...,m

j = m +1

mit

⇒

xi : Verbrauchsmenge des Faktors i (i = 1,..., m) yj : Ausbringungsmenge des Produkts j (j = m + 1,..., m + n) aij : Einsatzmenge des Faktors i für 1 Ausbringungseinheit des Produkts j (= Produktionskoeffizient)

Lineares Gleichungssystem zur Bestimmung der Materialbedarfsmengen aller Faktoren aus vorgegebenen Produktions- bzw. Bedarfsmengen aller Produkte.

Produktion und Logistik

PW / OR WS 06/07

4-33

Gleichungssystem in Matrix/Vektor-Schreibweise

x = A⋅y mit y

:

x

:

A

:

Erzeugnisprogramm, d.h. (n)-Vektor der herzustellenden Produktmengen (= Primärbedarfe) Einsatzprogramm, d.h. (m)-Vektor der fremd zu beziehenden (= Sekundärbedarfe) Bedarfsmatrix, d.h. Matrix der (direkten) Produktionskoeffizienten (=Direktbedarfskoeffizienten)

Materialbedarfsmengen

Beispiel Lederlotte x1 = 50 y4 + 50 y5 x2 = 40 y4 + 15 y5 x3 = 0,15 y4 + 0, 4 y5

bzw.

⎛ x1 ⎞ ⎛ 50 ⎜ ⎟ ⎜ ⎜ x2 ⎟ = ⎜ 40 ⎜ x ⎟ ⎜ 0,15 ⎝ 3⎠ ⎝

50 ⎞ ⎟ ⎛ y4 ⎞ 15 ⎟ ⋅ ⎜ ⎟ y 0, 4 ⎟⎠ ⎝ 5 ⎠

Produktion und Logistik

PW / OR WS 06/07

4-34

Bedarfsplanung bei mehrstufiger Produktion Besonderheit: Für Zwischenprodukte gibt es grundsätzlich ¾ sowohl Primärbedarfe als auch Sekundärbedarfe, ¾ sowohl Fremdbezug als auch Eigenherstellung Für die einzelnen Güterarten k = 1,..., κ sind damit grundsätzlich folgende verschiedene Materialmengen relevant:

yk sk rk uk xk

: : : : :

Primärbedarf (extern) der Güterart k Sekundärbedarf (intern) Gesamtbedarf bzw. Gesamtbezug Eigenherstellungsmenge Fremdbezugsmenge

Mengenbilanz (bei abgeschlossener Produktionsperiode) generell:

bzw. nach Güterarten differenziert:

xk x k + u k = rk = s k + y k für k = 1,..., κ

xk

+ uk uk

= rk

= sk

= rk = rk

= sk =

für originäre Faktoren + yk yk

für Zwischenprodukte für Endprodukte

Sekundärbedarf und Eigenherstellung im mehrstufigen Leontief-Modell : si = ∑ aij ⋅ u j j

für alle originären Faktoren/Zwischenprodukte i und alle Zwischenprodukte/Endprodukte j

Produktion und Logistik

PW / OR WS 06/07

4-35

Mengenzusammenhänge in Matrix/Vektor-Schreibweise

x+u=r =s+y s = A⋅u

⇒

mit A : Direktbedarfsmatrix

Produktionsmodell bei mehrstufigen Leontief-Systemen :

x + u = r = A⋅u + y ⇒

Gleichungssystem zur Materialbedarfsrechnung

Spezialfall: Ausschluss von Fremdbezug für Zwischenprodukte (d.h. xk = 0 für Zwischenprodukte)

⇒

Materialbedarfsmengen :

⎧x rk = ⎨ k ⎩u k

⇒

für originäre Faktoren (nur Fremdbezug!) für Zwischenprodukte (nur Eigenherstellung!)

Vereinfachtes Produktionsmodell bzw. Gleichungssystem

r = A ⋅r + y Transformation des mehrstufigen in eine einstufiges Produktionsmodell

r = (I − A ) ⋅ y −1

⇒

bzw.

r = G⋅y

einstufige Gesamtbedarfsermittlung

mit G = (I – A)-1 als sog. Gesamtbedarfsmatrix

Produktion und Logistik

PW / OR WS 06/07

4-36

Beispiel: Bedarfsplanung bei mehrstufiger Produktion Direktbedarfsmatrix: ⎛0 0 0 ⎜ ⎜0 0 0 ⎜0 0 0 ⎜ A = ⎜0 0 0 ⎜0 0 0 ⎜ ⎜0 0 0 ⎜0 0 0 ⎝

0⎞ ⎟ 0⎟ 4⎟ ⎟ 1⎟ 3⎟ ⎟ 0 0 0 0⎟ 0 0 0 0 ⎟⎠

0 5 1 0 0

6 3 0 2 0

0 0 0 0 2

Dreistufiger Gozinto-Graph [Quelle: Dyckhoff, S. 274

Gesamtbedarfsmatrix: ⎛1 0 0 ⎜ ⎜0 1 0 ⎜0 0 1 ⎜ G =(I -A)-1 = ⎜ 0 0 0 ⎜0 0 0 ⎜ ⎜0 0 0 ⎜0 0 0 ⎝

einstufiges Produktionsmodell: 0 6 12 18 ⎞ ⎟ 5 13 26 44 ⎟ 1 2 4 11⎟ ⎟ 1 2 4 7⎟ 0 1 2 3⎟ ⎟ 0 0 1 0⎟ 0 0 0 1⎟⎠

x1 =

6 y5

+ 12 y6

+ 18 y7

x2 x3

= 5 y4 = y4

+ 13 y5 + 2 y5

+ 26 y6 + 4 y6

+ 44 y7 + 11 y7

u4 u5

= =

+

+ +

+ +

y4

2 y5 y5

4 y6 2 y6

7 y7 3 y7

Produktion und Logistik

PW / OR WS 06/07

4-37

Numerische Ermittlung der Gesamtbedarfsmatrix G Bei nicht-zyklischen Produktionsstrukturen besitzt die Matrix I-A die Form einer oberen Dreiecksmatrix, so dass sich die Elemente der Inversen G (gij) sukzessiv berechnen lassen: gii = 1 ∀i und gij =

mit Ni :

∑ aik ⋅ gkj ∀i ≠ j

Menge der direkten Nachfolger von Objekt i

k∈N i

Beispielrechnungen g77 = 1 g57 = a57 ⋅ g77 = g 47 = a45 ⋅ g57 + g 27 = a24 ⋅ g 47 + ⎛0 ⎜ ⎜0 ⎜0 ⎜ A = ⎜0 ⎜0 ⎜ ⎜0 ⎜0 ⎝

(obiges Produktionssystem) 3 ⋅1 a47 ⋅ g77 a25 ⋅ g57 0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 5 1 0 0 0 0

= 3 = 2 ⋅ 3 + 1 ⋅1 = 7 = 5 ⋅ 7 + 3 ⋅ 3 = 44 6 3 0 2 0 0 0

0 0 0 0 2 0 0

0⎞ ⎟ 0⎟ 4⎟ ⎟ 1⎟ 3⎟ ⎟ 0⎟ 0 ⎟⎠

⎛1 ⎜ ⎜0 ⎜0 ⎜ I - A = ⎜0 ⎜0 ⎜ ⎜0 ⎜0 ⎝

0 −6

0

1 0 −5 −3 0 1 −1 0

0 0

0 0

1 −2

0

0 0 0 0

0 0

1 −2 0 1

0 0

0

0

0 0

0

0⎞ ⎟ 0⎟ −4 ⎟ ⎟ −1 ⎟ −3 ⎟ ⎟ 0⎟ 1⎟⎠

Produktion und Logistik

PW / OR WS 06/07

4-38

4.4.1.3 Matrizenverfahren zur mehrperiodigen Materialbedarfsrechnung Das Matrizenverfahren ist für eine Materialbedarfsplanung über mehrere Perioden unmittelbar nur dann anwendbar, wenn alle Planungsperioden isoliert betrachtet werden können.

Bedingungen für isolierte Periodenbetrachtung: ¾ Keine Lagerhaltung von Erzeugnissen ¾ Keine Zeitinanspruchnahme der Produktion (Null-Durchlaufzeiten) Bei isolierter Periodenbetrachtung Materialbedarfsrechnung:

gilt

entsprechend

rt = G ⋅ y t

mit rt : Vektor der Materialbedarfsmengen in Periode t yt : Vektor der Primärbedarfe in Periode t Ergebnis: Die Materialbedarfsmengen betragen ¾ für originäre Faktoren i (bei ausschließlichem Fremdbezug) κ

xit = ∑ gij ⋅ y jt j =1

¾ für Zwischenprodukte k (bei ausschließlicher Eigenherstellung) κ

ukt = ∑ g kj ⋅ y jt j =1

mit gij und gkj als Elemente der Gesamtbedarfsmatrix G .

der

einperiodigen

Produktion und Logistik

PW / OR WS 06/07

4-39

Beispiel: Mehrperiodige Materialbedarfsrechnung nach Matrizenverfahren Daten: 4 Planungsperioden (t = 1,...,4) mit folgenden Primärbedarfen (nur für Endprodukte) Endprodukt P6 Endprodukt P7 d. h.:

y61 = 1,

t=1 1 1 y62 = 1,

t=2 1 0 y63 = 1,

t=3 1 0 y64 = 1,

t=4 1 2

y71 = 1,

y72 = 0,

Materialbedarfsplan: Einsatzfaktoren:

E1 E2 E3 Zwischenprodukte B4 B5 Endprodukte P6 P7

t=1 30 70 15 11 5 1 1

t=2 12 26 4 4 2 1 0

t=3 12 26 4 4 2 1 0

t=4 48 114 26 18 8 1 2

xit ukt yjt

Rechenbeispiele: ¾ u51 = g 55 ⋅ y51 + g 56 ⋅ y61 + g57 ⋅ y71 = 1 ⋅ 0 + 2 ⋅1 + 3 ⋅1 = 5 ¾ x11 = g11 ⋅ y11 + g15 ⋅ y51 + g16 ⋅ y61 + g17 ⋅ y71 = 1 ⋅ 0 + 6 ⋅ 0 + 12 ⋅1 + 18 ⋅1 = 30 ¾ x14 = g11 ⋅ y14 + g15 ⋅ y54 + g16 ⋅ y64 + g17 ⋅ y74 = 1 ⋅ 0 + 6 ⋅ 0 + 12 ⋅1 + 18 ⋅ 2 = 48

y73 = 0,

y74 = 2,

Produktion und Logistik

PW / OR WS 06/07

4-40

4.4.2 Dispositionsstufenverfahren auf Basis von Stücklisten Das Dispositionsstufenverfahren ermöglicht eine mehrperiodige Materialbedarfsrechnung unter Berücksichtigung von Lagerbeständen und Produktionsdurchlaufzeiten. Beim Dispositionsstufenverfahren werden die Zwischenprodukte und Kaufmaterialien an Hand der Erzeugnisstruktur einzelnen Dispositionsstufen zugeordnet. Ihre Bedarfsmengen werden sukzessive Stufe für Stufe aus den Primärbedarfen der End- und Zwischenprodukte abgeleitet. Die Erzeugnisstruktur wird durch sog. Stücklisten dargestellt. 4.4.2.1 Stücklisten Stücklisten sind tabellarische Verzeichnisse der in ein End- oder Zwischenprodukt eingehenden Materialien. Zu unterscheiden sind Mengenübersichts- und Baukastenstücklisten. Eine Mengenübersichtsstückliste gibt an, aus welchen verschiedenen Materialien ein Produkt insgesamt besteht und in welchen Mengen einzelne Materialien in eine Einheit des jeweiligen Produkts eingehen. Der strukturelle Aufbau des Produkts ist nicht enthalten. ⇒ Die Angaben in Mengenübersichtsstücklisten entsprechen den Spalten der Gesamtbedarfsmatrix G. Eine Baukastenstückliste gibt an, welche Materialien in welchen Mengen direkt in eine Einheit eines Produkts eingehen. ⇒ Die Angaben der Baukastenstücklisten entsprechen den Spalten der Direktbedarfsmatrix A. Die Information über die gesamte Erzeugnisstruktur eines Endprodukts erhält man durch Verkettung der Baukastenstücklisten von Endprodukt und zugehörigen Baugruppen (=Zwischenprodukte, die sich aus mehreren Materialien zusammensetzen).

Produktion und Logistik

PW / OR WS 06/07

4-41

Beispiel zu Stücklisten

Gozintograph des Beispiels [Quelle: Günther/Tempelmeier: Produktion und Logistik, 4. Aufl., S. 187]

Mengenübersichtsstückliste [Quelle: Günther/Tempelmeier: Produktion und Logistik, 4. Aufl., S. 188]

Baukastenstücklisten [Quelle: Günther/Tempelmeier: Produktion und Logistik, 4. Aufl., S. 188]

Produktion und Logistik

PW / OR WS 06/07

4-42

4.4.2.2 Dispositionsstufenverfahren Die Dispositionsstufe eines Materials in einer Erzeugnisstruktur entspricht der maximalen Anzahl von Produktionsaktivitäten, die zwischen seinem Einsatz und der Erzeugung eines Endprodukts liegen (= maximale Fertigungsstufe). Alle Endprodukte besitzen die Dispositionsstufe Null. Beispiele: von Seite 4-41

von Seite 4-36

P1 1

(Dispositions-) Stufe 0

2

3 1

2

3

Stufe 1

4

2

E1

P7 2

B1

B2

P6

B5 2

6

2

Stufe 2

E1

B4

3

5 E2

Stufe 3

4

5 E2

1 E3

Produktion und Logistik

PW / OR WS 06/07

4-43

Reihenfolgebildung bei Bedarfsermittlung nach Dispositionsstufenverfahren: ¾ Die Materialbedarfe eines Erzeugnisses auf einer bestimmten Dispositionsstufe können erst dann berechnet werden, wenn die Bedarfe aller Erzeugnisse auf der darunter liegenden Stufe ermittelt sind. ¾ Die Materialbedarfe aller Erzeugnisse auf derselben Dispositionsstufe können in beliebiger Reihenfolge berechnet werden. Einzelschritte der Materialbedarfsrechnung Für jedes Erzeugnis werden der Reihe nach für jede Periode des Planungszeitraums (d.h. terminiert) jeweils folgende Rechenoperationen vorgenommen:

(1) (2) (3) (4) (5)

Sekundärbedarfsermittlung Bruttobedarfsermittlung Lagerbestandsfortschreibung Nettobedarfsermittlung Vorlaufverschiebung

Notwendige Informationen zur Materialbedarfsrechnung ¾ Stücklistendaten ¾ Primärbedarfe aller Produkte nach Perioden ¾ Lagerbestände aller Produkte zu Planungsbeginn ¾ Produktionsdurchlaufzeiten bzw. Lieferzeiten (als sog. Vorlaufzeiten) aller Produkte ⇒ Die Materialbedarfsrechnung mit dem Dispositionsstufenverfahren wird auch als Stücklistenauflösung bezeichnet.

Produktion und Logistik

PW / OR WS 06/07

4-44

Rechenoperationen beim Dispositionsstufenverfahren

[1]

Ermittlung der Sekundärbedarfe

(SB)

Die terminierten SB eines Zwischenproduktes bzw. Einsatzfaktors ergeben sich aus den terminierten Auftragsmengen der durch Mengenbeziehungen verbundenen End- und Zwischenprodukte niedrigerer Dispositionsstufen (entsprechend den Stücklisteninformationen).

[2] Ermittlung der Bruttobedarfe

(BB)

Die terminierten BB errechnen sich als Summe aus den terminierten SB und Primärbedarfen.

[3] Fortschreibung der Lagerbestände

(LB)

Für den Lagerbestand zu Beginn einer Periode gilt jeweils: LB =

max {LB der Vorperiode – BB der Vorperiode ; 0}

[4] Ermittlung der Nettobedarfe Für jede Periode gilt:

NB =

(NB) max {BB –LB ; 0}

.

[5] Vorlaufverschiebung der Bedarfsmengen Unter Berücksichtigung der Vorlaufzeit λ werden die NB (bei bedarfssynchroner Bildung von Produktions- bzw. Beschaffungsaufträgen) in terminierte Aufträge (TA) umgewandelt: NB der Periode t

=

TA der Periode t - λ

Produktion und Logistik

PW / OR WS 06/07

4-45

Mehrperiodige Materialbedarfsrechnung nach Dispositionsstufenverfahren am Beispiel von Seite 4-36 Daten: 4 Planungsperioden mit denselben Primärbedarfen wie auf Seite 4-39 P6 P7

t=1 1 1

t=2 1 0

t=3 1 0

t=4 1 2

(Dispositions-) Stufe 0

P6

Anfangsbestände Produkt E1 LB in t=1 40

E2 15

P7 3

2 E3 0

B4 3

B5 3

P6 2

Vorlaufzeiten: jeweils 0 Perioden bei E1, E2, E3 1 Periode bei B4, B5, P6, P7

P7 2

1

Stufe 1

B5 2

6 Stufe 2 Stufe 3

4

E1

B4

3 5 E2

1 E3

Produktion und Logistik

PW / OR WS 06/07

4-46

Berechnungen:

Dispositionsstufe 0 Endprodukt P7

Endprodukt P6

Periode t Primärbedarf (PB) Bruttobedarf (BB) Lagerbestand (LB) Nettobedarf (NB) Terminierter Auftrag (TA) Primärbedarf (PB) Bruttobedarf (BB) Lagerbestand (LB) Nettobedarf (NB) Terminierter Auftrag (TA)

Dispositionsstufe 1 Sekundärbedarf (SB) aus P7 Zwischenprodukt B5 SB (aus P6) BB LB NB TA

1 1 1 2 1 1 2 -

2 1 1 1 1 1

3 1 1 1 1 1 1

4 2 2 1 1 1 1 1 -

3 -

2 2 3 4

3 2 5 1 4 -

-

Produktion und Logistik

PW / OR WS 06/07

Periode t Dispositionsstufe 2 SB (aus P7) Zwischenprodukt B4 SB (aus B5) BB LB NB TA SB (aus B5) Kaufmaterial E1 BB LB NB TA Dispositionsstufe 3 SB (aus P7) SB (aus B4) Kaufmaterial E3 BB LB NB TA SB (aus B5) Kaufmaterial E2 SB (aus B4) BB LB NB TA

1 3 5 40 5 5 5 5 25 25 15 10 10

4-47

2 8 8 3 5 1 24 24 40 1 1 1 1 12 5 17 17 17

3 1 1 1 16 4 4 4 4 -

4 16 -

Produktion und Logistik

PW / OR WS 06/07

4-48

4.5 Losgrößenplanung Planungsaufgabe Zusammenfassung der Nettobedarfe einzelner Erzeugnisse in aufeinander folgenden Perioden zu Produktions- bzw. Beschaffungsaufträgen, die als sog. Produktions- bzw. Beschaffungslos in einem einzigen Vorgang hergestellt bzw. eingekauft werden. Motive für Losbildung ¾ Technische Beschränkungen ¾ Vorausproduktion/-beschaffung bei Kapazitätsengpässen ¾ Vorausproduktion/-beschaffung bei Preisänderungen ¾ Vermeidung von losfixen (d.h. mengenunabhängigen) Produktions- bzw. Beschaffungskosten → Fixkosten der Produktion : Rüstkosten bei Erzeugniswechsel → Fixkosten der Beschaffung : Kosten der Bestellabwicklung und (u. U.) des Transports

Hinweis: Beim Fehlen von technischen und ökonomischen Motiven zur Losbildung ist eine bedarfssynchrone Produktion bzw. Beschaffung (d. h. Auftragsgröße = Nettobedarf der lfd. Periode) zweckmäßig (→ Just-In-Time-Konzept).

Produktion und Logistik

PW / OR WS 06/07

4-49

Klassisches Kostenkalkül zur Losgrößenbestimmung ¾ Kostenkonflikt zwischen Lagerhaltungskosten und losfixen Kosten Losgröße

Lagerhaltungskosten

losfixe Kosten

Gesamtkosten

niedrig hoch

gering groß

groß gering

? ?

¾ Losgrößenoptimierung Festlegung der Losgröße (i. d. R. getrennt für jedes einzelne Erzeugnis) in der Form, dass die Summe aus Lagerhaltungs- und Fixkosten minimiert wird.

Produktion und Logistik

PW / OR WS 06/07

4-50

4.5.1 Statische Losgrößenplanung Kalkül zur Losgrößenplanung im Fall gleich hoher Bedarfsmengen in allen Planungsperioden. Modellannahmen ¾ Stetiger Verlauf der Zeit (keine Periodisierung) ¾ Keine Begrenzung des Planungshorizonts (unendlicher Planungszeitraum) ¾ Konstante Bedarfe im Zeitverlauf ¾ Ziel: Minimierung der Gesamtkosten pro Zeiteinheit (ZE) ⇒ Konsequenz: Optimale Bedarfszusammenfassung führt zu jeweils gleich großen Losen. ⇒ Offene Frage: Welches ist die optimale Größe q* der Produktions- bzw. Beschaffungslose?

Modellierung des statischen Losgrößenproblems Daten : B : Bedarfsmenge pro ZE (z.B. Jahr) in ME f : Fixkosten bei Bildung eines Produktions- bzw. Beschaffungsloses in GE l : Lagerhaltungskosten in GE je ME und ZE

Variable : q : Größe des Produktions- bzw. Beschaffungsloses in ME Zielgröße : K = Klos + Klag :

Gesamtkosten je ZE in GE mit Klos : losfixe Kosten je ZE Klag : Lagerhaltungskosten je ZE

Produktion und Logistik

PW / OR WS 06/07

4-51

Zielfunktion K= f⋅

Minimiere wobei :

B q q 2

B q +l⋅ q 2

= K (q)

= Anzahl der Losauflagen pro ZE = durchschnittlicher Lagerbestand

Nebenbedingung :

q≥0

⇒ Typ des Optimierungsproblems

Lager mit schlagartigem Zugang und gleichmäßigem Abgang [Quelle: Dyckhoff, 3. Aufl., S. 313]

Minimierung einer stetigen, differenzierbaren Funktion in einer Variablen, nämlich K(q), mit Konvexitätseigenschaft ⇒ Lösung des Optimierungsproblems

¾ Optimalitätsbedingung : ¾ Optimale Losgröße :

Hinweis:

dK 1 B =0 → − f ⋅ 2 +l⋅ =0 dq q 2

q* = +

2⋅ f ⋅ B l

Die Quadratwurzelformel für q* wird als (klassische) wirtschaftliche Losgrößenformel bezeichnet. Bei ihrer praktischen Anwendung ist i. d. R. eine Anpassung durch Rundung erforderlich.

Produktion und Logistik

Beispiel: B f l´

= = =

18000 4800 0,4

PW / OR WS 06/07

[Stück/Jahr] [€] [€/Stück und Monat]

→ l = 4,8

4-52

[€/Stück und Jahr]

Losgrößenabhängige Kosten [Quelle: Dyckhoff : Grundzüge der Produktionswirtschaft, 3. Aufl., S. 316]

⇒

q* =

2 ⋅ 4800 ⋅18000 = 6000 [Stück] 4,8

Produktion und Logistik

PW / OR WS 06/07

4-53

4.5.2 Dynamische Losgrößenplanung Kalkül zur Losgrößenplanung unter Berücksichtigung von zeitlichen Schwankungen der Bedarfsmengen in einzelnen Planperioden über einen vorgegebenen Planungshorizont. Modellannahmen ¾ Diskrete Betrachtung der Zeit (Periodisierung) ¾ Begrenzter Planungshorizont (endlicher Planungszeitraum) ¾ Beliebiger zeitlicher Verlauf der Periodenbedarfe ¾ Ziel: Minimierung der Gesamtkosten aus Lagerhaltung und Produktion/Beschaffung über den gesamten Planungszeitraum ⇒ Konsequenz: Optimale Zusammenfassung der Periodenbedarfe kann in einzelnen Perioden t zu unterschiedlich großen Losen qt führen! (→ dynamische Losgrößenbildung)

⇒ Offene Frage: Optimalen Losgrößen qt für alle Perioden des Planungszeitraums?

Modellierung des dynamischen Losgrößenproblems Daten : T : Länge des Planungszeitraums in Perioden Bt : Bedarfsmenge in Periode t (mit t = 1,2,...,T) in ME f : Fixkosten bei Bildung eines Produktions- bzw. Beschaffungsloses in GE l : Lagerhaltungskosten in GE je ME und Periode (bezogen auf den Lagerbestand am Ende einer Periode) y0 : Anfangslagerbestand zu Beginn des Planungszeitraums

Produktion und Logistik

PW / OR WS 06/07

4-54

Variablen : qt : Losgröße in Periode t : Lagerbestand am Ende der Periode t yt xt : Rüstvariable in Periode t (binäre Variable) mit folgender Bedeutung : ⎧ 1 , wenn in Periode t ein Los aufgelegt wird xt = ⎨ ⎩ 0 , sonst Entscheidungsmodell : ⇒ Minimiere die Gesamtkosten K aus Lagerhaltung und Losauflage unter Berücksichtigung von Lagerbilanzgleichungen (1), logischen Rüstbedingungen (2) und Variablenbeschränkungen (3). Minimiere

T

T

t =1

t =1

K = ∑ f ⋅ xt + ∑ l ⋅ yt

u. d. N. (1)

yt = yt-1 + qt - Bt

für

t = 1,..., T

(2)

qt ≤ M ⋅xt

für

t = 1,..., T

T

mit M : große Zahl, so dass M ≥ ∑ Bt t =1

(3)

qt, yt ≥ 0 und xt ∈ {0,1} für t = 1 ,..., T

⇒ Typ des Optimierungsproblems: Gemischt-ganzzahliges LOP wegen Ganzzahligkeit der Variablen xt ⇒ Konsequenz: Lösung über normale LOP-Lösungsverfahren (Simplex-Methode) i. d. R. nicht mehr möglich!

Produktion und Logistik

PW / OR WS 06/07

4-55

Beispiel zur dynamischen Losgrößenplanung Daten: t Bt

T = 6 , f = 100 , l = 1 , y0 = 0 1 25

2 70

3 60

4 50

5 40

6 5

Σ 250

Entscheidungsmodell: Minimiere K = 1⋅y1 + 1⋅y2 + 1⋅y3 + 1⋅y4 + 1⋅y5 + 1⋅ y6 + 100⋅x1 + 100⋅x2 + 100⋅x3 + 100⋅x4 + 100⋅x5 + 100⋅x6 u. d. N.

(1)

y1 y2 y3 y4 y5 y6

= = = = = =

q1 - 25 y1 + q2 - 70 y2 + q3 - 60 y3 + q4 - 50 y4 + q5 - 40 y5 + q6 - 5

(2)

qt ≤ 250x t

für t = 1,...,6

(3)

qt, y t ≥ 0 und x t ∈ {0,1}

für t=1,...,6

Produktion und Logistik

PW / OR WS 06/07

4-56

Lösungsvorschläge: (A) Bedarfssynchrone Losbildung:

q1 = 25, q2 = 70, q3 = 60, q4 = 50, q5 = 40, q6 = 5 → K = 600 + 0 = 600

(B) Maximale Losbildung:

q1 = 250, q2 = q3 = q4 = q5 = q6 = 0 → K = 100 + 525 = 625

Optimale Lösung des LOP ¾ als reellwertiges LOP (d.h. xt ≥ 0)

x1* = 0,10 x2* = 0,28 x3* = 0,24 x4* = 0,20 x5* = 0,16 x6* = 0,02

q1* = q2* = q3* = q4* = q5* = q6* =

25 70 60 50 40 5

[ → K* = 100 ] ⇒ Lösungseigenschaft:

y1* = 0 y2* = 0 y3* = 0 y4* = 0 y5* = 0 y6* = 0 ???

¾ als gemischt-ganzzahliges LOP (d. h. xt ∈ {0,1})

x1* = 1 x2* = 1 x3* = 0 x4* = 1 x5* = 0 x6* = 0

q1* = 25 q2* = 130 q3* = 0 q4* = 95 q5* = 0 q6* = 0

→ K* = 410

y1* = 0 y2* = 60 y3* = 0 y4* = 45 y5* = 5 y6* = 0

= 300 + 110

Losbildung durch Zusammenfassung ganzer Periodenbedarfe

Produktion und Logistik

PW / OR WS 06/07

5 Ganzzahlige Optimierung

5-1

Produktion und Logistik

PW / OR WS 06/07

5-2

5.1 Grundlagen der Ganzzahligen Optimierung Definitionen Ganzzahlige Optimierungsprobleme liegen vor, wenn einige oder alle Variablen (xi) eines Optimierungsproblems nur ganzzahlige Werte annehmen können. Handelt es sich dabei um ein Lineares Optimierungsproblem, so spricht man von einem (gemischt-)ganzzahligen LOP. Ursachen für Ganzzahligkeit ¾ Unteilbarkeit von Entscheidungsgegenständen (wie z.B. bei Stückgütern, Projekten, Personen, etc.) ⇒ xi ∈ {0,1,2, ... } → ganzzahlige Variable ¾ Entscheidungen in Form von Ja/Nein-Entscheidungen (wie z.B. bei Losauflagenentscheidung, bei Zuordnungsentscheidungen, etc.) ⇒ xi ∈ {0,1} → binäre Variable Klassifikationsmöglichkeiten ganzzahlige vs. binäre Optimierungsprobleme (reine) vs. gemischt-ganzzahlige Optimierungsprobleme kombinatorische Optimierungsprobleme

Ein Kombinatorisches Optimierungsproblem liegt vor, wenn der Wertebereich der ganzzahligen Variablen nach oben beschränkt ist, so dass nur eine endliche Anzahl von Kombinationsmöglichkeiten der Variablenwerte existiert.

Produktion und Logistik

PW / OR WS 06/07

5-3

Beispiel für ein ganzzahliges LOP Maximiere Z ( x1 , x2 ) = x1 + 2 x2

unter den Nebenbedingungen x1 + 3x2 ≤ 7 3x1 + 2 x2 ≤ 10 x1 , x2 ≥ 0 und ganzzahlig

(1) (2) (2)

(1)

Produktion und Logistik

PW / OR WS 06/07

5-4

Problemtypen der kombinatorischen Optimierung (1) Zuordnungsprobleme

Inhalt : Paarweise oder weitergehende gegenseitige Zuordnung von Elementen aus mehreren Gruppen

⎧1 , wenn Element i und j einander zugeordnet werden x = Variable : ij ⎨0 , sonst ⎩ Beispiele :

- Lineares Zuordnungsproblem - Stundenplanproblem - Personaleinsatzplanung

(2) Reihenfolgeprobleme

Inhalt : Bildung einer Reihenfolge von Elementen einer Gruppe

⎧1 , wenn Element j unmittelba r nach Element i gereiht wi rd x = Variable : ij ⎨0 , sonst ⎩ Beispiele :

- Rundreiseproblem - Maschinenbelegungsproblem

Produktion und Logistik

PW / OR WS 06/07

(3) Gruppierungsprobleme

Inhalt : Zusammenfassung von Elementen einer Gruppe zu mehreren Teilgruppen

⎧1 , wenn Element j der Gruppe i zugeteilt wird x = Variable : ij ⎨0 , sonst ⎩ Beispiele :

- Losgrößenplanung - Tourenplanung

(4) Auswahlprobleme

Inhalt : Auswahl einer Teilmenge von Elementen aus einer Gesamtmenge

⎧1 , wenn Element i ausgewählt wird x = Variable : i ⎨0 , sonst ⎩ Beispiel:

- Rucksackproblem - Standortplanung - Investitionsplanung

5-5

Produktion und Logistik

PW / OR WS 06/07

Das Rundreiseproblem (Traveling-Salesman-Problem) Aufgabe : Festlegung der Reihenfolge des Besuchs von n Orten, so dass die Gesamtstrecke der Rundreise minimiert wird.

Daten :

cij : Entfernung zwischen Ort i und Ort j (i, j = 1,..., n)

Variablen : ⎧1 wenn Ort j unmittelbar nach Ort i besucht wird xij = ⎨ ⎩0 sonst

Zielfunktion : n

n

Minimiere Z = ∑∑ cij ⋅ xij i =1 j =1

Nebenbedingungen : n

∑x

=1

für

∑x

=1

für i = 1,..., n

ij

i =1 n

ij

j = 1,..., n

j =1

Kurzzyklenbedingungen

xij ∈ {0,1} für i, j = 1,..., n

5-6

Produktion und Logistik

PW / OR WS 06/07

5-7

Beispiel „Rund um Magdeburg“: SDL

7

HVL

6

BRB

2

BRG

3

MD

0

HBS

5 WB

DE

BBG

8

4

1

Matrix der kürzesten Wege : 0 1 2 3 4 5 6 7 8

0 0

1 48 0

2 89 135 0

3 28 75 67 0

4 62 41 92 63 0

5 56 60 144 88 96 0

6 96 142 34 61 125 151 0

7 62 108 63 62 122 117 37 0

8 85 73 75 87 33 127 109 122 0

Produktion und Logistik

PW / OR WS 06/07

5-8

Das Rucksackproblem (Knapsack-Problem) Aufgabe : Auswahl einzelner Objekte aus einer Gesamtmenge von n Objekten mit unterschiedlichem Nutzen und Gewicht, so dass unter Einhaltung einer Gesamtgewichtsgrenze der Gesamtnutzen maximiert wird.

Daten : ci wi W

(i = 1,..., n) Nutzen des Objekts i (i = 1,..., n) Gewicht des Objekts i maximales Gesamtgewicht

: : :

Variablen : ⎧1 wenn Objekt i ausgewählt wird xi = ⎨ ⎩0 sonst Zielfunktion : n

Maximiere Z = ∑ ci ⋅ xi i =1

Nebenbedingungen : n

Buch subjektiver Nutzen Gewicht Maximalgewicht: 25

∑ wi ⋅ xi ≤ W i =1

xi ∈ {0,1} für

Beispiel „Die einsame Insel“:

i = 1,..., n

1 10 5

2 12 6

3 24 12

4 12 7

5 23 12

Produktion und Logistik

PW / OR WS 06/07

Lösungseigenschaften ganzzahliger LOP’s ¾ Die Lösungsmenge ist endlich (anders als bei kontinuierlichen LOP’s). ¾ Die Eckpunkteigenschaft der Lösung kontinuierlicher LOP’s ist nicht gegeben! ⇒ Die Suche nach der optimalen Lösung ist wesentlich aufwendiger als bei kontinuierlichen LOP’s (keine Anwendbarkeit des Simplex-Verfahrens!)

⇒ Ganzzahlige LOP’s sind i. A. „schwer lösbare“ Probleme, d.h. ihr Lösungsaufwand steigt exponentiell mit der Problemgröße.

5-9

Produktion und Logistik

PW / OR WS 06/07

5-10

Komplexität von ganzzahligen LOP’s Beispiel : Binäres LOP mit n Variablen (z.B. Rucksackproblem) ⇒ 2 n mögliche Lösungen Variablenzahl n Lösungsmöglichkeiten 2 2 4 5 32 10 1.024 20 ~ 106 30 ~ 109 40 ~ 1012 50 ~ 1015

n

Rechenzeit bei Vergleich aller Lösungen bei 1 Millisekunde pro Lösung 1 Sekunde 17 Minuten 12 Tage 35 Tage 35.700 Jahre

Produktion und Logistik

PW / OR WS 06/07

5-11

Rechenaufwand von Lösungsalgorithmen

Definition:

Rechenaufwand R(n) eines Algorithmus für ein Problem der Größe n ist von Größenordnung f(n), wenn für hinreichend große n gilt: R(n) ≤ c ⋅ f (n) mit c ∈

+

Maß der Problemkomplexität : O(f(n)) Unterscheidung : • polynomialer Aufwand : • exponentieller Aufwand :

f(n) ist Polynom der Ordnung n f(n) ist Exponentialfunktion von n

z.B. n2 oder n3 z.B. 2n oder en

Problemklassen • Klasse P : polynomial lösbar → „effizient lösbar“ • Klasse NP-schwer : (noch) nicht polynomial lösbar → „schwer lösbar“

Produktion und Logistik

PW / OR WS 06/07

5-12

Lösungsverfahren für ganzzahlige LOP’s • Optimierende Verfahren ⇒ Vollständige Enumeration ⇒ Unvollständige (begrenzte) Enumeration z.B. Branch & Bound-Verfahren Teilproblem 2

Teilproblem 1

⇒ Schnittebenen-Verfahren

⇒ Dynamische Optimierung (sukzessive Optimierung)

Produktion und Logistik

PW / OR WS 06/07

5-13

• Heuristische Verfahren sind Verfahren zur Ermittlung einer „guten“ zulässigen Lösung mit „geringem“ Rechenaufwand ohne Garantie zum Erreichen bzw. Erkennen der optimalen Lösung. ⇒ Eröffnungsverfahren (zur Bestimmung einer ersten zulässigen Lösung) ƒ uninformierte Verfahren z.B. – Nordwesteckenregel bei Transportproblemen – bedarfssynchrone Losgrößenbildung bei der Losgrößenplanung) ƒ Greedy Heuristiken – Verfahren des nächsten Nachbarn bei Rundreisenproblemen ƒ Look ahead-Heuristiken ƒ Rundungsheuristiken ⇒ Verbesserungsverfahren (zur systematischen Verbesserung einer gegebenen zulässigen Lösung) ƒ Lokale Suchverfahren ƒ Meta-Heuristiken (Simulated Annealing, Tabu Search, Genetische Algorithmen) ⇒ Unvollständig optimierende Verfahren z.B. vorzeitig abgebrochene Branch & Bound-Verfahren

Produktion und Logistik

PW / OR WS 06/07

5-14

Verfahren des nächsten Nachbarn am Beispiel 0 1 2 3 4 5 6 7 8

0 0

1 48 0

2 89 135 0

3 28 75 67 0

4 62 41 92 63 0

5 56 60 144 88 96 0

6 96 142 34 61 125 151 0

7 62 108 63 62 122 117 37 0

8 85 73 75 87 33 127 109 122 0

Route : [0 - 3 - 6 - 2 - 7 - 1 - 4 - 8 -5 - 0] ⇒ D = 551 SDL

7

HVL

6

BRB

2

BRG

3

MD

0

HBS

5

BBG

DE

WB 1

Optimale Route : [0 - 3 - 7 - 6 - 2 - 8 - 4 - 1 - 5 - 0] ⇒ D* = 426

4

8

Produktion und Logistik

PW / OR WS 06/07

Rundungsheuristik am Beispiel des Rucksackproblems Daten: Buch subjektiver Nutzen Gewicht

1 10 5

2 12 6

3 24 12

4 12 7

5 23 12

Maximalgewicht: 25 Optimale Lösung ohne Berücksichtigung der Ganzzahligkeit der Variablen: x1 = 1, x2 = 1, x3 = 1, x4 = 0, x5 = 1/6, Z = 49,83, Gesamtgewicht = 25 Gerundete Lösung: x1 = 1, x2 = 1, x3 = 1, x4 = 0, x5 = 0, Z = 46, Gesamtgewicht = 23 Optimale Lösung: x1* = 0, x2* = 1, x3* = 1, x4* = 1, x5* = 0, Z* = 48, Gesamtgewicht = 25

5-15

Produktion und Logistik

PW / OR WS 06/07

5-16

5.2 Branch & Bound-Verfahren Das Branch & Bound-Verfahren liefert eine optimale Lösung für kombinatorische Optimierungsprobleme, ohne den Aufwand vollständiger Enumeration zu betreiben, indem während der Problemzerlegung im Rahmen einer Verzweigung des Ausgangsproblems geprüft wird, an welchen Stellen auf eine weitere Verzweigung verzichtet werden kann. ⇒ Ersetzung einer vollständigen Enumeration durch eine begrenzte Enumeration der Lösungsmenge (= implizite Enumeration) ohne Optimalitätseinbuße. Grundidee: Die implizite Enumeration nach dem Branch & Bound-Verfahren basiert auf der gemeinsamen Anwendung zweier Prinzipien (nämlich Branching und Bounding): (1)

Branching Sukzessive Zerlegung des Ausgangsproblems P0 in Teilprobleme, indem die entsprechende zulässige Lösungsmenge X(P0) in Teilmengen zerlegt wird. ⇒ Wiederholtes Zerlegen (Verzweigen) erzeugt einen Lösungsbaum von Problemen:

Teilproblem 2

P0 P2

P1 P3

P4

Teilproblem 1

Produktion und Logistik

(2)

PW / OR WS 06/07

5-17

Bounding für Maximierungs- und Minimierungsprobleme Ermittlung von oberen bzw. unteren Schranken für die Zielfunktions- (ZF)-Werte der bei Zerlegung entstehenden Teilprobleme zur Prüfung, ob die weitere Zerlegung abgebrochen werden kann.

Z bzw. Z : untere bzw. obere ZF-Schranke für Ausgangsproblem P0 Z i bzw. Z i : obere bzw. untere ZF-Schranke für Teilproblem Pi

Abbruchkriterium für Weiterzerlegung von Teilproblem Pi bei Max-Aufgabe : Z i < Z

bei Min-Aufgabe : Z i > Z

Teilproblem 2

Teilproblem 1

Produktion und Logistik

PW / OR WS 06/07

5-18

Schrankenermittlung beim Bounding Schrankenermittlung für Teilprobleme Pi ( ⇒ ZF-Schranken für Lösungsverbesserung) erfolgt ' durch Bildung und Lösung eines vereinfachten (sog. relaxierten) Problems Pi , indem Nebenbedingungen gelockert oder weggelassen werden, so dass gilt: X (Pi ) ⊂ X (Pi ' )

Standardvorgehensweise zur Relaxation ist bei ganzzahligen LOP’s das Weglassen der Ganzzahligkeitsbedingungen (LOP-Relaxation). ' Der Zielfunktionswert des relaxierten Problems Pi ist mindestens genauso gut, wie der Zielfunktionswert des Problems Pi und führt bei

Max-Aufgaben zur Obergrenze Z i

Min-Aufgaben zur Untergrenze Z i

Schrankenermittlung für das Ausgangsproblem P0 ( ⇒ ZF-Schranke für Lösungsverschlechterung) erfolgt zu Beginn der Verzweigung durch Anwendung einer Heuristik zum Finden einer zulässigen Lösung oder durch Vorgabe von Z = −∞

bei Max-Aufgabe

Z = +∞

bei Min-Aufgabe

Im Laufe der Verzweigung wird diese Schranke durch den ZF-Wert der jeweils besten gefundenen zulässigen Lösung des Ausgangsproblems ersetzt. Heuristiken können genutzt werden, um eine bessere Schranke für P0 zu finden.

Produktion und Logistik

PW / OR WS 06/07

5-19

Abbruch der Weiterverzweigung Ein Teilproblem braucht nicht weiter verzweigt zu werden, wenn eine weitere Zerlegung keine zusätzliche Information über die optimale Lösung mit sich bringen kann. Ein solches Teilproblem heißt ausgelotet. Hierbei sind 3 Fälle zu unterscheiden.

Fall (a) Die optimale Lösung des Teilproblems ist schlechter als die beste bekannte zulässige Lösung. Fall (b) Die optimale Lösung des relaxierten Teilproblems ist zulässig für das Ausgangsproblem (z.B. ganzzahlig bei LOP-Relaxation) und ist besser als die beste bekannte zulässige Lösung. Fall (c) Das relaxierte Teilproblem besitzt keine zulässige Lösung, so dass dasselbe auch für das nicht-relaxierte Teilproblem gelten muss. Min-Aufgabe Fall Max-Aufgabe (a) Z i < Z Zi > Z (b) Z i > Z und Lösung von Pi ' Z i < Z und Lösung von Pi ' ist zulässig für P0 ist zulässig für P0 ⇒ Z = Zi ⇒ Z = Zi (c) X (Pi ' ) = ∅ ⇒ X (Pi ) = ∅ X (Pi ' ) = ∅ ⇒ X (Pi ) = ∅

Produktion und Logistik

PW / OR WS 06/07

5-20

Freiheitsgrade beim Branching • Reihenfolge der Auswahl von zu zerlegenden Problemen, z.B. ⇒ Tiefensuche ¾ LIFO-Regel: ⇒ Breitensuche ¾ FIFO-Regel: ¾ MUB/MLB-Regel : Maximum Upper Bound/Minimum Lower Bound-Regel • Zerlegungsmöglichkeit bei der Bildung von Teilproblemen, z.B. ¾ Wahl der Variablen mit größtem oder kleinsten nicht-ganzzahligen Anteil bei LOPRelaxation. • Reihenfolge der Untersuchung der Teilprobleme, z.B. ¾ aufsteigende oder absteigende Bearbeitungsreihenfolge ¾ gerundeter Wert zuerst oder zuletzt

Produktion und Logistik

PW / OR WS 06/07

5-21

Beispiel zum Branch and Bound-Verfahren Regeln FIFO, kleinster Abstand zur nächsten ganzen Zahl, aufsteigende Bearbeitungsreihenfolge Ausgangsproblem P0 Maximiere Z ( x1 , x2 ) = x1 + 2 x2

unter den Nebenbedingungen x1 + 3x2 ≤ 7

3x1 + 2 x2 ≤ 10 x1 , x2 ≥ 0 und ganzzahlig

(2) (1) (2) (1)

Produktion und Logistik

PW / OR WS 06/07

Graphische Lösung des relaxierten Ausgangsproblems P0’ Schnittpunkt der Restriktionen (1) und (2)

(2) P0

(1)

Branching: P0 wird verzweigt nach x1 und zerlegt in P1 und P2

5-22

Produktion und Logistik

PW / OR WS 06/07

Zerlegung und graphische Lösung von P1’ (P0’ mit zusätzlicher Restriktion x1 ≤ 2)

(2) P1

P0 (1)

5-23

Produktion und Logistik

PW / OR WS 06/07

Graphische Lösung von P2’ (P0’ mit zusätzlicher Restriktion x1 ≥ 3)

(2) P1

P0 (1) P2

Nach FIFO-Regel wird nun P1 nach x2 weiter verzweigt, und zerlegt in P3 und P4.

5-24

Produktion und Logistik

PW / OR WS 06/07

Zerlegung und graphische Lösung von P3’ (P1’ mit zusätzlicher Restriktion x2 ≤ 1)

(2) P1

P0

P3

(1) P2

5-25

Produktion und Logistik

PW / OR WS 06/07

Graphische Lösung von P4’ (P1’ mit zusätzlicher Restriktion x2 ≥ 2)

(2) P 4

P1

P0

P3

(1) P2

Optimale (ganzzahlige Lösung): x1*=1, x2*=2, Z*=5

5-26

Produktion und Logistik

PW / OR WS 06/07

5-27

5.3 Heuristische Lösungsverfahren Lokale Suchverfahren am Beispiel der Dynamischen Losgrößenplanung Suchprinzip • Start mit einer zulässigen Ausgangslösung • Definition einer `Nachbarschaft´ NBS(x) zu einer gegebenen Lösung x • Iterative Lösungsveränderung durch Übergag von einer Lösung x zu einer Nachbarlösung x' ∈ NBS (x) mit dem Ziel der Lösungsverbesserung • Abbruch wenn keine Lösungsverbesserung durch Nachbarschaftssuche mehr möglich ist Prüfvarianten bei Nachbarschaftssuche • vollständige Prüfung von NBS(x) • eingeschränkte Prüfung

: :

Best fit-Strategie First fit-Strategie (Prüfreihenfolge wichtig!)

Produktion und Logistik

PW / OR WS 06/07

5-28

Verfahren lokaler Suche am Beispiel der Dynamische Losgrößenplanung (S. 4-55) Daten:

T = 6,

t Bt

f = 100, l = 1,

y0 = 0

1

2

3

4

5

6

∑

25

70

60

50

40

5

250

Variablen: qt : Losgröße in Periode t yt : Lagerbestand am Ende von Periode t ⎧1 , wenn in Periode t ein Los aufgelegt wird xt = ⎨ ⎩0 , sonst

Produktion und Logistik

PW / OR WS 06/07

5-29

Anwendung des Suchverfahrens • Zulässige Startlösung (z.B. maximale Losbildung) x10 = 1 , x20 = x30 = x40 = x50 = x60 = 0 bzw. als Binärzahlfolge 0 x0 : 1 0 0 0 0 0 → q : 250 0 0 0 0 → y : 225 155 95 45 Kosten:

0

0

5

0

K (x0 ) = 100 ⋅1 + 1⋅ (225 + 155 + 95 + 45 + 5) = 625

• Nachbarschaftsdefinition : NBS(x) Menge aller zulässigen Binärzahlfolgen mit genau einem Binärzahlwechsel

NBS(x0) x1 x2 x3 x4 x5

: : : : :

1 1 1 1 1

1 0 0 0 0

0 1 0 0 0

0 0 1 0 0

0 0 0 1 0

0 0 0 0 1

Produktion und Logistik

PW / OR WS 06/07

5-30

• Iterative Suche

Auswertung • Nur 10 von 32 (= 25) möglichen Lösungen durchsucht! • Optimale Lösung opt

x : 1

1

0

1

0

0

mit K opt = 410 nicht gefunden!

Produktion und Logistik

PW / OR WS 06/07

5-31

Problematik des Verfahrens lokaler Suche • Existenz mehrerer lokaler Optima

• Hilfsstrategien zur (globalen) Optimumsuche ƒ Wiederholungen mit unterschiedlichen Startlösungen ƒ Wiederholungen mit unterschiedlichen (u.U. zufälligen) Suchreihenfolgen (bei First fit-Strategie) ƒ Anwendungen von Local Search-Verfahren (i.e.S.) mit Möglichkeit vorübergehender Lösungsverschlechterung

Produktion und Logistik

PW / OR WS 06/07

• Lösungssuche bei geänderter Startlösung (hier : bedarfssynchrone Losbildung)

Auswertung: • 16 von 32 möglichen Lösungen durchsucht und optimale Lösung gefunden!

5-32

Produktion und Logistik

PW / OR WS 06/07

6-1

6 Weitere Anwendungen und Gebiete des Operations Research

Produktion und Logistik

6.1 Überblick ¾ Nicht-lineare Optimierung ¾ Dynamische Optimierung ¾ Graphentheorie ¾ Netzplantechnik ¾ Warteschlangentheorie ¾ Simulation

PW / OR WS 06/07

6-2

Produktion und Logistik

PW / OR WS 06/07

6-3

6.2 Nicht-lineare Optimierung Aufgabe Lösung von Optimierungsproblemen bei nichtlinearen Zusammenhängen zwischen den betrachteten ökonomischen Größen, z.B. • Skaleneffekte • nichtlineare Preis-Absatz-Funktionen Allgemeines Problem

Konvexes Problem

Produktion und Logistik

PW / OR WS 06/07

6-4

Beispiel aus Hauptübung: Wyndor Glass mit Preis-Absatz-Funktion Gegeben: • 2 Produkte mit variablen Kosten und Preis-Absatz-Funktionen: Preis-Absatz-Funktion variable Produktionskosten

Produkt 1 p1(x1) = 18 – x1 10

• 3 Ressourcen (Kapazitätsbeschränkungen) Kapazitätsausnutzung je ME in Stunden Anlage Produkt 1 Produkt 2 1 1 0 2 0 2 3 3 2

Produkt 2 p2(x2) = 22 – x2 12

Verfügbare Kapazität (in Stunden) 4 12 18

Zielfunktion (Gesamtdeckungsbeitrag): Z = p1(x1) · x1 – 10x1 + p2(x2) · x2 – 12x2 = (18 – x1) · x1 – 10x1 + (22 – x2) · x2 – 12x2 = 8 · x1 – x12 + 10 · x2 – x22 Nebenbedingungen:

≤

x1 2x 2 3x1

+ 2x 2

x1 , x 2 ≥ 0

4 (1) ≤ 12 (2) ≤ 18 (3)

Produktion und Logistik

Unbeschränktes Optimum: x1 = 4, x2 = 5 ist nicht zulässig

Verfahren zur Lösung von Problemen der nichtlinearen Optimierung: • Auswertung der Kuhn-TuckerBedingungen • Methoden der zulässigen Richtungen bei konvexen Optimierungsproblemen • Quadratische Optimierung

PW / OR WS 06/07

6-5

Produktion und Logistik

PW / OR WS 06/07

6-6

6.3 Dynamische Optimierung Aufgabe Lösung von Optimierungsproblemen mit einer Folge von unabhängigen Entscheidungen. Das Entscheidungsproblem wird hier in mehrere Stufen (Perioden) unterteilt wobei auf jeder Stufe nur die dort relevanten Zustände und Alternativen betrachtet werden. Beispiele für als Dynamisches Optimierungsproblem modellierbare Aufgabenstellungen:

• Dynamische Losgröße • Rucksackproblem • Investitionsentscheidungen

Produktion und Logistik

PW / OR WS 06/07

Beispiel 1: Investitionsentscheidungen

Stufen: Zustände: Entscheidungen:

Perioden Kapazitäten, Markterwartungen Investition/Desinvestition

6-7

Produktion und Logistik

Beispiel 2: Rucksackproblem Daten: 1 2 3 subjektiver Nutzen 3 4 2 Gewicht 3 2 4 Maximalgewicht: 9

PW / OR WS 06/07

4 3 1

6-8

Optimierungsproblem: Maximiere Z = 3 x1 + 4 x2 + 2 x3 + 3 x4 u.d.N.:

3 x1 + 2 x2 + 4 x3 + x4 ≤ 9 xk ∈ {0,1} für k = 1,..., 4

Stufen: Objekte Zustände: Restkapazitäten Entscheidungen: Mitnahme/Nichtmitnahme

Lösungsmethodik: Vorwärts-/Rückwärtsrekursion

Quelle: Domschke & Drexl, Einführung in Operations Research, 6.Auflage, S. 166

Produktion und Logistik

PW / OR WS 06/07

6-9

6.4 Graphentheorie Aufgabe Beschreibung realer Sachverhalte und Entscheidungsproblemen durch Graphen und Analyse und Optimierung, z.B.: Ermittlung kürzester Wege, Aufbau von Kommunikationsnetzen, Rundreiseproblem Graphen • Knoten • Kanten/Pfeile • Bewertungen

Quelle: Domschke & Drexl, Einführung in Operations Research, 6.Auflage, S. 68

Produktion und Logistik

PW / OR WS 06/07

Beispiel für Suche nach kürzestem Weg Stadtplan:

6-10

Unfallstelle

Straßenbahn

Rettungsstation

Modell und Baum kürzester Wege ermittelt z.B. mit dem Dijkstra-Algorithmus

Quelle: Domschke & Drexl, Einführung in Operations Research, 6.Auflage, S. 73

Produktion und Logistik

PW / OR WS 06/07

Beispiel für den Aufbau von Kommunikationsnetzen (Minimal spannender Baum) Aufgabe: Entfernungsminimale Versorgung der Haushalte ausgehend von Knoten 1

Quelle: Domschke & Drexl, Einführung in Operations Research, 6.Auflage, S. 68 und 69

6-11

Produktion und Logistik

PW / OR WS 06/07

6-12

6.5 Netzplantechnik Aufgabe Planung und Steuerung von zeitlich und sachlich abgegrenzten komplexen Vorhaben, z.B. Anlagenbau (Einzelfertigung), Ressourceneinsatzplanung, F&E-Projekte, Organisation von Großveranstaltungen, Projektmanagement Vorgehensweise • Strukturplanung: Ermittlung von Aktivitäten/Vorgänge, Reihenfolgebeziehungen, Vorgangsdauern, Kapazitätsnutzung u.s.w. • Zeitplanung: Ermittlung frühester und spätester Beginn- und Endzeitpunkte sowie der minimalen Projektdauer, Bestimmung von Zeitreserven (Pufferzeiten) sowie der zeitkritischen Tätigkeiten (kritischer Weg) • Kapazitäts- und Kostenplanung: Kapazitätsausgleich und Kostenminimierung

Produktion und Logistik

PW / OR WS 06/07

Beispiel zur Netzplantechnik (Zeitplanung mit CPM, Critical Path Method) Gegeben: Aufgabenzerlegung und Strukturplan (Netzplan)

Quelle: Schneeweiß S. 183, 184

6-13

Produktion und Logistik

PW / OR WS 06/07

6-14

Gesuchte Größen: FAZj : FEZj : SAZj : SEZj : GPj :

frühestmöglicher Anfangszeitpunkt der Tätigkeit j frühestmöglicher Endzeitpunkt der Tätigkeit j spätestzulässiger Anfangszeitpunkt der Tätigkeit j spätestzulässiger Endzeitpunkt der Tätigkeit j Gesamtpufferzeit, d.h. maximale Zeitreserve für Verschiebung der Tätigkeit j

Vorgehensweise  Schritt (1) : Vorwärtsrechnung FAZ0 = 0

FAZ j = max { FEZ k } k∈V j

FEZj = FAZj + dj

mit Vj Menge der direkten Vorgänger von j

SAZj = SEZj – dj

mit Nj Menge der direkten Nachfolger von j

 Schritt (2) : Rückwärtsrechnung

{SAZ k } SEZn = FEZn SEZ j = max k ∈N j

 Schritt (3) : Ermittlung der Gesamtpufferzeiten GPj

=

SEZj – FEZj

=

SAZj – FAZj

 Schritt (4) : Ermittlung des kritischen Weges Kritischer Weg = Zusammenhängende Folge der Tätigkeiten mit Gesamtpufferzeit von Null

Produktion und Logistik

PW / OR WS 06/07

Beispiel Projekt „Lagerhalle“ : Zeitplanung Tätigkeit Dauer FAZ FEZ SAZ SEZ GP Kritisch? 0 (Start) 0 1 2 2 5 3 8 4 4 5 2 6 2 7 1 8 3 9 2 10 1 11 4 12 (Abnahme) 1

6-15

Produktion und Logistik

PW / OR WS 06/07

6-16

6.6 Warteschlangentheorie Aufgabe Analyse des Abfertigungsverhaltens und Dimensionierung von Service- und Bedienstationen (z.B. Call Center, Bankschalter, Mensa) unter Berücksichtigung stochastischer Einflüsse (z.B. Kundenankunft, Bediendauer)

Quelle: Campusmagazin der Universität Darmstadt

Kenngrößen • (mittlere) Schlangenlänge (Anzahl der Kunden im Warteraum) • (mittlere) Systemlänge (Anzahl der Kunden im System) • (mittlere) Wartezeiten und Verweilzeiten der Aufträge oder Kunden • (mittlere) Auslastung der Abfertigungskapazität

Produktion und Logistik

PW / OR WS 06/07

6-17

Vorgehensweise und Beispiel • Analytisch in einfachen Fällen (einfache Systeme und weiterer vereinfachender Annahmen): Einkanalmodell:

Paralleles Mehrkanalmodell:

Serielles Mehrkanalmodell:

Quelle: Domschke & Drexl, Einführung in Operations Research, 6.Auflage, S. 221

• Simulation

Produktion und Logistik

PW / OR WS 06/07

6-18

6.7 Simulation Aufgabe Untersuchung von komplexen (stochastischen) Systemen, wobei der Wirkungsmechanismus des Systems durch die Abbildung einzelner Komponenten und der Abhängigkeiten zwischen den Komponenten. Bsp.: komplex vernetztes Warteschlangensystem Analytische Lösung vs. Simulation: ƒ numerische Berechnungen und ƒ Schätzung der Model-Performance „Methode des letzten Auswegs“ Anwendungsgebiete in Produktion und Logistik Bestandsmanagement, Projektplanung, Warteschlangensysteme (z.B. Call-Center), Produktionssteuerung, Kommissionier-/Lagersysteme

Produktion und Logistik

PW / OR WS 06/07

Simulationsmodell einer Abfüllanlage (Visualisierung)

6-19

Produktion und Logistik

PW / OR WS 06/07

Simulationsmodell einer Abfüllanlage (Modelllogik)

6-20

1 von 8

Klausur: 5012 Prüfung: BWL B (Produktionswirtschaft und Operations Research) WS 2005/06 Prüfer:

Prof. Dr. Karl Inderfurth

Prüfungsbogen Vom Klausurteilnehmer auszufüllen! Name, Vorname

:

Fakultät

:

Matrikelnummer

:

Hinweise: Verwenden Sie für Ihre Berechnungen (sofern notwendig) das beiliegende Schmierpapier und tragen Sie anschließend das gesuchte Ergebnis in der dafür vorgesehenen Stelle unterhalb der Aufgabenstellung in den Prüfungsbogen ein. Es werden nur die Eintragungen im Prüfungsbogen bewertet. Sowohl der Prüfungsbogen als auch das Schmierpapier sind nach dem Ende der Klausur mit Namen, Fakultät und Matrikelnummer beschriftet abzugeben. Alle Aufgaben sind zu bearbeiten. Dieser Klausurteil besteht aus 8 Seiten. Bemerkung zu den Multiple-Choice-Aufgaben: Korrekt gesetzte Kreuze erhalten eine positive Punktzahl. Falsche Antworten werden negativ bewertet und innerhalb von Teilaufgaben mit Richtigen verrechnet. Zugelassene Hilfsmittel: Nicht-programmierbare Taschenrechner ohne Kommunikationsoder Textverarbeitungsfunktion.

Punkteverteilung: Aufgabe 1: Aufgabe 2: Aufgabe 3: Aufgabe 4: insgesamt:

20 18 14 8 60

Punkte Punkte Punkte Punkte Punkte

Nur für den Prüfer

Aufgabe Punkte

1

2

3

4

insgesamt

2 von 8 Aufgabe 1: Allgemeines (20 Punkte) (a)

Untersuchen Sie, ob für die folgenden Produktionsfunktionen bei Vorgabe der Produktionsmengen Limitationalität oder (totale bzw. partielle) Substitutionalität der Faktoren vorliegt! keine partielle totale Limitationalität Aussage Substitutionalität Substitutionalität möglich y3 = 8 ⋅ x1 ⋅ x2 … … … … y3 = 2 x1 + 5 x2 … … … … x1 = 5 ⋅ y3 , x2 = 3 ⋅ y3 … … … …

(b)

Nennen Sie ein Softwaretool zur Lösung linearer Optimierungsprobleme!

(c)

Das Verfolgen einer Synchronisationsstrategie in der mittelfristigen Produktionsprogrammplanung ... wahr falsch … … ... vermeidet Lagerbestände so weit wie möglich. … … ... vermeidet Überstunden so weit wie möglich. … … ... führt zu einer konstanten Produktion. … … ... optimiert die Kapazitätsauslastung.

(d)

Bei programmorientierter Materialbedarfsplanung benötigt man folgende Informationen über die einzelnen Materialien: wahr falsch … … Anfangsbestände … … Erzeugnisstrukturen … … Vergangenheitsbedarfe … … Produktionsprogrammdaten

(e)

Im Modell der statischen Losgrößenplanung gilt: Die Losgröße erhöht sich proportional zur Anzahl der Losauflagen pro Zeiteinheit. Der Bedarf wächst pro ZE mit konstanter Rate. Die optimale Losgröße hängt nicht von den Fixkosten der Beschaffung ab. Der Planungshorizont ist unbegrenzt.

(f)

wahr

falsch

…

…

…

…

…

…

…

…

Der jährliche Materialbedarf in Höhe von 50 Stück wird in Losen der Größe q beschafft. Je Bestellung fallen Fixkosten in Höhe von 250€ sowie Stückkosten von 100€ an. Die Lagerhaltungskosten betragen 10€ je Stück und Jahr. Die optimale Losgröße (gerundet auf die nächstliegende ganze Zahl) beträgt: … 25

… 35 … 50 … 100 … 141 … 200 … keine der Vorgaben sondern _____

3 von 8

(g)

Drei Systeme zur Güterproduktion (A), (B) und (C) mit linearer Technologie sind durch folgende Technologiematrizen beschrieben: System (A) : ⎡-2 ⎢0 MA = ⎢ ⎢1 ⎢ ⎣⎢ 1

0⎤ -2 ⎥ ⎥ 1⎥ ⎥ 1 ⎦⎥

System (B) : ⎡ 1 −3 −2 ⎤ ⎢ −4 2 0 ⎥ ⎥ MB = ⎢ ⎢ 3 0 −1⎥ ⎢ ⎥ ⎣0 0 1⎦

System (C) : ⎡ −8 −3⎤ ⎢ −1 −2 ⎥ ⎥ MC = ⎢ ⎢ 0 −1⎥ ⎢ ⎥ ⎣2 1⎦

Geben Sie für jedes der drei Produktionssysteme vollständig an, welche der genannten Technologietypen jeweils zutreffen! System (A) …

System (B) …

System (C) …

2. outputseitig determiniert

…

…

…

3. Verfahrenswahl bei Faktornutzung

…

…

…

4. elementar

…

…

…

5. allgemein nicht elementar

…

…

…

6. einstufig

…

…

…

7. mehrstufig

…

…

…

8. Verfahrenswahl bei Produktherstellung

…

…

…

9. inputseitig determiniert

…

…

…

Eigenschaft 1. zyklisch

(h)

Geben sie den Wahrheitswert der folgenden Aussagen an: wahr falsch Jede konvexe Technologie ist eine lineare Technologie.

…

…

Konvexe Technologien lassen die Möglichkeit der Verschwendung grundsätzlich zu. Bei Produktion mit Verfahrenswahl bei Faktornutzung lassen sich die Outputmengen als eindeutige Funktion der Inputmengen beschreiben. Jede konvexe Linearkombination effizienter Grundaktivitäten führt zu einer effizienten Aktivität.

…

…

…

…

…

…

4 von 8 Aufgabe 2: Lineare Optimierung (18 Punkte) (a)

Bei Lösung eines Maximierungsproblems (LOP1) erhalten sie folgendes Simplextableau.

BV

x1

x2

x3

x4

bi

x3 x4

-1 2

-2 1

1 0

0 1

-5 5

Z

5

-4

0

0

0

Führen Sie eine Iteration des Simplexalgorithmus durch und tragen Sie das Ergebnis in das folgende Tableau ein.

BV

bi

-Z

(b)

Gegeben ist das folgende Lineare Optimierungsproblem (LOP2): Maximiere Z = -2 x1 - 4 x2 unter den Nebenbedingungen: x1 + 2 x2 ≤ 8 x1 + x 2 ≥ 4 2 x1 + 3 x2 ≥ 10 x1 , x2 ≥ 0

(1) (2) (3)

Das Optimal-Tableau lautet:

BV

x1

x2

x3

X4

x5

bi

x3

0

½

1

0

½

3

x4

0

½

0

1

-½

1

x1

1

3/2

0

0

-½

5

Z

0

1

0

0

1

-10

(b1) In welchem Intervall kann der zu x2 gehörende Zielfunktionskoeffizient schwanken, ohne dass sich die optimalen Basislösung ändert?

5 von 8 (b2) Wie hoch ist der Zielfunktionswert, wenn die zweite Nebenbedingung wie folgt lautet: x1 + x2 ≥ 5

(b3) In welchem Intervall kann der Restriktionskoeffizient der ersten Nebenbedingung schwanken, ohne dass sich die Struktur der optimalen Basislösung ändert?

(b4) Formulieren Sie das zum obigen LOP2 duale Problem! Definieren Sie hierfür geeignete Entscheidungsvariablen.

(b5) Geben Sie die Optimalwerte der Strukturvariablen sowie den optimalen Zielfunktionswert des in (b4) formulierten dualen Problems an!

6 von 8 Aufgabe 3: Materialbedarfsplanung (14 Punkte) Gegeben ist der folgende Gozinto-Graph: 3 E1

2 P4

B3 1

4 E2 (a)

Klassifizieren Sie das durch den Gozinto-Graphen beschriebene Produktionssystem möglichst vollständig hinsichtlich aller Ihnen bekannten Typen von Technologien.

(b)

Geben Sie zu dem dargestellten Produktionssystem die Direkt- und Gesamtbedarfsmatrix an.

G=

A=

(c)

Auf welcher Dispositionsstufe ist das Material E2 zu disponieren? …0

(d)

…1

…2

…3

…4

…5

Führen Sie eine Materialbedarfsplanung nach dem Dispositionsstufenverfahren über 3 Perioden (t=1,...,3) durch, wenn für das Endprodukt P4 und für die Baugruppe B3 folgende Primärbedarfe vorliegen und jeweils eine Periode Durchlaufzeit anzusetzen ist? Die Anfangsbestände sind ebenfalls aus der Tabelle zu entnehmen. Primärbedarf t=1 P4 10 B3 5 E2 E1

t=2 20 10

t=3 10 10

Anfangsbestand 20 40 100 50

Führen Sie die Berechnung nur für die Dispositionsstufen 0 und 1 durch!

7 von 8

Dispositionsstufe / disponiertes Produkt

(e)

Periode

1

2

3

Zeileninhalt

Geben Sie den Wahrheitswert der folgenden Aussagen an. Im Rahmen des Dispositionsstufenverfahrens gilt für jedes Erzeugnis einer Baukastenstückliste: Der Bruttobedarf ist nicht kleiner als der Nettobedarf. Der Primärbedarf ist nicht kleiner als der Sekundärbedarf. Der Lagerbestand ist stets größer als Null. Dispositionsstufe ≥ Fertigungsstufe

wahr … … … …

falsch … … … …

8 von 8 Aufgabe 4: Zuordnungsproblem (8 Punkte) Der Lehrstuhlleiter hat die Aufgabe, den drei Lehrkräften I, K und L die Aufgaben Vorlesung (V), Hauptübung (H) und Internationales Programm (IP) zuzuordnen. Jede Lehrkraft soll dabei genau eine Aufgabe übernehmen. Aus den Erfahrungen der Vergangenheit hat sich die folgende Einschätzung bezüglich der Qualifikation der einzelnen Lehrkräfte für die Aufgaben herausgebildet. V H IP 5 5 5 I 4 2 K 3 3 5 L 3 Ziel ist es, eine Zuordnung zu finden, welche die Summe der Einschätzungen maximiert. (a)

Formulieren Sie zur Lösung der oben beschriebenen Aufgabe mit den dort gegebenen Daten ein LP-Modell unter Angabe und Erläuterung von Entscheidungsvariablen, Zielfunktion und allen Nebenbedingungen.

(b)

Geben Sie den Wahrheitswert der folgenden Aussagen an. Im obigen Zuordnungsproblem gilt: Aufgrund der Ganzzahligkeitsbedingungen lässt sich das lineare Zuordnungsproblem nicht mit dem Simplex-Verfahren lösen. Zur Lösung eignen sich grundsätzlich alle Lösungsverfahren des Klassischen Transportproblems. Die Anwendung der Nordwesteckenregel liefert stets eine optimale Lösung.

wahr

Falsch

…

…

…

…

…

…