Linjärprogrammeringens fundamentalsats

Från Wikipedia
Hoppa till navigering Hoppa till sök

Linjärprogrammeringens fundamentalsats säger att om det tillåtna området till ett linjärprogrammeringsproblem (som begränsas av bivillkoren) är begränsat men icke-tomt kommer optimallösningen att antas i minst en extrempunkt (dvs ett hörn).

Satsen är mycket användbar vid utformning av lösningsalgoritmer eftersom den innebär att endast extrempunkter i den tillåtna mängden behöver avsökas. Detta faktum används till exempel av simplexmetoden.