Systemy reprezentantów. Permanent macierzy. ([9], str. 25-29)

Niech X = {1,2,…,n}; X ⊂ P;

X₁ ⊆ X, X₂ ⊆ X,…, X_m ⊆ X - ciąg podzbiorów n-elementowego zbioru X.

Ciąg x₁, x₂,…,x_m taki, że x_i ∈ X_i oraz x_i ≠ x_j dla i ≠ j, 1≤ i,j ≤ m, m≤n nazywamy
systemem reprezentantów dla ciągu podzbiorów X₁, X₂,…,X_n.

Element x _i nazywamy reprezentantem podzbioru X _i.

Jeżeli m = n, to system reprezentantów jest permutacją zbioru X.

Przykład 1.5.1. Wyznaczyć systemy reprezentantów dla ciągu {2,3} {1,2} {1,2,3}.

Wynik: {2,1,3}, {3,1,2}, {3,2,1}.

Permanent macierzy A = [a_ij] jest to liczba perA = ∑ a_1,k1⋅ a_2,k2⋅…⋅ a_m,km, k_i ≠ k_j, i ≠ j. k_i∈X.

Przykład 1.5.2. Obliczyć permanent macierzy A=

Wynik: perA = 1⋅2 + 1⋅1 + 1⋅2 = 5.

Twierdzenie 1.5.3. Liczba systemów reprezentantów dla ciągu X₁, X₂,…,X_m jest równa per A, gdzie A jest macierzą incydencji tego ciągu.

=================================================================

Zastosowanie systemów reprezentantów oraz permanantu macierzy:

1. 
   
   Obliczenie liczby składników (permutacji) rzadkiej macierzy M_n×n.

Niech M = wtedy macierz incydencji A =

oraz per A = 1⋅1⋅1+1⋅1⋅1+1⋅1⋅1 = 3.

Wynik: liczba systemów reprezentantów macierzy M jako sM = 3 = |{a,e,g}, {b,c,g}, {b,d,f}|.

2. Znajdowanie s.r. można zastosować do rozwiązywania problemu przydziału:

przydzielenie każdej osobie pracę tak, aby różnym osobom odpowiadały różne prace.

Zagadnienie optymalnego przydziału

Dane: produktywność każdej osoby O1…O4 do wykonania wyrobów W1…W3

Zadanie: Wybrać osoby O1…O4 do produkcji W1…W3 tak, aby ogólna produktywność była maksymalną.

1. Algorytm węgierski (Königa). ([9], str.28-31)

A. Przygotowanie macierzy:

- dokonać kwadratowość macierzy za pomocą dodatkowych kolumn o zerowej wartości,
- jeżeli i-ta osoba nie ma kwalifikacji do j-tej pracy, to a_ij = ∞.

- zmienić elementy macierzy do zadania minimalizacji.

B. Zerowanie (zero w każdym wierszu i każdej kolumnie).

C. Skreślenie wierszy i kolumn z zerami najmniejszą liczbą linii.

Jeżeli ta liczba = wymiar macierzy (n), to - na Koniec. Inaczej

D. Wybieramy najmniejszy nieskreślony element oraz
dodajemy do elementów podwójnie skreślonych i

odejmujemy od elementów nieskreślonych.

E. Pozostałe elementy pozostawiamy bez zmian i wracamy do p. B.

Koniec. Elementy macierzy zastępujemy zerami i jedynkami tak, aby w każdym wierszu i w każdej kolumnie występowała tylko jedna jedynka na miejscach, w których przed skreśleniem występowało zero.

1	0	1
1	2	0

a		b
c	d	e
f	g

1		1
1	1	1
1	1

		Wyroby
		W1	W2	W3
Osoby	O1	1	2	3
		O2	1		3
		O3	1	2
		O4	1	2	3

		Wyroby
		W1	W2	W3
Osoby	O1	80	105	79
		O2	109	-	90
		O3	100	97	-
		O4	95	80	85

		Wyroby
		W1	W2	W3	W4
Osoby	O1	29	4	30	109
		O2	0	∞	19	109
		O3	9	12	∞	109
		O4	14	29	24	109

		Wyroby
		W1	W2	W3	W4
Osoby	O1	80	105	79	0
		O2	109	∞	90	0
		O3	100	97	∞	0
		O4	95	80	85	0

29	4	30	109
0	∞	19	109
9	12	∞	109
14	29	24	109

		Wyroby
		W1	W2	W3
Osoby	O1	80	105	79
		O2	109	-	90
		O3	100	97	-
		O4	95	80	85

Tabela produktywności

Wynik

0	105	0	0
109	0	0	0
0	0	0	0
0	0	85	0

25	0	16	10
0	∞	9	14
0	3	∞	5
0	15	0	0

0	1	0	0
1	0	0	0
0	0	0	1
0	0	1	0

0	105	0	0
109	0	0	0
0	0	0	0
0	0	85	0

Wynik:

zatrudniono osoby
O1, O2, O4.

Wydajność
105+109+85 = 299

Permutacji (system reprezentantów)

Sortowanie wg produktywności

25	0	16	10
0	∞	9	14
0	3	∞	5
0	15	0	0

28	0	16	10
0	∞	6	11
0	0	∞	2
3	15	0	0

28	0	14	8
0	∞	4	9
0	0	∞	0
5	17	0	0

		Wyroby
		W1	W2	W3
Osoby	O1	80	105	79
		O2	109	-	90
		O3	100	97	-
		O4	95	80	85

2105	1 80	3 79	40
1109	3 90	4 0
1100	2 97	4 0
1 95	3 85	2 80	40

2. Algorytm rzeszowski ( szukanie SR lub permutacji)

105	105	105	105	80	80
109	90	90	0	90	90
0	100	0	100	97	0
85	0	95	85	0	80
299	295	290	290	267	250

---