Übung 7 Aufgabe 3

Moderator: Effiziente Graphenalgorithmen

Ambush
Mausschubser
Mausschubser
Beiträge: 68
Registriert: 1. Feb 2008 12:16

Übung 7 Aufgabe 3

Beitrag 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.

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Re: Übung 7 Aufgabe 3

Beitrag 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. :)
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

Re: Übung 7 Aufgabe 3

Beitrag 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.

Ambush
Mausschubser
Mausschubser
Beiträge: 68
Registriert: 1. Feb 2008 12:16

Re: Übung 7 Aufgabe 3

Beitrag von Ambush »

Ah gut. Jetzt wird mir alles klar. Dankeschön!

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Re: Übung 7 Aufgabe 3

Beitrag 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...
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Antworten

Zurück zu „Effiziente Graphenalgorithmen“