3 Svarbios operacijų tyrimų priemonės
Šiame straipsnyje aptariamos trys svarbios veiklos tyrimų priemonės. Priemonės yra: 1. Linijinis programavimas 2. Transportavimo problemos 3. Priskyrimo problema.
Operacijos tyrimai: įrankis # 1. Linijinis programavimas:
Linijinis programavimas - tai matematinė technika, pritaikyta beveik visoms sprendimų problemų grupėms. Šis metodas taikomas siekiant pasirinkti geriausią alternatyvą iš galimų alternatyvų.
LPP objekto funkcijose ir suvaržymuose galima išreikšti linijinę matematinę funkciją, kuria galima išspręsti praktines planavimo problemas. Tai metodas, naudojamas sistemų elgsenai tirti.
LP daugiausia susijęs su sistemos komponentų tarpusavio ryšių aprašymu. Šis metodas skirtas padėti vadovams planuoti, priimti sprendimus ir paskirstyti išteklius. Vadovybė visada turi tendenciją kuo efektyviau panaudoti organizacijos išteklius. Ištekliai apima mašinų žaliavas, darbą, sandėlį, laiką ir pinigus.
Šie ištekliai gali būti naudojami įvairių rūšių gaminiams gaminti: mašinos, dalys / komponentai, baldai ir maisto produktai ir pan. Panašiai ištekliai gali būti naudojami paslaugoms teikti, pavyzdžiui, laivybos tvarkaraštis, reklamos politika ir investavimo sprendimai.
Visos organizacijos turi priimti sprendimą dėl savo ribotų išteklių skyrimo. Taigi vadovybei reikia nuolat skirti ribotus išteklius, kad būtų pasiekti organizacijos tikslai / tikslai.
Būdvardis linijinis buvo apibūdintas ryšys tarp dviejų ar daugiau kintamųjų. Programavimas susijęs su tam tikrų matematinių lygčių naudojimu, siekiant gauti geriausią įmanomą problemos, susijusios su ribotais / ribotais ištekliais, sprendimą.
Taigi, optimizavimo problemoms, kurios atitinka šią sąlygą, naudojamas tiesinis programavimas:
i) Tikslinga funkcija, kuri turi būti optimizuota, turėtų būti aiškiai apibrėžta ir išreikšta kaip tiesinė kintamųjų funkcija.
(ii) Apribojimas, jei tai susiję su šių tikslų pasiekimu, taip pat išreiškiamas kintamojo linijinėmis savybėmis / nelygybėmis.
iii) Taip pat yra keletas alternatyvių veiksmų.
(iv) Sprendimų kintamieji yra tarpusavyje susiję ir ne neigiami.
(v) Ištekliai yra riboti.
Linijinio programavimo taikymas pramoninėms problemoms:
i) Plėsti maisto perdirbimo pramonės ir naftos perdirbimo įmonių planavimą ir tt
ii) metalo apdirbimo pramonėje ji naudojama parduotuvių pakrovimui ir pasirinkimo tarp įvairių dalių pirkimui ir gamybai nustatyti.
iii) jis naudojamas įvairioms geležies rūdoms geležies ir plieno pramonėje įvertinti.
(iv) Jis naudojamas apdailos nuostolių sumažinimui popieriaus gamyklose.
(v) Jis naudojamas norint rasti optimalų pranešimų perdavimo ryšių tinkle maršrutą.
Linijinis programavimas Apibrėžimas:
Linijinis programavimas yra matematinis įrankis / technika, skirta nustatyti geriausius organizacijos išteklių panaudojimo būdus. Linijinis programavimas yra skirtas padėti vadovams planuoti ir priimti sprendimus. Kaip sprendimų priėmimo priemonė ji parodė savo vertę įvairiose srityse, pvz., Gamyboje; rinkodaros finansavimas, mokslinių tyrimų ir personalo užduotys.
Optimalaus produktų asortimento nustatymas, transportavimo grafikų portfelio parinkimo mašinos paskyrimas; augalų išdėstymas ir darbo vietų paskirstymas ir pan. yra keletas problemų, kurias galima išspręsti naudojant linijinį programavimą.
„Problemų analizė, kurioje turi būti maksimaliai padidinta (arba sumažinta) kelių kintamųjų linijinė funkcija, kai šie kintamieji priklauso nuo apribojimų skaičiaus linijinių lygių forma.“, Samuelson ir Slow
„Loomba “ teigimu, „Linijinis programavimas yra tik vienas aspektas, vadinamas sistemos požiūriu į valdymą, kur visose programose yra suprojektuota ir vertinama pagal jų galutinį poveikį įgyvendinant verslo tikslus“.
Linijinės programavimo problemos - grafinis metodas:
Grafinio metodo etapus galima apibendrinti taip:
1. Formuluoti linijinio programavimo problemą.
2. Apskaičiuokite nurodytas suvaržymo linijas, laikydami jas lygtimis.
3. Iš aukščiau pateikto grafiko nurodykite galimą sprendimo būdą.
4. Suraskite galimo sprendimo regiono atraminius taškus.
5. Apskaičiuokite tikslinės funkcijos vertę grįžimo taškuose.
6. Dabar pasirinkite tašką, kur tikslinė funkcija turi optimalią vertę.
Linijinės programavimo problemos - matematinis sprendimas:
Nors grafinis LPP sprendimo būdas yra vertinga pagalba, skirta suprasti jos pagrindinę struktūrą. Metodas yra labai naudingas pramoninėse problemose, nes ten esančių kintamųjų skaičius iš esmės yra didelis, todėl dar vienas matematinis sprendimas, vadinamas simpleksiniu metodu, yra tinkamas LPP sprendimui su daugybe kintamųjų.
Tai iteratyvi procedūra, kuri arba išsprendžia LPP baigtiniu skaičiumi žingsnių arba davė nuorodą, kad L.PR paprastasis metodas yra algebrinė procedūra linijinių programavimo problemų sprendimui arba yra sudaryta iš pakartotinių veiksmų, skirtų pasiekti optimalų sprendimą.
Tai yra plačiausiai naudojamas ir dažniausiai naudojamas programavimo algoritmas. Teoriškai ši procedūra gali išspręsti bet kokią problemą, kurią sudaro bet koks skaičius kintamųjų ir apribojimų. Jei problemą sudaro daugiau nei trys kintamieji ir trys apribojimai, reikia naudoti kompiuterį. 31.9 pav. Pavaizduotas paprastojo algoritmo schema.
Įvairūs „Simplex“ procedūros etapai:
Šios procedūros veiksmai išvardyti toliau:
1. Formuluokite problemą, nustatydami tikslinę funkciją ir apribojimus.
2. Konvertuokite nelygybę į lygiaverčius, kad gautumėte standartinę formą, įvedant laisvas perteklius ir dirbtinius kintamuosius tikslinėje funkcijoje.
3. Paruoškite pradinį simplekso lentelę.
4 .Skaičiuokite z j (grynojo nuostolio už vienetą) ir c j - z j (grynojo įnašo) vertę šiam sprendimui.
5. Nustatykite įvesties kintamąjį (raktų stulpelį), pasirinkdami stulpelį su labiausiai neigiamu
(z j - c j ).
6. Nustatykite išeinantį kintamąjį (raktų eilutę), apskaičiuodami santykio stulpelį iš 5 taisyklės ir pasirinkdami mažiausią ne neigiamą vertę.
7. Apskaičiuokite patobulintos simpleksinės lentelės pakeitimo eilutę pagal 6 taisyklę.
8. Apskaičiuokite likusias naujos lentelės eilutes pagal 7 taisyklę.
9. Apskaičiuokite šio tirpalo cj ir z j reikšmę.
10. Jei yra neigiamų (c j - z j ) reikšmių, grįžkite į 5 veiksmą.
11. Jei nėra neigiamų ( cj -z j ) verčių, gautas optimalus sprendimas.
1 pavyzdys:
Ūkininkas turi 1000 akrų žemės, ant kurio jis gali išpjauti kukurūzus, kviečius ar sojos pupeles. 100 už paruošimą, reikia 7 darbo dienų darbo ir duoda pelną R. 30 Kv. Kv. 120 paruošti, reikalauti 10 darbo dienų darbo ir gauti pelną R. 40.
Norint paruošti sojos pupelių kaštus Rs70, reikia 8 darbo dienų ir Rs pelnas. 20 Jei ūkininkas turi Rs. 100 000 paruošimui ir 8000 žmonių darbo dienų skaičiui. Kiek akrų turėtų būti skiriama kiekvienai kultūrai, siekiant padidinti pelną? (Gudžarato MBA, 1989)
Sprendimas:
Leiskite x akrų žemės skirti kukurūzams
kv. kv
za akrų žemės skiriama sojos pupelėms
Kadangi kiekvienas žemės akras kukurūzams duoda Rs pelną. 30, kviečių derlius Rs. 40 ir sojų pupelių R. 20. LLP matematinė formuluotė yra
Maks. Z = 30x + 40y + 20z + 0S 1, + OS 2, + 0S3
Priklauso nuo
100 x + 120y + 70z ≤ 100000
7x + 10y + 8z ≤ 8000
x + y + z ≤ 1000
x, y, z ≥ 0
Konvertuokite nelygybę į lygtis įvedant atleidžiamus kintamuosius S 1, S 2 ir S 3 . Tikslo funkcija ir suvaržymas gali būti parašyti kaip
Pagrindiniame kintamajame stulpelyje vektoriai yra kintamiesiems S 1, (1, 0, 0), S 2, (1, 0, 1) ir S 3 (0, 0, 1), o pradinis galimas sprendimas pateikiamas kintamųjų S 1, S 2 ir S 3 abu bendras pelnas = 0
Dabar Zj ir Cj - Zj apskaičiuojami pagal 1, 2 ir 3 taisykles. Pagrindinė stulpelis nustatomas su pradiniu pažymėtu stulpeliu ir Simplex II lentelė yra parengta taip.
II lentelėje nėra optimalaus sprendimo, kurį toliau tęsiame rengdami paprastą III lentelę ir tobulindami sprendimą taip:
Minimizavimo problema pagal didelį M. metodą:
Pramonėje gali būti vieta, kurioje gali būti siekiama sumažinti gamybos sąnaudas arba gamybos trukmę, ty tokiais atvejais tikslo funkcija turi būti sumažinta, nes mes galime veikti taip pat, kaip maksimalizavimo problema, paprasčiausiai padauginus iš abiejų pusių Objektyvios funkcijos reikšmė-1 Tokiais atvejais Z sumažinimas bus (-Z) maksimalizavimas.
Tokiais atvejais, kai pertekliniai kintamieji turi neigiamą vertę, pažeidžiančią negatyvumo apribojimą, norint įveikti šį sunkumą, įvedame naują dirbtinių kintamųjų stilių.
Dabar mes priskiriame 3000 koeficientų perteklių kintamiesiems ir + M dirbtiniams kintamiesiems, kad šaltinis, kad dirbtiniai kintamieji nėra pagrindiniai kintamieji optimaliame sprendime, priskiriame jiems labai didelę kainą, todėl M yra apibrėžiamas kaip labai didelis skaičius, ty Big M arba bausmė.
Šis metodas iliustruojamas taip:
2 pavyzdys:
Operacijos tyrimai: įrankis Nr. 2. Transporto problemos:
Transporto problemos yra vienas iš LPP tipų, kurių tikslas - gabenti įvairias vienalytes prekes / prekes į įvairias paskirties vietas, kad būtų sumažintos bendros gamybos sąnaudos kasdieniame gyvenime įvairiose gamybos organizacijose ar kitose įmonėse. įvairiais sumetimais saugokite savo galutinius produktus ar daiktus įvairiose vietose, vadinamose kilme arba sandėliuose, namuose, kai tiekimas turi būti teikiamas naudotojams, tada elementai gabenami iš kilmės į vieną ar daugiau paskirties vietų, bendras šio proceso tikslas yra nuspręsti dėl paskirstymo politikos tokiu būdu, kad bendra transporto kaina būtų minimali arba perkrovimo metu suvartojamas laikas būtų minimalus.
Po to, kai transportavimo metu iš gamyklos pagaminti produktai bus transportuojami ekonomiškiausiu būdu į sandėlius, čia galima pastebėti įvairias linijinio programavimo savybes, o įvairių centrų prieinamumas ir reikalavimai yra riboti ir sudaro ribotas išteklių transportavimo problemas, susijusias su ypatingais atvejais iš paprastojo metodo.
Taikymas vožtuvuose, kai produktai gabenami iš kelių šaltinių į įvairius paskirties taškus:
i) gabenamų vienetų vežimas paskirties vietoje. Tikslas - sumažinti transporto išlaidas.
(ii) Didinti pelną gabenant vienetus į paskirties vietą.
Pagrindiniai veiksmai yra šie :
1 žingsnis:
Suformuluokite problemą ir nustatykite transportavimo matricą.
2 žingsnis:
Gaukite pagrindinį įmanomą sprendimą.
3 žingsnis:
Tirpalo optimalumo bandymas.
4 veiksmas:
Atnaujinkite sprendimą sėkmingų patobulinimų pagalba, kol nebus įmanoma sumažinti transporto išlaidų.
Dažniausiai naudojami metodai:
1. Šiaurės vakarų kampo metodas.
2. Mažiausios kainos metodas.
3. Vogelio aproksimacijos metodas.
Veiksmai, susiję su Šiaurės Vakarų kampo metodu:
1 žingsnis:
Sukurkite tuščią didžiausią matricą, užpildytą eilėmis ir stulpeliais.
2 žingsnis:
Nurodykite eilutės sumas ir stulpelių sumas pabaigoje.
3 žingsnis:
Pradedant nuo (11) ląstelės matricos šiaurės vakarų atkarpoje, didžiausias galimas kiekis / skaičius skiriamas, kad paskirstymas negali būti didesnis nei kiekis, kurio reikalauja atitinkamos gamyklos, ir daugiau nei tiekimo centruose.
4 veiksmas:
Atlikę pasiūlos ir paklausos numerių koregavimą atitinkamose eilutėse ir stulpeliuose, pereikite prie pirmojo langelio ir iš eilės pakartokite 3 veiksmą.
5 veiksmas:
Po to, kai pirmosios stulpelio paklausa bus įvykdyta, atlikite kitą langelį antroje stulpelyje ir pirmoje eilutėje ir pereikite prie 3 veiksmo.
6 veiksmas:
Jei bet kuriam ląstelių tiekimui reikalingi tokie patys, sekantis paskirstymas gali būti režimas ląstelėse kitose eilutėse ir stulpeliuose.
7 veiksmas:
Tęskite procesą, kol bendras reikalingas kiekis bus visiškai paskirstytas ląstelėms pagal reikalavimą
3 pavyzdys:
NWCM išspręskite šią problemą, kad apskaičiuotumėte minimalias transportavimo išlaidas:
Mažiausių sąnaudų įvedimo metodo veiksmai:
Šiuo metodu atsižvelgiama į mažiausią kainą ir todėl trunka mažiau laiko problemai išspręsti.
1 žingsnis:
Pasirinkite matricos eilutes ir stulpelius mažiausia transportavimo kaina. Kiek įmanoma panaikinkite tą eilutę ar stulpelį, kuris išleidžia šaltinį arba užpildo visą reikalavimą. Jei abu yra patenkinti juos pašalinti vieną. Jei mažiausios kainos langelis nėra unikalus, pasirinkite savavališkai bet kurį langelį su mažiausia kaina.
2 žingsnis:
Pakartokite procedūrą visoms neperkeltoms eilutėms ir stulpeliams su sekančia mažiausia kaina. 3 veiksmas: pakartokite procedūrą, kol visi šaltiniai bus išnaudoti, arba visos paskirties vietos paklausa yra visiškai užpildyta.
4 pavyzdys:
Išspręskite šią problemą pagal mažiausią kainą:
Vogelio priartinimo metodas:
Šis metodas yra bausmių ar regretų metodas ir yra pirmenybė, palyginti su kitais dviem metodais, kai pradinis pagrindinis įmanomas sprendimas yra optimalus arba labai artimas optimaliam sprendimui, todėl laikas, reikalingas optimaliam tirpalui apskaičiuoti, yra mažesnis.
Taikant šį metodą, paskirstymo pagrindas yra vieneto sąnaudų nuobauda, ty pirma eilutė arba stulpelis, kuriame nurodoma didžiausia vieneto sąnaudų nuobauda / skirtumas tarp mažiausios ir kitos didžiausios kainos, pirmiausia skiriamas paskirstymo tikslais. Tokiu būdu vėlesni paskirstymai kitose ląstelėse taip pat atliekami atsižvelgiant į aukščiausias vieneto sąnaudų bausmes.
Paskirstymas atliekamas siekiant sumažinti skirtingas bausmės išlaidas:
1 žingsnis:
Apskaičiuokite baudą už kiekvieną eilutę ir stulpelį, kai tai atliekama vien tik mažiausio ir artimiausio mažiausio transportavimo kainos skirtumo nustatymu toje pačioje eilutėje ir stulpelyje, ty skirtumas parodo, kokią baudą reikia sumokėti, jei paskirstymas nebus atliktas iki minimalių išlaidų kriterijus.
2 žingsnis:
Pasirinkite eilutę ar stulpelį, kuriame yra didžiausia bausmė, ir kiek įmanoma paskirstykite mažiausiai kainuojančią langelį. Tais atvejais, kai susieti, pirmiausia pasirenkamas maksimalaus galimo paskirstymo langelis
3 žingsnis:
Atlikę paklausą arba išeikvojus tiekimą, iš eilės arba stulpelio išbraukite likusį eilutę arba stulpelį, kuriam priskiriamas nulinis pasiūla ar paklausa. Bet kokia eilutė ar stulpelis su nuliniu pasiūla arba paklausa nenaudojami tolesniems skaičiavimams.
4 žingsniai:
Pakartokite 1 ir 3 veiksmus, kol visi šaltiniai bus išnaudoti arba visi reikalavimai yra įvykdyti.
5 pavyzdys:
Gamyba nori pristatyti 8 savo produkto krovinius iš gamybos centrų X, Y & Z į paskirstymo centrus A, B ir C, o tarpas nuo kilmės 0 iki paskirties D yra ši matrica.
6 pavyzdys:
Raskite optimalų sprendimą dėl šių transportavimo problemų, pradedant pradiniu sprendimu su vogets aproksimavimo metodu:
Sprendimas:
Leiskite taikyti vogelio aproksimacijos metodą. Problemos subalansuotos kaip pasiūla = paklausa = 50 vienetų. Leiskite taikyti vogelio metodą, kaip nurodyta žemiau esančioje lentelėje.
Transportavimo kaina = 2 x 15 + 9 x 15 + 20 x 10 + 4 x 5 + 18 x 5 x 475 vnt.
Patikrinkite, ar optimaliai:
Optimumo bandymas gali būti atliktas, jei įvykdomos dvi sąlygos:
1. Yra m + n - 1 paskirstymas, kurio m yra eilučių skaičius, n yra stulpelių skaičius. Čia m + n - = 6. Tačiau paskirstymo skaičius yra penki.
2. Šie asignavimai m + n-1 turėtų būti nepriklausomose pozicijose, ty neturėtų būti įmanoma padidinti ar sumažinti paskirstymo, nekeičiant asignavimų padėties arba pažeidžiant eilutės ar stulpelio apribojimus.
Paprasta taisyklė, pagal kurią skirstymai turi būti nepriklausomose pozicijose, yra tai, kad neįmanoma važiuoti iš bet kokio paskirstymo, grįžti į 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 gali būti priskirtas ląstelėje (2, 2), kurių kaina yra 7 vienetai, ir vis dar skirstymai išliks nepriklausomoje padėtyje, kaip aprašyta 2 lentelėje.
Dabar paskirstymų skaičius yra m + n - 6 = 6 ir yra nepriklausomose pozicijose. Užrašykite sąnaudų matricą priskirtose ląstelėse. (3 lentelė)
Pradinė paskirstytų ląstelių sąnaudų matrica. Taip pat įrašykite u i ir v j reikšmes.
Iš 5 lentelės matyti, kad ląstelių (1, 4) ląstelių įvertinimas yra neigiamas, ty -4, todėl skiriant 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. paskirstymo lentelė taps
Transportavimo kaina = 5X 2 + 10X 1 1 + 10X 7 + 15X 9 + 5X 4 + 18 + 5 = 435 vnt.
ty Transportavimo išlaidos sumažėjo nuo 475 vienetų iki 435 vienetų.
Patikrinkite, ar optimaliai:
Pažiūrėkime, ar šis sprendimas yra optimalus, ar ne? Tam dar reikia patikrinti dvi sąlygas, ty
Paskirstymo skaičius = m + n- 1 = 6 (patenkintas)
Paskirstymas nepriklausomoje padėtyje (patenkintas, nes nesukurta paskirtoje ląstelėje esanti kilpa) Rašykite kainą pagal visas paskirtas ir u i ir v j reikšmes.
Operacijos tyrimai: įrankis Nr. 3. Priskyrimo problema:
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 problemą galima išspręsti 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.
Priskyrimo modelis:
Tarkime, yra n palengvinančių ir n darbų. Akivaizdu, 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, arba kad išlaidos arba laikas būtų kuo mažesnis.
Lentelėje Co ij yra apibrėžiama kaip kaina, kai j darbas priskiriamas i darbuotojui. Čia galima pažymėti, 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 yra 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, kad X ij yra kintamasis, kuris apibrėžiamas kaip
Problemos sprendimo būdas (vengrų kalba):
Apsvarstykite objektyvią minimalizavimo tipo funkciją.
Įgyvendinant šią užduoties problemą dalyvauja šie veiksmai:
1. Suraskite „mažiausios kainos elementą kiekvienoje pateiktos išlaidų lentelės eilutėje nuo pirmos eilės. Dabar šis mažiausias elementas atimamas iš kiekvieno tos eilutės elemento. Taigi, kiekvienoje šios naujos lentelės eilutėje gausime bent vieną nulį.
2. Pastatę lentelę (kaip 1 žingsnis), 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 taip: Kolonos iš eilės tikrinamos 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) pakopos kartojamos tol, kol visi nuliai bus 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 minimalų skaičių linijų (horizontalių ir vertikalių), būtinų padengti visus nulius matricoje, gautoje 3 pakopoje.
Priimta tokia procedūra:
i) Pažymėkite ženklą (V) visas eilutes, kuriose nėra jokio priskyrimo.
(ii) Dabar pažymėkite žymę (V) visuose šiuose stulpeliuose, kuriuose pažymėtos eilutės yra nulinės.
(iii) Dabar pažymėkite visas eilutes, kurios dar nėra pažymėtos, ir pažymėtos stulpeliuose.
(iv) Visi veiksmai, ty 4 (1), 4 (2), 4 (3), kartojami tol, kol nebus pažymėta daugiau eilučių ar stulpelių,
(v) Dabar pieškite tiesias linijas, kurios eina per visas nepaž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.
