3 Belangrijke tools voor operationeel onderzoek
Dit artikel werpt licht op de drie belangrijke instrumenten voor operationeel onderzoek. De hulpmiddelen zijn: 1. Lineaire programmering 2. Transportproblemen 3. Toewijzingsprobleem.
Operation Research: Tool # 1. Lineair programmeren:
Lineair programmeren is een wiskundige techniek die van toepassing is op bijna alle klasse van beslissingsproblemen. Deze techniek wordt toegepast om te kiezen als het beste alternatief uit een reeks van haalbare alternatieven.
In de functie LPP-objectief kunnen zowel beperkingen als lineaire wiskundige functies worden uitgedrukt, die kunnen worden gebruikt om de praktische planningsproblemen op te lossen. Het is een methode die wordt gebruikt om het gedrag van systemen te bestuderen.
LP houdt zich voornamelijk bezig met het beschrijven van de onderlinge relatie van de componenten van een systeem. Deze techniek is ontworpen om managers te helpen bij het plannen, beslissen en toewijzen van de middelen. Het management heeft altijd de neiging om het beste gebruik te maken van een organisatiehulpmiddel. Middelen omvatten machine-grondstoffen, arbeid, magazijn, tijd en geld.
Deze middelen kunnen worden gebruikt voor het produceren van producten van verschillende typen, zoals machines, onderdelen / componenten, meubels en voedselproducten, enz. Evenzo kunnen middelen worden gebruikt voor het leveren van diensten zoals planning voor verzending, advertentiebeleid en investeringsbeslissingen.
Alle organisaties moeten een beslissing nemen over de toewijzing van hun beperkte middelen. Het management moet dus voortdurend schaarse middelen toewijzen om de organisatiedoelstellingen / doelstellingen / doelen te bereiken.
Het adjectief lineair is gebruikt om een relatie tussen twee of meer variabelen te beschrijven. Programmeren houdt zich bezig met het gebruik van bepaalde wiskundige vergelijkingen die worden gebruikt om de best mogelijke oplossing te vinden voor een probleem met beperkte / schaarse middelen.
Dus lineaire programmering wordt gebruikt voor optimalisatieproblemen die aan de volgende voorwaarde voldoen:
(i) De te optimaliseren objectieffunctie moet goed gedefinieerd zijn en uitgedrukt worden als een lineaire functie van variabelen.
(ii) De beperking of deze met betrekking tot het bereiken van deze doelstellingen ook wordt uitgedrukt als lineaire kwaliteiten / ongelijkheden van variabel.
(iii) Er is ook een alternatief traject beschikbaar.
(iv) De beslissingsvariabelen zijn onderling gerelateerd en niet-negatief.
(v) Resource is beperkt.
Toepassing van lineaire programmering op industriële problemen:
(i) Planning ontwikkelen voor de voedselverwerkende industrie en voor aardolieraffinaderijen, enz.
(ii) In de metaalbewerkende industrie wordt het gebruikt voor het laden van winkels en voor het bepalen van de keuze tussen het kopen en produceren van verschillende onderdelen.
(iii) Het wordt gebruikt om verschillende ijzerertsen in de ijzer- en staalindustrie te evalueren.
(iv) Het wordt gebruikt om de hoeveelheid afsnijdingsverliezen in papierfabrieken te verminderen.
(v) Het wordt gebruikt om de optimale routering van berichten in een communicatienetwerk te vinden.
Lineaire programmeringsdefinitie:
Lineair programmeren is een wiskundig hulpmiddel / een techniek om het beste gebruik van de middelen van een organisatie te bepalen. Lineaire programmering is ontworpen om managers te helpen bij het plannen en beslissen. Als beslissingsinstrument heeft het zijn waarde bewezen op verschillende gebieden, zoals productie; marketingfinanciering, onderzoek en personeelsopdrachten.
Bepaling van optimale productmix, transportschema's portfoliokeuze machine-opdracht; fabriekslocatie en toewijzing van arbeid enz. zijn de weinige soorten problemen die met behulp van lineaire programmering kunnen worden opgelost.
"De analyse van problemen waarbij een lineaire functie van een aantal variabelen gemaximaliseerd (of geminimaliseerd) moet worden wanneer deze variabelen onderworpen zijn aan het aantal beperkingen in de vorm van lineaire in gelijkheden.", Samuelson en Slow
Volgens Loomba, "Lineaire programmering is slechts één aspect van wat een systeembenadering van management wordt genoemd, waarbij in alle programma's de uiteindelijke effecten worden bepaald en geëvalueerd in de realisatie van bedrijfsdoelen".
Lineaire programmeringsproblemen - grafische methode:
De stappen van de grafische methode kunnen als volgt worden samengevat:
1. Formuleer het probleem met lineaire programmering.
2. Maak een lijst van de gegeven beperkingslijnen en beschouw ze als vergelijkingen.
3Van de bovenstaande grafiek wordt het haalbare oplossingsgebied aangegeven.
4. Zoek de hoekpunten van de haalbare oplossingsregio.
5. Bereken de waarde van de doelfunctie op de hoekpunten.
6. Kies nu het punt waarop de doelfunctie een optimale waarde heeft.
Lineaire programmeringsproblemen-Wiskundige oplossing:
Hoewel de grafische methode om LPP op te lossen een waardevol hulpmiddel is om de basisstructuur ervan te begrijpen. De methode is van beperkt nut bij industriële problemen, aangezien het aantal variabelen dat daar voorkomt substantieel groot is. Dus een andere wiskundige oplossing genaamd simplexmethode is geschikt voor het oplossen van LPP met een groot aantal variabelen.
Het is een iteratieve procedure die LPP oplost in een eindig aantal stappen of een indicatie geeft dat er een onbegrensde oplossing is voor L.PR. Simplex-methode is een algebraïsche procedure voor het oplossen van lineaire programmeringsproblemen of is samengesteld uit een reeks herhaalde stappen om een optimale oplossing bereiken.
Het is een meest algemeen en meest algemeen gebruikt programmeeralgoritme. Theoretisch kan deze procedure elk probleem oplossen dat uit een aantal variabelen en beperkingen bestaat. Als het probleem uit meer dan drie variabelen en drie beperkingen bestaat, is het gebruik van de computer vereist. Fig. 31.9 toont de schematische weergave van het simplex-algoritme.
Verschillende stappen in de Simplex-procedure:
De stappen van deze procedure staan hieronder:
1. Formuleer het probleem door de objectieve functie en beperkingen te bepalen.
2. Converteer de ongelijkheden in gelijkheden om de standaardvorm te krijgen door het introduceren van slappe overschotten en kunstmatige variabelen in de doelfunctie.
3. Bereid de initiële simplex-tabel voor.
4. Bereken de waarde van zj (nettoverlies per eenheid) en cj-zj (netto bijdrage) voor deze oplossing.
5. Bepaal de invoervariabele (sleutelkolom) door de kolom met de meeste negatieve te selecteren
(z j - c j ).
6. Bepaal de vertrekkende variabele (sleutelrij) door de verhoudingskolom uit regel 5 te berekenen en de kleinste niet-negatieve waarde te kiezen.
7. Bereken de vervangende rij van de verbeterde simplex-tabel met regel 6.
8. Bereken de resterende rijen van de nieuwe tabel volgens regel 7.
9. Bereken de c j en z j -waarde voor deze oplossing.
10. Als er een niet-negatieve (c j - z j ) waarde is, gaat u terug naar stap 5.
11. Als er geen niet-negatieve ( cj - zj ) waarden zijn, is de optimale oplossing verkregen.
Voorbeeld 1:
Een boer heeft 1000 hectare grond waarop hij maïs, tarwe of sojabonen kan graven. Elke hectare maïs kost Rs. 100 voor voorbereiding, vereist 7 man werkdagen en levert een winst op van Rs. 30 Een hectare tarwe kost Rs. 120 om voor te bereiden, vereisen 10 man werkdagen en leveren een winst op van Rs. 40.
Een acre van soja-kosten Rs70 voor te bereiden vereist 8 man dagen werk en levert een winst op van Rs. 20 Als de boer Rs heeft. 100.000 voor voorbereiding en rekenen op 8000 man werkdagen. Hoeveel hectare moet aan elk gewas worden toegewezen om de winst te maximaliseren? (Gujarat MBA, 1989)
Oplossing:
Laat x hectare land toegewezen worden voor maïs
Een hectare land wordt toegewezen aan tarwe
Er wordt z acre land toegewezen aan sojabonen
Aangezien elk hectare land voor maïs een winst oplevert van Rs. 30, voor tarwe levert Rs. 40 en voor soja-Rs. 20. De wiskundige formulering van de LLP is
Max Z = 30x + 40y + 20z + 0S 1, + OS 2, + 0S 3
Onderworpen aan
100 x + 120y + 70z ≤ 100000
7x + 10y + 8z ≤ 8000
x + y + z ≤ 1000
x, y, z ≥ 0
Laten we de ongelijkheden omzetten in vergelijkingen door slappe variabelen S 1, S 2 en S 3 te introduceren. De objectieve functie en de beperking kunnen worden geschreven als
In de kolom van de basisvariabele zijn de vectoren voor variabele S 1, (1, 0, 0), S 2, (1, 0, 1) en S 3 (0, 0, 1) de aanvankelijk haalbare oplossing wordt gegeven door de variabelen S 1, S 2 en S 3 beide totale winst = 0
Nu Zj en Cj - Zj worden berekend door Regel 1, 2 en 3. De sleutelkolom wordt bepaald met start gemarkeerde kolom en Simplex Tabel II wordt als volgt voorbereid.
Tabel II biedt geen optimale oplossing. We gaan verder om eenvoudige tabel III voor te bereiden en de oplossing als volgt te verbeteren:
Minimalisatieprobleem door Big M. Methode:
In de industrie kan zich bevinden waar het doel kan zijn om de productiekosten of de productieduur te minimaliseren, dwz de doelfunctie moet worden geminimaliseerd. In dergelijke gevallen kunnen we op dezelfde manier doorgaan als een maximalisatieprobleem door simpelweg te vermenigvuldigen met beide zijden van objectieve functie by-1 In dergelijke situaties is minimalisatie van Z de maximalisatie van (-Z).
In dergelijke gevallen, aangezien de overtollige variabelen een negatieve waarde hebben die de non-negativiteitsbeperking schendt, introduceren we om deze moeilijkheid te overwinnen, nieuwe variabelen in de vorm van kunstmatige variabelen.
Nu kennen we 3000 coëfficiënten toe aan overschotvariabelen en + M aan kunstmatige variabelen. Om de bron te maken dat kunstmatige variabelen niet de basisvariabelen in de optimale oplossing zijn, kennen we ze zeer hoge kosten toe, vandaar dat M een zeer groot aantal is, dwz Big M of straf.
Deze methode wordt geïllustreerd aan de hand van het volgende:
Voorbeeld 2:
Operation Research: Tool # 2. Transportproblemen:
De vervoersproblemen zijn een van de soorten LPP waarbij het doel is goederen / producten in verschillende hoeveelheden van een enkel homogeen artikel / artikel naar verschillende bestemmingen te transporteren om de totale transportkosten in het dagelijks leven van de verschillende productieorganisaties of andere instellingen te minimaliseren. om verschillende overwegingen hun eindproducten of items op verschillende plaatsen op te slaan die worden aangeduid als hun oorsprong of waren, huis wanneer de levering aan gebruikers moet worden gedaan en de artikelen van oorsprong naar een of meer bestemmingen worden vervoerd, is het algemene doel van dit proces een distributiebeleid. zodanig dat de totale transportkosten minimaal zijn of dat de tijd die nodig is voor overslag minimaal is.
Nadat de naturel afgewerkte producten van de fabriek op de meest economische manier naar transportmagazijnen worden vervoerd in transportproblemen, zijn hier verschillende kenmerken van lineaire programmering waarneembaar, zowel de beschikbaarheid als de vereisten van verschillende centra zijn eindig en vormen de beperkte middelen transportproblemen in de speciale gevallen van de simplex-methode.
Toepassing in kleppen het transport van producten van verschillende bronnen naar verschillende bestemmingspunten zoals:
(i) Vervoeren van eenheden gescheurde bestemming. Het doel is om de transportkosten te minimaliseren.
(ii) Maximaliseer de winst bij het transporteren van de eenheden naar de bestemming.
De belangrijkste stappen zijn :
Stap 1:
Formuleer het probleem en stel het samen in de vorm van een transportmatrix.
Stap 2:
Verkrijg de basis haalbare oplossing.
Stap 3:
Test op optimale oplossing.
Stap 4:
Update de oplossing door succesverbeteringen tot geen verdere daling van de transportkosten mogelijk is.
Veelgebruikte methoden zijn:
1. Noordwestelijke hoekmethode.
2. Minste kosten methode.
3. Vogel's benaderingsmethode.
Stappen die betrokken zijn bij de North West Corner-methode:
Stap 1:
Constrict een lege maximale matrix aangevuld met rijen en kolommen.
Stap 2:
Geef aan het einde de rijtotalen en kolomtotalen aan.
Stap 3:
Beginnend met (11) cellen op de noordwestelijke hoek van de matrix, wijst u zoveel mogelijk aantal / aantal toe, waarbij u ervoor zorgt dat de toewijzing niet meer kan zijn dan de hoeveelheid die door de respectieve magazijnen wordt gevraagd, en niet meer dan de hoeveelheid die beschikbaar is bij de bevoorradingscentra.
Stap 4:
Nadat u het aantal vraag- en aanbodnummers in respectieve rijen en kolomtoewijzingen hebt aangepast, gaat u naar de eerste cel van en rij herhaalt u stap 3.
Stap 5:
Nadat de vraag van de eerste kolom is voldaan. Maak dan de volgende cel in de tweede kolom en eerste rij en ga naar stap 3.
Stap 6:
Als voor elke celtoevoer gelijk is aan de vraag, kan de volgende toewijzing de modus zijn in cellen in de volgende rijen en kolommen.
Stap 7:
Ga door met het proces totdat de totale beschikbare hoeveelheid volledig is toegewezen aan de cellen volgens de vereisten
Voorbeeld 3:
Los het volgende probleem op bij NWCM om de minimale transportkosten te berekenen:
Stappen in Least Cost Entry-methode:
Deze methode houdt rekening met de laagste kosten en neemt daarom minder tijd in beslag om het probleem op te lossen. De verschillende stappen zijn als volgt:
Stap 1:
Selecteer de cel met de laagste transportkosten tussen alle rijen en kolommen in de matrix. Wijs zoveel mogelijk toe om die rij of kolom te elimineren die ofwel de bron uitput of de vereiste volledig invult. Als beide voldoen, elimineren ze een van beide. Als de kleinste kostencel niet uniek is, selecteert u willekeurig een cel met de laagste kosten.
Stap 2:
Herhaal de procedure voor alle ongecodeerde rijen en kolommen met de volgende kleinste kostencel. Stap 3: Herhaal de procedure totdat alle bronnen zijn uitgeput of de vraag van alle bestemmingen vol is.
Voorbeeld 4:
Los het volgende probleem op met de goedkoopste methode:
Vogel Approximation Method:
Deze methode is een straf- of spijtmethode en verdient de voorkeur boven de andere twee methoden, waarbij de initiële basisuitvoerbare oplossing ofwel optimaal of zeer dicht bij de optimale oplossing wordt verkregen, waardoor de tijd die nodig is om de optimale oplossing te berekenen, wordt verminderd.
Bij deze methode is de allocatiebasis een kostenbesparing per eenheid, dwz die rij of kolom die de hoogste kostenpost boetes aangeeft / het verschil tussen de laagste en de op een na hoogste kosten wordt eerst geselecteerd met het oog op toewijzing. Op deze manier worden de volgende toewijzingen in de andere cellen ook gemaakt met het oog op de hoogste kostenpost per eenheid.
De toewijzing wordt gedaan om de boeterisico's te minimaliseren. Verschillende stappen zijn als volgt:
Stap 1:
Bereken de boete voor elke rij en kolom door het verschil tussen de kleinste en de volgende kleinste transportkosten in dezelfde rij en kolom te nemen, dwz het verschil geeft de boete aan die moet worden betaald als de toewijzing niet op de minimumkosten is gebaseerd criterium.
Stap 2:
Selecteer een rij of kolom met de grootste boete en wijs zo veel mogelijk toe aan de cel met de laagste kosten. In het geval van gelijkspel wordt eerst een cel met maximaal mogelijke toewijzing gekozen
Stap 3:
Doorstreep de rij of kolom na het vervullen van de vraag of het uitputten van de voorraad, de overblijvende rij of kolom krijgt een nultoevoer of -vraag toegewezen. Elke rij of kolom zonder toevoer of vraag die niet wordt gebruikt voor verdere berekeningen.
Stappen 4:
Herhaal de stappen 1 en 3 totdat alle bronnen zijn uitgeput of aan alle vereisten is voldaan.
Voorbeeld 5:
Een fabrikant wil 8 ladingen van zijn product verzenden vanuit productiecentra X, Y & Z naar distributiecentra A, B en C, de kilometerstand van oorsprong 0 naar bestemming D is de volgende matrix.
Voorbeeld 6:
Zoek de optimale oplossing voor het volgende transportprobleem door een initiële oplossing te krijgen met de benaderingsmethode van vogets:
Oplossing:
Laten we de benaderingsmethode van vogel toepassen. Problemen gebalanceerd als aanbod = vraag = 50 eenheden. Laten we de vogel-methode toepassen zoals weergegeven in de onderstaande tabel.
Transportkosten = 2 x 15 + 9 x 15 + 20 x 10 + 4 x 5 + 18 x 5 x 475 eenheden.
Controleer op Optimaal:
Optimaliteitstest kan worden uitgevoerd als aan twee voorwaarden is voldaan, dwz
1. Er zijn m + n - 1 toewijzing, waarvan m het aantal rijen is, n is het aantal kolommen. Hier m + n - = 6. Maar het aantal toewijzingen is vijf.
2. Deze m + n-1 toewijzingen moeten op onafhankelijke posities zijn, dwz het zou niet mogelijk moeten zijn om elke toewijzing te verhogen of te verlagen zonder de positie van de toewijzingen te veranderen of de rij- of kolombeperkingen te overtreden.
Een eenvoudige regel voor toewijzingen om in onafhankelijke posities te zijn, is dat het onmogelijk is om van elke toewijzing af te reizen, terug naar zichzelf een reeks horizontale en verticale stappen van de ene bezette cel naar de andere, zonder een directe omkering van de route. Er kan worden gezien dat in het huidige voorbeeld allocatie op onafhankelijke posities is omdat er geen gesloten lus kan worden gevormd op de toegewezen cellen.
Daarom is de eerste voorwaarde niet vervuld en daarom zullen we om aan de eerste voorwaarde te voldoen een kleine hoeveelheid E moeten toewijzen aan de lege cellen met de laagste transportkosten. Er kan worden gezien dat t kan worden toegewezen aan cel (2, 2) met een kostprijs van 7 eenheden en toch zullen de allocaties op een onafhankelijke positie blijven zoals hieronder in Tabel 2 wordt beschreven.
Het aantal toewijzingen is nu m + n - 6 = 6 en ze bevinden zich op onafhankelijke posities. Noteer kostenmatrix op toegewezen cellen. (Tafel 3)
Initiële kostenmatrix voor toegewezen cellen. Schrijf ook de waarden van u i en v j .
Uit tabel 5 is te zien dat celevaluatie in cel (1, 4) negatief is, dwz -4, en daarom door toewijzing aan cel (1, 4) de transportkosten verder worden verlaagd.
Laten we de oorspronkelijke toewijzingen en de voorgestelde nieuwe toewijzing noteren.
Uit Tabel 6 is te zien dat als we toewijzen aan cel (1, 4) een lus wordt gevormd zoals getoond en we 10 eenheden toewijzen zodat toewijzing bij cel (2, 4) verdwijnt zoals hieronder getoond in Tabel 7. Nieuw toewijzingstabel wordt
Transportkosten = 5X 2 + 10X 1 1 + 10X 7 + 15X 9 + 5X 4 + 18 + 5 = 435 eenheden.
dat wil zeggen dat de transportkosten zijn gedaald van 475 eenheden naar 435 eenheden.
Controleer op Optimaal:
Laten we eens kijken of deze oplossing optimaal is of niet? Daarvoor moeten opnieuw twee voorwaarden worden gecontroleerd, dwz
Aantal toewijzingen = m + n- 1 = 6 (tevreden)
Toewijzing op onafhankelijke positie (voldaan omdat gesloten lus voor toegewezen cellen niet is gevormd) Schrijf kosten op de toegewezen alle en waarden van u i en v j .
Operation Research: Tool # 3. Assignment Problem:
Opdrachtprobleem is een speciaal type lineair programmeringsprobleem dat zich bezighoudt met de toewijzing van de verschillende bronnen aan de verschillende activiteiten op één-op-één-basis.
Het doet het op een zodanige manier dat de kosten of tijd die het proces met zich meebrengt minimaal is en dat winst of verkoop maximaal is. Hoewel het probleem kan worden opgelost door de simplexmethode of door de transportmethode, maar het toewijzingsmodel geeft een eenvoudiger benadering voor deze problemen.
In een fabriek heeft een supervisor zes werknemers beschikbaar en zes banen om te ontslaan. Hij zal moeten beslissen welke baan moet worden toegewezen aan welke werknemer. Probleem vormt een op een basis. Dit is een toewijzingsprobleem.
Toewijzingsmodel:
Stel dat er n facilitaten en n banen zijn. Het is duidelijk dat in dit geval er n opdrachten zijn. Elke faciliteit of zeger kan elke taak een voor een uitvoeren. Maar er moet een bepaalde procedure zijn waardoor toewijzing moet worden gemaakt zodat de winst wordt gemaximaliseerd of de kosten of tijden worden geminimaliseerd.
In de tabel wordt Co ij gedefinieerd als de kosten wanneer j de baan is toegewezen aan de werknemer. Het kan hier worden opgemerkt dat dit een speciaal geval van transportprobleem is wanneer het aantal rijen gelijk is aan het aantal kolommen.
Wiskundige formulering:
Een mogelijke basisoplossing voor een toewijzingsprobleem bestaat uit (2n - 1) variabelen waarvan de (n - 1) variabelen nul zijn; n is aantal banen of aantal faciliteiten.
Vanwege deze hoge degeneratie zal het, als we het probleem oplossen met de gebruikelijke transportmethode, een complex en tijdrovend werk zijn. Daarom wordt er een aparte techniek voor afgeleid. Voordat we naar de absolute methode gaan, is het erg belangrijk om het probleem te formuleren.
Stel dat X ij een variabele is die is gedefinieerd als
Methode om probleem op te lossen (Hongaarse techniek):
Overweeg de doelfunctie van het minimaliseringstype.
Volgende stappen zijn betrokken bij het oplossen van dit toewijzingsprobleem:
1. Zoek 'het kleinste kostenelement in elke rij van de gegeven kostentabel beginnend met de eerste rij. Dit kleinste element wordt nu afgetrokken van elk element van die rij. Dus we krijgen ten minste één nul in elke rij van deze nieuwe tabel.
2. Nadat de tabel is geconstrueerd (zoals bij stap 1), worden de kolommen van de tabel genomen. Zoek vanuit de eerste kolom het kleinste kostenelement in elke kolom. Trek nu dit kleinste element van elk element van die kolom af. Nadat u stap 1 en stap 2 heeft uitgevoerd, krijgen we in de kolom met kostenverminderingen ten minste één nul in elke kolom.
3. Nu zijn de opdrachten voor de gereduceerde tabel op de volgende manier gemaakt:
(i) Rijen worden achtereenvolgens onderzocht, totdat de rij met exact één (één) nul is gevonden. Er wordt een toewijzing gemaakt aan deze enkele nul door er vierkant □ omheen te plaatsen en in de corresponderende kolom worden alle andere nullen doorgehaald (x) omdat deze niet zullen worden gebruikt om een andere toewijzing in deze kolom te maken. De stap wordt voor elke rij uitgevoerd.
(ii) Stap 3 (i) in nu uitgevoerd op de kolommen als volgt: Kolommen worden achtereenvolgens onderzocht tot een kolom met precies één nul is gevonden. Nu wordt een toewijzing gemaakt aan deze enkele nul door het vierkant eromheen te plaatsen en tegelijkertijd worden alle andere nullen in de overeenkomstige rijen doorstreept (x) wordt stap voor elke kolom uitgevoerd.
(iii) Stap 3 (i) en 3 (ii) worden herhaald totdat alle nullen gemarkeerd of doorgehaald zijn. Als het aantal gemarkeerde nullen of de gemaakte toewijzingen gelijk is aan het aantal rijen of kolommen, is de optimale oplossing bereikt. Er zal precies één toewijzing in elke kolom of kolom zijn zonder enige toewijzing. In dit geval gaan we naar stap 4.
4. Teken in dit stadium het minimale aantal lijnen (horizontaal en verticaal) dat nodig is om alle nullen in de matrix die in stap 3 is verkregen te dekken.
Volgende procedure is aangenomen:
(i) Vinkje (V) alle rijen aan die geen toewijzing hebben.
(ii) Kruis nu het vinkje (V) in al deze kolommen met nul in de met een vinkje gemarkeerde rijen.
(iii) Markeer nu alle rijen die nog niet zijn gemarkeerd en die een toewijzing hebben in de gemarkeerde kolommen.
(iv) Alle stappen, dwz 4 (1), 4 (2), 4 (3) worden herhaald totdat geen rijen of kolommen meer kunnen worden gemarkeerd,
(v) Teken nu rechte lijnen die door alle ongemarkeerde rijen en gemarkeerde kolommen gaan. Het valt ook op dat in een nxn-matrix altijd minder dan 'n'-lijnen alle nullen zullen beslaan als er geen oplossing tussen bestaat.
5. In stap 4, als het aantal getrokken lijnen gelijk is aan n of het aantal rijen, dan is dit de optimale oplossing als dat niet het geval is, ga dan naar stap 6.
6. Selecteer het kleinste element tussen alle niet-afgedekte elementen. Nu wordt dit element afgetrokken van alle onbedekte elementen en toegevoegd aan het element dat op het snijpunt van twee lijnen ligt. Dit is de matrix voor nieuwe opdrachten.
7. Herhaal de procedure vanaf stap (3) totdat het aantal toewijzingen gelijk is aan het aantal rijen of het aantal kolommen.
