Kürzeste Weg lineare Programmierung

Question

Ich bin an dem Punkt stecken zu maximieren d_t auf Seite 4 https://courses.engr.illinois.edu/cs498dl1/sp2015/notes/26-lp.pdf. Ich kann absolut nicht das Argument Autor folgen

Diese Entspannung Einschränkungen bedeuten, dass in jeder machbare Lösung, D_V atmost die kürzeste Wegstrecke von s nach v .So ist, etwas counterintuitively, sind wir richtig die Zielfunktion maximiert um den kürzesten Weg zu berechnen!

Wir suchen den kürzesten Weg, aber warum suchen wir für max d_t?

Answer 1

Stellen Sie sich den trivialen Fall des kürzesten Pfads zwischen zwei direkt verbundenen Scheitelpunkten s und t ohne andere Kanten oder Scheitelpunkte vor. Hier kocht die LP auf diese nach unten:

maximize d_t 
subject to d_s = 0 
      d_t − d_s ≤ l_st for every edge s -> t 

Der einzige Weg, d_t zu maximieren ist es auf dem kürzesten Weg zu setzen s-t - in diesem Fall die Kante zwischen den beiden. Dies liegt daran, dass die zweite Einschränkung d_t ≤ l_st jeden größeren Wert verbietet, d. H. Einen längeren Pfad von s zu t.

Nun kann diese Idee auf den allgemeinen Fall übertragen werden, wo s und t nicht Eckpunkten Nachbar: Denken Sie an die d Variablen wie kürzesten Wege zu allen benachbarten Eckpunkten t. Dann bestimmen die Beschränkungen, die mit d_t betroffen sind, welche dieser Kanten gewählt werden müssen, um den kürzesten Gesamtweg zu definieren. Es wird mit der Gleichheit zufrieden sein, während jeder höhere Wert für d_t mindestens eine dieser Einschränkungen verletzen wird.