Programowanie zero-jedynkowe

Programowanie zero-jedynkowe – szczególny przypadek zagadnienia transportowego. Otrzymujemy je nakładając na zmienne decyzyjne zagadnienia transportowego następujące warunki: zmienne decyzyjne mogą przyjmować wartości tylko 0 i 1 oraz w każdym wierszu i w każdej kolumnie tablicy zmiennych decyzyjnych może znajdować się tylko jedna zmienna decyzyjna z wartością 1. W konsekwencji suma wierszy i suma kolumn tablicy zmiennych decyzyjnych musi również wynosić jeden.

Forma liniowa albo funkcja celu w zagadnieniu transportowym jest równa sumie iloczynu tablicy warunków i tablicy zmiennych decyzyjnych. Nakładając na nią założenia odnośnie do minimum, maksimum lub odpowiedniej wartości otrzymujemy decyzje dopuszczalne spełniające te założenia.

W konkretnych zagadnieniach ww. warunki nałożone na zmienne decyzyjne można przedstawić w następującej bardziej opisowej formie:

• „Każdy pracownik może wykonywać tylko jedno zadanie, każde zadanie może być wykonywane jednocześnie tylko przez jednego pracownika.”
• „Każde zadanie można wykonywać jednocześnie tylko na jednej obrabiarce, każda obrabiarka może być zajęta wykonywaniem tylko jednego zadania.”
• „Na każdą trasę można przydzielić tylko jeden środek transportu, każdy środek transportu może być przydzielony tylko do jednej trasy”, itp.

Przykład

Mamy do wykonania sześć zadań oraz sześć osób. Każda z tych osób może wykonać tylko jedno zadanie i każde z tych zadań może być wykonane jednocześnie tylko przez jedną osobę. Przydatność poszczególnych osób do wykonywania poszczególnych zadań oceniliśmy na skali pięciopunktowej i przedstawiona jest w tablicy 1. Należy tak przydzielić osoby do poszczególnych zadań, aby łączna efektywność była jak największa.

W rozwiązaniu tego zagadnienia zakładamy, że elementy tablicy warunków przedstawiają efektywność wykonania zadań przez poszczególne osoby i funkcja celu powinna przyjąć wartość maksymalną.

Tablica 1. Tablica warunków.

	O1	O2	O3	O4	O5	O6
Z1	5	3	3	2	2	5
Z2	4	4	2	5	3	5
Z3	3	5	4	3	3	4
Z4	2	2	5	4	3	5
Z5	5	4	1	5	2	2
Z6	4	2	3	5	4	3

Tablica 2. Tablica zmiennych decyzyjnych.

	O1	O2	O3	O4	O5	O6
Z1	1	0	0	0	0	0
Z2	0	0	0	0	0	1
Z3	0	1	0	0	0	0
Z4	0	0	1	0	0	0
Z5	0	0	0	1	0	0
Z6	0	0	0	0	1	0

Tablica 3. Tablica wag.

	O1	O2	O3	O4	O5	O6
Z1	5	0	0	0	0	0
Z2	0	0	0	0	0	5
Z3	0	5	0	0	0	0
Z4	0	0	5	0	0	0
Z5	0	0	0	5	0	0
Z6	0	0	0	0	4	0

Wartość funkcji celu wynosi 29. Jest to jednocześnie rozwiązanie optymalne tego zagadnienia.

Załóżmy, że elementy tablicy warunków nie przedstawiają efektywności wykonania zadania przez poszczególne osoby, a koszty jednostkowe, względnie czas. Funkcja celu powinna wtedy przyjąć wartość minimalną, co będzie rozwiązaniem optymalnym.

Tablica 4. Tablica warunków.

	O1	O2	O3	O4	O5	O6
Z1	5	3	3	2	2	5
Z2	4	4	2	5	3	5
Z3	3	5	4	3	3	4
Z4	2	2	5	4	3	5
Z5	5	4	1	5	2	2
Z6	4	2	3	5	4	3

Tablica 5. Tablica zmiennych decyzyjnych.

	O1	O2	O3	O4	O5	O6
Z1	0	0	0	0	1	0
Z2	0	0	1	0	0	0
Z3	0	0	0	1	0	0
Z4	1	0	0	0	0	0
Z5	0	0	0	0	0	1
Z6	0	1	0	0	0	0

Tablica 6. Tablica wag.

	O1	O2	O3	O4	O5	O6
Z1	0	0	0	0	2	0
Z2	0	0	2	0	0	0
Z3	0	0	0	3	0	0
Z4	2	0	0	0	0	0
Z5	0	0	0	0	0	2
Z6	0	2	0	0	0	0

W tym przypadku wartość funkcji celu wynosi 13.

Metody rozwiązywania

Poniższa tabela zawiera kilka metod rozwiązywania problemów programowania zero-jedynkowego.

Metoda	Złożoność obliczeniowa	Uwagi
Przegląd bezpośredni	O(2nmn)	Stosowana tylko dla małej liczby zmiennych
Oparta na algorytmie najkrótszych dróg	Wielomianowa dla małych m i małych współczynników	Algorytm zmodyfikowany dla k∈{0,1}
Algorytm Balasa	Ponad wielomianowa	Opis algorytmu

Oznaczenia:

m – liczba równań

n – liczba zmiennych

Zobacz też

• programowanie liniowe
• programowanie matematyczne