ZAGADNIENIA DECYZYJNE
Osiągnięcie określonego celu zwykle wymaga zaangażowania pewnych środków pieniężnych, materialnych i czasu.
Te środki są ograniczone i należy nimi dysponować tak, aby w maksymalnym stopniu zrealizować wyznaczony cel.
Trzeba podjąć decyzje, które środki i w jakich ilościach należy zaangażować. Decyzji może być wiele.
Decyzja najlepsza z pkt widzenia przyjętego celu i przy uwzględnieniu istniejących ograniczeń, nazywa się DECYZJĄ OPTYMALNĄ (D_opt)
SYTUACJE DECYZYJNE
1. Ustalić taki plan produkcji uzyskanej z dostępnych czynników produkcji, przy którym przychód uzyskany ze sprzedaży wyrobów, będzie największy. 2. Ustalić taki plan rozwozu produktów, aby przy najniższym koszcie zaspokoić popyt odbiorców i wykorzystać podaż dostawców. 3. Ustalić taki harmonogram prac, aby stałe przedsięwzięcie zakończyć w najkrótszym czasie, przy zachowaniu pewnej kolejności wykonywanych czynności.
DECYZJE OPTYMALNE
Wyznaczanie D_opt ułatwią skonstruowane odpowiednio metody matematyczne. Problemy decyzyjne należy przedstawić w języku matematycznym i w tym modelu matematycznym wyznaczyć D_opt ze względu na przyjęte kryterium optymalizacyjne.
Metody wyznaczania D_opt należą do dziedziny zwanej BADANIAMI OPERACYJNYMI. Metody optymalizacji funkcji przy zadanych ograniczeniach nazywa się PROGRAMOWANIEM MATEMATYCZNYM (PM).
KONSTRUOWANIE MODELI MATEMATYCZNYCH
W typowych problemach decyzyjnych należy postępować wg podanych niżej reguł: 1. Określić zmienne decyzyjne. Będzie to ciąg zmiennych przyjmujących wartości liczbowe. 2. Zdefiniować ograniczenie określające decyzje w danych warunkach. Będzie to układ równań i nierówności. 3. Określić sposób porównania decyzji i wyboru spośród nich takiej, która najlepiej realizuje stawiany cel. Można osiągnąć to poprzez określenie funkcji celu, którą należy maksymalizować lub minimalizować w zależności od przyjętego kryterium optymalizacyjnego.
OGÓLNE SFORMUŁOWANIE ZADAŃ PM PRZY KRYTERIUM MAKSYMALNYM
x = (x₁, .., x_n1,  x_n + 1, …,  x_n) – decyzja
f(x₁ ,…, x_n) – funkcja celu
X – część wspólna dziedziny funkcji f oraz funkcji g₁,…, g_n
Zadanie PM z kryterium maksymalizacji zapisujemy:
f(x₁ ,…, x_n) -> max (1)
przy ograniczeniach, gdzie b₁ ,…, b_m to znane liczby :
g_i (x₁ ,…, x_n) ≤ b_i dla i = 1,…, m_1­ (2)
g_i (x₁ ,…, x_n) ≥ b_i dla i = m₁+1,…, m₂ (3)
g_i (x₁ ,…, x_n) = b_i dla i = m₂+1,…, m (4)
x_i ≥ dla i = 1,…,n (5)
Zadanie PM polega na znalezieniu wśród pkt x=(x₁ ,…, x_n) є X spełniających warunki (2) – (5) takiego pkt (być może wielu pkt) x_0­, w którym funkcja celu f osiąga największą wartość. Pkt x₀ nazywamy D_opt. Oznaczenia: D – podzbiór zbioru X taki, że dla każdego jego elementu spełnione są warunki ograniczające (2) - (5)
D_opt– podzbiór D taki, że dla każdego jego elementu x₀ zachodzi f(x) ≤ f(x₀). Zatem mamy relację: D_opt D X
ZADANIE PM Z KRYTERIUM MINIMALIZACJI
Elementy zbioru X nazywamy DECYZJAMI, X – zbiór decyzji. Elementy zbioru D nazywamy DECYZJAMI DOPUSZCZALNYMI, D – zbiór decyzji dopuszczalnych. Elementy zbioru D_opt nazywamy decyzjami optymalnymi, D_opt – zbiór decyzji optymalnych. Jeżeli D=Ø, to zadanie PM nazywamy SPRZECZNYM. Analogicznie określa się postać zadania PM z kryterium min, a mianowicie f(x) -> min przy warunkach ograniczających (2) – (5). Wówczas : D_opt={x₀ є D: $\bigwedge_{x \in D}^{}{f\left( x \right) \geq f(x_{0})}$}
ZMIANIA KRYTERIUM Z MIN NA MAX Ten przypadek można sprowadzić do problemu maksymalizacji funkcji g(x) = -f(x). Pkt x₀ w którym g(x₀) -> max jest również pkt, w którym f(x) -> min i f(x₀) = -g(x₀).
Zatem zagadnienie minimalizacji funkcji celu przy zadanych ograniczeniach sprowadza się do zagadnienia maksymalizacji funkcji celu. Zwykle bez komputera, D_opt nie da się wyznaczyć. Na szczęście jt duża biblioteka oprogramowania dla zadań PM.

