| |
| Autor |
  Beweis eines Farkas Lemma |
|
lochi
Senior 
Dabei seit: 19.08.2002
Mitteilungen: 1484
Wohnort: Allgäu
 |  Themenstart: 2004-02-14
|
Hallo zusammen,
ich möchte folgende Variante eines Farkas Lemma per Induktion über die Spalten von A mittels Fourier-Motzkin-Elimination beweisen:
\frame Ein lineares Ungleichungssystem A|x<=b hat eine Lösung x genau dann,
wenn es keinen Vektor y gibt mit y >= 0 und y^T|A=0 und y^T|b<0
Der Induktionsanfang für eine einspaltige Matrix A ist klar. Beim Induktionsschritt von n-1 Spalten auf n Spalten bin ich bisher so weit gekommen.
Sei A\el\IR^(m\cross n) und b\el\IR^m. Dann hat A|x<=b genau dann eine
Lösung, wenn A'|x<=b' eine Lösung hat, wobei A' die Matrix ist, die
man aus A erhält, wenn man die Zeilen nach der letzten Spalte
sortiert, wobei zuerst die positiven Einträge, dann die negativen und
zum Schluss die Nullen kommen. b' ist der Vektor, den man aus b
erhält, wenn man dessen Elemente genau so vertauscht wie die Zeilen
von A in A' vertauscht sind.
Sei \a die Zahl der positiven Einträge in der n-ten Spalte von A',
\b die der negativen und \g die der Nullen. Und a_ij bezeichne den
Eintrag von A' an Zeile i und Spalte j.
Dann kann man die Ungleichungen i=1,..\a so schreiben
x_n <= (1/a_in)|(b_i-sum(a_ik|x_k,k=1,n-1))
Entsprechend für j=\a+1,...,\a+\b:
x_n >= (1/a_jn)|(b_j-sum(a_jk|x_k,k=1,n-1))
Nach Fourier-Motzkin-Elimination ist A'|x<=b ist genau dann lösbar,
wenn (1/a_jn)|(b_j-sum(a_jk|x_k,k=1,n-1))<=(1/a_in)|(b_i-sum(a_ik|x_k,k=1,n-1))
für i=1,...,\a und j=\a+1,...,\a+\b eine Lösung in (x_1\,...\,x_(n-1)) hat.
Diese Ungleichungen lassen sich wiederum umschreiben und man erhält dann folgendes Ungleichungssystem:
A''|x<=b''
wobei
(A'')_ij=\fdef(a_(\p_1(\r)(i))\,n)|a_(\p_2(\r)(i))\,j)-a_(\p_2(\r(i))\,n)|a_(\p_1(\r(i))\,j),i<=\a|\b;a_(i-(\a|\b-\a-\b)),i>\a|\b)
\r eine Bijektion menge(1\,...\,\a*\b) -> menge(1\,...\,\a)\cross\menge(\a+1,...,\b)
\p_k die Projektion auf die k-te Komponente
(b'')_i=\fdef(a_(\p_1(\r(i))\,n)|b_(\p_2(\r(i)))-a_(\p_2(\r(i))\,n)|b_(\p_1(\r(i))),i<=\a|\b;b_(i-(\a|\b-\a-\b)),i>\a|\b)
Da A''\el\IR^(\a|\b+\g)\cross(n-1) ist, kann man darauf die Induktionsvoraussetzung anwenden. Damit erhält man dann:
(\exists x\el\IR^n A|x<=b)<=>(\not(\exists y\el\IR^(\a|\b+\g) y>=0 \and y^T|A''=0 \and y^T|b'' < 0))
Zum Abschluss des Induktionsschritts fehlt jetzt nur noch, dass ich beweise, dass gilt:
(\exists y\el\IR^(\a|\b+\g) y>=0 \and y^T|A''=0 \and y^T|b'' < 0)<=>(\exists y\el\IR^m y>=0 \and y^T|A'=0 \and y^T|b' < 0)
Mein Problem ist jetzt nur, dass ich keine Möglichkeit sehe, von dem einen y das andere zu konstruieren. Hat vielleicht jemand eine Idee, wie das gehen könnte (oder wo ich in meinem bisherigen Rechenweg etwas ändern sollte, damit es einfacher geht?)
Danke schon mal im Voraus,
Lochi
|
 Profil
|
Siah
Senior 
Dabei seit: 19.05.2002
Mitteilungen: 3539
Wohnort: Trier
 |  Beitrag No.1, eingetragen 2004-02-14
|
Hallo Lochi,
Ich kann Dir leider nicht wirklich bei deinem Problem weiterhelfen, aber wenn es Dir lediglich um einen Beweis geht, da gibts es einen schönen kurzen aus der Dualitätstheorie. Ich erzähle Dir wahrscheinlich nichts neues, aber man weiss ja nie.
beste Grüße
Siah
|
Profil
|
lochi
Senior
Dabei seit: 19.08.2002
Mitteilungen: 1484
Wohnort: Allgäu
| Beitrag No.2, vom Themenstarter, eingetragen 2004-02-14
|
Hallo Siah,
danke für den Hinweis, aber die Aufgabe lautet, dass man es eben genau mit diesem Verfahren beweisen soll.
Viele Grüße,
Lochi
|
Profil
|
Siah
Senior
Dabei seit: 19.05.2002
Mitteilungen: 3539
Wohnort: Trier
| Beitrag No.3, eingetragen 2004-02-14
|
Oh, dann entschuldige ich mich, da kann ich leider nichts beitragen.
beste Grüße
Siah
|
Profil
|
lochi
Senior
Dabei seit: 19.08.2002
Mitteilungen: 1484
Wohnort: Allgäu
| Beitrag No.4, vom Themenstarter, eingetragen 2004-02-15
|
Profil
|
Buri
Senior 
Dabei seit: 02.08.2003
Mitteilungen: 46890
Wohnort: Dresden
 | Beitrag No.5, eingetragen 2004-02-15
