Lineares Programmieren

Eine bildliche Darstellung eines einfachen linearen Programms mit zwei Variablen und sechs Ungleichheiten. Der Satz realisierbarer Lösungen wird gelb dargestellt und bildet a Polygon, ein 2-dimensional Polytope. Das Optimum der linearen Kostenfunktion besteht darin, dass die rote Linie das Polygon überschneidet. Die rote Linie ist a Level eingestellt der Kostenfunktion, und der Pfeil zeigt die Richtung an, in der wir optimieren.

Eine geschlossene realisierbare Region eines Problems mit drei Variablen ist konvex Polyeder. Die Oberflächen, die einen festen Wert der Zielfunktion geben, sind Flugzeuge (nicht gezeigt). Das Lineare Programmierungsproblem besteht darin, einen Punkt auf dem Polyeder zu finden, der mit dem höchstmöglichen Wert auf der Ebene liegt.

Lineares Programmieren (LP), auch genannt lineare Optimierung, ist eine Methode, um das beste Ergebnis (z. B. maximale Gewinn oder niedrigste Kosten) in a zu erzielen mathematisches Modell deren Anforderungen werden durch dargestellt lineare Beziehungen. Die lineare Programmierung ist ein spezieller Fall der mathematischen Programmierung (auch bekannt als Mathematische Optimierung).

Lineare Programmierung ist eine Technik für die Optimierung von a linear Zielfunktion, vorbehaltlich lineare Gleichheit und lineare Ungleichheit Einschränkungen. Es ist realisierbare Region ist ein konvexes Polytop, was ein Satz ist, definiert als die Überschneidung von endlich vielen halbe Leerzeichenjedes davon wird durch eine lineare Ungleichheit definiert. Seine objektive Funktion ist a real-geschätzt affine (lineare) Funktion auf diesem Polyeder definiert. Eine lineare Programmierung Algorithmus findet einen Punkt in der Polytope wo diese Funktion den kleinsten (oder größten) Wert hat, wenn ein solcher Punkt vorhanden ist.

Lineare Programme sind Probleme, die in ausgedrückt werden können kanonische Form wie

$oder } \\ & {\ text {unter}} && a \ mathbf {x} \ leq \ mathbf {b} \\ & {\ text {und}} && \ mathbf {x} \ geq \ mathbf {0}. \ mathbf {x} \ mathbf {0}. Ende {ausgerichtet}}}$

Hier die Komponenten von x sind die Variablen zu bestimmt, c und b sind gegeben Vektoren (mit ${\ displaystyle \ mathbf {c} ^{t}}$ was angeben, dass die Koeffizienten von c werden als Einzelreihe-Matrix verwendet, um das Matrixprodukt zu bilden) und A ist eine Selbstverständlichkeit Matrix. Die Funktion, deren Wert maximiert oder minimiert werden soll ($oder$ in diesem Fall) wird als die genannt Zielfunktion. Die Ungleichheiten Ax≤b und x ≥ 0 sind die Einschränkungen, die a angeben konvexes Polytop über die die Zielfunktion optimiert werden soll. In diesem Zusammenhang sind zwei Vektoren vergleichbar Wenn sie die gleichen Dimensionen haben. Wenn jeder Eintrag in der ersten oder gleich den entsprechenden Eintrag in der zweiten ist, kann der erste Vektor weniger als der zweite Vektor ist.

Lineare Programmierung kann auf verschiedene Studienfelder angewendet werden. Es wird in der Mathematik und in geringerem Maße im Geschäft weit verbreitet. Wirtschaftund für einige technische Probleme. Branchen, die lineare Programmiermodelle verwenden, umfassen Transport, Energie, Telekommunikation und Fertigung. Es hat sich als nützlich bei der Modellierung verschiedener Arten von Problemen in als nützlich erwiesen Planung, Routing, Planung, Abtretung, und Design.

Geschichte

Leonid Kantorovich

John von Neumann

Das Problem der Lösung eines Systems linearer Ungleichheiten reicht zumindest so weit zurück Fourier, der 1827 eine Methode zum Lösen veröffentlichte,^[1] und nach dem die Methode von Fourier -Motzkin -Eliminierung benannt.

1939 wurde eine lineare Programmierformulierung eines Problems, das dem allgemeinen linearen Programmierungsproblem entspricht Sowjet Mathematiker und Ökonom Leonid Kantorovich, der auch eine Methode zur Lösung vorgeschlagen hat.^[2] Es ist eine Art, wie er sich entwickelt hat, während Zweiter Weltkrieg, um Ausgaben und Renditen zu planen, um die Kosten der Armee zu senken und Verluste zu erhöhen, die dem Feind auferlegt werden. Kantorovichs Arbeit wurde zunächst in der vernachlässigt UdSSR.^[3] Etwa zur gleichen Zeit wie Kantorovich, der niederländisch-amerikanische Ökonom T. C. Koopmans formulierte klassische wirtschaftliche Probleme als lineare Programme. Kantorovich und Koopmans teilten sich später die 1975 mit Nobelpreis in Wirtschaftswissenschaften.^[1] 1941, Frank Lauren Hitchcock formulierte auch Transportprobleme als lineare Programme und gab eine Lösung, die dem später sehr ähnlich ist Simplex -Methode.^[2] Hitchcock war 1957 gestorben und der Nobelpreis wird nicht posthum ausgezeichnet.

