Sienicki Artur I7X6S1 Modelowanie Matematyczne
1
TREŚĆ ZADANIA:
Firma Intel pracuje nad procesorem nowej generacji. LZ zespołów składających się z LP
pracowników jest odpowiedzialnych za wytworzenie X elementów procesora. Do zespołów
przydzielani są specjaliści posiadający określone kwalifikacje. Aby praca przebiegała bez
Ŝ
adnych przeszkód Ŝaden z pracowników nie moŜe pracować w więcej niŜ jednym zespole.
Czas wykonania poszczególnego komponentu przez zespół wynosi T
ij
, a czas wykonania
całego procesora szacuje się na T
rz
. Firma Intel podkreśliła fakt, iŜ prace nad kaŜdym
komponentem procesora nie będą trwały jednocześnie. Dopiero kiedy jeden element zostanie
wykonany, moŜna rozpocząć pracę nad drugim – ze względu na fakt, iŜ pracownicy biorą
udział równieŜ w innym projekcieWyznaczono równieŜ budŜet, który moŜna przeznaczyć
na
produkcję
procesora
– K
max
. Zatem koszt wykonania poszczególnego elementu procesora
przez zespół będzie wynosił K
ij
, a rzeczywisty koszt projektu wyniesie K
rz
. Łączny czas pracy
nad procesorem nowej generacji nie moŜe przekroczyć T
max
. NaleŜy tak zorganizować
prace
nadnowym procesorem, by czas wykonania był jak najmniejszy oraz koszty poniesione przez
korporacje były minimalne i tym samym nie przekroczyły dostępnego budŜetu.
LP
– liczba zatrudnionych pracowników
LZ
– liczba zespołów pracujących nad nowym procesorem
LPD
– liczba komponentów
X
– zbiór numerów komponentów do wykonania X
⊂
2
N
, X
{
i
∈
N
i
: i
<
Z
}
X
i
– zbiór numerów podzespołów do wykonania przez zespół i
PR
– zbiór numerów wszystkich pracowników pracujących nad projektem
P
i
– zbiór numerów pracowników z zespołu i
Z
z
– zbiór numerów wszystkich zespołów
NKW
– zbiór numerów kwalifikacji potrzebnych do pracy nad procesorem
NKW
i
– zbiór numerów kwalifikacji i-tego pracownika
NKP
i
– zbiór numerów kwalifikacji potrzebnych do wykonania i-tego elementu
T
ij
– czas wykonania i-tego elementu przez j-ty zespół
T
rz
– rzeczywisty czas wykonania całego procesora
T
max
– maksymalny czas przeznaczony na wykonanie całego procesora
K
max
– budŜet przeznaczony na produkcję
procesora
K
ij
– koszt wykonania i-tego komponentu przez j-ty zespół
K
rz
– rzeczywiste koszty poniesione podczas produkcji procesora
OBJAŚNIENIE KOLORÓW:
Na
czerwono
zaznaczono zbiory moŜliwych (fizycznie) do uzyskania wartości. Decydent w chwili
podejmowania decyzji będzie znał wartości danych, rozkład ich prawopodobieństw, stopień
przynaleŜności jej wartości do zbioru, ale znane będzie jedynie przybliŜenie zbioru.
Na
zielono
zaś te cechy, na których wartości zaleŜy decydentowi i na które nie ma wpływu przez co
posiada niepełna znajomość
danych.
Sienicki Artur I7X6S1 Modelowanie Matematyczne
2
OPIS CECH:
{
}
{
}
{
}{
}
{
}
{
}
=
=
=
+
+
+
+
+
=
=
+
=
=
=
=
LZ
j
LPD
i
ij
rz
rz
LZ
j
LPD
i
ij
LPD
i
N
i
LP
i
N
i
N
N
z
LZ
i
N
i
N
LZ
i
N
i
N
O
R
K
R
K
R
K
R
T
R
T
R
T
NKWP
NKW
NKW
Z
P
PR
X
X
N
LPD
N
LZ
N
LP
X
1
1
max
max
1
1
1
1
1
1
,
,
,
,
,
,
,
,
,
,
,
,
2
,
,
2
,
,
2
,
,
2
,
,
2
,
,
2
,
,
2
,
,
2
,
,
,
,
,
,
,
OPIS ZWIĄZKÓW:
{
}
6
6
6
5
5
5
4
4
4
3
3
3
2
2
2
1
1
1
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
R
Y
Z
R
Y
Z
R
Y
Z
R
Y
Z
R
Y
Z
R
Y
Z
R
O
=
Z
1
: jeden pracownik moŜe pracować w jednym zespole
{ }
{ }
∅
=
∩
×
∈
=
=
∀
≠
∈
+
=
=
b
a
b
a
Zz
b
a
lz
N
lz
i
i
z
LZ
i
i
z
z
z
N
p
z
lz
R
P
Z
LZ
Y
,
1
1
1
1
1
:
)
2
(
,
,
,
,
Z
2
: rzeczywisty czas wykonania całego projektu
{ }
{
}
{ }
{ }
{
}
{ }
=
×
×
×
∈
=
=
∑ ∑
∈
∈
+
=
=
=
=
=
=
Zz
j
Xj
i
ij
rz
lz
N
N
lz
i
i
lz
j
lpd
i
ij
rz
z
LZ
i
i
LZ
j
LPD
i
ij
rz
z
t
t
R
N
x
t
t
z
lpd
lz
R
X
T
T
Z
LPD
LZ
Y
:
)
2
(
2
,
,
,
,
,
,
,
,
,
,
2
2
1
1
1
2
1
1
1
2
Z
3
: ograniczenie na czas wykonania całego procesora
{
}
max
2
max
3
max
3
:
,
,
t
t
R
t
t
R
T
T
Y
rz
rz
rz
≤
∈
=
=
+
Z
4
: rzeczywisty koszt poniesiony przy produkcji nowego procesora
{ }
{
}
{ }
{ }
{ }
{ }
=
×
×
×
∈
=
=
∑ ∑
∈
∈
+
=
=
=
=
=
=
Zz
j
Xj
i
ij
rz
lz
N
N
lz
i
i
lz
j
lpd
i
ij
rz
z
LZ
i
i
LZ
j
LPD
i
ij
rz
z
k
k
R
N
x
t
t
z
lz
lpd
R
X
T
T
Z
LZ
LPD
Y
:
)
2
(
2
,
,
,
,
,
,
,
,
,
,
2
2
1
1
1
4
1
1
1
4
Z
5
: ograniczenie na koszt – nie moŜna przekroczyć dostępnego budŜetu
{
}
max
2
max
5
max
5
:
,
,
k
k
R
k
k
R
K
K
Y
rz
rz
rz
≤
∈
=
=
+
Sienicki Artur I7X6S1 Modelowanie Matematyczne
3
Z
6
: powodzenie wykonania kaŜdego elementu
{ } {
} {
} { }
{ } {
} {
} { }
⊃
×
∈
=
=
∈
∈
∈
+
+
+
+
=
=
=
=
=
=
=
=
∀
i
Xj
k
i
Pj
i
Pz
j
lz
lpd
lp
lz
N
lz
i
i
lpd
i
i
lp
i
i
lz
i
i
z
LZ
i
i
LPD
i
i
LP
i
i
LZ
i
i
z
nkwp
nkw
N
x
nkwp
nkw
p
z
lz
lpd
lp
R
X
NKWP
NKW
P
Z
LZ
LPD
LP
Y
U
U
:
)
2
(
,
,
,
,
,
,
,
,
,
,
,
,
,
,
1
3
1
1
1
1
6
1
1
1
1
6
{ }
{
} {
}
{ }
{
}
{ }
{
}
{ }
LZ
i
i
rz
rz
LZ
j
LPD
i
ij
LZ
j
LPD
i
ij
LPD
i
i
LP
i
i
z
LZ
i
i
X
x
K
T
w
K
K
T
T
NKWP
NKW
NKW
Z
P
PR
X
LPD
LZ
LP
a
1
1
1
max
max
1
1
1
1
1
,
,
,
,
,
,
,
,
,
,
,
,
,
,
=
=
=
=
=
=
=
=
=
=
=
gdzie:
a – lista danych
w – lista wskaźników
x – lista zmiennych decyzyjnych
{ }
{
} {
}
{ }
{
}
{ }
{
}
( )
{ }
⊂
⊂
≤
≤
∈
=
Ω
=
=
∈
=
⊂
∅
=
∩
⊂
⊂
=
=
=
×
×
∈
=
∈
∈
∈
∈
∈
∈
∈
∈
=
∈
∈
∈
∈
+
∈
≠
∈
∈
∈
+
+
+
+
+
=
=
=
=
=
=
=
∀
∀
∑ ∑
∑ ∑
∑ ∑
∑ ∑
∀
∀
∀
∀
k
Zj
k
i
Xj
i
Zz
j
j
Zz
j
Zz
j
Xj
i
ij
Zz
j
Xj
i
ij
LZ
N
LZ
i
i
Zz
j
Xj
i
ij
rz
Zz
j
Xj
i
ij
rz
rz
rz
i
Zz
i
m
i
m
i
Zz
m
i
i
X
i
i
PR
i
z
LPD
LP
LZ
N
LZ
j
LPD
i
ij
LZ
j
LPD
i
ij
LPD
i
i
LP
i
i
z
LZ
i
i
NKW
NKWP
X
X
T
T
K
K
X
a
K
K
T
T
R
K
T
x
a
W
PR
P
Z
Z
NKW
NKWP
NKW
NKW
LPD
X
LP
PR
LZ
Z
R
N
K
K
T
T
NKWP
NKW
NKW
Z
P
PR
X
LPD
LZ
LP
A
U
U
,
,
,
:
)
2
(
,
:
,
)
,
(
,
,
,
,
,
,
:
)
2
(
,
,
,
,
,
,
,
,
,
,
,
,
,
max
max
1
2
,
4
2
2
3
1
1
max
max
1
1
1
1
1
Sienicki Artur I7X6S1 Modelowanie Matematyczne
4
SFORMUŁOWANIE ZADANIA OPTYMALIZACJI:
Dla danych a
∈
A naleŜy wyznaczyć
takie x
*
∈Ω
(a) aby
1
)
(
:
)
,
(
*
*
=
∈
∀
y
E
x
a
W
y
a
:
=
=
Ω
∈
p
p
w
x
T
y
gdy
y
E
rz
a
x
a
.
0
)
(
1
)
(
min
)
(
*
*
oraz
=
=
Ω
∈
p
p
w
x
K
y
gdy
y
E
rz
a
x
a
.
0
)
(
1
)
(
min
)
(
*
*
gdzie:
∑ ∑
∑ ∑
∈
∈
∈
∈
=
=
Zz
j
Xj
i
ij
rz
Zz
j
Xj
i
ij
rz
K
x
K
T
x
T
)
(
)
(
SFORMUŁOWANIE ZADANIA EKSTREMALIZACJI:
Dla danych a
∈
A naleŜy wyznaczyć
takie x
*
∈Ω
(a) aby
)
(
)
(
min
)
(
*
x
K
x
K
rz
a
x
rz
Ω
∈
=
oraz
)
(
)
(
min
)
(
*
x
T
x
T
rz
a
x
rz
Ω
∈
=