Programowanie matematyczne

Programowanie matematyczne – problem optymalizacyjny postaci:

Maksymalizacja $f(x)$ przy warunkach

1. $g(x)\leqslant 0,$
2. $h(x)=0.$

gdzie $x$ należy do $X,$ $X$ jest podzbiorem przestrzeni $\mathbb {R} ^{n},$ zaś $f,g$ i $h$ są funkcjami zdefiniowanymi na tym podzbiorze.

Warunki 1. i 2. nazywane są warunkami ograniczającymi, natomiast funkcja $f$ to funkcja celu; rozwiązania tego problemu nazywa się rozwiązaniami optymalnymi. W języku teorii decyzji, gdzie programowanie matematyczne znalazło szerokie zastosowanie (np. przy optymalizacji struktury kosztów produkcji), pojęciom tym odpowiadają kolejno: warunek ograniczający decyzję, kryterium oceny decyzji oraz decyzja optymalna.

Problem został zdefiniowany jako problem maksymalizacji, jednak można przedstawić problem równoważny:

Minimalizacja $-f(x)$ przy warunkach:

1. $g(x)\geqslant 0,$
2. $h(x)=0.$

Nie istnieje jeden efektywny algorytm rozwiązania problemu programowania matematycznego, dlatego problemy należące do różnych klas rozwiązywane są różnymi metodami. Oto najważniejsze z nich:

• programowanie całkowitoliczbowe
• programowanie celowe
• programowanie dynamiczne
• programowanie kwadratowe
• programowanie liniowe
• programowanie nieliniowe
• programowanie sieciowe
• programowanie zero-jedynkowe

Przykład

Do produkcji opakowań potrzebny jest karton i folia aluminiowa, przy czym dostępne są dwie metody produkcji (A i B). W metodzie A zużywamy 0,5 jednostki kartonu i 0,45 jednostki folii. W metodzie B zużywamy odpowiednio 0,6 i 0,5 jednostek produktów. Maksymalna dzienna produkcja jedną i drugą metodą wynosi 200 opakowań. Opakowanie wyprodukowane metodą A przynosi nam zysk w wysokości 1,5 zł, zaś metodą B – 1,8 zł. Jednocześnie jesteśmy w stanie dostarczyć dziennie do fabryki 200 jednostek kartonu i 300 jednostek folii. Jaki plan produkcji należy przyjąć, aby zysk z przedsięwzięcia był największy?

Formułujemy zadanie programowania matematycznego: Niech $x_{A}$ i $x_{B}$ oznaczają odpowiednio liczbę jednostek wyprodukowanych metodą A i B. Zysk można opisać funkcją: $f(x)=1{,}5{\text{ zł }}\cdot x_{A}+1{,}8{\text{ zł }}\cdot x_{B}.$ Dziennie zużyjemy $0{,}5\cdot x_{A}+0{,}6\cdot x_{B}$ jednostek kartonu i $0{,}45\cdot x_{A}+0{,}5\cdot x_{B}$ jednostek folii. Zapisujemy warunki oraz funkcję celu:

maksymalizacja: $1{,}5{\text{ zł }}\cdot x_{A}+1{,}8{\text{ zł }}\cdot x_{B}$

$0{,}5\cdot x_{A}+0{,}6\cdot x_{B}\leqslant 200$

$0{,}45\cdot x_{A}+0{,}5\cdot x_{B}\leqslant 300$

$x_{A}\leqslant 200$

$x_{B}\leqslant 200$

$x_{A}\geqslant 0$ i $x_{B}\geqslant 0$

Jednym z siedmiu rozwiązań optymalnych jest: należy wyprodukować 196 jednostek metodą A i 170 jednostek metodą B. Osiągniemy wtedy maksymalny zysk 600 zł.

Zobacz też

• optymalizacja
• teoria decyzji