Linijinio programavimo užduoties problema: įvadas ir priskyrimo modelis

Priskyrimo problema yra speciali linijinio programavimo problemos rūšis, susijusi su įvairių išteklių paskirstymu įvairioms veikloms vienu pagrindu. Ji tai daro taip, kad su procesu susijusios išlaidos arba laikas yra minimalūs, o pelnas arba pardavimas yra didžiausias. Nors problemos gali būti išspręstos paprastuoju metodu arba transportavimo metodu, tačiau priskyrimo modelis suteikia paprastesnį požiūrį į šias problemas.

Gamykloje vadovas gali turėti šešis darbuotojus ir šešias darbo vietas. Jis turės priimti sprendimą dėl to, kuris darbas turėtų būti suteiktas tam darbuotojui. Problema sudaro nuo vieno iki vieno pagrindo. Tai yra užduoties problema.

1. Priskyrimo modelis:

Tarkime, yra n palengvinančių ir n darbų, aišku, kad šiuo atveju bus n užduočių. Kiekvienas įrenginys arba darbuotojas gali atlikti kiekvieną darbą vienu metu. Tačiau turėtų būti nustatyta tam tikra procedūra, pagal kurią turėtų būti atliekamas priskyrimas, kad pelnas būtų maksimalus, o išlaidos arba laikas būtų kuo mažesnis.

Lentelėje Co _ij apibrėžiama kaip kaina, kai j darbas priskiriamas i darbuotojui. Čia gali būti pažymėta, kad tai yra ypatingas transportavimo problemos atvejis, kai eilučių skaičius yra lygus stulpelių skaičiui.

Matematinė formuluotė:

Bet koks esminis priskyrimo problemos sprendimas yra (2n - 1) kintamieji, kurių (n - 1) kintamieji yra nulis, n - darbo vietų skaičius arba įrenginių skaičius. Dėl šio didelio degeneracijos, jei problemą išsprendžiame įprastu transportavimo būdu, tai bus sudėtingas ir daug laiko reikalaujantis darbas. Tokiu būdu yra sukurtas atskiras metodas. Prieš pradedant absoliutųjį metodą, labai svarbu suformuluoti problemą.

Tarkime, _xjj yra kintamasis, kuris apibrėžiamas kaip

1 jei i ^th darbas priskiriamas j mašinai ar įrenginiui

0, jei i ^-asis darbas nėra priskiriamas j mašinai ar įrenginiui.

Dabar, kai problema sudaro vieną ar kelis pagrindus, arba vienas darbas turi būti priskirtas vienam įrenginiui ar mašinai.

Bendras priskyrimo išlaidas duos

Pirmiau pateiktas apibrėžimas gali būti plėtojamas į matematinį modelį taip:

Nustatykite x _ij > 0 (i, j = 1, 2, 3… n), kad

Taikomi apribojimai

ir x _ij yra arba nulis, arba vienas.

Problemos sprendimo būdas (vengrų kalba):

Apsvarstykite objektyvią minimalizavimo tipo funkciją. Įgyvendinant šią užduoties problemą dalyvauja šie veiksmai:

1. Raskite mažiausią sąnaudų elementą kiekvienoje pateiktos išlaidų lentelės eilutėje, pradedant nuo pirmos eilės. Dabar šis mažiausias elementas atimamas iš kiekvieno to eilutės elemento. Taigi, kiekvienoje šios naujos lentelės eilutėje gausime bent vieną nulį.

2. Sukūrę stalą (kaip 1 žingsniu) paimkite lentelės stulpelius. Nuo pirmojo stulpelio kiekviename stulpelyje suraskite mažiausią sąnaudų elementą. Dabar atimkite šį mažiausią elementą iš kiekvieno to stulpelio elemento. Atlikę 1 ir 2 žingsnius, kiekviename stulpelyje sumažintųjų išlaidų lentelėje gausime bent vieną nulį.

3. Dabar užduotys atliekamos sumažintai lentelei tokiu būdu.

(i) eilutės iš eilės nagrinėjamos tol, kol randama eilutė, kurioje yra lygiai vienas (vienas) nulis. Šiam vieninteliam nuliui priskiriamas kvadratas □ aplink jį ir atitinkamame stulpelyje visi kiti nuliai perbraukiami (x), nes jie nebus naudojami kitam priskyrimui šiame stulpelyje. Žingsnis atliekamas kiekvienai eilutei.

(ii) 3 stadija (i), dabar atlikta stulpeliuose, yra tokia: - stulpeliai iš eilės nagrinėjami tol, kol suras kolonėlę su lygiai vienu nuliu. Dabar priskyrimas šiam vieninteliam nuliui yra pastatomas kvadrato aplink jį ir tuo pačiu metu visi kiti atitinkamų eilučių nuliai perbraukiami (x) kiekvienam stulpui atliekamas žingsnis.

iii) 3, i) ir 3 (ii) žingsniai kartojami tol, kol visi nuliai yra pažymėti arba perbraukti. Dabar, jei pažymėtų nulio ar atliktų užduočių skaičius yra lygus eilučių arba stulpelių skaičiui, pasiekiamas optimalus sprendimas. Kiekvienoje arba stulpelyje bus lygiai vienas paskyrimas be jokio priskyrimo. Šiuo atveju pereisime prie 4 veiksmo.

4. Šiame etape atkreipkite dėmesį į minimalų skaičių (horizontalių ir vertikalių) eilučių, reikalingų visoms 3 etape gautoms matricoms padengti, skaičių.

i) Žymėjimo ženklas (

(ii) Dabar pažymėkite žymę (

(iii) Dabar pažymėkite visas eilutes, kurios dar nėra pažymėtos, ir pažymėtos stulpeliuose.

(iv) Visi etapai, ty (4 (i), 4 (ii), 4 (iii), kartojami tol, kol nebus pažymėta daugiau eilučių ar stulpelių.

(v) Dabar atkreipkite tiesias linijas, kurios eina per visas pažymėtas eilutes ir pažymėtas stulpelius. Taip pat galima pastebėti, kad nxn matricoje visuomet mažiau nei „n“ linijos apims visus nulius, jei jų nėra.

4. 4 žingsnyje, jei sudarytų linijų skaičius yra lygus n arba eilučių skaičius, tada jis yra optimalus sprendimas, jei ne, tada pereikite prie 6 veiksmo.

6. Pasirinkite mažiausią elementą tarp visų neatskleistų elementų. Dabar šis elementas atimamas iš visų neatskleistų elementų ir pridedamas prie elemento, esančio dviejų linijų susikirtimo vietoje. Tai yra šviežių užduočių matrica.

7. Pakartokite procedūrą nuo (3) žingsnio tol, kol užduočių skaičius bus lygus eilių arba stulpelių skaičiui.