Aufgabe 1 Gegeben sei folgendes lineares Programm min x1 + x2

Aufgabe 1
Gegeben sei folgendes lineares Programm
min x1 + x2
u. d. N. 2x1 + x2
x1 + 2x2
x1 + x2
x1 , x2
≥
≥
≥
≥
6 (LP )
6
2
0
a) Zeichnen Sie bitte den zulässigen Bereich von LP in ein Koordinatensystem ein und
ermitteln Sie graphisch eine Lösung von LP .
(4 Punkte)
b) Entspricht der Punkt (x1 , x2 ) = (1, 4) einer zulässigen Basislösung des Problems LP ?
Begründen Sie Ihre Antwort bitte präzise mit Hilfe der Definition einer Basislösung
und geben Sie diese Definition auch an!
(3 Punkte)
c) Bestimmen Sie bitte das zu LP gehörige duale lineare Programm LP ∗ !
(2 Punkte)
d) Bestimmen Sie bitte eine optimale Lösung von LP ∗ , ohne diese mit dem SimplexAlgorithmus zu berechnen. Greifen Sie stattdessen auf Ihnen bekannte Dualitätsaussagen und die Ihnen bekannte optimale Lösung von LP zurück! (6 Punkte)
Operations Research 2
Aufgabe 2
Um ihren Markteinstieg möglichst günstig zu gestalten, plant die neugegründete Baumarktkette Bauprofi ÖKO“, den Hochdruckreiniger Krächer 5.75 D150 Jubilee“ – ein Modell der
”
”
Spitzenklasse – zum überaus günstigen Preis von e199 zu verschleudern.
Ihre vier neu gebauten Baumärkte wurden nach ökologischen Gesichtspunkten an Bahntrassen
gebaut, um so die Versorgung mit Verkaufsgütern per Schiene vorzunehmen. Es wird für jeden
Baumarkt mit folgendem Bedarf an Hochdruckreinigern gerechnet:
Baumarkt
B1
B2
B3
B4
Bedarf
700
3000
2800
1500
In den drei angemieteten Lagern der Baumarktkette, die ebenfalls ans Schienennetz angeschlossen sind, sind bereits die bestellten Hochdruckreiniger eingegangen. Somit befinden sich
folgende Mengen an Hochdruckreinigern im jeweiligen Lager:
Lager
L1
L2
L3
Vorrat
3000
4000
1500
Die Baumärkte können von den angemieteten Lagern mit der Bahn erreicht werden, wobei
folgende Entfernungen (in km) gegeben sind:
L1
L2
L3
B1
20
11
8
B2
13
8
10
B3
30
25
33
B4
5
40
15
a) Formulieren Sie bitte das Problem, die Baumärkte möglichst kostengünstig zu beliefern
(wobei der Transport eines Hochdruckreinigers pro km e0,01 kostet) als klassisches
Transportproblem. Geben Sie dabei explizit Entscheidungsfragen, Entscheidungsschranken und Systemziel sowie die zugehörigen Komponenten im mathematischen Modell an!
(3 Punkte)
b) Beschreiben Sie bitte, wie man aus dem klassischen Transportproblem das StandardTransportproblem entwickeln kann, indem man Grundannahmen über eine optimale
Lösung des Transportproblems trifft und Schlupfvariablen einführt. Wie lassen sich
die eingeführten Schlupfvariablen interpretieren? Überführen Sie das in a) aufgestellte Transportproblem bitte in ein Standard-Transportproblem.
(3 Punkte)
c) Da von den in Lager 1 befindlichen Hochdruckreinigern 2000 Stück leichte Mängel
haben, wird beschlossen, diese 2000 Stück in Baumarkt 2 zum vergünstigten Preis
Operations Research 3
von e169 anzubieten. Mit den vergünstigten Hochdruckreinigern wird also ein Teil des
Bedarfs in Baumarkt 2 befriedigt. Welchen Einfluss hat dies auf das Transportproblem
und wie lässt sich dies modellieren?
(2 Punkte)
d) Das Transportunternehmen SchwerLastBahn“ (SLB) möchte ein Angebot dafür abge”
ben, den Transport der Hochdruckreiniger von den Lagern zu den Baumärkten durchzuführen (dabei muss die Zusatzannahme aus c) nicht berücksichtigt werden). SLB
verfügt auf den Strecken zwischen den Lagern über folgende Transportkapazitäten (in
Hochdruckreinigern):
L1
L2
L3
B1
900
700
200
B2
2500
1100
2000
B3
600
1400
700
B4
1200
500
100
SLB steht also vor dem Problem, ob es überhaupt möglich ist, den Transport der Hochdruckreiniger mit seinen Transportkapazitäten durchzuführen. Formulieren Sie bitte dieses Problem von SLB als Max-Fluss-Problem, indem Sie ein entsprechendes Netzwerk
angeben! Wie erkennen Sie aus der Lösung dieses Max-Fluss-Problems, ob der Transport
möglich ist?
(5 Punkte)
e) Erläutern Sie bitte (im Kontext eines Max-Fluss-Problems), was ein Fluss ist und
wobei es sich bei der Flussstärke handelt!
(2 Punkte)
Operations Research 4
Aufgabe 3
Durch das Aufstellen von Packstationen ist es dem Paketdienst DHL gelungen, die Kosten
für die Auslieferung von Paketen stark zu senken. Allerdings sind dadurch neue Probleme
entstanden, die es nun mit Mitteln des Operations Research zu lösen gilt.
Alleine im Dortmunder Westen sind sieben Packstationen angelegt worden, nämlich:
Nr.
Ort
1
Hombruch
2
Barop
3
Möllerbrücke
4
Oespel
5
Innenstadt-West
6
Dorstfeld
7
Huckarde
Dabei sind zwischen den Packstationen folgende Entfernungen (in km) gegeben:
Ort-Nr.
1
2
3
4
5
6
7
1
3
4
5,5
4
4,5
7
2
3
3
3,5
2,5
2
4,5
3
4
3
6
0,5
2
4
4
5,5
3,5
6
5
4
5,5
5
4
2,5
0,5
5
1,5
3,5
6
4,5
2
2
4
1,5
3
7
7
4,5
4
5,5
3,5
3
-
a) Stellen Sie bitte für die oben beschriebene Situation einen Graphen G = (V, E, c) auf,
indem Sie V , E und c angeben!
(2 Punkte)
b) Um die Packstationen mit neu im Depot in Hombruch angekommenen Paketen zu
bestücken, ist es notwendig, jeden Tag die Pakete von dort aus auf die Packstationen
zu verteilen, wobei dies durch eine möglichst kurze Rundreise geschehen soll.
(i) Stellen Sie bitte für den Verteilvorgang ein entsprechendes Optimierungsmodell auf.
Geben Sie hierzu Entscheidungsvariablen, Nebenbedingungen und Zielfunktion an.
Beschreiben Sie jeweils deren Bedeutung!
(4 Punkte)
(ii) Der Fahrer, welcher die Pakete verteilt, möchte zur Mittagszeit in Dorstfeld sein,
um sich im dortigen Imbiss einen kleinen Snack zu genehmigen. Dazu möchte er
gerne die Packstation in Dorstfeld als dritte anfahren. Wie lässt sich dies
realisieren?
(1 Punkt)
(iii) Da in der Packstation in Barop hauptsächlich Studenten ihre Pakete anliefern lassen, soll diese als letzte oder vorletzte beliefert werden, da sie erfahrungsgemäß
vorher noch recht voll ist und somit eventuell nicht alle Pakete aufnehmen könnte.
Wie lässt sich dies realisieren?
(2 Punkte)
c) Um den Füllstand der Packstationen elektronisch zu erfassen, sollen diese vernetzt
werden. Hierzu sollen entlang der Wege Netzwerkkabel verlegt werden, um unabhängig
von Telekommunikationsdienstleistern zu sein. Über die verlegten Netzwerkkabel soll
von dem Depot in Hombruch aus der Füllstand jeder Packstation abgefragt werden
können.
Operations Research 5
(i) Welcher graphentheoretischen Problemstellung entspricht das Problem, die Netzwerkkabel möglichst kostengünstig zu verlegen? Erläutern Sie bitte alle verwendeten Begriffe!
(3 Punkte)
(ii) Welche graphentheoretischen Verfahren eignen sich zur Lösung dieser Problemstellung? Erläutern Sie die Verfahren und gehen Sie insbesondere auf deren Unterschiede ein!
(3 Punkte)
Operations Research 6

Download Report