Geradlinige Programmierung (LP oder geradlinige Optimierung) ist eine mathematische Methode, für eine Weise zu bestimmen, das beste Ergebnis (wie maximaler Gewinn oder niedrigste Kosten) in einem gegebenen mathematischen Modell für eine Liste von als geradlinige Beziehungen vertretenen Voraussetzungen zu erreichen. Geradlinige Programmierung ist ein spezifischer Fall der mathematischen Programmierung (mathematische Optimierung).

Mehr formell ist geradlinige Programmierung eine Technik für die Optimierung einer geradlinigen objektiven Funktion, Themas der geradlinigen Gleichheit und den geradlinigen Ungleichheitseinschränkungen. Sein ausführbares Gebiet ist ein konvexes Polyeder, das ein Satz ist, der als die Kreuzung von begrenzt vielen Hälften von Räumen definiert ist, von denen jeder durch eine geradlinige Ungleichheit definiert wird. Seine objektive Funktion ist eine reellwertige auf diesem Polyeder definierte Affine-Funktion. Ein geradliniger Programmieralgorithmus findet einen Punkt im Polyeder, wo diese Funktion das kleinste (oder am größten) Wert hat, wenn solcher Punkt besteht.

Geradlinige Programme sind Probleme, die in der kanonischen Form ausgedrückt werden können:

:

& \text {maximieren} && \mathbf {c} ^\\mathrm {T} \mathbf {x }\\\

& \text {unterwerfen} && ein \mathbf {x} \leq \mathbf {b} \\

& \text {und} && \mathbf {x} \ge \mathbf {0 }\

\end {richten} </Mathematik> {aus}

wo x den Vektoren von Variablen vertritt (um bestimmt zu werden), c und b Vektoren (bekannter) Koeffizienten sind und A eine (bekannte) Matrix von Koeffizienten ist. Der Ausdruck, der zu maximieren oder zu minimieren ist, wird die objektive Funktion (cx in diesem Fall) genannt. Die Ungleichheitsaxt  b ist die Einschränkungen, die einen konvexen polytope angeben, über den die objektive Funktion optimiert werden soll. In diesem Zusammenhang sind zwei Vektoren vergleichbar, wenn sie dieselben Dimensionen haben. Wenn jeder Zugang im ersten weniger - als oder gleich ist - zum entsprechenden Zugang im zweiten dann können wir sagen, dass der erste Vektor weniger - als oder - dem zweiten Vektoren gleich ist.

Geradlinige Programmierung kann auf verschiedene Studienfächer angewandt werden. Es wird im Geschäft und der Volkswirtschaft verwendet, aber kann auch für einige Technikprobleme verwertet werden. Industrien, die geradlinige Programmiermodelle verwenden, schließen Transport, Energie, Fernmeldewesen und Herstellung ein. Es hat sich nützlich im Modellieren verschiedener Typen von Problemen in Planung, Routenplanung, Terminplanung, Anweisung und Design erwiesen.

Geschichte

Das Problem, ein System der geradlinigen Ungleichheit zu lösen, geht mindestens zurück, so weit Fourier, nach dem die Methode der Beseitigung von Fourier-Motzkin genannt wird. Die frühste geradlinige Programmierung wurde zuerst von Leonid Kantorovich 1939 entwickelt. Leonid Kantorovich hat die frühsten geradlinigen Programmierprobleme 1939 für den Gebrauch während des Zweiten Weltkriegs verursacht, um Ausgaben und Umsatz zu planen, um Kosten zur Armee und Zunahme-Verluste gegen den Feind zu reduzieren. Die Methode wurde heimlich bis 1947 behalten, als George B. Dantzig die Simplexmethode veröffentlicht hat und John von Neumann die Theorie der Dualität als eine geradlinige Optimierungslösung entwickelt hat, und es im Feld der Spieltheorie angewandt hat. Nachkriegs-haben viele Industrien seinen Gebrauch in ihrer täglichen Planung gefunden.

Wie man

zuerst zeigte, war das geradlinig programmierende Problem in der polynomischen Zeit durch Leonid Khachiyan 1979 lösbar, aber ein größerer theoretischer und praktischer Durchbruch im Feld ist 1984 gekommen, als Narendra Karmarkar eine neue Innenpunkt-Methode eingeführt hat, um geradlinig programmierende Probleme zu beheben.

Das ursprüngliche Beispiel von Dantzig sollte die beste Anweisung von 70 Menschen zu 70 Jobs finden. Die Rechenmacht, die erforderlich ist, alle Versetzungen zu prüfen, um die beste Anweisung auszuwählen, ist riesengroß; die Zahl von möglichen Konfigurationen überschreitet die Zahl von Partikeln im Weltall. Jedoch braucht man nur einen Moment, um die optimale Lösung durch das Aufwerfen des Problems als ein geradliniges Programm und die Verwendung des Simplexalgorithmus zu finden. Die Theorie hinter der geradlinigen Programmierung vermindert drastisch die Anzahl von möglichen optimalen Lösungen, die überprüft werden müssen.

Gebrauch

