Sachverzeichnis

Abbruchbedingung 117 Abstiegsbedingung 115 Abteilung 80 Abteilungsprogramm 81, 94 Adjazetenreprlisentation 254 Aktivitlit 13, 171, 174 Algorithmus 3,187,234,277 AII-Integer-Verfahren 183 Alternativen 171, 184,273 Anfangsbedingungen 266 Anfangszustand 7, 266, 273 Anpassungsschritt 211 Approximation 166 Assignment-Problem 224 Ausgangstableau 25,38,89, 100, 155 Auslotung 192 Ausgangslosung 121 Austauschregel19, 146 Auswahlregel 183

Baias-Algorithmus 187,279 Basis 35, 39, 58, 66, 99, 91,102,106,146,

151 BasislOsung 13, 17,24,36,38,220,221,

222,225 - erweiterte 101 - zullissige 13, 17,23, 38, 91 - optimale 17,22,38,44,70 Basismatrix 39, 44, 221 Basisvariable 14,36, 102 Basiswechsel 18,48,58,62,71,74, 103,

146, 181 Bedarf206 Begrenzte Enumeration 186 Beschrlinkte Variable 101 Beschriinkungskonstante 17,41,50,57,58,

71,73,221,225 Beschrankungsmatrix 12, 57, 65, 79, 217,

225 Beschriinkungsvektor 73, 151 Bestandsfiihrung 262 Bewertung 25,49,92, 130,211 Bewertungsschritt 210 Beziehungen zwischen Primal und Dual

41,50 Big-M-Methode 121 Binlirer Vektor 191 Binlires Programm, 171, 184,225,234,279 - lineares Programm 187 Binlirkodierung 253, 261

Binarvariable 173, 184, 237 Boolesche Variable 171 Bounding 186 Branch-and-Bound-Verfahren 186, 188,

192,197,279 Branching 186 Bruchteil 177, 178

Chromosom 259, 260 Complementary Slackness 45,132 Constraint Qualification 133, 139 Crossover 259,260

Deckungsbeitrag 13,52 Degeneration 28,35,37,82,223 Dekodierung 254 Dekompositions-Algorithmus 83, 91, 94 Dekompositionsprinzip 79, 84, 94, 98 Diskrete Optimierung 6 Dreigruppen-Permutation 249 Dual 41, 50, 63,110, 148 - des Transportmodells 224 Dualer Pivotschritt 75

287

Duale Simplex-Methode 53, 68, 159, 177, 189,200,278

- Unzullissigkeit 118 Dualitatsslitze 42, 51, 117 Dualitatstheorie 40, 48, 148, 277 Duality Gap 117 Dualvariable 41, 46, 48, 58, 73, 82, 86, 87,

92,97,99,116,130,139 - nicht positive 49 - nicht vorzeichenbeschrankte 50 Dual zulassig 54, 66, 11 0, 177, 189, 200 Durchschnittsverhalten 109,233,237,275 Dynamische Prograrnmierung 2, 265, 273 Dynamisches Programm 273,279

Eckentheorem 31 Ein-Punkt-Rekombination 261 Elementare Operationen 13,39,236 Elementarmatrix 100 Ellipsoid 1l0, 113 Eltern 261 Endzustand 8, 265 Engpass 18, 28 Entfernungsmatrix 245 Entscheidungsalternative 1 Entscheidungsbaum 185 Entscheidungsmodell I, 3 Entscheidungsproblem 1 Entscheidungsprozess 266, 273 Entscheidungstheorie 3 Entscheidungsvariable I, ll, 79, 172

288

Entscheidungszeitpunkt 266 Enumeration 184, 196 Erklarungsmodell 3 Eroffnungsverfahren 209, 240, 244 Ersatzzeitpunkt 268 Erweiterte Basislosung 102 Evolution 259 Extremalpunkt 30, 31, 32, 84, 94, 95

Fitness 254, 255, 259, 260 Fitness-Differenz 257 Fixkosten-Problem 173 Folge von Entscheidungen 265 Fractional-Integer-Verfahren 175,278

Ganzzahlige BasislOsung 221 - lineare Programmierung 175,278 - Uisung 176, 178, 198 - Programmierung 171,206,277 Ganzzahliger Teil 175 Ganzzahliges lineares Programm 6, 172,

173,278 - Programm 6, 171 Ganzzahligkeit 172, 183, 221, 225 Ganzzahligkeitsbedingung 171, 183, 198,

