Badania operacyjne

Wykład 6

Wykład 6

Zagadnienie przydziału

Plan wykładu



Zagadnienie przydziału



Algorytm węgierski

2013-12-13

2

Zagadnienie przydziału



Optymalna alokacja szeroko pojętych zasobów

K t i

i l k ji j t

j

ś i j



Kryteriami alokacji jest najczęściej:



Minimalizacja kosztów lub czasu wykonywania planowanych
zadań,



Maksymalizacja efektów pracy (np. ilość wyprodukowanych

Maksymalizacja efektów pracy (np. ilość wyprodukowanych
wyrobów).

2013-12-13

3

Zagadnienie przydziału



Najogólniej problem można sformułować następująco:



N wyrobów (czynności) można wykonać na P miejscach produkcji



N wyrobów (czynności) można wykonać na P miejscach produkcji
(w zakładach, na stanowiskach pracy, maszynach)

Z

i

d k j

ól

h i j



Znane są ograniczone moce produkcyjne poszczególnych miejsc
pracy (np. dopuszczalny czas pracy), a często także zadania
planowe w zakresie produkcji wyrobów



Podana jest macierz, w której znajdują się koszty (czas pracy lub
wydajność) na danym miejscu pracy przy wykonywaniu

y j

)

y

j

p

y p y y

y

odpowiedniego zadania.

2013-12-13

4

Zagadnienie przydziału



Szczególnym przypadkiem zadań alokacyjnych jest

zagadnienie przydziału z dodatkowymi ograniczeniami

,

ż k żd

ść

ż b ć

k

t lk

i ż

że każda czynność może być wykonana tylko raz i że na
każdym stanowisku można wykonać tylko jedną czynność
w zakładanym przedziale czasu

w zakładanym przedziale czasu.

2013-12-13

5

Zagadnienie przydziału



Model matematyczny zagadnienia przydziału
z ograniczeniami, że każdą czynność można wykonać
t lk

i ż

k żd

t

i k

ż

k

ć t lk

tylko raz i że na każdym stanowisku można wykonać tylko
jedną czynność, jest następujący:



Funkcja celu (np. minimalizacja czasu pracy):



Ograniczenia:



Ograniczenia:



Warunki brzegowe:

2013-12-13

6

Zagadnienie przydziału



Zagadnienie przydziału można rozwiązać:



Metodami programowania liniowego



Metodami programowania całkowitoliczbowego



Specjalnie opracowanymi do tego celu algorytmami
(np

algorytmem węgierskim

)

(np.

algorytmem węgierskim

).

2013-12-13

7

Algorytm węgierski (min)



Krok 1:

Przekształcenie macierzy kosztów tak, aby

w każdym jej wierszu i w każdej kolumnie występowało co

j

i j j d

najmniej jedno zero.
W tym celu należy znaleźć minimalny element w każdym
wierszu macierzy odjąć go od każdego elementu danego

wierszu macierzy, odjąć go od każdego elementu danego
wiersza i zbudować nową macierz.
Jeśli trzeba (gdy nie ma w każdej kolumnie zera) to

Jeśli trzeba (gdy nie ma w każdej kolumnie zera), to
z każdego elementu kolumny należy odjąć jej najmniejszy
element i zbudować nową macierz.

ą

2013-12-13

8

Algorytm węgierski (min)



Krok 2:

Skreślenie – w przekształconej macierzy kosztów

– wszystkich wierszy i kolumn zawierających zera, przy

ż i

żli i

j

i j

j li b li ii

i

h

użyciu możliwie najmniejszej liczby linii poziomych
i pionowych (należy pokryć liniami wszystkie zera w całej
macierzy)

macierzy).
Jeśli najmniejsza liczba linii niezbędnych do pokrycia
wszystkich zer jest równa wymiarowi macierzy, to możliwe

wszystkich zer jest równa wymiarowi macierzy, to możliwe
jest otrzymanie rozwiązania optymalnego. Przejść do
kroku 4.
Jeśli liczba skreśleń jest mniejsza od wymiaru macierzy,
należy przejść do kroku 3.

2013-12-13

9

Algorytm węgierski (min)



Krok 3:

Jeśli liczba skreśleń jest mniejsza od wymiaru

macierzy, to należy znaleźć najmniejszy nieskreślony

l

t i

element i:



Odjąć go od elementów nieskreślonych



Dodać go do elementów podwójnie skreślonych



Dodać go do elementów podwójnie skreślonych

Elementy skreślone jedną linią (raz) zostawiamy bez
zmian!

zmian!
Przejść do kroku 2.

2013-12-13

10

Algorytm węgierski (min)



Krok 4:

Ustalenie rozwiązania optymalnego w macierzy

końcowej, polegającego na takiej konstrukcji nowej

i

b j d ki

l ł

i t lk

l h

i

macierzy, aby jedynki znalazły się tylko w polach z zerami
(przy czym należy pamiętać, aby w każdym wierszu
i w każdej kolumnie wystąpiła tylko jedna jedynka)

i w każdej kolumnie wystąpiła tylko jedna jedynka).
Często możliwe jest uzyskanie kilku rozwiązań
optymalnych, dających tę samą wartość funkcji celu.

optymalnych, dających tę samą wartość funkcji celu.

2013-12-13

11

Algorytm węgierski (max)



Aby rozwiązać problem maksymalizacji zagadnienia,
należy:



Pomnożyć macierz (każdy element macierzy przez -1)



Następnie rozwiązać problem analogicznie jak problem
minimalizacji.

2013-12-13

12

Literatura



Ignasiak E. (red.), Badania operacyjne. Polskie
Wydawnictwo Ekonomiczne, Warszawa 1996.



Mitchell G.H. (red.), Badania operacyjne. Metody
i przykłady. Wydawnictwo Naukowo-Techniczne,
Warszawa 1977

Warszawa 1977.



Łucki Z. (red.), Matematyczne techniki zarządzania.
Przykłady i zadania Wydawnictwa AGH Kraków 1998

Przykłady i zadania. Wydawnictwa AGH, Kraków 1998.



Sawik T., Badania operacyjne dla inżynierów
zarządzania Wydawnictwa AGH Kraków 1998

zarządzania. Wydawnictwa AGH, Kraków 1998.



Wagner H.M., Badania operacyjne: zastosowania
w zarządzaniu. Państwowe Wydawnictwo Ekonomiczne,

ą

y

,

Warszawa 1980.

13

2013-12-13