Problem
Ein Problem ist eine Kombination aus Eingabe, LR, ZB, ZS und Frage.
Optimierungs- und Entscheidungsproblem
Ein Optimierungsproblem ist ein Problem, bei dem nach einer gemäß ZS optimalen Lösung und/oder deren Zielfunktionswert gefragt wird. Ein Entscheidungsproblem ist ein Problem, bei dem die Frage nur mit ja oder nein beantwortet werden kann.
Probleminstanz
Eine Probleminstanz ist eine Belegung aller Daten der Eingabe mit Werten.
Algorithmus
Ein Algorithmus ist eine präzise und eindeutige Handlungsvorschrift, mittels derer eine Eingabe in eine Ausgabe transformiert wird.
Eckpunkt
Eckpunkte sind Schnittpunkte der (𝑛𝑛 − 1)-dimensionalen Unterräume von 𝑛𝑛 linear unabhängigen NB/NNB. Wir nennen einen Eckpunkt zulässig, wenn er eine zulässige Lösung repräsentiert.
Theorem 2.1.
Wenn es einen Eckpunkt und eine optimale Lösung gibt, dann gibt es mindestens einen optimalen Eckpunkt.
Satz 2.1.
Für das Verhältnis von (benachbarten) Basen und (benachbarten) Eckpunkten gilt:
• Zu zwei benachbarten Eckpunkten gibt es zwei benachbarte Basen.
• Zu einem Eckpunkt kann es mehrere Basen geben.
• Zwei benachbarte Basen, die zulässigen Eckpunkten entsprechen, entsprechen entweder demselben Eckpunkt oder zwei benachbarten Eckpunkten.
Theorem 2.2.
Wenn es einen Eckpunkt gibt, der eine optimale Lösung darstellt, dann hat jeder Eckpunkt, der keine optimale Lösung darstellt, einen benachbarten Eckpunkt, der besser ist.
Theorem 2.3.
Wenn das LP nicht (primal) degeneriert ist, ermittelt der (primale) Simplex-Algorithmus in der oben dargestellten Form eine optimale Lösung oder bestimmt korrekt, dass das LP unbeschränkt ist.
Satz 3.1.(WLP)
Für eine gegebene Belegung der Variablen 𝑦𝑖, 𝑖 = 1, … , 𝑚, existiert eine kostenminimale Zuordnung (d.h. eine Belegung der Variablen 𝑥𝑖, 𝑖 = 1, … , 𝑚, 𝑗 = 1, … , 𝑛), in der jeder Kunde durch einen für ihn kostengünstigsten Standort voll beliefert wird.
Graph
Weg
Ablaufplanungsproblem
Last changed3 months ago
