Sjekker for optimalitet
Optimalitetstest kan utføres dersom to forhold er tilfredsstillende, dvs.
1. Det er m + n - 1 tildelinger, hvis m er antall rader, n er antall kolonner. Her m + n - 1 = 6. Men antall tildelinger er fem.
2. Disse m + n - 1 tildelingene skal være på uavhengige stillinger. Dvs. det bør ikke være mulig å øke eller redusere allokering uten å endre plasseringen av tildelingene eller bryte rad- eller kolonnrestriksjonene.
En enkel regel for tildelinger å være i uavhengige stillinger er at det er umulig å reise fra enhver tildeling, tilbake til seg selv ved en rekke horisontale og vertikale trinn danner en okkupert celle til en annen, uten direkte reversering av ruten. Det kan sees at i nåværende eksempel er allokering i uavhengige posisjoner, da ingen lukket sløyfe kan dannes ved de tildelte celler.
Derfor er første tilstand ikke fornøyd, og derfor for å tilfredsstille første betingelse, må vi tildele en liten mengde E til de ledige cellene som har laveste transportkostnad. Det kan sees at t kan allokeres på celle (2, 2) med 7 enheter, og fortsatt vil tildelingene forbli i uavhengig posisjon som beskrevet nedenfor:
Nå er antall tildelinger m + n- = 6 og de er i uavhengige stillinger.
Skriv ned kostnadsmatrisen ved tildelte celler.
Initial kostnadsmatrise for tildelte celler.
Skriv også verdiene til u i og v j som forklart tidligere.
Cell evalueringsmatrise
Det fremgår av tabell 5 at celleevaluering ved celle (1, 4) er negativ, dvs. -4, derfor blir transportkostnaden ytterligere redusert ved å allokere ved celle (1, 4). La oss skrive ned de opprinnelige tildelingene og den foreslåtte nye tildelingen.
Det kan ses fra tabell 6 at hvis vi allokerer ved celle (1, 4), dannes en sløyfe som vist og vi tildeler 10 enheter slik at allokering ved celle (2, 4) forsvinner som vist under i tabell 7.
Ny allokeringstabell blir
Transportkostnad = 5X 2 + 10X 1 1 + 10X 7 + 15X9 + 5X 4 + 18 + 5 = 435 enheter. dvs. Transportkostnadene har kommet ned fra 475 enheter til 435 enheter.
Sjekk etter optimalitet:
La oss se om denne løsningen er optimal! eller ikke? For det igjen må to forhold kontrolleres, dvs.
Antall tildeling = m + n - 1 = 6 (fornøyd)
Allokering i uavhengig posisjon (tilfredsstilt siden lukket sløyfe for tildelte celler er ikke dannet)
Skriv kostnaden ved allokert total og verdier av u i og v j
Eksempel 2:
(Ubalansert tilbud og etterspørsel). Løs opp følgende transportproblem
Total forsyning = 200 enheter, etterspørsel = 185 enheter.
Løsning:
Siden tilbud og etterspørsel ikke er like, er problemet ubalansert. For å balansere problemet må en dummy kolonne tilføyes som vist nedenfor. Etterspørselen på den dummy kolonnen (butikk) vil være 15 enheter.
Grunnleggende gjennomførbar løsning:
Vi skal bruke Vogels tilnærmelsesmetode for å finne den første mulige løsningen.
Den første mulige løsningen er gitt av følgende matrise:
Optimalitetstest:
Fra ovenstående matrise finner vi at:
(a) Antall tildelinger = m + n - 1 = 4 + 5-1 = 8
(b) Disse m + n - 1 tildelingene er i uavhengige stillinger.
Derfor kan optimalitetstest utføres. Dette består av delstrinnene som er forklart tidligere som vist i tabeller nedenfor:
Siden celleverdier er + ve er den første mulige løsningen optimal. Siden tabell 6 inneholder null oppføringer, finnes det alternative optimale løsninger. Den praktiske betydningen av at etterspørselen er 15 enheter mindre enn forsyningen, er at selskapet kan redusere produksjonen på 15 enheter på fabrikken hvor den er uøkonomisk.
Den optimale (minimum) transport pluss produksjonskostnad.
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.
Eksempel 3:
Løs det følgende transportproblemet for å maksimere fortjenesten. På grunn av forskjell i råvarekostnad og transportkostnad, varierer overskuddet for enheten i rupees som er gitt i tabellen under:
Løs problemet for å maksimere fortjenesten.
Løsning:
Problemet er ubalansert, og derfor må en dummy-rad legges til for å gjøre den balansert.
Finn første grunnleggende gjennomførbar løsning:
Vi skal bruke vogels tilnærmelsesmetode for å bestemme den første mulige løsningen.
Merk at vi har å gjøre med maksimeringsproblem. Derfor skal vi legge inn forskjellen mellom de høyeste og nest høyeste elementene i hver rad til høyre for rad og forskjellen mellom de høyeste og nest høyeste elementene i hver kolonne under den tilsvarende kolonnen.
Hver av disse forskjellene representerer ethetsresultatet fortapt for ikke å allokere til den høyeste profittcellen. Således, ved å gjøre tildelinger, velger vi først cellen (2, 3) med høyeste oppføring i rad 2 som tilsvarer den høyeste forskjellen på [45].
Optimalitetstest:
Nødvendig antall tildelinger = m + n - 1 = 3 + 4 - 1 = 6
Faktisk antall tildelinger = 5.
Derfor tildeler vi lite positivt antall € til celle (1, 3) (celle som har maksimal fortjeneste ut av ledige celler) slik at antall tildelinger blir 6. Disse 6 tildelingene er i uavhengige stillinger. Derfor kan optimalitetstest utføres.
Siden alle celleverdier er enten negative eller null (maksimeringsproblem), er den første grunnleggende mulige løsningen optimal. Etterspørselen ved første destinasjon er "venstre utilfreds med 5 enheter. Profitten er
Z max = Rs. [90 x 70 + 90 x 100 + 110 x 30 + 130 x 100 + 0 x 5]
= Rs. 31 600.
