PROGRAMOWANIE LINIOWE

Zbudować model matematyczny do poniższych zagadnień (ułożyć program matematyczny ).

Problem 1.

Przedsiębiorstwo przewozowe ‘ STAR ‘ zajmuje się dostarczaniem lodów do sklepów. Dane dotyczące

kosztów przewozu jednostki z magazynu do sklepu oraz wielkości zapasów i zapotrzebowania

zamieszczono w tabeli. Określić plan przewozu minimalizujący koszty.

Magazyn

Sklep

M

1

M

2

M

3

M

4

Zapotrzebowanie w sklepie

S

1

50

70

35 100

500

S

2

60

30

20

45

100

S

3

70

55

75

80

300

S

4

100 130 150 110

1000

S

5

75

50

60

85

200

Zapas w magazynie 300 700 600 500

-

Problem 2.

Zakład ‘RURA’ ma wyprodukować 100 rur o długości 5,5 m i 150 o długości 7,5 m. Zakład ma do

dyspozycji rury o długości 17 m. Jak należy pociąć rury, aby odpad był najmniejszy? Pozostałe rury

długości 5,5 i 7,5 stanowią odpad. Zapisz odpowiedni program liniowy.

Problem 3. – zadanie domowe

Zakład dysponuje czterema typami koparek oraz ma wykonać usługi polegające na
wykopaniu odpowiednich rowów. Tabela podaje liczby odpowiednich typów koparek w
zakładzie, ich wydajności przy poszczególnych pracach, koszty eksploatacji oraz minimalne
ilości m

3

.

Wydajność m

3

/ dzień Liczba koparek

Koszty

Koparka

Rów 1 Rów 2 Rów 3

w zakładzie

eksploatacji

A

17

20

5

12

16

B

9

4

20

5

7

C

19

16

9

10

20

D

15

17

12

8

15

Minimalna dzienna wydajność m

3

200

190

170

Zapisać program liniowy wyznaczający przydział koparek do prac minimalizujący koszty prac.

Problem 4. – zadanie domowe

Podjąć decyzję o zwolnieniu pracowników w fabryce. Strukturę zatrudnienia przedstawia tabela.

wiek

pracownika

ilość

pracowników

w danej grupie

średni wiek

pracownika w

danej grupie

wiekowej

średnie

doświadczenie

pracownika w

danej grupie

( od 0 do 10 )

średnie koszty

utrzymania 1

pracownika

danej grupy

średni przychód

od jednego

pracownika

danej grupy

starsi

80

52

9

15

25

średni

120

36

6.5

13

20

młodzi

60

25

3

10

15

Założono dodatkowo, że:

•

nie można zwolnić więcej niż 15 % wszystkich pracowników.

•

średni wiek pracowników nie powinien się zmienić o więcej niż 10%.

•

średnie doświadczenie pracowników nie powinno być mniejsze niż 6.5.

Jako jedyne kryterium postanowiono zastosować kryterium zysku przedsiębiorstwa.

Problem 5. – zadanie domowe

Zakład produkuje 4 rodzaje opon. Do ich wytworzenia można używać zamiennie czterech maszyn.

Jedna opona produkowana jest tylko na jednej maszynie. Tabela podaje maksymalny czas pracy

maszyn na 3 zmianach oraz minimalne ilości opon, które mają być wyprodukowane podczas zmiany.

Jak ustalić produkcję, aby wytworzyć maksymalną liczbę opon?

Zużycie czasu pracy w [szt/h]

Opona

Maszyna

Zima

Sporting

HighLife

Super CX

Czas pracy maszyny

[ min]

M1

5

10

1

15

1360

M2

6

5

2

2

1300

M3

5

2

2

7

1400

M4

1

1

21

6

1420

Minimalne zamówienie

10

20

3

5

Problem 6. – zadanie domowe

Rafineria wytwarza trzy rodzaje olejów A, B, C z trzech surowców I, II, III, których może zamówić

odpowiednio 200 tys. ton , 300 tys. ton i 250 tys. ton . Do produkcji oleju A należy użyć surowców I,

II, III odpowiednio w proporcjach 2:4:3, do oleju B surowca II i III w proporcji 3:4, do oleju C

surowców I, II, III odpowiednio w proporcjach 4:3:2. Koszt jednej tony surowca I, II, III wynosi

odpowiednio 23, 55, 40 jp. Oleje A, B, C rafineria sprzedaje odpowiednio po 70, 50, 65 jp. Ustalić

plan zamówień surowców oraz produkcji mający na uwadze maksymalizacje zysku i wyprodukowanie

minimum po 50 tysięcy ton każdego oleju.

PROGRAMOWANIE SIECIOWE

Problem 1.

Mając dane zawarte w tablicy narysować wykres sieciowy oraz sporządzić wykres Gantta

przedsięwzięcia (projektu), którego czynności i poszczególne czasy zamieszczono w tabeli. Ponadto

obliczyć czas realizacji projektu (możliwie najkrótszy) oraz zaznaczyć i zapisać ścieżkę krytyczną.

Czas trwania czynności

Oznaczenie czynności

Czynności poprzedzające

5

A

7

B

4

C

2

D

A

8

E

C

3

F

B, D, E

2

G

F

5

H

F

6

I

F

4

J

G

3

K

H

1

L

I

Problem 2.

Na podstawie danych w tabeli sporządzić siatkę zależności (zbudować model sieciowy). Jakie jest

prawdopodobieństwo dotrzymania terminu realizacji przedsięwzięcia: a) 40 dni b) 43 dni.

Czynności i-j

Ocena czasu trwania czynności

Optymistyczna

Najbardziej

prawdopodobna

(modalna)

Pesymistyczna

1-2

2

5

8

2-3

8

9

16

2-4

6

7

8

3-4

3

6

9

3-5

9

11

13

3-6

4

6

8

4-7

2

2

2

4-8

5

9

19

5-6

0

0

6

5-8

5

6

13

6-8

10

11

12

6-9

2

3

10

7-8

7

7

7

7-9

7

9

11

8-9

2

4

12

PROGRAMOWANIE DYNAMICZNE

Problem 1.

Pewna firma chce opracować program produkcji elementów na kolejne 3 miesiące. Znany jest popyt
na te elementy wynoszący 3 elementy w każdym z kolejnych trzech miesięcy. Firma może
produkować maksymalnie 5 takich elementów miesięcznie. Koszty produkcji zależne od liczby
wyprodukowanych elementów podano w tabeli:

Liczba elementów

0

1

2

3

4

5

Koszty w [jp]

0

15 17 19 21 23

Jednostkowy koszt przechowywania zapasów jest stały w okresie planistycznym i wynosi 1 jednostkę
pieniężną (koszty magazynowania w i-tym miesiącu obliczamy według stanu na koniec miesiąca).
Maksymalnie magazyn może pomieścić 4 elementy. W chwili obecnej w magazynie znajdują się 2
elementy. Pod koniec trzeciego miesiąca magazyn ma pozostać pusty.

Rozwiązanie.

Przyjmijmy oznaczenia dla i=1,2,3:
s

i

- poziom zapasów na początku i-tego miesiąca,

p

i

- popyt w i-tym miesiącu,

h

i

(j)

- koszt magazynowania j elementów (0

≤

j

≤

4) w i-tym miesiącu,

K

i

(x

i

)

- koszt produkcji x

i

elementów (0

≤

x

i

≤

5) w i-tym miesiącu,

f

i

(x

i

,s

i

) - koszty produkcji i magazynowania w i-tym miesiącu.

Zauważmy, że
f

i

(x

i

,s

i

) = K

i

(x

i

) + h

i

(s

i+1

), gdzie 0

≤

s

i+1

