Ubungsblatt 1.1 − Transportoptimierung

Übungsblatt 1.1 − Transportoptimierung
Kleine Transportaufgaben f ür den Eigenbedarf
1. Gegeben ist die Datentabelle eines klassischen Transportproblems.
1
2
3
1
5
3
1
8
2
1
2
5
2
3
3
2
3
6
5
4
7
Bestimmen Sie eine ersten zulässigen Transportplan mit Hilfe
(a) der NWE-Regel,
(b) der Zeilenminimumregel,
(c) der Spaltenminimumregel,
(d) der Gesamtminimumregel !
Bestimmen Sie ausgehend von dem in d) bestimmten Transportplan einen optimalen
Transportplan !
2. Bestimmen Sie ausgehend von einem zulässigen Transportplan nach der NWE-Regel
für folgende klassische Transportprobleme einen optimalen Transportplan ! Achten
Sie auf die auftretende Degeneration !
a)
1
2
3
1
2
1
3
3
2
1
2
1
5
3
4
2
4
2
4
7
4
1
9
8
7
4
b)
1
2
3
1 2
2 1
4 1
5 3
10 50
3
3
2
1
10
4
2
1
2
30
5
5
6
3
40
30
60
50
3. Bestimmen Sie ausgehend von dem zulässigen Transportplan nach der Gesamtminimumregel für folgende klassische Transportprobleme alle optimalen Transportpläne !
a)
1
2
3
1
6
7
3
5
2
3
6
1
3
3
3
4
4
8
4
1
2
2
2
5
7
6
b)
1
2
3
4
1
7
6
6
7
9
2
5
3
4
6
8
3
3
2
4
4
9
4
7
5
5
6
5
13
3
9
6
Übungsblatt 1.2 − Transportoptimierung
1. Zuweisung von Wohnungen (Domschke, Drexl)
In einer Kleinstadt sind in 4 Bezirken neue Wohnungen gebaut worden. Die Wohnungen sollen von Familien aus 4 Einkommensgruppen bezogen werden. In den Bezirken
sind 10, 6, 15 und 4 neue Wohnungen entstanden. Die insgesamt 35 wohnungssuchenden Familien verteilen sich auf die 4 Einkommensgruppen wie folgt: 5, 14, 10
und 6.
Der Stadtrat möchte bei der Belegung soziale Spannun-1 2 1 0
gen möglichst vermeiden. Daher wird ein Grad der ”Un0 4 -1 -1
zufriedenheit” der durch die Zuteilung einer Wohnung
1 9 -3 10
im Bezirk i an eine Familie aus der Einkommensgruppe
9 15 2 12
j entsteht, bestimmt. Die entsprechenden Werte können
der nebenstehenden Tabelle entnommen werden.
a) Formulieren Sie ein geeignetes klassisches Transportproblem zur Ermittlung
einer optimalen Zuweisung der verfügbaren Wohnungen an die Familien unter
der Zielsetzung, die Unzufriedenheit insgesamt möglichst gering zu halten !
b) Ermitteln Sie eine zulässige Lösung mit Hilfe der Vogel’schen Approximationsmethode ! Überprüfe die Lösung auf Optimalität !
c) Gegeben ist die Zuordnung x13 = 10, x24 = 6, x31 = 1, x32 = 14 und x41 = 4.
Handelt es sich um eine zulässige Zuordnung ? Handelt es sich um eine zulässige
Basislösung ?
2. Allocation (Hillier, Liebermann)
Suppose that England, France, and Spain produce all the wheat, barley, and oats in
the world. The world demand for wheat requires 125 million acres of land devoted to
wheat production. Similarly, 60 million acres of land are required for barley and 75
million acres of land for oats. The total amount of land availabel for these purposes
in England, France, and Spain is 70 million acres, 110 million acres, and 80 million
acres, respectively. The number of hours of labor needed in England, France, and
Spain to produce an acre of wheat is 18 hours, 13 hours, and 16 hours, respectively.
The number of hours of labor needed in England, France, and Spain to produce an
acre of barley is 15 hours, 12 hours, and 12 hours, respectively. The number of hours
of labor needed in England, France, and Spain to produce an acre of oats is 12 hours,
10 hours, and 16 hours, respectively. The labor cost per hour in producing wheat
is $3.00 , $2.40 , and $3.30 in England, France, and Spain, respectively. The labor
cost per hour in producing barley is $2.70 , $3.00 , and $2.80 in England, France,
and Spain, respectively. The labor cost per hour in producing oats is $2.30 , $2.50 ,
and $2.10 in England, France, and Spain, respectively. The problem is to allocate
land use in each country so as to meet the world food requirement and minimize
the total labor cost.
Formulate this problem as a transportation problem by constructing the appropriate
cost and requirements table and solve this problem.
3. Studienplatzbörse (Müller-Merbach)
Einige pfiffige Studenten (der Betriebswirtschaftslehre), die schon vor Abschluß ihres Studiums viel Geld verdienen möchten, haben eine private Studienplatzbörse
gegründet. An der Börse werden insgesamt drei Studienorte gehandelt: Aachen, Bochum und Cologne.
Die Idee dieser Böerse ist wie folgt: Jeder Student, der seinen Studienort wechseln will, gibt seine persönlichen Präferenzen bekannt. Um diese Präferenzen zu
quantifizieren, stehen ihm 14 Präferenzpunkte zur Verfügung. Für jeden im Tauschverfahren verwirklichten Präferenzpunkt hat der Student 100 DM an die Börse zu
zahlen. Die gewinnmaximierenden Börsianer werden natürlich eine möglichst hohe
Zahl an Präferenzpunkten zu realisieren versuchen.
Ein Beispiel: Ein Student stellt seinen Studienplatz in Aachen zur Verfügung. Am
liebsten möchte er nach Bochum, wofür er 9 Punkte vergibt. Den Studienort Cologne
bewertet er mit 5 Punkten. Wenn die Studienplatzbörse ihm Bochum vermittelt,
muß er also 900 DM zahlen. Wird ihm dagegen Cologne zugewiesen, muß er nur
500 DM zahlen. Er kann allerdings auch an seinem alten Studienplatz bleiben. Eine
Vermittlungsgebühr wird dann nicht fällig.
Insgesamt möchten 70 finanzkräftige Studenten ihren Studienort wechseln. Davon
kommen 22 Studenten aus Aachen, 28 Studenten aus Bochum und 20 Studenten aus
Cologne. Die potentiellen Hochschulwechsler lassen sich in 6 Gruppen mit jeweils
einheitlichen Präferenzpunkten einteilen:
13
7
12
16
14
8
Studenten: 8 Punkte für Aachen und 6 Punkte
Studenten: 10 Punkte für Aachen und 4 Punkte
Studenten: 4 Punkte für Aachen und 10 Punkte
Studenten: 12 Punkte für Aachen und 2 Punkte
Studenten: 6 Punkte für Bochum und 8 Punkte
Studenten: 9 Punkte für Bochum und 5 Punkte
für
für
für
für
für
für
Bochum
Bochum
Cologne
Cologne
Cologne
Cologne
Welche Aufteilung soll gewählt werden, damit der Gewinn der Jungunternehmer
maximiert wird ?
4. Betontransport (Berens, Delfmann)
Ein mittelständischer Betonhersteller verfügt über zwei an der B1 gelegenen Zementwerke in Soest und Salzkotten. Die mit Beton zu beliefernden Baustellen liegen gleichfalls an der B1, und zwar in Osttönnen und Geseke. Die Entfernungen der
Städte, die Kapazitäten der Zementwerke und der Bedarf der Baustellen sind der
folgenden Skizze zu entnehmen:
———10 km ———- 40 km ———- 10 km
———
– B1 –
Osttönnen
Soest
Geseke
Salzkotten
7 ME
10 ME
8 ME
5 ME
Die Transportkosten je gefahrenen Kilometer betragen 1 DM.
a) Lösen Sie das Transportproblem !
b) Nach der Ermittlung der Optimallösung stellt sich heraus, daß in Osttönnen
zwei zusätzliche ME Beton benötigt werden. Die Produktionskapazität kann
jedoch nur in Salzkotten um zwei ME erweitert werden. Wie verhalten sich die
Kosten bei Berücksichtigung dieser zusätzlichen Lieferung ?
5. Optimal car shipping schedule (Winston)
A company produces cars in Atlanta, Boston, Chicago, and Los Angeles. The cars
are then shipped to warehouses in Memphis, Milwaukee, New York City, Denver,
and San Francisco. The number of cars available at each plant is given in the first
table. Each warehouse needs to have available the number of cars given in the second
table.
Plant
Cars Available
Atlanta
5000
Boston
6000
Chicago
4000
L.A.
3000
Warehouse
Cars Required
Memphis
6000
Milwaukee
4000
N.Y.
4000
Denver
2000
San Francisco
2000
The distance (in miles) between the cities is given in the third table.
Atlanta
Boston
Chicago
L.A.
Memphis Milwaukee New York City Denver San Francisco
371
761
841
1398
2496
1296
1050
206
1949
3095
530
87
802
996
2142
1817
2012
2786
1059
379
a) Assuming, that the cost (in dollars) of shipping a car equals the distance between two cities, determine an optimal shipping schedule.
b) Assuming, that the cost (in dollars) of shipping a car equals the square root of
the distance between two cities, determine an optimal shipping schedule.
6. Die Kosten eines klassischen Transportproblems seien
cij = Kpi + Lqj ,
(i, j) ∈ N .
Zeigen Sie, daß jeder zulässige Transportplan optimal ist !
7. Betrachten ein klassisches Transportproblem, dessen Kostenmatrix die sogenannte
Monge-Eigenschaft erfüllt:
cij + crs ≤ cis + crj ,
∀(i, j) ∈ N , ∀(r, s) ∈ N , mit
1≤i<r≤m,1≤j<s≤n
Zeigen Sie, daß die Nordwesteckenregel einen optimalen Transportplan erzeugt !
Hinweis:
B. Bräunig: Monge Eigenschaften und ihre Bedeutung zur Lösung von
Problemen der Produktions-Transport-Optimierung
Diplomarbeit, TU Freiberg, 1998, Abschnitt 3.5
K.E. Hoffmann: Bedeutung der Monge Matrizen für die Optimierung
Seminararbeit in Operations Research, Fakultät 6, 2000
8. Konstruieren Sie ein einfaches Lösungsverfahren für klassische Transportprobleme
der Dimension m = 2 und n ≥ 2 !
9. Die Kostenmatrix eines klassischen Transportproblem sei quadratisch, nichtnegativ
mit Nulleinträgen in der Diagonale, symmetrisch und erfülle die Dreiecksungleichung.
Lassen sich mit Hilfe dieser Informationen Aussagen für die Menge der optimalen
Transportpläne ableiten ?
10. Betrachten ein klassischen Transportproblem (P) mit ganzzahligen Vorrats- und
Bedarfsmengen. Zeigen Sie, daß das klassische Transportproblem (Q) mit
ãi = ai ,
b̃j = bj +
i = 1,...,m-1 ,
1
n
,
ãm = am + 1
j = 1,...,n
keine degenerierten Basislösungen besitzt ! Wie kann man aus einer Optimallösung
von (Q) eine Optimallösung für (P) konstruieren ?
11. Jeder zulässigen Basislösung ist ein Eckpunkt des Transportpolyeders T zugeordnet.
Wieviele Kanten gehen von einem einfach degenerierten Eckpunkt aus ?
Untersuchen Sie dies für den zu




