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

Ω

∈

=