Geradlinige Programmierung ist ein beträchtliches Feld der Optimierung aus mehreren Gründen. Viele praktische Probleme in der Operationsforschung können als geradlinige Programmierprobleme ausgedrückt werden. Bestimmte spezielle Fälle der geradlinigen Programmierung, wie Netzfluss-Probleme und Mehrwarenfluss-Probleme werden wichtig genug in Betracht gezogen, um viel Forschung über Spezialalgorithmen für ihre Lösung erzeugt zu haben. Mehrere Algorithmen für andere Typen von Optimierungsproblemen arbeiten durch das Beheben von LP-Problemen als Teilprobleme. Historisch haben Ideen von der geradlinigen Programmierung viele der Hauptkonzepte der Optimierungstheorie, wie Dualität, Zergliederung und die Wichtigkeit von der Konvexität und seinen Generalisationen begeistert. Ebenfalls wird geradlinige Programmierung in der Mikrovolkswirtschaft und dem Firmenmanagement, wie Planung, Produktion, Transport, Technologie und andere Probleme schwer verwendet. Obwohl die modernen Verwaltungsprobleme unbeständig sind, würden die meisten Gesellschaften gern Gewinne maximieren oder Kosten mit beschränkten Mitteln minimieren. Deshalb können viele Probleme als geradlinige Programmierprobleme charakterisiert werden.

Standardform

Standardform ist die übliche und intuitivste Form, ein geradliniges Programmierproblem zu beschreiben. Es besteht aus den folgenden vier Teilen:

• Eine geradlinige Funktion, maximiert zu werden

: z.B

• Problem-Einschränkungen der folgenden Form

: z.B.

::

a_ {11} x_1 + a_ {12} x_2 &\\leq b_1 \\

a_ {21} x_1 + a_ {22} x_2 &\\leq b_2 \\

a_ {31} x_1 + a_ {32} x_2 &\\leq b_3 \\

\end {Matrix} </Mathematik>

• Nichtnegative Variablen

: z.B.::

x_1 \geq 0 \\

x_2 \geq 0

\end {Matrix} </Mathematik>

• Nichtnegative Konstanten der rechten Seite

::

Das Problem wird gewöhnlich in der Matrixform ausgedrückt, und wird dann:

:

Andere Formen, wie Minimierungsprobleme, Probleme mit Einschränkungen auf alternative Formen, sowie Probleme, die negative Variablen einschließen, können immer in ein gleichwertiges Problem in der Standardform umgeschrieben werden.

Beispiel

Nehmen Sie an, dass ein Bauer ein Stück des Ackerlandes hat, sagen Sie L km, um entweder mit Weizen oder mit Gerste oder einer Kombination der zwei gepflanzt zu werden. Der Bauer hat einen beschränkten Betrag von Dünger, F Kilogramme und Insektizid, P Kilogramme. Jeder Quadratkilometer Weizen verlangt F Kilogramme Dünger und P Kilogramme Insektizid, während jeder Quadratkilometer der Gerste F Kilogramme Dünger und P Kilogramme Insektizid verlangt. Lassen Sie S der Abgabepreis von Weizen pro Quadratkilometer und S sein, der Preis der Gerste sein. Wenn wir das Gebiet des Landes anzeigen, das mit Weizen und Gerste durch x und x beziehungsweise gepflanzt ist, dann profitieren, kann durch die Auswahl optimaler Werte für x und x maximiert werden. Dieses Problem kann mit dem folgenden geradlinigen Programmierproblem in der Standardform ausgedrückt werden:

Der in der Matrixform wird:

: maximieren Sie

: unterwerfen Sie

Vermehrte Form (lockern Form)

Geradlinige Programmierprobleme müssen in die vermehrte Form umgewandelt werden, bevor sie durch den Simplexalgorithmus gelöst werden. Diese Form führt nichtnegative lockere Variablen ein, um Ungleichheit durch Gleichheiten in den Einschränkungen zu ersetzen. Das Problem kann dann in der folgenden Block-Matrixform geschrieben werden:

: Maximieren Sie Z:

:

\begin {bmatrix }\

1 &-\mathbf {c} ^T & 0 \\

0 & \mathbf & \mathbf {ich }\

\end {bmatrix }\

\begin {bmatrix }\

Z \\\mathbf {x} \\\mathbf {x} _s

\end {bmatrix} =

\begin {bmatrix }\

0 \\\mathbf {b }\

\end {bmatrix }\</Mathematik>:

wo x die kürzlich eingeführten lockeren Variablen sind, und Z die zu maximierende Variable ist.

Beispiel

Das Beispiel wird oben in die folgende vermehrte Form umgewandelt:

wo x, x, x (nichtnegative) lockere Variablen sind, in diesem Beispiel das unbenutzte Gebiet, der Betrag von unbenutztem Dünger und der Betrag von unbenutztem Insektizid vertretend.

In der Matrixform wird das:

: Maximieren Sie Z:: \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 \\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} \ge 0.

</Mathematik>

Dualität

Jedes geradlinige Programmierproblem, gekennzeichnet als ein ursprüngliches Problem, kann in ein Doppelproblem umgewandelt werden, das einen zum optimalen Wert des ursprünglichen Problems gebundenen oberen zur Verfügung stellt. In der Matrixform können wir das ursprüngliche Problem als ausdrücken:

: Maximieren Sie Cx-Thema der Axt &le; b, x &ge; 0;

:: mit dem entsprechenden symmetrischen Doppelproblem,

: Minimieren Sie durch das Thema Ja &ge; c, y &ge; 0.

Eine alternative ursprüngliche Formulierung ist:

: Maximieren Sie Cx-Thema der Axt &le; b;

:: mit dem entsprechenden asymmetrischen Doppelproblem,

: Minimieren Sie durch das Thema Ja = c, y &ge; 0.