X=
2
0
0
0
2
5
0
0
0
0
0
2
0
0
1
3





gehörigen Eckpunkt !
12. Für ein klassischen Transportproblem sei ein optimaler Transportplan mit allen zugehörigen Informationen bekannt. Das Angebot eines Erzeugers Ak und die Nachfrage eines Verbrauchers Bl erhöhe sich um jeweils eine Mengeneinheit.
Kann man aus den vorliegenden Informationen Aussagen über die Änderung der minimalen Gesamtkosten ableiten ? Ist es möglich, daß trotz positiver Kostenmatrix
der neue Optimalwert kleiner als der alte ist ?
13. Übertragen Sie den aus der linearen Optimierung bekannten dualen Simplexalgorithmus auf das KTP ! (Setzen dabei die Kenntnis einer dual zulässigen Basislösung
voraus.)
Hinweis: Wie kann man die zu einer Basisvariable xpq gehörige Zeile des
Simplextableaus gewinnen ? (Die relativen Bewertungskoeffizienten stehen
auch in einer Zeile des Simplextableaus !)
14. Gegeben sei ein klassisches Transportproblem, dessen Bedarfsvektor beliebig permutiert werden kann.
Formulieren Sie Ideen zur Lösung dieser Aufgabe !
Hinweis:
S.G. Meusel, R.E. Burkard:
A transportation problem with a permuted demand vector
TU Graz, SFB 003, Bericht Nr. 135, August 1998
Übungsblatt 1.3 − Transportoptimierung
Studienmaterial
1. Optimale Planung des Erdtransportes bei einer Geländeregulierung
Quelle:
G. Jandy:
Optimale Transport- und Verkehrsplanung
Verlag für Verkehrswesen, 1968 , S. 110-114
2. Einkauf und Logistik
Quelle:
M. Bliesener:
Einkauf und Logistik
Fallstudie aus der Betriebswirtschaftslehre
WISU (Wirtschaftswissenschaftliches Studium) 2/1995
S. 145-146
3. Transportprobleme beim Massenunfall
Quelle:
H. Röding:
Massenunfall und Operationsforschung
Zeitschrift für Militärmedizin, 6/1970 , S. 317-326
H. Röding u.a.:
Der Massenunfall - Taktik und Planung medizinischer Hilfe
Johann Ambrosius Barth Verlag, Leipzig, 1985
4. Testen Sie das Programm ktp.exe von V. Sameske (Version vom 08.11.1995) zur
Lösung von klassischen Transportproblemen ! (Treten Fehler auf ?)
5. Sensity analysis for transportation problems
Quelle:
W.L. Winston: Operations Research
Duxbury Press, Belmont, California, 1993 p. 369-372
6. Monge Sequenzen und klassische Transportprobleme
Quelle:
N. Alon, S.Cosares, D.S. Hochbaum, R. Shamir:
An algorithm for the detection and construction of Monge sequences
LINEAR ALGEBRA AND ITS APPLICATIONS 114/115: 669-680 (1989)
Übungsblatt 2.1 − Transportoptimierung
1. Für welche Parameter s ist die Transportaufgabe mit Kapazitätsbeschränkungen
z=
m X
n
X
cij xij −→ min
i=1 j=1
n
X
j=1
m
X
xij = ai ,
i = 1, ..., m
xij = bj ,
j = 1, ..., n
i=1
0 ≤ xij ≤ s ,
i = 1, ..., m , j = 1, ..., n
lösbar?
Zahlenbeispiel:
a1 = 9 , a2 = 8 , a3 = 2
b1 = 8 , b2 = 7 , b3 = 3 , b4 = 1
s≥?
2. Auswahl eines Transportunternehmens
Das Unternehmen Zackenbarth hat drei Produktionsstandorte P1 , P2 und P3 , die
einen Produktionsausstoß von 10; 6 bzw. 6 ME (in 10000 Stück) eines Produktes haben. Von den Produktionsstandorten aus werden drei Großlager G1 , G2 , und G3 des
Großhandelsunternehmens Reisswolf beliefert, die auf Grund von Prognosen 5; 7
bzw. 10 ME des Produktes bestellen. Für die Realisierung der Transportleistungen
kommen zwei Transportunternehmer in die engere Wahl.
• Der Transportunternehmer Wernesgrün bietet die Transporte zu folgenden
Kosten (GE pro ME) an:
P1
P2
P3
G1
7
3
4
G2
5
2
4
G3
9
3
5
Vom Produktionsstandort P1 zu den Großhandelsunternehmen G1 und G2 kann
das Transportunternehmen zusammen nur 8 ME transportieren.
• Der Transportunternehmer Ehnotex bietet die Transporte zu folgenden Kosten (GE pro ME) an:
P1
P2
P3
G1
9
2
5
G2
4
1
5
G3
8
3
7
Das Transportunternehmen kann nur 2 ME vom Produktionsstandort P3 zum
Großhandelsunternehmen G1 transportieren.
Für welches der beiden Transportunternehmen sollte sich das Großhandelsunternehmen entscheiden ?
3. Benzinlieferung (Domschke, Drexl)
Eine Behörde schreibt Aufträge zur Belieferung von vier staatlichen Depots Dj
(j=1,...,n) mit Benzin aus. Die Depots besitzen folgenden Treibstoffbedarf:
D1 : 12 ME; D2 : 17 ME; D3 : 10 ME; D4 : 11 ME
Um die Aufträge bewerben sich zwei Lieferanten Li (i=1,2). Das Gebot enthält zum
einen die genaue Menge an Benzin, die der Unternehmer zu liefern wünscht; und
zwar bieten Lieferant L1 20 ME und Lieferant L2 30 ME Benzin an. Zum anderen
nennt jeder Unternehmer den Preis, den er für die Belieferung des Depots Dj mit
je 1 ME Treibstoff fordert. Die Preise sind in der folgenden Tabelle enthalten:
8
3
10 5 4
7 7 6
Die Behörde möchte die Aufträge so vergeben, daß der Bedarf der Depots zu minimalen Kosten gedeckt wird. Um die Depots nicht in eine zu starke Abhängigkeit
geraten zu lassen, wird die mögliche Liefermenge jedes Unternehmens für jedes Depot auf ein Maximum beschränkt. Die maximalen Liefermengen der Unternehmer
für jedes Depot sind in der folgenden Tabelle enthalten:
8
7
12 7
14 8
6
7
Bestimmen Sie für dieses kapazitierte Transportproblem einen optimalen Plan !
Geben Sie auch einen einfachen Lösungsweg an !
4. Lösen Sie das folgende Transportproblem mit Hilfe des dualen Lösungsverfahrens!
Die Schranken für die Variable befinden sich rechts über den Kosten im Kleindruck.
cij \ sij
1
2
3
bj
1
912
814
1018
15
2
613
220
46
25
3
75
710
325
25
4
525
39
66
35
ai
25
25
50
Untersuchen Sie anschließend, welchen Einfluß die Änderung der Schranke s33 = 25
auf den Wert s33 = 26 für den Ablauf des Lösungsverfahrens hat!
Quelle:
M. Schoch: Das Erweiterungsprinzip und seine Anwendung
Deutscher Verlag der Wissenschaften, 1976
S. 80-102
5. Welche Vereinfachung des dualen Lösungsverfahrens sind beweistechnisch als auch
numerisch für klassische Transportprobleme möglich ?
Lösen Sie Beispiel 1.1 der Vorlesung mit dem angepaßten dualen Lösungsverfahren !
6. Entwickeln Sie Ideen für primale und duale Lösungsverfahren für das Bottleneck
Transportproblem
z = max tij −→ min
xij >0
n
X
j=1
m
X
xij = ai ,
i = 1, ..., m
xij = bj ,
j = 1, ..., n
i=1
0 ≤ xij ≤ sij ,
i = 1, ..., m , j = 1, ..., n
und beachten Sie dabei die Verwendung effektiver Schranken für die Zielfunktion.
Übungsblatt 2.2 − Transportoptimierung
Studienmaterial
1. Optimaler Kohleversorgungsplan
Quelle:
M. Schoch: Anwendung der linearen Optimierung zur Ermittlung
eines optimalen Kohleversorgungsplanes
Freiberger Forschungshefte A 317 , 1964
S. 9-124
2. Ermittlung eines optimalen Wagenbestandes
Quelle:
G. Jandy:
Optimale Transport- und Verkehrsplanung
Verlag für Verkehrswesen, 1968
S. 124-127
Welche Lösungsverfahren eignen sich zur Behandlung des beschriebenen Problems ?
3. Abgestumpfte Transportpolyeder
Quelle:
V.A. Emeličev, M.M. Kovalev, M.K. Kravcov:
Polyeder Graphen Optimierung
VEB Deutscher Verlag der Wissenschaften, 1985, S. 279-285
Übungsblatt 3.1 − Transportoptimierung
1. Gegeben sei ein Zuordnungsproblem mit der Kostenmatrix cij = (i − 1)(n − j),
i = 1, ..., n, j = 1, .., n.
a) Wie lautet die optimale Zuordnung ?
b) Welchen Aufwand verursacht das duale Lösungsverfahren aus Abschnitt 2.3
der Vorlesung zur Lösung dieser Aufgabe ?
2. Ein Fuhrunternehmen hat 4 Fahrzeuge (F1 , F2 , F3 , F4 ) im Einsatz, die an verschiedenen Standorten untergebracht sind. Es liegen 4 Aufträge vor. Das Fahrzeug F2 ist
nicht für den Auftrag A2 und das Fahrzeug F3 nicht für den Auftrag A4 geeignet.
Die Entfernungen der Fahrzeuge zu den Auftragsorten sind in der folgenden Tabelle
gegeben:
F1
F2
F3
F4
A1
70
65
30
25
A2
40
60
45
30
A3
20
45
50
55
A4
55
90
75
40
Wie sollte der Fuhrunternehmer die Fahrzeuge zu den Auftragsorten schicken, damit
die totale Leerfahrt minimal wird ? Ist die Einsatzplanung eindeutig ?
3. Bauer Cleverle (Domschke, Drexl)
Der schwäbische Bauer Cleverle beabsichtigt den Kauf einer neuen Melkmaschine
für seinen landwirtschaftlichen Betrieb. Ein vollautomatisches Melksystem wird in
drei Jahren installiert werden, so daß die Melkmaschine dann nicht mehr benötigt
wird. Da jedoch vorher mit einer sehr starken Beanspruchung der Melkmaschine zu
rechnen ist, werden die Betriebs- und Wartungskosten mit der Zeit stark zunehmen.
Es wäre unter Umständen sinnvoller, die gekaufte Melkmaschine nach ein und/oder
zwei Jahren durch eine neue desselben Typs zu ersetzen.
Die folgende Tabelle enthält die durch den Kauf einer Melkmaschine am Beginn
des Jahres i und deren Nutzung bis zum Ende des Jahres j entstehenden Kosten
(Wertminderung, Betriebs- und Wartungskosten):
8 18 31
- 10 21
- - 12
Man bestimme die Zeitpunkte, zu denen die neue Melkmaschine ggf. ersetzt werden
sollte, um die Melkkosten für die nächsten drei Jahre zu minimieren !
Der Sachverhalt läßt sich als Kürzeste-Weg-Problem formulieren. Ist auch eine Formulierung als Zuordnungsproblem möglich ?
4. Gewinnmaximierung (Behrens)
Ein Immobilienmakler bietet vier Eigentumswohnungen in bevorzugter Wohnanlage
an. Da sich seine Courtage nach dem Kaufpreis richtet, strebt er einen möglichst
großen Gesamtkaufpreis an. Für die von ihm angebotenen Wohnungen interessieren
sich insgesamt vier potentielle Käufer. Ihre Zahlungsbereitschaft (in Tsd. Mark) ist
bekannt und läßt sich der folgenden Tabelle entnehmen:
Wohnung
Wohnung
Wohnung
Wohnung
1
2
3
4
Käufer 1 Käufer 2
200
210
180
185
190
190
200
205
Käufer 3
205
175
180
200
Käufer 4
205
180
195
210
Wie soll der Immobilienmakler die Zuordnung zu den Wohnungen vornehmen ?
5. Hausarbeit (Domschke, Drexl)
Das junge Ehepaar Gottfried und Kunigunde Kahlebutz will sich die wichtigsten
Haushaltsarbeiten (Einkaufen, Kochen, Waschen inkl. Bügeln und Klein-Elizabeth
wickeln) so teilen, daß jeder der beiden genau zwei Aufgaben übernimmt und die
dabei insgesamt von ihnen für den Haushalt geopferte Zeit minimiert wird. Beide
meinen in der Lage zu sein, jede beliebige der auszuführenden Arbeiten zufriedenstellend und ohne Ehekrach zu erledigen. Dies geschieht jedoch mit unterschiedlicher
Effizienz, woraus unterschiedliche Zeiten zur Bewältigung der Aufgaben resultieren:
Stunden pro Woche für
Kunigunde
Gottfried
Einkauf Kochen Waschen Wickeln
3.6
7.8
2.9
4.5
4.3
7.2
3.1
4.9
Wie sieht eine optimale Aufgabenverteilung aus und wie groß ist der gemeinsame
Zeitaufwand ?
In welche Kategorie kann man das zugrunde liegende Modell einordnen ? Wie kann
es effektiv gelöst werden ?
6. Teaching (Winston)
Three professors must be assigned to teach six sections of finance. Each professor
must teach two sections of finance, and each has ranked the six time periods during
which finance is taught, as shown in the following table.
Professor 1
Professor 2
Professor 3
9 a.m.
8
9
7
10 a.m.
7
9
6
11 a.m.
6
8
9
1 p.m.
5
8
6
2 p.m.
7
4
9
3 p.m.
6
4
9
A ranking of 10 means that the professor want to teach that time, and a ranking of
1 means that he or she does not want to teach at that time. Determine a assignment
of professors to sections that will maximize the total satisfaction of the professors.
7. Doc Councillman (Machol)
Doc Councillman is putting together a relay team for the 400-meter relay. Each
swimmer must swim 100 meters of breaststroke, backstroke, butterfly, or freestyle.
Doc believes that each swimmer will attain the times given in the following table.
Gary Hall
Mark Spitz
Jim Montgommery
Chet Jastremski
Free Breast
54
54
51
57
50
53
56
54
Fly Back
51
53
52
52
54
56
55
53
To minimize the team’s time for the race, which swimmer should swim which stroke ?
8. Wild West im Tal des Rio Grande (Hering/Scheurer)
Seit Jahrzehnten herrscht Streit zwischen den beiden größten Ranchern im Tal des
Rio Grande, den Millers und den Montojas. Der Zwist hat ganz belanglos mit der
Frage angefangen, wer als Brandzeichen ein großes M in einem stehenden Dreieck führen dürfe. Der harmlos begonnene Streit eskalierte im Laufe der Jahre zu
einem blutigen Krieg, dessen Kampfhandlungen nur unterbrochen wurden, damit
die Streithähne ihre Wunden auskurieren konnten. Im Laufe der Zeit waren beide
Parteien gewillt, die unheilbringenden Kriege zu beenden. Zu diesem Zwecke boten
Big Jack Miller und Don Jose de Montoja ungeheure Summen auf, um berühmte
Revolverhelden für den letzten, alles entscheidenden Shoot-Out zu gewinnen. Zwölf
der berühmtesten Schützen des Wilden Westens waren dem Ruf und der Ehre (und
des Geldes) gefolgt, wobei sechs Männer für die Montojas und sechs Männer für
die Millers kämpfen wollten. Gewitzt durch die Erfahrung jahrzehntelanger Kriege,
zögerten beide den Zeitpunkt der offenen Auseinandersetzung hinaus, wohl wissend,
daß sie keine Chance haben würden, einen einmal gemachten Fehler zu korrigieren.
Für beide Anführer war es schwierig, die für sie günstigsten Paarungen für die Duelle
herauszufinden. Der einzige Hinweis, der ihnen für ihre strategischen Überlegungen
zur Verfügungen stand, waren die Siege, die ihre Schützen und die des Gegners im
Kampf Mann gegen Mann erzielt hatten:
Schützen für Miller
Schützen für Montoja
Name
Siege
John Wayne
46
Indiana Jones
30
Pat Garret
24
Buffalo Bill
20
Wyatt Earp
17
Doc Holliday
14
Name
Siege
Billy the Kid
42
Jesse James
34
Butch Cassidy
22
Jonny Ringo
18
Mr. Bean
17
Dirty Harry
15
Wir wissen, daß ohne Kenntnis der Zukunft jede Entscheidung mit Risiko behaftet
ist. Die einzige Möglichkeit, die Chancen auf einen endgültigen Sieg zu verbessern,
besteht darin, die Revolverhelden so einzusetzen, daß das Gesamtrisiko einer Niederlage minimiert wird. Wie lauten die risikominimalen Paarungen, die die Anführer
jeweils vorschlagen müßten ?
9. Bundeswettbewerb Mathematik 1996 (Aufgabe 2 der 1. Runde)
Auf einem n × n Schachbrett sind die Felder so numeriert, wie auf dem abgebildeten
Beispiel für n = 5.
1
6
11
16
21
2
7
12
17
22
3
8
13
18
23
Es werden n Felder derart ausgewählt, daß aus
jeder Zeile und aus jeder Spalte genau ein Feld
kommt. Anschließend werden die Nummern dieser
Felder addiert. Welche Werte für die Summen sind
hierbei möglich ? (Beweis!)
4 5
9 10
14 15
19 20
24 25
10. Chaos-Lexikon (P.M. Logik-Trainer)
Unsere kleine Gemeindebibliothek ist stolz darauf, die komplette, zehnbändige Enzyklopädie der großen Persönlichkeiten der Weltgeschichte zu besitzen. Um so mehr
ärgert sich Petra Baumkamp, die Bibliothekarin, wenn die Leser mit den wertvollen Bänden schlampig umgehen. Gestern fand sie alle zehn Bände an den falschen
Plätzen. In welcher Reihenfolge standen die Exemplare, bevor Petra sie richtig
ordnete ?
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(?)
(?)
(?)
(?)
(?)
(?)
(?)
(?)
(?)
(?)
Hinweise:
• Jeder Band stand mindestens zwei und höchstens sieben Plätze von dem Platz
entfernt, auf dem er hätte stehen müssen. In keinem Fall wurden die Bücher so
zurückgestellt, daß sich die korrekten und die falschen Platzziffern wechselseitig
entsprachen; d.h., wenn etwa Band 10 auf dem Platz von Band 1 stand, befand
sich Band 1 nicht auf Platz 10.
• Kein Band wurde irrtümlich an einen Platz gestellt, dessen Ziffer doppelt so
groß oder halb so groß wie die korrekte Platzziffer war.
• Band 4 und Band 9 standen von ihren korrekten Plätzen jeweils gleich weit
entfernt. Beide waren aber näher zu ihren korrekten Plätzen als Band 3 zu der
Position, auf die ihn Petra zurückstellte.
• Band 7 war auf einen Platz gestellt worden, der drei Plätze links von dem war,
auf dem irrtümlich Band 8 stand.
• Band 10 stand auf einem Platz mit ungerader Positionsnummer.
• Band 2 stand auf dem Platz, auf dem eigentlich der Band hätte stehen müssen,
der irrtümlich auf Platz 6 stand. Band 6 nahm den Platz eines Bandes ein,
dessen korrekte Position zwei Plätze rechts von dem war, an dem Band 3 stand,
bevor Petra wieder Ordnung schaffte.
Übungsblatt 3.2 − Transportoptimierung
Studienmaterial
1. Studieren Sie die Ungarische Methode zur Lösung des Zuordnungsproblems und den
grundlegenden Satz von König-Egerváry !
Quelle:
B. Kreko: Lehrbuch der linearen Optimierung
Deutscher Verlag der Wissenschaften, 1973
Anhang, Abschnitt XX, S. 377-398
2. Geben Sie für ein Maschinenbelegungsproblem aus der Polygraphie ein effektives
Lösungsverfahren an !
Quelle:
K. D. Maudrich: Beitrag zur operativen Planung in der Polygraphie
Wissenschaftliche Zeitschrift TU Leipzig, 16/1982
Heft 4, S. 249-253
3. Untersuchen Sie, ob die von Leow Soo Kar angegebenen Zuverlässigkeitsmodelle
effektiv gelöst werden können !
Quelle:
Leow Soo Kar:
Maximum Reliability For Combined Hardware-Software
Fault-Tolerant Computer-Systems
Opsearch, Vol.27, No.1(1990), S. 1-13
4. Der Kauf von Flugtickets
Quelle:
W. Berens: Der Kauf von Flugtickets als Zuordnungsproblem
Fallstudie aus der Betriebswirtschaftslehre
WISU (Wirtschaftswissenschaftliches Studium) 8-9/1992
S. 658-659
5. Errichtung von Produktionsstätten
Quelle:
M. Meyer:
”Aufschwung Ost”
Fallstudie aus der Betriebswirtschaftslehre
WISU (Wirtschaftswissenschaftliches Studium) 7/1992
S. 568-569
Übungsblatt 4.1 − Transportoptimierung
1. Immobilienfinanzierung
Eine Immobilienfirma hat die Absicht, drei Gebäude zu erwerben, die in unterschiedlichen Regionen liegen und zu unterschiedlichen Zwecken genutzt werden sollen. Die
Erwerbskosten betragen 30, 50 bzw. 70 Millionen DM. Zur Finanzierung der Kosten wurden Verhandlungen mit 3 Banken geführt, die bereit sind, jeweils höchstens
80, 40 bzw. 50 Mill. DM Kredit zu geben. Auf Grund der verschiedenen Standortlagen und Nutzungszwecke haben die Kreditabteilungen beschlossen, unterschiedliche Zinssätze für die Finanzierung der verschiedenen Gebäude einzuräumen. Die
Zinssätze (in %) und die bereits genannten Geldmengen (in Mio) sind in folgender
Tabelle gegeben:
Bank 1
Bank 2
Bank 3
Gebäude 1 Gebäude 2
14
12
12
9
10
13
30
50
Gebäude 3
11
13
14
70
80
40
50
a) Wie sollte die Immobilienfirma die Kreditangebote nutzen, damit die Gesamtzinszahlungen möglichst klein werden ? Wie groß ist die durchschnittliche Zinsrate, die durch die Immobilienfirma zu leisten ist ?
b) Ändert sich etwas an der gefundenen Splittung der Kredite, wenn Bank 3 ihre
Zinssätze generell um 2% absenkt ?
2. Schnapsbrennerei (Domschke, Drexl)
Ein Unternehmen, das in verschiedenen Städten vier Schnapsbrennereien betreibt,
kann bei drei landwirtschaftlichen Genossenschaften den zur Produktion notwendigen Weizen beziehen. Die Brennerei B1 nimmt mindestens 30 t, die Brennereien B2
bis B3 nehmen genau 40 t, 20 t bzw. 10 t Weizen von den Genossenschaften ab. Mit
der Genossenschaft G1 besteht ein Abnahmevertrag über mindestens 35 t, wobei
der Preis 5 GE/t beträgt. Die Genossenschaft G2 bietet maximal 50 t an; der Preis
beträgt 4 GE/t. Sowohl bei G1 als auch bei G2 müssen die Weizenlieferungen selbst
abgeholt werden. Dagegen bietet die Genossenschaft G3 maximal 30 t für 6 GE/t
an, wobei die Anlieferung im Preis inbegriffen ist.
Das Unternehmen möchte die Beschaffungskosten für Weizen minimieren. Die Kosten für den Transport einer Tonne Weizen von den Genossenschaften Gi zu den
Schnapsbrennereien Bj können der folgenden Tabelle entnommen werden:
3 4 2
2 4 3
4 2 3
1
2
4
Wieviele Tonnen Weizen sollen im kostengünstigsten Fall in den einzelnen landwirtschaftlichen Genossenschaften abgenommen werden und wieviel erhält die erste
Schnapsbrennerei ? Wie ist der zugehörige Transport zu gestalten ?
3. Produktions-Transport-Optimierung
Ein Unternehmen produziert in zwei Werken ein Produkt, das an drei Auslieferungslager zu transportieren ist. Während die Produktionskosten je Einheit in beiden Werken gleich ist, hängen die Transportkosten (in 100 Dollar) je Einheit vom
ausliefernden Werk ab:
Werk A
Werk B
Lager 1 Lager 2
4
6
6
5
Lager 3
3
2
Pro Woche sollen 60 Einheiten produziert und an die Lager ausgeliefert werden.
Jedes Werk verfügt über eine maximale wöchentliche Produktions- und Transportkapazität von 50 Einheiten. Es besteht also genügend Spielraum, die Gesamtproduktion zur Reduzierung der Transportkosten auf die Werke zu verteilen.
Das Management möchte für die nachfolgenden Bedingungen wissen, wieviele Produkteinheiten in den Werken hergestellt werden sollen und wie der Distributionsplan
zu gestalten ist, wenn die Transportkosten minimiert werden sollen.
a) Jedes Auslieferungslager soll genau 20 Einheiten pro Woche erhalten.
b) Jedes Auslieferungslager kann mit einer beliebigen Menge zwischen 10 und 30
Einheiten pro Woche beliefert werden.
c) Auslieferungslager 1 soll genau 5 Einheiten, Auslieferungslager 2 genau 25 Einheiten und Auslieferungslager 3 genau 30 Einheiten pro Woche erhalten. Jedes
Auslieferungslager soll aber nur von einem Werk aus beliefert werden.
4. Kapazitätserweiterung
In einer Wirtschaftsregion besitzt ein Bauunternehmen vier Fabriken, in denen das
Vorfertigen von Bauteilen für den Wohnungsbau erfolgt. Diese Fabriken verarbeiten täglich 80, 30, 50 bzw. 80 Tonnen Kies. Es ist auch eine fünfte Fabrik im Bau,
deren Kapazität täglich 200 Tonnen betragen soll. Bisher wurden die vier Fabriken
aus drei Gruben versorgt, deren Kapazität durch 80, 60 bzw. 100 Tonnen pro Tag
beschränkt ist. Um den wachsenden Anforderungen genügen zu können, soll entweder die Kapazität der Gruben G2 und G3 um maximal je 100 Tonnen pro Tag
erhöht werden oder aber eine neue vierte Grube mit einer Kapazitätsschranke von
200 Tonnen pro Tag erschlossen werden. Die Bahntarife für die kürzesten Strecken
zwischen Gruben und Fabriken zeigt die folgende Tabelle:
G1
G2
G3
G4
F1 F2 F3 F4
524 98 285 408
258 427 161 226
187 586 453 470
312 194 274 615
F5
140
176
210
351
Das Bauunternehmen ist daran interessiert, seinen Bedarf an Kies mit einem minimalen Kostenaufwand zu befriedigen. Soll man die bestehenden Gruben weiter
ausbauen oder die neue Grube erschließen, und aus welchen Gruben soll jede der
Fabriken versorgt werden ?
5. Appletree Cleaning (Winston)
Appletree Cleaning has five maids. To complete cleaning my house, they must vacuum, clean the kitchen, clean the bathroom, and do general straightening up. The
time it takes each maid to do each job is shown in the following table:
Maid
Maid
Maid
Maid
Maid
1
2
3
4
5
Clean
Clean
Vacuum Kitchen Bathroom
6
5
2
9
8
7
8
5
9
7
7
8
5
5
6
Straighten
Up
1
3
4
3
4
Each maid is assigned one job. Determine assignments that minimize the total number of maid-hours needed to clean my house.
6. Bids (Winston)
The Chicago Board of Education is taking bids on the city’s four school bus routes.
Four companies have made the bids:
Company
Company
Company
Company
1
2
3
4
Route 1 Route 2
$4000
$5000
$4000
$3000
-
Route 3
$2000
$4000
Route 4
$4000
$5000
a) Suppose each bidder can be assigned only one route.
b) Suppose that each company can be assigned two routes.
Use the assignment method to minimize Chicago’s cost of running the four bus
routes.
7. Storage Problem (Evans)
Currently, State Univercity can store 200 files on hard disk, 100 files in computer
memory, and 300 files on tape. User want to store 300 word-processing files, 100
packaged-program files, and 100 data files. Each month a typical word-processing
file is accessed eight times, a typical packaged-program file, four times; a typical
data file, two times. When a file is accessed, the time it takes for the file to be
retrieved depends on the typ of file and on the storage medium:
Hard disk
Memory
Tape
Word
Processing
5
2
10
Packaged
Program Data
4
4
1
1
8
6
If the goal is to minimize the total time per month that users spend accessing their
files, formulate a transportation problem that can be used to determine where files
should be stored.
8. Home Brew
Tom would like excactly 3 pints of home brew today and at least an additional 4
pints of home brew tomorrow. Dick is willing to sell a maximum of 5 pints total
at a price of 80 cents/pint today and 72 cents/pint tomorrow. Harry is willing to
sell a maximum of 4 pints total at a price of 77 cents/pint today and 75 cents/pint
tomorrow.
Tom wishes to know what his purchases should be to minimize his cost while satisfying his minimum thirst requirements.
Formulate this problem as a transportation problem and solve it.
9. Gegeben sei ein offenes Transportproblem, z.B. TP(≤, =), dessen Kostenmatrix die
Monge-Eigenschaft erfüllt:
cij + crs ≤ cis + crj ,
∀(i, j) ∈ N , ∀(r, s) ∈ N ,
1≤i<r≤m,1≤j<s≤n
Läßt sich diese Eigenschaft analog zum klassischen Transportproblem für eine effektive Lösung des offenen Transportproblems verwenden ?
Übungsblatt 4.2 − Transportoptimierung
Studienmaterial
1. Übungsaufgaben 6.1 , 6.5 , 6.6
Quelle:
Dinkelbach: Operations Research – Kurzlehr- und Übungsbuch
Springer-Verlag, 1992
S270 ff.
2. Optimal Allocation of Receivers to Transmitters
Quelle:
G.B. Dantzig: Linear Programming And Extensions
Princeton University Press, Princeton, New Jersey, 1963
p. 326-329
3. Ein Produktionsprogramm
Quelle:
B. Kreko: Lehrbuch der linearen Optimierung
Deutscher Verlag der Wissenschaften, 1973
S. 339-342
4. Transport von Rohtabak
Quelle:
J. Varga: Angewandte Optimierung
B.I. Wissenschaftsverlag Mannheim/Wien/Zürich, 1991
S. 148-150