3 Viktige operasjonsverktøy
Denne artikkelen kaster lys over de tre viktige verktøyene for operasjonsforskning. Verktøyene er: 1. Lineær programmering 2. Transportproblemer 3. Oppgaveproblem.
Operasjonsforskning: Verktøy # 1. Lineær programmering:
Lineær programmering er en matematisk teknikk som har applikasjon til nesten alle klasser av beslutningsproblemer. Denne teknikken brukes for å velge som det beste alternativet fra et sett av gjennomførbart alternativ.
I LPP kan objektiv funksjon i samt begrensninger uttrykkes som lineær matematisk funksjon, som kan brukes til å løse de praktiske planleggingsproblemer. Det er en metode som brukes til å studere systemadferdene.
LP er hovedsakelig opptatt av å beskrive sammenhengen mellom komponentene i et system. Denne teknikken er utformet for å hjelpe ledere i planlegging, beslutningstaking og tildeling av ressursene. Ledelsen har alltid en tendens til å utnytte en organisasjonsressurs mest mulig effektivt. Ressurser inkluderer maskineri, råvarer, arbeidskraft, lager, tid og penger.
Disse ressursene kan benyttes til å produsere produkter av ulike typer kan være maskiner, deler / komponenter, møbler og matvarer mv. Tilsvarende kan ressurser brukes til å yte tjenester som tidsplan for frakt, reklamepolitikk og investeringsbeslutninger.
Alle organisasjoner må ta beslutning om allokering av deres begrensede ressurser. Så ledere må kontinuerlig tildele knappe ressurser for å oppnå organisasjonsmålene / målene / målene.
Den adjektive lineære har blitt brukt til å beskrive et forhold mellom to eller flere variabler. Programmering er opptatt av bruk av visse matematiske ligninger som brukes til å oppnå best mulig løsning på et problem med begrensede / knappe ressurser.
Dermed er lineær programmering brukt for optimaliseringsproblemer som tilfredsstiller følgende tilstand:
(i) Målfunksjonen som skal optimaliseres, skal være veldefinert og uttrykt som en lineær funksjon av variabler.
(ii) Begrensningen hvis noen angående oppnåelse av disse målene uttrykkes også som lineære kvaliteter / ulikheter av variabel.
(iii) Noen alternative handlinger er også tilgjengelige.
(iv) Beslutningsvariablene er sammenhengende og ikke-negative.
(v) Ressurs er begrenset.
Anvendelse av lineær programmering til industrielle problemer:
(i) Å utvikle planlegging for næringsmiddelindustrien og for petroleumsraffinaderier mv.
ii) I metallindustrien brukes den til butikkbelastning og for å bestemme valget mellom kjøp og produksjon av ulike deler.
(iii) Det brukes til å vurdere ulike jernmalm i jern- og stålindustrien.
(iv) Det brukes til å redusere antall trimtap i papirfabrikker.
(v) Det brukes til å finne den optimale rutingen av meldinger i kommunikasjonsnettverket.
Lineær programmeringsdefinisjon:
Lineær programmering er et matematisk verktøy / teknikk for å bestemme den beste bruken av organisasjonens ressurser. Linjær programmering er laget for å hjelpe ledere angående planlegging og beslutningstaking. Som et verktøy for beslutningstaking har det vist sin verdi på ulike områder som produksjon; markedsføring finans, forskning og personal oppgaver.
Bestemmelse av optimal produktmiks, transportplaner porteføljevalgsmaskinoppgave; anleggssted og tildeling av arbeidskraft mm er de få typer problemer som kan løses ved hjelp av lineær programmering.
"Analysen av problemer der en lineær funksjon av en rekke variabler skal maksimeres (eller minimeres) når disse variablene er gjenstand for antall restriksjoner i form av lineære i likeverd.", Samuelson og Slow
Ifølge Loomba, "Linjær programmering er bare ett aspekt av det som har blitt kalt en systemtilnærming til ledelse der i alle programmer er utformet og evaluert i forhold til deres ultimate innvirkning på realiseringen av forretningsmålene".
Lineære programmeringsproblemer-grafisk metode:
Trinnene i grafisk metode kan oppsummeres som følger:
1. Formuler det lineære programmeringsproblemet.
2. Tegn de angitte begrensningslinjene i betraktning av dem som ligninger.
3. Fra den ovennevnte grafen identifiserer den mulige løsningsregionen.
4. Finn komerpoengene i den mulige løsningsregionen.
5. Beregn verdien av objektivfunksjonen på komerpoengene.
6. Velg nå punktet der objektivfunksjonen har optimal verdi.
Lineære programmeringsproblemer-matematisk løsning:
Selv om den grafiske metoden for å løse LPP er et verdifullt hjelpemiddel for å forstå sin grunnleggende struktur. Metoden er av begrenset nytte i industrielle problemer siden antall variabler som forekommer der er vesentlig stor. Så en annen matematisk løsning kalt som simplex-metode er egnet å løse LPP med et stort antall variabler.
Det er en iterativ prosedyre som enten løser LPP i et begrenset antall trinn eller gir en indikasjon på at det er en ubundet løsning på L. PR Simplex-metoden er en algebraisk prosedyre for å løse lineære programmeringsproblemer eller består av en rekke gjentatte trinn for å oppnå en optimal løsning.
Det er en mest brukte og mest brukte programmeringsalgoritme. Teoretisk kan denne prosedyren løse et problem som består av et hvilket som helst antall variabler og begrensninger. Hvis problemet består av mer enn tre variabler og tre begrensninger, er det nødvendig med bruk av datamaskinen. Fig. 31.9 viser skjematisk fremstilling av simpleksalgoritmen.
Ulike trinn i Simplex Prosedyre:
Trinnene i denne prosedyren er oppført nedenfor:
1. Formuler problemet ved å bestemme objektivfunksjonen og begrensningene.
2. Konverter ulikhetene til likheter for å få standardformularen ved å innføre slakkoverskudd og kunstige variabler i objektivfunksjonen.
3. Klargjør den grunnleggende simplex-tabellen.
4. Beregn zj (netto tap per enhet) og c j - z j (netto bidrag) verdi for denne løsningen.
5. Bestem inntastingsvariabelen (nøkkolonne) ved å velge kolonnen med mest negative
(z j - c j ).
6. Bestem avvikende variabel (nøkkelrad) ved å beregne forholdskolonnen fra regel 5 og velge den minste ikke negative verdien.
7. Beregn den erstatte raden i det forbedrede simplex-tabellen ved hjelp av regel 6.
8. Beregn de resterende radene i det nye tabellen ved regel 7.
9. Beregn c j og z j- verdien for denne løsningen.
10. Hvis det ikke er negativ (c j - z j ) returnerer verdien til trinn 5.
11. Hvis det ikke er noen negative (c j - z j ) verdier, har den optimale løsningen blitt oppnådd.
Eksempel 1:
En bonde har 1000 hektar land hvor han kan grave mais, hvete eller soyabønne, Hver hektar med mais koster Rs. 100 for forberedelse, krever 7 manners dag med arbeid og gir et overskudd på Rs. 30 En hektar hvetekostnader Rs. 120 for å forberede, krever 10 manners dager med arbeid og gir et overskudd på Rs. 40.
En acre av soyabean koster Rs70 å forberede krever 8 manners dager med arbeid og gir et overskudd på Rs. 20 Hvis bonden har Rs. 100.000 for forberedelse og telling på 8000 mannsdager av arbeid. Hvor mange hektar skal allokeres til hver avling for å maksimere fortjenesten? (Gujarat MBA, 1989)
Løsning:
La x hektar jord tildeles for mais
Å ha areal fordelt på hvete
z acre av land bli tildelt for soyabean
Siden hver hektar land for mais gir et overskudd på Rs. 30, for hvete gir Rs. 40 og for soyabean Rs. 20. Den matematiske formuleringen av LLP er
Maks Z = 30x + 40y + 20z + 0S 1, + OS 2, + 0S 3
Underlagt
100 x + 120y + 70z ≤ 100000
7x + 10y + 8z ≤ 8000
x + y + z ≤ 1000
x, y, z ≥ 0
La oss konvertere ulikhetene til ligninger ved å introdusere slakkvariabler S 1, S 2 og S 3 . Målfunksjonen og begrensningen kan skrives som
I grunnleggende variabel kolonne er vektorene for variabel S1, (1, 0, 0), S2, (1, 0, 1) og S3 (0, 0, 1) den initiale gjennomførbare løsningen gitt av variablene S 1, S 2 og S 3 begge totale fortjeneste = 0
Nå Z j og C j - Z j beregnes etter regel 1, 2 og 3. Nøkkelkolonnen er bestemt med start merket kolonne og Simplex Tabell II er utarbeidet som følger.
Tabell II gir ikke optimal løsning vi fortsetter videre for å forberede enkel tabell III og forbedre løsningen som følger:
Minimeringsproblem av Big M. Metode:
I industrien kan det ligge hvor målet kan være å minimere produksjonskostnadene eller varigheten av produksjonen, dvs. at objektivfunksjonen skal minimeres i slike tilfeller kan vi fortsette på samme måte som et maksimeringsproblem ved å bare multiplisere ved begge sider av objektiv funksjon av-1 I slike tilfeller vil minimering av Z være maksimeringen av (-Z).
I slike tilfeller, da overskuddsvariablene tar en negativ verdi som bryter mot ikke-negativitetsbegrensningen, for å overvinne denne vanskeligheten, introduserer vi nye variabelstilte som kunstige variabler.
Nå tilordner vi 3000 koeffisient til overskudsvariabler og + M til kunstige variabler. For å lage kilde om at kunstige variabler ikke er de grunnleggende variablene i den optimale løsningen, tilordner vi dem svært høye kostnader derfor er M definert til å være et veldig stort tall, dvs. Big M eller straff.
Denne metoden er illustrert ved hjelp av følgende:
Eksempel 2:
Operasjonsforskning: Verktøy # 2. Transportproblemer:
Transportproblemene er en av de typer LPP som har til formål å transportere varer / produkter i forskjellige mengder av en enkelt homogen vare / vare til forskjellige destinasjoner for å minimere total transportkostnad i hverdagen de ulike produksjonsorganisasjoner eller andre virksomheter som skyldes til ulike hensyn lagre sine sluttprodukter eller gjenstander på forskjellige steder betegnet som opprinnelse eller varehus, hus når forsyning skal gjøres til brukere, da varene blir transportert fra opprinnelse til en eller flere destinasjoner, er det generelle formålet med denne prosessen å avgjøre en distribusjonspolitikk slik at total transportkostnad er minimum eller tiden som forbrukes ved omladning er minimum.
Etter at nativt ferdige produkter fra anlegget skal transporteres til lager på mest økonomisk måte i transportproblemer, kan ulike funksjoner ved lineær programmering observeres her tilgjengeligheten og kravene til ulike sentre er begrensede og utgjør begrensede ressurser transportproblemer de spesielle tilfeller av simplex-metoden.
Bruk i ventiler transport av produkter fra flere kilder til forskjellige destinasjonspoeng som:
(i) Transport av enheter revet destinasjon. Målet er å minimere transportkostnadene.
(ii) Maksimere fortjeneste ved transport av enhetene til destinasjon.
De viktigste trinnene som er involvert er :
Trinn 1:
Formuler problemet og sett opp i form av transportmatrise.
Steg 2:
Hent den grunnleggende mulige løsningen.
Trinn 3:
Test for optimal løsning.
Trinn 4:
Oppdater løsningen gjennom suksessforbedringer til det ikke er mulig å redusere transportkostnadene ytterligere.
Vanligvis brukte metoder er:
1. Nordvest hjørne metode.
2. Least cost metode.
3. Vogels Approximation metode.
Trinn involvert i nordvest hjørne Metode:
Trinn 1:
Konstruer en tom maksimal matrise fullført med rader og kolonner.
Steg 2:
Angi rad-totalene og kolonnens totalene på slutten.
Trinn 3:
Begynn med (11) celle i den nordvestlige delen av matrisen tilordne maksimal mulig mengde / antall og pass på at tildelingen hverken kan være mer enn mengden som kreves av de respektive varehusene, eller mer enn den tilgjengelige mengden på forsyningsstedene.
Trinn 4:
Etter å ha gjort justering av tilbuds- og etterspørselsnumre i respektive rader og kolonner tildelinger, flytt ned til første celle og rad gjenta trinn 3.
Trinn 5:
Etter at etterspørselen fra første kolonne er fornøyd, gjør du til neste celle i den andre kolonnen og første rad og gå til trinn 3.
Trinn 6:
Hvis for en celleforsyning tilsvarer kreve dem, kan neste tildeling være modus i celler i de neste radene og kolonnene.
Trinn 7:
Fortsett prosessen til den totale tilgjengelige mengden er fullt tildelt til cellene etter behov
Eksempel 3:
Løs følgende problem av NWCM for å beregne minimum transportkostnad:
Trinn i laveste inntektsmetode:
Denne metoden tar hensyn til laveste pris, og det tar derfor mindre tid å løse problemet. De ulike trinnene er som følger:
Trinn 1:
Velg cellen med laveste transportkostnad blant alle rader og kolonner i matrisen. Allokere så mye som mulig for å eliminere enten den raden eller kolonnen som enten eksoserer kilden eller fyller kravet fullt ut. Hvis begge er tilfredsstillende, eliminerer de en. Hvis den minste kostnaden celle ikke er unik, velger du vilkårlig hvilken som helst celle med laveste pris.
Steg 2:
Gjenta prosedyren for alle uncrossed ut rader og kolonner med neste minste kostnad celle. Trinn 3: Gjenta prosedyren til alle kilder er oppbrukt eller etterspørsel av hele destinasjonen er fullstendig fylt.
Eksempel 4:
Løs følgende problem med minst kostnaden metode:
Vogel Approximation Metode:
Denne metoden er en straff eller angrer metode og er foretrukket i løpet av de andre to metodene, den første grunnleggende gjennomførbare løsningen oppnådd enten optimal eller svært nær den optimale løsningen, derfor er tiden som trengs for å beregne den optimale løsningen redusert.
I denne metoden er grunnlaget for allokering enhetsomkostningsstraff, dvs. den raden eller kolonnen som indikerer den høyeste enhetskostnadstraffen / differansen mellom laveste og neste høyeste kostnad velges først med det formål å tildele. På denne måten blir de etterfølgende tildelingene i de andre cellene også gjort med sikte på å oppnå den høyeste enhetskostnadstraffen.
Fordelingen er gjort for å minimere straffen kostnadene ulike trinn involvert er som følger:
Trinn 1:
Beregn straffen for hver rad og kolonne det gjøres ved å bare ta forskjellen mellom den minste og neste minste transportkostnaden i samme rad og kolonne, dvs. forskjellen indikerer straffen som skal betales dersom tildelingen ikke gjøres til minimumskostnaden kriterium.
Steg 2:
Velg en rad eller kolonne med den største straffen og allokere så mye som mulig til laveste priscellen. I tilfelle bindingen velges en celle med maksimal allokering først
Trinn 3:
Kryss ut enten raden eller kolonnen etter å ha oppfylt etterspørselen eller utmatt forsyningen, den gjenværende rad eller kolonne er tildelt en nullforsyning eller etterspørsel. En hvilken som helst rad eller kolonne med nullforsyning eller etterspørsel med ikke brukt til videre beregninger.
Trinn 4:
Gjenta trinn 1 og 3 til alle kildene er oppbrukt eller alt kravet er oppfylt.
Eksempel 5:
En produksjon vil sende 8 laster av sitt produkt fra produksjonssentrene X, Y og Z til distribusjonssenterene A, B og C, milningen fra opprinnelse 0 til destinasjon D er følgende matrise.
Eksempel 6:
Finn den optimale løsningen av følgende transportproblem ved å få første løsning med vogets approximation metode:
Løsning:
La oss bruke vogels tilnærmelsesmetode. Problemer balansert som forsyning = Etterspørsel = 50 enheter. La oss anvende vogels metode som vist i tabellen nedenfor.
Transportkostnad = 2 x 15 + 9 x 15 + 20 x 10 + 4 x 5 + 18 x 5 x 475 enheter.
Sjekk etter optimalt:
Optimalitetstest kan utføres dersom to forhold er tilfredsstillende, dvs.
1. Det er m + n - 1 allokering, hvis m er antall rader, n er antall kolonner. Her m + n - = 6. Men antall tildelinger er fem.
2. Disse m + n-1-tildelingene bør være i uavhengige stillinger, dvs. det bør ikke være mulig å øke eller redusere allokering uten å endre plasseringen av tildelingene eller bryte rad- eller kolonnebegrensningene.
En enkel regel for tildelinger å være i uavhengige stillinger er at det er umulig å reise fra enhver tildeling, tilbake til seg selv en rekke horisontale og vertikale trinn danner en okkupert celle til en annen, uten direkte reversering av ruten. Det kan sees at i nåværende eksempel er allokering i uavhengige posisjoner, da ingen lukket sløyfe kan dannes ved de tildelte celler.
Derfor er første tilstand ikke fornøyd, og derfor for å tilfredsstille første betingelse, må vi tildele en liten mengde E til de ledige cellene som har laveste transportkostnad. Det kan ses at t kan allokeres på celle (2, 2) med en kostnad på 7 enheter, og fortsatt vil tildelingene forbli i uavhengig posisjon som beskrevet nedenfor i tabell 2.
Nå er antall tildelinger m + n - 6 = 6 og de er i uavhengige stillinger. Skriv ned kostnadsmatrisen ved tildelte celler. (Tabell 3)
Initial kostnadsmatrise for tildelte celler. Skriv også verdiene til deg i og v j .
Det fremgår av tabell 5 at celleevaluering ved celle (1, 4) er negativ, dvs. -4, og ved å allokere ved celle (1, 4) blir transportkostnaden ytterligere redusert.
La oss skrive ned de opprinnelige tildelingene og den foreslåtte nye tildelingen.
Det kan ses fra tabell 6 at hvis vi allokerer ved celle (1, 4), dannes en sløyfe som vist og vi allokerer 10 enheter slik at allokering i celle (2, 4) forsvinner som vist under i Tabell 7. Ny allokeringstabellen blir
Transportkostnad = 5X 2 + 10X 1 1 + 10X 7 + 15X 9 + 5X 4 + 18 + 5 = 435 enheter.
dvs. Transportkostnadene har kommet ned fra 475 enheter til 435 enheter.
Sjekk etter optimalt:
La oss se om denne løsningen er optimal eller ikke? For det igjen må to forhold kontrolleres, dvs.
Antall tildeling = m + n-1 = 6 (fornøyd)
Allokering i uavhengig posisjon (tilfredsstilt siden lukket sløyfe for tildelte celler er ikke dannet) Skriv kostnad ved allokert allas og verdier av u i og v j .
Operasjonsforskning: Verktøy nr. 3. Oppgaveproblem:
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 problemet kan løses ved hjelp av simplex-metoden eller ved transportmetode, 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.
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 en viss prosedyre ved hvilken oppdrag skal gjøres slik at fortjenesten maksimeres eller kostnadene eller tidene blir minimert.
I tabellen er Co ij definert som kostnaden når jobben er tildelt til arbeidstaker. Det kan bemerkes 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 ij er en variabel som er definert som
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 hvert element i 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) tar kolonnene av bordet. 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 oppgavene laget 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 nuller 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 oppnådd i trinn 3.
Følgende fremgangsmåte er vedtatt:
(i) Merk av (V) alle rader som ikke har noen oppgave.
(ii) Merk av (V) alle disse kolonnene som har null i de merket merkene.
(iii) Merk av alle rader som ikke allerede er merket og som har oppgave i de merkede kolonnene.
(iv) Alle trinnene, dvs. 4 (1), 4 (2), 4 (3), gjentas til ingen flere rader eller kolonner kan merkes,
(v) Tegn nå rette linjer som går gjennom alle umarkerte 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 finnes 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.
