Kollar efter optimitet

Optimitetstest kan utföras om två villkor är uppfyllda, dvs

1. Det finns m + n-1 tilldelningar, vars m är antal rader, n är antal kolumner. Här m + n - 1 = 6. Men antalet tilldelningar är fem.

2. Dessa m + n-1 anslag ska vara i oberoende positioner. Dvs. det borde inte vara möjligt att öka eller minska någon allokering utan att antingen ändra placeringen av tilldelningarna eller bryta mot rad- eller kolumnrestriktionerna.

En enkel regel för att anslagen ska vara i oberoende positioner är att det är omöjligt att resa från någon fördelning, till sig själv genom en serie horisontella och vertikala steg från en upptagen cell till en annan, utan direkt omväxling av rutt. Det framgår att i det nuvarande exemplet är allokering i oberoende positioner eftersom ingen sluten slinga kan bildas vid de tilldelade cellerna.

Därför är det första villkoret inte nöjd och därför för att tillfredsställa första villkoret måste vi fördela en liten mängd E till de lediga cellerna som har lägsta transportkostnad. Det kan ses att t kan tilldelas i cell (2, 2) med en kostnad på 7 enheter och fortfarande kommer anslagen att vara kvar i oberoende position enligt nedan:

Nu är antalet fördelningar m + n- = 6 och de befinner sig i oberoende positioner.

Skriv ner kostmatrisen vid tilldelade celler.

Initial kostnadsmatris för tilldelade celler.

Skriv även värdena för u _i och v _j som förklaras tidigare.

Cell utvärderingsmatris

Det framgår av tabell 5 att cellutvärdering vid cell (1, 4) är negativ dvs -4, därför att transportkostnaden ytterligare reduceras genom att allokera vid cell (1, 4). Låt oss skriva ned de ursprungliga anslagen och den föreslagna nya tilldelningen.

Det framgår av tabell 6 att om vi allokerar i cellen (1, 4) bildas en slinga som visas och vi fördelar 10 enheter så att tilldelningen i cellen (2, 4) försvinner som visas nedan i tabell 7.

Ny fördelningstabellen blir

Transportkostnad = 5X ₂ + 10X ₁ 1 + 10X ₇ + 15X9 + 5X ₄ + 18 + 5 = 435 enheter. dvs transportkostnaden har sjunkit från 475 enheter till 435 enheter.

Kolla efter Optimaiity:

Låt oss se om denna lösning är optimal! eller inte? För det igen måste två villkor kontrolleras, dvs

Antal fördelning = m + n - 1 = 6 (nöjd)

Allokering vid oberoende position (nöjd eftersom sluten slinga för tilldelade celler bildas inte)

Skriv kostnad på det tilldelade totalvärdet och värdena på u _i och v _j

Exempel 2:

(Obalanserad utbud och efterfrågan). Lös följande transportproblem

Total leverans = 200 enheter, Efterfrågan = 185 enheter.

Lösning:

Eftersom utbud och efterfrågan inte är lika är problemet obalanserat. För att balansera problemet måste en dummy coloumn läggas till som visas nedan. Efterfrågan på den dummy coloumn (store) kommer att vara 15 enheter.

Grundläggande genomförbar lösning:

Vi ska använda Vogels approximationsmetod för att hitta den initiala möjliga lösningen.

Den initiala möjliga lösningen ges av följande matris:

Optimitetstest:

Från ovanstående matris finner vi att:

(a) Antal anslag = m + n - 1 = 4 + 5-1 = 8

(b) Dessa m + n - 1 anslag är i oberoende positioner.

Därför kan optimitetstest utföras. Detta består av de tidigare beskrivna delstegen som visas i tabellerna nedan:

Eftersom cellvärden är + ve är den första möjliga lösningen optimal. Eftersom tabell 6 innehåller noll poster finns alternativa optimala lösningar. Den praktiska betydelsen av att efterfrågan är 15 enheter mindre än utbudet är att företaget kan sänka produktionen av 15 enheter på fabriken där den är oekonomisk.

Den optimala (minsta) transportkostnaden plus produktionskostnaden.

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. 1465.

Exempel 3:

Lös följande transportproblem för att maximera vinsten. På grund av skillnaden i råmaterialkostnad och transportkostnad skiljer sig vinsten för enheten i rupier som anges i tabellen nedan:

Lös problemet för att maximera vinsten.

Lösning:

Problemet är obalanserat och därför måste en dummyrad läggas till för att balansera den.

Hitta Initial Basic Feasible lösning:

Vi ska använda vogels approximationsmetod för att bestämma den initiala möjliga lösningen.

Observera att vi har att göra med maximeringsproblem. Därför ska vi ange skillnaden mellan de högsta och näst högsta elementen i varje rad till höger om raden och skillnaden mellan de högsta och näst högsta elementen i varje kolumn under motsvarande kolumn.

Var och en av dessa skillnader representerar enhetsvinsten förlorad för att inte tilldelas den högsta vinstcellen. Således väljer vi cell (2, 3) med högsta inmatning i rad 2, vilket motsvarar den högsta skillnaden på [45] vid tilldelningen.

Optimitetstest:

Erforderligt antal anslag = m + n - 1 = 3 + 4 - 1 = 6

Faktiskt antal fördelningar = 5.

Därför fördelar vi litet positivt antal € till cell (1, 3) (cellen har maximal vinst ur lediga celler) så att antalet anslag blir 6. Dessa 6 anslag är i oberoende positioner. Därför kan optimitetstest utföras.

Eftersom alla cellvärden antingen är negativa eller noll (maximeringsproblem) är den initiala grundläggande möjliga lösningen optimal. Efterfrågan vid första destinationen är "vänster missnöjd med 5 enheter. Vinsten är

Z _max = Rs. [90 x 70 + 90 x 100 + 110 x 30 + 130 x 100 + 0 x 5]

= Rs. 31.600.