ekonometria _cz3_1a.pdf

(251 KB) Pobierz
EKONOMETRIA dr inż. Zbigniew Tarapata
Temat 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
EKONOMETRIA dr inż. Zbigniew Tarapata
Temat 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 liczbach bochenków
chleba), popyt P j na pieczywo (w liczbach bochenków chleba)
z czterech miejscowości oraz oszacowane przyszłe jednostkowe
koszty produkcji k i i przewozu pieczywa c ij (w zł za jeden bochenek
chleba) 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
924639056.027.png 924639056.028.png 924639056.029.png 924639056.030.png 924639056.001.png 924639056.002.png 924639056.003.png 924639056.004.png 924639056.005.png 924639056.006.png 924639056.007.png 924639056.008.png 924639056.009.png 924639056.010.png 924639056.011.png
 
EKONOMETRIA dr inż. Zbigniew Tarapata
Temat 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
i
=
1
M
j
=
1
N
iejsc
ści,
,
.
Pozostałe oznaczenia jak w treści zadania.
Funkcja celu będzie miała postać:
M
N
M
N
∑∑
∑
∑
y
⋅
c
+
k
⋅
y
→
min
(3.1)
ij
ij
i
ij
i
==
11
j
i
=
1
j
=
1
przy ograniczeniach:
N
∑ =1
y ≤
Z
i
=
1
M
(3.2)
,
ij
i
j
M
∑ =1
y ≥
P
j
=
1
N
(3.3)
,
ij
j
i
y
≥
0
i
=
1
M
j
=
1
N
(3.4)
,
,
ij
y
−
calkowitol
iczbowe
i
=
1
M
j
=
1
N
(3.5)
,
,
ij
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
924639056.012.png 924639056.013.png 924639056.014.png
 
EKONOMETRIA dr inż. Zbigniew Tarapata
Temat 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;
•
[ ] N
* y - macierz optymalnych wielkości produkcji
i przewozu z poszczególnych piekarni do miejscowości.
*
=
y
ij
M
×
Po podstawieniu danych do zadania i rozwiązaniu go otrzymamy:
1000
0
0
126
0
0
2000
0
800
0
*
y
=
0
0
1500
674
526
(3.6)
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
EKONOMETRIA dr inż. Zbigniew Tarapata
Temat 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
[ ] n
W
=
w
wydajności
, gdzie w ij jest wydajnością
j -tego
ij
m
×
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
924639056.015.png 924639056.016.png 924639056.017.png 924639056.018.png 924639056.019.png 924639056.020.png 924639056.021.png 924639056.022.png 924639056.023.png 924639056.024.png 924639056.025.png 924639056.026.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin