Kontrol for optimitet

Optimitetstest kan udføres, hvis to betingelser er opfyldt dvs.

1. Der er m + n - 1 tildelinger, hvis m er antal rækker, n er antal kolonner. Her m + n - 1 = 6. Men antallet af tildelinger er fem.

2. Disse m + n-1 tildelinger skal være i uafhængige stillinger. Dvs. det bør ikke være muligt at øge eller formindske en tildeling uden at ændre placeringen af ​​tildelingerne eller krænke række eller kolonne restriktioner.

En simpel regel for tildelinger at være i uafhængige stillinger er, at det er umuligt at rejse fra enhver tildeling, tilbage til sig selv ved en række horisontale og vertikale trin, der danner en besat celle til en anden uden direkte omstilling af rute. Det kan ses, at i det nuværende eksempel er tildelingen i uafhængige positioner, da der ikke kan dannes lukket sløjfer ved de tildelte celler.

Derfor er første betingelse ikke opfyldt, og derfor skal vi for at tilfredsstille første betingelse fordele en lille mængde E på de ledige celler med laveste transportomkostninger. Det kan ses, at t kan tildeles i celle (2, 2) med 7 enheder, og alligevel vil tildelingerne forblive i uafhængig stilling som beskrevet nedenfor:

Nu er antallet af tildelinger m + n- = 6 og de er i uafhængige stillinger.

Skriv ned omkostningsmatrix på tildelte celler.

Indledende omkostningsmatrix for tildelte celler.

Skriv også værdierne for u i og v j som forklaret tidligere.

Cellevalueringsmatrix

Det fremgår af tabel 5, at celleevaluering ved celle (1, 4) er negativ dvs. -4, hvorfor transportomkostningerne yderligere reduceres ved at allokere i celle (1, 4). Lad os skrive ned de oprindelige tildelinger og den foreslåede nye tildeling.

Det fremgår af tabel 6, at hvis vi tildeler i celle (1, 4), dannes en sløjfe som vist og vi tildeler 10 enheder, således at fordeling ved celle (2, 4) forsvinder som vist nedenfor i tabel 7.

Ny tildelingstabel bliver

Transportomkostninger = 5X 2 + 10X 1 1 + 10X 7 + 15X9 + 5X 4 + 18 + 5 = 435 enheder. dvs. Transportomkostninger er faldet fra 475 enheder til 435 enheder.

Check for Optimaiity:

Lad os se, om denne løsning er optima! eller ikke? For det skal to betingelser kontrolleres, dvs.

Antal tildeling = m + n - 1 = 6 (tilfreds)

Allokering i uafhængig position (tilfreds siden lukket kredsløb for tildelte celler er ikke dannet)

Skriv kost ved det tildelte total og værdier for u i og v j

Eksempel 2:

(Ubalanceret forsyning og efterspørgsel). Løs følgende transportproblem

Samlet udbud = 200 enheder, Efterspørgsel = 185 enheder.

Opløsning:

Da udbud og efterspørgsel ikke er ens, er problemet ubalanceret. For at balancere problemet skal der tilføjes en dummy kolonne som vist herunder. Efterspørgslen på den dummy coloumn (butik) vil være 15 enheder.

Grundlæggende gennemførlig løsning:

Vi skal bruge Vogels tilnærmelsesmetode til at finde den første mulige løsning.

Den første mulige løsning er givet ved følgende matrix:

Optimaltest:

Fra ovenstående matrix finder vi, at:

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

(b) Disse m + n - 1 tildelinger er i uafhængige positioner.

Derfor kan optimitetstest udføres. Dette består af de trin, der er forklaret tidligere, som vist i tabellerne nedenfor:

Da celleværdier er + ve er den første mulige løsning optimal. Da tabel 6 indeholder nul poster, findes der alternative optimale løsninger. Den praktiske betydning, at efterspørgslen er 15 enheder mindre end forsyningen, er, at virksomheden kan nedskære produktionen på 15 enheder på fabrikken, hvor den er uøkonomisk.

Den optimale (minimum) transport plus produktionsomkostninger.

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 følgende transportproblem for at maksimere fortjenesten. På grund af forskellen i råvareomkostninger og transportomkostninger varierer overskuddet for enheden i rupees som angivet i nedenstående tabel:

Løs problemet for at maksimere fortjenesten.

Opløsning:

Problemet er ubalanceret, og derfor skal en dummy række tilføjes for at gøre den afbalanceret.

Find den grundlæggende grundlæggende mulige løsning:

Vi skal bruge vogels tilnærmelsesmetode til at bestemme den første mulige løsning.

Bemærk at vi beskæftiger os med maksimeringsproblem. Derfor indgår vi forskellen mellem de højeste og næsthøjeste elementer i hver række til højre for rækken og forskellen mellem de højeste og de næsthøjeste elementer i hver kolonne under den tilsvarende kolonne.

Hver af disse forskelle repræsenterer enhedens fortjeneste tabt for ikke at allokere til den højeste profitcelle. Således vælger vi i første omgang celle (2, 3) med højeste indtastning i række 2, hvilket svarer til den højeste forskel på [45].

Optimaltest:

Nødvendigt antal tildelinger = m + n - 1 = 3 + 4 - 1 = 6

Faktisk antal tildelinger = 5.

Derfor tildeler vi lille positivt antal € til celle (1, 3) (celle med maksimal fortjeneste ud af ledige celler), så antallet af tildelinger bliver 6. Disse 6 tildelinger er i uafhængige stillinger. Derfor kan optimitetstest udføres.

Da alle celleværdier er enten negative eller nul (maksimeringsproblem), er den oprindelige basale gennemførlige løsning optimal. Efterspørgslen ved første destination er "venstre utilfreds med 5 enheder. Overskuddet er

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

= Rs. 31.600.