W działalności gospodarczej realizowana jest zasada racjonalnego gospodarowania. Zasada ta orzeka, ze stojące do dyspozycji środki umożliwiające realizacje jakiegoś celu powinny być użyte w sposób gwarantujący maksymalna realizacje postanowionego celu. Zasada ta może być stosowana wtedy, gdy zarówno cel jak i środki dają się ująć w sposób ilościowy. Stosowanie zasady racjonalnego gospodarowania sprowadza się w praktyce do rozwiązywania tzw. zagadnień optymalizacyjnych to znaczy optymalizacji decyzji przy określonym kryterium optymalności. Możemy mieć przy tym do czynienia z zasada największej efektywności, jeśli przy danym nakładzie środków uzyskuje się maksymalny stopień ustalonego celu. Innym wariantem zasady racjonalnego gospodarowania jest zasada najmniejszego nakładu środków. Mamy z nią do czynienia wówczas, gdy ustalone zadania produkcyjne uzyskujemy przy najmniejszych nakładach środków. Plan zgodny z zasada racjonalnego gospodarowania nazywamy planem optymalnym. Jest to wiec taki plan, przy którym zadania produkcyjne osiąga się przy najmniejszych nakładach środków, lub z danych nakładów osiągany jest maksymalny efekt produkcyjny.
Dla zbudowania planu optymalnego konieczna jest znajomość tzw. metod programowania matematycznego. Najbardziej znana metoda programowania matematycznego jest tzw. programowanie liniowe. Ze względu na swoja efektywność znajduje ono liczne zastosowanie w praktyce. Przy jego pomocy ustala się na przykład program przydziału produkcji z m zakładów produkcyjnych do n hurtowni przy minimalizacji kosztów transportu. Układa się tez optymalna dietę przy m środkach żywnościowych i n składnikach odżywczych.
Jednym z zasadniczych założeń leżących u podstaw programowania liniowego jest założenie o proporcjonalności wyników do nakładów.
Modele programowania liniowego
W działalności ekonomicznej podejmując decyzje należy najpierw określić zbiór dopuszczalnych decyzji D (określony nierównościami lub równaniami) a następnie sprecyzować kryterium wyboru (tzn. funkcje celu, która ma osiągać wartość największa, czy najmniejsza).
Rozpatrywane jest zagadnienie, w którym funkcja f(x1,x2,...,xn) jest liniowa, jak również warunki qi(x1,x2,...,xn)ł0 lub qi(x1,x2,...,xn)Ł0 dla i=1,2,...,m są liniowe a ponad to zada się, aby xk ł0 dla k=1,2,...,n. Zmienne xk (k=1,2,...,n) nazywamy zmiennymi decyzyjnymi. Zagadnienie optymalizacyjne w postaci liniowej ma następujące postacie:
Zagadnienie 1. Znaleźć wszystkie punkty (x1,x2,...,xn) o współrzędnych nieujemnych tzn. x1ł0, x2ł0,..., xn ł 0 spełniające układ nierówności (warunków):
Dla których funkcja celu:
z=c1x1+c2x2+...+cnxn,
Przyjmuje wartość największa.
Zagadnienie 2. Znaleźć wszystkie punkty (x1,x2,...,xn) o współrzędnych nieujemnych tzn. x1ł0, x2ł0,..., xn ł 0 spełniające układ nierówności (warunków):
Dla których funkcja celu:
z=c1x1+c2x2+...+cnxn,
Przyjmuje wartość najmniejsza.
Z teorii dotyczącej zbiorów wypukłych oraz rozwiązania nierówności, wynika ze każda z nierówności występujących w podanych układach przedstawia przy założeniu:
(ai1) 2+(ai2) 2+...+(ain) 2>0, i=1,2,…,m.
Zbiór wypukły. Wiadomo, ze cześć wspólna zbiorów wypukłych jest zbiorem wypukłym. Zatem zbiór rozwiązań dopuszczalnych zadania 1 czy 2 jest zbiorem wypukłym, konkretnie zbiorem wielościennym, mającym skończona liczbę wierzchołków. Skorzystamy z tego w metodzie graficznej rozwiązywania żądań programowania liniowego, jak również w metodzie simpleks.
Metoda graficznego rozwiązywania żądań programowania liniowego.
Zadanie programowania liniowego w przypadku, gdy mamy do czynienia tylko z dwiema zmiennymi decyzyjnymi rozwiązuje się łatwo w sposób graficzny:
Przypuśćmy, ze funkcja celu zmiennych x1 i x2 jest
Z=c1x1+c2x2, (c1>0, c2>0)
A układ ma postać:
a11x1+a12x2Ł b1
a21x1+a22x2Ł b2
gdzie aik>0 (I,k = 1,2) i b1,b2>o oraz x1ł0, x2ł0 (warunki brzegowe).
Chodzi o znalezienie wartości zmiennych decyzyjnych x1,x2 takich, aby spełniony był podany układ warunków i aby funkcja celu
Z=c1x2+c2x2
Przyjmowała wartość największa.
Oznaczając przez l1 i l2 proste o równaniach: l1: a11x1+a12x2=b1, l2 : a21x1=a22x2=b2,
To na płaszczyźnie Ox1x2 nierówność a11x1+a12x2Łb1 spełniają współrzędne wszystkich punktów płaszczyzny znajdujących się na lub pod prosta l1.
Analogicznie nierówność a21x1+a22x2Łb2 spełniają współrzędne wszystkich punktów płaszczyzny leżących na lub pod prosta l2. Przyjmując jeszcze warunki brzegowe x1ł0 i x2ł0 otrzymujemy, ze obszar rozwiązań dopuszczalnych tworzą punkty pierwszej ćwiartki układu współrzędnych leżące równocześnie pod prostymi l1 i l2 lub na nich, a wiec współrzędne wszystkich punktów czworokąta OABC (patrz rysunek 1). Jeśli w funkcji celu z=c1x1+c2x2 zmienia się z, to równanie to przedstawia pęk prostych równoległych. Przedstawmy ten pęk prostych w postaci kierunkowej:
Im większe jest, z (czyli im większy jest stopień realizacji funkcji celu) tym wyżej jest położona odpowiednia prosta z pęku prostych równoległych. Najwyżej położona spośród nich prosta, która ma przynajmniej jeden punkt wspólny z czworokątem OABC, przedstawia (tzn. punkt wspólny) rozwiązanie optymalne.
Rysunek 1 (patrz załącznik)
Przykład 1.
Przedsiębiorstwo produkuje wyroby A i B przy pomocy trzech rodzajów tokarek T1, T2, T3. zdolność produkcyjna w tysiącach sztuk na rok (Z.P.) poszczególnych tokarek jest następująca:
T1 T2 T3
A 6 5
B 6 4 10
Zysk na jednostce wyrobu a wynosi 2 jednostki pieniężne, a na jednostce B wynosi cztery jednostki pieniężne. Określić rozmiary produkcji wyrobów A i B, aby przedsiębiorstwo osiągnęło zysk maksymalny.
Warunki przykładu przełożymy na język nierówności i funkcji. Oznaczymy roczna produkcje wyrobu A przez x1, a wyrobu B przez x2. Zgodnie z warunkami zadania roczny zysk z tej produkcji (funkcja celu) wynosi:
Z=2x1+4x2
Przy czym x1ł0 i x2ł0. Ponieważ zdolności produkcyjne w ciągu roku tokarek są ograniczone wiec:
x1+x2Ł6 gdyż produkcja nie może być większa od zdolności produkcyjnej tokarek T1
x2Ła gdyż produkcja wyrobu B nie może być większa od zdolności produkcyjnej tokarek T2
2x1+x2Ł10 gdyż produkcja obu wyrobów nie może być większa od zdolności produkcyjnej tokarek T3
Rysunek 2 (patrz załącznik)
Rozwiązanie zadania sprowadza się do znalezienia optymalnego ze względu na funkcje celu z=2x1+4x2 punktu obszaru określonego nierównościami:
W tym celu rysujemy proste l1: x1+x2=6, l2: x2=4, l3 : 2x1+x2=10. Obszarem rozwiązań dopuszczalnych (leży w I ćwiartce, patrz rysunek 2) jest pięciokąt OABCD. Weźmy teraz pod uwagę funkcje celu z=2x1+4x2. Przyjmując z=0 otrzymujemy prosta p: 2x1+4x2=0. Prosta ta w szczególności przechodzi przez punkty (2,-1) i (0,0). Proste odpowiadające funkcji celu dla rożnych wartości z są równolegle do prostej p (2x1+4x2=0). Im większa jest wartość z, tym wyżej (i bardziej na prawo) leży odpowiednia prosta. Zatem najwyższy zysk odpowiada prostej równoległej do prostej P przechodzącej przez obszar rozwiązań dopuszczalnych położonej możliwie najwyżej. Z rysunku widać, ze punktem rozwiązań odpowiadających najwyższemu zyskowi jest punkt C(2,4). Zatem gdy przedsiębiorstwo będzie produkować 2000 sztuk rocznie wyrobu A i 4000 sztuk wyrobu B, to osiągnie najwyższy zysk.
Przykład 2.
Dieta żołnierza składa się z dwóch środków żywnościowych z chleba i mięsa, zawierającego dwa składniki odżywcze np.: kalorii i proteiny. Jednostka wagowa chleba zawiera 1 jednostkę protein oraz 5 jednostek kalorii, a jednostka wagowa mięsa zawiera 5 jednostek protein oraz 1 jednostkę kalorii. Żołnierz powinien otrzymać dziennie, co najmniej 15 jednostek kalorii i 15 jednostek protein. Przy jakiej diecie koszt będzie najmniejszy, jeśli cena chleba wynosi 1, a cena mięsa 3 jednostki pieniężne.
Warunki zadania przełożymy na język nierówności i funkcji. Przypuśćmy, ze żołnierz otrzymuje dziennie x1 jednostek chleba i x2 jednostek mięsa. Koszt dzienny utrzymania żołnierza (funkcja celu) wynosi:
Z=x1+3x2
Obszar rozwiązań dopuszczalnych określony jest następującymi nierównościami (patrz rysunek 3):
x1+5x2ł15 (ilość jednostek protein otrzymanych w chlebie i mięsie nie może być mniejsza od 15 jedni stek)
Rysunek 3. (patrz załącznik)
5x1+x2ł15 (ilość jednostek kalorii otrzymanych w chlebie i mięsie nie może być mniejsza od 15 jednostek)
Oraz musi leżeć w pierwszej ćwiartce (x1ł0 i x2ło). Rysujemy proste l1: x1+5x2=15, l2: 5x1+x2=15. Obszar rozwiązań dopuszczalnych leży na i powyżej prostych l1 i l2, czyli jest to obszar wypukły nieskończony ograniczony odcinkami AB i BC oraz odpowiednimi częściami osi Ox1 i Ox2. Biorąc pod uwagę funkcje celu z=x1+3x2 i przyjmując z=0 otrzymujemy prosta p: x1+3x2=0, która w szczególności przechodzi przez punkty (-3,1) oraz (0,0). Proste odpowiadające funkcji celu z=x1+3x2 dla rożnych wartości z są równolegle do prostej p(x1+3x2=0). Im mniejsza wartość z, tym niżej (i bardziej na lewo) leży odpowiednia prosta. Zatem najmniejszy koszt odpowiada prostej równoległej do prostej p przechodzącej przez obszar rozwiązań dopuszczalnych i położonej możliwie najniżej. Z rysunku widać, ze punktem rozwiązań odpowiadającym najniższemu kosztowi jest punkt B (5/2,5/2). Oznacza to, ze najtańsza dieta powinna się składać z dwóch i pól jednostek wagowych chleba i dwóch i pól jednostek wagowych mięsa.