Reduzieren der linearen Programmierung auf positive lineare Programmierung

Angenommen, wir haben ein Orakel, das Probleme der Form löst

wenn $c\geq 0$ (alle Koeffizienten im Maximierungsziel sind nicht negativ).

Kann es verwendet werden, um allgemeine lineare Programme effizient zu lösen?

FAILED ATTEMPT # 1: Ersetzen Sie jede Variable $x_i$ , die durch einen negativen Koeffizienten in $c^T x$ , durch eine andere Variable $y_i := - x_i$ . Leider erfüllt dieses $y_i$ nicht die Nicht-Negativitätsbedingung.

FAILED ATTEMPT # 2: Stellen Sie sicher, dass alle Elemente in $b$ nicht positiv sind (multiplizieren Sie die Gleichung bei Bedarf mit -1). Erstellen Sie dann die Dual-LP:

Hier sind alle Koeffizienten im Objektiv nicht negativ. Diese Form stimmt jedoch nicht mit der Form überein, die das Orakel lösen kann, da die Bedingungen keine Gleichungsbedingungen sind und die Variablen $y$ unbegrenzt sind.

Sie können für einige eine Variable und eine lineare Gleichheit hinzufügen . Dann entspricht das ursprüngliche Problem der Maximierung von im neuen System.$y$$y=c^Tx+c_0$$c_0$$y$

Mit Ausnahme der Bedingung . Hier kommt ins . Wir müssen groß machen, dass wir für ein realisierbares ( und hold) . In diesem Fall spielt es keine Rolle, dass Nicht-Negativität Teile des realisierbaren Raums abschneidet. Der optimale Wert ist immer noch der gleiche.$y\geq 0$$c_0$$c_0$$x$$Ax=b$$x\geq 0$$c^Tx+c_0\geq 0$

Wie wählt man also ? Ich bin kein Experte für lineare Optimierung. Ist es einfacher, ein machbares finden, als eines, das die Zielfunktion maximiert? Wenn ja, können wir als .$c_0$$x_0$$c_0$$-c^Tx_0$

Wenn die angegebenen Koeffizienten rational sind, gibt es einen anderen Weg. Stellen wir zunächst fest, dass das Polytop von machbarem Eckpunkte hat (es sei denn, es ist leer): Sei ein Punkt in einer minimaldimensionalen Grenzzelle des Polytops. Nehmen Sie im Widerspruch an, dass die Dimension dieser Zelle . Dann gibt es einen anderen Punkt in derselben Zelle. Da die Zelle eine minimale Abmessung hat, ist sie unbegrenzt, so dass Punkte der Form in derselben Zelle und somit im Polytop liegen. Da , haben einige solcher negative Koordinaten, was der Polytopbedingung widerspricht .$x$$p$$\geq 1$$q$$r=p+t(q-p)$$q-p\not=0$$r$$r\geq 0$

Machen Sie nun alle Koeffizienten von und ganzzahlig, indem Sie mit dem gemeinsamen Nenner multiplizieren. Sei die Dimension (die Länge des Vektors ) und sei der maximale Absolutwert eines beliebigen Koeffizienten von , oder . Dann können wir die Koordinaten eines beliebigen Scheitelpunkts des realisierbaren Polytops durch binden . Wählen Sie also .$A$$b$$n$$c$$M$$A$$b$$c$$n!\cdot M^n$$c_0:=n\cdot n!\cdot M^{n+1}$

[BEARBEITEN]

Noch ein anderer Ansatz, falls Sie bereit sind, das Orakel mehrmals anzurufen: Versuchen Sie zunächst das Obige mit . Wenn Sie eine Lösung oder die Antwort "unbegrenzt" erhalten, geht es Ihnen gut. Wenn die Antwort "unlösbar" ist, müssen Sie herausfinden, ob es Lösungen mit negativer Zielfunktion gibt. Setzen Sie daher und maximieren Sie stattdessen . Wenn Sie eine Lösung erhalten, können Sie diese als . Wenn Sie wieder "unlösbar" werden, sind Sie auch fertig. Der letzte Fall ist die Antwort "unbegrenzt". Dann müssen Sie immer größere ausprobieren (verwenden Sie für einige Orakelaufrufe eine schnell wachsende Funktion; die Ackermann-Funktion kann dies tun), bis Sie eine Lösung erhalten.$c_0=0$$z=-c^T$$z$$x_0$$c_0$

Sie können eine Variable x ohne positive Einschränkung durch zwei Variablen ersetzen, wobei sowohl als auch positiv sind. Alle ihre Koeffizienten sind identisch, außer dass sie das entgegengesetzte Vorzeichen haben.$x^+ - x^-$$x^+$$x^-$

Im Simplex-Algorithmus ist es immer möglich, nur einen davon in die Basis zu stellen. Tatsächlich können Sie zusätzliche Berechnungen vermeiden, indem Sie einfach verfolgen, ob eine Basisvariable derzeit positiv oder negativ ist.