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