Programowanie matematyczne
Z Wikipedii
Programowanie matematyczne to problem optymalizacyjny postaci:
- Maksymalizacja f(x) przy warunkach
- g(x) ≤ 0
- h(x) = 0
- gdzie x należy do X, X jest podzbiorem przestrzeni Rn, zaś f, g i h są funkcjami zdefiniowanymi na tym podzbiorze.
Warunki 1. i 2. nazywane są warunkami ograniczającymi (por. warunek ograniczający decyzję), natomiast funkcja f to funkcja celu (por. kryterium oceny decyzji). Rozwiązania tego problemu nazywamy rozwiązaniami optymalnymi (por. decyzja optymalna).
Problem został zdefiniowany jako problem maksymalizacji, jednak można przedstawić problem równoważny:
- Minimalizacja −f(x) przy warunkach
- g(x) ≥ 0
- 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 liniowe
- programowanie całkowitoliczbowe
- programowanie zero-jedynkowe
- programowanie celowe
- programowanie kwadratowe
- programowanie nieliniowe
- programowanie dynamiczne
- programowanie sieciowe
Programowanie matematyczne znalazło szerokie zastosowanie w teorii decyzji, np. przy optymalizacji struktury kosztów produkcji.
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 xA i xB oznaczają odpowiednio ilość jednostek wyprodukowanych metodą A i B. Zysk można opisać funkcją: f(x) = 1,5 zł * xA + 1,8 zł * xB. Dziennie zużyjemy 0,5 * xA + 0,6 * xB jednostek kartonu i 0,45 * xA + 0,5 * xB jednostek folii. Zapisujemy warunki oraz funkcję celu:
- maksymalizacja: 1,5 zł * xA + 1,8 zł * xB
- 0,5 * xA + 0,6 * xB ≤ 200
- 0,45 * xA + 0,5 * xB ≤ 300
- xA ≤ 200
- xB ≤ 200
- xA ≥ 0 i xB ≥ 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ł.
