Kategorie materiałów Ekonomia

Przedmiot: Ekonometria Wróć do kategorii

Ekonomietria - programowanie liniowe (10 stron)

plik Pobierz Ekonomietria - programowanie liniowe (10 stron).doc

schematy i tabele w pliku do pobrania.

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, ...

Ciąg dalszy w pliku do pobrania.

Wkuwanko.pl jako podmiot świadczący usługę hostingu materiałów edukacyjnych nie ponosi odpowiedzialności za ich zawartość.

Aby zgłosić naruszenie prawa autorskiego napisz do nas.

ikona Pobierz ten dokument

Wróć do kategorii

wkuwanko.pl

Wasze komentarze: dodaj komentarz

  • Nie ma jeszcze komentarzy do tego materiału.

Materiały w kategorii Ekonometria [51]

  • podgląd pobierz opis Badania operacyjne [65 stron]
  • podgląd pobierz opis Doświadczenia wieloczynnikowe (10 stron)
  • podgląd pobierz opis Ekonometria - kolokwium
  • podgląd pobierz opis Ekonometria - metoda simplex (14 stron)
  • podgląd pobierz opis Ekonometria - modelowanie
  • podgląd pobierz opis Ekonometria - Prognozowanie [34 strony]
  • podgląd pobierz opis Ekonometria - regresja wieloraka
  • podgląd pobierz opis Ekonometria - wzory
  • podgląd pobierz opis Ekonometria - wzory 2
  • podgląd pobierz opis Ekonometria - wzory 3
  • podgląd pobierz opis Ekonometria - zadania transportowe.doc
  • podgląd pobierz opis Ekonometria [33 strony]
  • podgląd pobierz opis Ekonometria [47 stron]
  • podgląd pobierz opis Ekonometryczna analiza - absolwenci (45 stron)
  • podgląd pobierz opis Ekonomietria - programowanie liniowe (10 stron)
  • podgląd pobierz opis Klasyfikacja modeli ekonometrycznych (9 stron)
  • podgląd pobierz opis Metoda transportowa - zadanie
  • podgląd pobierz opis Model ekonometryczny (8 stron)
  • podgląd pobierz opis Model ekonometryczny - bezrobocie (17 stron)
  • podgląd pobierz opis Model ekonometryczny - Depozyty złotowe i walutowe
[ Misja ] [ Regulamin ] [ Kontakt ] [ Reklama ]   © wkuwanko.pl 2008-2017 właściciel serwisu SZLIFF

Partnerzy: matzoo.pl matmag.pl batmat.pl onlinefm.pl pisupisu.pl Matematyka radio online