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
edytujMamy 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
edytujPoniż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