Programowanie matematyczne

Ten artykuł od 2010-12 wymaga zweryfikowania podanych informacji: nauk ścisłych nie można pozostawiać bez uźródłowienia. Należy podać wiarygodne źródła w formie przypisów bibliograficznych. Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte. Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary) Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu. Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

Programowanie matematyczne – problem optymalizacyjny postaci:

Maksymalizacja ${\displaystyle f(x)}$ przy warunkach

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

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

Warunki 1. i 2. nazywane są warunkami ograniczającymi, natomiast funkcja ${\displaystyle 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 ${\displaystyle -f(x)}$ przy warunkach:

1. ${\displaystyle g(x)\geqslant 0,}$
2. ${\displaystyle 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 ${\displaystyle x_{A}}$ i ${\displaystyle x_{B}}$ oznaczają odpowiednio liczbę jednostek wyprodukowanych metodą A i B. Zysk można opisać funkcją: ${\displaystyle f(x)=1{,}5{\text{ zł }}\cdot x_{A}+1{,}8{\text{ zł }}\cdot x_{B}.}$ Dziennie zużyjemy ${\displaystyle 0{,}5\cdot x_{A}+0{,}6\cdot x_{B}}$ jednostek kartonu i ${\displaystyle 0{,}45\cdot x_{A}+0{,}5\cdot x_{B}}$ jednostek folii. Zapisujemy warunki oraz funkcję celu:

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

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

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

${\displaystyle x_{A}\leqslant 200}$

${\displaystyle x_{B}\leqslant 200}$

${\displaystyle x_{A}\geqslant 0}$ i ${\displaystyle 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