Zulässiger Bereich

Zulässiger Bereich (auch zulässige Lösungsmenge, zulässige Menge; englisch Feasible region, feasible set) ist im Operations Research, der Optimierung und der mathematischen Modellierung die Menge aller möglichen Lösungen (Sätze von Variablenwerten), die alle Nebenbedingungen (Restriktionen) eines Problems erfüllen.

Der zulässige Bereich stellt den Unterraum dar, in dem nach der optimalen Lösung gesucht wird. Jede Lösung, die außerhalb dieses Bereichs liegt, ist unzulässig.

Definition und Abgrenzung

Der zulässige Bereich wird als Schnitt der Mengen gebildet, die durch jede einzelne Nebenbedingung des Problems definiert werden. Die Nebenbedingungen können in folgender Form vorliegen:

• Ungleichungen: Legen obere oder untere Schranken für die Werte von Variablen oder deren Kombinationen fest (z. B. „Der Verbrauch von Ressource A darf 100 Einheiten nicht überschreiten“, „Die produzierte Stückzahl muss mindestens 50 betragen“).
• Gleichungen: Erfordern die exakte Erfüllung einer Bedingung (z. B. „Das Gesamttransportvolumen muss genau 1000 Tonnen betragen“, „Die Bilanz der ein- und ausgehenden Ströme ist null“).
• Vorzeichenbedingungen für Variablen: Oft müssen Variablen nicht-negativ, ganzzahlig sein oder einer bestimmten diskreten Menge angehören.

Ein Punkt (oder ein Vektor von Variablenwerten) gehört genau dann zum zulässigen Bereich, wenn er alle diese Nebenbedingungen gleichzeitig erfüllt.

Geometrische Interpretation

Der zulässige Bereich hat oft eine anschauliche geometrische Interpretation, insbesondere bei Problemen mit einer geringen Anzahl von Variablen:

• Im zweidimensionalen Raum (2 Variablen): Jede lineare Nebenbedingungs-Ungleichung definiert eine Halbebene. Der zulässige Bereich ist der Schnitt dieser Halbebenen – ein konvexes Polygon (möglicherweise unbeschränkt oder leer).
• Im dreidimensionalen Raum (3 Variablen): Jede lineare Nebenbedingungs-Ungleichung definiert einen Halbraum. Der zulässige Bereich ist der Schnitt dieser Halbräume – ein konvexes Polyeder.
• Im mehrdimensionalen Raum: Ein durch lineare Nebenbedingungen definierter zulässiger Bereich ist ein konvexes Polytop.

Bei nichtlinearen Nebenbedingungen kann der zulässige Bereich eine komplexere Form haben und nicht-konvex sein.

Rolle in der Optimierung

Der zulässige Bereich spielt eine fundamentale Rolle in der Optimierung:

1. Definition des Suchraums: Die optimale Lösung eines Problems (sofern sie existiert) befindet sich immer innerhalb des zulässigen Bereichs oder an dessen Rand. Optimierungsalgorithmen suchen das Extremum der Zielfunktion genau in diesem Bereich.
2. Prüfung der Existenz von Lösungen: Wenn der zulässige Bereich eine leere Menge ist (d.h., die Nebenbedingungen widersprechen sich), dann hat das Problem keine zulässigen Lösungen und somit auch keine optimale Lösung.
3. Einfluss auf die optimale Lösung: Die Form und Größe des zulässigen Bereichs beeinflussen direkt die Möglichkeit, das Extremum der Zielfunktion zu erreichen, sowie den Wert dieses Extremums.

Eigenschaften des zulässigen Bereichs (in der linearen Programmierung)

Bei Problemen der linearen Programmierung (LP), bei denen alle Nebenbedingungen und die Zielfunktion linear sind, besitzt der zulässige Bereich wichtige Eigenschaften:

• Konvexität: Wenn zwei Punkte zum zulässigen Bereich gehören, dann gehört auch die gesamte Strecke, die diese beiden Punkte verbindet, zum zulässigen Bereich. Diese Eigenschaft garantiert, dass die optimale Lösung (sofern sie existiert und eindeutig ist) in einer der Ecken des Polyeders liegt, das den zulässigen Bereich bildet.
• Abgeschlossenheit: Der zulässige Bereich schließt seine Grenzen mit ein (aufgrund von nicht-strengen Ungleichungen ≤, ≥ und Gleichungen).

Der zulässige Bereich kann sein:

• Beschränkt: Er hat endliche Ausmaße.
• Unbeschränkt: Er erstreckt sich in eine oder mehrere Richtungen ins Unendliche.
• Leer: Er enthält keinen einzigen Punkt.

Siehe auch

• Operations Research
• Optimierung
• Mathematisches Modell
• Nebenbedingung
• Zulässige Lösung
• Optimale Lösung
• Zielfunktion
• Lineare Optimierung
• Konvexe Menge

Literatur

• Вентцель Е. С. Исследование операций: задачи, принципы, методология. — М.: Наука, 1988.
• Акоф Р., Сасиени М. Основы исследования операций. — М.: Мир, 1971.
• Taha, Hamdy A. Operations Research: An Introduction. — Pearson. (10th ed., 2017)
• Hillier, Frederick S.; Lieberman, Gerald J. Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021)