Oppgaveproblem i lineær programmering: Introduksjons- og oppdragsmodell
Oppgaveproblem er en spesiell type lineær programmeringsproblem som omhandler fordelingen av de ulike ressursene til de ulike aktivitetene på ett til ett grunnlag. Det gjør det på en slik måte at kostnaden eller tiden som er involvert i prosessen er minimum, og fortjeneste eller salg er maksimalt. Selv om det kan løses problemer ved hjelp av simplex-metoden eller transportmetoden, men oppgavemodellen gir en enklere tilnærming til disse problemene.
I en fabrikk kan en veileder ha seks arbeidere tilgjengelig og seks jobber til ild. Han må ta beslutning om hvilken jobb som skal gis til hvilken arbeidstaker. Problemet danner ett til ett grunnlag. Dette er et oppdragsproblem.
1. Oppdragsmodell:
Anta at det er n forenkler og n jobber det er klart at i dette tilfellet vil det bli n oppgaver. Hvert anlegg eller si arbeidstaker kan utføre hver jobb, en om gangen. Men det bør være viss prosedyre ved hvilken oppdrag skal gjøres slik at overskuddet maksimeres eller kostnaden eller tiden minimeres.
I tabellen er det definert som kostnaden når jobben er tilordnet til arbeideren. Det bemerkes kanskje at dette er et spesielt tilfelle av transportproblem når antall rader er lik antall kolonner.
Matematisk formulering:
Enhver grunnleggende gjennomførbar løsning av et oppdragsproblem består av (2n - 1) variabler hvorav (n - 1) variablene er null, n er antall jobber eller antall anlegg. På grunn av denne høye degenerasjonen, hvis vi løser problemet ved vanlig transportmetode, blir det et komplisert og tidskrevende arbeid. Dermed er en egen teknikk avledet for den. Før du går til den absolutte metoden, er det svært viktig å formulere problemet.
Anta at x jj er en variabel som er definert som
1 hvis den første jobben er tilordnet maskinen eller anlegget
0 hvis den første jobben ikke er tildelt maskinen eller anlegget.
Nå som problemet danner ett til ett grunnlag eller en jobb skal tilordnes til ett anlegg eller en maskin.
Den totale oppgavekostnaden vil bli gitt av
Ovenstående definisjon kan utvikles til matematisk modell som følger:
Bestem x ij > 0 (i, j = 1, 2, 3 ... n) for å
Underlagt begrensninger
og x ij er enten null eller en.
Metode for å løse problem (ungarsk teknikk):
Vurder objektiv funksjon av minimeringstype. Følgende trinn er involvert i å løse dette oppdragsproblemet,
1. Finn det minste kostnadselementet i hver rad av det angitte kostetabellen som begynner med den første raden. Nå trekkes dette minste elementet fra hver del av den raden. Så vil vi få minst ett null i hver rad i dette nye bordet.
2. Etter å ha konstruert bordet (som ved trinn 1), ta tabellens kolonner. Fra det første kolonnen finner du det minste kostnaden i hver kolonne. Trekk nå dette minste elementet fra hvert element i den kolonnen. Etter å ha utført trinn 1 og trinn 2, vil vi få minst ett null i hver kolonne i reduserte kostnadstabellen.
3. Nå blir oppdragene gjort for det reduserte bordet på følgende måte.
(i) Rader undersøkes suksessivt, til raden med nøyaktig enkelt (en) null er funnet. Oppdrag er gjort til dette nullpunktet ved å sette firkantet □ rundt det og i den tilsvarende kolonnen, krysses alle andre nuller (x) fordi disse ikke vil bli brukt til å gjøre noen annen oppgave i denne kolonnen. Trinn utføres for hver rad.
(ii) Trinn 3 (i) i nå utført på kolonnene som følger: - Kolonner undersøkes suksessivt til en kolonne med nøyaktig ett null er funnet. Nå legges tildeling til dette nullet ved å sette plassen rundt det og samtidig blir alle andre nuller i de tilsvarende radene krysset ut (x) trinn utføres for hver kolonne.
(iii) Trinn 3, (i) og 3 (ii) gjentas til alle nullene er merket eller krysset ut. Nå, hvis antall merkede nuller eller oppgavene er like som antall rader eller kolonner, har optimal løsning blitt oppnådd. Det vil være nøyaktig enkelt oppgave i hver eller kolonnene uten noen oppgave. I dette tilfellet går vi til trinn 4.
4. På dette stadiet tegner du det minste antall linjer (horisontal og vertikal) som er nødvendig for å dekke alle nuller i matrisen som er oppnådd i trinn 3, Følgende prosedyre er vedtatt:
(i) Merk av (
(ii) Nå kryss markering (
(iii) Merk av for alle rader som ikke allerede er merket og som har oppgave i de merkede kolonnene.
(iv) Alle trinnene, dvs. (4 (i), 4 (ii), 4 (iii), gjentas til ingen flere rader eller kolonner kan merkes.
(v) Tegn nå rette linjer som går gjennom alle un merkede rader og merkede kolonner. Det kan også bli lagt merke til at i en nxn-matrise, vil alltid mindre enn 'n' linjer dekke alle nuller hvis det ikke er noen løsning blant dem.
5. I trinn 4, hvis antall linjer tegnet er lik n eller antall rader, er det den optimale løsningen hvis ikke, og deretter gå til trinn 6.
6. Velg det minste elementet blant alle de avdekkede elementene. Nå trekkes dette elementet fra alle de avdekkede elementene og legges til elementet som ligger i skjæringspunktet mellom to linjer. Dette er matrisen for friske oppdrag.
7. Gjenta prosedyren fra trinn (3) til antall oppgaver blir lik antall rader eller antall kolonner.
