Modul: Operations Research - Universität Rostockmerker/SkriptOperationsResearch.pdf · 1Formalien Ablauf I In der Lehrveranstaltung Operations Research (mit " s\) werden wir uns

$Page 1: Modul: Operations Research - Universität Rostockmerker/SkriptOperationsResearch.pdf · 1Formalien Ablauf I In der Lehrveranstaltung Operations Research (mit " s\) werden wir uns$
Modul: Operations Research

Dr.habil. Jochen Merker

Business Intelligence and Statistics

18.+19.09.2013 Modul: Operations Research – Dr.habil. Jochen Merker 1/43

1 Formalien

Dozent

Jochen Merker

1996-2001: Studium der Mathematik und Informatik an derUniversitat Hamburg (Diplom)

2001-2004: wissenschaftlicher Mitarbeiter am FachbereichMathematik der Universitat Hamburg (Promotion)

2004-2013: wissenschaftlicher Mitarbeiter am Institut furMathematik der Universitat Rostock (Habilitation)

seit WS 2013: Professor fur Business Intelligence und Statistik ander FH Stralsund


1 Formalien

Ablauf

I In der Lehrveranstaltung Operations Research (mit”s“)

werden wir uns mit Modellen und Methoden beschaftigen, diemoglichst optimale (Unternehmens-)Entscheidungenvorbereiten sollen.

I Operations Research umfasst weit mehr als die imModulhandbuch aufgefuhrten Themen, und ich werdeversuchen, Ihnen Operations Research in einer ausreichendenBreite vorzustellen.

I Ich werde die Lehrveranstaltung (Mi+Do, 09.45 - 11.15 Uhr)als Einheit von Vorlesung und Ubung halten, d.h. nach derVorstellung theoretischer Konzepte werden wir gleichakademische und anwendungsnahe Beispiele behandeln.

I Als Prufungsleistung ist eine zweistundige Klausur zubestehen.


1 Formalien

Ablauf







1 Formalien

Ablauf







1 Formalien

Ablauf







1 Formalien

Ablauf

Ubungsaufgaben

Ich werde Ubungsaufgaben stellen, fur deren Bearbeitung Sie biszur ersten Lehrveranstaltung der nachsten Woche Zeit haben. Siegeben vor der Lehrveranstaltung an, welche Ubungsaufgaben Siegelost haben, und einer von Ihnen prasentiert dann die Losung. Furdie Zulassung zur Klausur mussen Sie mindestens 50% derUbungsaufgaben bearbeiten.

ACHTUNG

Nachste Woche nehme ich an der Jahrestagung der DMV-OMGteil, die Veranstaltung fallt daher aus und wird in der Blockwochevom 18.-22.11. nachgeholt.


1 Formalien

Ablauf

Ubungsaufgaben

Ich werde Ubungsaufgaben stellen, fur deren Bearbeitung Sie biszur ersten Lehrveranstaltung der nachsten Woche Zeit haben. Siegeben vor der Lehrveranstaltung an, welche Ubungsaufgaben Siegelost haben, und einer von Ihnen prasentiert dann die Losung. Furdie Zulassung zur Klausur mussen Sie mindestens 50% derUbungsaufgaben bearbeiten.

ACHTUNG

Nachste Woche nehme ich an der Jahrestagung der DMV-OMGteil, die Veranstaltung fallt daher aus und wird in der Blockwochevom 18.-22.11. nachgeholt.


1 Formalien

Literatur

Es gibt eine große Auswahl an Literatur zu Operations Researchmit unterschiedlichen Schwerpunkten. Zu meiner Vorlesungempfehle ich die folgenden Bucher:

Dempe, Schreier: Operations Research - Deterministische Modelleund Methoden, Teubner.

Domschke, Drexl: Einfuhrung in Operations Research, Springer.

Zimmermann: Operations Research - Methoden und Modelle furWirtschaftsingenieure, Betriebswirte, Informatiker, Springer.


1 Formalien

Literatur






1 Formalien

Literatur






2 Operations Research

Operations Research

Operations Research

I Die Meinungen, was Operations Research ist, gehen weitauseinander. Sicherlich gehort dazu jedoch einerseits dasModellieren von Problemen aus der Praxis und andererseitsdie Anwendung und Entwicklung von mathematischenMethoden zur Losung der modellierten Probleme.

I Wir werden uns nahezu ausschließlich mit Modellen undMethoden der Operations Research beschaftigen, aber z.B.nicht damit, wie man die Modellierung von Problemen aus derPraxis interdisziplinar angeht oder wie man Methoden optimalauf einem Rechner implementiert.



Operations Research

Operations Research

I Die Meinungen, was Operations Research ist, gehen weitauseinander. Sicherlich gehort dazu jedoch einerseits dasModellieren von Problemen aus der Praxis und andererseitsdie Anwendung und Entwicklung von mathematischenMethoden zur Losung der modellierten Probleme.

I Wir werden uns nahezu ausschließlich mit Modellen undMethoden der Operations Research beschaftigen, aber z.B.nicht damit, wie man die Modellierung von Problemen aus derPraxis interdisziplinar angeht oder wie man Methoden optimalauf einem Rechner implementiert.



Historisches

Historisches

I Ende der 1930er Jahre wurde der Begriff Operations Researchfur die Arbeit von Wissenschaftlern im Dienst der britischenArmee verwendet, die sich mit den Einsatzmoglichkeiten desRadar und optimalen Strategien im Luft- bzw. Seekampfbeschaftigten.

I Die Gemeinsamkeit dieser Forschung war der Einsatzmathematischer Methoden zur Unterstutzung vonEntscheidungen.



Historisches

Historisches

I Ende der 1930er Jahre wurde der Begriff Operations Researchfur die Arbeit von Wissenschaftlern im Dienst der britischenArmee verwendet, die sich mit den Einsatzmoglichkeiten desRadar und optimalen Strategien im Luft- bzw. Seekampfbeschaftigten.

I Die Gemeinsamkeit dieser Forschung war der Einsatzmathematischer Methoden zur Unterstutzung vonEntscheidungen.



Historisches

Historisches

I Die Erfolge des Operations Research fuhrten nach demzweiten Weltkrieg zu zahlreichen Grundungen vonOR-Abteilungen durch Unternehmen bzw. Hochschulen, diesich aus angewandter bzw. theoretischer Sicht mit dermathematischen Modellierung hauptsachlichbetriebswirtschaftlicher Standardprobleme beschaftigten.

I Daher hat Operations Research heutzutage zwei Bereiche,einen eher angewandt-wirtschaftlichen und einen ehertheoretisch-mathematischen.



Historisches

Historisches

I Die Erfolge des Operations Research fuhrten nach demzweiten Weltkrieg zu zahlreichen Grundungen vonOR-Abteilungen durch Unternehmen bzw. Hochschulen, diesich aus angewandter bzw. theoretischer Sicht mit dermathematischen Modellierung hauptsachlichbetriebswirtschaftlicher Standardprobleme beschaftigten.

I Daher hat Operations Research heutzutage zwei Bereiche,einen eher angewandt-wirtschaftlichen und einen ehertheoretisch-mathematischen.



Historisches

Historisches

I Stark angeregt wurde die Entwicklung des OperationsResearch durch die Entwicklung der elektronischenDatenverarbeitung und die Entwicklung der Simplex-Methodezur Losung linearer Optimierungsaufgaben durch Dantzig(1949) und Tucker (1950).

I In den 1960er Jahren durchlief Operations Research inDeutschland eine sturmische Phase mit einem starken Hypeund anschließender Desillusionierung.

I Heutzutage ist Operations Research sehr vielseitig und wird inDeutschland durch die Gesellschaft fur Operations Research(GOR) vertreten, die 1998 aus einer eher angewandten undeiner eher theoretischen Gesellschaft fur Operations Researchhervorgegangen ist.



Historisches

Historisches






Historisches

Historisches






Optimierungsprobleme

Die mathematische Modellierung vieler Probleme aus der Praxisfuhrt auf Optimierungsprobleme:

Definition

Als allgemeines mathematisches Optimierungsproblem (oder ma-thematisches Programm) bezeichnet man das Problem, zu ge-gebenen reellwertigen Funktionen f : X → R, gi : X → R(i = 1, . . . ,m), auf einer Menge X eine Maximalstelle (bzw. Mi-nimalstelle) x ∈ X von f unter den Nebenbedingungen gi (x) ≤ bi

(bzw. gi (x) = bi bzw. gi (x) ≥ bi ), i = 1, . . . ,m, zu finden.


3 Lineare Optimierungsprobleme

Lineare Programme

Ist X = Rn und sind die Funktionen f , gi (i = 1, . . . ,m) linear, sospricht man von einem linearen Optimierungsproblem (oderlinearen Programm).

I Lineare Optimierungsprobleme sind eine der wichtigstenProblemklassen des Operations Research und treten invielfaltigen Anwendungen auf.

I Sie haben das Simplex-Verfahren zur Losung linearerOptimierungsprobleme schon in Mathematik II kennengelernt,wir wiederholen dieses aber aufgrund seiner großen Bedeutungim Folgenden.



Lineare Programme






Lineare Programme






Lineare Programme in kanonischer Form

Definition

Bei einem linearen Optimierungsproblem in kanonischer Formsind

I x1, . . . , xn ≥ 0 so gesucht, dass die lineare Zielfunktionf (x) = c1x1 + · · ·+ cnxn (+d) maximal wird,

I wobei x1, . . . , xn eingeschrankt sind durch lineare

Ungleichungen

a11x1 + . . . +a1nxn ≤ b1...

......

am1x1 + . . . +amnxn ≤ bm .

.


3 Lineare Optimierungsprobleme3.1 Produktionsplanung

Ein Problem der Produktionsplanung

Das Mozartproblem

Beispiel

Eine Firma stellt Mozartkugeln und Mozarttaler aus Marzipan, Nou-gat und Kakao her. Pro Packung Mozartkugeln benotigt man 2 Tei-le Marzipan, 1 Teil Nougat, 1 Teil Kakao, und beim Verkauf ei-ner Packung macht man 3 EUR Gewinn. Pro Packung Mozarttalerbenotigt man 1 Teil Marzipan, 1 Teil Nougat, 2 Teile Kakao, undbeim Verkauf einer Packung macht man 2 EUR Gewinn. Vorhan-den sind 10 Teile Marzipan, 6 Teile Nougat, 9 Teile Kakao. WievielePackungen Mozartkugeln / Mozarttaler sollte man produzieren?

1. Stellen Sie das zugehorige lineare Programm auf.



Das Mozartproblem

Das Mozartproblem als lineares Programm

Modelliert x1 die Anzahl der Packungen von Mozartkugeln und x2

die Anzahl der Packungen von Mozarttalern, dann istf (x) = 3x1 + 2x2 unter den Nebenbedingungen x1 ≥ 0, x2 ≥ 0,2x1 + 1x2 ≤ 10, 1x1 + 1x2 ≤ 6, 1x1 + 2x2 ≤ 9 zu maximieren.



Graphische Losung des Mozartproblems

Geometrie linearer Programme

Die Losungsmenge jeder einzelnenUngleichung ist eine Halbebene, derSchnitt aller dieser Halbebenen istder Polyeder der zulassigen Punkte.In den Ecken des Polyeders liegt inzwei Ungleichungen Gleichheit vor.



Graphische Losung des Mozartproblems


Um die Zielfunktion 3x1 + 2x2 zumaximieren, verschiebe man diedurch 3x1 + 2x2 = 0 gegebeneGerade soweit in Richtung desKostenvektors c = (3, 2)T , dass Sieden Polyeder der zulassigen Punktegerade noch schneidet. DieSchnittmenge enthalt dannoffensichtlich eine Ecke desPolyeders, welche das lineareOptimierungsproblem lost, hierx = (4, 2)T .


3 Lineare Optimierungsprobleme3.2 Kapazitatsplanung

Ein Problem der Kapazitatsplanung

Beispiel

Eine Firma stellt zwei Produkte her, fur deren Fertigung drei Maschi-nen A, B, C zur Verfugung stehen. Maschine A kann 170 Stunden,B kann 150 Stunden und C kann 180 Stunden im Monat laufen. DerVerkauf einer Mengeneinheit des ersten Produktes bringt 300 EURGewinn, eine Mengeneinheit des zweiten Produkts 500 EUR. Um ei-ne Mengeneinheit des ersten Produkts zu fertigen, benotigt man eineStunde lang Maschine A und eine Stunde lang Maschine B. wahrendfur das zweite Produkt Maschine A zwei Stunden, Maschine B eineStunde und Maschine C drei Stunden benotigt wird.

2. Stellen Sie das zugehorige lineare Programm auf.

3. Losen Sie das Problem graphisch.

4. Wieviele optimale Punkte gabe es, wenn beide Produkte den gleichenGewinn abwerfen wurden?



Graphische Losung des Kapazitatsproblems


I max 300x1 + 500x2 unter denNebenbedingungen x1, x2 ≥ 0undx1 + 2x2 ≤ 170,x1 + x2 ≤ 150,3x2 ≤ 180.

I Optimal ist x = (130, 20)T .

I Bei max c1x1 + c2x2 mit c1 = c2

ware jeder Punkt auf derStrecke von (150, 0) nach(130, 20) optimal.



















Anwendungen linearer Programme


I Produktionsplanung bei beschrankten Resourcen zurMaximierung des Gewinns

I Mischungsprobleme wie z.B. das Diat-Problem: WelcheKombination von Lebensmitteln hat die minimalen Kostenunter der Nebenbedingung, dass bestimmte Mindest- undHochstgrenzen fur die einzelnen Nahrwerte eingehaltenwerden?

I Mehrguterfluss-Probleme (engl. multicommodity flowproblems) wie z.B. das Leiten von Verkehr durch ein Netz beibeschrankter Kapazitat, das auch beim Routing in derTelekommunikation auftritt.

















Lineare Optimierung

Schwierigkeiten bei der linearen Optimierung

I Bei Problemen mit mehr als zwei (oder drei) Variablen ist einegraphische Losung nicht mehr moglich.

I Nicht jedes lineare Programm besitzt eine eindeutigeOptimallosung:

I Kein Punkt konnte zulassig sein (= dieUngleichungsnebenbedingungen schließen sich aus)

I Der Polyeder der zulassigen Punkte ist unbeschrankt, dannkann es zulassige Punkte mit beliebig hohenZielfunktionswerten geben (wie bei max x unter derNebenbedingung x ≥ 0).

I Die durch die Zielfunktion induzierte Hyperebene kann beimoptimalen Wert parallel zu einer Seitenhyperflache desPolyeders der zulassigen Punkte liegen, dann gibt es unendlichviele Optimallosungen.



Lineare Optimierung









Lineare Optimierung









Lineare Optimierung









Lineare Optimierung









Lineare Optimierung

Hauptsatz der linearen Optimierung

Hat ein lineares Programm in kanonischer Form einen endlichenOptimalwert, so wird dieser auch in einer Ecke angenommen.

Trivialer Losungsalgorithmus fur nVariablen

I Potentielle Ecken aus demSchnitt von n Hyperebenenberechnen,

I uberprufen, welche Eckenzulassig sind,

I Zielfunktionswerte vergleichen.

Problem: Großer Aufwand!



Lineare Optimierung

Hauptsatz der linearen Optimierung

Hat ein lineares Programm in kanonischer Form einen endlichenOptimalwert, so wird dieser auch in einer Ecke angenommen.

Trivialer Losungsalgorithmus fur nVariablen

I Potentielle Ecken aus demSchnitt von n Hyperebenenberechnen,

I uberprufen, welche Eckenzulassig sind,

I Zielfunktionswerte vergleichen.

Problem: Großer Aufwand!


3 Lineare Optimierungsprobleme3.3 Das Simplex-Verfahren

Idee des Simplex-Verfahrens


Wandere die Ecken des Polyeders (= Schnitt von n Hyperebenen)ab und tausche in jedem Schritt eine Hyperebene gegen eineandere aus (dadurch bewegt man sich entlang von Kanten desPolyeders), so dass sich der Zielfunktionswert maximal vergroßert.

Notation

Schreibe ein lineares Programm in kanonischer Form als max cT xunter den Nebenbedingungen x ≥ 0 und Ax ≤ b mit einer MatrixA ∈ Rn×m und Vektoren c, x ∈ Rn, b ∈ Rm, wobei dieUngleichungen komponentenweise zu interpretieren sind.





Wandere die Ecken des Polyeders (= Schnitt von n Hyperebenen)ab und tausche in jedem Schritt eine Hyperebene gegen eineandere aus (dadurch bewegt man sich entlang von Kanten desPolyeders), so dass sich der Zielfunktionswert maximal vergroßert.

Notation

Schreibe ein lineares Programm in kanonischer Form als max cT xunter den Nebenbedingungen x ≥ 0 und Ax ≤ b mit einer MatrixA ∈ Rn×m und Vektoren c, x ∈ Rn, b ∈ Rm, wobei dieUngleichungen komponentenweise zu interpretieren sind.



Das Mozartproblem in kanonischer Form

Beispiel

Beim Mozartproblem in kanonischer Form ist

A =

2 11 11 2

, b = (10, 6, 9)T und c = (3, 2)T .



Schlupfvariablen

Lineare Programme in Standardform

Statt in kanonischer Form benutzt man beim Simplex-Verfahrendie Standardform (oder Normalform) eines linearen Programms,bei der nach der Losung von max cT x unter Ax = b, x ≥ 0,gesucht wird (da man mit dem Gleichungssystem Ax = b besserrechnen kann).

Schlupfvariablen

Durch Einfuhrung von Schlupfvariablen kann man jedes inkanonischer Form vorliegende lineare Programm umschreiben in einlineares Programm in Standardform, wobei sich allerdings n erhoht.



Schlupfvariablen

Lineare Programme in Standardform

Statt in kanonischer Form benutzt man beim Simplex-Verfahrendie Standardform (oder Normalform) eines linearen Programms,bei der nach der Losung von max cT x unter Ax = b, x ≥ 0,gesucht wird (da man mit dem Gleichungssystem Ax = b besserrechnen kann).

Schlupfvariablen

Durch Einfuhrung von Schlupfvariablen kann man jedes inkanonischer Form vorliegende lineare Programm umschreiben in einlineares Programm in Standardform, wobei sich allerdings n erhoht.



Das Mozartproblem in Standardform

Beispiel

Beim Mozartproblem in Standardform mit Schlupfvariablen ist

A =

2 1 1 0 01 1 0 1 01 2 0 0 1

b = (10, 6, 9)T und c = (3, 2, 0, 0, 0)T .



Zulassige Basislosungen

Definition

Die Spalten einer Matrix A heißen linear unabhangig, falls das Glei-chungssystem Ax = b fur jede rechte Seite b eine eindeutige Losungx besitzt.

Definition

Sei A ∈ Rm×n, b ∈ Rm und M = {x ∈ Rn |Ax = b , x ≥ 0}die Menge der zulassigen Punkte. Ein Punkt x ∈ M heißt zulassigeBasislosung, wenn die zu positiven Komponenten von x gehorendenSpaltenvektoren von A linear unabhangig sind, d.h. {aj | xj > 0} istlinear unabhangig.



Zulassige Basislosungen

Definition

Die Spalten einer Matrix A heißen linear unabhangig, falls das Glei-chungssystem Ax = b fur jede rechte Seite b eine eindeutige Losungx besitzt.

Definition

Sei A ∈ Rm×n, b ∈ Rm und M = {x ∈ Rn |Ax = b , x ≥ 0}die Menge der zulassigen Punkte. Ein Punkt x ∈ M heißt zulassigeBasislosung, wenn die zu positiven Komponenten von x gehorendenSpaltenvektoren von A linear unabhangig sind, d.h. {aj | xj > 0} istlinear unabhangig.



Basislosungen

Startbasislosung des Simplex-Verfahrens

Fur ein aus kanonischer Form entstandenes lineares Programm in

Standardform ist bei b ≥ 0 automatisch

(0b

)eine zulassige

Basislosung, da die zugehorigen Spalten von A die Einheitsmatrixbilden.

Charakterisierung von zulassigen Basislosungen

Um eine zulassige Basislosung x zu bekommen, setzt man alsoeinige Komponenten XN von x auf Null (die zurNichtbasisindexmenge N gehorigen), so dass sich die restlichenKomponenten XB (die zur Basisindexmenge B gehorigen)eindeutig aus Ax = b ergeben, wobei man aber dieVorzeichenbedingung x ≥ 0 beachten muss.

Die Ecken des Polyeders entsprechen zulassigen Basislosungen.



Basislosungen




(0b

)eine zulassige







Basislosungen




(0b

)eine zulassige







Schritte des Simplex-Verfahrens

Ein Schritt des Simplex-Verfahrens

Sei x eine zulassige Basislosung mit Basisindexmenge B.

I Finde ein q ∈ N, so dass die Zielfunktion mit wachsendem xq

von 0 an großer wird, wenn ansonsten xj = 0 fur j ∈ N \ {q}bleibt.

I Bestimme das maximale xq, fur dass noch xB ≥ 0 gilt.

I Dann ist zumindest xp = 0 fur ein p ∈ B.

I Tausche p ∈ B und q ∈ N aus und beginne erneut.

Beende des Simplex-Verfahren, falls

I die zulassige Basislosung schon optimal ist (d.h. es keinpassendes q gibt),

I das lineare Programm unbeschrankt ist (d.h. es gibt keinpassendes p)



Schritte des Simplex-Verfahrens

Ein Schritt des Simplex-Verfahrens

Sei x eine zulassige Basislosung mit Basisindexmenge B.

I Finde ein q ∈ N, so dass die Zielfunktion mit wachsendem xq

von 0 an großer wird, wenn ansonsten xj = 0 fur j ∈ N \ {q}bleibt.

I Bestimme das maximale xq, fur dass noch xB ≥ 0 gilt.

I Dann ist zumindest xp = 0 fur ein p ∈ B.

I Tausche p ∈ B und q ∈ N aus und beginne erneut.

Beende des Simplex-Verfahren, falls

I die zulassige Basislosung schon optimal ist (d.h. es keinpassendes q gibt),

I das lineare Programm unbeschrankt ist (d.h. es gibt keinpassendes p)



Finden von q

Finden des Nichtbasisindex q

I Spalte Ax = b auf in ABxB + ANxN = b.

I Also xB = A−1B (b − ANxN).

I Daher cT x = cTB xB + cT

N xN = cTB A−1

B b− (cTB A−1

B AN − cTN )xN .

I Mit zTN := cT

B A−1B AN wachst also cT x bei Erhohung von xq,

falls zq − cq < 0 ist.

I Gibt es kein solchen Index q, so ist x Optimallosung.

I Ansonsten wahle einen Index q mit zq − cq < 0.



Finden von q





N xN = cTB A−1

B b− (cTB A−1

B AN − cTN )xN .

I Mit zTN := cT







Finden von q





N xN = cTB A−1

B b− (cTB A−1

B AN − cTN )xN .

I Mit zTN := cT







Finden von q





N xN = cTB A−1

B b− (cTB A−1

B AN − cTN )xN .

I Mit zTN := cT







Finden von q





N xN = cTB A−1

B b− (cTB A−1

B AN − cTN )xN .

I Mit zTN := cT







Finden von q





N xN = cTB A−1

B b− (cTB A−1

B AN − cTN )xN .

I Mit zTN := cT







Finden von p

Finden des Basisindex p

I Um den maximalen Wert zu bestimmen, auf den man xq

erhohen darf, ohne xB ≥ 0 zu verletzen, muß wegenxB = A−1

B b − A−1B ANxN und xj = 0 fur alle j ∈ N \ {q} die

Ungleichung xi = (A−1B b)i − (A−1

B AN)i ,qxq ≥ 0 fur jedes i ∈ Bgelten.

I Ist (A−1B AN)i ,q ≤ 0 fur alle i , so kann man xq beliebig

großwahlen und das lineare Programm ist unbeschrankt.

I Ansonsten wahle einen Index p mit (A−1B AN)p,q > 0 aus,

erhohe xq von 0 auf (A−1B b)p/(A−1

B AN)p,q und setze xp auf 0,dann ist das so entstandene x eine neue zulassige Basislosung.



Finden von p














Finden von p














Simplex-Tableau

Simplex-Tableau

I Rechentechnisch ist es vorteilhaft, die Spalten von A durchZeilenoperationen (die die Losungsmenge der GleichungAx = b nicht andern) so abzuandern, dass die zu Basisindizesgehorigen Spalten AB immer die Einheitsmatrix bilden.

I Dies fuhrt in jedem Schritt zu einer Anderung der Matrix Adie man gut in einem Simplex-Tableau genannten Schemafesthalten kann.



Simplex-Tableau

Simplex-Tableau

I Rechentechnisch ist es vorteilhaft, die Spalten von A durchZeilenoperationen (die die Losungsmenge der GleichungAx = b nicht andern) so abzuandern, dass die zu Basisindizesgehorigen Spalten AB immer die Einheitsmatrix bilden.

I Dies fuhrt in jedem Schritt zu einer Anderung der Matrix Adie man gut in einem Simplex-Tableau genannten Schemafesthalten kann.



Vorteile

Vorteile des Simplex-Verfahrens

I leicht zu implementieren,

I viele Moglichkeiten, spezielle Strukturen eines linearenProgramms zu nutzen,

I einfache Berechnungen,

I in der Praxis oft auch sehr schnell,

I Speicherbedarf ist durch Nutzung des Simplex-Tableaus gering



Vorteile









Vorteile









Vorteile









Vorteile









Nachteile

Nachteile des Simplex-Verfahrens

I Die in der Praxis gute Laufzeit ist theoretisch nicht beweisbar,tatsachlich ist fur bestimmte lineare Programme die Laufzeitsogar exponentiell.

I Ohne entsprechende Auswahlverfahren sind Endlosschleifenmoglich.

I Fur Probleme in kanonischer Form ist die Laufzeit polynomial,namlich O(nm).

Bemerkung

Es gibt Alternativen zum Simplex-Verfahren, die beweisbarpolynomial (also theoretisch schnell) sind, aber in Praxis vomSimplex-Algorithmus geschlagen werden, oder nur Naherungenstatt exakter Losungen liefern.



Nachteile





Bemerkung




Nachteile





Bemerkung




Nachteile





Bemerkung

Es gibt Alternativen zum Simplex-Verfahren, die beweisbarpolynomial (also theoretisch schnell) sind, aber in Praxis vomSimplex-Algorithmus geschlagen werden, oder nur Naherungenstatt exakter Losungen liefern.18.+19.09.2013 Modul: Operations Research – Dr.habil. Jochen Merker 33/43


Wahl von q und p

Blandsche Regel

Wahle sowohl fur den Nichbasisindex q ∈ N als auch denBasisindex p ∈ B stets den Kandidaten mit dem kleinsten Index,dann treten keine Schleifen auf und das Simplexverfahren endetnach endlich vielen Schritten.

Regel des steilsten Abstiegs

Es wird derjenige Nichbasisindex q ∈ N mit minimalem zq − cq < 0und derjenige Basisindex p mit minimalem (A−1

B AN)p,q > 0gewahlt, in der (nicht immer begrundeten) Hoffnung, dass dieseWahl zu einer maximalen Erhohung der Zielfunktion fuhrt.Tatsachlich kann es in diesem Fall zu Endlosschleifen kommen, unddagegen benotigt man Schutzmechanismen!



Wahl von q und p

Blandsche Regel

Wahle sowohl fur den Nichbasisindex q ∈ N als auch denBasisindex p ∈ B stets den Kandidaten mit dem kleinsten Index,dann treten keine Schleifen auf und das Simplexverfahren endetnach endlich vielen Schritten.

Regel des steilsten Abstiegs

Es wird derjenige Nichbasisindex q ∈ N mit minimalem zq − cq < 0und derjenige Basisindex p mit minimalem (A−1

B AN)p,q > 0gewahlt, in der (nicht immer begrundeten) Hoffnung, dass dieseWahl zu einer maximalen Erhohung der Zielfunktion fuhrt.Tatsachlich kann es in diesem Fall zu Endlosschleifen kommen, unddagegen benotigt man Schutzmechanismen!



Implementierung des Simplex-Verfahrens

5. Im Folgenden finden Sie eine Implementierung des Simplex-Verfahrens in Cmit der Regel des steilsten Abstiegs, die das in kanonischer Form durch

A =

2 3 14 1 23 4 2

, b = (5, 11, 8)T und c = (5, 4, 3)T

gegebene lineare Programm lost.

Machen Sie sich die einzelnen Schritte des Programms und dieAktualisierung des Simplex-Tableaus in jedem Schritt klar.




#include <stdio.h>#define INFINITY 999#define N 3#define M 6

void BestimmeMinimum(float *, int *, int);void BestimmezMinusc

(float *, float [][], float [], int []);

int main(){float c[M]={5,4,3,0,0,0};float a[N][M]={ {2,3,1,1,0,0},

{4,1,2,0,1,0},{3,4,2,0,0,1} };

float b[N]={5,11,8};18.+19.09.2013 Modul: Operations Research – Dr.habil. Jochen Merker 36/43



float zMinusc[M]={0,0,0,0,0,0};int positionOfMinimumInzMinusc;float miniratio[N];int miniratiominpos;float key;int gooutcol;float x[M];int i,j;int basic[N];int nonbasic[N];for(i=0;i<N;i++) {basic[i]=(i+N);nonbasic[i]=i; }

int flag;




do {BestimmezMinusc(zMinusc,a,c,basic);BestimmeMinimum(zMinusc,&positionOfMinimumInzMinusc,M);for(i=0;i<N;i++) {

x[basic[i]]=b[i];x[nonbasic[i]]=0; }

for(i=0;i<N;i++) {if(a[i][positionOfMinimumInzMinusc] <= 0) {miniratio[i]=INFINITY;continue; }

miniratio[i]=b[i]/a[i][positionOfMinimumInzMinusc];}BestimmeMinimum(miniratio,&miniratiominpos,N);for(i=0;i<N;i++)

if(miniratiominpos==i) gooutcol=basic[i];




basic[miniratiominpos]=positionOfMinimumInzMinusc;nonbasic[positionOfMinimumInzMinusc]=gooutcol;key=a[miniratiominpos][positionOfMinimumInzMinusc];b[miniratiominpos]/=key;for(i=0;i<M;i++)

a[miniratiominpos][i]/=key;for(i=0;i<N;i++) {

if(miniratiominpos==i) continue;key=a[i][positionOfMinimumInzMinusc];for(j=0;j<M;j++)a[i][j]-=a[miniratiominpos][j]*key;

b[i]-=b[miniratiominpos]*key; }




for(i=0;i<M;i++) {flag=1;if(zMinusc[i]<0) {flag=0;break; }

}} while (flag==0);printf("Optimale Basislosung: ");for(i=0;i<N;i++)printf("x[%d]=%g ",basic[i]+1,b[i]);

printf("\nMaximaler Wert der Zielfunktion: ");float valueOfTheObjectiveFunction = 0;for(i=0;i<N;i++)valueOfTheObjectiveFunction += c[i]*x[i];

printf("%g",valueOfTheObjectiveFunction);return 0; }




void BestimmezMinusc(float *temp,float a[N][M], float c[M], int basic[N]) {

int i,j;for(i=0;i<M;i++) { temp[i]=0;for(j=0;j<N;j++)

temp[i]+=c[basic[j]]*a[j][i];temp[i]-=c[i]; } }

void BestimmeMinimum(float *arr, int *arrminpos, int n) {int i; float arrmin=arr[0];*arrminpos=0;for(i=0;i<n;i++)if(arr[i]<arrmin) {arrmin=arr[i];*arrminpos=i; } }



Erweitertes Mozartproblem

6. Losen Sie das erweiterte Mozartproblem, bei dem zusatzlich Mozartstangenproduziert werden konnen, die einen Gewinn von 6 EUR pro verkaufterPackung abwerfen und fur die man pro Packung 3 Teile Marzipan, 1 TeilNougat und 1 Teil Kakao benotigt.

7. Andern Sie die Implementierung so ab, dass nach jedem Schritt desSimplex-Verfahrens das Simplex-Tableau ausgegeben wird.



Lineare Programme in anderer Form

8. Wie kann man ein lineares Programm in kanonische Form uberfuhren, beidem

I die Zielfunktion minimiert werden soll?I die Nebenbedingungen Ungleichungen mit ≥ enthalten?I die Nebenbedingungen Gleichungen enthalten?

9. Erweitern Sie die Implementierung des Simplexverfahrens so, dass derBenutzer die Anzahl der Variablen und Nebenbedingungen, die Matrix Aund die Vektoren b, c eingeben kann.


Documents

Modul: Operations Research - Universität Rostockmerker/SkriptOperationsResearch.pdf · 1Formalien Ablauf I In der Lehrveranstaltung Operations Research (mit " s\) werden wir uns