In den Jahren 1946–1947,, George B. Dantzig Unabhängig entwickelte allgemeine lineare Programmierformulierung für Planungsprobleme in der US -Luftwaffe.^[4] 1947 erfand Dantzig auch das Simplex -Methode Das wurde zum ersten Mal in den meisten Fällen das lineare Programmierungsproblem effizient angeht.^[4] Als Dantzig ein Treffen mit organisierte John von Neumann Um seine Simplex -Methode zu diskutieren, vermutete Neumann sofort die Theorie von Dualität Indem er erkannte, dass das Problem, in dem er gearbeitet hatte Spieltheorie war äquivalent.^[4] Dantzig lieferte am 5. Januar 1948 einen formellen Beweis in einem unveröffentlichten Bericht "Ein Satz über lineare Ungleichheiten".^[3] Dantzigs Arbeiten wurden 1951 der Öffentlichkeit zur Verfügung gestellt. In den Nachkriegsjahren wandten viele Branchen sie in ihrer täglichen Planung an.

Dantzigs ursprüngliches Beispiel war es, die beste Aufgabe von 70 Personen zu 70 Arbeitsplätzen zu finden. Die Rechenleistung, die erforderlich ist, um alle Permutationen zu testen, um die beste Zuordnung auszuwählen, ist groß. Die Anzahl der möglichen Konfigurationen übersteigt die Anzahl der Partikel in dem Beobachtbares Universum. Es dauert jedoch nur einen Moment, um die optimale Lösung zu finden, indem Sie das Problem als lineares Programm aufstellen und das anwenden Simplex -Algorithmus. Die Theorie hinter der linearen Programmierung reduziert drastisch die Anzahl der möglichen Lösungen, die überprüft werden müssen.

Es wurde zuerst gezeigt, dass das lineare Programmierungsproblem in der Polynomzeit von löslich ist Leonid Khachiyan 1979,,^[5] Aber ein größerer theoretischer und praktischer Durchbruch auf dem Feld kam 1984, als Narendra Karmarkar stellte eine neue vor Innenpunktmethode zur Lösung von Problemen linearprogrammierende Probleme.^[6]

Verwendet

Die lineare Programmierung ist aus mehreren Gründen ein weit verbreitetes Optimierungsfeld. Viele praktische Probleme in Unternehmensforschung kann als lineare Programmierungsprobleme ausgedrückt werden.^[3] Bestimmte besondere Fälle von linearer Programmierung, wie z. Netzwerkfluss Probleme und Mehrmoditätsfluss Probleme werden als wichtig genug angesehen, um viele Forschungen zu spezialisierten Algorithmen für ihre Lösung herzustellen. Eine Reihe von Algorithmen für andere Arten von Optimierungsproblemen wirkt durch Lösen von LP-Problemen als Unterprobleme. Historisch gesehen haben Ideen aus der linearen Programmierung viele der zentralen Konzepte der Optimierungstheorie inspiriert, wie z. Dualität, Zersetzung, und die Bedeutung von Konvexität und seine Verallgemeinerungen. Ebenso wurde die lineare Programmierung in der frühen Bildung von stark verwendet Mikroökonomie und es wird derzeit im Unternehmensmanagement verwendet, wie Planung, Produktion, Transport, Technologie und andere Probleme. Obwohl sich die modernen Managementprobleme ständig verändern, möchten die meisten Unternehmen gerne Gewinne maximieren und minimieren Sie die Kosten mit begrenzten Ressourcen. Google verwendet eine lineare Programmierung, um YouTube -Videos zu stabilisieren.^[7] Daher können viele Probleme als lineare Programmierprobleme charakterisiert werden.

Standardform

Standardform ist die übliche und intuitivste Form der Beschreibung eines linearen Programmierproblems. Es besteht aus den folgenden drei Teilen:

• A lineare Funktion zu maximieren

z.B. ${\ displayStyle f (x_ {1}, x_ {2}) = c_ {1} x_ {1}+c_ {2} x_ {2}}$

• Problembeschränkungen der folgenden Form

z.B.

$oder 2} & \ leq B_ {2} \\ a_ {31} x_ {1}+a_ {32} x_ {2} & \ leq b_ {3} \\\ end {matrix}}}$

• Nicht negative Variablen

z.B.

$oder$

Das Problem wird normalerweise in ausgedrückt Matrix bildenund wird dann:

$oder {x} \ leq \ mathbf {b} \ land \ mathbf {x} \ geq 0 \, \}}$

Andere Formen wie Minimierungsprobleme, Probleme mit Einschränkungen für alternative Formen sowie Probleme mit negativen Variablen kann immer in ein äquivalentes Problem in Standardform umgeschrieben werden.

Beispiel

Angenommen, ein Landwirt hat ein Stück Ackerland, sagen wir L km², mit Weizen oder Gerste oder einer Kombination aus beiden gepflanzt werden. Der Landwirt hat eine begrenzte Menge an Dünger, F Kilogramm und Pestizid, P Kilogramm. Jeder quadratische Kilometer Weizen erfordert F₁ Kilogramm Dünger und P₁ Kilogramm Pestizid, während jeder Quadratkilometer Gerste erfordert F₂ Kilogramm Dünger und P₂ Kilogramm Pestizid. Lasst uns₁ Seien Sie der Verkaufspreis von Weizen pro Quadratkilometer und s₂ Sei der Verkaufspreis von Gerste. Wenn wir das mit Weizen und Gerste gepflanzte Landgebiet bezeichnen x₁ und x₂ Anschließend kann der Gewinn maximiert werden, indem optimale Werte für auswählen x₁ und x₂. Dieses Problem kann mit dem folgenden linearen Programmierungsproblem in der Standardform ausgedrückt werden:

