Optimumo tikrinimas

Optimumo bandymas gali būti atliktas, jei įvykdomos dvi sąlygos:

1. Yra m + n - 1 asignavimai, kurių m yra eilučių skaičius, n yra stulpelių skaičius. Čia m + n - 1 = 6. Tačiau paskirstymo skaičius yra penki.

2. Šie m + n - 1 asignavimai turėtų būti nepriklausomi. Pvz., Neturėtų būti įmanoma padidinti ar sumažinti jokio paskirstymo, nekeičiant paskirstymo padėties arba pažeidžiant eilutės ar stulpelio apribojimus.

Paprasta taisyklė, pagal kurią paskirstymai turi būti nepriklausomose pozicijose, yra tai, kad neįmanoma važiuoti iš bet kokio paskirstymo, atgal į save horizontalių ir vertikalių pakopų, sudarytų iš vienos užimtos ląstelės, į kitą, be tiesioginio maršruto atšaukimo. Galima matyti, kad šiuo pavyzdžiu priskyrimas yra nepriklausomose padėtyse, nes priskirtose ląstelėse negali būti sudaryta uždara kilpa.

Todėl pirmoji sąlyga nėra įvykdyta, todėl, norint patenkinti pirmąją sąlygą, turėsime skirti mažą kiekį E laisvų ląstelių, turinčių mažiausią transportavimo kainą. Galima matyti, kad t galima priskirti ląstelėje (2, 2), kurių kaina yra 7 vienetai, ir vis dar skirstymai išliks nepriklausomoje padėtyje, kaip aprašyta toliau:

Dabar paskirstymo skaičius yra m + n- = 6 ir yra nepriklausomose pozicijose.

Užrašykite sąnaudų matricą priskirtose ląstelėse.

Pradinė paskirstytų ląstelių sąnaudų matrica.

Taip pat įrašykite u i ir v j reikšmes, kaip paaiškinta anksčiau.

Ląstelių vertinimo matrica

Iš 5 lentelės matyti, kad ląstelių (1, 4) ląstelių įvertinimas yra neigiamas, ty -4, todėl skirstant ląstelių (1, 4) transportavimo išlaidas, dar labiau sumažėja. Užrašykime pradinius asignavimus ir siūlomą naują paskirstymą.

Iš 6 lentelės matyti, kad jei skirstome ląstelėje (1, 4), kaip parodyta, yra suformuota kilpa, ir skiriame 10 vienetų, kad paskirstymas ląstelėje (2, 4) išnyktų, kaip parodyta 7 lentelėje.

Bus sukurta nauja paskirstymo lentelė

Transportavimo kaina = 5X 2 + 10X 1 1 + 10X 7 + 15X9 + 5X 4 + 18 + 5 = 435 vnt. ty Transportavimo išlaidos sumažėjo nuo 475 vienetų iki 435 vienetų.

Patikrinkite „Optimaiity“:

Pažiūrėkime, ar šis sprendimas yra optimalus! arba ne? Tam dar reikia patikrinti dvi sąlygas, ty

Paskirstymo skaičius = m + n - 1 = 6 (patenkintas)

Paskirstymas savarankiškoje padėtyje (patenkintas, nes nesukurta paskirtoje ląstelių kilpa)

Įrašykite sąnaudas priskirtose visumose ir u i ir v j reikšmėse

2 pavyzdys:

(Nesubalansuotas tiekimas ir paklausa). Išspręskite šią transportavimo problemą

Bendras tiekimas = 200 vnt., Paklausa = 185 vnt.

Sprendimas:

Kadangi pasiūla ir paklausa nėra vienodos, problema yra nesubalansuota. Siekiant subalansuoti problemą, reikia pridėti manekeno stulpelį, kaip parodyta toliau. Paklausa toje manekeno stulpelyje (parduotuvėje) bus 15 vienetų.

Pagrindinis įmanomas sprendimas:

Norėdami rasti pradinį įmanomą sprendimą, naudosime „Vogel“ aproksimacijos metodą.

Pradinį įmanomą sprendimą pateikia ši matrica:

Optimumo testas:

Iš aukščiau nurodytos matricos matome, kad:

a) Paskirstymų skaičius = m + n - 1 = 4 + 5-1 = 8

b) Šie m + n - 1 asignavimai yra nepriklausomi.

Todėl galima atlikti optimalumo bandymą. Tai susideda iš ankstesnių etapų, kaip parodyta toliau pateiktose lentelėse:

Kadangi ląstelių reikšmės yra + ve, pirmasis galimas sprendimas yra optimalus. Kadangi 6 lentelėje pateikiami nuliniai įrašai, yra alternatyvių optimalių sprendimų. Praktinė paklausos reikšmė 15 vienetų mažesnė už pasiūlą yra ta, kad įmonė gali sumažinti 15 vienetų gamybą gamykloje, kur ji yra neekonomiška.

Optimalus (minimalus) transportavimas ir gamybos sąnaudos.

Z = R. (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.

3 pavyzdys:

Išspręskite šią transportavimo problemą, kad padidintumėte pelną. Dėl skirtingų žaliavų savikainos ir transportavimo sąnaudų vieneto rupijų pelnas skiriasi, kuris pateikiamas toliau pateiktoje lentelėje:

Išspręskite problemą, kad gautumėte kuo daugiau pelno.

Sprendimas:

Problema yra nesubalansuota ir todėl reikia pridėti manekeno eilutę, kad ji būtų subalansuota.

Rasti pradinį pagrindinį įmanomą sprendimą:

Mes nustatysime vogelio aproksimacijos metodą, kad nustatytume pradinį galimą sprendimą.

Atkreipkite dėmesį, kad susiduriame su didinimo problema. Todėl įvesime skirtumą tarp aukščiausių ir antrųjų aukščiausių elementų kiekvienoje eilutėje, esančioje dešinėje nuo eilutės, ir skirtumą tarp aukščiausių ir antrųjų aukščiausių elementų kiekviename stulpelyje po atitinkamu stulpeliu.

Kiekvienas iš šių skirtumų reiškia prarastą vieneto pelną, nesuteikiant didžiausią pelną. Taigi, skirstant lėšas, iš pradžių mes išrenkame langelį (2, 3) su didžiausiu įrašu 2 eilutėje, kuri atitinka didžiausią skirtumą [45].

Optimumo testas:

Reikalingas paskirstymų skaičius = m + n - 1 = 3 + 4 - 1 = 6

Faktinis paskirstymo skaičius = 5.

Todėl ląstelei (1, 3) skiriame nedidelį teigiamą skaičių € (ląstelių, turinčių maksimalų pelną iš laisvų ląstelių), kad paskirstymų skaičius taptų 6. Šie 6 asignavimai yra nepriklausomose pozicijose. Todėl galima atlikti optimalumo bandymą.

Kadangi visos ląstelių reikšmės yra neigiamos arba nulinės (maksimalizavimo problema), pradinis pagrindinis įmanomas sprendimas yra optimalus. Pirmosios paskirties paklausa „paliekama nepatenkinti 5 vienetų. Pelnas yra

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

= Rs. 31, 600.