Badania operacyjne
BIBLIOGRAFIA
Goddard L.S. Metody matematyczne w badaniach operacyjnych, PWN, Warszawa. 1965.
Bellman R,, Dreyfus S. Programowanie dynamiczne, PWE, Warszawa. 1967.
Sadowski W. Teoria podejmowania decyzji, PWG, Warszawa. 1967.
Ford L.R., Fulkerson D.R. Przepływy w sieciach, PWN, Warszawa. 1969.
Zangwill W.I. Programowanie nieliniowe, WNT, Warszawa. 1974.
Barton R. Wprowadzenie do symulacji i gier, WNT, Warszawa. 1974.
Mitchell G.H. Badania operacyjne — metody i przykłady, Warszawa, WNT. 1977.
W.Radzikowski. Matematyczne techniki zarządzania. - Warszawa. PWE. 1980.
J.Buga, W.Grabowski, J.Greń i inny. Ekonometria i badania operacyjne. - Warszawa. PWN. 1980.
Wagner H.M. Badania operacyjne w zarządzaniu, PWE, Warszawa, 1980.
Grabowski W. Programowanie matematyczne, PWE, Warszawa. 1980.
Galas Z., Nykowski I., Żółkiewski Z. Programowanie wielokryierialne, PWE, Warszawa. 1987.
Roy B. Wielokryterialne wspomaganie decyzji, WNT, Warszawa. 1990.
Czerwiński Z. Dylematy ekonomiczne, PWE, Warszawa. 1992.
Sysło M., Deo N., Kowalik J. Algorytmy optymalizacji dyskretnej, PWN, Warszawa. 1993.
Jajuga W., Jajuga T. Jak inwestować w papiery wartościowe, Wydawnictwo Naukowe PWN, Warszawa. 1993.
Kukula K. Badania operacyjne w przykładach i zadaniach, PWN, Warszawa, 1993.
Kofler E. Podejmowanie decyzji przy niepeinej informacji, Real Publisher, Warszawa. 1993.
Ignasiak E. Optymalizacja projektów inwestycyjnych, PWE, Warszawa, 1994.
Mikołajczyk Z. Techniki organizatorskie w rozwiązywaniu problemów zarządzania, PWN, Warszawa. 1994.
Ignasiak E., Borucki W., Marcinkowski J., Sikora W. Badania operacyjne, Optymalizacja projektów inwestycyjnych, PWE, Warszawa, 1997.
R.Barczyk, B.Guzik, A.Korzeniowski, Z.Romanow. Ekonometria i badania operacyjne. Zagadnienia podstawowe. Wydanie 3. - Poznań. Wydawnictwo Akademii Ekonomicznej. 2000.
T.Szapiro i inni. Decyzje menedżerskie z Excel'em. - Warszawa. Państwowe Wydawnictwo Ekonomiczne. 2000.
I. Badania operacyjne. WstęP. Programowanie liniowe.
Lekcja 1. Zadania programowania liniowego.
1.0. Wstęp. Przedmiot badań operacyjnych.
1.1. Przedmiot programowania matematycznego.
1.2. Przykłady ekonomicznych zadań programowania liniowego.
1.3. Ekonomiczno-matematyczny model zadań programowania liniowego.
1.4. Elementy algebry macierzowej. Przekształcenia Jordanego.
1.0. Wstęp. Przedmiot badań operacyjnych.
W każdej działalności ludzkiej, a w tym gospodarczej, mamy do czynienia z organizowaniem, planowaniem i kontrolowaniem wykonania wyodrębnionego zbioru czynności. Działalność taka podporządkowana jest określonemu celowi (celom) i opiera się na zadanych zasobach (finansowych lub materialnych) oraz zasilaniu informacyjnym. Istotną sprawą jest zatem sprawne zarządzanie. Do nauk o zarządzaniu należą badania operacyjne (ang. operations research), które mają określony własny przedmiot dociekań, jak również posługują się specyficznymi metodami ilościowymi.
Można powiedzieć, że badania operacyjne są dziedziną nauki zajmującą się analizą celowych działalności (operacji), generowaniem i oceną ilościową różnych decyzji kierowniczych (taktycznych lub strategicznych).
Podstawowym przedmiotem badań operacyjnych są decyzje w warunkach ograniczających. Przy ich analizowaniu w badaniach operacyjnych posługujemy się metodami matematycznymi (szczególnie zaś optymalizacyjnymi), heurystycznymi oraz symulacją komputerową. Do analizy tych decyzji niezbędna jest informacja, której przetwarzanie ułatwia technika komputerowa, stąd jej związek z badaniami operacyjnymi.
Definicja 1. Przedmiot badania operacyjnego jest dziedziną matematyki, która zajmuje się opracowywaniem najlepszych strategii rozwiązania zadań ekonomicznych z ograniczeniami.
Nie należy jednak utożsamiać badań operacyjnych z techniką obliczeniową. Pełni ona jednak rolę służebną wobec badań operacyjnych. W analizie operacji rozważa się pewne systemy decyzyjne. Są to uporządkowane zbiory elementów mających wspólny cel (cele). Rozwój układów gospodarczych, firm, banków itp., jak i technologii coraz bardziej komplikuje relacje między elementami tych systemów. Niezbędne jest zatem dokonanie analizy i zobiektywizowanie ocen podejmowanych decyzji w dziedzinie zarządzania tymi układami. W tym celu została wypracowana określona metodologia badań operacyjnych przydatna w analizie pewnego wycinka rzeczywistości gospodarczej. Sprowadza się ona do następujących etapów:
1) formułowanie problemu decyzyjnego,
2) budowa modelu matematycznego lub jego analogu w wersji symulacyjnej,
3) pozyskanie i przetwarzanie informacji wyjściowej niezbędnej do ustalenia parametrów modelu,
4) procedura obliczeniowa lub postępowanie symulacyjne za pomocą wybranego algorytmu,
5) analiza jakości rozwiązań modelu,
6) weryfikacja modelu — sprawdzenie jego adekwatności,
7) zastosowanie rozwiązania.
W pierwszym etapie określa się opisowo cel (cele) działania, wyodrębnia się czynniki, od których zależy osiągnięcie tego celu. Ustala się zakres zmienności. Ważne jest tutaj wyróżnienie czynników głównych i mniej istotnych, które mogą być pominięte w analizie.
Konstrukcja modelu matematycznego (etap 2) polega na znalezieniu zależności analitycznych odpowiadających sformułowanemu problemowi. Może to być np. zadanie optymalizacyjne, model teorii gier lub model symulacji komputerowej.
Ze struktury modelu decyzyjnego wynika informacja o parametrach, np. o kosztach czy cenach (etap 3). Niekiedy mówi się tutaj o identyfikacji systemu zarządzania.
Etap 4 obejmuje poszukiwanie i wykorzystanie efektywnego algorytmu (sposobu rozwiązywania pewnej klasy zadań).
Analiza rozwiązań (etap 5) powinna być dokonywana z punktu widzenia realności oraz stabilności rozwiązań, tj. odpowiedzi na pytanie, jak dalece rozwiązanie pozostanie aktualne, jeżeli w toku procesu decyzyjnego zmienią się wartości parametrów.
W przypadku niezadowalającej odpowiedzi powinna nastąpić korekta modelu (etap 6), a następnie poszczególne kroki procedury powinny być powtórzone. Uzyskanego rozwiązania nie należy traktować jako gotowej decyzji, lecz jako wskazówkę do jej podjęcia. Aktualnie przyjęło się sformułowanie, że mamy do czynienia z procesem wspomagania decyzji. Wyniki badań operacyjnych stanowią wówczas podstawę odpowiedniego zachowania się podmiotów gospodarczych.
1.1. 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.
Modelowanie problemów decyzyjnych
W wielu różnych sytuacjach podejmujemy decyzje. Sytuacje te nazywamy sytuacjami decyzyjnymi, a osobę podejmującą decyzję — decydentem. Warunki, w jakich działa decydent, nie pozwalają na wybór dowolnej decyzji. Decyzję zgodną z warunkami ograniczającymi nazywa się decyzją dopuszczalną.
Nie każda decyzja dopuszczalna jest równie dobra. W świetle celów, jakie sobie stawia decydent, jedne decyzje mogą być lepsze, inne gorsze. Stąd wynika problem wyboru decyzji najlepszej, zwanej decyzją optymalną. Wybór decyzji optymalnej wymaga przyjęcia określonego kryterium, według którego oceniamy decyzje jako lepsze lub gorsze. Kryterium to nazywamy kryterium wyboru (oceny).
PRZYKŁAD. Możemy podjąć jedną z trzech decyzji inwestycyjnych. Nakłady inwestycyjne oraz oczekiwany roczny zysk osiągnięty z tych inwestycji przedstawiono w tablicy. Która z trzech decyzji jest optymalna?
Tablica
Decyzje |
A |
B |
C |
Nakłady inwestycyjne (min PLN) |
40 |
50 |
30 |
Zyski (min PLN) |
8 |
4 |
6 |
Na pytanie to nie możemy odpowiedzieć, gdyż nie zostało określone żadne kryterium wyboru. Jeżeli kryterium oceny będzie minimalizacja nakładów, to najlepszą decyzją jest decyzja C. Gdy jako kryterium wyboru przyjmiemy maksymalizację zysku, to najlepszą decyzją jest decyzja A. W przypadku maksymalizacji stopy zysku najlepsze są decyzje A i C.
Opis określonej sytuacji decyzyjnej nazywamy problemem (zagadnieniem) decyzyjnym. Dalej będziemy rozpatrywać tylko takie sytuacje, w których warunki ograniczające, kryterium wyboru i decyzje dają się opisać w języku matematycznym. Zapis problemu decyzyjnego w jeżyku maiematycznym to formułowanie modelu matematycznego. Model matematyczny problemu decyzyjnego nazywamy zadaniem decyzyjnym.
Opisanie sytuacji decyzyjnej w języku matematycznym ma na celu sprowadzenie problemu wyboru najlepszej decyzji do rozwiązania pewnego jednoznacznie określonego zadania matematycznego. Aby rozwiązanie takiego zadania rzeczywiście umożliwiło wybór najlepszej decyzji, trzeba je tak sformułować, by dokładnie opisywało ono daną sytuację decyzyjną. Należy zatem ustalić:
1) jakie wielkości mają być wyznaczone i odpowiednio je oznaczyć (tzn. należy podać zmienne decyzyjne],
2) jakie wielkości są dane (określić parametry zadania),
3) jakie warunki ograniczające musi spełnić dopuszczalna decyzja i sformułować je w postaci równań lub nierówności wiążących zmienne decyzyjne (zapisać warunki ograniczające),
4) cel, jaki chce osiągnąć decydent oraz sformułować funkcję zmiennych decyzyjnych określającą stopień osiągnięcia celu (podać funkcję celu).
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).
Warunki ograniczające najczęściej opisywane są za pomocą układów równań lub nierówności. W równaniach tych (lub nierównościach) występować będą pewne wielkości dane, zwane parametrami, oraz wielkości, które należy ustalić, zwane zmiennymi decyzyjnymi.
Oprócz warunków ograniczających w zadaniu decyzyjnym mogą także występować warunki dotyczące znaku zmiennych (np. warunek nieujemności) lub typu zmiennych (np, warunek ich ciągłości, całkowitoliczbowości lub binarności).
Decyzje dopuszczalne utożsamiać będziemy z takim układem wartości zmiennych (układem liczb), które spełniają wszystkie warunki opisujące badaną sytuację. Rolę kryterium wyboru będzie pełnić pewna funkcja zmiennych decyzyjnych mierząca cel, który chce osiągnąć decydent. Funkcję tę nazywa się funkcją celu (junkcją-kryterium).
Wybór decyzji optymalnej polega na ustaleniu takiej decyzji dopuszczalnej, przy której funkcja celu osiąga wartość najkorzystniejszą, tzn. w zależności od badanej sytuacji wartość minimalną lub maksymalną.
Jeżeli przez D oznaczymy zbiór dopuszczalnych decyzji, przez x dowolną decyzję, a przez f(x) — funkcję celu, to zadanie decyzyjne można zapisać następująco:
znajdź taką decyzję dopuszczalną x* ∈ D, że: f (x*} = max{f(x) x∈D} — jeżeli zależy nam na maksymalizacji funkcji celu,
f (x*} = min{f(x) x∈D} - jeżeli zależy nam na minimalizacji funkcji celu.
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.
1.2. 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<n. Wówczas układ ma nieskończenie wiele rozwiązań. I jednocześnie układ (1.29) można przekształcić do postaci:
, i=1,2, ... r (1.41)
Zmienne x1, x2, ... xr nazywają się bazowymi, a xr+1, x2, ... xn — swobodnymi (nie bazowymi).
12
Lekcja 1. Zadania programowania liniowego
1
Lekcja 1. Zadania programowania liniowego
Wyszukiwarka