1. Wyjaśnij znaczenie słowa liniowe w nazwie programowanie liniowe.

Programowanie liniowe to klasa problemów programowania matematycznego, w której wszystkie warunki ograniczające oraz funkcja celu mają postać liniową. Warunki ograniczające mają postać:

Znaleźć maksimum (minimum) funkcji:

przy założeniu że zmienne x₁ ,x₂,...., x_n czynią zadość następującym warunkom:

oraz

Programowanie liniowe, maksymalizacja lub minimalizacja funkcji wielu zmiennych, gdy zmienne te, lub niektóre z nich, podlegają liniowym warunkom ograniczającym w postaci równań lub nierówności. Nazwa "programowanie" wskazuje w tym kontekście na schemat działań.

Program liniowy- model, w którym zarówno warunki ograniczające jak i funkcja celu są funkcjami linowymi

2. Opisz wykorzystanie programowania liniowego do zagadnienia transportowego?

np. transport cukru z cukrowni do sklepów

funkcja celu: minimalizacja kosztów transportu;

warunki ograniczające:

1. Zamówienie z punktu widzenia odbiorcy;

2. Możliwości dostawcy;

3. Stan magazynów;

Zadania transportowe możemy podzielić na dwa rodzaje, zadania otwarte i zamknięte(zbilansowane).

Zadanie zbilansowane oznacza, że $\sum_{i = 1}^{m}a_{i} = \sum_{j = 1}^{n}b_{j}$.

Do zadania transportowego wprowadzamy zmienne decyzyjne.

Model matematyczny zamkniętego zagadnienia transportowego (ZZT) np.:

$$\sum_{i = 1}^{m}{\sum_{j = 1}^{n}{c_{\text{ij}}x_{\text{ij}}} \rightarrow \min}$$

$$\sum_{i = 1}^{m}{x_{\text{ij}} = a_{i}}\text{\ \ \ \ \ \ }\left( i = 1,\ldots.,m \right)$$

$$\sum_{j = 1}^{n}{x_{\text{ij}} = b_{j}\text{\ \ \ \ \ \ }\left( j = 1,\ldots.n \right)}$$

x_ij ≥ 0     (i=1,….m;j=1….n)

Jest liniowe zadanie decyzyjne, a więc można je rozwiązać metodą simpleks.

Zadania transportowe są odmianą zadań programowania liniowego, zarówno funkcja celu jak i warunki mają postać liniową.

3. Opisz wykorzystanie programowania liniowego do zagadnienia rozkroju materiałów?

np. krojenie prętów jest to

1. rozkład jednowymiarowy:

2. funkcja celu: minimalizacja zużycia prętów;

warunek ograniczający: wycięcie ilości prętów zgodnie z zamówieniem

rozkład dwuwymiarowy- obywa się w dwóch wymiarach, np. przemysł włókienniczy;

Model rozkroju nazywany jest również w literaturze modelem minimalizacji odpadów. Do rozwiązywania tych problemów wykorzystuje się metodę programowania liniowego. Liniowy model ma następującą postać:

x_j ≥ 0

F =

gdzie:

a_ij – liczba sztuk elementu „i” otrzymana z jednostki materiału wyjściowego przy danej strategii rozkroju „j”

x_j – liczba jednostek materiału wyjściowego, która będzie rozkrojona daną strategią „j”

b_i – założona liczba elementów

c_j – odpad jednostki materiału wyjściowego przy strategii rozkroju „j”

Przykład nr 1

Proces technologiczny wymaga, żeby do wytworzenia pewnego produktu gotowego wytwarzać trzy rodzaje elementów. Mogą to być elementy drewniane, papierowe ewentualnie metalowe – w każdym razie są wycinane z jednorodnego arkusza danego materiału o ustalonych wymiarach: 5 metrów na 10 metrów. Element pierwszy e1 jest trapezem prostokątnym: podstawa dolna 5 m, podstawa górna 3 m, wysokość 4 m. Drugi element e2 jest prostokątem o wymiarach: 3m x 4m. Trzeci element e3 jest również prostokątem o wymiarach: 2m x 5m. Wiadomo, że należy wytworzyć co najmniej 12000 elementów e1, co najmniej 6000 elementów e2, co najmniej 8000 elementów e3.

