unendlich viele Lösungen < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:44 Di 02.12.2008 | | Autor: | DerGraf |
| Aufgabe | Beantworten Sie folgende Fragen und begründen Sie Ihre Antwort:
a) Kann ein ganzzahliges lineares Programm unendlich viele Lösungen haben?
b)Kann ein ganzzahliges lineares Programm mit beschränktem zulässigen Bereich unendlich viele Lösungen haben?
c) Kann ein gemischt-ganzzahliges Programm mit beschränktem zulässigem Bereich unendlich viele Lösungen haben? |
Hallo,
Durch reines Überlegen würde ich sagen, dass a) und c) richtig sind und b) falsch ist. Nur wie zeige ich das?
Kann mir jemand weiterhelfen?
LG DerGraf
|
|
| |
|
> Beantworten Sie folgende Fragen und begründen Sie Ihre
> Antwort:
>
> a) Kann ein ganzzahliges lineares Programm unendlich viele
> Lösungen haben?
>
> b)Kann ein ganzzahliges lineares Programm mit beschränktem
> zulässigen Bereich unendlich viele Lösungen haben?
>
> c) Kann ein gemischt-ganzzahliges Programm mit beschränktem
> zulässigem Bereich unendlich viele Lösungen haben?
> Hallo,
>
> Durch reines Überlegen würde ich sagen, dass a) und c)
> richtig sind und b) falsch ist. Nur wie zeige ich das?
> Kann mir jemand weiterhelfen?
>
> LG DerGraf
Guten Abend !
Wenn ich die Frage jetzt richtig verstanden habe (zuerst
bin ich über den Begriff "lineares Programm" gestolpert,
der heute meist in ganz anderer Bedeutung als in der
"linearen Programmierung" verwendet wird), geht es
um Lösungen z.B. beim Simplex-Verfahren. Unendlich
viele Lösungen gibt es doch dann, wenn die Zielgerade
(bzw. -ebene oder Hyperebene) das Simplex nicht nur
an einer Ecke, sondern längs einer Kante (Facette)
berührt. Ob diese Kante dann endliche (positive) oder
unendliche Länge hat, ist dabei unerheblich.
So "vom Schiff aus" beurteilt würde ich also sagen,
dass das wohl in allen obigen Fällen möglich sein sollte,
d.h. alle Antworten wären "ja". Oder ist da doch noch
eine versteckte Schwierigkeit dabei ?
LG al-Chw.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:57 Di 02.12.2008 | | Autor: | DerGraf |
Bei a) und c) stimme ich dir zu.
In b) soll das Problem doch einen beschränkten zulässigen Bereich haben. Kann ich da ebenfalls eine unendlich lange Kante finden? Ich denke eher nein (zumal die Aufgabe sonst auch etwas merkwürdig wäre, wenn alle Antworten stimmen).
LG DerGraf
|
|
|
| |
|
> Bei a) und c) stimme ich dir zu.
>
> In b) soll das Problem doch einen beschränkten zulässigen
> Bereich haben. Kann ich da ebenfalls eine unendlich lange
> Kante finden?
Eine unendlich lange Kante ist gar nicht nötig,
denn jede Kante positiver Länge enthält unendlich
viele Punkte. Ob das bei Anwendungen von Wirt-
schaftsmathematik dann auch real eine Rolle
spielt, ist eine andere Frage ... 
> Ich denke eher nein (zumal die Aufgabe sonst
> auch etwas merkwürdig wäre, wenn alle Antworten stimmen).
(mit diesem nicht sehr wasserdichten Argument
hat der Aufgabensteller wohl schon gerechnet ...)
> LG DerGraf
gute Nacht ! al-Chw.
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 00:09 Mi 03.12.2008 | | Autor: | DerGraf |
Ich glaube, du übersiehst, dass das Problem ganzzahlig sein soll. Da kann es bei Kanten endlicher Länge auch bloß endlich viele ganzzahlige Punkte darauf geben. Damit bräuchte man bei b schon eine unendlich lange Kante.
Hab ich da jetzt einen Denkfehler drin oder du?
LG DerGraf
|
|
|
| |
|
> Ich glaube, du übersiehst, dass das Problem ganzzahlig sein
> soll. Da kann es bei Kanten endlicher Länge auch bloß
> endlich viele ganzzahlige Punkte darauf geben. Damit
> bräuchte man bei b schon eine unendlich lange Kante.
> Hab ich da jetzt einen Denkfehler drin oder du?
>
> LG DerGraf
Du hast natürlich Recht.
Jetzt habe ich endlich verstanden, was mit dem Begriff
"ganzzahliges lineares Programm" gemeint ist:
man sucht nur ganzzahlige Lösungs-n-Tupel, richtig ?
Und was genau ist dann ein "gemischt-ganzzahliges
Programm" in dieser Terminologie?
Gruß al-Chw.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:32 Mi 03.12.2008 | | Autor: | DerGraf |
Ja, ein ganzzahliges Programm hat nur ganze Variablen.
Ein gemischt-ganzzahliges Programm besitzt sowohl ganzzahlige als auch reelle Variablen.
Da wir uns nun über die Lösung einig geworden sind, bleibt nur noch die Frage: Wie formuliert man dies aber nun mathematisch?
Gruß DerGraf
|
|
|
| |
|
> Ja, ein ganzzahliges Programm hat nur ganze Variablen.
> Ein gemischt-ganzzahliges Programm besitzt sowohl
> ganzzahlige als auch reelle Variablen.
>
> Da wir uns nun über die Lösung einig geworden sind, bleibt
> nur noch die Frage: Wie formuliert man dies aber nun
> mathematisch?
> Gruß DerGraf
Das Wesentliche ist schon gesagt. Wenn es
unendlich viele Lösungspunkte (Gitterpunkte)
gibt, müssen diese auf einer Kante des erlaubten
Bereiches sein. Da diese Gitterpunkte einen
regelmässigen konstanten positiven Abstand
voneinander haben, ist dies nur möglich,
wenn diese Kante unendlich lang ist. Bei
beschränktem zulässigem Bereich ist dies
unmöglich.
good night Duke !
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:26 Mi 03.12.2008 | | Autor: | DerGraf |
Vielen Dank für deine Hilfe :)
LG DerGraf
|
|
|
|
