Lin. Optimier. - Eindeutigkeit < Optimierung < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:56 So 26.08.2012 | | Autor: | Fin_H |
| Aufgabe | Gegeben sei die folgende diskrete Optimierungsaufgabe:
Gesucht wird [mm] x\in\IZ^{n} [/mm] mit minimalem
[mm] \summe_{i=1}^{n}x_{i} [/mm] so, dass die Ungleichungen
[mm] x_{i}\ge0 [/mm] (für i=1..n)
sowie
[mm] \summe_{i\in T}x_{i}-\summe_{i\in \{1..n\}-T}x_{i}>0 [/mm] (gewisse [mm] T\subseteq\{1..n\})
[/mm]
und
[mm] \summe_{i\in T}x_{i}-\summe_{i\in \{1..n\}-T}x_{i}=0 [/mm] (gewisse [mm] T\subseteq\{1..n\})
[/mm]
erfüllt sind.
Dabei komme für jede Teilmenge [mm] T\subseteq\{1..n\} [/mm] oder dessen Komplement [mm] \{1..n\}-T [/mm] eine Ungleichung oder Gleichung der oben genannten Formen vor.
Weiter sei bekannt, dass eine Lösung der Optimierungsaufgabe existiert.
Zu prüfen ist, ob diese eindeutig bestimmt sein muss (Gegenbeispiel oder Beweis). |
Hallo allerseits!
Ich interessiere mich für die Lösung dieser Optimierungsaufgabe, habe aber selbst kaum Erfahrungen mit Aufgaben der diskreten Mathematik. Kennt jemand vielleicht Eindeutigkeitssätze für Optimierungsaufgaben dieses Typs? Es handelt sich ja um ganzzahlige Koeffizienten, da habe ich die Hoffnung, dass es sich um ein Standardproblem handelt. Ich habe sehr viele Beispiele mit dem Rechner geprüft, ohne ein Gegenbeispiel zu finden, deshalb vermute ich Eindeutigkeit. Bin dankbar für jede Idee!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:41 Mo 27.08.2012 | | Autor: | Stoecki |
> Gegeben sei die folgende diskrete Optimierungsaufgabe:
> Gesucht wird [mm]x\in\IZ^{n}[/mm] mit minimalem
> [mm]\summe_{i=1}^{n}x_{i}[/mm] so, dass die Ungleichungen
> [mm]x_{i}\ge0[/mm] (für i=1..n)
> sowie
> [mm]\summe_{i\in T}x_{i}-\summe_{i\in \{1..n\}-T}x_{i}>0[/mm]
> (gewisse [mm]T\subseteq\{1..n\})[/mm]
Frage: sicher, dass es hier > 0 und [mm] \ge [/mm] 0 heißt? andernfalls würde automatisch [mm] \ge [/mm] 1 gelten.
> und
> [mm]\summe_{i\in T}x_{i}-\summe_{i\in \{1..n\}-T}x_{i}=0[/mm]
> (gewisse [mm]T\subseteq\{1..n\})[/mm]
> erfüllt sind.
> Dabei komme für jede Teilmenge [mm]T\subseteq\{1..n\}[/mm] oder
> dessen Komplement [mm]\{1..n\}-T[/mm] eine Ungleichung oder
> Gleichung der oben genannten Formen vor.
> Weiter sei bekannt, dass eine Lösung der
> Optimierungsaufgabe existiert.
> Zu prüfen ist, ob diese eindeutig bestimmt sein muss
> (Gegenbeispiel oder Beweis).
> Hallo allerseits!
>
> Ich interessiere mich für die Lösung dieser
> Optimierungsaufgabe, habe aber selbst kaum Erfahrungen mit
> Aufgaben der diskreten Mathematik. Kennt jemand vielleicht
> Eindeutigkeitssätze für Optimierungsaufgaben dieses Typs?
> Es handelt sich ja um ganzzahlige Koeffizienten, da habe
> ich die Hoffnung, dass es sich um ein Standardproblem
> handelt. Ich habe sehr viele Beispiele mit dem Rechner
> geprüft, ohne ein Gegenbeispiel zu finden, deshalb vermute
> ich Eindeutigkeit. Bin dankbar für jede Idee!
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
ich bin mir ziemlich sicher, dass es nicht eindeutig sein muss. alleine deshalb schon, da du extrem viele möglichkeiten hast T zu wählen. wählst du T so, dass bestimmte variablengruppen gleichbehandelt werden können verlierst du ziemlich sicher die eindeutigkeit. konstruier mal ein gegenbeispiel bei dem zwei variablen in allen [mm] T_i [/mm] enthalten sind und die eine im optimalfall nicht gleich der anderen ist.
andere möglichkeit um das zu konstruieren wäre zu versuchen die variablen ein wenig zu shiften. sei [mm] x_1 [/mm] immer in T und [mm] x_2 [/mm] immer in {1,...,n} \ T, dann könntest du die gegeineinander ausspielen: sei X:= [mm] (x_1,x_2,...,x_n) [/mm] optimal, dann ist auch [mm] (x_1 [/mm] + [mm] 1,x_2 [/mm] -1 [mm] ,...,x_n) [/mm] optimal.
gruß bernhard
gruß bernhard
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:16 Di 28.08.2012 | | Autor: | Fin_H |
Vielen Dank für Deine Antwort! Die Ungleichheitszeichen sind tatsächlich richtig angegeben. Ich habe auch gedacht, es müsse ein Gegenbeispiel geben. Habe mit dem Rechner vermutlich alle Beispiel bis n=7 durchprobiert und viele mit mehr Variablen. Allerdings gab es hier einfach kein Gegenbeispiel. Habe auch Tage damit verbracht, per Hand ein Gegenbeispiel zu konstruieren, aber leider erfolglos. Bin dabei sogar ähnlich vorgegangen (Stichwort "gegeneinander ausspielen" von zwei Variablen). Mittlerweile glaube ich an die Richtigkeit der Aussage
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:39 Di 28.08.2012 | | Autor: | Stoecki |
ich habe noch einmal zwei kurze rückfragen zur aufgabe
1. müssen alle T aus der potenzmenge in die restriktionen oder nur eine (beliebige) teilmenge?
2. falls nein (also falls alle teilmengen genommen werden mussten) was war die optimallösung für n=1,2,3,...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:16 Mi 29.08.2012 | | Autor: | Fin_H |
Es kommen nicht alle T vor, sonst gäbe es gar keine Lösung. Beispielsweise kommt für [mm] T=\emptyset [/mm] eine Ungleichung heraus, die keine Lösungen besitzt (in den natürlichen Zahlen)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:04 Fr 31.08.2012 | | Autor: | Stoecki |
ich mache mal aus dem einen T ein S, damit klar ist, dass es verschiedene T sind (andernfalls ist das problem so eh nicht lösbar
$ [mm] \summe_{i\in S}x_{i}-\summe_{i\in \{1..n\}-S}x_{i}>0 [/mm] $ (gewisse $ [mm] S\subseteq\{1..n\}) [/mm] $
$ [mm] \summe_{i\in T}x_{i}-\summe_{i\in \{1..n\}-T}x_{i}=0 [/mm] $ (gewisse $ [mm] T\subseteq\{1..n\}) [/mm] $
n=4
wähle S= [mm] {x_1, x_2, x_3, x_4}
[/mm]
und T = [mm] {x_1, x_2}
[/mm]
das sollte ein gegenbeispiel liefern
gruß bernhard
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:53 Fr 31.08.2012 | | Autor: | wieschoo |
> ich mache mal aus dem einen T ein S, damit klar ist, dass
> es verschiedene T sind (andernfalls ist das problem so eh
> nicht lösbar
>
> [mm]\summe_{i\in S}x_{i}-\summe_{i\in \{1..n\}-S}x_{i}>0[/mm]
> (gewisse [mm]S\subseteq\{1..n\})[/mm]
> [mm]\summe_{i\in T}x_{i}-\summe_{i\in \{1..n\}-T}x_{i}=0[/mm]
> (gewisse [mm]T\subseteq\{1..n\})[/mm]
>
> n=4
> wähle S= [mm]{x_1, x_2, x_3, x_4}[/mm]
> und T = [mm]{x_1, x_2}[/mm]
>
> das sollte ein gegenbeispiel liefern
>
Das verstehe ich nicht so ganz. Die beiden Bedingungen
> [mm]\summe_{i\in S}x_{i}-\summe_{i\in \{1..n\}-S}x_{i}>0[/mm]
> (gewisse [mm]S\subseteq\{1..n\})[/mm]
> [mm]\summe_{i\in T}x_{i}-\summe_{i\in \{1..n\}-T}x_{i}=0[/mm]
> (gewisse [mm]T\subseteq\{1..n\})[/mm]
gelten für T und S oder deren Komplement. Wenn
[mm]\summe_{i\in T}x_{i}-\summe_{i\in \{1..n\}-T}x_{i}=0[/mm]
nicht für ein [mm]T\subseteq\{1..n\}[/mm] gilt, dann sollte es für [mm]T^\complement[/mm] gelten. Für [mm] $x_1=x_3$ [/mm] und [mm] $x_2=x_4$ [/mm] sehe ich da keinen Widerspruch.
Stehe ich auf dem Schlauch?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:07 Mi 29.08.2012 | | Autor: | wieschoo |
Ich sende es mal ab, obwohl es noch nicht ganz fertig ist. Ein Fall muss noch betrachtet werden.
---------------------------------------------------------------------------
Moin,
Die Idee ist wahrscheinlich die Summen geschickt zu bestücken. Für einen Beweis per Widerspruch (x ungleich y) macht es wenig Sinn die Koordinaten der Vektoren, in denen diese sich unterscheiden in eine Summe zu platzieren, wobei am Ende die sich in der Summe schon wegheben. Man muss da also irgendwie trennen.
ich würde es so versuchen:
Seien [mm]x,y\in\IZ^n[/mm] mit [mm]x_i,y_i\geq 0[/mm] und [mm]\sum_{i=1}^nx_i=\sum_{i=1}^ny_i[/mm] minimal unter den gegeben Bedingungen.
Annahme: [mm]x\neq y[/mm].
Aus [mm]T=\emptyset[/mm] folgt [mm]-\sum_{1\leq k\leq n}x_k=0[/mm] also [mm]x_k=0[/mm] für alle k und analog auch [mm]y_k=0[/mm] für alle k. Widerspruch!
Aus [mm]T=\{1,\ldots,n\}[/mm] folgt aus [mm]\sum_{1\leq k\leq n}x_k=0[/mm] wieder [mm]x_k=0[/mm] für alle k und analog auch [mm]y_k=0[/mm] für alle k. Widerspruch!
Wir können also annehmen, dass [mm]\sum_{1\leq k\leq n}x_k>0[/mm] und [mm]\sum_{1\leq k\leq n}y_k>0[/mm] gilt. Wegen der Annahme unterscheidet sich mindestens ein Eintrag.
Wir betrachten die folgenden Mengen
[mm]T_1:=\{i\; |\; x_i>y_i\}[/mm]
[mm]T_2:=\{i\; |\; x_i
[mm]T_3:=\{i\; |\; x_i=y_i\}[/mm]
Dabei ist
[mm]\sum_{k\in T_1}x_k=\sum_{k\in T_1}y_k+\delta_1[/mm]
und
[mm]\sum_{k\in T_2}x_k=\sum_{k\in T_2}y_k-\delta_2[/mm]
für [mm]\delta_1,\delta_2\in \IN\setminus \{0\}[/mm]
und setzen [mm]T:=T_1\cup T_3[/mm]. Betrachte nun
[mm]\sum_{k\in T_1\cup T_3}x_k-\sum_{k\in T_2}x_k=\sum_{k\in T_3}y_k+\sum_{k\in T_1}x_k-\sum_{k\in T_2}x_k=\sum_{k\in T_3}y_k+\sum_{k\in T_1}y_k+\delta_1-\left(\sum_{k\in T_2}y_k-\delta_2\right)[/mm] mit [mm]\delta_1,\delta_2\in \IN\setminus \{0\}[/mm]
Nun haben wir
[mm]\sum_{k\in T_1 \cup T_2 \cup T_3}x_k=2\sum_{k\in T_2}x_k+\left(\sum_{k\in T_1\cup T_3}x_k-\sum_{k\in T_2}x_k\right)=2\sum_{k\in T_2}x_k+\left(\sum_{k\in T_3}y_k+\sum_{k\in T_1}y_k+\delta_1-\sum_{k\in T_2}y_k+\delta_2\right)[/mm]
[mm]=2\sum_{k\in T_2}x_k+\left(\sum_{k\in T_3}y_k+\sum_{k\in T_1}y_k-\sum_{k\in T_2}y_k+\delta_1+\delta_2\right)=2\sum_{k\in T_2}x_k+\left(\sum_{k\in T_3}y_k+\sum_{k\in T_1}y_k+\sum_{k\in T_2}y_k+\delta_1+\delta_2-2\sum_{k\in T_2}y_k\right)[/mm]
[mm]=2\sum_{k\in T_2}x_k+\left(\sum_{k\in T_1 \cup T_2 \cup T_3}x_k+\delta_1+\delta_2-2\sum_{k\in T_2}y_k\right)[/mm]
ziehen wir nun [mm]\sum_{k\in T_1 \cup T_2 \cup T_3}x_k[/mm] auf beiden Seiten ab, so erhalten wir
[mm]0=2\sum_{k\in T_2}(x_k-y_k)+\delta_1+\delta_2 \Rightarrow \delta_1=\delta_2[/mm]
Also mit [mm]0<\delta_1+\delta_2=:\delta[/mm] auch
[mm]\sum_{k\in T_1\cup T_3}x_k-\sum_{k\in T_2}x_k=\sum_{k\in T_1\cup T_3}y_k-\sum_{k\in T_2}y_k+\delta[/mm]
Damit erhalten wir für den einen Fall =0
[mm]0=\sum_{k\in T_1\cup T_3}x_k-\sum_{k\in T_2}x_k=\sum_{k\in T_1\cup T_3}y_k-\sum_{k\in T_2}y_k+\delta [/mm]
also
[mm]0=\sum_{k\in T_1\cup T_3}x_k-\sum_{k\in T_1\cup T_3}y_k-\sum_{k\in T_2}x_k+\sum_{k\in T_2}y_k-\delta [/mm]
[mm]0=\sum_{k\in T_1\cup T_3}(x_k-y_k)-\sum_{k\in T_2}(x_k+y_k)-\delta [/mm]
[mm]\sum_{k\in T_2}(x_k-y_k)=\sum_{k\in T_1\cup T_3}(x_k-y_k)-\sum_{k\in T_2}(x_k+y_k)-\delta +\sum_{k\in T_2}(x_k-y_k)[/mm]
[mm]\sum_{k\in T_2}(x_k-y_k)=\sum_{k\in T_1\cup T_2 \cup T_3}(x_k-y_k)-\sum_{k\in T_2}(x_k+y_k)-\delta[/mm]
[mm]\sum_{k\in T_2}(x_k-y_k)+\sum_{k\in T_2}(x_k+y_k)+\delta=\sum_{k\in T_1\cup T_2 \cup T_3}(x_k-y_k)[/mm]
[mm]0<2\sum_{k\in T_2}x_k+\delta=\sum_{k\in T_1\cup T_2 \cup T_3}(x_k-y_k)\Rightarrow \sum x_k \neq\sum y_k[/mm]
Widerspruch!
Das wäre ja nur der eine Teil.
(hoffentlich ohne gravierende Rechenfehler)
edit: peinlichen Rechtschreibfehler im Titel korrigiert.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:13 Mi 29.08.2012 | | Autor: | Fin_H |
Vielen Dank für die Hilfe! Ich kann Deine Rechnung nachvollziehen. Schade, dass die Rechnung bisher nur einen Fall ("=0") erschlägt.
|
|
|
| |
|
Hi,
> Vielen Dank für die Hilfe! Ich kann Deine Rechnung
> nachvollziehen.
> Schade, dass die Rechnung bisher nur einen
> Fall ("=0") erschlägt.
Immerhin muss man nicht noch eine Fallunterscheidung in Bezug auf
[mm]T[/mm] oder [mm]T^\complement[/mm] machen.
Der obige Fall ist nun [mm]\sum_{T}-\sum_{T^\complement}=0[/mm]. Multipliziert man mit -1. Hat man auch den Fall [mm]\sum_{T^\complement}-\sum_{T}=0[/mm].
Du schriebst ja, dass die Ungleichung entweder für T oder das Komplement von T gelte.
Ich sehe leider auch noch nicht, ob der Weg für >0 funktioniert. Allerdings bin ich mir recht sicher, dass dies die einzig vernünftige Aufteilung von [mm]T_1, T_2, T_3[/mm] ist.
Im übrigen eine sehr interessante Aufgabe!
Grüße
wieschoo
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:21 So 02.09.2012 | | Autor: | wieschoo |
Der Weg
geht auch im anderen Fall:
------------------------------------------------
Damit erhalten wir für den einen Fall >0
[mm] 0<\sum_{k\in T_1\cup T_3}x_k-\sum_{k\in T_2}x_k=\sum_{k\in T_1\cup T_3}y_k-\sum_{k\in T_2}y_k+\delta [/mm]
also (trotzdem)
[mm] 0=\sum_{k\in T_1\cup T_3}x_k-\sum_{k\in T_1\cup T_3}y_k-\sum_{k\in T_2}x_k+\sum_{k\in T_2}y_k-\delta [/mm]
gruß
wieschoo
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:04 Di 04.09.2012 | | Autor: | Fin_H |
Habe leider in der ursprünglichen Rechnung einen Vorzeichenfehler gefunden. Zweite Zeile nach dem letzten "Also". Hier muss es [mm] -y_k [/mm] heißen, nicht [mm] +y_k
[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:46 Mi 05.09.2012 | | Autor: | Fin_H |
Vielen Dank allen, die mitgeholfen haben! Die Antwort auf die Frage lautet: Es gibt NICHT in allen Fällen eine eindeutige Lösung. Beispielsweise kann man die Gleichungen so wählen, dass das Tupel (11,9,6,6,4,4,4,2,1) Lösung ist. Dann ist es auch minimale Lösung, allerdings ebenso das Tupel (11,9,6,6,4,4,4,1,2).
|
|
|
|