Należy zbudować zadanie PL w celu udzielenia odpowiedzi na pytanie: jak rozcinać standardowe arkusze, aby zminimalizować liczbę zużytych arkuszy i wytworzyć wymaganą liczbę wymienionych, trzech elementów?

4. Wyjaśnij na przykładzie znaczenie pojęcia obszar rozwiązań dopuszczalnych.

Rozwiązanie dopuszczalne - układ zmiennych , które spełniają wszystkie nierówności, jest to taki układ decyzyjnych, który spełnia wszystkie ograniczenia ; np. x1=0, x2=0, x3=0 , x4=0 dopuszcza teoretycznie istnienie takich zmiennych, albo np.: x1=3, x2=2, x3=0 x4=1

5. Wyjaśnij na przykładzie znaczenie pojęcia rozwiązanie optymalne.

Rozwiązanie optymalne - rozwiązanie dopuszczalne, które gwarantuje ekstremum funkcji celu. Jeżeli rozwiązanie dopuszczalne jest zbiorem pustym, to rozwiązanie optymalne nie istnieje! Ekstremum oznacza minimum lub maksimum funkcji.

Np. Funkcja celu : Z=4x1+5x2+9x3+2x4->max

to rozwiązanie optymalne jest w 3 iteracji i wyniki to x1=7,14 x2=0, x3=7,86 x4=0

F.C=99,29

6. Co to jest rozwiązanie kompromisowe (optymalne w sensie Pareto)?

Programowanie w sensie Pareto należy do programowania wielokryterialnego. Czasem istnieje kilka kryteriów oceny, która z decyzji dopuszczalnych jest najlepsza. Każde kryterium może wskazywać inne rozwiązanie optymalne. Są to optima cząstkowe. W takiej sytuacji musimy znaleźć kompromis – ustalić jedną (albo zbiór) decyzję/rozwiązanie kompromisowe.

Służą ku temu różne metody, np.:

Rozwiązanie optymalne w sensie Pareto/ optimum Pareto/ zbiór decyzji sprawnych / zbiór decyzji efektywnych / zbiór decyzji niezdominowanych – Czyli rozwiązanie najlepsze z punktu widzenia wszystkich funkcji celu - takie rozwiązania, że nie istnieje żadne inne rozwiązanie od nich lepsze chociaż dla jednej funkcji celu, przy pozostałych funkcjach przynajmniej zachowujących swoje wartości. Innymi słowy - jest to takie rozwiązanie (tak dobre rozwiązanie), że żeby je polepszyć (tzn. znaleźć inne lepsze rozwiązanie) dla jednej funkcji celu to tylko kosztem pogorszenia dla innej funkcji.

Cechy rozwiązania optymalnego Pareto?

1. zaletą rozwiązania optymalnego w sensie Pareto jest to że wyznaczenie rozwiązania najlepszego nie wymaga uzyskania informacji o preferencjach

2. wyznaczając decyzję Pareto-optymalne ograniczamy się do operacji porównawczych, czyli w skali porządkowej. Jest to taka skala, w której w zależności od rozpatrywania cechy decyzja A jest lepsza od decyzji B. Wyróżniamy wobec tego:

a) rozwiązanie zdominowane- rozwiązanie , które jest gorsze od innego, z punktu widzenia wszystkich kryteriów optymalizacji;

b) rozwiązanie dominujące-jest lepsze od innego z punktu widzenia wszystkich kryteriów optymalizacji;

7. Wyjaśnij na przykładzie znaczenie pojęcia funkcja celu.

Funkcja Celu - kryterium według którego można oceniać dokonywany wybór rozwiązania najlepszego spośród dopuszczalnych rozwiązań czyli jak dany system w procesie swojego działania zbliża się do osiągnięcia wyznaczonego celu. FC określa więc zależność między celem systemu a środkami służącymi do jego realizacji.

Np.: przedsiębiorstwo produkuje wyroby i za każdy wyrób ma zysk f celu będzie maksymalny zysk za każdy wyrób

