matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenOperations ResearchDual zu Primal
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Deutsch • Englisch • Französisch • Latein • Spanisch • Russisch • Griechisch
Forum "Operations Research" - Dual zu Primal
Dual zu Primal < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Operations Research"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Dual zu Primal: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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

        
Bezug
Dual zu Primal: Allgemein zum Thema, Intuition
Status: (Antwort) fertig Status 
Datum: 07:11 Fr 24.02.2006
Autor: mathiash

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


Bezug
                
Bezug
Dual zu Primal: Frage (überfällig)
Status: (Frage) überfällig Status 
Datum: 10:40 Do 15.05.2008
Autor: AndyBruch

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!

Bezug
                        
Bezug
Dual zu Primal: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 11:20 Do 22.05.2008
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Operations Research"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


Alle Foren
Status vor 4h 10m 3. TS85
MaßTheo/Sigma-Algebra = P(X)
Status vor 21h 58m 8. Gonozal_IX
MaßTheo/Beweis Sigma-Algebra
Status vor 1d 20h 41m 6. hohohaha1234
USons/Größtmöglichstes Produkt
Status vor 2d 2. matux MR Agent
Mathematica/parametrischen Plot
Status vor 2d 3. Gonozal_IX
UAuslg/Log. Äquivl. vs. log. Schluss
^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]