237 Gemischt-ganzzahliges Programm 6,171,

197 Generationenkonzept 263 Genetische Algorithmen 252, 259 Genkombination 262 Gewicht 85, 92, 95, 166 Gitterpunkt 172 Gleichgewichtsbedingung 206,218 Gleichgewichtskonzept 263 Globales Minimum 5, 126, 127 Globales Optimum, 168 Gomory-Algorithmus 181 Gomory-Schnitt 177 Gradient 112, 114, 136, 156 Greedy-Prinzip 239 Greedy-Verfahren 243 GroBer-Gleich-Restriktionen 23, 49, 50, 60 Gtlterwagenumlauf 207

Heuristik 239, 244 - deterministische 239 - zufallsgesteuerte 239, 249 Hilfsprogramm 152, 15, 157, 163, 198,278 Hilfszielfunktion 24, 28 Hilfszielfunktionszeile 25, 142

Innere-Punkt-Methode Ill, 115 Interpretation der Dualvariablen 48

Sachverzeichnis

Inverse der Basis 38, 40, 43, 58,66,99 Iterationsschritt 90, 192 Iterationsverfahren 82, 163,209 Iterationsvorschrift 155

Kanonische Form 13,23,39,58, 142, 177, 200

Kapazitat 13, 19, 80 Karmarkar-Algorithmus 111,235,278 Keine zullissige Losung 28, 31, 56 Kelley-Algorithmus 154, 162,278 Khachian-Algorithmus 110,235 Klee-Minty-Problem 106, 109 Knappheitspreise 48, 82, 86 Knapsack-Problem 234, 239 Knospe 186, 194, 197 Knoten 185, 196,272 Kodierung 253 Koeffizienten-Matrix 17,41,50,207,208,

219 Kombinatorische Verfahren 184,279 Komplexitatstheorie 235, 239, 283 Konkav 72,123 Konkave Funktion, 72, 123, 125 Kontrolltheorie 279 Kontrollvariable 7, 265, 269 Konvergenz 146, 151, 162, 181, 183 Konvex 30, 72, 123, 133 Konvexe Funktion, 126, 127, 136, 167 - Menge 30, 31, 126, 133 - Programmierung 123,278 Konvexes Maximum-Problem 125 - Minimum-Problem 125 - Programm, 5, 123, 125, 133, 139, 153, 162, 165 Konvexitat 30, 132 Konvexitatsbedingung 85,87,92,96, 167 Konvexkombination 16,30,31,36,84,85,

91,94,96,166 Kritischer Punkt 60, 65, 71, 72, 73 Kuhn-Tucker-Bedingungen 129, 135,136,

277 - Theorem 133 Kiihlfunktion 257 Kiinstliche Schlupfvariable 23, 60, 68, 93,

142,146,151,189 Kiirzester Weg 271 Kurzzyklen 231, 246

Lagrange-Funktion 129, 131, 136, 141 - Multiplikator 130, 139, 141 Layout-Planung 225 Lexikographisch 182 Linear abhangig 28, 33

Sachverzeichnis

- affine Transformation 112 - unabhlingig 33, 35, 36 Lineare Approximation 123 - Politik 274 - Programmierung 4,12 Lineares Assignment Problem 224 Lineares Programm 12 - allgemeine Form, 12 - kanonische Form, 13 - Normalform 12, 16,29,94,189 - Ranking 260 Linearisierung 155, 165 Linearkombination 33 Losungsspalte 20, 28, 55, 77, 99,103, 190 Losungsvektor 12, 58, 190 Lokale Kuhn-Tucker-Bedingungen 135, 139 - Optimalitiitsbedingungen 5 Lokales Minimum,S, 126 - Optimum 249

Maximum-Problem 11,72, 125 Maximin-Regel 244 Menge der optimalen LOsungen 126 - der zulassigen Losungen 14,30,84, 126,

153, 172 Minimum-Problem 11,41,53,72,125 Mutation 253, 254, 259, 262 Mutativ-selektive Verfahren 254 Myopisch 239

Nachfolger 190 Niiherungslosung 155, 183 Niiherungspolygon 166 Naturanaloge Verfahren 252 Negative Komponente 12, 50 Netzwerk 271 Nicht-Basisvariable 18,21,28,37,39,59,

