Najlepsze pytania
Chronologia
Czat
Perspektywa

Programowanie zero-jedynkowe

Z Wikipedii, wolnej encyklopedii

Remove ads
Remove ads

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.
Remove ads

Przykład

Podsumowanie
Perspektywa

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.

Remove ads

Metody rozwiązywania

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

Więcej informacji Metoda, Złożoność obliczeniowa ...

Oznaczenia:

m – liczba równań
n – liczba zmiennych
Remove ads

Zobacz też

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads