QTDS3001 – Operations Research

Einführung
• Definition
• Anwendungsbereiche des OR
• Modelle in Operation Research
• Teilgebite des OR

Vorlesung 1 1
Definition

Operations Research (kurz: OR, auch: Unternehmensforschung) dient der

Entscheidungsvorbereitung im Rahmen des Planungsprozesses. OR arbeitet stets
mit Modellen, so dass eine enge Verbindung vor allem zur modellgestützten
Planung besteht. Hierbei fließen quantifizierbare Informationen (Daten) in die
Optimierung eines oder mehrerer operational formulierbarer Ziele ein.

Zur Formulierung der Modelle, zur Optimierung der Zielerreichung und damit zur
Lösung der Modelle bedient sich das OR mathematischer Methoden.

Vorlesung 1 2
Anwendungsbereiche des OR
Der Ursprung des OR findet sich in den Jahren kurz vor und während des 2.
Weltkrieges in Großbritannien und den USA. Seine Aufgabe bestand in dieser Zeit
primär in der Planung militärischer Aufgaben.

Nach dem 2. Weltkrieg widmete sich das OR der Analyse und Lösung
wirtschaftlicher und anderer Planungsprobleme. Heute wirkt das OR in
verschiedene wissenschaftliche Disziplinen und praktische Anwendungsgebiete
hinein.

Enge Verbindungen bestehen insbesondere zu Mathematik,

Wirtschaftswissenschaften und Informatik. Anwendung finden Konzepte des
OR vor allem in der Logistik und Produktion, aber auch im Projektmanagement
und Controlling.

Vorlesung 1 3
Modelle in Operation Research

Ein Modell ist ein vereinfactes Abbild eines realen Systems oder Problems.
Modelle spilen im OR eine zentrale Rolle. OR benützt im Wesentlichen
Entscheidunds- bzw. Optimierungs- sowie Simulationsmodelle.

Ein Optimierungsmodell ist eine formale Darstellung eines Entschedungs- oder

Plannungproblems, das in seiner einfachsten Form mindestens eine
Alternativenmenge und eine diese bewertende Zielfunktion enthält. Es wird
entwickelt, um mit geeigneten Verfahren optimale oder suboptimale Lösungen
finden zu können.

Simulationsmodelle sind häufig sehr komplexe Optimierungsmodelle für die

keine analytischen Lösungen existieren. Sie dienen dem Zweck die
Konsequenzen einzelner Alternativen zu bestimmen.

Vorlesung 1 4
Optimierungsmodelle
Ein Optimierungsmodelle lässt sich allgemein wie folgt aufschreiben :

Maximiere oder minimiere z = F 𝒙

unter den Nebenbedingungen

≥
𝑔! 𝒙 = 0 für i= 1, …, m
≤

𝒙 ∈ 𝑊" × 𝑊# × ⋯ …× 𝑊$ . 𝑊% ∈ 𝑅& , 𝑍&, 𝐵 j= 1, ….., n

𝒙 ein Variablenvektor mit n Komponenten 𝑥" , … … , 𝑥$

F 𝒙 eine Zielfunktion
𝑥% ∈ 𝑅& nichtnegativitetsbedingung (kontinuerliche Variable)
𝑥% ∈ 𝑍& Ganzzahligkeitsbedingung (ganzzahlige Variable)
𝑥% ∈𝐵 Binärbedingung (binäre Variable)

Vorlesung 1 5
F 𝒙 entspricht einer Zielfunktion die maximiert or minimiert werden soll.
Bei zu maximierenden Größen kann es z.B. um den Absatz, den Umsatz
oder den Gesamtdeckungsbeitrag handeln, der seitens eines
Unternehmens mit einem Produktvektor zu erzielen ist. Veralgemeinernd
sprechen wir gelegentlich von zu maximierenden Nutzen.

Bei zu minimierenden Größen handelt es sich um Distanzen in

Verkehrsnetzen, Projectdauern in Netplänen, zumeist aber um Kosten.

≥
𝑔! 𝒙 = 0 für i= 1, …, m ist ein System von m Gleichungen oder
≤
Ungleichungen.
𝑥 ∈ 𝑊" × 𝑊# × ⋯ …× 𝑊$ . 𝑊% ∈ 𝑅& , 𝑍&, 𝐵 j= 1, ….., n
legt den Wertebereich der Entscheidungsvariablen fest. Jede variable hat
einen kontinuierlichen, ganzzahligen oder binären Wertebereich.

Vorlesung 1 6
Beispiel

Ein Modell der Produktionsprogrammplannung

Gegeben seien die Priese 𝑝% , die variablen Kosten 𝑘% und damit die
Deckungsbeiträge 𝑑𝑏% = 𝑝% − 𝑘% von n Produkten 𝑗 (=1,…,n) sowie die
technischen Produktionskoeffizienten 𝑎!% die den Verbrauch an Kapazität
von Maschine 𝑖 für die Herstellung einer Einheit von Produkt 𝑗 angeben.
Maschine 𝑖 (= 1,…, m) möge eine Kapazität von 𝑏! Kapazitätseinheiten
besitzen. Gesucht sei das Produktionsprogramm mit maximalem
Deckungsbeitrag.

Bezeichnen wir die von Produkt 𝑗 zu fertigenden Mengeneinheiten (ME)

𝑥% so ist das folgende mathematische Modell zu lösen :

Maximiere ∑$%(" 𝑑𝑏% 𝑥%

unter den Nebenbedingungen

∑$%(" 𝑎!% 𝑥% ≤ 𝑏! für 𝑖 = 1, …., m

𝑥% ≥ 0 für 𝑗 = 1, ….., n
Vorlesung 1 7
Beispiel

Ein binäres Optimierungsmodell , das Knapsack-Problem

Ein Wanderer kann in seinem Rucksack unterschiedlich nützliche Güter

verschiedenen Gewichts mitnehmen. Welche soll er auswählen so dass
bei einem einzuhaltenden Höchstgewict maximaler Nutzen erzielt wird ?

Allgemein stehen n Gegenstände (𝑗 = 1, …., n) mit den Nutzen 𝑐% und

Gewichten 𝑤% zur Wahl. Das Höchstgewicht der mitnehmbaren
Gegenstände sei b. Verwenden wir für Gut j die Binärvariable 𝑥% (= 1 ,
falls das Gut mitzunehmen ist und 0 sonst) , so lässt sich das Modell
mathematisch wie folgt formulieren :

Maximiere ∑$%(" 𝑐% 𝑥%

unter den Nebenbedingungen

∑$%(" 𝑤% 𝑥% ≤ 𝑏

𝑥% ∈ 0,1 für j = 1, ….., n

Vorlesung 1 8
Teilgebiete des Operation Research

Lineare Optimierung

Vor allem das Instrumentarium der linearen Optimierung oder auch

linearen Programmierung (LP) hat dem OR zum Aufschwung verholfen. Es
ist der am weitesten entwickelte und wichtigste Teilbereich des OR.

Im Mittelpunkt stehen hier lineare Optimierungsmodelle, zugehörige

Lösungsverfahren, wie z.B. der Simplex-Algorithmus, und die
Dualitätstheorie.

Ein LP-Modell beschreibt ein Optimierungsproblem durch lineare

Zielfunktion(en) und lineare Nebenbedingungen, wobei die
Entscheidungsvariablen beliebige reelle nichtnegative Zahlenwerte
annehmen können.

Vorlesung 1 9
Ganzzahlige und kombinatorische Optimierung

Häufig dürfen die Variablen jedoch nicht jeden beliebigen reellen Wert
annehmen, sondern sind auf Ganzzahligkeit beschränkt. Dies ist z. B.
bei der Bestimmung von Produktionsmengen von Stückgütern oder bei
der Entscheidung über die Annahme oder Ablehnung eines Auftrags
der Fall. Man spricht dann von ganzzahliger Optimierung (auch Integer
Programming (IP)).

Vorlesung 1 10
Darüber hinaus ist eine Vielzahl betriebswirtschaftlicher
Probleme kombinatorischer Natur, d.h. mögliche Lösungen
entstehen durch Kombinieren und Reihen von
Lösungselementen. Dazu gehört z. B. die Festlegung der
Besuchsreihenfolge eines Handelsvertreters bei seinen Kunden,
das Zusammenstellen von Transportaufträgen zu Touren, die
Zuordnung von Personal zu Aufgaben und/oder Schichten
(Personaleinsatzplanung, Personalplanung) oder die Auswahl
von Investitionsalternativen bei gegebenem Investitionsbudget
(Investitionsplanung). Hier ergeben sich meist (gemischt-)
ganzzahlige oder (gemischt-) binäre Optimierungsmodelle, d.h.,
solche mit reellwertigen und ganzzahligen Variablen.

Vorlesung 1 11
Nichtlineare Optimierung

Obwohl die Mehrzahl ökonomischer Entscheidungsprobleme mit Hilfe

eines LP- oder IP-Modells hinreichend gut abgebildet bzw. gelöst
werden kann, erweisen sich die tatsächlichen bzw. empirisch
nachgewiesenen Wirkungszusammenhänge zwischen ökonomischen
Größen i.d.R. als nichtlinear. Beispiele hierfür sind nichtlineare Preis-
Absatz-Funktionen, degressive Kostenfunktionen aufgrund von
Skaleneffekten und die Kapitalwertfunktion. Nichtlineare
Optimierungsmodelle können solche Zusammenhänge explizit
berücksichtigen. Die verfügbaren Lösungsverfahren für nichtlineare
Optimierungsprobleme eignen sich allerdings jeweils nur für bestimmte
Modellklassen und sind nicht allgemein anwendbar.

Vorlesung 1 12
Dynamische Optimierung

Die dynamische Optimierung (DO) ist auf (ganzzahlige oder

kombinatorische) Probleme anwendbar, die so in einzelne Stufen zerlegt
werden können, dass eine stufenweise Optimierung zum Gesamtoptimum
führt . Diese Stufen können z. B. Zeitabschnitte repräsentieren. Dabei ist
die Entscheidung auf jeder Stufe abhängig von der Entscheidung auf der
vorhergehenden Stufe.

Dadurch entsteht eine Folge voneinander abhängiger Entscheidungen. Auf

jeder Stufe wird deren Erfolgsbeitrag separat ermittelt. Das
Gesamtproblem lässt sich auf diese Weise durch eine stufenweise
Optimierung lösen. Im Bereich der DO lässt sich keine
Standardmodellformulierung angeben; es handelt sich um ein allgemeines
Prinzip, das stets problemspezifisch ausgestaltet werden muss.
Anwendungen sind u. a. bei der Bestellmengen- und Losgrößenplanung zu
finden.

Vorlesung 1 13
Stochastische Optimierung

In den Abschnitten zuvor wurde unterstellt, dass alle notwendigen Daten

(Problemparameter und Wirkungszusammenhänge) vollständig und mit
Sicherheit bekannt sind (deterministische Optimierung). Im Gegensatz dazu
dient die stochastische Optimierung zur Planung bei unsicheren Erwartungen.
Anstelle eines einzigen, sicheren Wertes treten bei unsicheren
Modellparametern mehrwertige Informationen oder lediglich mögliche
Wertebereiche. Auch unsichere Wirkungszusammenhänge (stochastische
Nebenbedingungen) und unsichere Bewertungsansätze (stochastische
Zielfunktionen) sind denkbar. Häufig werden deterministische Ersatzmodelle zur
Beurteilung von Lösungen bei vorliegender Stochastik herangezogen. Bekannte
Vorgehensweisen sind hier Fat-Solution-Modelle, deterministische
Ersatzwertmodelle, Chance-Constrained-Modelle oder Kompensationsmodelle.

Vorlesung 1 14
Graphentheorie

In der Graphentheorie werden reale Sachverhalte und Entscheidungsprobleme

durch Graphen und zugehörige Methoden beschrieben, analysiert und optimiert.
Es lassen sich längste bzw. kürzeste Wege, z. B. mit Hilfe des Dijkstra-Algorithmus,
bestimmen und Flüsse durch Netzwerke optimieren. Auch vielfältige
Strukturuntersuchungen sind möglich.

Vorlesung 1 15
Weitere Gebiete des OR

Neben den aufgeführten Bereichen des OR lassen sich weitere Teilgebiete bzw.
Verfahrensklassen identifizieren. Dazu gehören Prognoseverfahren,
Netzplantechnik, Warteschlangentheorie, Simulation und Spieltheorie.

Prognosen ermitteln Informationen über die Zukunft betreffende

Sachverhalte. Sie liefern somit Planungsinformationen und leisten im Rahmen
des OR einen wesentlichen Beitrag zur Entscheidungsvorbereitung.

Die Netzplantechnik dient der Analyse, Planung und Steuerung von Projekten.
Das OR stellt damit dem Projektmanagement ein wichtiges methodisch
fundiertes, graphentheoretisches Konzept zur Entscheidungsfindung im
Projektablauf zur Verfügung.

Vorlesung 1 16
Warteschlangen

Warteschlangen findet man in allen Bereichen des täglichen Lebens und von
Unternehmen. Einige Beispiele sind Kundenschlangen an den Kassen in
Supermärkten, an Bank- und Behördenschaltern, Autoschlangen vor Ampeln oder
Baustellen oder auch Flugzeuge vor der Start- und Landebahn. In der
betrieblichen Praxis findet man aber auch Aufträge vor Bearbeitungsstationen
oder noch nicht ausgeführte Bestellungen in Warteschlangen. Mit Hilfe der
Warteschlangentheorie lassen sich u. a. zu erwartende Schlangenlängen und
Wartezeiten bei einer gegebenen Systemkonfiguration bestimmen. Durch die
Bewertung systematisch variierter Konfigurationen kann so ein geeignetes System
bestimmt werden.

Vorlesung 1 17
Simulation

Für komplexe stochastische Prozesse eignet sich die analytische

Warteschlangentheorie weniger. Hier ist die Simulation vorzuziehen. Sie ist eines
der wichtigsten Teilgebiete des OR für die Praxis. Mit Hilfe von
Simulationsmethoden können komplexe stochastische Problemstellungen
analysiert werden. Durch die Untersuchung von einzelnen Alternativen oder
Systemkonfigurationen werden Entscheidungsmöglichkeiten durchgespielt, wenn
exakte Analysen zu teuer, zu aufwendig oder zu gefährlich sind. Anwendung
findet die Simulation z. B. bei der Analyse von Warteschlangesystemen, Lager-
und Materialflusssystemen oder bei der Auswertung stochastischer Netzpläne.

Vorlesung 1 18
Spieltheorie

Auch die Spieltheorie wird als Teilgebiet des OR verstanden, so dass hier eine
enge Verknüpfung des OR zur Volkswirtschaftslehre entsteht. Sie befasst sich auf
mathematisch-theoretischer Basis mit Wettbewerbssituationen und gibt
Handlungsempfehlungen für Entscheidungen gegnerischer Parteien.

Vorlesung 1 19
QTDS3001 – Lineare Programmierung

Themen:
• Optimierungsprobleme
• Mathematische Programmierung
• Formulierung
• Beispile

Vorlesung 1 20
 Optimierungsprobleme

In einer Optimierungsroblem versucht man, um zu maximieren bzw. minimieren eine

bestimmte Menge, die Zielfunktion genannt wird und die abhängig von einer
endlichen Anzahl der Eingangsvariablen. Diese Variablen können unabhängig
voneinander oder durch eine oder mehrere Einschränkungen verbunden sein.

minimiere 𝑧 = 𝑥"# + 𝑥##

unter bedingungen 𝑥" − 𝑥# = 3
𝑥# ≥ 2

Das Problem ist ein Optimierungsproblem für das Ziel z. Eingabevariablen sind 𝑥!
und 𝑥" , die in zwei Weisen beschränkt sind. 𝑥! − 𝑥" muss gleich 3 und 𝑥# muss
grösser als 2 oder gleich 2 sein. Wir wollen die Werte der Eingabevariablen
finden, die die Summe deren Quadratzahlen unter den Gegebenen bedingungen
minimieren.

Vorlesung 1 21
 Mathematische Programierung

Eine mathematische Programierung ist ein Optimierungsproblem, in dem das Ziel

und die Bedingungen als mathematische Funktionen und funktionalen
Beziehungen gegeben sind. Mathematische Programierung haben die folgende
Form. Jede der m Bedingungen hat eines der drei Zeichen ≤ ≥=.

optimiere 𝑧 = 𝑓(𝑥" , 𝑥# , … … … , 𝑥$ )

unter den bedingungen

𝑔" (𝑥" , 𝑥# , … … … , 𝑥$ ) 𝑏"
𝑔# (𝑥" , 𝑥# , … … … , 𝑥$ ) ≤ 𝑏#
=
≥
𝑔) (𝑥" , 𝑥# , … … … , 𝑥$ ) 𝑏)

Vorlesung 1 22
Eine mathematische Programierung ist eine Lineare Programierung wenn f und
jede g sind linear.

𝑓(𝑥" , 𝑥# , … … … , 𝑥$ ) = 𝑐" 𝑥" + 𝑐# 𝑥# + .............+ 𝑐$ 𝑥$

𝑔! (𝑥" , 𝑥# , … … … , 𝑥$ ) = 𝑎!" 𝑥" +𝑎!# 𝑥# + .............+𝑎!$ 𝑥$

𝑐% und 𝑎!% sind vorgegebene Konstanten. Jede andere Funktion die nicht in dieser
Form ist, ist keine lineare Funktion.

Vorlesung 1 23
Formilierung des Problems

Optimierungsprobleme sind meist verbal angegeben. Die Lösung Verfahren ist das Problem mit
einem mathematischen Problem zu modellieren und das Programm durch die in der Vorlesung
beschriebenen Techniken zu lösen. Folgende Vorgehensweise wird empfohlen für das Umwandeln
eines verbalen Problem in ein mathematisches Problem.

Schritt 1 ; Bestimmen die Menge zu optimieren und stellen sie als eine mathematische
Funktion dar. Dies dient zum Definieren von Eingabevariablen.

Schritt 2 ; Identifizieren Sie alle Anforderungen, Einschränkungen und Begrenzungen und stellen
sie mathematisch dar. Diese Anforderungen sind die Bedingungen.

Schritt 3 ; Stellen jegliche versteckten Bedingungen dar. Solche Bedingungen nicht ausdrücklich
festgelegt, sondern ergeben sich aus der Situation die modelliert wird. In der Regel beinhalten sie
nicht-Negativität oder Ganzzahlige Anforderungen an die Eingangsvariablen.

Vorlesung 1 24
Beispiel I

Eine Metzgerei traditionell macht seinen Hackbraten aus einer Kombination Rind und Lamm. Rindfleisch enthält 80 Prozent Fleisch und 20 Prozent Fett und
kosten 8 Euro pro kg. Lammfleisch enthält 68 Prozent Fleisch und 32 Prozent Fett und kosten 6 Euro pro kg. Wie viel von jeder Art von Fleisch sollte der
Shop verwenden in jedes kg des Hackbratens, wenn sie Ihre Kosten minimieren will und dafür zu sorgen, dass der Fettgehalt des Hackbratens auf nicht
mehr als 25 Prozent ist?

Ziel ist die Minimierung der Kosten der kg des Hackbratens wo z ist gleich 8 mal kg von Rindfleisch plus 6 Mal von kg Lamm verwendet.

Erst definieren wir ;

𝑥! ≡ Rindfieischmenge in einem Kg des Hackbratens,

𝑥" ≡ Lammfieischmenge in einem Kg des Hackbratens.

Darstellen das Ziel als ;

z=8x1 +6 x2

Ein Kg Hackbraten muss die folgende Fettmenge enthalten;

0.2 x1 +0.32 x2 ≤ 0.25

Zusӓtzlich die Menge der Rind und Lammfleisch die in jedem kg verwendet wird, muss gleich zu 1 sein;

x1 + x2 = 1.

Wenn man alle zusammen bringt, das mathematisches Programm lautet;

minimire z=8x1 +6 x2

unter den Bedingungen 0.2 x1 +0.32 x2 ≤ 0.25

x1 + x2 = 1

x1 ≥ 0 , x2 ≥ 0

Vorlesung 1 25
Das Problem lӓsst sich mit graphischen methoden lösen weil es nur zwei Variablen gibt;

1.2

1 x1 + x2 = 1

0.8

0.6

0.4
0.2 x1 +0.32 x2 = 0.25

0.2

0
0 0.2 0.4 0.6 0.8 1 1.2 1.4

0.2 x1 +0.32 x2 = 0.25

" % "
x1 + x2 = 1 → x1 ∗ = , x2 ∗ = → 𝑧 ∗ = 8 #$
%
+6 = 7.17 𝑒𝑢𝑟𝑜 .
#$ #$ #$

Vorlesung 1 26
Beispiel II

Ein Tischler hat 6 Stück Holz und 28 Stunden Zeit, in der er dekorative Bildschirme
herstellt. Zwei Modelle haben gut verkauft in der Vergangenheit, so wird er sich auf
diese zwei beschränken. Er schätzt, dass Modell I erfordert 2 Stück Holz und 7
Stunden, während das Modell II erfordert 1 Stück Holz und 8 Stunden Zeit. Die Preise
für die Modelle 120 und 80 Euros jeweils. Wie viele dekorative Bildschirme von jedem
Modell sollte der Tischler zusammenbauen, wenn er will zur Maximierung von
Absatz?

Vorlesung 1 27
 maximiere z=120x1 +80 x2

unter den Bedingungen 2 x1 + x2 ≤ 6

7

7x1 +8 x2 ≤ 28

6 2x1+ x2 =6 x1 ≥ 0 , x2 ≥ 0

x1 , x2 𝑔𝑎𝑛𝑧𝑧𝑎ℎ𝑙𝑖𝑔
5

4 𝑧 ∗ = 120 3 + 80 (0)=360 Euro

Zulӓssiger
7x1+ 8x2 =28
Bereich
1

0
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5

Vorlesung 1 28