3 Vigtige operationelle forskningsaktiviteter
Denne artikel sætter lys på de tre vigtige værktøjer i operationsforskning. Værktøjerne er: 1. Lineær programmering 2. Transportproblemer 3. Opgaveproblem.
Operation Research: Tool # 1. Lineær programmering:
Lineær programmering er en matematisk teknik, der har anvendelse på næsten alle klasser af beslutningsproblemer. Denne teknik anvendes til at vælge som det bedste alternativ fra et sæt mulige alternativer.
I LPP kan objektiv funktion i såvel som begrænsninger udtrykkes som lineær matematisk funktion, som kan bruges til at løse de praktiske planlægningsproblemer. Det er en metode, der bruges til at studere systemers adfærd.
LP beskæftiger sig primært med at beskrive sammenhængen mellem komponenterne i et system. Denne teknik er designet til at hjælpe ledere i planlægning, beslutningstagning og tildeling af ressourcerne. Ledelsen har altid en tendens til at udnytte en organisationsressource mest effektivt. Ressourcer omfatter maskineri råvarer, arbejdskraft, lager, tid og penge.
Disse ressourcer kan anvendes til at producere produkter af forskellige typer kan være maskiner, dele / komponenter, møbler og fødevarer mv. Tilsvarende kan ressourcer bruges til at yde service som skema for forsendelse, annonceringspolitikker og investeringsbeslutninger.
Alle organisationer skal træffe beslutning om tildeling af deres begrænsede ressourcer. Derfor er ledelsen forpligtet til løbende at tildele knappe ressourcer til at nå organisationens mål / mål / mål.
Den adjektive lineære er blevet brugt til at beskrive et forhold mellem to eller flere variabler. Programmering vedrører brugen af visse matematiske ligninger, der bruges til at opnå den bedst mulige løsning på et problem, der involverer begrænsede / knappe ressourcer.
Således anvendes lineær programmering til optimeringsproblemer, der opfylder følgende betingelse:
(i) Den objektive funktion, der skal optimeres, skal være veldefineret og udtrykt som en lineær funktion af variabler.
(ii) Begrænsningen om nogen vedrørende opnåelsen af disse mål udtrykkes også som lineære kvaliteter / uligheder af variabel.
(iii) Der findes også et alternativt handlingsforløb.
(iv) Beslutningsvariablerne er indbyrdes forbundne og ikke-negative.
(v) Ressource er begrænset.
Anvendelse af lineær programmering til industrielle problemer:
(i) At udvikle planlægning for fødevareforarbejdningsindustrien og for olieraffinaderier mv.
ii) I metalindustrien anvendes den til butiksladning og til at bestemme valget mellem køb og produktion af forskellige dele.
(iii) Det bruges til at evaluere forskellige jernmalm i jern- og stålindustrien.
(iv) Det bruges til at reducere mængden af trim tab i papirfabrikker.
(v) Det bruges til at finde den optimale routing af meddelelser i kommunikationsnetværk.
Lineær programmeringsdefinition:
Lineær programmering er et matematisk værktøj / teknik til bestemmelse af de bedste anvendelser af en organisations ressourcer. Lineær programmering er designet til at hjælpe ledere med hensyn til planlægning og beslutningstagning. Som et redskab til beslutningstagning har det vist sin værdi på forskellige områder som produktion; marketingfinansiering, forskning og personaleopgaver.
Bestemmelse af optimal produktmiks, transportplaner porteføljevalg maskine opgave; plante placering og tildeling af arbejdskraft mv er de få typer af problemer, der kan løses ved hjælp af lineær programmering.
"Analysen af problemer, hvor en lineær funktion af en række variabler skal maksimeres (eller minimeres), når disse variabler er underlagt et antal begrænsninger i form af lineære i ligeværdier." Samuelson og Slow
Ifølge Loomba er "Lineær programmering kun et aspekt af, hvad der er blevet kaldt en systemtilgang til ledelse, hvor i alle programmer er designet og evalueret med hensyn til deres ultimative indvirkning på realiseringen af forretningsmålene".
Lineære programmeringsproblemer-grafisk metode:
Trinene i den grafiske metode kan opsummeres som følger:
1. Formulér det lineære programmeringsproblem.
2. Tegn de givne begrænsningslinjer i betragtning af dem som ligninger.
3. Fra den ovenstående graf identificere den mulige opløsningsregion.
4. Find comer punkterne i den gennemførlige løsning region.
5. Beregn værdien af objektivfunktionen på comer punkterne.
6. Vælg nu det punkt, hvor objektivfunktionen har optimal værdi.
Lineære programmeringsproblemer-matematisk løsning:
Selvom den grafiske metode til løsning af LPP er et værdifuldt hjælpemiddel til at forstå sin grundlæggende struktur. Metoden har begrænset anvendelighed i industrielle problemer, da antallet af variabler der forekommer der er væsentligt stor. Så en anden matematisk løsning kaldet som simplex-metode er egnet til at løse LPP med et stort antal variabler.
Det er en iterativ procedure, som enten løser LPP i et begrænset antal trin eller giver en indikation på, at der er en ubundet løsning på L. PR Simplex-metoden er en algebraisk procedure til løsning af lineære programmeringsproblemer eller består af en række gentagne trin til opnå en optimal løsning.
Det er en mest almindeligt anvendte programmeringsalgoritme. Teoretisk kan denne procedure løse ethvert problem, der består af et hvilket som helst antal variabler og begrænsninger. Hvis problemet består af mere end tre variabler og tre begrænsninger, kræves brug af computer. Figur 31.9 viser den skematiske repræsentation af simplex-algoritmen.
Forskellige trin i Simplex Procedure:
Fremgangsmåden i denne procedure er angivet nedenfor:
1. Formuler problemet ved at bestemme den objektive funktion og begrænsninger.
2. Konverter ulighederne til ligeværdier for at få standardformularen ved at indføre slap overskud og kunstige variabler i objektivfunktionen.
3. Forbered det oprindelige simplex-bord.
4. Beregn z j (netto tab pr. Enhed) og c j - z j (netto bidrag) værdi for denne løsning.
5. Bestem indtastningsvariablen (nøglesøjle) ved at vælge kolonnen med de fleste negative
(z j - c j ).
6. Bestem afvigende variabel (nøgle række) ved at beregne forholdskolonnen fra regel 5 og vælge den mindste ikke-negative værdi.
7. Beregn den erstatte række af den forbedrede simplex tabel ved regel 6.
8. Beregn de resterende rækker af den nye tabel ved regel 7.
9. Beregn c j og z j- værdien for denne løsning.
10. Hvis der ikke er negativ (c j - z j ) værdi, returneres til trin 5.
11. Hvis der ikke er nogen ikke-negative (c j - z j ) værdier, er den optimale løsning blevet opnået.
Eksempel 1:
En landmand har 1000 hektar jord, hvor han kan grave majs, hvede eller sojabønne. Hver hektar majs koster Rs. 100 til forberedelse, kræver 7 mand arbejdsdage og giver et overskud på Rs. 30 En acre hvedekostnader Rs. 120 for at forberede, kræver 10 mand arbejdsdage og giver en fortjeneste på Rs. 40.
En acre sojabønne koster Rs70 at forberede kræver 8 mand arbejdsdage og giver et overskud på Rs. 20 Hvis bonden har Rs. 100.000 til forberedelse og regning på 8000 manddage arbejde. Hvor mange acres skal tildeles hver afgrøde for at maksimere overskuddet? (Gujarat MBA, 1989)
Opløsning:
Lad x acre jord tildeles til majs
y acre jord tildeles til hvede
z acre jord tildeles til sojabønner
Da hver hektar jord til majs giver et overskud på Rs. 30, for hvede udbytter Rs. 40 og for sojabønne Rs. 20. Den matematiske formulering af LLP er
Max 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
Lad os konvertere ulighederne til ligninger ved at indføre slakkevariabler S 1, S 2 og S 3 . Den objektive funktion og begrænsningen kan skrives som
I basisvariabel søjle er vektorerne for variabel S1, (1, 0, 0), S2, (1, 0, 1) og S3 (0, 0, 1) den initiale gennemførlige løsning givet af variablerne S 1, S 2 og S 3 begge samlede overskud = 0
Nu Z j og C j - Z j beregnes ved regel 1, 2 og 3. Nøglesøjlen er bestemt med startmærket kolonne, og Simplex Tabel II fremstilles som følger.
Tabel II giver ikke optimal løsning, vi fortsætter videre med at forberede simpel tabel III og forbedre opløsningen som følger:
Minimeringsproblem ved Big M. Metode:
I industrien kan der være beliggende, hvor målet kan være at minimere produktionsomkostningerne eller fremstillingsvarigheden, dvs. at objektivfunktionen skal minimeres. I sådanne tilfælde kan vi fortsætte på samme måde som et maksimeringsproblem ved simpelthen at multiplicere med begge sider af objektiv funktion med-1 I sådanne situationer vil minimering af Z være maksimeringen af (-Z).
I sådanne tilfælde, da overskudsvariablerne tager en negativ værdi, der overtræder begrænsningen af ikke-negativitet, for at overvinde denne vanskelighed introducerer vi nye variable stilarter som kunstige variabler.
Nu tildeler vi 3000 koefficient til overskudsvariabler og + M til kunstige variabler. For at skabe kilde om, at kunstige variabler ikke er de grundlæggende variabler i den optimale løsning, tildeler vi dem meget høje omkostninger, derfor er M defineret til at være et meget stort antal, dvs Big M eller straf.
Denne metode illustreres ved hjælp af følgende:
Eksempel 2:
Operation Research: Tool # 2. Transportproblemer:
Transportproblemerne er en af de typer af LPP, hvor målet er at transportere varer / produkter i forskellige mængder af en enkelt homogen vare / vare til forskellige destinationer for at minimere de samlede transportomkostninger i hverdagen de forskellige fremstillingsorganisationer eller andre virksomheder skyldige til forskellige overvejelser opbevare deres slutprodukter eller genstande på forskellige steder betegnet som oprindelse eller værker, hus, når forsyningen skal foretages til brugerne, når varerne transporteres fra oprindelse til en eller flere destinationer, er det overordnede formål med denne proces at afgøre en distributionspolitik således at den samlede transportomkostninger er mindst eller den tid, der forbruges ved omladning, er minimum.
Efter at nativt færdige produkter fra fabrikken skal transporteres til lager på den mest økonomiske måde i transportproblemer kan forskellige funktioner ved lineær programmering overholdes her er tilgængeligheden såvel som kravene fra forskellige centre begrænset og udgør de begrænsede ressourcer transportproblemer de særlige tilfælde af simplex-metoden.
Anvendelse i ventiler transport af produkter fra flere kilder til forskellige destinationspunkter som:
(i) Transportenheder revet destination. Målet er at minimere transportomkostningerne.
(ii) Maksimere fortjenesten ved transport af enhederne til destinationen.
De vigtigste trin er :
Trin 1:
Formuler problemet og oprettet i form af transportmatrix.
Trin 2:
Få den grundlæggende gennemførlige løsning.
Trin 3:
Test for optimalt af opløsningen.
Trin 4:
Opdater løsningen gennem succesforbedringer, indtil det ikke er muligt at reducere transportomkostningerne yderligere.
Almindeligt anvendte metoder er:
1. Nordvest hjørne metode.
2. Least cost metode.
3. Vogel's Approximation metode.
Strid involveret i North West Corner Metode:
Trin 1:
Konstruer en tom maksimal matrix, der er fuldført med rækker og kolonner.
Trin 2:
Angiv række totaler og kolonne totaler i slutningen.
Trin 3:
Begynd med (11) celle i den nordvestlige del af matrixen allokere maksimal mulig mængde / antal, idet man sørger for, at tildelingen hverken kan overstige den mængde, der kræves af de respektive værtshuse eller mere end den disponible mængde på forsyningscentrene.
Trin 4:
Når du har foretaget justering af udbuds- og efterspørgselsnumre i respektive rækker og kolonner, skal du flytte ned til første celle og række gentage trin 3.
Trin 5:
Når efterspørgslen efter første kolonne er opfyldt, skal du gøre til næste celle i den anden kolonne og første række og gå til trin 3.
Trin 6:
Hvis for en celleforsyning er lig med at kræve dem, kan den næste tildeling være mode i celler i de næste rækker og kolonner.
Trin 7:
Fortsæt processen, indtil den samlede disponible mængde er fuldt fordelt til cellerne pr. Krav
Eksempel 3:
Løs følgende problem af NWCM for at beregne minimale transportomkostninger:
Trin i laveste pris indtastningsmetode:
Denne metode tager højde for den laveste pris og tager derfor mindre tid til at løse problemet. De forskellige trin er som følger:
Trin 1:
Vælg cellen med laveste transportomkostning blandt alle rækker og kolonner i matrixen. Allokér så meget som muligt for at eliminere enten den række eller kolonne, som enten udtømmer kilden eller fuld opfylder kravet. Hvis begge er tilfredsstillende dem eliminerer man en. Hvis den mindste priscelle ikke er unik, skal du vælge vilkårligt enhver celle med den laveste pris.
Trin 2:
Gentag proceduren for alle ukrydsede rækker og kolonner med næste mindste priscelle. Trin 3: Gentag proceduren, indtil alle kilder er opbrugt, eller efterspørgslen fra hele destinationen er fyldt op.
Eksempel 4:
Løs følgende problem med mindsteprismetode:
Vogel Approximation Metode:
Denne metode er en straf eller beklagelse metode og foretrækkes over de to andre metoder, den første basale gennemførlige løsning opnået enten optimal eller meget tæt på den optimale løsning, derfor er den tid, der er nødvendig for at beregne den optimale løsning, reduceret.
I denne metode er tildelingsgrundlaget enhedsomkostninger, dvs. den række eller kolonne, der angiver den højeste enhedsomkostningsstraf / forskellen mellem laveste og næste højeste pris vælges først med henblik på tildeling. På denne måde gøres de efterfølgende tildelinger i de andre celler også under hensyntagen til den højeste enhedsomkostningsstraf.
Fordelingen er lavet for at minimere straffen omkostninger forskellige involverede trin er som følger:
Trin 1:
Beregn straffen for hver række og kolonne det gøres ved blot at tage forskellen mellem den mindste og næste mindste transportomkostning i samme række og kolonne, dvs. forskellen angiver den straf, der skal betales, hvis tildelingen ikke sker til minimumsomkostningerne kriterium.
Trin 2:
Vælg en række eller kolonne med den største straf og allokér så meget som muligt til den mindste priscelle. I tilfælde af binding vælges først en celle med maksimal tildeling
Trin 3:
Kryds ud enten rækken eller kolonnen efter opfyldelse af efterspørgslen eller udmattende forsyningen, den resterende række eller kolonne er tildelt en nulforsyning eller efterspørgsel. Enhver række eller kolonne med nulstilførsel eller efterspørgsel med ikke brugt til yderligere beregninger.
Trin 4:
Gentag trin 1 og 3, indtil alle kilder er opbrugt eller alt krav er opfyldt.
Eksempel 5:
En fremstilling ønsker at sende 8 belastninger af hans produkt fra produktionscentrene X, Y og Z til distributionscentrene A, B og C, milningen fra oprindelse 0 til destination D er følgende matrix.
Eksempel 6:
Find den optimale løsning af følgende transport problem ved at få den første løsning med vogets approximation metode:
Opløsning:
Lad os anvende vogels tilnærmelsesmetode. Problemer afbalanceret som supply = Efterspørgsel = 50 enheder. Lad os anvende vogels metode som angivet i nedenstående tabel.
Transportomkostninger = 2 x 15 + 9 x 15 + 20 x 10 + 4 x 5 + 18 x 5 x 475 enheder.
Kontroller optimalt:
Optimitetstest kan udføres, hvis to betingelser er opfyldt dvs.
1. Der er m + n - 1 allokering, hvis m er antal rækker, n er antal kolonner. Her m + n - = 6. Men antallet af tildelinger er fem.
2. Disse m + n-1-tildelinger skal være i uafhængige positioner, dvs. det bør ikke være muligt at øge eller reducere en tildeling uden at ændre placeringen af tildelingerne eller krænke række eller kolonnebegrænsninger.
En simpel regel for tildelinger at være i uafhængige stillinger er, at det er umuligt at rejse fra enhver tildeling, tilbage til sig selv en række vandrette og vertikale trin danner en besat celle til en anden uden direkte omstilling af rute. Det kan ses, at i det nuværende eksempel er tildelingen i uafhængige positioner, da der ikke kan dannes lukket sløjfer ved de tildelte celler.
Derfor er første betingelse ikke opfyldt, og derfor skal vi for at tilfredsstille første betingelse fordele en lille mængde E på de ledige celler med laveste transportomkostninger. Det kan ses, at t kan allokeres i celle (2, 2) med omkostninger på 7 enheder, og alligevel vil tildelingerne forblive på uafhængig position som beskrevet nedenfor i tabel 2.
Nu er antallet af tildelinger m + n - 6 = 6, og de er i uafhængige stillinger. Skriv ned omkostningsmatrix på tildelte celler. (Tabel 3)
Indledende omkostningsmatrix for tildelte celler. Skriv også værdierne for u i og v j .
Det fremgår af tabel 5, at celleevaluering i celle (1, 4) er negativ dvs. -4, og derfor ved at allokere i celle (1, 4) reduceres transportomkostningerne yderligere.
Lad os skrive ned de oprindelige tildelinger og den foreslåede nye tildeling.
Det fremgår af tabel 6, at hvis vi allokerer i celle (1, 4), dannes en sløjfe som vist, og vi allokerer 10 enheder, således at fordeling ved celle (2, 4) forsvinder som vist nedenfor i tabel 7. Ny fordelingsbordet bliver
Transportomkostninger = 5X 2 + 10X 1 1 + 10X 7 + 15X 9 + 5X 4 + 18 + 5 = 435 enheder.
dvs. Transportomkostninger er faldet fra 475 enheder til 435 enheder.
Kontroller optimalt:
Lad os se, om denne løsning er optimal eller ej? For det skal to betingelser kontrolleres, dvs.
Antal tildeling = m + n-1 = 6 (tilfreds)
Allokering i uafhængig position (tilfreds, da lukket kredsløb for tildelte celler ikke er dannet) Skriv omkostning ved de allokerede og værdier af u i og v j .
Operation Research: Tool # 3. Opgaveproblem:
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 problem ved simplex-metode 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.
Opgave Model:
Antag at der er n letter og n job. Det er klart, at der i dette tilfælde vil 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 om omkostningerne eller tiderne minimeres.
I tabellen er Co ij defineret som prisen, når jobbet er tildelt til medarbejderen. Det kan her bemærkes, 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, hvoraf (n - 1) -variablerne 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, at X ij er en variabel, som er defineret som
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 i det givne omkostningsbord, der begynder med den første række. Nu trækkes dette mindste element fra hvert element i den 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) tager kolonnerne af bordet. 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 enten 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. Træk i dette trin det mindste antal linjer (vandret og lodret), der er nødvendige for at dække alle nuller i matricen opnået i trin 3.
Følgende procedure vedtages:
(i) Marker (V) alle rækker, der ikke har nogen opgave.
(ii) Markér nu (V) 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 (1), 4 (2), 4 (3) gentages, indtil der ikke kan mærkes flere rækker eller kolonner,
(v) Træk nu lige linjer, som passerer gennem alle de umærkede rækker og markerede søjler. Det kan også bemærkes, at i en nxn matrix vil altid mindre end 'n' linjer dække alle nuller hvis der ikke findes 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.
