Transformation des primalen in das duale LP |
| 16.03.2011, 19:38 | eisbearschen | Auf diesen Beitrag antworten » | ||
| Transformation des primalen in das duale LP Hi! Ich plag mich momentan mit dem Simplex-Algorithmus und im speziellen mit der Transformation des primalen in das duale LP rum. Der allgemeine Zusammenhang ist mir klar, jedoch versteh ich z.T. nicht so ganz die Umwandlungsregeln hinsichtlich der <=, =, unbeschr. und >= Relationen. In einer Tabelle, die dazu Regeln enthält steht folgendes: Umwandlung der NB des PLP zu Nebenbedingungen des DLP: <= NB des PLP wird zu >= Variablen des DLP >= NB des PLP wird zu <= Variablen des DLP = NB des PLP wird zu unbeschränkten Variablen des DLP Umwandlung der Variablen des PLP zu Nebenbedingungen des DLP: >= Variablen des PLP werden zu >= Nebenbedingungen des NB <= Variablen des PLP werden zu <= Nebenbedingungen des NB unbeschränkte Variablen des PLP werden zu = Nebenbedingungen des NB *EDIT* zur Verdeutlichung hab ich hier noch einmal die betreffende Grafik beigefügt:  http://bildr.no/view/844646Meine Ideen: leider versteh ich in diesem Kontext diese Umwandlungsregeln überhaupt nicht 
. Dass der Zielfunktionskoeffizienten-Vektor des PLP zum Restriktionsvektor/rechte Seite des DLP werden und vice versa ist mir klar. Nur handelt es sich bei den Komponenten dieser beiden Vektoren ja nicht um Variablen oder versteh ich da was total falsch?Vielen Dank vorab! |
||||
| 17.03.2011, 22:50 | Abakus | Auf diesen Beitrag antworten » | ||
RE: Transformation des primalen in das duale LP
Hallo, schau dir am besten ein Beispiel oder mehrere an und schaue, welche Beziehungen dort gelten. Die Umwandlungsregeln sind erstmal eine Definition, sonst nichts. Schaue auch hier: Dualitätsprinzip in der LP (Wiki) Grüße Abakus 
|
||||
| 18.03.2011, 11:31 | plizzz | Auf diesen Beitrag antworten » | ||
Hallo, mein Tipp an dich: Schlag dich nicht mit den Regeln rum. Schreibe einfach jedes Problem in die übliche Form max{c^t x: Ax <= b}, indem du die Matrizen von den Nebenbedingung in eine Matrix übereinander schreibst. Dann dualisierst du ganz normal und teilst ggf. den Vektor aus dem dualen Programm in mehrere Vektoren auf (da du ja mehrere Matrizen hast). Dann fasst du Vektoren zusammen, wenn es passt (zB Av - Aw = A(v-w) => (v-w)=:u, nur diesmal ohne >=0 Bedingung) und eliminierst die Schlupfvariablen. Am Ende hast du dann das duale LP. Das geht wirklich immer, ist sicher und sauber und du musst dich nicht mit irgendwelchen Regeln plagen, die am Anfang mehr das Verständnis stören als dass sie helfen. Wenn du oft dualisierst hast, dann verstehst du die Regeln und kannst dadurch etwas abkürzen, aber am Anfang ist es meiner Meinung nach viel besser, immer geradeaus durch zu dualisieren. |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