Z=4x1+6x2+3x3+12x4->max

8. Wyjaśnij na przykładzie znaczenie pojęcia warunki ograniczające.

Warunkami ograniczające to przeszkody jakie mogą sie pojawić w trakcie realizacji celu.

Np.: limity przedsiębiorstwo produkuje wyroby z limitami 90000 i 120000

Warunki ograniczające:

X1+ x2+x3+x4<=90000

2x1+2x2+2x3+2x4<=120000

9. Co to jest analiza postoptymalizacyjna?

Analiza wrażliwości (postoptymalizacyjna)-zwana zwykle często analizą wrażliwości, jest to analiza prowadzona po uzyskaniu rozwiązania optymalnego. Chodzi w niej o ustalenie, jak zmieni się rozwiązanie optymalne i jakie będą tego skutki, jeżeli zmienią się parametry zadania. (odpowiada na pytanie w jakich granicach mogą zmieniać się dane liczbowe, aby uzyskane rozwiązanie pozostało optymalne)

Zachodzi jedno z trzech przypadków:

1. rozwiązywanie optymalne się nie zmienia(zmiany parametrów są nieistotne);

2. rozwiązywanie optymalne zmienia się w sposób nieprzewidziany (zmiana parametrów jest istotna);

3. rozwiązywanie optymalne zmienia się w sposób nieprzewidziany(zmiana parametrów jest nadmierna), co wymaga rozwiązanie zadania jeszcze raz, chociaż nie zawsze od początku

Rozwiązanie jest wrażliwe , kiedy współczynnik początkowy przy funkcji celu jest blisko swojej granicy.

Np. Analiza wrażliwości dla wyrobu B.

