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