2. Model planowania zapasów dopuszczający niedobór zapasów
Przyczyny niedoborów:
związane z mobilnością
w wyniku zakłóceń produkcyjnych (owe zakłócenia mogą powodować niedobór, pojawi się koszt braków - trzeba będzie dokupić wówczas po cenach wyższych oraz koszt utraconych możliwości powiększający koszt niedoboru)
Przyjmujemy założenia z modelu I (klasycznego):
zapotrzebowanie na rozpatrywany zasób przypadające na okres [0,T] jest znane i wynosi Q
zużycie zasobów jest równomierne w czasie
zakup zasobu w okresie [0,T] dokonywany jest n razy w jednakowych odstępach czasu to gdzie to=
, w partiach w o jednakowej wielkości S=
zamówienia składane są wyprzedzająco tak, aby dostawa kolejnej partii nastąpiła w momencie zużycia poprzedniej
W okresie [0,T] cena jednostkowa zasobu nie ulega zmianie
Koszt magazynowania jest wprost proporcjonalny do wielkości zapasu
Koszt realizacji zakupu nie zależy od wielkości partii i dla pojedynczej partii wynosi K.
Natomiast założenie e zmienia się na : dopuszczalny jest niedobór zapasu, przy czym jednostkowy koszt tego niedoboru C2 jest wprost proporcjonalny do wielkości niedoboru.
Średni zapas przez pierwsze t' jednostek każdego cyklu wynosi Z=
przy czym udział czasu w przedziale [0,T] w ciągu którego zapas jest dodatni wynosi
.
Celem jest wyznaczenie S' i S w taki sposób aby łączne koszty magazynowania, realizacji, zakupu oraz niedoboru zapasu w okresie [0,T] były minimalne stąd
biorąc pod uwage, że
=
mamy:
koszt realizacji zakupów
Następnie należy określić koszt niedoboru zapasu
Wynosi on
funkcja celu jest zatem następująca:
Funkcja osiąga minimum dla takich S i S', dla których:
;
z ostatniego wynika, że:
(*)
Z pochodnych oraz z tego, że
mamy: SS'=
(**)
Ze wzorów (*) i (**) otrzymamy szukane optymalne S i S'
14. Podstawowe tw. dot. rozwiązań liniowych modeli decyzyjnych (PYT.2.2+2.5)
Zbiór rozwiązań dopuszczalnych może być zbiorem ograniczonym, nieograniczonym lub zbiorem pustym (oznacza to, że źle postawiliśmy problem decyzyjny).
Twierdzenie I mówi, że zbiór rozwiązań dopuszczalnych modelu programowania liniowego jest zbiorem (wielobokiem) wypukłym
Twierdzenie II Funkcja celu modelu programowania liniowego osiąga wielkość optymalną na wierzchołku zbioru rozwiązań dopuszczalnych modelu
Twierdzenie III Jeżeli w modelu programowania liniowego istnieją co najmniej 2 rozwiązania optymalne, o różnych wartościach wektorów zmiennych decyzyjnych, to każda wypukła kombinacja tych rozwiązań jest również optymalnym rozwiązaniem tego modelu.
Twierdzenia dla modeli dualnych:
1) Zadanie pierwotne jest zadaniem dualnym do swojego zadania dualnego (i jest to wtedy model pierwotny)
2) Jeżeli zadanie pierwotne i zadania dualne mają rozwiązanie dopuszczalne to obydwa mają rozwiązanie optymalne. Jeżeli natomiast jedno z nich nie ma rozwiązania dopuszczalnego to obydwa nie mają rozwiązania optymalnego.
3) Jeżeli x1,x2…xn jest rozwiązaniem dopuszczalnym zadania pierwotnego, a y1, y2,… yn jest rozwiązaniem dopuszczalnym zadania dualnego to pomiędzy wartościami funkcji celu zachodzi nierówność
L(x)
L(y) jeżeli L(x) max i odwrotnie.
4) Jeżeli istnieją dwa takie rozwiązania dopuszczalne x1,x2…xn oraz y1, y2,… yn ze funkcje celu są sobie równe L(x)=L(y) to obydwa rozwiązania są rozwiązaniami optymalnymi.
5) Jeżeli x1,x2…xn jest rozwiązaniem dopuszczalnym zadania prymarnego oraz y1, y2,… yn jest rozwiązaniem dopuszczalnym zadania dualnego to aby rozwiązania te były rozwiązaniami optymalnymi wystarczy że są spełnione następujące warunki:
|
|
yi>0 |
xi>0
|
22. Definicja współczynnika obsługi
Współczynnik obsługi (
) - iloraz czasu, w ciągu którego zapas jest dodatni, do całkowitego czasu (w warunkach zaopatrywanego modelu)
27. Istota programowania liniowego
Modele programowania liniowego są jednymi z najbardziej popularnych i uniwersalnych struktur modelowych służących matematycznej analizie ekonomicznych problemów decyzyjnych. Ich rozpowszechnienie uwarunkowane jest z jednej strony dużymi możliwościami liniowego przybliżenia większości procesów gospodarczych, z drugiej strony prostotą posługiwania się modelami tego typu. Proces kwantyfikacji problemu decyzyjnego oraz budowa modelu liniowego podlega ogólnym regułom budowy modelu matematycznego. Należy jedynie podkreślić warunki szczególne, którymi powinna cechować się sytuacja decyzyjna, aby możliwe było zastosowanie optymalizacyjnych modeli liniowych.
Ogólnie model liniowy można zapisać:
1) funkcja celu
f(x)=c1x1+ c2x2+...+ ckxk=
2) warunki ograniczające
a11x1+ a12x2+...+ a1kxk
a21x1+ a22x2+...+ a2kxk
...
am1x1+ am2x2+...+ amkxk
3)warunki brzegowe
xj
0 ; j=1,2,...k
cj-parametry funkcji celu; aij- parametry ograniczające; bij - parametry informujące o wielkości i-tego ograniczenia
28. Metoda simplex - wyjaśnij jej istotę
Etap I:
Polega na wyborze bazowego rozwiązania oraz ocenie jego optymalności. Wykonujemy nastepujące czynności:
Przyjęcie bazowego wstępnego rozwiązania dopuszczalnego
Budowa tablicy simplexowej dla przyjętego rozwiązania bazowego:
- jeżeli zgodnie z przyjętym kryterium optymalności rozwiązanie bazowe jest optymalne to postępowanie zakończone (zależy od delty)
- jeżeli stwierdzimy że rozwiązanie bazowe nie jest optymalne przechodzimy do etapu II
Etap II:
Polega na wyznaczeniu kolejnego poprawionego rozwiązania bazowego
Ustala się zmienną, którą wprowadzimy do nowego rozwiązania bazowego
Ustala się zmienną którą należy usunąć z poprzedniego rozwiązania
Wyznaczenie wartości zmiennych nowego rozwiązania bazowego poprawionego do odpowiadającej nowemu rozwiązaniu tablicy simplexowej
Etap III:
Dla rozwiązania uzyskanego w etapie II powtarzamy postępowania od pkt 2 etapu I aż do momentu uzyskania rozwiązania optymalnego.
31. Zasada optymalności Bellmana
„Strategia optymalna ma tą własność, że nie niezależnie od stanu początkowego i decyzji początkowej pozostałe decyzje muszą stanowić ciąg optymalny ze względu na stan wynikający z pierwszej decyzji”
Zasada optymalności pozwala na dekompozycję zadania wyjściowego na ciąg powiązanych ze sobą prostych zadań, które rozwiązujemy kolejno rozpoczynając od ostatniego etapu.
32. Postać kanoniczna, standardowa i bazowa (funkcji?) (PYT. 6.5)
Jeżeli w modelu warunki ograniczające mają charakter nierówności to taki model liniowy ma postać standardową. Natomiast jeśli mają postać równań to model ma postać Kanoniczną.
Każdą postać standardową można sprowadzić do postaci kanonicznej poprzez wprowadzenie do modelu postaci standardowej dodatkowych zmiennych (swobodnych, bilansowych)
n - liczba zmiennych w modelu; m - liczba równań ; n>m
Postać standardowa 9x1+6x2max
|
Postać kanoniczna 9x1+6x2max
|
35. Opisać metodę graficzną
Polega na szukaniu rozwiązania na płaszczyźnie układu współrzędnych. Możliwa jest do zastosowania wtedy, gdy w modelu występują 2 zmienne decyzyjne.
x1 - ilość wyrobu I
x2 - ilość wyrobu II
Z = 9x1 + 6 x2 --> max
I 3x1 + 6 x2 ≤ 24, *(0, 4); (8, 0)
II 8x1 + 4 x2 ≤ 40, *(0,10); (5, 0)
III 9x1 + 3 x2 ≤ 27, *(0, 9); (3, 0)
1) Należy znaleźć zbiór rozwiązań dopuszczalnych - proste I, II, III umieszczamy na układzie współrzędnych(*)
Wszystkie punkty pod I, II, III nierównością wraz z krawędziami , należące do I ćwiartki spełniają tą nierówność.
2) Szukamy teraz części wspólnej (zbioru rozwiązań dopuszczalnych).
3) Równanie kierunkowe prostej: y = ax + b
Z = 9x1 + 6 x2
-6 x2 = 9 x1 - Z
x2 = -9/6 x1 + Z/6
x2 = -3/2 x1 + Z/6 --> równ. kierunkowe f. celu
Z = 0
x2 = -3/2 x1 (0,0),(2,-3) - rysujemy taką prostą na układzie współrzędnych. Następnie przesuwamy ją równolegle w stronę rozwiązań dopuszczalnych. Do przecięcia których dwóch prostych (rozwiązań dopuszczalnych) prosta ta dojdzie (rozwiązanie optymalne), je bierzemy pod uwagę w celu rozwiązania zadania. Wyznaczamy z nich wartość x1 i x1.
Część wspólna wszystkich wyznaczonych półpłaszczyzn wyznacza nam zbiór rozwiązań dopuszczalnych. Wszystkie proste wyznaczone z funkcji celu nazywa się izokwantami lub liniami izocelowymi. ......................................
29. Zmienne decyzyjne w przekroju przez wszystkie modele.
a) Optymalny wybór asortymentu produkcji,
b) Problem mieszanki,
c) Wybór procesu technologicznego,
ad a) Optymalny wybór asortymentu produkcji,
Zakładamy, że zakład może produkować n wyrobów. Do ich produkcji zużywane są różne środki produkcji, z których część (m) jest dostępna w ograniczonych ilościach. Dane są normy zużycia środków produkcji na jednostkę każdego wyrobu, dane są zasoby środków produkcji oraz ceny bądź zyski jednostkowe. Mogą być znane informacje dotyczące popytu produkowanego wyrobu oraz minimalne ilości wyrobów, jakie trzeba wyprodukować (podaż). Które wyroby i w jakich ilościach produkować aby nie przekraczając posiadanych zasobów środków produkcji maksymalizować przychód (lub zysk) z ich sprzedaży
MODEL:
(j=1,2,…n)
- zużycie i-tego środka produkcji na wytworzenie jednostki j-tego wyrobu
- posiadany zasób i-tego środka produkcji
- cena lub zysk jednostkowy ze sprzedaży j-tego wyrobu
- minimalna ilość ilość-tego wyrobu jaką trzeba wyprodukować
- maksymalna ilość j-tego wyrobu jaką trzeba sprzedać (ograniczenie popytowe)
- wielkość produkcji j-tego wyrobu
ad b) Problem mieszanki
W zagadnieniu optymalnego składu mieszanki, podejmujący decyzję pragnie określić jakie ilości podstawowych surowców należy zakupić i zmieszać aby otrzymać produkt o pożądanym składzie chemicznym, przy możliwie najniższych kosztach zakupu surowców.
Jednym z wariantów problemów mieszanek jest zagadnienie diety.
Aby zaspokoić potrzeby organizmu trzeba mu dostarczyć w różnych ilościach rozmaitych składników odżywczych. Składniki te są zawarte w różnych produktach żywnościowych
Zakładamy, że mamy do dyspozycji n-produktów żywnościowych, w których powinno być zawarte m-składników odżywczych
Model:
(j=1,2,…n)
- zawartość i-tego składnika odżywczego w jednostce jednostce-tego produktu (i=1,2,…m)
- tak zwana norma żywienia, czyli ilość i-tego składnika
- cena j-tego produktu żywnościowego
- minimalna ilość ilość-tego produktu, jaką powinno się spożywać
- maksymalna ilość j-tego wyrobu jaką organizm może przyjąć
ad c) Wybór procesu technologicznego
Zakład ma proukować r- wyrobów w ilości B1,B2,Br do wytworzenia tych wyrobów można stosować n-procesów technologicznych, stosując j-ty proces technologiczny z jednostkową intensywnością uzyskuje się określone produkty w ilościach aij i ponosi koszty cj
(j=1,2,…r)
33. Ogólny model transportowy
Jako jedno z zagadnień programowania liniowego. Po raz 1 zostało sformułowane przez Hitchcok'a w 1941r.
Ekonomiczne zagadnienie transportowe można przedstawić w następujący sposób:
Danych jest m-dostawców (i) pewnego jednorodnego produktu. Zasoby tego produktu znajdujące się u i-tego dostawcy wynoszą ai. Produkt jest przeznaczony dla n-odbiorców (j) których zapotrzebowanie wynosi odpowiednio (b1,b2…bn). Koszt transportu jednostki tego produktu od i-tego do j-tego odbiorcy wynosi cij.
Należy określić plan przewozów pomiędzy dostawcami a odbiorcami, aby uwzględnić dostępne zasoby dostawców i wymagane zapotrzebowania odbiorców tak, aby łączne koszty transportu były minimalne.
Xij - zmienna decyzyjna, określająca wielkość przewozu od i-tego dostawcy do j-tego odbiorcy
Przed przystąpieniem do matematycznej budowy modelu musimy określić, czy zagadnienie jest zbilansowanie czy niezbilansowane (zamknięte czy otwarte)
Jeżeli
to mamy zagadnienie transportowe Zbilansowane
to model matematyczny może być zapisany:
K- łączny koszt przewozu
(i=1,2...,m) warunki ograniczające ze strony dostawców
(j=1,2...n) warunki ograniczające ze strony odbiorców
xij
0
Jeżeli
to mamy zagadnienie transportowe NIEzbilansowane
K- łączny koszt przewozu
(i=1,2...,m) zmieniły się warunki dostawców, NADWYŻKA PODAŻY nad popytem
(j=1,2...n)
Jeżeli
to mamy zagadnienie transportowe NIEzbilansowane
(i=1,2...,m)
(j=1,2...n) zmieniły się warunki obiorców, NADWYŻKA POPYTU nad podażą
36.Wyjaśnić pojęcia: koszt magazynowania, koszt realizacji zakupu, koszt niedoboru (braku) zapasów, współczynnik obsługi.
Koszt magazynowania - koszty zamrożenia środków obrotowych + amortyzacja magazynu i urządzeń transportowych + koszty operacyjne
Koszt realizacji zakupu - koszty zamówienia + koszty transportu do magazynu
Koszt braku (niedoboru) zapasów - dodatkowe koszty zakupu w warunkach pośpiechu + koszty strat z tytułu opóźnień lub utraconych możliwości produkcyjnych
Współczynnik obsługi (
) - iloraz czasu, w ciągu którego zapas jest dodatni, do całkowitego czasu (w warunkach zaopatrywanego modelu)
37.Ogólna charakterystyka programowania dynamicznego.
Jak decyzja podejmowana jest jednorazowo to --> zadanie statyczne.
Jak decyzja jest podejmowana wielokrotnie --> zadanie dynamiczne.
Jest to jedna z technik matematycznych, którą można wykorzystać do zarządzania procesami wieloetapowymi. Istnieje wiele zagadnień, których decyzji nie podejmujemy jednorazowo, lecz wielokrotnie, dlatego nazywa się je wieloetapowymi procesami decyzyjnymi.
Na ocenę interesującego nas procesu mają wpływ wszystkie decyzje podejmowane w trakcie jego trwania. Chcąc zoptymalizować wieloetapową funkcję celu obejmującą wszystkie etapy nie wystarczy rozwiązać ciągu zadań jednoetapowych, lecz trzeba na rozwiązanie popatrzeć kompleksowo.
Skutki decyzji podjętych w etapach wcześniejszych mogą w istotny sposób zmieniać możliwości decyzyjne w następnych etapach.
Na początku każdego etapu proces charakteryzowany jest wielkościami nazywanymi zmiennymi stanu. Decydent na początku każdego etapu ma możliwość obserwowania tych wielkości.
W kolejnych etapach istnieje możliwość sterowania przebiegiem takiego procesu przez wybór dopuszczalnych wartości zmiennych decyzyjnych. Zbiór tych wartości uzależniony jest od stanu w jakim znajduje się proces.
Podjęcie decyzji etapowej powoduje, że na początku następnego etapu proces znajduje się w kolejnym stanie.
Funkcję opisującą zależność między stanem procesu na początku następnego etapu a stanem procesu na początku etapu i podjętą decyzją nazywamy funkcją przejścia. Jednocześnie z przejściem takim związana jest etapowa korzyść lub strata.
Przy rozwiązywaniu zadań używana jest zasada optymalności Bellmana, która pozwala na dekompozycję zadania wyjściowego na ciąg powiązanych ze sobą prostych zadań, które rozwiązujemy kolejno rozpoczynając od ostatniego etapu. Przykładem zadania tego typu jest problem dyliżansu (należy przetransportować ładunek z punktu A do E. Układ komunikacyjny między punktami wraz z odległościami jest dany. Zadanie polega na wyborze najkrótszej trasy.).
38.Metody uzyskiwania początkowych dopuszczalnych rozwiązań bazowych w zagadnieniach transportowych (opisać te metody).
a) Metoda kąta północno-zachodniego (lewego górnego rogu)
Zaczynamy wyznaczanie od lewego górnego rogu, czyli od D1 do O1. itd.
b) Metoda minimalnego elementu w macierzy kosztów jednostkowych
Zaczynamy wyznaczanie początkowych dopuszczalnych rozwiązań od komórki macierzy, gdzie koszt jednostkowy jest minimalny
c) metoda minimalnego elementu w wierszu macierzy kosztów jednostkowych
d) metoda minimalnego elementu w kolumnie macierzy kosztów jednostkowych
48. Czym różni się rozwiązanie dopuszczalne od bazowego liniowego modelu.
Rozwiązanie dopuszczalne - to takie, które spełnia wszystkie warunki ograniczające i brzegowe. Wśród r. dopuszcz. wyróżniamy rozw. optymalne, które optymalizuje funkcję celu - jest to najlepsze rozwiązanie.
Definicja: Rozwiązanie bazowe - nazywa się dowolne rozwiązanie uzyskane przez podstawienie (przyjęcie) za n-m zmiennych 0 i rozwiązanie układu równań ze względu na pozostałe m-zmiennych.
Rozwiązań bazowych jest skończona liczba.
Rozwiązań jest tyle, ile jest kombinacji
, np. n=5, m=3
Rozwiązanie bazowe może być dopuszczalne bądź niedopuszczalne. Nie wszystkie rozwiązania bazowe są rozwiązaniami dopuszczalnymi bo nie bierzemy pod uwagę warunków brzegowych.
44. Opisać model klasyczny (programowanie sieciowe)
Założenia:
zapotrzebowanie na rozpatrywany zasób przypadające na okres [0,T] jest znane i wynosi Q
zużycie zasobów jest równomierne w czasie
zakup zasobu w okresie [0,T] dokonywany jest n razy w jednakowych odstępach czasu to gdzie to=
, w partiach w jednakowej wielkości S=
zamówienia składane są wyprzedzająco tak, aby dostawa kolejnej partii nastąpiła w momencie zużycia poprzedniej
zapotrzebowanie w każdym momencie okresu [0,T] musi być zaspokojone, tzn. nie dopuszczany jest niedobór zapasu.
W okresie [0,T] cena jednostkowa zasobu nie ulega zmianie
Koszt magazynowania jest wprost proporcjonalny do wielkości zapasu
Koszt realizacji zakupu nie zależy od wielkości partii i dla pojedynczej partii wynosi K.
Niech D1 - oszt magazynowania w okresie [0,T] wynosi:
D1=C1Z
Z- średnia wielkość zapasu w przedziale [0,T]
Z Założenia (g) i S=
mamy: Z=
=
Czyli D1=C1
D2- koszt realizacji zakupów
Z założenia (h) S=
jest D2=K*n=K*
Problem polega na wyznaczeniu S, dla którego łączne koszy D=D1+D2 minimalne czyli:
D=c1
+K
--> min
Stąd otrzymuje się wzór na optymalną wielkość partii
--> Wzór WILSONA
49. Na czym polega wybór decyzji za pomocą modelu decyzyjnego? (PYT. 4.5)
Trzeba określić, oszacować, zmierzyć parametry. Następni musimy sformułować zależności w postaci funkcji matematycznych. Model musi być tak zapisany żebyśmy mogli go rozwiązać.
Budowa modeli decyzyjnych jest strukturą formalną odzwierciedlającą istotne cechy rzeczywistej sytuacji decyzyjnej (Może być sformułowana w różnej postaci)
Matematyczna postać modelu decyzyjnego:
K=f(D,z)
F=(D,z)
0
D=[x1,x2,…xk]
K - pewne kryterium, funkcja zmiennych decyzyjnych i parametrów - parametrów korzyści (celu), które zależą od:
D- wektor zmiennych decyzyjnych - co do których podejmujemy decyzje (niewiadome)
Z - zbiór wszystkich parametrów opisujących stany ( środowisko) warunków zewnętrznych
F - układ relacji, które stanowią układ warunków, które muszą być spełnione aby zapewnić wykonalność podjętej decyzji - warunki ograniczające.
52. Metoda eliminacji Gaussa-Jordana i tw. o optymalnym rozwiązaniu bazowym (PYT. 6.1)
Metoda eliminacji Gaussa-wśród wekt. A poszukuje się wektorów liniowo niezależnych=wektorów bazowych.
Tw: Jeżeli zadanie programowania liniowego ma rozwiązanie optymalne to ma także rozwiązanie optymalne - bazowe
Wniosek: rozwiązania optymalnego należy szukać wśród rozwiązań bazowych, których liczba jest skończona.
Definicja: Rozwiązanie bazowe - nazywa się dowolne rozwiązanie uzyskane przez podstawienie (przyjęcie) za n-m zmiennych 0 i rozwiązanie układu równań ze względu na pozostałe m-zmiennych.
Rozwiązań bazowych jest skończona liczba.
Rozwiązań jest tyle, ile jest kombinacji
, np. n=5, m=3
55. Programowanie liniowe w liczbach całkowitych
Jeżeli rozwiązanie optymalne wychodzi niecałkowite to w wielu przypadkach można jako rozwiązanie przybliżone przyjąć najbliższe nieujemne liczby całkowite spełniające warunki ograniczające zadania.
Istnieją jednak takie przypadki w których zaokrąglenie rozwiązań prowadzi do uzyskania decyzji dopuszczalnych bardzo odległych od optymalnych. W takiej sytuacji model należy poszerzyć o warunki całkowitej liczebności.
DEF 1
Dwie liczby a i b należące do zbioru liczb wymiernych nazywamy kongruentnymi (odpowiednimi)<=> gdy różnica tych liczb jest liczbą całkowitą
np.
DEF2
Część całkowita liczby wymiernej a nazywamy największą liczbę całkowitą nie większą niż a. Oznaczamy ją symbolem [a]
[a]=a jeżeli a jest liczbą całkowitą
[2,3]=2 [0,3]=0 [-0,3]=1 [-1,5]=2
DEF 3
Częścią ułamkową liczby wymiernej a nazywamy liczbę {a} spełniającą warunek {a}=a-[a]
{2,3}=0,3 ponieważ 2,3-2=0,3
{1}=0 1-1=0
{-0,6}=0,4 -0,6-(-1)=0,4
{-1,5}=0,5 -1,5-(-2)=0,5
Własności części ułamkowej liczb wymiernych a i b
=> Jeżeli dwie liczby wymierne są kongruentne to ich części ułamkowe są sobie równe tj.
Jeżeli
Np.
stąd
=> część ułamkowa sumy dwóch liczb wymiernych jest kongruentna sumie części ułamkowych tych liczb tj:
{a+b}
{a}+{b}
np.
{2,6+(-0,4)}=0,2
{2,6}+{-0,4}=0,6+0,6=1,2
Stąd 0,2
1,2
=> iloczyn liczby całkowitej przez dowolną liczbę wymierną jest kongruentny części ułamkowej tego iloczynu a ten ostatni kongruentny iloczynowi liczby całkowitej przez część ułamkową danej liczby wymiernej tj.:
(Ca
{ca}
c{a})
np.
;
;
Stąd