Seite 1 von 1

Übung 7 Aufgabe 3

Verfasst: 16. Jan 2011 15:25
von Ambush
Hallo,

was bedeutet es, dass "der Zielfunktionswert ... nach unten beschränkt ist" ? was ist hier mit Zielfunktionswert gemeint? der Funktionswert von allen Zielknoten, also b(v) eines Zielknotens v? oder die Summe von allen cij*xij ? Ich dachte es wäre zweiteres, aber dann verstehe ich nicht wieso diese nach unten beschränkt ist. Diese soll doch minimiert werden. Gibt die untere Schranke dann an wieviel mindestens an Kosten entstehen muss?

Grüße
A.

Re: Übung 7 Aufgabe 3

Verfasst: 17. Jan 2011 18:37
von Stille
Hallo,

natürlich die Summe aller c_{ij} x_{ij}. Beschränktheit siehe z.B. http://de.wikipedia.org/wiki/Beschr%C3%A4nktheit oder O.Forster, Analysis I, S.67ff. :)

Re: Übung 7 Aufgabe 3

Verfasst: 17. Jan 2011 19:07
von MisterD123
eine untere schranke heißt einfach es gibt auch wirklich ein ergebnis. Beispiel: Zyklus mit in der summe negativem gewicht und unbeschränkter maximalkapazität. Da würde man offensichtlich keine optimallösung finden, weil man einfach beliebig viel fluss im kreis jagen kann und die lösung immer besser wird.

Re: Übung 7 Aufgabe 3

Verfasst: 17. Jan 2011 19:20
von Ambush
Ah gut. Jetzt wird mir alles klar. Dankeschön!

Re: Übung 7 Aufgabe 3

Verfasst: 17. Jan 2011 20:07
von Stille
MisterD123 hat geschrieben:eine untere schranke heißt einfach es gibt auch wirklich ein ergebnis. Beispiel: Zyklus mit in der summe negativem gewicht und unbeschränkter maximalkapazität. Da würde man offensichtlich keine optimallösung finden, weil man einfach beliebig viel fluss im kreis jagen kann und die lösung immer besser wird.
So ist es, sprich der Zielfunktionswert betrüge in diesem Fall \(-\infty\), was keiner unteren Schranke genügte.

Dasselbe im Max-Flow-Fall: hier nehmen wir an, dass es keinen s-t-Pfad unbeschränkter Kapazität gibt, denn sonst wäre der Zielfunktionswert nicht nach oben beschränkt. Mehr dazu morgen...