Materiały
- Wykład (dokładne omówienie slajdów i rozwiązanie zadań 1-34 oprócz 24; pobieżne podsumowanie od slajdu 35)
- Zadania
- Rozwiązania
Przebieg zajęć
1. Czym jest „Programowanie Matematyczne?”
Programowanie matematyczne jest metodą optymalizacji, w której konstruowany jest model matematyczny problemu. Cel oraz ograniczenia jakie muszą zostać uwzględnione zapisywane są za pomocą funkcji matematycznych. Spośród rozwiązań, które spełniają zadane ograniczenia, wybierane jest rozwiązanie najlepsze ze względu na funkcję celu. Zanim przejdziemy do ścisłej definicji problemu PM, zastanówmy się nad tym, jak za pomocą języka matematyki zamodelować problem z życia kognitywisty-badacza.
1.1 Przykład
Badacz musi zrealizować projekt obejmujący badania EEG i eyetrackerem na tych samych osobach. Średnie czasy trwania bodźców wynoszą odpowiednio 6 i 12 sekund. Badacz wie, że chce eksponować nie mniej niż 120 bodźców w trakcie obu badań jednej osoby. Wie ponadto, że całe badanie nie powinno trwać dłużej niż godzinę. Z założeń projektu wynika też, że powinien zebrać minimum 30 bodźców w badaniach EEG i 25 bodźców w trakcie badania eyetrackerem. Badacz chce zminimalizować koszt badania zakładając, że koszt jednego bodźca EEG to 10 złotych, a koszt jednego bodźca przy użyciu eyetrackera to 5 złotych .
1.2 Definicja problemu PM
Problem PM ma trzy główne składowe:
- Zmienne decyzyjne: $x_1, x_2, …, x_n$
- Funkcję celu: $z = f(x_1, x_2, …, x_n)$
- Ograniczenia: $g_i(x_1, x_2, …, x_n) \leq 0$
Wektory wartości zmiennych decyzyjnych $(x_1, x_2, …, x_n)$ odpowiadają rozwiązaniom problemu. Ograniczenia wyznaczają zbiór rozwiązań dopuszczalnych. Wśród rozwiązań dopuszczalnych poszukiwane jest takie, które maksymalizuje bądź minimalizuje wartość funkcji celu (w zależności od postawionego problemu).
Ogólna definicja problemu PM wygląda następująco:
max/min $z = f(x_1, x_2, …, x_n)$
przy ograniczeniach:
$g_1(x_1, x_2, …, x_n) \leq 0$
$g_2(x_1, x_2, …, x_n) \leq 0$
…
$g_m(x_1, x_2, …, x_n) \leq 0$
Problem programowania liniowego to problem w którym funkcja celu oraz wszystkie ograniczenia są funkcjami liniowymi. W postaci standardowej występują tylko warunki postaci $g_i(x_1, x_2, …, x_n) \leq 0$ oraz wszystkie zmienne są nieujemne.
2. Rodzaje problemów PM
- linowe vs nieliniowe
- dyskretne vs ciągłe
3. Interpretacja graficzna
Jedną z metod rozwiązywania problemów PM jest metoda graficzna. Jako ilustrację rozważymy poniższy problem:
max $z =3x + y$
p.o.
$x + y \leq 6$
$5x + y \leq 10$
$x, y \geq 0$