Es gibt zwei für die Dualitätstheorie grundsätzliche Ideen. Man ist die Tatsache, dass (für den symmetrischen Doppel-) das Doppel-von einem geradlinigen Doppelprogramm das ursprüngliche ursprüngliche geradlinige Programm ist. Zusätzlich gibt jede mögliche Lösung für ein geradliniges Programm einem gebundenen den optimalen Wert der objektiven Funktion seines Doppel-. Der schwache Dualitätslehrsatz stellt fest, dass der objektive Funktionswert des Doppel-an jeder möglichen Lösung immer größer oder gleich dem objektiven Funktionswert des ursprünglichen an jeder möglichen Lösung ist. Der starke Dualitätslehrsatz stellt dass fest, wenn das ursprüngliche eine optimale Lösung, x hat, dann hat der Doppel-auch eine optimale Lösung, y, solch dass cx=by.

Ein geradliniges Programm kann auch unbegrenzt oder unausführbar sein. Dualitätstheorie sagt uns, dass, wenn das ursprüngliche dann unbegrenzt ist, der Doppel-durch den schwachen Dualitätslehrsatz unausführbar ist. Ebenfalls, wenn der Doppel-unbegrenzt ist, dann muss das ursprüngliche unausführbar sein. Jedoch ist es sowohl für den Doppel-als auch für das ursprüngliche möglich, unausführbar zu sein (Siehe auch das Lemma von Farkas).

Beispiel

Besuchen Sie das obengenannte Beispiel des Bauers wieder, der Weizen und Gerste mit der Satz-Bestimmung von einem L-Land, F Dünger und P Insektizid anbauen kann. Nehmen Sie an, jetzt wo Einheitspreise für jedes dieser Mittel der Produktion (Eingänge) von einem Planungsausschuss festgelegt werden. Der Planungsvorstandsjob ist, die Gesamtkosten zu minimieren, die Satz-Beträge von Eingängen zu beschaffen, während er den Bauer mit einem Fußboden auf dem Einheitspreis von jedem seiner Getreide (Produktionen), S für Weizen und S für die Gerste versorgt. Das entspricht dem folgenden geradlinigen Programmierproblem:

Der in der Matrixform wird:

: Minimieren Sie:

: Thema:

Das ursprüngliche Problem befasst sich mit physischen Mengen. Mit allen Eingängen, die in beschränkten Mengen und dem Annehmen der Einheitspreise aller Produktionen verfügbar sind, ist bekannt, welche Mengen von Produktionen zu erzeugen, um Gesamteinnahmen zu maximieren? Das Doppelproblem befasst sich mit Wirtschaftswerten. Mit Fußboden-Garantien auf allen Produktionseinheitspreisen und dem Annehmen der verfügbaren Menge aller Eingänge ist bekannt, was gab Einheitspreiskalkulationsschema ein unterzugehen, um Gesamtverbrauch zu minimieren?

Zu jeder Variable im ursprünglichen Raum entspricht eine Ungleichheit, um im Doppelraum, beide zu befriedigen, die durch die Output-Art mit einem Inhaltsverzeichnis versehen sind. Zu jeder Ungleichheit, um im ursprünglichen Raum zu befriedigen, entspricht eine Variable im Doppelraum, beide, die durch den Eingangstyp mit einem Inhaltsverzeichnis versehen sind.

Die Koeffizienten, die die Ungleichheit im ursprünglichen Raum gebunden haben, werden verwendet, um das Ziel im Doppelraum zu schätzen, Mengen in diesem Beispiel einzugeben. Die Koeffizienten haben gepflegt zu rechnen das Ziel im ursprünglichen Raum hat die Ungleichheit im Doppelraum, Produktionseinheitspreise in diesem Beispiel gebunden.

Sowohl das ursprüngliche als auch die Doppelprobleme machen von derselben Matrix Gebrauch. Im ursprünglichen Raum drückt diese Matrix den Verbrauch von physischen Mengen von Eingängen aus, die notwendig sind, um Satz-Mengen von Produktionen zu erzeugen. Im Doppelraum drückt es die Entwicklung der Wirtschaftswerte aus, die mit den Produktionen von festgelegten Eingangseinheitspreisen vereinigt sind.

Da jede Ungleichheit durch eine Gleichheit und eine lockere Variable ersetzt werden kann, bedeutet das, dass jede ursprüngliche Variable einer lockeren Doppelvariable entspricht, und jede Doppelvariable einer ursprünglichen lockeren Variable entspricht. Diese Beziehung erlaubt uns der Ergänzungsschlaffheit.

Ein anderes Beispiel

Manchmal kann man es intuitiver finden, um das Doppelprogramm zu erhalten, ohne auf die Programm-Matrix zu schauen. Denken Sie das folgende geradlinige Programm:

Wir haben M + n Bedingungen, und alle Variablen sind nichtnegativ. Wir werden M + n Doppelvariablen definieren: y und s. Wir kommen:

Da das ein Minimierungsproblem ist, würden wir gern ein Doppelprogramm erhalten, das ein des ursprünglichen gebundener niedrigerer ist. Mit anderen Worten würden wir gern die Summe von ganz richtigen Handseite der Einschränkungen das maximale unter der Bedingung sein, dass für jede ursprüngliche Variable die Summe seiner Koeffizienten seinen Koeffizienten in der geradlinigen Funktion nicht überschreitet. Zum Beispiel erscheint x in n + 1 Einschränkungen. Wenn wir die Koeffizienten seiner Einschränkungen summieren, kommen wir ja + ja +... + ja + fs. Diese Summe muss am grössten Teil von c sein. Infolgedessen kommen wir:

Bemerken Sie, dass wir in unseren Berechnungsschritten annehmen, dass das Programm in der Standardform ist. Jedoch kann jedes geradlinige Programm in die Standardform umgestaltet werden, und es ist deshalb nicht ein Begrenzungsfaktor.

Bedeckung einpackende Dualitäten

Eine Bedeckungs-LP ist ein geradliniges Programm der Form:

