Polyeder < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:18 Di 30.11.2004 | | Autor: | cremchen |
Halli hallo!
Und noch eine Aufgabe bei der ich leider überhaupt keinen Plan habe....
Die zwei Polyeder [mm] {\cal P}_{1}=\{x\in\IR^{n} : Ax\le{b}\} [/mm] und [mm] {\cal P}_{2}=\{x\in\IR^{n} : Cx\le{d}\} [/mm] seien nichtleer und disjunkt. Gesucht ist eine Hyperebene, die [mm] {\cal P}_{1} [/mm] und [mm] {\cal P}_{2} [/mm] strikt trennt, d.h. gesucht ist ein [mm] a\in\IR^{n} [/mm] und [mm] \alpha\in\IR, [/mm] so dass [mm] a^{T}x\ge\alpha \forall{x}\in{\cal P}_{1}, a^{T}x<\alpha \forall{x}\in{\cal P}_{2}.
[/mm]
Formulieren Sie dies als lineares Problem.
Ein Hinweis ist auch noch dabei:
Für a und [mm] \alpha [/mm] muß gelten: [mm] inf_{x\in{\cal P}_{1}}a^{T}x>\alpha>sup_{x\in{\cal P}_{2}}a^{T}x.
[/mm]
Vereinfachen Sie Infimum und Supremum mit Hilfe der LP-Dualität.
(Die LP-Dualität besagt:
Das zu dem primalen Problem
min [mm] c^{T}x
[/mm]
s.t. [mm] Ax\ge{b}
[/mm]
[mm] x\ge{0}
[/mm]
zugehörige duale Problem lautet:
max [mm] b^{T}y
[/mm]
s.t. [mm] A^{T}y\le{c}
[/mm]
[mm] y\ge{0} [/mm] )
Also ich habe so eine Umformung auch schonmal gemacht aber hier hat man doch gar keine solche Form gegeben.....
Ich weiß hier echt nicht wie ich rangehen soll!
Wäre dankbar für jede Hilfe die ich kriegen kann!
Liebe Grüße und schonmal ein ganz großes Danke
Ulrike
|
|
| |
|
Hallo cremchen,
versuch es mal so:
such die beiden Punkte auf den beiden Polyedern, die den geringsten Abstand von einander haben.
Diese Punkte haben eine Verbindungsstrecke und die mitten durch die Strecke gehende, darauf senkrecht stehende Hyperebene könnte eine sein, die deine (konvexen) Polyeder trennt.
Hugo
|
|
|
|
