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.