Sprawdzanie optymalności
Test optymalności można wykonać, jeśli spełnione są dwa warunki, tj
1. Istnieją przydziały m + n-1, których m to liczba wierszy, n to liczba kolumn. Tutaj m + n - 1 = 6. Ale liczba przydziałów to pięć.
2. Te przydziały m + n - 1 powinny znajdować się na niezależnych pozycjach. Oznacza to, że zwiększenie lub zmniejszenie alokacji nie powinno być możliwe bez zmiany pozycji alokacji lub naruszenia ograniczeń dotyczących wierszy lub kolorów.
Prostą zasadą przydziałów na niezależne pozycje jest to, że niemożliwe jest przemieszczanie się z każdej alokacji, z powrotem do siebie poprzez szereg pionowych i poziomych kroków z jednej zajętej komórki do drugiej, bez bezpośredniego odwrócenia trasy. Można zauważyć, że w niniejszym przykładzie alokacja odbywa się w niezależnych pozycjach, ponieważ nie można utworzyć zamkniętej pętli w przydzielonych komórkach.
Dlatego też pierwszy warunek nie jest spełniony, dlatego aby spełnić pierwszy warunek, będziemy musieli przeznaczyć niewielką ilość E na wolne komórki o najniższych kosztach transportu. Widać, że t może być przydzielone w komórce (2, 2) z kosztem 7 jednostek, a mimo to alokacje pozostaną w niezależnej pozycji, jak opisano poniżej:
Teraz liczba przydziałów wynosi m + n- = 6 i są one w niezależnych pozycjach.
Zapisz macierz kosztu w przydzielonych komórkach.
Macierz początkowej kosztów dla przydzielonych komórek.
Napisz również wartości u i v v jak wyjaśniono wcześniej.
Macierz oceny komórki
Z tabeli 5 można wywnioskować, że ocena komórki w komórce (1, 4) jest ujemna, tj. -4, a zatem dzięki alokacji w komórce (1, 4) koszty transportu jeszcze bardziej zmniejszają się. Zapiszmy pierwotne alokacje i proponowaną nową alokację.
Z tabeli 6 wynika, że jeśli przydzielimy komórkę (1, 4), utworzona zostanie pętla, jak pokazano, i przydzielamy 10 jednostek, aby przydział w komórce (2, 4) znikał, jak pokazano poniżej w tabeli 7.
Nowa tabela alokacji stanie się
Koszt transportu = 5X 2 + 10X 1 1 + 10X 7 + 15X9 + 5X 4 + 18 + 5 = 435 jednostek. Koszt transportu spadł z 475 do 435 jednostek.
Sprawdź Optimaiity:
Zobaczmy, czy to rozwiązanie jest optymalne! albo nie? W tym celu należy ponownie sprawdzić dwa warunki, tj
Liczba przydziałów = m + n - 1 = 6 (spełnione)
Alokacja w niezależnej pozycji (spełnione, ponieważ zamknięta pętla dla przydzielonych komórek nie jest tworzona)
Zapisz koszt w przydzielonych allach i wartościach u i v j
Przykład 2:
(Niezbilansowany popyt i podaż). Rozwiąż następujący problem z transportem
Całkowita podaż = 200 sztuk, popyt = 185 sztuk.
Rozwiązanie:
Ponieważ podaż i popyt nie są równe, dlatego problem jest niezrównoważony. Aby zrównoważyć problem, należy dodać ślepy kolor, jak pokazano poniżej. Zapotrzebowanie na tę manekinową coloumn (sklep) wyniesie 15 sztuk.
Podstawowe możliwe rozwiązanie:
Będziemy używać metody aproksymacji Vogla do znalezienia początkowego możliwego rozwiązania.
Pierwsze możliwe rozwiązanie jest podane w następującej macierzy:
Test optymalności:
Z powyższej matrycy wynika, że:
(a) Liczba przydziałów = m + n - 1 = 4 + 5-1 = 8
(b) Te przydziały m + n - 1 znajdują się w niezależnych pozycjach.
Dlatego można przeprowadzić test optymalności. Składa się z podtrybów podanych wcześniej, jak pokazano w poniższych tabelach:
Ponieważ wartości komórek są większe, pierwsze możliwe rozwiązanie jest optymalne. Ponieważ tabela 6 zawiera wpisy zerowe, istnieją alternatywne rozwiązania optymalne. Praktyczne znaczenie popyt jest o 15 jednostek mniej niż podaż, że firma może zmniejszyć produkcję 15 sztuk w fabryce, gdzie jest nieopłacalne.
Optymalny (minimalny) transport i koszt produkcji.
Z = Rs. (4 x 25 + 6 x 5 + 8 x 20 +10 x 70 + 4 x 30 + 13 x 15 + 8 x 20 + 0 x 15)
= Rs. (100 + 30 + 160 + 170 + 120 + 195 + 160 + 0) = Rs. 1 465.
Przykład 3:
Rozwiąż następujący problem z transportem, aby zmaksymalizować zysk. Ze względu na różnicę w kosztach surowców i kosztach transportu, zysk jednostki w rupiach różni się, co przedstawiono w poniższej tabeli:
Rozwiąż problem, aby zmaksymalizować zyski.
Rozwiązanie:
Problem jest niezbalansowany i dlatego należy dodać obojętny wiersz, aby był zrównoważony.
Znajdź rozwiązanie Initial Basic wykonalne:
Będziemy używać metody aproksymacji firmy Vogel do określenia początkowego możliwego rozwiązania.
Zauważ, że mamy do czynienia z problemem maksymalizacji. W związku z tym wprowadzimy różnicę między najwyższym i drugim najwyższym elementem w każdym rzędzie po prawej stronie rzędu, a różnicą między najwyższym i drugim najwyższym elementem w każdej kolumnie poniżej odpowiedniej kolumny.
Każda z tych różnic oznacza utracony zysk jednostkowy za brak alokacji do komórki najwyższego zysku. Tak więc, dokonując alokacji, najpierw wybieramy komórkę (2, 3) z najwyższym wpisem w wierszu 2, co odpowiada najwyższej różnicy [45].
Test optymalności:
Wymagana liczba przydziałów = m + n - 1 = 3 + 4 - 1 = 6
Aktualna liczba przydziałów = 5.
Dlatego przydzielamy małą dodatnią liczbę € do komórki (1, 3) (komórka mająca maksymalny zysk z wolnych komórek), tak aby liczba przydziałów wynosiła 6. Te 6 przydziałów znajduje się w niezależnych pozycjach. Dlatego można przeprowadzić test optymalności.
Ponieważ wszystkie wartości komórek są ujemne lub zerowe (problem z maksymalizacją), początkowe podstawowe możliwe rozwiązanie jest optymalne. Popyt na pierwszym celu jest "pozostawiony niezadowolony przez 5 jednostek. Zysk jest
Z max = Rs. [90 x 70 + 90 x 100 + 110 x 30 + 130 x 100 + 0 x 5]
= Rs. 31 600.