Maximieren: ${\ displayStyle s_ {1} \ cdot x_ {1}+s_ {2} \ cdot x_ {2}}$		(Maximieren Sie den Umsatz (der Gesamtwellverkauf von Weizen zuzüglich des gesamten Gersteumsatzes) - Umsatz ist die "objektive Funktion"))
Vorbehaltlich:	${\ displaystyle x_ {1}+x_ {2} \ leq l}$	(Grenze der Gesamtfläche)
	${\ displayStyle f_ {1} \ cdot x_ {1}+f_ {2} \ cdot x_ {2} \ leq f}$	(Begrenzung des Düngers)
	${\ displaystyle p_ {1} \ cdot x_ {1}+p_ {2} \ cdot x_ {2} \ leq p}$	(Begrenzung des Pestizids)
	${\ displayStyle x_ {1} \ geq 0, x_ {2} \ geq 0}$	(kann keine negative Fläche pflanzen).

In Matrixform wird dies:

maximieren $oder$

vorbehaltlich $oder 2} \ end {bmatrix}} \ leq {\ begin {bmatrix} l \\ f \\ p \ end {bmatrix}}, \, {\ begin {Bmatrix} x_ {1} \ X_ {2}}}}}}}}}}}}}} $ {bmatrix}} \ geq {\ begin {bmatrix} 0 \\ 0 \ end {bMatrix}}.}$

Augmented Form (Slack -Form)

Lineare Programmierprobleme können in eine umgewandelt werden Augmented Form Um die gemeinsame Form der anzuwenden Simplex -Algorithmus. Dieses Formular führt nicht negativ ein Slack Variablen Ungleichungen durch Gleichheiten in den Einschränkungen zu ersetzen. Die Probleme können dann im Folgenden geschrieben werden Blockmatrix bilden:

Maximieren ${\ displayStyle z}$:

${\ displaystyle {\ begin {bmatrix} 1 &-\ mathbf {c} ^{t} & 0 \\ 0 & \ mathbf {a} & \ mathbf {i} \ end {bmatrix} {{{batrix} Z \\ Z \\ Z \\ Z \\ Z \ \ \ mathbf {x} \\\ mathbf {s} \ end {bmatrix}} = {\ begin {bmatrix} 0 \\\ mathbf {b} \ end {bmatrix}}}}}}}}}$

$oder$

wo ${\ displaystyle \ mathbf {s}}$ sind die neu eingeführten Slack -Variablen, ${\ displaystyle \ mathbf {x}}$ sind die Entscheidungsvariablen und ${\ displayStyle z}$ Ist die Variable maximiert.

Beispiel

Das obige Beispiel wird in die folgende erweiterte Form umgewandelt:

Maximieren: ${\ displayStyle s_ {1} \ cdot x_ {1}+s_ {2} \ cdot x_ {2}}$		(Zielfunktion)
vorbehaltlich:	${\ displaystyle x_ {1}+x_ {2}+x_ {3} = l}$	(erweiterte Einschränkung)
	${\ displayStyle f_ {1} \ cdot x_ {1}+f_ {2} \ cdot x_ {2}+x_ {4} = f}$	(erweiterte Einschränkung)
	${\ displayStyle p_ {1} \ cdot x_ {1}+p_ {2} \ cdot x_ {2}+x_ {5} = p}$	(erweiterte Einschränkung)
	${\ displayStyle x_ {1}, x_ {2}, x_ {3}, x_ {4}, x_ {5} \ geq 0.}$

wo ${\ displaystyle x_ {3}, x_ {4}, x_ {5}}$ sind (nicht negative) Slack-Variablen, die in diesem Beispiel den ungenutzten Bereich, die Menge an nicht verwendeten Dünger und die Menge an nicht verwendeten Pestiziden darstellen.

In Matrixform wird dies:

Maximieren ${\ displayStyle z}$:

