9
Lekcja 1. Zadania programowania liniowego
I. Programowanie liniowe.
Lekcja 1. Zadania programowania liniowego.
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.
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.
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. ...
Puchaczo_o