= s

i

+ x

i

– p

i

≤

4, i=1,2,3 oraz s

4

= 0.

Łączne koszty magazynowania i produkcji wynoszą

f

1

(x

1

,s

1

) + f

2

(x

2

,s

2

) + f

3

(x

3

,s

3

).

Koszty te mają być najmniejsze.
Korzystając z równań funkcyjnych Bellmana możemy zapisać:
Krok 1. (miesiąc 3)

g

3

(s

3

) = min (f

3

(x

3

,s

3

)) dla 0

≤

s

3

≤

4

0

≤

x

3

= p

3

–s

3

Krok 2. (miesiąc 2)

g

2

(s

2

) = min (f

2

(x

2

,s

2

) + g

3

(s

3

)) dla 0

≤

s

2

≤

4

p

2

-s

2

≤

x

2

≤

4+p

2

–s

2

Krok 3. (miesiąc 1)

g

1

(s

1

) = min (f

1

(x

1

,s

1

) + g

2

(s

2

)) dla s

1

=2.

p

1

–s

1

≤

x

1

≤

4+p

1

–s

1

Z treści zadania wynika, że
s

1

= 2, p

1

= p

2

= p

3

= 3

s

4

= s

3

+ x

3

– 3 = 0 stąd x

3

= 3 – s

3

.

Mamy zatem:
Krok 1. (miesiąc 3) g

3

(s

3

) = min f

3

(x

3

,s

3

)

0

≤

x

3

=3–s

3

s

3

x

3

s

4

f

3

(x

3

,s

3

)

g

3

(s

3

)

0
1
2
3

3
2
1
0

0
0
0
0

19+0
17+0
15+0

0+0

19
17
15

0

Krok 2. (miesiąc 2)

g

2

(s

2

) = min (f

2

(x

2

,s

2

)+g

3

(s

3

)) dla 0

≤

s

2

≤

4

3–s

2

≤

x

2

≤

7–s

2

s

2

x

2

s

3

f

2

(x

2

,s

2

)

g

3

(s

3

)

f

2

