Beweiser – „Integer
Linear Problems“
Oleg Iskov
Methoden der Verifikation
Universität Bremen SS2005
Grundidee
Optimierung
Beispiel zu Einführung

Politiker
 Weniger Ausgeben
 Viel
Stimmen bekommen
Beispiel zu Einführung
Thema
Variable
Stadt
Vorstadt Land
Straßenbau
X1
-2
5
3
Waffenkontrolle
X2
8
2
-5
Subventionen
X3
0
0
10
Mineralölsteuer
X4
10
0
-2
Gewinne oder Verluste in Tausend pro $1000
Beispiel zu Einführung
Minimiere x1+x2+x3+x4
unter der Bedienungen:
-2 x1 + 8 x2 + 0 x3 + 10 x4 >= 50
5 x1 + 2 x2 + 0 x3 + 0 x4 >= 100
3 x1 – 5 x2 + 10 x3 – 2 x4 >= 25
x1, x2, x3 , x4 >= 0
Formale, Abstrakte
Formulierung
Formale, Abstrakte Formulierung
Lineare Funktion:
Formale, Abstrakte Formulierung
Formale, Abstrakte Formulierung


Matrixschreibweise:
Maximire
Unter Nebenbedienungen
(A, b, c)
f(x) = c x
Ax <= b
X >= 0
Normalformen
Normalformen

Standartform

Slackform
Normalformen

Mögliche Abweichungen von der Standartform:
 Minimierungsproblem
statt Maximierungsproblem
 Variablen ohne Nichtnegativitätsbedienung
 Gleichheitsbedienungen statt
Ungleichheitsbedienungen
 Größer als Bedienungen statt Kleiner als
Bedienungen
Normalformen

Einige einfache Operationen zum Umformen:
 Negierung
der Koeffizienten c in der Zielfunktion,
 Ersetzung von xj durch x’j - x’’j mit x’j , x’’j >= 0
 Ersetzung von f(x) = b durch f(x) <= b, f(x) >= b
 Negierung der Koeffizienten aij , bi in der
betreffenden Bedienung i
Normalformen
Minimiere
-2 x1 + 3 x2
Unter Einhaltung der Nebenbedienungen:
x1 + x2 = 7
x1 – 2 x2 <= 4
x1
>= 0
Normalformen
Maximiere 2x1 - 3x2 + 3x3
x1 + x2
- x3
-x1 – x2 + x3
x1 – 2x2 + 2x3
x1 , x2 , x3
>= 0
<= 7
<= -7
<= 4
Normalformen
Integer Linear
Programming
Ein Spezialfall der linearen
Programmierung
Geometrische
Interpretation
Geometrische Interpretation
Beispiel:
Maximiere x1 + x2
Nebenbedienungen:
4x1 - x2 <= 8
2x1 + x2 <= 10
5x1 - 2x2 <= -2
x1, x2 >= 0
Geometrische Interpretation
Lösbarkeit
LP muss nicht lösbar sein
Lösungsverfahren
Lösungsverfahren
Simplexalgorithmus
 Ellipsoid-Methode
 Inner-Punkt-Verfahren


Cutthing-Plane-Methoden
Lösungsverfahren

Simplexalgorithmus,
1947 von George Dantzig entwickelt
Lösungsverfahren

Simplexalgorithmus – Beispiel

Eine Firma stellt 2 verschiedene Produkte her. Es stehen 3
Maschinen A, B, C zur Verfügung.
Maschine A hat eine
maximale monatliche Laufzeit (Kapazität) von 170 Stunden,
Maschine B von 150 Stunden und Maschine C
von 180
Stunden. Eine Mengeneinheit (ME) von Produkt 1 liefert
einen Deckungsbeitrag von 300 Euro, eine ME von Produkt 2
dagegen 500 Euro. Die Fixkosten betragen 36.000 Euro pro
Monat. Fertigt man 1 ME von Produkt 1, dann benötigt man
dafür zunächst 1 Stunde die Maschine A und danach 1 Stunde
die Maschine B. 1 ME von Produkt 2 belegt nacheinander 2
Stunden Maschine A, 1 Stunde Maschine B und 3 Stunden
Maschine C.
Lösungsverfahren
Simplexalgorithmus – Beispiel
 Formulierung mit Ungleichungen

G
= 300x1 + 500x2 - 36.000
 1·x1 + 2·x2 ≤ 170 Maschine A
 1·x1 + 1·x2 ≤ 150 Maschine B
 0·x1 + 3·x2 ≤ 180 Maschine C
 x1 ≥ 0,
x2 ≥ 0
Lösungsverfahren
Simplexalgorithmus – Beispiel
 Maximiere die Zielfunktion G unter den
Nebenbedingungen:
G - 300x1 - 500x2 = - 36.000
yA + x1 + 2x2 = 170
yB + x1 + x2 = 150
yC + 3x2 = 180
yA, yB, yC, x1, x2 ≥ 0

Lösungsverfahren


Simplexalgorithmus – Beispiel
Diese Gleichungen überträgt man in ein so
genanntes Simplex-Tableau:
G
x1
-300
YA
YB
YC
1
1
0
x2
-500
2
1
3
rechte Seite
-36000
170 = b1
150 = b2
180 = b3
Lösungsverfahren
Simplexalgorithmus – Beispiel
 Auswahl des Pivotelementes

G
:= G - a0s bj / ars
 bj
/ ars mit ars <> 0
Lösungsverfahren


Simplexalgorithmus – Beispiel
Auswahl des Pivotelementes




Spalte1:
Reihe 1: 170 / 1 = 170 Reihe 2: 150 / 1 = 150 Reihe 3: a31 = 0,
daher kein Quotient berechenbar.
Der minimaler Quotient 150
G = -36000 - (-300)×150 / 1 = 9000
Spalte 2:
Reihe 1: 170 / 2 = 85 Reihe 2: 150 / 1 = 150 Reihe 3: 180 / 3 = 60
Der minimaler Quotient 60 erhält man also in Reihe 3.
G = -36000 - (-500)×60 / 3 = -26000
Lösungsverfahren
Simplexalgorithmus – Beispiel
 Neue Tabelle:

G
YB
300
YA
x1
YC
-1
1
0
x2
-200
1
1
3
rechte Seite
9000
20 = b1
150 = b2
180 = b3
Lösungsverfahren
Simplexalgorithmus – Beispiel
 Nach noch einem Austauschschritt:

G
YB
100
x2
x1
YC
-1
2
3
YA
200
1
-1
-3
rechte Seite
13000
20 = b1
130 = b2
120 = b3
GLPK - Solver

Beweiser – „Integer Linear Problems“ - FB3