C₂ = 5 C₂ ϵ (−∞;5, 4>

10. Wyjaśnij pojęcia: przestrzeń decyzji i przestrzeń kryteriów dla problemu optymalizacji wielokryterialnej.

Problem optymalizacji wielokryterialnej to taki rodzaj zadań, w których należy dokonać wyboru najlepszego wyrobu ze zbioru wyrobów, który każdy jest scharakteryzowany przez wiele cech. Jeżeli przy podejmowani decyzji kierujemy się jedną kryteria, to konstruujemy model sytuacji decyzyjnej i podejmujemy próbę wyznaczania rozwiązania optymalnego. Natomiast,, gdy mamy do czynienia z wieloma kryteriami, nie istnieje jednoznaczne rozwiązanie. Konieczne jest uzyskanie informacji na temat ważności kryteriów. Przyjmujemy, że podejmujemy decyzje dopuszczalną x ϵ D, chce w maksymalny sposób zrealizować cele f₁….f_K., są mierzalne( mogą być wyznaczone przez funkcje liczbowe). Ocena decyzji to y ϵ  S.

Optymalizacje wielokryterialną możemy rozpatrywać na:

1. przestrzeń decyzyjną- jest to zbiór decyzji. Jeżeli jest to zbiór dyskretny to wyznacza „najlepszą” decyzję ze względu na rozpatrywany zbiór kryteriów, jest to zbiór D, do którego należą wszystkie x, czyli decyzje dopuszczalne.; zbiór ten może być dyskretny lub ciągły;

2. przestrzeń kryteriów- zbiór ocen decyzji, jest to zbiór S, wszystkie y, czyli zbiór wszystkich ocen; zbiór ten może być domknięty lub ograniczony.

Twierdzenie 1

Zbiór rozwiązań dopuszczalnych zadania w przestrzeni kryterialnej jest wielościanem wypukłym. Każdy wierzchołek tego wielościanu jest obrazem pewnego wierzchołka zbioru decyzji dopuszczalnych w przestrzeni decyzyjnej, natomiast pozostałe punkty to zbiór wszystkich kombinacji wypukłych punktów wierzchołkowych.

11. Co to jest rozwiązanie zdominowane?

Rozwiązanie jest zdominowane, jeśli istnieje inne rozwiązanie nie gorsze z punktu widzenia żadnego kryterium i lepsze w co najmniej jednym kryterium. Rozwiązanie Z jest zdominowane, jeśli istnieje dopuszczalne rozwiązanie X, które:

· Jest co najmniej tak dobre jak Z ze względu na wszystkie wymiary, tzn dla każdego celu f(i=1,…,m)

fx≤fz dla wszystkich 1≤i≤m

· Ściśle lepsze od z co najmniej ze względu na jeden cel „i”

fx<fz dla pewnego 1≤i≤m

12. Zastosowanie centralnego twierdzenia granicznego rachunku prawdopodobieństwa do budowy generatora liczb losowych o rozkładzie normalnym.

Generator liczb losowych- technika symulacyjna, w exelu LOS()-to generator o rozkładzie jednostajnym na odcinku (0,1).

W symulacjach komputerowych zdarza się, że potrzebujemy wygenerować wartości zmiennej losowej o rozkładzie normalnym. Istnieje kilka metod, najprostszą z nich jest odwrócenie dystrybuanty standardowego rozkładu normalnego.

Jedną z najważniejszych własności rozkładu normalnego jest fakt, że, przy pewnych założeniach, rozkład sumy dużej liczby zmiennych losowych jest w przybliżeniu normalny. Jest to tak zwane centralne twierdzenie graniczne.

Centralne twierdzenie graniczne – jedno z najważniejszych twierdzeń rachunku prawdopodobieństwa, uzasadniające powszechne występowanie w przyrodzie rozkładów zbliżonych do rozkładu normalnego.

Rozkład normalny (μ, σ).

gęstość-$f\left( x \right) = \frac{1}{\sqrt{2\pi}*\sigma}*e^{- \frac{{(x - \mu)}^{2}}{2\sigma^{2}}}$

dystrybuanta-Φ(x) = P(X<x) = ∫_−∞^xf(t)dt

Jeżeli zmienna losowa jest opisana podanym wzorem to ma ona rozkład normalny z parametrami 0 i 1.

$$x = \operatorname{}\frac{\sum_{i = 1}^{n}{Y_{i} - \sum_{i = 1}^{n}\left( E\left( Y_{i} \right) \right)}}{\sqrt{\sum_{i = 1}^{n}{D^{2}\left( Y_{i} \right)}}}$$

Y_i ≡ R_i , $E\left( \text{Yi} \right) = \frac{1}{2}$ , $D^{2}\left( \text{Yi} \right) = \frac{1}{12}$

$$\mathbf{x}\mathbf{=}\sum_{\mathbf{i}\mathbf{=}\mathbf{1}}^{\mathbf{12}}{\mathbf{R}_{\mathbf{i}}\mathbf{-}\mathbf{6}}$$

13. Generatory liczb losowych.

Generatory liczb losowych:

a)dla rozkładu jednostajnego

W przypadku rozkładu jednostajnego liczby są z przedziału(0,1), i pojawiają się z prawdopodobieństwem równym 0. Np. rzut monetą,

b)dla rozkładu wykładniczego: W rozkładzie pojawiają się najczęściej wartości bliskie 0. Rozkład wykładniczy można spotkać przy odchyłkach kształtu.

f(x) = λ * e^−λx

F(x) = 1 − e^−λx

$x = - \frac{1}{\lambda}\ln\left( 1 - R \right)$-wzór na generator liczb losowych o rozkładzie wykładniczym

c)dla rozkładu normalnego:

Rozkład normalny (μ,  σ).

gęstość-$f\left( x \right) = \frac{1}{\sqrt{2\pi}*\sigma}*e^{- \frac{\left( x - \mu \right)^{2}}{2\sigma^{2}}}$

dystrybuanta-Φ(x) = P(X<x) = ∫_−∞^xf(t)dt

Jeżeli zmienna losowa jest opisana podanym wzorem to ma ona rozkład normalny z parametrami 0 i 1.

$$x = \operatorname{}\frac{\sum_{i = 1}^{n}{Y_{i} - \sum_{i = 1}^{n}\left( E\left( Y_{i} \right) \right)}}{\sqrt{\sum_{i = 1}^{n}{D^{2}\left( Y_{i} \right)}}}$$