(x

2

,s

2

+g

3

(s

3

)

g

2

(s

2

)

0

0
0

3
4
5

0
1
2

19+0
21+1
23+2

19
17
15

38
39
40

38

1
1
1
1

2
3
4
5

0
1
2
3

17+0
19+1
21+2
23+3

19
17
15

0

36
37
38
26

26

2
2
2
2

1
2
3
4

0
1
2
3

15+0
17+1
19+2
21+3

19
17
15

0

34
35
36
24

24

3
3
3
3

0
1
2
3

0
1
2
3

0

15+1
17+2
19+3

19
17
15

0

19
33
34
21

19

4
4
4

0
1
2

1
2
3

0+1

15+1
17+3

17
15

0

18
32
20

18

Krok 3 (miesiąc 1)

g

1

(s

1

) = min (f

1

(x

1

,2)+g

2

(s

2

)) = min (f

1

(x

1

,2)+g

2

(s

2

))

3-2

≤

x

1

≤

4+3-2 1

≤

x

1

≤

5

s

1

x

1

s

2

f

1

(x

1

,2)

g

2

(s

2

)

F

1

(x

1

,2)+g

2

(s

2

)

g

1

(s

1

)

2
2
2
2
2

1
2
3
4
5

0
1
2
3
4

15+0
17+1
19+2
21+3
23+4

38
26
24
19
18

53
44
45
43
45

43

Optymalna strategia ma postać

x

1

= 4, x

2

= 0, x

3

= 3.

Koszty poniesione przez firmę są wtedy najniższe i wynoszą 43 jp.

GRY Z NATURĄ, ANALIZA DECYZJI

Problem 1.

Trzy typy hamulców tramwajowych I, II, III poddano próbom w trzech rodzajach warunków
drogowych A, B, C. Procent zadowalających prób zawarto w tablicy.

A

B

C

I

85

75

95

II

85

90

76

III

85

65

92

Wybrać jeden z trzech typów hamulców

a.

za pomocą kryterium Walda,

b.

za pomocą kryterium Hurwicza ze współczynnikiem pesymizmu

α

= 0,6,

c.

za pomocą kryterium Laplace’a,

d.

za pomocą kryterium Savage’a.

Problem 2.
Znany cukiernik mieszkający w dużym mieście wypieka co sobotę pewną niewielką liczbę
bardzo poszukiwanych torcików z bitą śmietaną i owocami tropikalnymi. Torciki te są bardzo
drogie i nie sprzedane w sobotę nadają się w poniedziałek do wyrzucenia. Niestety nie
zawsze udaje mu się sprzedać wypieczoną liczbę torcików. W ciągu ostatniego roku cukiernik
zapisywał ile torcików sprzedał każdej soboty (było ich razem 50) , a wyniki zapisał w tablicy.

Liczba sobót

5

8

10

15

7

5

Liczba sprzedanych torcików

0

1

2

3

4

5

Ile torcików powinien wypiekać każdej soboty cukiernik aby zmaksymalizować swój
oczekiwany zysk, jeśli
1.

koszt przygotowania torcika wynosi 0,75 jp,

2.

każdy torcik jest sprzedawany za 1,3 jp,

3.

klient zamierza kupić torcik śmietanowy, a dowie się, że już wszystkie zostały sprzedane
czuje się bardzo zawiedziony i w konsekwencji kupuje mniej ciastek. Cukiernik szacuje, że
spowodowane tym straty wynoszą około 0,4 jp na jednym kliencie. Ponieważ cukiernik
słynie w całym mieście ze swoich torcików, więc rozczarowanie z powodu brak torcików
jakie spotkało klienta w poprzednim tygodniu nie ma wpływu na jego zakupy w przyszłym
czasie.

ZAGADNIENIE PROJEKTOWE

: ułożyć program + rozwiązać z wykorzystaniem narzędzia SOLVER lub

podobnego. K jest parametrem zadania - wartością, która zostanie przydzielona każdej osobie na

zajęciach.

Fabryka mebli wytwarza dwa rodzaje szaf, dwa rodzaje regałów i jeden typ barku. Następnie składa
je w trzy komplety mebli: Agata, Beata, Cecylia.

Szafa 1

Szafa 2

Regał 1

Regał 2

Barek 1

Agata

1

1

1

Beata

1

1

1

Cecylia

1

1

1

Fabryka posiada dwa zakłady produkujące poszczególne elementy i dwa sklepy firmowe. W sklepach
ogółem złożono zamówienia na 30 zestawów Agata, 35 zestawów Beata i 25 zestawów Cecylia
( w sklepie pierwszym odpowiednio 20, 15, 15 ). Tabele przedstawiają zdolności produkcyjne
poszczególnych zakładów koszty wytworzenie jednego elementu oraz ceny transportu
poszczególnych elementów do poszczególnych sklepów.

Zakład 1 produkcja

Koszt

Zdolności

produkcyjne

Koszt transportu

do sklepu 1

Koszt transportu

do sklepu 2

Szafa 1

500+K

150

30

20

Szafa 2

600-K

120

22

17

Regał 2

900-K

140

27

25

Barek

650+K

130

16

12

Zakład 2 produkcja

Koszt

Zdolności

produkcyjne

Koszt transportu

do sklepu 1

Koszt transportu

do sklepu 2

Szafa 1

750-K

150

20

27

Regał 1

550+K

200

25

33

Regał 2

800-K

70

35

40

Barek

600+K

150

10

15

1.

Ustalić plan produkcji minimalizujący koszty produkcji oraz transportu.

2.

Ustalić plan produkcji minimalizujący wyłącznie koszty produkcji.

3.

Ustalić plan produkcji minimalizujący wyłącznie koszty transportu.