ZWIĄZEK MIĘDZY PM I PROGRAMOWANIEM LINOWYM (PL)
W dalszych wykładach skupimy się na PL tzn. na optymalizacji funkcji przy liniowych ograniczeniach. Najbardziej znaną i pożyteczną metodą wyznaczania optymalnych decyzji w zagadnieniach liniowych jest metoda SYMPLEKS.
SFORMUŁOWANIE ZADANIA PROGRAMOWANIA LINIOWEGO
PM jt programowaniem liniowym, gdy funkcja celu f jt funkcją liniową i funkcje g_1­, g₂,…, g_m są liniowe, tzn. :
c₁x₁ + c₂x₂ + … + c_nx_n → max(min)
przy ograniczeniach:
a_i1x₁ + a_i2x₂ + … + a_inx_n  ≤ b_i dla i = 1,2, …, m₁
a_i1x₁ + a_i2x₂ + … + a_inx_n ≥  b_i dla i = m₁+1, …, m₂
a_i1x₁ + a_i2x₂ + … + a_inx_n = b_i dla i = m₂+1, …, n
x_i ≥ 0 dla i = 1,2, …, n x_{i ­}≤ 0 dla i = n₁+1, …., n₂
x_i є R dla i = n₁+1, …., n₂
Macierz:
A= [a_ij]=$\begin{bmatrix} a_{11} & a_{21} & \begin{matrix} \ldots & a_{1n} \\ \end{matrix} \\ a_{21} & a_{22} & \begin{matrix} \ldots & a_{2n} \\ \end{matrix} \\ \begin{matrix} \ldots \\ a_{m1} \\ \end{matrix} & \begin{matrix} \ldots \\ a_{m2} \\ \end{matrix} & \begin{matrix} \begin{matrix} \ldots \\ \ldots \\ \end{matrix} & \begin{matrix} \ldots \\ a_{\text{mn}} \\ \end{matrix} \\ \end{matrix} \\ \end{bmatrix}$ jt macierzą znaną. Również parametry c_i i= 1,2, … ,n oraz b_j j=1,2, …, n mają znane wartości liczbowe. Rozwiązanie zadania PL polega na znalezienie D_opt (${\dot{x}}_{1},{\dot{x}}_{2},\ldots,{\dot{x}}_{n}$) є D_opt, tzn.: $c_{1}{\dot{x}}_{1},c_{2}{\dot{x}}_{2},\ldots,c_{n}{\dot{x}}_{n} = \max{(min)}\ $
oraz spełnione są warunki ograniczające.
UKŁADANIE ZADAŃ DECYZYJNYCH (ZD)
Polega na „przetłumaczeniu” słownego, czasami dość swobodnego opisu sytuacji decyzyjnych na język matematyczny. Ogólne reguły formułowania ZD: - określenie zmiennych decyzyjnych jakie decydent ma wyznaczyć,
- sformułowanie warunków ograniczających jakie powinna spełniać decyzja dopuszczalna - sformułowanie celu decydenta, tj. ustalenie funkcji celu określonej na zmiennych decyzyjnych
OPTYMALNY WYBÓR ASORTYMENTU PRODUKCJI
Określić które wyroby i w jakich ilościach produkować aby nie przekroczyć posiadanych zasobów produkcji i zmaksymalizować przychód (lub zysk) z ich sprzedaży.
Posiadane dane:
n –lb wyborów produkowanych przez firmę
a_ij – zużycie i-tego środka produkcji na wytworzenie jednostki j-tego wyrobu i=1,…,r, j=1,…,n
b_i - posiadany zasób i-tego środka produkcji
c_j – cena lub zysk jednostkowy ze sprzedaży j-tego wyrobu
d_j – min ilośc j-tego wyrobu jaką trzeba wyprodukować
e_j- max ilośc j-tego wyrobu jaka można sprzedać
ZAPIS MATEMATYCZNY ASORTYMENTU PRODUKCJI
Niech x_i –wielkość produkcji wyrobu i, x₁ = 0;   x₂ ≥ 0;  x_n ≥ 0
Funkcja celu: f(x₁ ,…, x_n)= c₁x₁+….+c_nx_n -> max
Ograniczenia związane ze środkami produkcji:
$\begin{pmatrix} a_{11}x_{1} + \ a_{12}x_{2} + \ldots + \ a_{1n}x_{n} \leq b_{1} \\ a_{21}x_{1} + \ a_{22}x_{2} + \ldots + \ a_{2n}x_{n} \leq b_{2} \\ \ldots\text{..} \\ a_{r1}x_{1} + a_{r2}x_{2} + \ldots + \ a_{\text{rn}}x_{n} \leq b_{r} \\ \end{pmatrix}$
ograniczenia związane z popytem: d_j ≤ x_j ≤ e_j dla niektórych j.
PLAN PRODUKCJI
Plan produkcji, czyli decyzja co do wielkości produkcji każdego asortymentu: (x₁ ,…, x_n) jt rozwiązaniem dopuszczalnym, jeśli spełnia warunki ograniczające. Rozwiązanie optymalne będzie to (Lub będą te) spośród rozwiązań dopuszczalnych, dla którego (lub dla których) f-cja celu przyjmuje wartość max. D_opt wyznacza się metoda sympleks. Która będzie omówiona wkrótce po metodzie graficznej.
WARSTWICE
Graficzną metodę rozwiązywania zadań PL stosuje się wtedy gdy w zadaniu występują dwie zmienne decyzyjne. Wówczas łatwo wyznaczyć zbiór dopuszczalny D na płaszczyźnie. Posługując się warstwicami f-cji celu f można wyznaczyć pkt optymalny x₀ w którym f(x₀)=max (min) (o ile istnieje). Przypomnijmy pojęcie warstwicy f-cji f(x). Warstwicą f-cji f odpowiadają wartości z R nazywamy zbiór: Wz(f)={x Df: f(x)=z}.
Zbior Wz(f) jt zbiorem agrumentow f-cji f, dla których wartość f-cji f jt równa z.
WŁASNOŚCI PL
1. Jeżeli zbiór D jt niepusty i ograniczony, to zadanie PL posiada co najmniej jedną D_opt. 2. Jeżeli zbiór D_opt nie jt Ø, to przynajmniej jeden wierzchołek zbioru D należy do zbioru D_opt. 3. Jeżeli D_opt ≠ Ø albo funkcja celu jt funkcją nieograniczoną na zbiorze D, to zadanie PL nie posiada rozwiązania (jest zadaniem sprzecznym) 4. Zbiór D_opt decyzji dopuszczalnych jt zbiorem wypukłym, domkniętym, o skończonej lb wierzchołków (niekoniecznie ograniczony) 5. Zbiór D_opt jt również zbiorem wypukłym, domkniętym i o skończonej lb wierzchołków.
STANDARDOWA POSTAĆ ZADANIA PL
Zadanie programowania liniowego:
$\sum_{i = 1}^{n}{c_{i}x_{i}}$ -> max $\sum_{j = 1}^{n}{a_{\text{ij}} \leq b_{i}}$ dla i = 1,2, …, m₁
$\sum_{j = 1}^{n}{a_{\text{ij}} \geq b_{i}}$ dla i = m₁+1, …, m₂
$\sum_{j = 1}^{n}{a_{\text{ij}} = b_{i}}$ dla i = m₂+1, …, n
x_j≥0 dla j = 1, …, n
Wprowadzając dodatkowo m₁+m₂ zmiennych, warunki zawierające nierówność ≤ lub ≥ przejdą na warunki zawierające znak =. Pozwoli to przedstawić PL w postaci : $\sum_{i = 1}^{n + m_{1} + m_{2}}{c_{i}x_{i}}$ -> max
przy warunkach: $\sum_{j = 1}^{n + m_{1} + m_{2}}{a_{\text{ij}} = b_{i}}$ i=1, 2, …, n
x_j ≥ 0; j = 1,2,…, n+ m₁+ m₂
Ten zapis PL nazywa się standardową lub kanoniczną postacią programowania liniowego. W metodzie sympleks zadanie PL przedstawia się w postaci standardowej.
PRZEJŚCIE DO STANDARDOWEJ POSTACI
W zadaniu PL g_i (x) ≤ b_i , i = 1, …, m₁ oraz g_i (x) ≥ b_i , i = m₁+1, …, m₂ należy przekształcić ma równość g_i (x) = b_i przez wprowadzenie nieujemnych zmiennych dodatkowych. x_n + 1, x_n + 2, …, x_n + m;   x_{n + m1 + 1}, x_{n + m1 + 2}, …, x_{n + m1 + m2}
Zmienne dodatkowe zmienne dodatkowe
niedoboru nadmiaru
takich aby:g_i(x) + x_n + i = b_ix_n + i = b_i − g_i(x); i = 1,  …, m₁
g_i(x) − x_n + i = b_ix_n + i = g_i(x) − b_i i =  m₁ + 1, …, m₁ + m₂
PRZYKŁAD : PROCEDURA ITERACYJNA METODY SYMPLEKS
Metoda SYPMLEKS jt uniwersalną metodą rozwiązania PL. Jt procedurą iteracyjną. W każdym kroku: a) wyznacza dopuszczalne rozwiązanie bazowe; b) sprawdza czy jt ono rozwiązaniem optymalnym; c) jeśli nie jest to rozwiązanie optymalne, wskazuje jak przejść do następnego dopuszczalnego rozwiązanie bazowego, nie gorszego od poprzedniego.
Wyniki poszczególnych iteracji zapisuje się w kolejnych tablicach sympleksowych. Procedurę kończy się w momencie stwierdzenia, że aktualne rozwiązanie jt rozwiązaniem optymalnym.
ISTOTA METODY SYMPLEKS
Metoda sympleks pozwala wyznaczyć współrzędne wierzchołka zbioru dopuszczalnego D i sprawdzić, czy ten wierzchołek jt rozwiązaniem optymalnym.
Jeśli nie jt optymalny, rozpoczyna wędrówkę do następnego wierzchołka D, który jt rozwiązaniem zadani PL, nie gorszym od poprzedniego.
Po skończonej lb kroków, procedura kończy się znalezieniem optymalnego rozwiązania albo stwierdzeniem, że nie istnieje rozwiązanie, czyli że zadanie PL jt sprzeczne.
Wierzchołki zbioru dopuszczalnego D są bazowymi rozwiązaniami dopuszczalnymi.
ZADANIE PL
Zadanie PL w postaci standardowej (kanonicznej):
f(x) = c^′x → max (1)
przy warunkach : Ax = b (2) ; x ≥ 0 (3)
gdzie: A=$\begin{bmatrix} a_{11} & \ldots & a_{1n} \\ & \ldots & \\ a_{m1} & \ldots & a_{\text{mn}} \\ \end{bmatrix}$, b=$\begin{bmatrix} b_{1} \\ \ldots \\ b_{m} \\ \end{bmatrix}$, x=$\begin{bmatrix} x_{1} \\ \ldots \\ x_{n} \\ \end{bmatrix}$, c=$\begin{bmatrix} c_{1} \\ \ldots \\ c_{n} \\ \end{bmatrix}$
Zakładamy, że układ (2) jest układem niesprzecznym, tzn. rzA=rz[A/b]. Zakładamy, że rzA=m. Jeżeli rzA<m, to m-rzA warunków układu (2) odrzucamy.
MACIERZ BAZOWA
Macierz A ma m liniowo niezależnych kolumn oznaczonych przez a_j1, a_j2, …, a_jm. Z tych kolumn utworzymy macierz B, a z pozostałych kolumn macierz P.
Zatem: A=[BP], gdzie : B(x_i)= [a_j1, …, a_jn] P(x_j)=[a_{j, n + 1}, …, a_jn]
Macierz B – macierz bazowa, P – zmienne niebazowe, a – współrzędne wektora x o indeksach j₁, j₂, …, j_n - zmienne bazowe, pozostałe współrzędne wektora x – zmienne niebazowe.
Wymaga się, żeby B była macierzą nieosobliwą tzn. istniała B⁻¹ (det B≠0)
OZNACZENIE ZWIĄZANE Z BAZĄ B
Odpowiednio do podziału macierzy A, dzielimy wektor x na części 𝑥𝐵 𝑖 𝑥𝑃. A=$\begin{bmatrix} x_{B} \\ x_{P} \\ \end{bmatrix}$ gdzie x_B = [x_j1, …, x_jm]′ - wektor zmiennych bazowych; x_P = [x_jn + 1, …, x_jn]′ - wektor zmiennych niebazowych. Analogicznie dzielimy wektor współczynników funkcji celu c=$\begin{bmatrix} c_{B} \\ c_{P} \\ \end{bmatrix}$ gdzie c_B = [c_j1,…,c_jm]^′ - współczynnik przy zmiennych bazowych; c_P = [c_jn + 1,…,c_jn]^′ - wsp. przy zmiennych niebazowych.
BAZOWE ROZWIĄZANIE DOPUSZCZALNE (BRD)
PL (1)-(3) zapisuje się w postaci $\left\lbrack \text{BP} \right\rbrack\begin{bmatrix} x_{B} \\ x_{P} \\ \end{bmatrix} = b$, którego rozwiązanie jt w postaci $x = \begin{bmatrix} x_{B} \\ x_{P} \\ \end{bmatrix} = \begin{bmatrix} B^{- 1}b - B^{- 1}Px_{P} \\ x_{P} \\ \end{bmatrix}$. Szczególne rozwiązanie układu (2) otrzymujemy, gdy postawimy x_P = 0 i to rozwiązanie oznaczamy przez $x^{B} = \begin{bmatrix} x_{B} \\ x_{P} \\ \end{bmatrix} = \begin{bmatrix} B^{- 1}b \\ 0 \\ \end{bmatrix}$. x^B- całe rozwiązanie; x_B- oznacza tylko część rozwiązania odpowiadającego zmiennym bazowym. Jeżeli x_B = B⁻¹b > 0, to wektor x^B jt rozwiązaniem dopuszczalnym odpowiadającym bazie B i nazywane jt bazowym rozwiązaniem dopuszczalnym.
BAZOWE ROZWIĄZANIE OPTYMALNE
Współrzędne wektora x_B = B⁻¹b w BRD x^B są współrzędnymi wierzchołka zbioru D. Rozwiązań optymalnych zad PL z kryterium mx poszukuje się wśród rozwiązań BRD. Rozwiązanie BRD x^B będzie rozwiązaniem optymalnym, gdy f(x^B) ≥ f(x) dla każdego rozwiązania (4). Niech H_P = B⁻¹P, Z_P^′ = c_B^′H_p , z_B = c_B ; $Z^{B} = \begin{bmatrix} z_{B} \\ z_{P} \\ \end{bmatrix}$. BRD x^B jt optymalnym rozwiązaniem zad PL, gdy c − z^B ≤ 0.
WSKAŹNIKI OPTYMALNOŚCI
Warunek optymalności BRD x^B c-z≤0 oznacza, że c_j − z_j^B ≤ 0 dla każdego j=1,2, …, n. Zauważmy, że c_j − z_j^B = 0 dla jєB, czyli każdej zmiennej bazowej. Różnice c_j − z_j^B nazywamy wskaźnikami optymalności.
DOPUSZCZALNA POSTAĆ BAZOWA B
Aby nie obliczać macierzy odwrotnej B⁻¹ bd stosowali przekształcenia elementarne na wierszach macierzy rozszerzonej [A|b] takie, aby dostać macierz [H^B|h₀^B], przy czym H^B = B⁻¹A = B⁻¹[B P] = [B⁻¹B B⁻¹P] = [I  H_P] , gdzie H_P = B⁻¹P, h₀^B = B⁻¹b. Mówimy, że zad PL o macierzy rozszerzonej [H^B|h₀^B], ma dopuszczalną postać bazową. W tej nowej macierzy kolumna h₀^B = x_B, więc znane jt BRD x^B. Macierz H^B pozwoli łatwo sprawdzić, czy to rozwiązanie x^B jest optymalne. Rachunki z tym związane zapisujemy w tablicy sympleksowej.
SCHEMAT TABLICY SYMPLEKSOWEJ

