Programowanie zero-jedynkowe


Programowanie zero-jedynkowe w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

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 | edytuj kod

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 | edytuj kod

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

Oznaczenia:

m – liczba równań n – liczba zmiennych

Zobacz też | edytuj kod

Na podstawie artykułu: "Programowanie zero-jedynkowe" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy