wzbo-wyklad nr 1a, MATERIAŁY DYDAKTYCZNE, WYBRANE ZAGADNIENIA BADAŃ OPERACYJNYCH
[ Pobierz całość w formacie PDF ]
Wybrane zagadnienia badania operacyjnych
dr inż. Zbigniew Tarapata
Wykład nr 1a: Modelowanie problemów decyzyjnych, c.d.
___________________________________________________________________________
OPTYMALIZACJA DYSKRETNA
Zagadnienia decyzyjne, w których chociaż jedna zmienna
decyzyjna przyjmuje wartości dyskretne (całkowitoliczbowe),
nazywamy
dyskretnymi zagadnieniami decyzyjnymi
.
Model matematyczny opisujący tą sytuację nazywamy
dyskretnym zadaniem decyzyjnym (DZD)
. Zajmiemy się jedynie
takimi zagadnieniami dyskretnymi, w których relacje zachodzące
między poszczególnymi wielkościami są liniowe. Formułowane
zadania będą zatem zadaniami programowania dyskretnego,
liniowego (PDL).
Wśród zadań programowania dyskretnego, liniowego
wyróżnia się trzy ich typy:
•
zadania programowania całkowitoliczbowego liniowego (PCL)
– gdzie wszystkie zmienne są liczbami całkowitymi,
•
zadania programowania binarnego liniowego (PBL)
– gdzie
wszystkie zmienne są liczbami binarnymi (tzn. 0 lub 1),
•
zadania programowania mieszanego liniowego (PML
)
– gdzie
część zmiennych to zmienne ciągłe, część – zmienne całkowite, a
część – zmienne binarne.
31
Wybrane zagadnienia badania operacyjnych
dr inż. Zbigniew Tarapata
Wykład nr 1a: Modelowanie problemów decyzyjnych, c.d.
___________________________________________________________________________
Przykład zadania PCL (planowanie produkcji i transportu)
Projektowana jest budowa od jednej do 4 nowych piekarni
mających zaopatrywać w pieczywo 5 miejscowości: A, B, C, D i E.
Piekarnie można wybudować w miejscowościach A, B, C i E.
Dzienne zdolności wytwórcze Z
i
piekarni (w kg), popyt P
j
na
pieczywo (w kg) z czterech miejscowości oraz oszacowane przyszłe
jednostkowe koszty produkcji k
i
i przewozu pieczywa c
ij
(w zł za kg)
podano w Tabeli 3.1. Oszacowano również, że koszty wybudowania
każdej z piekarni są jednakowe.
Tabela 3.1
c
ij
A
B
C
D
E
Z
i
k
i
A
0
0,4
0,6
0,8
0,7
3000
8,7
B
1
0
1,2
0,9
0,6
2800
6,5
C
0,5
0,5
0
0,8
0,4
2700
7,9
E
1
1,2
0,4
0,5
0
3500
9,1
P
j
1000 2000 1500 1600 1400
-
-
Zaproponować wielkość rocznej produkcji każdego z zakładów
oraz plan transportu pieczywa, dzięki którym całkowite koszty
produkcji i transportu będą możliwie najniższe.
32
Wybrane zagadnienia badania operacyjnych
dr inż. Zbigniew Tarapata
Wykład nr 1a: Modelowanie problemów decyzyjnych, c.d.
___________________________________________________________________________
Rozwiązanie:
Przyjmijmy następujące oznaczenia:
M
- liczba piekarni;
N
- liczba miejscowości dostarczania pieczywa;
y
ij
- wielkość produkcji
i
-tej
piek
arni
prze
znaczona dla
j
-tej
iejsc ści,
i
1
=
M
,
j
1
=
N
.
Pozostałe oznaczenia jak w treści zadania.
Funkcja celu będzie miała postać:
∑∑
M
N
∑
M
∑
N
(3.1)
y
ij
⋅
c
ij
+
k
i
⋅
y
ij
→
min
i
==
11
j
i
=
1
j
=
1
przy ograniczeniach:
∑
=1
N
y
≤
Z
(3.2)
ij
i
,
i
1
=
M
j
∑
=1
M
(3.3)
y
≥
ij
P
j
,
j
1
=
N
i
(3.4)
y
ij
≥
0
,
i
1
=
M
,
j
1
=
N
(3.5)
y
ij
−
calkowitol
iczbowe
,
i
1
=
M
,
j
1
N
Zadanie (3.1) – (3.5) jest zadaniem programowania
całkowitoliczbowego, liniowego (PCL). Funkcja celu (3.1)
postuluje minimalizację łącznych kosztów transportu (pierwszy
składnik) i produkcji (drugi składnik). Warunek (3.2) zapewnia,
że wielkość produkcji każdej z piekarń nie będzie większa aniżeli
jej zdolności wytwórcze. Spełnienie warunku (3.3) zapewnia, że
wielkość produkcji każdej z piekarń nie będzie mniejsza aniżeli
lokalne zapotrzebowanie. Warunek (3.4) wymusza, nieujemność
wielkości produkcji, a (3.5) – jej całkowitoliczbowość (nie można
przecież produkować ½ bułki lub 10 ¾ chleba).
33
=
Wybrane zagadnienia badania operacyjnych
dr inż. Zbigniew Tarapata
Wykład nr 1a: Modelowanie problemów decyzyjnych, c.d.
___________________________________________________________________________
Dla naszego zadania mamy:
•
M
=4;
•
N=
5;
•
Z
i
- przedostatnia kolumna tabeli 3.1;
•
k
i
- ostatnia kolumna tabeli 3.1;
•
P
j
- ostatni wiersz tabeli 3.1;
•
y
- macierz optymalnych wielkości produkcji i
przewozu z poszczególnych piekarni do miejscowości.
=
[ ]
N
y
*
ij
M
×
Po podstawieniu danych do zadania i rozwiązaniu go otrzymamy:
1000
0
0
126
0
0
2000
0
800
0
y
*
=
(3.6)
0
0
1500
674
526
0
0
0
0
874
Plan przewozu pieczywa zawiera macierz y
*
. Wynika z niej, że
wielkość produkcji poszczególnych piekarni jest następująca:
•
dla piekarni w miejscowości A: 1000+126=1126;
•
dla piekarni w miejscowości B: 2000+800=2800;
•
dla piekarni w miejscowości C: 1500+674+526=2700;
•
dla piekarni w miejscowości E: 874.
Zapewni to nam minimalny koszt produkcji i transportu w
wysokości 58850 zł, tzn.:
58850
=
=
1000
⋅
0
+
126
⋅
0
8
+
2000
⋅
0
+
800
⋅
0
.
9
+
1500
⋅
0
+
674
⋅
0
8
+
.
+
526
⋅
0
4
+
874
⋅
0
+
8
.
7
⋅
1126
+
6
.
5
⋅
2800
+
7
.
9
⋅
2700
+
9
1
⋅
874
34
*
Wybrane zagadnienia badania operacyjnych
dr inż. Zbigniew Tarapata
Wykład nr 1a: Modelowanie problemów decyzyjnych, c.d.
___________________________________________________________________________
Przykład zadania PBL (zagadnienie optymalnego przydziału)
Na wydziale obróbki mamy cztery maszyny (M1, M2, M3, M4)
i czterech obsługujących je robotników (R1, R2, R3, R4). Znamy
wydajność każdego robotnika na poszczególnych stanowiskach.
Wydajność tą określa liczba detali, które dany robotnik może
wykonać na danej maszynie w ciągu jednej godziny. Przedstawiono
ją w tabeli 3.2.
Tabela 3.2
w
ij
R1
R2
R3
R4
M1
6
7
8
4
M2
12
6
9
8
M3
10
5
9
7
M4
13
11
7
9
Należy ustalić taki przydział robotników do poszczególnych
stanowisk, aby łączna wydajność całego zespołu była maksymalna.
UWAGA!
Zagadnienie to można łatwo uogólnić i określić następujący
problem decyzyjny:
Mamy
m
stanowisk i
n
pracowników. Znamy macierz
wydajności
W
=
[ ]
n
ij
m
×
, gdzie
w
ij
jest wydajnością
j
-tego
pracownika na
i
-tym stanowisku.
Należy ustalić taki przydział pracowników do stanowisk
pracy, aby łączna wydajność całego zespołu była maksymalna.
35
w
[ Pobierz całość w formacie PDF ]