Programowanie zero-jedynkowe
Z Wikipedii
Programowanie zero-jedynkowe jest szczególnym przypadkiem 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 minimum, maksimum lub odpowiedniej wartości otrzymujemy decyzje dopuszczalne spełniające te założenia.
W konkretnych zagadnieniach w/w warunki nałożone na zmienne decyzyjne możemy 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.
[edytuj] 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ą
Tablica1 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
Tablica2 Tablica zmiennych decyzyjnych
O1 O2 O3 O4 O5 O6 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0
Z1 Z2 Z3 Z4 Z5 25 Z6
Tablica3 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ść 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.
Rozwiązanie
Tablica1 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
Tablica2 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
Tablica3 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. Do rozwiązania zagadnienia użyto programu SOLVER.
