PROGRAMOWANIE LINIOWE.
Zadania programowania liniowego.
Przedmiot programowania matematycznego.
Przykłady ekonomicznych zadań programowania liniowego.
Ekonomiczno-matematyczny model zadań programowania liniowego.
Elementy algebry macierzowej. Przekształcenia Jordanego.
Przedmiot programowania matematycznego.
Wiele zadań ekonomicznych ma dużo sposobów rozwiązania. Wśród tych możliwych sposobów rozwiązania trzeba znale¼ć jedno najlepsze pasujące do ograniczeń rozwiązanie, które pasuje do naturalnych, technicznych, ekonomicznych i innych możliwości. Wcześniej takie zadania były nie bardzo skomplikowane i rozwiązywane na podstawie zdrowego rozsądku i doświadczenia osób, które mogły podjąć decyzję. Ale takie podejście nie gwarantuje, że rozwiązanie będzie najlepszym w sensie ekonomicznym. Dla współczesnych, tempo rozwinięcia i poziomów produkcji, transportu, konsumpcji błędy ekonomicznych decyzji powodują duże straty czasu i środków dla przedsiębiorstw dowolnego poziomu rozwinięcia. W związku z tym, znaczną aktualność przybierają zastosowania ekonomiczno-matematycznych metod analizy ekonomicznych sytuacji, zastosowanie komputerów dla modelowania i poszukiwania optymalnych rozwiązań ekonomicznych zadań. Matematyczne metody analizy i synteza problemów ekonomiki otrzymały nazwę matematycznego programowania i badań operacyjnych.
Definicja 1. Przedmiot badania operacyjnego jest dziedziną matematyki, która zajmuje się opracowywaniem najlepszych strategii rozwiązania zadań ekonomicznych z ograniczeniami.
Definicja 2. Programowanie matematyczne jest dziedziną matematyki, która zajmuje się opracowywaniem teorii i metod numerycznych rozwiązań wielowymiarowych ekstremalnych zadań z ograniczeniami.
Innymi słowy, programowanie matematyczne i badania operacyjne są dziedzinami matematyki, które zajmują się opracowywaniem teorii i metod numerycznych rozwiązania zadań na ekstremum funkcji wielu zmiennych z ograniczeniami na dziedzinach niezależnych zmiennych.
Definicja 3. Funkcja, dla której potrzeba znale¼ć wartość ekstremalną, nazywa się funkcją celu.
Definicja 4. Matematyczny model zadania – to jest odbicie zadania ekonomicznego w postaci funkcji, równań, nierówności, liczb, itd.
Model matematyczny zadania ekonomicznego zawiera:
1. zbiór zmiennych niewiadomych x=(x1,x2,...xn) - działań, które pozwalają udoskonalić model. Zmienne te nazywają się planem zadania.
2. funkcję celu. Pozwala ona wybierać najlepsze warianty ze zbioru rozwiązań. Dla najlepszego wariantu funkcja celu ma wartość ekstremalną.
3. warunki (lub system ograniczeń), które nałożone są na zmienne niewiadome. Te warunki dotyczą ograniczeń zasobów, które wykorzystuje się w tych procesach ekonomicznych.
Również, te ograniczenia związane są z ograniczeniami finansowymi, materialnymi i innymi.
Te matematyczne ograniczenia wyrażają się w postaci równań i nierówności. Ich zbiór jest dziedziną rozwiązań dopuszczalnych (lub dziedziną ekonomicznych możliwości).
Takim czynem, należy opracować model zadania programowania matematycznego to znaczy:
znale¼ć plan x=(x1,x2,...xn), dla którego funkcja celu Z osiągnie ekstremum, tj.
max (min) Z=z(x1,x2,...,xj,...,xn),
dla ograniczeń fi(x1,x2,...,xj,...,xn) { lub = lub } bi, i=1,2,...m.
Często, biorąc pod uwagę ekonomiczne, fizyczne lub inne warunki, na zmienne należące do planu zadań musimy założyć warunek, że nie są one ujemne xj 0 (j=1,2,...k), w innych przypadkach, że są one całkowite (xj Z, gdzie Z – zbiór liczb całkowitych (j=1,2,...k)).
Definicja 5. Plan x=(x1,x2,...xn), który czyni zadość wszystkim ograniczeniom, nazywa się dopuszczalnym.
Definicja 6. Plan dopuszczalny x*=(x1*,x2*,...xn*), dla którego osiągnie ekstremum funkcji celu Z*=z(x1*,x2*,...xn*), nazywa się optymalnym.
Optymalnych rozwiązań może być jedno, może być skończona lub nieskończona ilość.
Klasyfikacja metod badania operacyjnego i programowania matematycznego.
W zależności od funkcji celu Z=Z(X) i funkcji ograniczeń f=f(X), gdzie X=(x1,x2,...xn), zadania programowania matematycznego dzielą się na:
1. Zadania programowania liniowego. W tym przypadku funkcja celu Z=Z(X) i funkcja ograniczeń f=f(X) są liniowe (pierwszego stopnia).
Do tych zadań należą zadanie wykorzystania zasobów, zadanie o dietach, zadanie o podziale materiałów, zadanie transportowe i inne.
2. Zadania programowania nieliniowego. W tym przypadku funkcja celu Z=Z(X) lub funkcja ograniczeń f=f(X) są nieliniowe.
Do tych zadań należą zadanie o dostawach dóbr, wykorzystanie zasobów, rozmieszczenie sił produkcyjnych i inne.
3. Zadania programowania dynamicznego. W tym przypadku funkcja celu Z=Z(X) i funkcja ograniczeń f=f(X) zmieniają się w czasie, decyzja rozwiązania jest wielokrokowa, a funkcja celu Z=Z(X) jest addytywna lub multiplikatywna .
Do tych zadań należą zadanie o sterowaniu produkcyjnym lub sterowaniu zasobami, o strategiach wymiany urządzeń i inne.
4. Zadania programowania całkowitoliczbowego. W tym przypadku rozwiązanie zadań musi być całkowitoliczbowe.
Do tych zadań należą zadanie komiwojażera (o marszrutach ruchu), zadanie teorii rozkładów i inne.
5.Zadania programowania stochastycznego. W tym przypadku parametry funkcji celu są losowe lub potrzebują podjęcia decyzji w warunkach ryzyka lub niedostatecznej informacji.
Do tych zadań należą zadanie teorii gier, zadanie ekspertowe i inne.
6. Zadania wielokryterialnej analizy. W rzeczywistości ekonomiczne zadania są na tyle skomplikowane, że istnieje potrzeba szukać ekstremum jednocześnie dla kilku celowych funkcji: Z1=z1(x1,x2,...,xj,...,xn1), Z2=z2(x1,x2,...,xj,...,xn2), ... Zk=zk(x1,x2,...,xj,...,xnk), gdzie k – ilość funkcji celu, ni (i=1,2,...k) – ilość zmiennych dla k-ej funkcji celu.
Przykłady zadań programowania liniowego.
1. Zadanie o najlepszym wykorzystaniu zasobów.
Niech niektóra jednostka wytwórcza (hurtownia, ...) może wyprodukować n różnych typów produkcji (towarów), które oznaczymy P1, P2, ... Pj, ... Pn. Jednostka wytwórcza jest ograniczona dysponującymi rodzajami produkcyjnych zasobów, technologii, surowców, siły roboczej itd. Niech liczba takich ograniczeń m, a ich ilości odpowiednio są równe b1, b2, ... bm umownych jednostek. Znana jest też miara użyteczności wyprodukowania produkcji każdego rodzaju (na przykład, cena sprzedaży, zysk itd.) c1, c2, ... cn.. Wiadome są również współczynniki technologiczne wskazujące ile jednostek i - go zasobu potrzebne będzie dla wyprodukowania jednostki j - go rodzaju produkcji.
Oznaczymy przez x=(х1, х2, ... хn) plan produkcji, zgodnie z którym muszą być wyprodukowane wyroby P1, P2, ... Pn w ilościach odpowiednio х1, х2, ... хn, żeby przedsiębiorstwo miało maksymalną produkcję dla zasobów b1, b2, ... bm, którymi on dysponuje.
Tak jak koszt jednostki j-ej produkcji jest cj, ilość jednostek xj, to suma ze sprzedaży xj jednostek będzie cj*xj, a ogólna suma ze sprzedaży wyprodukowanej produkcji będzie
Z=c1*x1+c2*x2+ ... +cn*xn = (1.1)
Rozchód i-gо zasobu na produkcję xj jednostek j-gо produktu można określić jako aij*xj. Wówczas sumowany rozchód tego zasobu nie powinien przekroczyć bi (i=1,2, ... m) jednostek:
ai1*x1+ai2*x2+ ... + ain*xn bi, lub , (i=1,2,...m) (1.2)
Rzeczywiście, że objętość wyprodukowanej produkcji xj powinna być nieujemna:
xj 0, j=1,2, ... n. (1.3)
Przedsiębiorstwu dla optymalizacji produkcji konieczne jest maksymalizować celową funkcję Z z (1.1). W ten sposób, ekonomiczno-matematyczny model zadania o najlepszym wykorzystaniu zasobów przyjmie postać:
znale¼ć
max Z = c1*x1+c2*x2+ ... +cn*xn = (1.4)
dla ograniczeń (1.2), (1.3).
Zadanie liniowego programowania (1.4) z ograniczeniami (1.2), (1.3) można sformułować w macierzowej postaci:
max Z = c*x (1.4a)
dla ograniczeń
А*х b (1.2a)
gdzie с = (c1, c2 , ... cn) jest wektorem cen na produkcję, х = (х1, х2 , ... хn) jest wektorem ilości wyprodukowanej produkcji (plan zadania), b = (b1, b2 , ... bm) jest wektorem dysponowanych zasobów, А= (aij) jest macierzą technologicznych współczynników.
2. Zadania o dietach (mieszankach).
W produkcji, w medycynie, w rolnictwie powstają zadania o porównaniu mieszanek na podstawie wstępnych składników, które nadawałyby końcowemu produktowi pożądane właściwości . Do takich zadań można odnieść zadanie ułożenia diety, zadania racjonalnego karmienia zwierząt, zadanie doboru mieszanek dla otrzymania budowlanych materiałów i inne.
Jako przykład rozpatrzymy zadanie o przygotowaniu najlepszego pokarmu (racji) dla zwierząt.
Mamy produkty na pokarm zwierząt P1, P2, ... Pj, ... Pn. (siano, buraki, ziarno itd.). W nich zawarte są różne materie pożywne (węglowodany, białka, mikroelementy itd.), oznaczymy ich numerami 1, 2, ... m . Jednostka j-gо produktu ma w sobie aij jednostek i-gо materiału pożywnego. Według norm za określony czas potrzebne zwierzęta muszą otrzymać nie mniej niż bi jednostek i-gо materiału pożywnego. Niech znany jest również koszt ci jednostki produktu i-го rodzaju. Potrzebne jest dokonać wyboru pokarmu najmniejszego kosztu, w którym są niezbędne ilości materiałów pożywnych, tj. określić plan х = (х1, х2 , ... хn) zadania.
Ekonomiczno-matematyczny model zadania ma postać:
min Z = c1*x1+c2*x2+ ... +cn*xn = (1.5)
dla ograniczeń
ai1*x1+ai2*x2+ ... + ain*xn bi, lub (i=1,2,...m) (1.6)
xj 0, j=1,2, ... n (1.7)
3. Zadanie o rozdziale materiałów.
W praktyce często mamy do czynienia z zadaniami wymagającymi optymalnego rozdzielenia wyjściowego obiektu na technologiczne części według masy, objętości, pola itd. Na przykład dla wyszycia garnituru, kawałek tkaniny należy podzielić na cholewki dla rękawów, spodni, itd. Przy tym resztki tkaniny muszą być minimalne.
Zadanie o optymalnym rozdziale materiałów polega na zdefiniowaniu takiego technologicznie możliwego planu rozdziału materiałów, dla którego otrzymamy niezbędną ilość części, a liczbę odpadek minimalną.
Rozpatrzymy najprostszy model rozdziału według jednego wymiaru (prętów, rur itd.). Niech mamy N sztuk wejściowego materiału, długość każdej sztuki równa L. Potrzebna przygotować m kawałków o długościach li (i=1,2, ... m). Wiadomo, że potrzebne jest bi kawałków każdego rodzaju. Niech, również mamy n rożnych technologicznych sposobów rozdziału wejściowego materiału. Oznaczymy przez aij – ilość półwyrobów i-go rodzaju, które otrzymamy przy rozdziale jednostki materiału według j- go sposobu (j = 1,2,...n), сj – odpady przy rozdziale jednostki materiału według j- go sposobu.
Celowa funkcja, dla której potrzeba osiągnąć minimum odpadów przy rozdziale ma postać:
min Z = c1*x1+c2*x2+ ... +cn*xn = (1.8)
przy ograniczeniach
- na ilość jednostek wstępnego materiału
x1+x2+ ... + xn N , lub (1.9)
-na spełnienie asortymentu, potrzebnego konsumentom:
ai1*x1+ai2*x2+ ... + ain*xn bi, lub , (i=1,2,...m) (1.10)
i warunek nieujemności
xj 0, j=1,2, ... n (1.11)
4. Zadanie transportowe.
Rozpatrzymy najprostszy przypadek zadania transportowego. Mamy m punktów produkcji, w każdym z których znajduje się ai (i=1,2, ... m) jednostek produktu jednego rodzaju. Ten produkt potrzeba dostarczać n konsumentom, u których zapotrzebowanie jest bj (j=1,2,...n) jednostek, gdzie , więc ogólna ilość wyprodukowanego i spożywanego produktu jest taka sama. Znane są również cij – koszty dostawy jednostki produkcji z i-gо punktu produkcji do j-go punktu konsumpcji (taryfa na dostawę). Oznaczymy przez хij – ilość produktu, dostarczonego z i-gо punktu produkcji do j-go punktu konsumpcji. Macierz С=(cij) nazywa się macierzą taryfową, a macierz Х=(хij) – macierzą przewozów.
Konieczne jest zminimalizować koszty przy dostawach produktów. Wówczas ekonomiczno-matematyczny model zadania transportowego przyjmie postać:
min Z = c11*x11+c12*x12+ ... +cmn*xmn = (1.12)
przy ograniczeniach
-na możliwości dostawców (cały produkt musi być wywieziony od dostawców)
xi1+xi2+ ... +xin =ai lub , i=1,2, ... m (1.13)
- na popyt konsumentów, którzy muszą być w pełni zadowoleni
x1j+x2j+ ... +xmj =bj lub , j=1,2, ... n (1.14)
- na wykluczenie odesłania towaru do dostawcy
xij 0, i=1,2,...m, j=1,2, ... n (1.15)
Wiele zadań z innych rozdziałów matematycznego programowania możemy także sprowadzić do zadań liniowego programowania.
1.3. Ekonomiczno-matematyczny model zadań programowania liniowego.
Przykłady zadań liniowego programowania (1.2)-(1.4), (1.5)-(1.7), (1.8)-(1.11), (1.12)-(1.15) pozwalają zapisać ogólną postać ekonomiczno-matematycznego modelu zadania programowania liniowego.
Ogólnym zadaniem programowania liniowego (ОZPL) nazywamy zadanie
max (min) Z = c1*x1+c2*x2+ ... +cn*xn = (1.16)
przy ograniczeniach:
ai1*x1+ai2*x2+ ... + ain*xn bi, lub , (i=1,2,...m1) (1.17)
ai1*x1+ai2*x2+ ... + ain*xn = bi, lub , (i=m1+1, m1+2,...m2) (1.18)
ai1*x1+ai2*x2+ ... + ain*xn bi, lub , (i= m2+1, m2+2,...m) (1.19)
xj 0, j=1,2, ... n1 (1.20)
xj - dowolne (j= n1+1, n1+2, ... n) (1.21)
gdzie сj, aij, bi - dane rzeczywiste liczby; (1.16) — celowa funkcja; (1.17) — (1.21) —ograniczenia; х=(х1; ...; xn) —plan zadania.
Symetryczną formą zapisu ZLP nazywamy zadanie
max Z = c1*x1+c2*x2+ ... +cn*xn = (1.22)
przy ograniczeniach:
ai1*x1+ai2*x2+ ... + ain*xn bi, lub , (i=1,2,...m1) (1.23)
xj 0, j=1,2, ... n (1.24)
lub zadanie
min Z = c1*x1+c2*x2+ ... +cn*xn = (1.25)
przy ograniczeniach:
ai1*x1+ai2*x2+ ... + ain*xn bi, lub , (i= 1,2,...m) (1.26)
xj 0, j=1,2, ... n (1.27)
Kanoniczną formą zapisu ZLP nazywamy zadanie
max Z = c1*x1+c2*x2+ ... +cn*xn = (1.28)
przy ograniczeniach:
ai1*x1+ai2*x2+ ... + ain*xn = bi, lub , (i=1, 2,...m) (1.29)
xj 0, j=1,2, ... n (1.30)
Jak było pokazane wyżej, zadanie programowania liniowego może być zapisane w macierzowej postaci.
Jeśli jest to konieczne, zadanie minimalizacji można zamienić zadaniem maksymalizacji i odwrotnie. Dla funkcji jednej zmiennej to twierdzenie jest rzeczywiste.
Jeśli х* — punkt minimum funkcji y=f{x), wtedy dla funkcji у=-f{x) będzie on punktem maksimum, bo wykresy funkcji f(x) i -f(x) są symetryczne odnośnie osi odciętych, tj. min{f(x*)}= -max{-f(x*)}.
To samo ma miejsce w przypadku funkcji n zmiennych:
min{f(x1* , x2* , ... , xn*)}= -max{-f(x1* , x2* , ... , xn*)}.
W zadaniach programowania liniowego większość ograniczeń stawia się w nierównościach. Najczęściej metody ZPL wykorzystuje się tylko do zadań zapisanych w kanonicznej postaci.
Zrealizować przejście do ZLP zapisanych w kanonicznej postaci można następująco. Niech, na przykład, wyjściowa ZLP ma postać:
max Z = c1*x1+c2*x2+ ... +cn*xn = (1.31)
przy ograniczeniach:
ai1*x1+ai2*x2+ ... + ain*xn bi, lub , (i=1,2,...m1) (1.32)
ai1*x1+ai2*x2+ ... + ain*xn bi, lub , (i= m1+1, m1+2,...m) (1.33)
xj 0, j=1,2, ... n (1.34)
Przekształcimy jego do kanonicznej postaci. Wprowadzimy т dodatkowych (swobodnych, bilansowych) nieujemnych zmiennych xn+i 0, (i=1,2, ... m).
Dlatego, żeby nierówności postaci w (1.32) przekształcić w równości, do ich lewych stron dodamy swobodne zmienne xn+i (i=1,2, ... m1), po czym układ nierówności (1.32) przyjmie postać:
ai1*x1+ai2*x2+ ... + ain*xn + xn+i = bi, lub , (i=1,2,...m1) (1.35)
źeby nierówności postaci w (1.33) przekształcić w równości, od ich lewych stron odejmiemy swobodne zmienne xn+i (i= m1+1, m1+2, ... m). Otrzymamy:
ai1*x1+ai2*x2+ ... + ain*xn - xn+i = bi, lub , (i= m1+1, m1+2,...m) (1.36)
Układ równań (1.35) ((1.36)) razem z warunkiem, że zmienne swobodne są nieujemne nazywa się ekwiwalentnym układu nierówności (1.32) ((1.33)).
Swobodne zmienne xn+i (i=1,2, ... m) w celową funkcję wprowadzamy ze współczynnikami równymi zeru. Otrzymamy zadanie:
max Z = c1*x1+c2*x2+ ... +cn*xn + 0* xn+1 + ...+ 0* xn+m = + (1.37)
ai1*x1+ai2*x2+ ... + ain*xn + xn+i = bi, lub , (i=1,2,...m1) (1.38)
ai1*x1+ai2*x2+ ... + ain*xn - xn+i = bi, lub , (i= m1+1, m1+2,...m) (1.39)
xj 0, j=1,2, ... n, xn+i 0, i=1,2, ... m (1.40)
Zadania (1.37) - (1.39) mają kanoniczną postać. Zadania (1.31) - (1.34) i (1.37) - (1.40) są ściśle powiązane pomiędzy sobą.
Twierdzenie 1.1. Każdemu dopuszczalnemu rozwiązaniu (х10; ...; хn0) zadania (1.31) - (1.34) odpowiada całkiem określone dopuszczalne rozwiązanie (х10; ...; хn0 ; хn+10; ...; хn+m0) zadania (1.37) - (1.40), gdzie xn+i 0, (i=1,2, ... m), i odwrotnie, każdemu dopuszczalnemu rozwiązaniu (х10; ...; хn0 ; хn+10; ...; хn+m0) zadania (1.37) - (1.40) odpowiada dopuszczalne rozwiązanie (х10; ...; хn0) zadania (1.31) — (1.34).
Tak jak swobodne zmienne хn+i0 wchodzą w celową funkcję (1.37) ze współczynnikami równymi zeru, to znaczenia celowych funkcji (1.31) i (1.37) dla odpowiednich dopuszczalnych rozwiązań (х10; ...; хn0) i (х10; ...; хn0 ; хn+10; ...; хn+m0) są jednakowe. Stąd wnioskujemy , że celowe funkcje (1.31) i (1.37) na zbiorze odpowiednich dopuszczalnych rozwiązań osiągają ekstremalne znaczenia jednocześnie. Optymalnemu rozwiązaniu (х1*; ...; хn*) zadania (1.31) - (1.34) odpowiada optymalne rozwiązanie (х1*; ...; хn* ; хn+1*; ...; хn+m*) zadania (1.37) - (1.40).
Podkreślimy ekonomiczny sens swobodnych zmiennych. W każdym zadaniu są one ściśle związane z jego ekonomiczną zawartością.
Na przykład, dla zadania (1.2) - (1.4) o najlepszym wykorzystaniu zasobów swobodna zmienna pokazuje wielkość niewykorzystanego zasobu.
Dla zadaniach o mieszankach (1.5) - (1.7) swobodna zmienna pokazuje konsumpcję odpowiedniego składnika pożywnego w optymalnym planie powyżej normy.
W niektórych produkcyjno-ekonomicznych sytuacjach, nie na wszystkie zmienne nakładają się warunki, że nie są one ujemne. W podobnych sytuacjach, nawet jeśli ograniczenia przedstawione są w postaci równań, zadanie nie będzie kanonicznym. Dla przedstawienia takiego zadania w kanonicznej postaci każdą zmienną хk, która ma warunek nieujemny, zastąpimy różnicą dwóch nieujemnych zmiennych х’k i х”k, tj. хk = х’k - х”k, gdzie х’k 0, х”k 0.
Niech ranga macierzy symetrycznego zadania programowania liniowego (1.29) jest równa r i r
, i=1,2, ... r (1.41)
Zmienne x1, x2, ... xr nazywają się bazowymi, a xr+1, x2, ... xn — swobodnymi (nie bazowymi).
|
