Poprzednia

ⓘ Programowanie matematyczne




                                     

ⓘ Programowanie matematyczne

Programowanie matematyczne – problem optymalizacyjny postaci:

Maksymalizacja f x {\displaystyle fx} przy warunkach
  • g x ⩽ 0, {\displaystyle gx\leqslant 0,}
  • h x = 0. {\displaystyle hx=0.}
gdzie x {\displaystyle x} należy do X, {\displaystyle X,} X {\displaystyle X} jest podzbiorem przestrzeni R n, {\displaystyle \mathbb {R} ^{n},} zaś f, g {\displaystyle f,g} i h {\displaystyle h} są funkcjami zdefiniowanymi na tym podzbiorze.

Warunki 1. i 2. nazywane są warunkami ograniczającymi, natomiast funkcja f {\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 − f x {\displaystyle -fx} przy warunkach:
  • h x = 0. {\displaystyle hx=0.}
  • g x ⩾ 0, {\displaystyle gx\geqslant 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 zero-jedynkowe
  • programowanie sieciowe
  • programowanie liniowe
  • programowanie dynamiczne
  • programowanie całkowitoliczbowe
  • programowanie celowe
  • programowanie nieliniowe
  • programowanie kwadratowe
                                     

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

maksymalizacja: 1, 5 zł ⋅ x A + 1, 8 zł ⋅ x B {\displaystyle 1{,}5{\text{ zł }}\cdot x_{A}+1{,}8{\text{ zł }}\cdot x_{B}} 0, 5 ⋅ x A + 0, 6 ⋅ x B ⩽ 200 {\displaystyle 0{,}5\cdot x_{A}+0{,}6\cdot x_{B}\leqslant 200} 0, 45 ⋅ x A + 0, 5 ⋅ x B ⩽ 300 {\displaystyle 0{,}45\cdot x_{A}+0{,}5\cdot x_{B}\leqslant 300} x A ⩽ 200 {\displaystyle x_{A}\leqslant 200} x B ⩽ 200 {\displaystyle x_{B}\leqslant 200} x A ⩾ 0 {\displaystyle x_{A}\geqslant 0} i x B ⩾ 0 {\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ł.