Kryterium wejścia i wyjścia
Kryterium wejścia do zbioru zmiennych bazowych wprowadza się zmienną niebazową x_s, dla której wskaźnik optymalności przyjął największa wartość dodatnią: c_S − z_S = max{c_j − z_S :   c_j − z_j > 0} . Kryterium wyjścia ze zbioru zmiennych bazowych należy usunąć zmienną x_r, dla której:
$\frac{h_{r0}}{h_{\text{rs}}} = \operatorname{}{\{\frac{h_{r0}}{h_{\text{is}}}:\ \ \ h_{\text{is}} > 0\}}$ gdzie h_ij są elementami macierzy H^B = B⁻¹A, a h_r0 są współrzędnymi wektora h₀^B = B⁻¹b.
TWIERDZENIA O BRD (DLA MAX)
1T: Jeżeli BRD x^B ma wszystkie współrzędne bazowe różne od 0, to x^B jt rozwiązaniem optymalności (RO) wtedy i tylko wtedy, gdy wszystkie wskaźniki optymalności są niedodatnie, czyli c − z^B ≤ 0.
2T: Jeżeli BRD x^B ma wszystkie współrzędne bazowe różne od 0, to x^B jt jedynym RO wtedy i tylko wtedy, gdy wszystkie wskaźniki optymalności są ujemna, czyli c − z^B < 0 dla jB.
3T: Jeżeli BRD x^B istnieje zmienna niebazowa o nr k, dla której wskaźnik optymalności jt dodatni c_k − z_k > 0 oraz k-ta kolumna macierzy H^B ma elementy niedodatnie, tzn. h₀^B ≤ 0, to f.celu jt niegraniczona z góry. Zbior D_opt = ⌀.