lineær programmering

Lineær programmering er en matematisk optimeringsmetode, der anvendes på problemet at maksimere en lineær funktion, objektfunktionen, af flere variable under lineære bibetingelser, dvs. at de variable skal tilfredsstille et antal lineære uligheder.

En lineær ulighed kan fx beskrive et budget: Hvis man skal købe tre slags ting til priser \(p_1\), \(p_2\) og \(p_3\), så må man købe \(x_i\) af hver slags \(i\), således at \(x_1p_1 + x_2p_2+x_3p_3 \leq K\), hvor \(K\) er det budgetterede beløb. Objektfunktionen kan så være antallet af varer, der kan produceres, når hver vare kræver \(q_i\) ting af slags \(i\), dvs. at \(x_1q_1+x_2q_2+x_3q_3\) skal maksimeres inden for budgettet. Det praktiske problem opstår, når der er flere uligheder, der skal opfyldes samtidig.

Den mængde af \(x\)'er, der opfylder alle de givne uligheder, udgør et konvekst polyeder, og objektfunktionen må antage sit maksimum i et af dettes hjørner. Dette er idéen bag den oftest benyttede metode, Simplexmetoden, der på hensigtsmæssig måde gennemsøger hjørnerne og beregner objektfunktionen i udvalgte hjørner. Når værdien af denne funktion i et hjørne er større end eller lig med værdien i samtlige nabohjørner, har man fundet den optimale løsning.