: Minimieren Sie:

: Thema:

solch, dass die Matrix A und die Vektoren b und c nichtnegativ ist.

Die Doppel-von einer Bedeckungs-LP ist eine sich verpacken lassende LP, ein geradliniges Programm der Form:

: Maximieren Sie:

: Thema:solch, dass die Matrix A und die Vektoren b und c nichtnegativ ist.

Beispiele

Die Bedeckung und die Verpackung der LP entstehen allgemein als eine geradlinige Programmierentspannung eines kombinatorischen Problems und sind in der Studie von Annäherungsalgorithmen wichtig. Zum Beispiel packen die LP-Entspannungen des Satz-Verpackungsproblems, des unabhängigen Satz-Problems und des zusammenpassenden Problems LP ein. Die LP-Entspannungen des Satz-Deckel-Problems, des Scheitelpunkt-Deckel-Problems und des Beherrschens gehen unter Problem bedecken auch LP.

Die Entdeckung eines Bruchfärbens eines Graphen ist ein anderes Beispiel einer Bedeckungs-LP. In diesem Fall gibt es eine Einschränkung für jeden Scheitelpunkt des Graphen und einer Variable für jeden unabhängigen Satz des Graphen.

Ergänzungsschlaffheit

Es ist möglich, eine optimale Lösung des Doppel-zu erhalten, wenn nur eine optimale Lösung des ursprünglichen mit dem Ergänzungsschlaffheitslehrsatz bekannt ist. Die Lehrsatz-Staaten:

Nehmen Sie an, dass x = (x, x..., x) ausführbar ursprünglich ist, und dass y = (y, y..., y) ausführbar Doppel-ist. Lassen Sie (w, w..., w) zeigen die entsprechenden ursprünglichen lockeren Variablen an und lassen (z, z..., z) zeigen die entsprechenden lockeren Doppelvariablen an. Dann sind x und y für ihre jeweiligen Probleme wenn und nur wenn optimal

• x z = 0, für j = 1, 2..., n, und
• w y = 0, weil ich = 1, 2..., M.

So, wenn sich die i-th lockern, ist die Variable des ursprünglichen nicht Null, dann ist die i-th Variable des Doppel-der Null gleich. Ebenfalls, wenn sich die j-th lockern, ist die Variable des Doppel-nicht Null, dann ist die j-th Variable des ursprünglichen der Null gleich.

Diese notwendige Bedingung für optimality befördert einen ziemlich einfachen Wirtschaftsgrundsatz. In der Standardform (wenn es maximiert), wenn dort in einer gezwungenen ursprünglichen Quelle locker ist (d. h. gibt es "Reste"), dann müssen zusätzliche Mengen dieser Quelle keinen Wert haben. Ebenfalls, wenn dort in der Doppel(schatten)-Preisnichtnegativitätseinschränkungsvoraussetzung locker ist, d. h. der Preis ist nicht Null, dann muss es knappen Bedarf (keine "Reste") geben.

Theorie

Existenz von optimalen Lösungen

Geometrisch definieren die geradlinigen Einschränkungen das ausführbare Gebiet, das ein konvexes Polyeder ist. Eine geradlinige Funktion ist eine konvexe Funktion, die andeutet, dass jedes lokale Minimum ein globales Minimum ist; ähnlich ist eine geradlinige Funktion eine konkave Funktion, die andeutet, dass jedes lokale Maximum ein globales Maximum ist.

Optimale Lösung braucht aus zwei Gründen nicht zu bestehen. Erstens, wenn zwei Einschränkungen inkonsequent sind, dann besteht keine mögliche Lösung: Zum Beispiel können die Einschränkungen x  2 und x  1 nicht gemeinsam zufrieden sein; in diesem Fall sagen wir, dass die LP unausführbar ist. Zweitens, wenn der polytope in der Richtung auf den Anstieg der objektiven Funktion unbegrenzt ist (wo der Anstieg der objektiven Funktion der Vektor der Koeffizienten der objektiven Funktion ist), dann wird kein optimaler Wert erreicht.

Optimale Scheitelpunkte (und Strahlen) Polyeder

Sonst, wenn eine mögliche Lösung besteht, und wenn die (geradlinige) objektive Funktion begrenzt wird, dann wird der optimale Wert immer an der Grenze von optimalem Niveau-gesetztem, durch den maximalen Grundsatz für konvexe Funktionen (wechselweise, durch den minimalen Grundsatz für konkave Funktionen) erreicht: Rufen Sie Zurück, dass geradlinige Funktionen sowohl konvex als auch konkav sind. Jedoch haben einige Probleme verschiedene optimale Lösungen: Zum Beispiel ist das Problem, eine mögliche Lösung zu einem System der geradlinigen Ungleichheit zu finden, ein geradliniges Programmierproblem, in dem die objektive Funktion die Nullfunktion (d. h. die unveränderliche Funktion ist, die die Wertnull überall nimmt): Für dieses Durchführbarkeitsproblem mit der Nullfunktion für seine objektive Funktion, wenn es zwei verschiedene Lösungen gibt, dann ist jede konvexe Kombination der Lösungen eine Lösung.