|
Hi lochi,
ich werfe mal die Bijektion und die Projektionen als unnötigen Ballast weg,
dann besagt die Induktionsvoraussetzung, dass es im Falle der
Lösbarkeit des eliminierten Ungleichungssystems Zahlen uij und vl gibt mit
sum(sum(u_ij*(a_in*a_jk-a_jn*a_ik),j=\a+1,\a+\b),i=1,\a)+sum(v_l*a_lk,l=\a+\b+1,m)=0
und sum(sum(u_ij*(a_in*b_j-a_jn*b_i),j=\a+1,\a+\b),i=1,\a)+sum(v_l*b_l,l=\a+\b+1,m)<0.
Dann kann man y_i=sum(u_ij*(-a_jn),j=\a+1,\a+\b) für i=1,...,\a,
y_j=sum(u_ij*a_in,i=1,\a) für j=\a+1,...,\a+\b und
y_l=v_l für l=\a+\b+1,...,n setzen.
Offensichtlich ist dann y >= 0 und yT A = 0 und yT b < 0 erfüllt.
Für die andere Richtung ist der Vektor y >= 0 vorgegeben, und man muß daraus die uij und vl konstruieren.
Aus der Gleichung yT A = 0 folgt, dass
sum(y_i*a_in,i=1,\a)+sum(y_j*a_jn,j=\a+1,\a+\b)=0
ist. In eine Tabelle mit \a Zeilen und \b Spalten kann man dann
nichtnegative Zahlen so eintragen, dass die Summe in der i\-ten Zeile
gleich y_i*a_in und die Summe in der (j-\a)\-ten Spalte gleich
-y_j*a_jn ist. Die notwendige und hinreichende Bedingung dafür,
dass das möglich ist, lautet, dass die vorgegebenen Zeilen\- und
Spaltensummen >= 0 sind und die Summe der Spaltensummen mit der Summe
der Zeilensummen übereinstimmt. Das ist hier erfüllt.
Dann kann man u_ij gleich dem Element in der i\-ten Zeile und
(j-\a)\-ten Zeile einer solchen Tabelle, dividiert durch - a_in*a_jn
setzen. Ferner wird v_l=y_l für alle l=\a+\b+1,...,n festgesetzt.
Dann haben die u_ij und v_l die geforderten Eigenschaften.
Schöne Aufgabe war das, hat mir Spaß gemacht!
Gruß Buri
[ Nachricht wurde editiert von Buri am 2004-02-15 17:51 ]
|
Profil
|
lochi
Senior
Dabei seit: 19.08.2002
Mitteilungen: 1484
Wohnort: Allgäu
| Beitrag No.6, vom Themenstarter, eingetragen 2004-02-15
|
Super! Danke Buri.
Nur noch so ne Frage: Wie kommst du auf die erste Konstruktion (der yi)? Die ist doch nicht vom Himmel gefallen, oder?
Ich hab immer versucht, ein Gleichungssystem zwischen y_i und u_ij aufzustellen. Sobald ich dann eine Lösung für y hatte, war die dann aber nicht mehr unabhängig von der betrachteten Spalte in A.
Ciao,
Andreas
|
Profil
|
Buri
Senior
Dabei seit: 02.08.2003
Mitteilungen: 46890
Wohnort: Dresden
| Beitrag No.7, eingetragen 2004-02-15
|
Hi lochi,
Die Formel für den ersten Teil fällt nicht vom Himmel, sie ergibt sich doch daraus, was man hat:
sum(u_ij*(a_in*a_jk-a_jn*a_ik))+sum(z_l*a_lk)=0.
Hier habe ich einfach die Beiträge zu aik und ajk gesammelt, und so habe ich meine yi.
Der zweite Teil ist mir schwerer gefallen, ich hatte plötzlich die Idee mit der Tabelle.
Hierfür ist die Begründung aber auch nicht ganz trivial, ich reiche sie hiermit nach:
Wir haben die Zeilensummen zi >= 0 und die Spaltensummen sj >= 0 gegeben.
Auf einer Geraden zeichnen wir eine Strecke der Länge
sum(z_i,i=1,\a)=sum(s_j,j=1,\b). Wir können sie einerseits in Intervalle
A_1\.,...,A_\a der Längen z_1\.,...,z_\a und andererseits in Intervalle
B_1\.,...,B_\b der Längen s_1\.,...,s_\b zerlegen.
Die Länge des Durchschnitts der Intervalle A_i und B_j
(sofern nichtleer), sonst Null, ergibt dann die vorgegebenen
Zeilen\- und Spaltensummen.
Gruß Buri
[ Nachricht wurde editiert von Buri am 2004-02-15 19:32 ]
|
Profil
|
lochi
Senior
Dabei seit: 19.08.2002
Mitteilungen: 1484
Wohnort: Allgäu
| Beitrag No.8, vom Themenstarter, eingetragen 2004-02-15
|
Hallo Buri,
ja, das mit den Beträgen hatte ich auch mal versucht, mich aber hoffnungslos verstrickt. Und die Begründung für die Tabelle ist einfach umwerfend einleuchtend wie genial.
Danke noch mal,
Lochi
|
Profil
|
lochi hat die Antworten auf ihre/seine Frage gesehen.
lochi hat selbst das Ok-Häkchen gesetzt. |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
