Ganzzahlige lineare Optimierung

Problemdefinition

Mathematische Formulierung

Ein ganzzahliges Programm (engl. integer program, IP) hat die gleiche Form wie ein lineares Programm (LP), mit dem Unterschied, dass die Variablen ganzzahlig sein müssen:

Dabei ist A eine reelle Matrix und b und c sind Vektoren passender Dimension. Die Bedingung ist komponentenweise zu verstehen, also als

für alle Zeilen i der Matrix A. Genauso bedeutet die Bedingung , dass alle Einträge des Vektors x nichtnegativ sein müssen. Gelten die Ganzzahligkeitsbedingungen nur für einen Teil der Variablen, spricht man auch von einem gemischt-ganzzahligen Programm (engl. mixed-integer program, MIP). Auch die Präzisierung ganzzahliges lineares Programm (engl. integer linear program, ILP) ist gebräuchlich. Wie auch in der linearen Optimierung gibt es mehrere äquivalente Formulierungen, die sich ineinander transformieren lassen (siehe Lineare Optimierung: Problemdefinition).

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Ganzzahlige lineare Optimierung aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren

Anbieterkennzeichnung