Die Scheitelpunkte des polytope werden auch grundlegende mögliche Lösungen genannt. Der Grund für diese Wahl des Namens ist wie folgt. Lassen Sie d die Zahl von Variablen anzeigen. Dann bezieht der Hauptsatz der geradlinigen Ungleichheit ein (für ausführbare Probleme), dass für jeden Scheitelpunkt x der LP ausführbares Gebiet, dort eine Reihe von d (oder weniger) Ungleichheitseinschränkungen von der solcher LP besteht, dass, wenn wir jene d Einschränkungen als Gleichheiten behandeln, die einzigartige Lösung x ist. Dadurch können wir diese Scheitelpunkte mittels des Schauens an bestimmten Teilmengen des Satzes aller Einschränkungen (ein getrennter Satz), aber nicht das Kontinuum von LP-Lösungen studieren. Dieser Grundsatz unterliegt dem Simplexalgorithmus, um geradlinige Programme zu lösen.

Algorithmen

Basisaustauschalgorithmen

Simplexalgorithmus von Dantzig

Der Simplexalgorithmus, der von George Dantzig 1947 entwickelt ist, behebt LP-Probleme durch das Konstruieren einer möglichen Lösung an einem Scheitelpunkt des polytope und dann das Wandern entlang einem Pfad an den Rändern des polytope zu Scheitelpunkten mit nichtabnehmenden Werten der objektiven Funktion, bis ein Optimum erreicht wird. In vielen praktischen Problemen, "" kommt vor: Viele Türangeln werden ohne Zunahme in der objektiven Funktion gemacht. In seltenen praktischen Problemen können die üblichen Versionen des Simplexalgorithmus wirklich "Rad fahren". Um Zyklen zu vermeiden, haben Forscher neue sich drehende Regeln entwickelt.

In der Praxis ist der Simplexalgorithmus ziemlich effizient und kann versichert werden, das globale Optimum zu finden, wenn bestimmte Vorsichtsmaßnahmen gegen das Radfahren genommen werden. Wie man bewiesen hat, hat der Simplexalgorithmus "zufällige" Probleme effizient, d. h. in einer Kubikzahl von Schritten behoben, die seinem Verhalten auf praktischen Problemen ähnlich ist.

Jedoch hat der Simplexalgorithmus schlechtes Grenzfall-Verhalten: Klee und Minty haben eine Familie von geradlinigen Programmierproblemen gebaut, für die die Simplexmethode mehrere in der Problem-Größe Exponential-Schritte macht. Tatsächlich für einige Zeit war es nicht bekannt, ob das geradlinige Programmierproblem in der polynomischen Zeit, d. h. der Kompliziertheitsklasse P lösbar war.

Kreuzalgorithmus

Wie der Simplexalgorithmus von Dantzig ist der Kreuzalgorithmus ein Basisaustauschalgorithmus, den das zwischen Basen drehbar lagert. Jedoch braucht der Kreuzalgorithmus nicht Durchführbarkeit aufrechtzuerhalten, aber kann sich eher von einer ausführbaren Basis bis eine unausführbare Basis drehen. Der Kreuzalgorithmus hat polynomische Zeitkompliziertheit für die geradlinige Programmierung nicht. Beide Algorithmen besuchen alle 2 Ecken eines (gestörten) Würfels in der Dimension D, der Würfel von Klee-Minty (nach Victor Klee und George J. Minty) im Grenzfall.

Innenpunkt

Ellipsoid-Algorithmus, im Anschluss an Khachiyan

Das ist der erste Grenzfall polynomisch-maliger Algorithmus für die geradlinige Programmierung. Um ein Problem zu beheben, das n Variablen hat und in L-Eingangsbit verschlüsselt werden kann, verwendet dieser Algorithmus O (nL) pseudoarithmetische Operationen auf Zahlen mit O (L) Ziffern. Der Algorithmus von Khachiyan und sein langes Stehproblem wurden von Leonid Khachiyan 1979 mit der Einführung der Ellipsoid-Methode aufgelöst. Die Konvergenz-Analyse hat (reelle Zahl) Vorgänger, namentlich die wiederholenden Methoden, die von Naum Z. Shor und den Annäherungsalgorithmen durch Arkadi Nemirovski und D. Yudin entwickelt sind.

Projektiver Algorithmus von Karmarkar

Der Algorithmus von Khachiyan ist von merklicher Wichtigkeit gewesen, für die polynomisch-malige Lösbarkeit von geradlinigen Programmen zu gründen. Der Algorithmus war nicht ein rechenbetonter Durchbruch, weil die Simplexmethode für alle außer besonders gebauten Familien von geradlinigen Programmen effizienter ist.

Jedoch hat der Algorithmus von Khachiyan neue Linien der Forschung in der geradlinigen Programmierung begeistert. 1984 hat N. Karmarkar eine projektive Methode für die geradlinige Programmierung vorgeschlagen. Der Algorithmus von Karmarkar hat das gebundene (Geben) des Polynoms des Grenzfalls von Khachiyan übertroffen. Karmarkar hat behauptet, dass sein Algorithmus in der praktischen LP viel schneller war als die Simplexmethode, ein Anspruch, der großes Interesse an Innenpunkt-Methoden geschaffen hat. Seine projektive Geometrie ist interessant.

Pfad folgende Algorithmen

Im Gegensatz zum Simplexalgorithmus, der eine optimale Lösung durch das Überqueren der Ränder zwischen Scheitelpunkten auf einem polyedrischen Satz, Innenpunkt-Methode-Bewegung durch das Interieur des ausführbaren Gebiets findet. Seitdem sind viele Innenpunkt-Methoden vorgeschlagen und analysiert worden. Früh haben erfolgreiche Durchführungen auf affine kletternde Varianten der Methode basiert. Sowohl zu theoretischen als auch zu praktischen Zwecken, Barriere-Funktion oder Pfad folgenden Methoden sind seit den 1990er Jahren am populärsten gewesen.

Vergleich von Innenpunkt-Methoden gegen Simplexalgorithmen

