Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Binary Programming (Definition) noch nicht klar
Hallo,
im inoffiziellen BFS-Skript steht auf PDF-Seite 29 die Definition von Binary Programming:
BP := {<A,b> |A ist eine m × n-Matrix mit ganzzahligen Einträgen, b ist ein Vektor mit m
ganzzahligen Einträgen und es gibt einen 0-1-Vektor x ∈ {0, 1}^n mit A · x ≤ b}
Wie ich es verstehe:
Matrix A und Vektor b stellen m viele lineare Ungleichungen der Form 2x1 - 5x3 <= -4 etc.
Und nun wählt man quasi über x aus, welche Spalten (Wenn man die Ungleichungen untereinander schreibt) man “dabei haben” will und welche nicht.
Was bringt es nun einen solchen Vektor gefunden zu haben? Wie kommt man davon auf die lineare Programmierung die man aus Mathe C3 kennt?
An sich sind hier die Variablen doch auf {0, 1} beschränkt und es wird nur verlangt, dass die Bedingungen (Ungleichungen) eingehalten werden.
Inwiefern löst die Definition ein Optimierungsproblem?
Freundliche Grüße, Tobi
Meines Verständnisses nach, bleibt es ein Optimierungsproblem, insofern man jetzt nicht mehr sich Gedanken macht über Fragen wie “Wie viel Holz und wie viel Eisen soll ich Kaufen?” sondern “wie viele Menschen (eine Bekanterweise nicht-teilbare Ressource) soll ich für Holz- und Eisenabbau einsetzen?”.
Aber ansonsten beantwortest du die meisten deiner Fragen:
- Der Sinn ist zu wissen mit welchen Spalten die Bedingungen der Form “21 + 50 + 4*0 + … <= -4” erfüllt bleibt, und im Kontext der Berechenbarkeit, ob eine solche Lösung existiert (Probleme bilden ja aus einem “Problemraum” auf wahr oder falsch ab).
- Binäre Lineare Programmierung ist einfach nur “normale” Lineare Programmierung, mit der Zusatzeinschränkung dass jede Komponente des Vektors entweder “0” oder “1” ist.
Ok, alles klar, danke!