Y_i ≡ R_i , $E\left( \text{Yi} \right) = \frac{1}{2}$ , $D^{2}\left( \text{Yi} \right) = \frac{1}{12}$

$$\mathbf{x}\mathbf{=}\sum_{\mathbf{i}\mathbf{=}\mathbf{1}}^{\mathbf{12}}{\mathbf{R}_{\mathbf{i}}\mathbf{-}\mathbf{6}}$$

d) rozkład hipergeometryczny: np. dla lotto

$$P\left( X = x \right) = h\left( x,n,M,N \right) = \frac{\left( \frac{M}{x} \right)\left( \frac{N - M}{n - x} \right)}{\left( \frac{N}{n} \right)}$$

gdzie: x-próbka s, n-wielkość próbki, M-populacja s, L-wielkość populacji

14. Rozkrój materiału: co jest zmienną decyzyjną, co funkcją celu, a co warunkiem ograniczającym.

Rozkrój materiałów:

a)rozkrój jednowymiarowy- np. krojenie prętów

FC: minimalizacja zużycia prętów

WO: wycięcie ilości prętów zgodnie z zamówieniem

b) rozkład dwuwymiarowy: odbywa się w dwóch wymiarach

15. Wyprowadzić wzór na generator liczb losowych o rozkładzie wykładniczym.

Dla rozkładu wykładniczego: W rozkładzie pojawiają się najczęściej wartości bliskie 0. Rozkład wykładniczy można spotkać przy odchyłkach kształtu.

f(x) = λ * e^−λx

F(x) = 1 − e^−λx

Stosuję się metodę odwracania dystrybuanty, zakładając, że dystrybuanta jest zmienną losową o rozkładzie jednostajnym na odcinku <0,1>.

R = 1 − e^−λx

λ−parametr rokłądu;

e^−λx = 1 − R

−λx = ln(1−R)

$x = - \frac{1}{\lambda}\ln(1 - R)$-wzór na generator liczb losowych o rozkładzie wykładniczym

16. Co to jest metoda odwracania dystrybuanty?

Metoda odwracania dystrybuanty - generowanie liczb losowych o praktycznie dowolnych rozkładach umożliwia następujące twierdzenie: jeżeli zmienna losowa R ma rozkład jednostajny na odcinku (0,1) to zmienna losowa x=F-1 ma rozkład o dystrybuancie F. F^-1 oznacza funkcję odwrotną do dystrybuanty F. Z twierdzenia wynika więc że leżeli ciąg (Rn), n=1,2,.... jest ciągiem liczb losowych o rozkładzie jednostajnym na (0,1) to ciąg (xn), n=1,2... dla Xn=F^-1(Rn) jest ciągiem liczb losowych o rozkładzie z dystrybuantą F.

17. Co realizuje funkcja LOS() w Excelu?

Excel pozwala nam uzyskać liczbę losową z przedziału <0,1) za pomocą formuły LOS(). Jeśli chcemy uzyskać liczbę z zakresu 1-6 musimy zastosować następujący wzór: 6*LOS()+1. Najlepiej jeszcze zaokrąglić wynik do wartości całkowitych, więc ostatecznie formuła przyjmie postać =ZAOKR.W.DÓŁ(6*LOS()+1;1). Czy aby na pewno? Dlaczego jednak nie użyć formuły ZAOKR(5*LOS()+1;0)? Sprawdźmy. W tym celu oszacujemy sobie, jak dobrze nasz generator daje liczby losowe. Innymi słowy - jak "dobra" jest nasza Excelowa kostka D6.

18. Co to jest prawo wielkich liczb Bernulliego?

Sformułowane po raz pierwszy przez Jakuba Bernoulliego. Twórca nazwał je ”złotym twierdzeniem”. Z prawdopodobieństwem dowolnie bliskim 1 można się spodziewać, iż przy dostatecznie wielkiej liczbie powtórzeń eksperymentu losowego, z których każdy kończy się sukcesem lub porażką, częstość występowania sukcesu w serii eksperymentów będzie się dowolnie mało różniła od jego prawdopodobieństwa.