Die aktuelle Meinung ist, dass die Leistungsfähigkeit von guten Durchführungen von simplexbasierten Methoden und Innenpunkt-Methoden für alltägliche Anwendungen der geradlinigen Programmierung ähnlich ist. Jedoch, für spezifische Typen von LP-Problemen, kann es sein, dass ein Typ von solver besser ist als ein anderer (manchmal viel besser).

LP solvers ist im weit verbreiteten Gebrauch für die Optimierung von verschiedenen Problemen in der Industrie wie Optimierung des Flusses in Transport-Netzen.

Offene Probleme und neue Arbeit

Es gibt mehrere offene Probleme in der Theorie der geradlinigen Programmierung, deren Lösung grundsätzliche Durchbrüche in der Mathematik und potenziell größere Fortschritte in unserer Fähigkeit vertreten würde, groß angelegte geradlinige Programme zu lösen.

• Lässt LP einen stark polynomisch-maligen Algorithmus zu?
• Lässt LP einen stark polynomischen Algorithmus zu, eine ausschließlich ergänzende Lösung zu finden?
• Lässt LP einen polynomischen Algorithmus in der reellen Zahl zu (Einheit kostete) das Modell der Berechnung?

Dieser nah zusammenhängende Satz von Problemen ist von Stephen Smale als unter den 18 größten ungelösten Problemen des 21. Jahrhunderts zitiert worden. In den Wörtern von Smale ist die dritte Version des Problems "das ungelöste Hauptproblem der geradlinigen Programmiertheorie." Während Algorithmen bestehen, um geradlinige Programmierung in der schwach polynomischen Zeit, wie die Ellipsoid-Methoden und Innenpunkt-Techniken zu lösen, sind keine Algorithmen noch gefunden worden, dass stark polynomisch-malige Leistung in der Zahl von Einschränkungen und der Zahl von Variablen erlauben. Die Entwicklung solcher Algorithmen würde von großem theoretischem Interesse sein, und vielleicht praktische Gewinne im Lösen großer LP ebenso erlauben.

Obwohl die Vermutung von Hirsch kürzlich für höhere Dimensionen widerlegt wurde, lässt sie noch die folgenden Fragen offen.

• Gibt es Türangel-Regeln die führen zu polynomisch-maligen Simplexvarianten?
• Haben alle polytopal Graphen polynomisch begrenztes Diameter?

Diese Fragen beziehen sich auf die Leistungsanalyse und Entwicklung von simplexähnlichen Methoden. Die riesige Leistungsfähigkeit des Simplexalgorithmus in der Praxis trotz seiner exponentialmaligen theoretischen Leistung deutet an, dass es Schwankungen des Simplexes geben kann, die im Polynom oder sogar stark polynomische Zeit laufen. Es würde der großen praktischen und theoretischen Bedeutung sein zu wissen, ob irgendwelche solche Varianten besonders als eine Annäherung an das Entscheiden bestehen, wenn LP in der stark polynomischen Zeit gelöst werden kann.

Der Simplexalgorithmus und seine Varianten fallen in der Familie von Rand folgenden Algorithmen, so genannt, weil sie geradlinige Programmierprobleme beheben, indem sie sich vom Scheitelpunkt bis Scheitelpunkt entlang Rändern eines polytope bewegen. Das bedeutet, dass ihre theoretische Leistung durch die maximale Zahl von Rändern zwischen irgendwelchen zwei Scheitelpunkten auf der LP polytope beschränkt wird. Infolgedessen interessieren wir uns für das Wissen des maximalen mit dem Graphen theoretischen Diameters von polytopal Graphen. Es ist bewiesen worden, dass alle polytopes Subexponentialdiameter haben. Die neue Widerlegung der Vermutung von Hirsch ist der erste Schritt sich zu erweisen, ob ein polytope superpolynomisches Diameter hat. Wenn irgendwelche solche polytopes bestehen, dann kann keine Rand folgende Variante in der polynomischen Zeit laufen. Fragen über das polytope Diameter sind von unabhängigem mathematischem Interesse.

Simplextürangel-Methoden bewahren ursprünglich (oder Doppel-) Durchführbarkeit. Andererseits bewahren Kreuztürangel-Methoden (ursprünglich oder Doppel-) Durchführbarkeit nicht — sie können ursprüngliche ausführbare, unausführbare ursprüngliche-Und-Doppel- oder ausführbare Doppelbasen in jeder Ordnung besuchen. Türangel-Methoden dieses Typs sind seit den 1970er Jahren studiert worden. Im Wesentlichen versuchen diese Methoden, den kürzesten Türangel-Pfad auf der Einordnung polytope unter dem geradlinigen Programmierproblem zu finden. Im Gegensatz zu polytopal Graphen, wie man bekannt, haben Graphen der Einordnung polytopes kleines Diameter, die Möglichkeit des stark polynomisch-maligen Kreuztürangel-Algorithmus erlaubend, ohne Fragen über das Diameter von allgemeinem polytopes aufzulösen.

Ganze Zahl unknowns

Wenn die unbekannten Variablen alle erforderlich sind, ganze Zahlen zu sein, dann wird das Problem ein Problem der Programmierung der ganzen Zahl (IP) oder ganzen Zahl geradlinigen Programmierung (ILP) genannt. Im Gegensatz zur geradlinigen Programmierung, die effizient im Grenzfall gelöst werden kann, sind Programmierprobleme der ganzen Zahl in vielen praktischen Situationen (diejenigen mit begrenzten Variablen) NP-hard. 0-1 Programmierung der ganzen Zahl oder binäre Programmierung der ganzen Zahl (BIP) sind der spezielle Fall der Programmierung der ganzen Zahl, wo Variablen erforderlich sind, 0 oder 1 (aber nicht willkürliche ganze Zahlen) zu sein. Dieses Problem wird auch als NP-hard klassifiziert, und tatsächlich war die Entscheidungsversion eines von 21 NP-complete Problemen von Karp.

Wenn nur einige der unbekannten Variablen erforderlich sind, ganze Zahlen zu sein, dann wird das Problem ein Problem der Mischprogrammierung der ganzen Zahl (MIP) genannt. Das ist allgemein auch NP-hard.

Es gibt jedoch einige wichtige Unterklassen von IP und MIP Problemen, die, am meisten namentlich Probleme effizient lösbar sind, wo die Einschränkungsmatrix völlig unimodular ist, und die Rechten der Einschränkungen ganze Zahlen sind.

Fortgeschrittene Algorithmen, um ganze Zahl geradlinige Programme zu lösen, schließen ein:

• schneidstufige Methode
• Zweig und gebundener
• Zweig und Kürzung
• Zweig und Preis
• wenn das Problem eine Extrastruktur hat, kann es möglich sein, verzögerte Säulengeneration anzuwenden.

Solche ganze Zahl programmierenden Algorithmen werden von Padberg und in Beasley besprochen.

Integrierte geradlinige Programme

Wie man

sagt, ist ein geradliniges Programm in echten Variablen integriert, wenn es mindestens eine optimale Lösung hat, die integriert ist. Ebenfalls, wie man sagt, ist ein Polyeder integriert, wenn für alle begrenzten ausführbaren objektiven Funktionen c das geradlinige Programm ein Optimum mit Koordinaten der ganzen Zahl hat. Wie beobachtet, durch Edmonds und Giles 1977 kann man gleichwertig sagen, dass ein Polyeder integriert ist, wenn für jede begrenzte ausführbare integrierte objektive Funktion c der optimale Wert des geradlinigen Programms eine ganze Zahl ist.

Integrierte geradlinige Programme sind von Hauptwichtigkeit im polyedrischen Aspekt der kombinatorischen Optimierung, da sie eine abwechselnde Charakterisierung eines Problems zur Verfügung stellen. Spezifisch, für jedes Problem, ist der konvexe Rumpf der Lösungen ein integriertes Polyeder; wenn dieses Polyeder eine nette/kompakte Beschreibung hat, dann können wir die optimale mögliche Lösung unter jedem geradlinigen Ziel effizient finden. Umgekehrt, wenn wir beweisen können, dass eine geradlinige Programmierentspannung integriert ist, dann ist es die gewünschte Beschreibung des konvexen Rumpfs von ausführbaren (integrierten) Lösungen.

Bemerken Sie, dass Fachsprache überall in der Literatur nicht entspricht, so sollte man darauf achten, die folgenden zwei Konzepte, zu unterscheiden

• in einer ganzen Zahl wird geradliniges Programm, das in der vorherigen Abteilung, Variablen beschrieben ist, gewaltsam beschränkt, ganze Zahlen zu sein, und dieses Problem ist NP-hard im Allgemeinen,
• in einem integrierten geradlinigen Programm, das in dieser Abteilung beschrieben ist, werden Variablen nicht beschränkt, ganze Zahlen zu sein, aber eher hat man irgendwie bewiesen, dass das dauernde Problem immer einen integrierten optimalen Wert hat (das Annehmen c ist integriert), und dieser optimale Wert kann effizient gefunden werden seit der ganzen polynomischen Größe können geradlinige Programme in der polynomischen Zeit gelöst werden.

Eine allgemeine Weise zu beweisen, dass ein Polyeder integriert ist, soll zeigen, dass es völlig unimodular ist. Es gibt andere allgemeine Methoden einschließlich des Zergliederungseigentums der ganzen Zahl und ganzen Doppelintegrality. Andere spezifische wohl bekannte integrierte LP schließt das Zusammenbringen polytope, die Gitter-Polyeder, die Submodulfluss-Polyeder ein, und die Kreuzung 2 hat verallgemeinert polymatroids/g-polymatroids---sehen z.B Schrijver 2003.

Ein begrenztes integriertes Polyeder wird manchmal ein konvexes Gitter polytope besonders in zwei Dimensionen genannt.

Solvers und scripting (Programmierung) von Sprachen

Freie offene Quelle permissive Lizenzen:

Freie offene Quelle copyleft (gegenseitige) Lizenzen:

MINTO (Gemischte Ganze Zahl Optimizer, eine ganze Zahl, solver programmierend, der Zweig und gebundenen Algorithmus verwendet) lässt öffentlich verfügbare Quelle codieren, aber Quelle nicht öffnen.

Eigentums-:

Siehe auch

• Mathematische Programmierung

Nichtlineare Programmierung

• Konvexe Programmierung
• Dynamische Programmierung
• Simplexalgorithmus, verwendet, um LP-Probleme zu beheben
• Quadratische Programmierung, eine Obermenge der geradlinigen Programmierung
• Schattenpreis
• Datei der MITGLIEDER DES PARLAMENTS formatiert
• Nl-Datei formatiert
• MIP Beispiel, Job-Geschäftsproblem
• Geradlinig-Bruchprogrammierung (LFP)
• Orientierter matroid
• Problem des LP-TYPS

Referenzen

