Opgaveproblem i lineær programmering: Introduktions- og opgavemodel

Opgaveproblem er en speciel type lineær programmeringsproblem, der omhandler fordelingen af ​​de forskellige ressourcer til de forskellige aktiviteter på et til en basis. Det gør det på en sådan måde, at omkostningerne eller den tid, der er involveret i processen, er minimum, og fortjeneste eller salg er maksimalt. Selvom der kan løses problemer ved hjælp af simplexmetode eller ved transportmetode, men tildelingsmodellen giver en enklere tilgang til disse problemer.

I en fabrik kan en tilsynsførende have seks arbejdstagere til rådighed og seks arbejdspladser til brand. Han bliver nødt til at træffe beslutning om hvilket job der skal gives til hvilken arbejdstager. Problemet danner et til et grundlag. Dette er et opgaveproblem.

1. Opgave Model:

Antag at der er n letter og n job Det er klart, at i dette tilfælde vil der være n opgaver. Hver facilitet eller sige arbejdstager kan udføre hvert job, en ad gangen. Men der bør være en vis procedure, hvormed opgaven skal ske, så overskuddet maksimeres, eller prisen eller tiden minimeres.

I tabellen er Co ij defineret som kostprisen, når jobbet er tildelt den pågældende medarbejder. Det bemærkes måske her, at dette er et specielt tilfælde af transportproblem, når antallet af rækker er lig med antallet af kolonner.

Matematisk formulering:

Enhver grundlæggende gennemførlig løsning af et opgaveproblem består af (2n - 1) variabler, hvor variablerne (n - 1) er nul, n er antal job eller antal faciliteter. På grund af denne høje degeneration, hvis vi løser problemet ved sædvanlig transportmetode, vil det være et komplekst og tidskrævende arbejde. Således er en separat teknik afledt af den. Før du går til den absolutte metode, er det meget vigtigt at formulere problemet.

Antag x jj er en variabel, der er defineret som

1 hvis det første job er tildelt den pågældende maskine eller facilitet

0 hvis det pågældende job ikke er tildelt maskinen eller anlægget.

Nu som problemet danner et til et grundlag eller ét job skal tildeles et enkelt anlæg eller en maskine.

Den samlede opgave omkostninger vil blive givet af

Ovennævnte definition kan udvikles til matematisk model som følger:

Bestem x ij > 0 (i, j = 1, 2, 3 ... n) for at

Underlagt begrænsninger

og x ij er enten nul eller en.

Metode til løsning af problem (ungarsk teknik):

Overvej den objektive funktion af minimeringstype. Følgende trin er involveret i at løse dette opgaveproblem,

1. Find det mindste omkostningselement i hver række af den givne omkostnings tabel, der begynder med den første række. Nu trækkes dette mindste element fra hvert element af den pågældende række. Så vi får mindst et nul i hver række i denne nye tabel.

2. Efter at have lavet bordet (som ved trin-1) skal du tage tabellernes kolonner. Fra det første kolonne skal du finde det mindste omkostningselement i hver kolonne. Træk nu det mindste element fra hvert element i den kolonne. Efter at have udført trin 1 og trin 2 vil vi få mindst et nul i hver kolonne i tabellen med nedsat pris.

3. Nu er opgaverne lavet til det reducerede bord på følgende måde.

(i) Rækker undersøges successivt, indtil rækken med nøjagtigt enkelt (en) nul er fundet. Opgave foretages til dette enkelt nul ved at sætte firkant □ omkring det og i den tilsvarende kolonne krydses alle andre nuller (x), fordi disse ikke vil blive brugt til at foretage en anden opgave i denne kolonne. Trin udføres for hver række.

(ii) Trin 3 (i) i nu udført på kolonnerne som følger: - Kolonner undersøges successivt, indtil en kolonne med nøjagtigt et nul er fundet. Nu er tildelingen lavet til dette enkelt nul ved at sætte firkanten rundt om det og samtidig er alle andre nuller i de tilsvarende rækker krydset ud (x) trin udføres for hver søjle.

(iii) Trin 3, (i) og 3 (ii) gentages, indtil alle nuller er markeret eller krydset ud. Nu, hvis antallet af markerede nuller eller de udførte opgaver er lig med antallet af rækker eller kolonner, er der opnået en optimal løsning. Der vil være nøjagtig enkelt opgave i hver eller kolonner uden nogen opgave. I dette tilfælde vil vi gå til trin 4.

4. På dette stadium tegner det mindste antal linjer (vandret og lodret), der er nødvendige for at dække alle nuller i matrixen opnået i trin 3, Følgende procedure er vedtaget:

(i) Tick markering (

) alle rækker, der ikke har nogen opgave.

(ii) Nu kryds markering (

) alle disse kolonner, der har nul i de markerede rækker.

(iii) Marker nu alle de rækker, der ikke allerede er markeret, og som har en opgave i de markerede kolonner.

(iv) Alle trin, dvs (4 (i), 4 (ii), 4 (iii) gentages, indtil der ikke kan markeres flere rækker eller kolonner.

(v) Træk nu lige linjer, der passerer gennem alle de u markerede rækker og markerede kolonner. Det kan også bemærkes, at i en nxn matrix vil altid mindre end 'n' linjer dække alle nuller, hvis der ikke er nogen løsning blandt dem.

5. I trin 4, hvis antallet af linjer tegnet er lig med n eller antallet af rækker, er det den optimale løsning, hvis ikke, så gå til trin 6.

6. Vælg det mindste element blandt alle de afdækkede elementer. Nu subtraheres dette element fra alle de afdækkede elementer og tilføjes til elementet, som ligger ved skæringspunktet mellem to linjer. Dette er matricen for friske opgaver.

7. Gentag proceduren fra trin (3), indtil antallet af opgaver bliver lig med antallet af rækker eller antal kolonner.