Es liegt eine Instanz des WLP vor, für die Sie eine Lösung mit Hilfe des Add-Algorithmus bestimmen. Kann es sich dabei um eine optimale Lösung handeln? Begünden Sie!
Es kann sich um eine optimale Lösung handeln. Der Add-Algorithmus ist zwar eine Heuristik, dennoch kann die ausgegebene Lösung optimal sein. Es gibt dafür allerdings keine Garantie.
Ist es möglich, beliebige Instanzen des WLP mit Hilfe des primalen Simplex-Algorithmus zu lösen? Begru ̈nden Sie!
Aufgrund der vorhandenen Binärvariablen kann der Simplex-Algorithmus nicht eingesetzt werden.
Gegeben sei eine Instanz des WLP und eine feste Belegung der Variablen yi, i = 1, . . . , m. Können Sie eine kostenminimale Belegung der Variablen xij, i = 1,...,m, j = 1,...,n, angeben? Welchen Satz nutzen Sie dabei aus?
Wir können Satz 3.1 aus der Vorlesung nutzen: Für eine gegebene Belegung der Variablen yi, i = 1, . . . , m, existiert eine kostenminimale Zuordnung (d.h. eine Belegung der Variablen xij, i = 1,...,m, j = 1,...,n), in der jeder Kunde durch einen für ihn kostengünstigsten Standort voll beliefert wird.
Last changed2 years ago