Zad.1.

Model programowania liniowego

jest to analityczna (matematyczna) postać abstrakcji rzeczywistego

zjawiska, czy procesu cechującego się ściśle, bądź też częściej aproksymacją (przybliżeniem) liniowego

charakteru zmian tego procesu.

W postaci standardowej (w notacji macierzowej) model programowania liniowego przyjmuje postać

następującą:

Funkcja celu (uwzględniająca kryterium efektywności):

Z=c

T

x → max,min

Oraz liniowe warunki uboczne (warunki ograniczające):

Ax=b

1

i warunki brzegowe (warunki nieujemności):

x≥0

gdzie:

Z – funkcja celu;

x - wektor zmiennych decyzyjnych (zmiennych kontrolowanych procesu);

c – wektor parametrów funkcji celu;

A – macierz parametrów stojących po lewej stronie równań warunków brzegowych;

b – wektor ograniczeń równań warunków brzegowych.

Aby sytuacja decyzyjna mogła zostać zaklasyfikowana do zadań modeli liniowych musi cechować się

następującymi właściwościami:



Proporcjonalność

– zmian wartości kryterium efektywności oraz wartości parametrów ograniczających

względem zmian decyzyjnych;



Addytywność

– nakładów i efektów;



Podzielność

(nieskończona) – wartości zmiennych decyzyjnych;



Determinizm

– sytuacji decyzyjnej (ścisłe zdefiniowanie problemu).

Algorytm budowania modelu liniowego jest następujący:

(1)

Zdefiniowanie problemu decyzyjnego

(2)

Analiza jakościowa problemu – sprawdzenie czy dany problem należy do klasy modeli

decyzyjnych: aby tak było sytuacja decyzyjna musi spełnić warunki posiadania decydenta (czyli osoby

podejmującej decyzję) oraz pole decyzyjne (przynajmniej muszą istnieć 2 alternatywne względem siebie decyzje,

które są powiązane ze sobą relacją preferencji/obojętności);

(3)

Analiza ilościowa (konstrukcja modelu): określenie funkcji celu, kryterium efektywności,

zmiennych decyzyjnych, zmiennych obojętnych określających warunki brzegowe modelu. W tej części ustalana

jest również postać analityczna modelu (liniowa/nieliniowa) przy uwzględnieniu rozpatrywanego horyzontu

1

Zapis ten odpowiada modelowi w postaci kanonicznej. Dla modelu w postaci niezbilansowanej w przypadku

szukania maksimum funkcji w warunkach ubocznych stosowany jest znak ≤. Natomiast przy poszukiwaniu minimum
funkcji wstawiamy znak ≥.

czasowego;

(4)

Walidacja poprawności stworzonej abstrakcji matematycznej – tzn. sprawdzeniu czy model

w konfrontacji z zastosowaniu zdanymi statystycznymi dobrze odzwierciedla rzeczywistość;

(5)

Implementacja modelu – Prezentacja modelu → Uzyskanie wyniku → Podjęcie decyzji w

oparciu o zastosowany model;

(6)

Analiza pooptymalizacyjna – analiza RHS i OFC.

Klasy zadań PL, to np.: zagadnienia przydziału (w szczególności możemy wyróżnić

zagadnienia

transportowe),

zadania

optymalizacji

dyskretnej

(w

tym:

zagadnienia

całkowitoliczbowego PCL, zadania programowania binarnego PBL, zadania programowania

mieszanego liniowego PML), problem komiwojażera.

Zad.2

x

ij

– zmienna decyzyjna oznaczająca liczbę ton i–tego surowca zaangażowanego w produkcję j-tej

mieszaniny.

c

ij

– jednostkowy zysk z zaangażowania i-tego surowca w j-tą mieszankę.

Funkcja kryterium:

F ( x)=

∑

i= 1

2

∑

j= 1

3

c

ij

⋅ x

ij

= 3x

11

+ 6x

12

+ 9x

13

+ 4x

21

+ 7x

22

+ 11x

23

→max

Warunki podażowe (posiadane zasoby surowców):

x

11

+ x

12

+ x

13

≤ 28

x

11

+ x

12

+ x

13

≤ 25

Warunki popytowe (zapotrzebowanie zgłaszane przez odbiorcę):

x

11

+ x

21

≥ 20

x

12

+ x

22

≥ 10

x

13

+ x

23

≥ 4

Warunki technologiczne:

0,1𝑥

11

+ 0,2𝑥

21

𝑥

11

+ 𝑥

21

≥ 0,15

0,05𝑥

12

+ 0,04𝑥

22

𝑥

12

+ 𝑥

22

≥ 0,045

𝑥

13

𝑥

23

≥ 3

Warunki brzegowe:

x

ij

≥ 0

Zad.3.

Ad. a) Aby produkt P2 pozostał w optymalnym planie produkcji jednostkowy koszt wytworzenia tegoż

produktu może wzrosnąć co najwyżej o 8,5 zł, gdyż tyle wynosi dopuszczalny spadek marży.

Ad b) Dla produktu P3 podwyższenie marży do wartości 25 zł nie spowoduje zmian w optymalnej

strukturze produkcji, gdyż 25 zł - 12 zł < 39 zł a dopuszczalny wzrost marży wynosi 39 zł.

