Programowanie matematyczne - Polski Serwis Naukowy

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 R, 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).

Decyzja optymalna to pojęcie z zakresu teorii decyzji, oznaczające taką decyzję, która jest decyzją dopuszczalną i jednocześnie jest najlepsza z punktu widzenia kryteriów oceny decyzji. Zbiór wszystkich takich decyzji nazywamy zbiorem decyzji optymalnych.

Teoria decyzji to wspólny obszar zainteresowań wielu różnych dziedzin nauki, obejmujący analizę i wspomaganie procesu podejmowania decyzji. Korzystają z niej i rozwijają ją: kognitywistyka, matematyka, statystyka, psychologia, socjologia, ekonomia, zarządzanie, filozofia, informatyka oraz medycyna.

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.

Programowanie dynamiczne jest techniką lub strategią projektowania algorytmów, stosowaną przeważnie do rozwiązywania zagadnień optymalizacyjnych. Jest alternatywą dla niektórych zagadnień rozwiązywanych za pomocą algorytmów zachłannych. Wynalazcą techniki jest amerykański matematyk Richard Bellman, uhonorowany za to odkrycie medalem IEEE (ang. medal of honour) w 1979 roku.

Kryterium oceny decyzji - to pojęcie z zakresu teorii decyzji, oznaczające przyporządkowanie każdej dopuszczalnej decyzji, ilościowej lub jakościowej oceny korzyści, wynikających z podjęcia takiej decyzji. Często kryterium oceny nazywane jest celem decyzji.

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?

Algorytm – w matematyce oraz informatyce skończony, uporządkowany ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego rodzaju zadań. Słowo "algorytm" pochodzi od starego angielskiego słowa algorism, oznaczającego wykonywanie działań przy pomocy liczb arabskich (w odróżnieniu od abacism - przy pomocy abakusa), które z kolei wzięło się od nazwiska, które nosił Muhammad ibn Musa al-Chuwarizmi (أبو عبد الله محمد بن موسى الخوارزمي), matematyk perski z IX wieku.

Warunek ograniczający decyzję to pojęcie z zakresu teorii decyzji. Warunek taki ogranicza przestrzeń decyzyjną do pewnego podzbioru decyzji. Po uwzględnieniu wszystkich warunków ograniczających otrzymujemy zbiór decyzji dopuszczalnych.

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:

Optymalizacja - metoda wyznaczania najlepszego (optymalnego) rozwiązania (poszukiwanie ekstremum funkcji) z punktu widzenia określonego kryterium (wskaźnika) jakości (np. kosztu, drogi, wydajności).

Programowaniem całkowitoliczbowym nazywamy programowanie liniowe, w którym na zmienne decyzyjne (niektóre lub wszystkie) nałożono dodatkowe warunki, że muszą przyjmować wartości całkowite dodatnie, ponieważ rozwiązania z wartościami ułamkowymi nie miałyby sensu rzeczywistego (np. określenia 2/3 osoby lub ¾ samochodu).

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ł.

Zobacz też

optymalizacja

teoria decyzji