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. MetodaZłożoność obliczeniowaUwagiPrzegląd bezpośredniO(2nmn)Stosowana tylko dla małej liczby zmiennychOparta na algorytmie najkrótszych drógWielomianowa dla małych m i małych współczynnikówAlgorytm zmodyfikowany dla k∈{0,1}Algorytm BalasaPonad wielomianowaOpis algorytmu Oznaczenia: m – liczba równań n – liczba zmiennych
Zobacz też programowanie liniowe programowanie matematyczne
Kategoria:Teoria decyzji