${\displaystyle {\begin{bmatrix}1&-S_{1}&-S_{2}&0&0&0\\0&1&1&1&0&0\\0&F_{1}&F_{2}&0&1&0\\0&P_{1}&P_{2}&0&0&1\\\ End {Bmatrix}} {\ begin {bmatrix} z ​​\\ x_ {1} \\ x_ {2} \\ x_ {3} \\ x_ {4 {4} \\ x_ {5} \ end {bmatrix} = {{{{{{{{{{{{ \ begin {bmatrix} 0 \\ l \\ f \\ p \ end {bmatrix}}, \, {\ begin {bmatrix} x_ {1} \\ x_ {2} \\ x_ {3} \\ x_ {{{{{{{{{{{ 4} \\ x_ {5} \ end {bmatrix}} \ geq 0.}$

Dualität

Jedes lineare Programmierungsproblem, das als als bezeichnet bezeichnet wird ursprünglich Problem kann in a konvertiert werden Dual Problem, was eine Obergrenze zum optimalen Wert des Urproblems liefert. In Matrixform können wir das ausdrücken ursprünglich Problem als:

Maximieren c^Tx vorbehaltlich Ax ≤ b, x ≥ 0;

mit dem entsprechenden symmetrisch Duales Problem,

Minimieren b^Ty vorbehaltlich A^Ty ≥ c, y ≥ 0.

Eine alternative ursprüngliche Formulierung ist:

Maximieren c^Tx vorbehaltlich Ax ≤ b;

mit dem entsprechenden asymmetrisch Duales Problem,

Minimieren b^Ty vorbehaltlich A^Ty = c, y ≥ 0.

Es gibt zwei Ideen für die Dualitätstheorie. Eine davon ist die Tatsache, dass (für das symmetrische Dual) das Dual eines doppelten linearen Programms das ursprüngliche ursprüngliche lineare Programm ist. Zusätzlich liefert jede praktikable Lösung für ein lineares Programm eine Grenze zum optimalen Wert der objektiven Funktion seines Dual. Das Schwache Dualität Theorem stellt fest, dass der objektive Funktionswert des Dual in jeder realisierbaren Lösung immer größer oder gleich dem objektiven Funktionswert des Urs an jeder realisierbaren Lösung ist. Das Starke Dualität Theorem stellt fest, dass, wenn das Primal eine optimale Lösung hat, x^*dann hat das dual auch eine optimale Lösung, y^*, und c^Tx^*=b^Ty^*.

Ein lineares Programm kann auch unbegrenzt oder nicht realisierbar sein. Die Dualitätstheorie sagt uns, dass das Dual durch den schwachen Dualitätstheorem, wenn das Primal unbegrenzt ist, das Dual nicht realisierbar ist. Ebenso muss das Primal, wenn das Dual unbegrenzt ist, nicht zu tun. Es ist jedoch möglich, dass sowohl das Dual als auch das Primal nicht realisierbar sind. Sehen Dual lineares Programm Einzelheiten und einige weitere Beispiele.

Variationen

Deckung/Verpacken von Dualität

A LP ist ein lineares Programm der Form:

Minimieren: b^Ty,

vorbehaltlich: A^Ty ≥ c, y ≥ 0,

so dass die Matrix A und die Vektoren b und c sind nicht negativ.

Das Dual einer bedeckenden LP ist a Packing LP, ein lineares Programm der Form:

Maximieren: c^Tx,

vorbehaltlich: Ax ≤ b, x ≥ 0,

so dass die Matrix A und die Vektoren b und c sind nicht negativ.

Beispiele

Das Abdecken und Verpacken von LPs entstehen häufig als Lineare Programmierrelaxation eines kombinatorischen Problems und sind wichtig für die Studie von wichtig Näherungsalgorithmen.^[8] Zum Beispiel die LP -Relaxationen der Packungsproblem einstellen, das Unabhängiges Problem, und die passendes Problem packen LPS. Die LP -Relaxationen der Stellen Sie das Cover -Problem fest, das Scheitelpunktabdeckungsproblem, und die Dominierender Satzproblem decken auch LPS ab.

Finden a Bruchfärbung von a Graph ist ein weiteres Beispiel für eine LP. In diesem Fall gibt es für jeden Scheitelpunkt des Diagramms eine Einschränkung und für jeden eine Variable unabhängiger Satz der Grafik.

Komplementäres Lockerheit

Es ist möglich, eine optimale Lösung für das Dual zu erhalten, wenn nur eine optimale Lösung für das Primal unter Verwendung des komplementären Slackness -Theorems bekannt ist. Der Satz gibt an:

Nehme an, dass x= (x₁Anwesendx₂, ...,x_n) ist ursprünglich machbar und das y= (y₁Anwesendy₂, ...,y_m) ist doppelt machbar. Lassen (w₁Anwesendw₂, ...,w_m) Bezeichnen Sie die entsprechenden ursprünglichen Slack -Variablen und lassen Sie (lassenz₁Anwesendz₂, ...,z_n) Bezeichnen Sie die entsprechenden doppelten Slack -Variablen. Dann x und y sind optimal für ihre jeweiligen Probleme, wenn und nur wenn

• x_j z_j= 0, für j= 1, 2, ...,n, und
• w_i y_i= 0, für i= 1, 2, ...,m.

Also wenn die i-Die Slack -Variable des Urs ist nicht Null, dann die dann die i-Die Variable der Dual entspricht Null. Ebenso, wenn die j-Die Slack -Variable des Dual ist nicht Null, dann die j-Die Variable des Urs ist gleich Null.

Diese notwendige Bedingung für die Optimalität vermittelt ein ziemlich einfaches wirtschaftliches Prinzip. In Standardform (bei Maximierung), wenn eine eingeschränkte ursprüngliche Ressource (d. H. Es gibt "Reste"), müssen zusätzliche Mengen dieser Ressource keinen Wert haben. Wenn der doppelte (Schatten-) Preis-Nicht-Negativitäts-Einschränkungspflicht, d. H. Der Preis ist, ist nicht Null, muss es knapp (keine "Reste").

Theorie

Existenz optimaler Lösungen

Geometrisch definieren die linearen Einschränkungen die realisierbare Region, die ein konvex Polyeder. EIN lineare Funktion ist ein Konvexe Funktion, was impliziert, dass jeder Lokales Minimum ist ein globales Minimum; In ähnlicher Weise ist eine lineare Funktion a konkave Funktion, was impliziert, dass jeder Lokales Maximum ist ein Global Maximum.

Aus zwei Gründen muss eine optimale Lösung nicht vorhanden sein. Wenn die Einschränkungen inkonsistent sind, gibt es zuerst keine machbare Lösung: Zum Beispiel die Einschränkungen x≥ 2 und x≤ 1 kann nicht gemeinsam erfüllt werden; In diesem Fall sagen wir, dass die LP ist undurchführbar. Zweitens, wenn die Polytope ist in Richtung des Gradienten der objektiven Funktion unbegrenzt (wo der Gradient der objektiven Funktion der Vektor der Koeffizienten der objektiven Funktion ist), dann wird kein optimaler Wert erreicht, da es immer möglich ist, besser als jeder endliche Wert zu tun der Zielfunktion.

Optimale Eckpunkte (und Strahlen) von Polyedera

Andernfalls, wenn eine praktikable Lösung vorhanden ist und die Einschränkung begrenzt ist, wird der optimale Wert immer an der Grenze der Einschränkung erreicht, von der Maximales Prinzip zum konvexe Funktionen (Alternativ von der Minimum Prinzip für konkave Funktionen) Da lineare Funktionen sowohl konvex als auch konkav sind. Einige Probleme haben jedoch unterschiedliche optimale Lösungen. Zum Beispiel ist das Problem, eine praktikable Lösung für ein System linearer Ungleichheiten zu finden, ein lineares Programmierungsproblem, bei dem die objektive Funktion die Nullfunktion ist (dh die konstante Funktion, die den Wert Null überall nimmt). Für dieses Machbarkeitsproblem mit der Nullfunktion für seine objektive Funktion ist bei zwei unterschiedlichen Lösungen jede konvexe Kombination der Lösungen eine Lösung.

Die Scheitelpunkte des Polytops werden ebenfalls genannt grundlegende machbare Lösungen. Der Grund für diese Namenswahl ist wie folgt. Lassen d Bezeichnen Sie die Anzahl der Variablen. Dann impliziert der grundlegende Theorem linearer Ungleichheiten (für praktikable Probleme), die für jeden Scheitelpunkt x^* Von der LP -realisierbaren Region gibt es eine Reihe von einer Reihe von d (oder weniger) Ungleichheitsbeschränkungen der LP so, dass wir diese behandeln, wenn wir diese behandeln d Einschränkungen als Gleichheiten, die einzigartige Lösung ist x^*. Dadurch können wir diese Scheitelpunkte untersuchen, indem wir bestimmte Teilmengen des Satzes aller Einschränkungen (ein diskreter Satz) und nicht das Kontinuum von LP -Lösungen betrachten. Dieses Prinzip zugrunde liegt Simplex -Algorithmus Zur Lösung linearer Programme.

Algorithmen

In einem linearen Programmierungsproblem erzeugt eine Reihe linearer Einschränkungen a konvex realisierbare Region möglicher Werte für diese Variablen. Im zweivariablen Fall hat diese Region in Form eines Konvexen Einfacher Polygon.

Basis -Austauschalgorithmen

Simplexalgorithmus von Dantzig

Das Simplex -Algorithmus, entwickelt von George Dantzig 1947 löst LP -Probleme, indem sie eine praktikable Lösung an einem Scheitelpunkt des Polytope und dann auf einem Pfad an den Kanten des Polytops zu Eckpunkten mit nicht abfälligen Werten der objektiven Funktion, bis ein Optimum mit Sicherheit erreicht ist. In vielen praktischen Problemen ","Stalling"tritt auf: Viele Pivots werden ohne Zunahme der Zielfunktion hergestellt.^[9][10] Bei seltenen praktischen Problemen können die üblichen Versionen des Simplex -Algorithmus tatsächlich "Zyklus".^[10] Um Zyklen zu vermeiden, entwickelten Forscher neue Drehregeln.^{[11][12][9][10][13][14]}

In der Praxis der Simplex Algorithmus ist ziemlich effizient und kann garantiert das globale Optimum finden, wenn bestimmte Vorsichtsmaßnahmen gegen Radfahren sind vergeben. Es wurde nachgewiesen, dass der Simplex -Algorithmus "zufällige" Probleme effizient löst, d. H. In einer kubischen Anzahl von Schritten,^[15] Dies ähnelt seinem Verhalten bei praktischen Problemen.^[9][16]

Der Simplex-Algorithmus hat jedoch ein schlechtes Verhalten von Worst-Case: Klee und Minty haben eine Familie linearer Programmierprobleme konstruiert, für die die Simplex-Methode eine Reihe von Schritten in der Problemgröße exponentiell unternimmt.^[9][12][13] Tatsächlich war es für einige Zeit nicht bekannt Polynomzeit, d.h. von Komplexitätsklasse p.

Kreuzungsalgorithmus

Wie der Simplex -Algorithmus von Dantzig die Kreuzungsalgorithmus ist ein Basisaustauschalgorithmus, der sich zwischen Basen drehen. Der Kreuzungsalgorithmus muss jedoch nicht die Machbarkeit aufrechterhalten, kann jedoch eher von einer realisierbaren Basis bis hin zu einer nicht durchführbaren Basis schwenken. Der Kreuzungsalgorithmus hat nicht Polynomzeitkomplexität Für die lineare Programmierung. Beide Algorithmen besuchen alle 2^D Ecken eines (gestört) Würfel in DimensionD, das Klee -Minty Cube, in dem schlimmsten Fall.^[14][17]

Innenausstattung

Im Gegensatz zum Simplex-Algorithmus, der eine optimale Lösung findet, indem die Kanten zwischen Scheitelpunkten auf einem polyedrischen Satz durchquert werden, bewegen sich die Innenpunktmethoden durch das Innere des realisierbaren Bereichs.

Ellipsoid -Algorithmus nach Khachiyan

Das ist das erste schlimmsten Fall Polynomzeit Algorithmus wurde jemals für die lineare Programmierung gefunden. Ein Problem zu lösen, das hat n Variablen und können in codiert werden L Eingabebits, dieser Algorithmus läuft in ${\ displayStyle o (n^{6} l)}$ Zeit.^[5] Leonid Khachiyan löste dieses langjährige Komplexitätsproblem 1979 mit der Einführung der Ellipsoid -Methode. Die Konvergenzanalyse hat (reale) Vorgänger, insbesondere die iterative Methoden entwickelt von Naum Z. Shor und die Näherungsalgorithmen Von Arkadi Nemirovski und D. Yudin.

Projektivalgorithmus von Karmarkar

Der Algorithmus von Khachiyan war für die Festlegung der Polynom-Zeit-Solvabilität linearer Programme von Bedeutung. Der Algorithmus war kein rechnerischer Durchbruch, da die Simplex-Methode für alle als speziell konstruierten Familien linearer Programme effizienter ist.

Der Algorithmus von Khachiyan inspirierte jedoch neue Forschungslinien in der linearen Programmierung. 1984,, N. Karmarkar vorgeschlagen a Projektivmethode Für die lineare Programmierung. Karmarkars Algorithmus^[6] verbessert bei Khachiyan's^[5] schlimmster Fall Polynomgebundene (geben ${\ displayStyle o (n^{3.5} l)}$). Karmarkar behauptete, sein Algorithmus sei in der praktischen LP viel schneller gewesen als in der Simplex-Methode, eine Behauptung, die großes Interesse an Innenpunktmethoden darstellte.^[18] Seit Karmarkars Entdeckung wurden viele Innenausstattungsmethoden vorgeschlagen und analysiert.

Vaidyas 87 Algorithmus

1987 schlug Vaidya einen Algorithmus vor ${\ displayStyle o (n^{3})}$ Zeit.^[19]

Vaidyas 89 Algorithmus

1989 entwickelte Vaidya einen Algorithmus, der in der Lage ist ${\ displayStyle o (n^{2.5})}$ Zeit.^[20] Formell spricht der Algorithmus ${\ displayStyle o ((n+d)^{1.5} nl)}$ arithmetische Operationen im schlimmsten Fall, wo ${\ displayStyle d}$ ist die Anzahl der Einschränkungen, ${\ displayStyle n}$ ist die Anzahl der Variablen und ${\ displayStyle l}$ ist die Anzahl der Bits.

Eingabe -Sparsity -Zeitalgorithmen

Im Jahr 2015 zeigten Lee und Sidford, dass es gelöst werden kann ${\ displaystyle {\ tilde {o}} ((nnz (a)+d^{2}) {\ sqrt {d}} l)}$ Zeit,^[21] wo ${\ displayStyle nnz (a)}$ repräsentiert die Anzahl der Elemente ungleich Null, und es bleibt übrig ${\ displayStyle o (n^{2.5} l)}$ im schlimmsten Fall.

Aktueller Matrix -Multiplikationszeitalgorithmus

Im Jahr 2019 verbesserten Cohen, Lee und Song die Laufzeit $oder$ Zeit, ${\ displayStyle \ Omega}$ ist der Exponent von Matrix-Multiplikation und ${\ displayStyle \ alpha}$ ist der doppelte Exponent von Matrix-Multiplikation.^[22] ${\ displayStyle \ alpha}$ wird (ungefähr) als die größte Zahl definiert, so dass man sich multiplizieren kann ${\ displayStyle n \ Times n}$ Matrix durch a ${\ displayStyle n \ Times n^{\ alpha}}$ Matrix in ${\ displayStyle o (n^{2})}$ Zeit. In einem Follow -up -Werk von Lee, Song und Zhang reproduzieren sie das gleiche Ergebnis über eine andere Methode.^[23] Diese beiden Algorithmen bleiben bestehen ${\ displayStyle {\ tilde {o}} (n^{2+1/6} l)}$ Wenn ${\ displayStyle \ Omega = 2}$ und ${\ displayStyle \ alpha = 1}$. Das Ergebnis aufgrund von Jiang, Song, Weinstein und Zhang verbesserte sich ${\ displayStyle {\ tilde {o}} (n^{2+1/6} l)}$ zu ${\ displayStyle {\ tilde {o}} (n^{2+1/18} l)}$.^[24]

Vergleich von Innenpunktmethoden und Simplexalgorithmen

Die aktuelle Meinung ist, dass die Effizienz guter Implementierungen von simplexbasierten Methoden und Innenpunktmethoden für Routineanwendungen der linearen Programmierung ähnlich sind. Für bestimmte Arten von LP-Problemen kann es jedoch sein, dass eine Art von Löser besser ist als ein anderer (manchmal viel besser) und dass die Struktur der von Innenpunktmethoden erzeugten Lösungen im Vergleich zu simplexbasierten Methoden mit der Unterstützung erheblich unterschiedlich sind Die Menge aktiver Variablen sind typischerweise für letztere kleiner.^[25]

Offene Probleme und jüngste Arbeiten

In der Theorie der linearen Programmierung gibt es mehrere offene Probleme, deren Lösung grundlegende Durchbrüche in der Mathematik und möglicherweise wichtige Fortschritte bei unserer Fähigkeit zur Lösung von linearen Programmen aus großem Maßstab darstellen würde.

• Gibt LP a zu a? stark polynomisch-Time -Algorithmus?
• Gibt LP einen stark polynomialen Zeitalgorithmus zu, um eine streng komplementäre Lösung zu finden?
• Gibt LP einen Polynom-Zeit-Algorithmus im Realzahl-Berechnungsmodell (Einheitskosten) zu?

Diese eng verwandte Probleme wurden von zitiert von Stephen Smale wie unter den 18 größte ungelöste Probleme des 21. Jahrhunderts. In Smeles Worten ist die dritte Version des Problems "das Hauptproblem der linearen Programmierungstheorie". Während Algorithmen existieren, um eine lineare Programmierung in schwach polynomialer Zeit zu lösen, wie die Ellipsoid -Methoden und InnenausstattungstechnikenEs wurden noch keine Algorithmen gefunden, die eine starke polynomiale Leistung in der Anzahl der Einschränkungen und die Anzahl der Variablen ermöglichen. Die Entwicklung solcher Algorithmen wäre von großem theoretischen Interesse und ermöglicht möglicherweise auch praktische Gewinne bei der Lösung großer LPS.

Obwohl die Hirsch -Vermutung Wurde kürzlich wegen höherer Dimensionen widerlegt, lässt es immer noch die folgenden Fragen offen.

• Gibt es Pivot-Regeln, die zu Polynom-Zeit-Simplex-Varianten führen?
• Haben alle Polytopaldiagramme einen polynomisch begrenzten Durchmesser?

Diese Fragen beziehen sich auf die Leistungsanalyse und Entwicklung von simplexähnlichen Methoden. Die immense Effizienz des Simplex-Algorithmus in der Praxis trotz seiner theoretischen Leistung exponentieller Zeit deutet darauf hin, dass es möglicherweise Variationen von Simplex in Polynom oder sogar stark polynomialer Zeit gibt. Es wäre von großer praktischer und theoretischer Bedeutung zu wissen, ob solche Varianten vorhanden sind, insbesondere als Ansatz zur Entscheidung, ob LP in stark polynomialer Zeit gelöst werden kann.

Der Simplex-Algorithmus und seine Varianten fallen in die Familie der randverfolgenden Algorithmen, die so genannt werden, weil sie lineare Programmierprobleme lösen, indem sie sich entlang der Kanten eines Polytops vom Scheitelpunkt zu Scheitelpunkten wechseln. Dies bedeutet, dass ihre theoretische Leistung durch die maximale Anzahl von Kanten zwischen zwei beliebigen Scheitelpunkten am LP -Polytop begrenzt ist. Infolgedessen sind wir daran interessiert, das Maximum zu kennen Grafik-theoretischer Durchmesser von Polytopal Grafiken. Es wurde nachgewiesen, dass alle Polytope einen Subtopentialdurchmesser haben. Die jüngste Entsorgung der Hirsch -Vermutung ist der erste Schritt, um zu beweisen, ob ein Polytop einen überpolynomialen Durchmesser hat. Wenn solche Polytope vorhanden sind, kann in der Polynomzeit keine Variante der Kantenverfolgung ausgeführt werden. Fragen zum Polytopendurchmesser sind von unabhängigem mathematischen Interesse.

Simplex Pivot -Methoden bewahren die ursprüngliche (oder doppelte) Machbarkeit. Auf der anderen Seite bewahren Kriss-Cross-Pivot-Methoden nicht (ursprünglich oder doppelte) Machbarkeit-sie können ursprüngliche, machbare, doppelte oder ursprüngliche und duale uninteressante Basen in irgendeiner Reihenfolge besuchen. Seit den 1970er Jahren wurden Pivot -Methoden dieses Typs untersucht. Im Wesentlichen versuchen diese Methoden, den kürzesten Drehweg auf dem Arrangement -Polytop unter dem linearen Programmierproblem zu finden. Im Gegensatz zu Polytopalgraphen sind bekannt, dass Diagramme der Arrangement-Polytope einen kleinen Durchmesser aufweisen, der die Möglichkeit eines stark polynomialen Zeitalgorithmus mit kreuz und kreuzen Pivot-Algorithmus ermöglicht, ohne Fragen zum Durchmesser allgemeiner Polytope zu lösen.^[14]

Ganzzahl Unbekannte

Wenn alle unbekannten Variablen für Ganzzahlen erforderlich sind, wird das Problem als ein bezeichnet Ganzzahlprogrammierung (Ip) oder Ganzzahl lineare Programmierung (ILP) Problem. Im Gegensatz zur linearen Programmierung, die im schlimmsten Fall effizient gelöst werden kann, sind ganzzahlige Programmierprobleme in vielen praktischen Situationen (solche mit begrenzten Variablen) Np-harte. 0–1 Ganzzahlprogrammierung oder Binär -Ganzzahl -Programmierung (BIP) ist der Sonderfall der Ganzzahlprogrammierung, bei dem Variablen 0 oder 1 (und nicht willkürliche Ganzzahlen) betragen müssen. Dieses Problem wird auch als NP-HART eingestuft, und tatsächlich war die Entscheidungsversion eine von Karps 21 NP-Complete-Probleme.

Wenn nur einige der unbekannten Variablen für Ganzzahlen erforderlich sind, wird das Problem als a genannt gemischte Ganzzahl (linear) Programmierung (MIP oder MILP) Problem. Diese sind im Allgemeinen auch NP-HART, da sie noch allgemeiner sind als ILP-Programme.

Es gibt jedoch einige wichtige Unterklassen von IP- und MIP -Problemen, die effizient lösbar sind, insbesondere Probleme, bei denen die Einschränkungsmatrix ist Völlig unimodular und die rechten Seiten der Einschränkungen sind Ganzzahlen oder-allgemeiner-wo das System das hat Total Dual Integrality (TDI) Eigentum.

Erweiterte Algorithmen zur Lösung von Linearprogrammen für ganzzahlige Programme umfassen:

• Schneidemethode
• Zweig und gebunden
• Zweig und Schnitt
• Zweig und Preis
• Wenn das Problem eine zusätzliche Struktur aufweist, kann es möglich sein, sich zu bewerben Verzögerte Spaltengenerierung.

Solche INTEGER-Programmieralgorithmen werden durch diskutiert Padberg und in Beasley.

Integrale lineare Programme

Ein lineares Programm in realen Variablen soll sein Integral- Wenn es mindestens eine optimale Lösung hat, die integral ist, d. H. Nur aus ganzzahligen Werten. Ebenso ein Polyeder ${\ displayStyle p = \ {x \ mid ax \ geq 0 \}}$ wird gesagt, dass Integral- Wenn für alle begrenzten machbaren Zielfunktionen c, das lineare Programm ${\ displayStyle \ {\ max Cx \ Mid X \ in p \}}$ hat ein Optimum ${\ displayStyle x^{*}}$ mit Ganzzahlkoordinaten. Wie Edmonds und Giles im Jahr 1977 beobachtet, kann man gleich sagen, dass das Polyeder ${\ displayStyle p}$ ist integral, wenn für jede begrenzte machbare integrale Zielfunktion c, das optimale Wert des linearen Programms ${\ displayStyle \ {\ max Cx \ Mid X \ in p \}}$ ist eine Ganzzahl.

Integrale lineare Programme sind im polyedrischen Aspekt von zentraler Bedeutung Kombinatorische Optimierung da sie eine alternative Charakterisierung eines Problems bieten. Insbesondere für jedes Problem ist der konvexe Rumpf der Lösungen ein integrales Polyeder; Wenn dieses Polyeder eine schöne/kompakte Beschreibung hat, können wir die optimale realisierbare Lösung unter einem linearen Ziel effizient finden. Umgekehrt, wenn wir das beweisen können Lineare Programmierrelaxation ist integral, dann ist es die gewünschte Beschreibung des konvexen Rumpfes von realisierbaren (integralen) Lösungen.

Die Terminologie ist in der gesamten Literatur nicht konsistent, daher sollte man darauf achten, die folgenden zwei Konzepte zu unterscheiden.

• in einem (n Ganzzahl lineares Programm, Im vorherigen Abschnitt beschrieben, sind Variablen zwangsweise beschränkt, Ganzzahlen zu sein, und dieses Problem ist im Allgemeinen NP-Hard.
• in einem (n integrales lineares Programm, In diesem Abschnitt beschrieben sind Variablen nicht als Ganzzahlen beschränkt, sondern hat irgendwie bewiesen, dass das kontinuierliche Problem immer einen integralen optimalen Wert hat (vorausgesetzt c ist integral) und dieser optimale Wert kann effizient gefunden werden, da alle linearen Programme in Polynomgröße in der Polynomzeit gelöst werden können.

Eine häufige Möglichkeit zu beweisen, dass ein Polyeder integral ist, besteht darin, zu zeigen, dass es ist Völlig unimodular. Es gibt andere allgemeine Methoden, einschließlich der Ganzzahl -Zersetzungseigenschaft und Total Dual Integrality. Andere spezifische bekannte integrale LPs umfassen das passende Polytop, Gitterpolyeder, submodular Flow Polyeder und der Schnittpunkt von zwei verallgemeinerten Polymatroiden/g-Polymatroiden -z. Siehe Schrijver 2003.

Löser und Skriptsprachen (Programmier-) Sprachen

Permissive Lizenzen:

Copyleft (gegenseitig) Lizenzen:

Minto (Gemischter Ganzzahl -Optimierer, und Ganzzahlprogrammierung Solver, der Branch und Bound -Algorithmus verwendet) hat öffentlich verfügbaren Quellcode^[26] ist aber nicht Open Source.

Proprietär Lizenzen:

Siehe auch

Anmerkungen

Verweise

Weitere Lektüre

Externe Links

• Anleitung zur Formulierung von LP -Problemen
• Mathematisches Programmierglossar
• Die linearen Programmierfaq
• Benchmarks für Optimierungssoftware