63, 101, 175, 190,221 Nicht-ganzzahlige LOsung 175 Nicht-ganzzahliger Koeffizient 177 Nicht-linearesProgramm 165 Nicht-Negativit!itsbedingung 2, Ill, 130 Niveau-Linie IS Nordwest-Ecken-RegeI209,222 Normalform II, 16,29,43,45,94, III

Opportunitiitskosten 18, 21, 48, 210 Optimale Basislosung 22,38, 43, 58, 70, 92 - Entscheidung 266 - ganzzahlige LOsung 173, 183 - Losung 3, 15,28,32,36,43,45,58,70,

72,85,110,129,133,136,142,152,

289

154,162,164,177,183,216,225, 275

- Steuerung 267 Optimalitiit 37, 46, 51 Optimalitiitsbedingung 5, 277 Optimalitiitskriterium 3 Optimalitiitsprinzip 273, 277 Optimierungsmodell 3 Orakel236

Parameter 70, 71,76 Parametrische Programme 70 - Programmierung 58, 70, 277 Periode 266 Permutation 250 Permutationskodierung 253,261 Pfadreprlisentation 254 Pfeil 272 Phase I 24, 28, 93 Phase 1124, 29, 93,142,146,151 Pivot-Element 19,54,106,190 - -Spalte 19,28,55, 182, 189 --Wahl 106 - -Zeile 19,28,55, 190 Planungshorizont 269 PMX-Rekombination 261 Politik 267,274 Polyeder 15,31,32 Polygonzug 165 Polynom 236 Polynomial 109,236 - beschrlinkt 233 Polynominaler Algorithmus 109 Positionsnummer 254 Positionsrepriisentation 254 Positiv defmit 150, lSI - semidefinit 140, 149, lSI Positive Komponente 50,143 Postoptimale Analyse 57 Preistheorem 46, 51, 277 Pretiale Lenkung 81, 94 Primal 41, 42, 43, 45, 50, 63 - unzulassig 54, 68 - zulassig 56, 66, 110 Primale Innere-Punkt-Methode III, 115 - Unzullissigkeit 118 Prioritiitsregeln 239 ProblemgroBe 109, 235 Problemkiasse 235 -EXP 236 -NP 236 - NP-vollstlindig 236 -P236

290

Problemvariable 12, 17,46 Produktform der Inversen 101 Produktionsglattung 275 Produktionskoeffizient 19, 21 Produktionsplanung 2, 13,24,66,75 Projektion des Gradienten 114 Projektionsmatrix 114, 115

Quadratische Norm 114, 118 - Zielfunktion 139, 222, 274 Quadratisches Assignment-Problem 225,

240 - Programm 140, Quelle 206, 223, 225 Quellenbedingung 218 QueIlzeile 175, 181

Randoptima 130 Rang37,219 Rechenaurwand 108,184,197,235 Redundante Gleichung 208 Redundanz 28 Reduzierte Kosten 99,116,247 Reihenfolgebedingung 174 Rein ganzzahliges Programm 171, 184 Reinversion 101 Rekombination 260, 261, 262 Rekursionsbeziehung 191, 197,266 Rekursiv 266, 272 Relation 209, 220 Relatives Minimum 127 Relaxation 175, 189,256,278 Restriktion 2, 11, 13,38,48,58,65,79,91,

126, 130, 176,208,265 - in Gleichungsform 23, 49, 60,141, 145,

208 Restriktionskonstante 4, 12,23,49,58 - negative 23 Restriktionsver1etzung 156 Revidierte Simplex-Methode 99, 278 Richtung 113 Richtungsableitung 124 Richtungsvektor 115 Roulett-Verfahren 259 Rundreise 231 Rundungsfehler 183 Riickkopplungssteuerung 266, 273, 274, 279 Riicktransformation 113 Riickwiirtsrechnung 268 Riickwartsschritt 193 Riistkosten 1 73

Sattelpunkt 131 -Bedingung 131,135

Sachverzeichnis

- Satz 131 Schlupfvariable II, 13, 16,23,40,45,49,

59,74,85, 100, 141 Schnittebene 155, 163, 175, 183 Schnittebenen Verfahren 153, 175, 177, 183, Schranke 101, 167, 181, 197,256 Schritt1iinge 116 Schrittweite 113, 115 Selbstorganisierende Prozesse 252 Selektion 253,259,289 - zum Uberleben 263 - zum Fortpflanzen 263 Selektionsverfahren 258 Senke 206, 223, 225 Senkenbedingung 218 Sensitivitiitsanalyse 57. 58 Separierbare Funktion 165 Separierbares Programm, 165, 168 Simplex-Kriterium 37, 43,72,99, 101,221 - -Tableau 17,23,24,38, 58, 79, 99, 189 - -Verfahren 14, 16,25, 102, 109, 141,208,

