Problem przydziału w programowaniu liniowym: Wprowadzenie i model przypisania

Problem przydziału jest szczególnym rodzajem problemu programowania liniowego, który zajmuje się przydzielaniem różnych zasobów do różnych działań na zasadzie jeden do jednego. Robi to w taki sposób, że koszt lub czas związany z procesem jest minimalny, a zysk lub sprzedaż jest maksymalna. Chociaż problemy można rozwiązać za pomocą metody simpleks lub metody transportowej, ale model przypisania daje prostsze podejście do tych problemów.

W fabryce osoba nadzorująca może mieć sześciu pracowników i sześć zadań do wykonania. Będzie musiał podjąć decyzję dotyczącą tego, które zadanie należy przyznać pracownikowi. Problem stanowi jeden do jednego. To jest problem z przydziałem.

1. Model przydziału:

Załóżmy, że istnieje n facilitates i n zadań, jasne jest, że w tym przypadku będzie n zadań. Każdy obiekt lub pracownik może wykonywać każde zadanie, po jednym na raz. Ale powinna istnieć pewna procedura, zgodnie z którą należy dokonać cesji, aby zysk był zmaksymalizowany lub zminimalizowany został koszt lub czas.

W tabeli Co _ij jest definiowane jako koszt, gdy j jest przypisane do ^tego pracownika. Można zauważyć, że jest to szczególny przypadek problemu z transportem, gdy liczba rzędów jest równa liczbie kolumn.

Formuła matematyczna:

Każde podstawowe, wykonalne rozwiązanie problemu z przyporządkowaniem składa się z zmiennych (2n - 1), z których zmienne (n - 1) wynoszą zero, n to liczba zleceń lub liczba obiektów. Z powodu tej wysokiej degeneracji, jeśli rozwiążemy problem za pomocą zwykłej metody transportu, będzie to praca złożona i czasochłonna. W ten sposób powstaje dla niej oddzielna technika. Przed przejściem do metody absolutnej bardzo ważne jest sformułowanie problemu.

Załóżmy, że x _jj jest zmienną zdefiniowaną jako

1, jeśli to zadanie jest przypisane do j maszyny lub obiektu

0, jeśli to zadanie nie jest przypisane do j maszyny lub obiektu.

Teraz problem stanowi jeden do jednego lub jedno zadanie należy przypisać do jednego obiektu lub maszyny.

Całkowity koszt zadania zostanie podany przez

Powyższą definicję można rozwinąć w model matematyczny w następujący sposób:

Określ x _ij > 0 (i, j = 1, 2, 3 ... n), aby

Podlega ograniczeniom

a x _ij oznacza zero lub jeden.

Metoda rozwiązania problemu (technika węgierska):

Rozważ obiektywną funkcję typu minimalizacji. Poniższe kroki są zaangażowane w rozwiązanie tego problemu przypisania,

1. Znajdź element najmniejszego kosztu w każdym wierszu tabeli kosztów, zaczynając od pierwszego wiersza. Teraz ten najmniejszy element jest odejmowany od każdego elementu tego rzędu. Tak więc, otrzymamy co najmniej jedno zero w każdym wierszu tej nowej tabeli.

2. Po skonstruowaniu stołu (jak po kroku 1) weź kolumny tabeli. Począwszy od pierwszej kolumny znajdź element najmniejszego kosztu w każdej kolumnie. Teraz odejmij ten najmniejszy element z każdego elementu tej kolumny. Po wykonaniu kroku 1 i kroku 2 otrzymamy co najmniej jedno zero w każdej kolumnie w tabeli kosztów zredukowanych.

3. Teraz zadania są wykonywane dla zredukowanej tabeli w następujący sposób.

(i) Wiersze są badane sukcesywnie, aż do znalezienia wiersza z dokładnie jednym (jednym) zerem. Przypisanie do tego pojedynczego zera polega na umieszczeniu kwadratu □ wokół niego, a w odpowiedniej kolumnie wszystkie pozostałe zera są przekreślone (x), ponieważ nie zostaną użyte do wykonania innego przypisania w tej kolumnie. Krok jest przeprowadzany dla każdego rzędu.

(ii) Etap 3 (i) teraz wykonywany na kolumnach w następujący sposób: - kolumny są badane sukcesywnie aż do znalezienia kolumny z dokładnie jednym zerem. Teraz przypisanie do tego pojedynczego zera polega na umieszczeniu kwadratu wokół niego i jednocześnie wszystkie pozostałe zera w odpowiednich wierszach są przekreślone (x) krok jest przeprowadzany dla każdej kolumny.

(iii) Kroki 3, (i) i 3 (ii) powtarza się, aż wszystkie zera zostaną oznaczone lub przekreślone. Teraz, jeśli liczba oznaczonych zer lub przypisanych wartości jest równa liczbie wierszy lub kolumn, uzyskano optymalne rozwiązanie. Będzie dokładnie jedno zadanie w każdej z kolumn lub bez żadnych przydziałów. W takim przypadku przejdziemy do kroku 4.

4. Na tym etapie narysuj minimalną liczbę linii (poziomą i pionową) konieczną do pokrycia wszystkich zer w macierzy uzyskanej w kroku 3, Następująca procedura jest przyjęta:

(i) Znak Tick (

(ii) Teraz znacznik wyboru (

(iii) Teraz zaznaczaj wszystkie wiersze, które nie są jeszcze oznaczone i które mają przypisanie w zaznaczonych kolumnach.

(iv) Wszystkie etapy tj. (4 (i), 4 (ii), 4 (iii) powtarza się, dopóki nie można oznaczyć więcej wierszy lub kolumn.

(v) Teraz narysuj proste linie, które przechodzą przez wszystkie niezaznaczone wiersze i zaznaczone kolumny. Można również zauważyć, że w macierzy nxn, zawsze mniej niż "n" wierszy obejmie wszystkie zera, jeśli nie ma wśród nich żadnego rozwiązania.

5. W kroku 4, jeśli liczba narysowanych linii jest równa n lub liczba rzędów, wówczas jest to optymalne rozwiązanie, jeśli nie, a następnie przejdź do kroku 6.

6. Wybierz najmniejszy element spośród wszystkich odkrytych elementów. Teraz ten element jest odejmowany od wszystkich niepokrytych elementów i dodawany do elementu, który leży na przecięciu dwóch linii. Jest to matryca dla świeżych zadań.

7. Powtórz procedurę od kroku (3), aż liczba przypisań stanie się równa liczbie wierszy lub liczby kolumn.