• L.V. Kantorovich: Eine neue Methode, einige Klassen von extremal Problemen, Doklady Akad Sci die UDSSR, 28, 1940, 211-214 zu lösen.
• G.B Dantzig: Die Maximierung einer geradlinigen Funktion von Variablen unterwirft der geradlinigen Ungleichheit, 1947. Veröffentlichte Seiten 339-347 in T.C. Koopmans (Hrsg.):Activity Analyse der Produktion und der Zuteilung, des New-Yorks-Londons 1951 (Wiley & Chapman-Hall)
• J. E. Beasley, Redakteur. Fortschritte im Geradlinigen und der Programmierung der Ganzen Zahl. Wissenschaft von Oxford, 1996. (Sammlung von Überblicken)
• R. G. Bland, Neue begrenzte sich drehende Regeln für die Simplexmethode, Mathematik. Oper. Res. 2 (1977) 103-107.
• Karl-Heinz Borgwardt, Der Simplexalgorithmus: Eine Probabilistic Analyse, Algorithms und Combinatorics, Band 1, Springer-Verlag, 1987. (Durchschnittliches Verhalten auf zufälligen Problemen)
• Richard W. Cottle, Hrsg. Der Grundlegende George B. Dantzig. Geschäftsbücher von Stanford, Universität von Stanford Presse, Stanford, Kalifornien, 2003. (Ausgewählte Vorträge von George B. Dantzig)
• George B. Dantzig und Mukund N. Thapa. 1997. Geradlinige Programmierung 1: Einführung. Springer-Verlag.
• George B. Dantzig und Mukund N. Thapa. 2003. Geradlinige Programmierung 2: Theorie und Erweiterungen. Springer-Verlag. (Umfassend, z.B das Drehen und die Innenpunkt-Algorithmen, die groß angelegten Probleme, die Zergliederung im Anschluss an Dantzig-Wolfe und Saufereien und das Einführen stochastischer Programmierung bedeckend.)
• Edmonds, J. und Giles, R., "Eine Beziehung der Minute-max für Submodulfunktionen auf Graphen," Ann. Getrennte Mathematik. v1, Seiten 185-204, 1977
• Evar D. Nering und Albert W. Tucker, 1993, Geradlinige Programme und Zusammenhängende Probleme, Akademische Presse. (elementarer)
• M. Padberg, Geradlinige Optimierung und Erweiterungen, die Zweite Ausgabe, der Springer-Verlag, 1999. (sorgfältig geschriebene Rechnung von ursprünglichen und Doppelsimplexalgorithmen und projektiven Algorithmen, mit einer Einführung in die ganze Zahl geradlinige Programmierung---Aufmachung des Handelsreisender-Problems für Odysseus.)
• Christos H. Papadimitriou und Kenneth Steiglitz, Kombinatorische Optimierung: Algorithmen und Kompliziertheit, Korrigierte Neuauflage mit einer neuen Einleitung, Dover. (Informatik)

• (Eingeladener Überblick, vom Internationalen Symposium auf der Mathematischen Programmierung.)

• (Informatik)

Weiterführende Literatur

Ein Leser kann denken, mit Nering und Tucker, mit dem ersten Volumen von Dantzig und Thapa, oder mit Williams zu beginnen.

• Dmitris Alevras und Manfred W. Padberg, Geradlinige Optimierung und Erweiterungen: Probleme und Lösungen, Universitext, Springer-Verlag, 2001. (Probleme von Padberg mit Lösungen.)

• Kapitel 4: Geradlinige Programmierung: Seiten 63-94. Beschreibt einen randomized Halbflugzeug-Kreuzungsalgorithmus für die geradlinige Programmierung.

• A6: MP1: PROGRAMMIERUNG DER GANZEN ZAHL, pg.245. (Informatik, Kompliziertheitstheorie)
• Bernd Gärtner, Jiří Matoušek (2006). Verstehend und das Verwenden Geradliniger Programmierung, Berlins: Springer. Internationale Standardbuchnummer 3-540-30697-8 (elementare Einführung für Mathematiker und Computerwissenschaftler)
• Cornelis Roos, Tamás Terlaky, Jean-Philippe Vial, Innenpunkt-Methoden für die Geradlinige Optimierung, die Zweite Ausgabe, den Springer-Verlag, 2006. (Absolventenniveau)
• Alexander Schrijver, Theorie von Geradlinigen und Programmierung der Ganzen Zahl. John Wiley & Söhne, 1998, internationale Standardbuchnummer 0-471-98232-6 (mathematische)
• Robert J. Vanderbei, Geradlinige Programmierung: Fundamente und Erweiterungen, 3. Hrsg., Internationale Reihe in der Operationsforschung & Verwaltungswissenschaft, Vol. 114, Springer Verlag, 2008. Internationale Standardbuchnummer 978-0-387-74387-5. (Eine zweite Online-Ausgabe war früher verfügbar. Die Seite von Vanderbei enthält noch umfassende Materialien.)
• H. P. Williams, Mustergebäude in der Mathematischen Programmierung, der Dritten verbesserten Auflage, 1990. (Das Modellieren)
• Stephen J. Wright, 1997, Ursprünglich-Doppelinnenpunkt-Methoden, SIAM. (Absolventenniveau)
• Yinyu Ye, 1997, Innenpunkt-Algorithmen: Theorie und Analyse, Wiley. (Fortgeschrittenes Absolventenniveau)
• Ziegler, Günter M., Kapitel 1-3 und 6-7 in Vorträgen auf Polytopes, Springer-Verlag, New York, 1994. (Geometrie)

Links

• Leitung bei der Formulierung von LP-Problemen
• Mathematisches Programmierwörterverzeichnis
• Die geradlinigen häufig gestellten Programmierfragen
• Abrisspunkte für die Optimierungssoftware
• 2009 Geradliniger Programmiersoftwareüberblick - ODER/FRAU Heute
• George Dantzig