Dual zu Primal < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:37 Do 23.02.2006 | | Autor: | ardik |
Hallo Ihr,
wie komme ich von den Lösungen des Dualen Problems zu denen des zugehörigen Primals?
Mir ist bekannt, dass das Produkt "korrespondierender" Lösungen gleich null ist. Aber da hört's auch schon auf.
Und was ist in diesem Zusammenhang ein "Schattenpreis"?
Aus dem mir vorliegenden Skript werde ich nicht recht schlau.
Mir ist klar, dass das u.U. eine sehr allgemeine Frage ist...
Links zu guten Skripts / Erklärungen sind natürlich auch sehr willkommen.
Herzliche Grüße,
ardik
|
|
| |
|
Hallo und guten Morgen ardik,
und hallo Freunde eines der Grundprinzipien der Mathematik ueberhaupt,
zunaechst mal:
Wenn man ein LP gegeben hat, wie kommt man dann auf das Duale ? Nun, langweilige Antwort waere: Ja, da gibt's ne
Formel fuer den allgemeinen Fall, die kann man nachschauen oder auswendig lernen, und dann macht man das so.
Besser ist es, die Intuition zu haben, so dass man dann ohne eine einzige auswendig gelernte Formel zu jedem LP
das Duale hinschreiben kann.
Also sei [mm] min\{cx\: |\: Ax\leq b\} [/mm] ein LP. (Jedes LP kann man in diese Form bringen.)
Dann erhaelt man das Duale wie folgt:
Man moechte fuer das Minimum des LP eine moeglichst gute untere Schranke berechnen. Wie macht man das ? Nun, die
einzige Information, die man hat, ist doch das LP selber.
Nun kann man doch versuchen, aus den Ungleichungen des LP eine untere Schranke zu erhalten.
Wenn also x eine Loesung des LP ist, so erfuellt x alle Ungleichungen [mm] a_jx\leq b_j, 1\leq j\leq [/mm] m,
wobei [mm] a_1,\ldots [/mm] , [mm] a_m [/mm] die Zeilen der Matrix A seine und [mm] b_1,\ldots [/mm] , [mm] b_m [/mm] die Eintraege von b.
Dann erfuellt solches x doch auch jede Linearkombinatiopn dieser Ungleichungen mit Koeffizienten [mm] y_j\geq [/mm] 0:
Aus
[mm] a_1x\leq b_1,.\ldots [/mm] , [mm] a_mx\leq b_m [/mm] folgt
[mm] \sum_{j=1}^m y_j\cdot a_j\cdot x\leq\sum_{j=1}^m y_j\cdot b_j.
[/mm]
Auf der linken Seite ist ja nun [mm] \sum_jy_j\cdot a_j [/mm] wieder ein Vektor. Wenn es nun gelingt, die Linearkombination so
zu waehlen, dass dieser Vektor komponentenweise - d.h. jeder einzelne Eintrag- kleiner oder gleich c ist, dann
ergibt doch die rechte Seite [mm] \sum_jy_j\cdot b_j [/mm] eine untere Schranke fuer das Optimum, richtig ?
Also suchen wir, um eine moeglichst gute untere Schranke zu berechnen, Koeffizienten [mm] y_j\geq [/mm] 0, so dass
[mm] \sum_jb_j\cdot y_j [/mm] maximal wird (eine moeglichst grosse untere Schranke)
unter der Nebenbedingung, dass
[mm] \sum_jy_j\cdot a_j [/mm] komponentenweise kleiner/gleich c ist, also:
[mm] \min\:\: b\cdot y\:\: [/mm] s.t.
[mm] \:\:\: y^T\cdot A\leq [/mm] c [mm] \:\:\: (c\:\: als\: Zeilenvektor\:\: [/mm] gelesen)
[mm] \:\:\: v\geq [/mm] 0
und das ist auch schon das Duale.
So einfach ist das schon mal.
Nun weiss man noch viel mehr, naemlich dass, wenn das Primale eine endliche Loesung hat, dann auch das Duale, und die beidel Loesungen haben denselben Wert, also das Minimum des Primalen ist gleich dem Maximum des Dualen. Weiterhin kann man ein solches Paar [mm] x^{\star}, y^{\star} [/mm] von primaler und dualer Loesung gut beschreiben
(Complelemtary Slackness, d.h Satz vom Komplementaeren Schlupf):
Es sind genau die Ungleichungen des Primalen mit Gleichheit erfuellt, fuer die die Dualen Variablen einen Wert >0 haben (besser: es gibt ein solches Paar von Loesungen).
Wenn man also eine Duale Loesung y hat und weiss, dass diese optimal ist, so sucht man also eine primale Loesung
x dadurch, dass man das LGS der Ungleichungen (auf Gleicheit gesetzt) loest, fuer die das entsprechende [mm] y_j [/mm] nicht gleich 0 ist.
Gut nachzulesen ist dies genauer im Buch von Alexander Schrijver ''Linear and Integer Programming'', die Intuition zu
Dualitaet findet man auch im Buch von V. Vazirani 'Approximation Algorithms'' gut beschrieben, allerdings nichts explizit zu Techniken der Linearen Optimierung, sondern eher zu deren Anwendung fuer Approximationsalgorithmen.
Viele Gruesse,
Mathias
|
|
|
| |
|
Hallo zusammen!
Auch ich bin grad bei dem "Problem" des Umformens von primal zu dual.
Aus der oberen Antwort kann man gut nachvollziehen wie der Hintergrund dazu ist und wie man auf das duale Problem kommt.
Aber:
Wie kann man dies mathematisch anders formulieren, sodass die Transformation als Nachweis/Beweis anzusehen und vielleicht auch kürzer ist.
Beispielsweise würde das Anwendung finden folgendes zu zeigen:
"Das duale vom dualen ist wieder das primal" -->Dual-Primale-Paare.
Desweiteren muss man ja auch Relationszeichen beim Umformen beachten bzw. ob x>=0 oder x=0 oder x frei ist. Ich weiß, dass sich Relationszeichen in der Nebenbedingung aufgrunddessen entsprechend ändern nur weiß ich nicht wie man dies mathematisch schreiben kann.
Da ich mich erst anfänglich mit linerer Optimierung beschäftige, hab ich noch nicht so richtig den Überblick über Transformationsregeln und welche man an welcher Stelle braucht.
Ich hoffe ihr könnt mir da weiterhelfen?
Viele Grüße,
Andy!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:20 Do 22.05.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