Ad c) Zmniejszenie tygodniowego limitu zasobu B o 250 jednostek spowoduje zmiany w aktualnym

asortymencie produkcji, gdyż dopuszczalny limit wynosi 200 jednostek.

Ad d) Na podstawie tabel możemy powiedzieć że zasób C jest zasobem wiążącym, ponadto jednostkowy

przyrost zasobu C spowoduje wzrost zysku o 0,2857 zł. Dodatkowo wzrost zasobu C o 600 jednostek nie

spowoduje zmiany w aktualnym asortymencie produkcji. Zatem dla przyrostu o 500 jednostek zasobu C zysk ze

sprzedaży wzrośnie o:

500 * 0,2857 zł = 142,85 zł

Ad e) Wykonanie planu optymalnego wiąże się z konsekwencją niewykorzystania zasobów A i D

odpowiednio w ilościach: 742,857 oraz 214,285 jednostek.

Zad.4.

Ad. A)

Model ten należy do klasy modeli deterministycznych optymalizacji zapasów, a bardziej

szczegółowo do klasycznego modelu optymalnej partii zamówienia (EOQ). Ponieważ w rozpatrywanym

zadaniu chodzi o sprzedaż obuwia w sklepie, tym samym nie interesuje nas w żadnym stopniu produkcja (w

typowym modelu zapasy robione są w celu zapewnienia produkcji co powoduje inną konstrukcję modelu

uwzględniającą jednostkową cenę wytworzenia produktu).

Całkowity koszt utrzymania zapasów sprowadza się do postaci:

𝑇𝐾

∗

=

𝐷𝐾

𝑄

∗

+

ℎ𝑄

∗

2

Natomiast optymalna ilość zamówienia Q powinna wynieść:

𝑄

∗

= √

2𝐷𝐾

ℎ

Do rozwiązania tego typu zadania niezbędna jest znajomość następujących zmiennych:

D – w rozpatrywanym horyzoncie decyzyjnym stałe zapotrzebowanie na obuwie;

K – stały (niezależny od wielkości zamówienia i czasu) koszt odnowienia;

h – stały w czasie koszt jednostkowy koszt magazynowania.

Ad. B)

Model ten należy do stochastycznych modeli zapasów charakteryzujących się popytem opisanym

rozkładem losowym (najczęściej rozkładem normalnym)- klasa modelu jednookresowego.

Całkowity koszt utrzymania zapasów sprowadza się do postaci:

KT(d, Q) = pQ + b max(0, d - Q) + h max(0, Q - d)

Natomiast optymalna ilość zamówienia Q powinna wynieść:

𝐹(𝑄

∗

) =

𝑏 − 𝑝
𝑏 + ℎ

A więc optymalna partia zakupu Q* jest wielkością dla której dystrybuanta popytu przyjmuje wartość

(b-p)/(b+h).

Do rozwiązania tego typu zadania niezbędna jest znajomość następujących zmiennych:

d – w rozpatrywanym horyzoncie decyzyjnym stałe zapotrzebowanie na obuwie;

K – stały (niezależny od wielkości zamówienia i czasu) koszt odnowienia;

h – stały w czasie koszt jednostkowy koszt magazynowania.

p – cena jednostkowa

b - koszt jednostkowy niezaspokojonego popytu b

Zad.5.

Funkcja celu

(maksymalizacja użyteczności pakietu medycznego):

∑ u

𝑖

𝑥

𝑖 → 𝑚𝑎𝑥

20

𝑖=1

Warunki ograniczające

(maksymalizacja użyteczności pakietu medycznego):

w

i

< W

∑ 𝑤

𝑖

20

𝑖=1

𝑥

𝑖

≤ 𝑊

∑ 𝑤

𝑖

20

𝑖=1

> 𝑊

𝑥

3

𝑥

5

𝑥

6

𝑥

12

≥ 1

𝑥

7

𝑥

8

= 0 & 𝑥

7

+𝑥

8

≥ 1

−2𝑥

15

+ 𝑥

17

≥ 0

𝑥

20

(𝑥

18

+ 𝑥

19

) = 0

Warunki brzegowe

:

𝑥

𝑖

≥ 0

𝑥 ∈ 𝐶

Zad.6.

Dla klasycznego zagadnienia transportowego model wygląda następująco:

Funkcja kryterium:

𝑧 = ∑ ∑ 𝑐

𝑖𝑗

𝑥

𝑖𝑗

5

𝑗=1

3

𝑖=1

→ 𝑚𝑖𝑛

Warunki podażowe:

∑ 𝑥

𝑗

5

𝑗=1

≤ 𝑎

𝑖

dla i = 1,2,3

Warunki popytowe:

∑ 𝑥

𝑖

3

𝑖=1

= 𝑏

𝑗

dla j = 1, … ,5

Warunki brzegowe:

𝑥

𝑖𝑗

≥ 0 dla i = 1,2,3 oraz j = 1, … ,5

Ażeby istniało rozwiązanie musi zostać spełniony następujący warunek:

∑ 𝑎

𝑖

3

𝑖=1

≥ ∑ 𝑏

𝑗

5

𝑖=1