Machbarkeitsproblem für lineare Programmierung mit strengen Positivitätsbeschränkungen

  • Es gibt ein System linearer Abhängigkeiten $ {\ bf Ax} \ leq {\ bf b} $. Ich möchte einen strikt positiven Vektor finden. $ {\ Bf x} & gt; 0 $, der diese Bedingungen erfüllt. Das heißt, $ x_i & gt; 0 $ ist für jede Komponente $ x_i $ von $ {\ bf x} $ erforderlich. Wie kann ich einen LP-Solver verwenden, um einen solchen streng positiven Vektor $ {\ bf x} $ zu finden (oder bestätigen) nein $ {\ bf x} $ existiert)? Ich kann nicht einfach ein anderes System von Einschränkungen einführen. $ X_i & gt; 0 $, weil Gleichheit in einer LP immer zulässig sein muss - aber ich kann den LP-Solver mit wechselnden Zielfunktionen mehrmals verwenden. Ich denke, ich sollte die Variable-Variable-Methode verwenden, aber ich ziehe das nicht weiß nicht wie.

    24 January 2012
    prakash
4 answers
  • Sie können das Problem der Auswahl eines kleinen $ \ epsilon & gt; 0 $ umgehen, indem Sie etwas ehrgeiziger sind: Versuchen Sie, $ \ mathbf {x} $ so zu finden, dass $ \ mathbf {Ax} \ leq \ mathbf {b} $ und dass der kleinste Eintrag in $ \ mathbf {x} $ so groß wie möglich ist.

    Fügen Sie zu diesem Zweck eine neue Variable $$ \ mathbf {ein. y} = \ begin {bmatrix} \ mathbf {x} \\ \ epsilon \ end {bmatrix} \ in \ mathbb {R} ^ {n + 1} $$ (wenn $ \ mathbf {x} $ war in $ \ mathbb {R} ^ n $) und lösen Sie das folgende Problem durch einen LP-Solver $$ \ max_y [0 \ dots 0 \ 1] \ cdot \ mathbf {y} \ quad \ text {st} \ quad [A \ \ mathbf {0}] \ mathbf {y} \ leq \ mathbf {b} \ quad \ text {und} \ quad \ mathbf {0} \ leq \ begin {bmatrix} 1 & amp; &Ampere; &Ampere; 1 \\ & amp; \ ddots & amp; & amp; \ vpunkte \\ & amp; &Ampere; 1 & amp; 1 \ end {bmatrix} \ mathbf {y}. $$

    Dies ist eine Neuformulierung des folgenden Problems: $$ \ max \ epsilon \ quad \ text {st} \ quad \ mathbf {Ax \ leq b} \ quad \ text {und} \ quad \ mathbf {x} \ geq \ epsilon \ mathbf {1}. $$

    24 January 2012
    Jake McGraw
  • Für ein LP-Durchführbarkeitsproblem würde ich kein Standard-Simplex verwenden. Standard-Primimal-Algorithmen (oder Dual-Simplex-Algorithmen) werden nur die Scheitelpunkte der realisierbaren Menge der Prim-Probleme (oder Dual-Probleme) untersuchen.

    Lassen Sie die möglichen Probleme des Problems, das Sie tatsächlich lösen möchten, $ F = \ {\ mathbf {x} sein: \ mathbf {Axe} \ leq \ mathbf {b}, \ mathbf {x} & gt; \ mathbf {0} \} $, und stattdessen sollten Sie das Problem lösen ($ F _ {\ varepsilon} $):

    $$ \ begin {alignat} {1 } & amp; \ min _ {\ mathbf {x}} \ quad 0 \\ \ textrm {s.t.} & amp; \ quad \ mathbf {Ax} \ leq \ mathbf {b} \\ & amp; \ quad \ mathbf {x} \ geq \ varepsilon \ cdot \ mathbf {1}. \ end {alignat} $$

    Die nächste Annäherung an das Problem, das Sie lösen möchten, ist $ F_ {0} $, das etwas zu viele Punkte zulässt . Das Problem ist, dass die Grenze des positiven Orthanten (dh die Menge $ B = \ {\ mathbf {x}): \ mathbf {x} \ geq 0, \ besteht {i}: x_ {i} = 0 \} $ Könnte einen Teil der Grenze des möglichen Satzes von $ F_ {0} $ ausmachen. Wir möchten diese Punkte ausschließen. Eine Möglichkeit, dies zu tun, ist das zu tun, was Aron vorgeschlagen hat, nämlich $ \ varepsilon $ auf einige zu setzen Wenn Sie einen kleinen positiven Wert verwenden, dann verwenden Sie einen beliebigen LP-Standardalgorithmus. Diese Strategie ist gut und wird wahrscheinlich in einer Vielzahl von Situationen zum Einsatz kommen. Wenn jedoch $ F _ {\ varepsilon} $ nicht durchführbar ist, wird dies fehlschlagen F_ {0} \ subset F \ subset F _ {\ varepsilon} $ für alle $ \ varepsilon & gt; 0 $ (um die Notation zu missbrauchen und auf eine durchführbare Menge anhand des entsprechenden Problems zu verweisen), und es ist möglich, dass Sie auch ein kleines positives Ergebnis auswählen Werte von $ \ varepsilon $, gibt der LP-Solver an, dass Ihre LP nicht durchführbar ist.

    Für einen LP-Solver würde ich jeden inneren Punktalgorithmus für LPs verwenden, der mit einem machbare Punkte und bleibt machbar, was eine weitere Möglichkeit ist, Punkte auszuschließen, d. h n $ B $. Sie müssen für diese Algorithmen keinen machbaren Punkt angeben. Standardlöser erledigen das für Sie. Methoden wie affine Skalierung, Potenzialreduzierung und Barrieremethoden richten Hilfs-LPs ein, die sich als machbar herausstellen

    24 January 2012
    Geoff Oxberry
  • Durchführbarkeitsprobleme sind ein etwas schwierigeres Spiel als allgemeine lineare Probleme, die Sie bemerkt haben. Wenn Sie das Problem lösen (mit einer Fließkomma-Repräsentation des Gleichungssystems und der Bedingungen), ist es legitim, $ x_i & gt; = \ epsilon $ anzugeben, wobei $ \ epsilon $ ein sehr kleiner numerischer Wert ist, der groß genug ist um sicherzustellen, dass $ x_i $ tatsächlich in $ \ Re _ + $ lebt, aber klein genug, dass eine Lösung an der Grenze nicht berücksichtigt wird.

    Möglicherweise müssen Sie $ \ epsilon $ anpassen , und Ihre Lösung wird "innerhalb eines Faktors von $ \ epsilon $" qualifiziert, aber dies ist in vielen Situationen ausreichend.

    24 January 2012
    29 revs, 25 users 37%Shaik Raffi
  • Die Antwort von aeismail ist sorgfältig zu lesen, siehe lp

    $ \ max (x_1 + x_2) $

    st

    $ x_1 + x_2 \ le 1 $

    $ x_1, x_2 \ ge 0 $

    Es hat Lösungen $ (1,0) $ und $ (0,1) $ sowie andere (degeneriert). Die Allgemeingültigkeit der Frage impliziert, dass diese Fälle ebenfalls behandelt werden müssen.

    Da Sie Ihre Zielfunktion auswählen können, können Sie versuchen, sie iterativ zu ändern. Z.B. Beginnen Sie mit allen Koeffizienten für alle Variablen, die gleich eins sind, und prüfen Sie, ob Sie eine geeignete Lösung erhalten. Wenn eine Variable gleich Null ist, erhöhen Sie den Koeffizienten und beginnen Sie von vorne ...

    Obwohl ich keinen mathematischen Beweis dafür liefern kann, dass dies funktioniert (oder ein genau definiertes Verfahren, um das Ziel zu ändern Funktion). Ich hoffe das hilft:)

    24 January 2012
    MattH