235,278 - Sonderfalle 25 Simulated Annealing 252, 257 Simulation 250 Sintflutmethode 259,263 Skalarprodukt 114 Skalieren 112 Skalierte Abstiegsrichtung 116 Skalierte Projektionsmatrix 116 Skaliertes Problem 116 Skalierung 114 Skalierungsmatrix 119 Slater-Bedingung 133, 136, 139 Spezifische Zielfunktionsbeitriige 243 Spezielles Maximum-Problem 13, 16, 40,

46,54,83,91,110 Steilster Anstieg 106 Stepping-Stone-Methode 209, 222, 279 Stetige Optimierungsmodelle 4 Steuerung 7, 265, 267 Steuervariable 6 Stochastische Programmierung 279 Strafkostenverfahren 121 Strategie 267 Streng konkav 123 - konvex 123 Strikte Se1ektion 257,263 Struktur der Losung 57 Stiickweise linear 165 Stufe 272 Stiitzstelle 165, 167 Sukzessive Einbeziehung 244

Sachverzeichnis

- Entscheidungsprobleme 266, 271 - Hinzunahme 240 - Verbesserung 252 Systematische Veriinderung 57 Systemdynamik 7, 265, 267, 268, 274

Taylor-Entwicklung 155 Tenninplanung 174 Threshold Accepting 258, 263 Toleranzschwelle 258 Transfonnation III Transportfrequenz 240 Transporttnodell 206, 217, 222, 279 Travelling-Salesman-Problem 231, 236,244 Trennsatz fUr konvexe Mengen 133 Triangulierbarkeit 220

Uberschuss 207, 223 Unbeschrankt 28, 45, 57, 94, 102 Unzuliissigkeit24, 93,142,183,194 Updating 194

Variation des Beschriinkungsvektors 70, 73 - der Zielfunktionskoefftzienten 70, 73 Vektoroptimierung 279 Verbesserungsschritt 243 Verbesserungsverfahren 242 Vererbung 253,259 Verfahren von Land und Doig 197, 279 Verfahren von Wolfe 141,278 Verrechnungspreise 53, 94 Vertauschen 240 Verzweigungsbaum 204 Vollstandige Enumeration 184 Vollstandiges Zentralprogramm 95,96 Vorwiirtsrechnung 268 Vorwiirtsschritt 193

Wahrscheinlichkeiten 260 Wertfunktion 266, 269, 272, 274 Worst-case 109,237

Zeilenrang 29 Zeitkomplexitiit 237 Zentrale Ressourcen 81, 86 - Restriktion 84, 91, 95 Zentralprogramm 85, 91, 98

291

Zielfunktion 3, II, 15,31,36,72,126, 136, 153,165

Zielfunktional 265, 273 Zielfunktionskoefftzient 4, 12,20,28,37,

44,57,62,70,78,84,187 - der Basisvariablen 37, 43, 63 - der Nicht-Basisvariablen 37, 63 Zielfunktionswert 21, 48,87,93,106,108,

181,186, 188, 197, 198 Zielfunktionszeile 20, 29, 38, 66, 182,222 Zufallige Schwankungen 57 Zufallszahl 245, 260 Zulassige Basislosung 13, 16,24,36, 71, 83,

91,222 - Entscheidung I - ganzzahlige Losung 175, 181 - LOsung 15,28,42,84,93,153, 162, 168,

176,184,188,191,198,217 Zuliissiger Nachfolger 191 Zulassigkeitsbedingung 115 Zuordnung 224 Zuordnungsvariable 225, 226, 229 Zusatzliche Entscheidungsalternative, 57 - Restriktion 58, 68 - Variable 58, 65 Zustand 7, 265,266,273,274 Zustandsraum 274 Zustandsvariable 265, 269, 273 Zustandsvektor 7, 273 Zweiertausch 242 Zweig 198 Zweikampf263 Zweikampf-Verfahren 260 Zweiphasen-Methode 24, 54, 93, 142,208 Zyklenfrei 272 Zyklus 211