Opdrachtprobleem bij lineaire programmering: introductie- en toewijzingsmodel

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 er problemen kunnen worden opgelost met de simplexmethode of met de transportmethode, maar het toewijzingsmodel geeft een eenvoudiger aanpak 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.

1. toewijzingsmodel:

Stel dat er n facilitaten en n banen zijn, dan is het duidelijk dat in dit geval er n toewijzingen 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 tijd wordt geminimaliseerd.

In de tabel wordt Co _ij gedefinieerd als de kosten wanneer j ^de taak is toegewezen aan ^de werknemer. Hier is misschien 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 het aantal banen of het aantal voorzieningen. 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 _jj een variabele is die is gedefinieerd als

1 als de taak is toegewezen aan ^de machine of faciliteit

0 als de taak niet is toegewezen aan ^de machine of faciliteit.

Nu het probleem één-op-één-basis vormt of één taak wordt toegewezen aan één faciliteit of machine.

De totale toewijzingskosten worden gegeven door

De bovenstaande definitie kan als volgt worden omgezet in een wiskundig model:

Bepaal x _ij > 0 (i, j = 1, 2, 3 ... n) om

Onderworpen aan beperkingen

en x _ij is nul of één.

Methode om probleem op te lossen (Hongaarse techniek):

Overweeg de doelfunctie van het minimaliseringstype. Volgende stappen zijn betrokken bij het oplossen van dit opdrachtprobleem,

1. Zoek het kleinste kostenelement in elke rij van de gegeven kostentabel beginnend met de eerste rij. Nu wordt dit kleinste element afgetrokken van elk element van die rij. Dus we krijgen ten minste één nul in elke rij van deze nieuwe tabel.

2. Nadat u de tafel hebt geconstrueerd (zoals bij stap 1), neemt u de kolommen van de tafel. 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 minimumaantal regels (horizontaal en verticaal) dat nodig is om alle nullen in de matrix die in stap 3 is verkregen te dekken. De volgende procedure wordt gevolgd:

(i) Vinkje (

(ii) Nu vinkje (

(iii) Kruis nu alle rijen aan die nog niet zijn gemarkeerd en die een toewijzing hebben in de gemarkeerde kolommen.

(iv) Alle stappen, dwz (4 (i), 4 (ii), 4 (iii) worden herhaald totdat geen rijen of kolommen kunnen worden gemarkeerd.

(v) Teken nu rechte lijnen die alle ongemarkeerde rijen en gemarkeerde kolommen passeren. Het valt ook op dat in een nxn-matrix altijd minder dan 'n' lijnen alle nullen zullen beslaan als er geen oplossing tussen is.

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.