3 Viktiga verktyg för operationsforskning

Denna artikel lyfter fram de tre viktiga verktygen för operationsforskning. Verktygen är: 1. Linjär programmering 2. Transportproblem 3. Uppdragsproblem.

Driftforskning: Verktyg # 1. Linjär programmering:

Linjär programmering är en matematisk teknik som har tillämpning på nästan alla klasser av beslutsproblem. Denna teknik tillämpas för att välja som det bästa alternativet från en uppsättning möjliga alternativ.

I LPP kan objektiv funktion i såväl som begränsningar uttryckas som linjär matematisk funktion, som kan användas för att lösa de praktiska schemaläggningsproblemen. Det är en metod som används för att studera systemets beteende.

LP är huvudsakligen intresserad av att beskriva sambandet mellan komponenterna i ett system. Denna teknik är utformad för att hjälpa cheferna i planering, beslutsfattande och fördela resurserna. Ledningen har alltid en tendens att utnyttja en organisationsresurs mest effektivt. Resurser inkluderar maskinråvaror, arbetskraft, lager, tid och pengar.

Dessa resurser kan utnyttjas för att producera produkter av olika slag kan vara maskiner, delar / komponenter, möbler och livsmedelsprodukter etc. På liknande sätt kan resurser användas för att tillhandahålla tjänster som schema för frakt, reklampolitik och investeringsbeslut.

Alla organisationer måste fatta beslut om fördelningen av sina begränsade resurser. Således måste ledningen kontinuerligt fördela knappa resurser för att uppnå organisationens mål / mål / mål.

Adjektivet linjärt har använts för att beskriva ett förhållande mellan två eller flera variabler. Programmering handlar om användning av vissa matematiska ekvationer som används för att uppnå bästa möjliga lösning på ett problem med begränsade / knappa resurser.

Således används linjär programmering för optimeringsproblem som uppfyller följande villkor:

(i) Den objektiva funktionen som ska optimeras bör vara väldefinierad och uttryckas som en linjär funktion av variabler.

(ii) Begränsningen om någon med avseende på uppnåendet av dessa mål uttrycks också som linjära kvaliteter / ojämlikheter av variabel.

(iii) En del alternativa åtgärder är också tillgängliga.

(iv) Beslutsvariablerna är inbördes relaterade och icke-negativa.

(v) Resurs är begränsade.

Tillämpning av linjär programmering till industriella problem:

(i) Att utveckla schemaläggning för livsmedelsindustrin och för oljeraffinaderier etc.

ii) I metallindustrin används den för butikslastning och för att bestämma valet mellan att köpa och producera olika delar.

(iii) Det används för att utvärdera olika järnmalm i järn- och stålindustrin.

(iv) Det används för att minska mängden trimförluster i pappersbruk.

(v) Det används för att hitta den optimala routningen av meddelanden i kommunikationsnätverket.

Linjär programmeringsdefinition:

Linjär programmering är ett matematiskt verktyg / teknik för att bestämma de bästa användningarna av en organisations resurser. Linjär programmering är utformad för att hjälpa cheferna när det gäller planering och beslutsfattande. Som ett redskap för beslutsfattande har det visat sitt värde på olika områden som produktion; marknadsföring finans, forskning och personal uppdrag.

Bestämning av optimal produktmix, transportplaner, portföljval anläggningsplats och arbetsfördelning etc. är de få typerna av problem som kan lösas med hjälp av linjär programmering.

"Analysen av problem där en linjär funktion av ett antal variabler ska maximeras (eller minimeras) när dessa variabler är föremål för antal restriktioner i form av linjära i jämställdhet.", Samuelson och Slow

Enligt Loomba är "linjär programmering bara en aspekt av vad som kallats ett systeminriktat förhållningssätt till förvaltningen där i alla program utformas och utvärderas i termer av deras ultimata påverkan vid uppnåendet av affärsmål".

Linjära programmeringsproblem-grafisk metod:

Stegen i den grafiska metoden kan sammanfattas enligt följande:

1. Formulera det linjära programmeringsproblemet.

2. Rita de givna begränsningslinjerna med tanke på dem som ekvationer.

3. Från den ovanstående grafen identifiera den möjliga lösningsregionen.

4. Hitta kommandopunkterna i den genomförbara lösningsregionen.

5. Beräkna värdet på objektivfunktionen på kommandopunkterna.

6. Välj nu den punkt där objektivfunktionen har optimalt värde.

Linjära programmeringsproblem-matematisk lösning:

Även om den grafiska metoden att lösa LPP är ett värdefullt hjälpmedel för att förstå dess grundläggande struktur. Metoden är av begränsad nytta i industriella problem eftersom antalet variabler som uppstår där är väsentligen stor. Så en annan matematisk lösning som kallas som simplex-metod är lämplig att lösa LPP med ett stort antal variabler.

Det är ett iterativt förfarande som antingen löser LPP i ett begränsat antal steg eller ger en indikation på att det finns en obegränsad lösning på L. PR Simplex-metoden är en algebraisk procedur för att lösa linjära programmeringsproblem eller består av en rad repetitiva steg till uppnå en optimal lösning.

Det är en mest allmänt använd programmeringsalgoritm. Teoretiskt kan denna procedur lösa alla problem som består av ett antal variabler och begränsningar. Om problemet består av mer än tre variabler och tre begränsningar krävs att datorn används. Fig. 31.9 visar den schematiska representationen av simplexalgoritmen.

Olika steg i Simplex-proceduren:

Stegen i denna procedur anges nedan:

1. Formulera problemet genom att bestämma objektets funktion och begränsningar.

2. Konvertera ojämlikheterna till jämställdhet för att få standardformuläret genom att införa slack överskott och konstgjorda variabler i objektivfunktionen.

3. Förbered det initiala simplex-bordet.

4. Beräkna zj (nettoförlust per enhet) och c j - z j (nettobidrag) för denna lösning.

5. Bestäm inmatningsvariabeln (nyckelkolumn) genom att markera kolumnen med de flesta negativa

( zj - cj ).

6. Bestäm avvikande variabel (nyckelrad) genom att beräkna förhållandekolonnen från regel 5 och välja det minsta icke-negativa värdet.

7. Beräkna ersättningsraden för det förbättrade enkeltabellen med regel 6.

8. Beräkna de övriga raderna i den nya tabellen med regel 7.

9. Beräkna cj och zj- värdet för denna lösning.

10. Om det icke-negativa (c j - z j ) värdet återgår till steg 5.

11. Om det inte finns några icke-negativa (c j - z j ) värden har den optimala lösningen erhållits.

Exempel 1:

En jordbrukare har 1000 hektar mark där han kan gräva majs, vete eller sojabönor, varje hektar av majs kostar Rs. 100 för beredning, kräver 7 man dagar av arbete och ger en vinst på Rs. 30 En tunnland vete kostar Rs. 120 för att förbereda, kräver 10 man dagar av arbetet och ge en vinst på Rs. 40.

En acre sojabönor kostar Rs70 att förbereda kräver 8 man dagar av arbete och ger en vinst på Rs. 20 Om bonden har Rs. 100 000 för förberedelse och räkning på 8000 mandagar av arbetet. Hur många hektar ska tilldelas varje grödor för att maximera vinsten? (Gujarat MBA, 1989)

Lösning:

Låt x tunnland markeras för majs

y arealer markeras för vete

z akre mark fördelas för sojabönor

Eftersom varje hektar mark för majs ger en vinst på Rs. 30, för veteutbyten Rs. 40 och för sojabönor Rs. 20. Den matematiska formuleringen av LLP är

Max Z = 30x + 40y + 20z + 0S 1, + OS 2, + 0S 3

Med förbehåll för

100 x + 120y + 70z <100000

7x + 10y + 8z ≤ 8000

x + y + z <1000

x, y, z ≥ 0

Låt oss konvertera ojämlikheterna till ekvationer genom att introducera slakvariablerna S 1, S 2 och S 3 . Objektfunktionen och begränsningen kan skrivas som

I den grundläggande variabla kolumnen är vektorerna för variabel S1, (1, 0, 0), S2, (1, 0, 1) och S3 (0, 0, 1) den initiala möjliga lösningen ges av variablerna S 1, S 2 och S 3 båda totala vinsten = 0

Nu Z j och C j - Z j beräknas enligt regel 1, 2 och 3. Nyckelkolumnen bestäms med startmarkerad kolumn och Simplex Tabell II bereds enligt följande.

Tabell II ger inte optimal lösning vi fortsätter vidare för att förbereda enkel tabell III och förbättra lösningen enligt följande:

Minimeringsproblem av Big M. Metod:

I industrin kan det vara beläget där målet kan vara att minimera produktionskostnaden eller tillverkningstidens längd, dvs att objektivfunktionen ska minimeras i sådana fall kan vi fortsätta på samma sätt som ett maximeringsproblem genom att enkelt multiplicera med båda sidorna av objektiv funktion av-1 I sådana situationer kommer minimering av Z att vara maximeringen av (-Z).

I sådana fall, eftersom överskottsvariablerna tar ett negativt värde som bryter mot icke-negativitetsbegränsningen, för att övervinna denna svårighet introducerar vi nya variabla format som artificiella variabler.

Nu tilldelar vi 3000 koefficient till överskott variabler och + M till konstgjorda variabler. För att få källa att artificiella variabler inte är de grundläggande variablerna i optimal lösning, tilldelar vi dem mycket höga kostnader, varför M definieras som ett mycket stort antal, dvs Big M eller straff.

Denna metod illustreras med hjälp av följande:

Exempel 2:

Driftforskning: Verktyg # 2. Transportproblem:

Transportproblemen är en av de typer av LPP som syftar till att transportera varor / produkter i olika kvantiteter av en enda homogen föremål till olika destinationer för att minimera totala transportkostnader i vardagen de olika tillverkningsorganisationerna eller andra anläggningar som är förfallna för olika överväganden lagra sina slutprodukter eller föremål på olika ställen betecknade som ursprung eller varor, hus när leveransen ska göras till användarna, då varorna transporteras från ursprung till en eller flera destinationer är det övergripande syftet med denna process att bestämma en distributionspolitik så att den totala transportkostnaden är minst eller den tid som förbrukas vid omlastning är minst.

Efter inhemska färdiga produkter från fabriken ska transporteras till lager på mest ekonomiskt sätt i transportproblemen kan olika egenskaper hos linjär programmering observeras här tillgängligheten liksom kraven hos olika centra är ändliga och utgör de begränsade resurserna för transportproblem de särskilda fallen av simplexmetoden.

Applicering i ventiler transport av produkter från flera källor till olika destinationspunkter som:

(i) Transportenheter sönderdelad destination. Målet är att minimera transportkostnaden.

(ii) Maximera vinsten vid transport av enheterna till destinationen.

De viktigaste stegen är följande :

Steg 1:

Formulera problemet och sätt i form av transportmatris.

Steg 2:

Hämta den grundläggande möjliga lösningen.

Steg 3:

Test för optimala lösningar.

Steg 4:

Uppdatera lösningen genom framgångsförbättringar tills ingen ytterligare minskning av transportkostnaden är möjlig.

Vanligtvis använda metoder är:

1. North West Corner Method.

2. Minsta kostnadsmetod.

3. Vogels Approximation-metod.

Åtgärder involverade i nordvästra hörnet Metod:

Steg 1:

Konstruera en tom maxmatris kompletterad med rader och kolumner.

Steg 2:

Ange raden Totals och kolumn Totals i slutet.

Steg 3:

Börja med (11) cell vid den nordvästra delen av matrisen tilldela maximal mängd / antal som tar hand om att tilldelningen inte kan vara mer än den kvantitet som krävs av respektive lagerhus eller mer än den tillgängliga kvantiteten vid leveranscentra.

Steg 4:

Efter att du har justerat utbuds- och efterfrågningsnummer i respektive rader och kolumner allokeras, flyttas ner till första cellen i och raden upprepa steg 3.

Steg 5:

Efter att efterfrågan på första kolumnen är uppfylld, gör den till nästa cell i den andra kolumnen och första raden och gå till steg 3.

Steg 6:

Om någon cellleverans motsvarar efterfrågan på dem kan nästa tilldelning vara i celler i nästa rader och kolumner.

Steg 7:

Fortsätt processen tills den totala tillgängliga kvantiteten tilldelas helt till cellerna enligt krav

Exempel 3:

Lös följande problem av NWCM för att beräkna minsta transportkostnad:

Steg i lägsta kostnad:

Denna metod tar hänsyn till den lägsta kostnaden och tar därför mindre tid att lösa problemet. De olika stegen är följande:

Steg 1:

Markera cellen med lägsta transportkostnad bland alla rader och kolumner i matrisen. Tilldela så mycket som möjligt för att eliminera antingen den raden eller kolumnen som antingen avgaser källan eller fyller hela kravet. Om båda uppfyller dem eliminerar man endera. Om minsta kostnadscell inte är unik, välj sedan valfritt någon cell med lägsta kostnad.

Steg 2:

Upprepa proceduren för alla okrossade rader och kolumner med nästa minsta kostnadscell. Steg 3: Upprepa proceduren tills alla källor är uttömda eller efterfrågan på hela destinationen är fylld.

Exempel 4:

Lös följande problem med minsta kostnadsmetod:

Vogel Approximation Method:

Denna metod är en sanktion eller ånger metod och är föredragen över de andra två metoderna, den initiala basiska möjliga lösningen erhållen antingen optimal eller mycket nära den optimala lösningen, därför reduceras den tid som krävs för att beräkna den optimala lösningen.

I denna metod är anslaget enhetsomkostningsbördan dvs den raden eller kolumnen som anger den högsta enhetsomkostningsstraffen / skillnaden mellan den lägsta och den näst högsta kostnaden väljs först med avseende på fördelningen. På så sätt görs de följande tilldelningarna i de andra cellerna med tanke på den högsta enhetskostnadsstraffen.

Tilldelningen görs för att minimera straffkostnaden. De olika åtgärderna är följande:

Steg 1:

Beräkna bötesbeloppet för varje rad och kolumn det görs genom att bara ta skillnaden mellan den minsta och nästa minsta kostnaden för transport i samma rad och kolumn, dvs skillnaden anger det straff som ska betalas om tilldelningen inte görs till minimikostnaden kriterium.

Steg 2:

Välj en rad eller kolumn med största straff och allokera så mycket som möjligt till den billigaste cellen. Vid bindning väljs en cell med maximal fördelning först

Steg 3:

Korsa antingen raden eller kolumnen efter att du har uppfyllt efterfrågan eller uttömt utbudet, den återstående raden eller kolumnen är tilldelad nolltillförsel eller efterfrågan. Varje rad eller kolumn med nolltillförsel eller efterfrågan med inte användas för ytterligare beräkningar.

Steg 4:

Upprepa steg 1 och 3 tills alla källor är uttömda eller allt krav är uppfyllda.

Exempel 5:

En tillverkning vill skicka 8 laster av sin produkt från produktionscentra X, Y och Z till distributionscentra A, B och C miljonen från ursprung 0 till destination D är följande matris.

Exempel 6:

Hitta den optimala lösningen av följande transportproblem genom att få initial lösning med vogets approximation metod:

Lösning:

Låt oss tillämpa vogels approximationsmetod. Problem balanserade som utbud = Efterfrågan = 50 enheter. Låt oss tillämpa vogels metod enligt tabellen nedan.

Transportkostnad = 2 x 15 + 9 x 15 + 20 x 10 + 4 x 5 + 18 x 5 x 475 enheter.

Kontrollera optimalt:

Optimitetstest kan utföras om två villkor är uppfyllda, dvs

1. Det finns m + n-1 fördelning, vars m är antal rader, n är antal kolumner. Här m + n - = 6. Men antalet fördelningar är fem.

2. Dessa m + n-1-tilldelningar borde vara i oberoende positioner, dvs det bör inte vara möjligt att öka eller minska någon fördelning utan att antingen ändra placeringen av tilldelningarna eller bryta mot rad- eller kolumnrestriktionerna.

En enkel regel för tilldelningar att vara i oberoende positioner är att det är omöjligt att resa från någon fördelning, till sig själv en serie horisontella och vertikala steg från en upptagen cell till en annan, utan direkt omgång av rutt. Det framgår att i det nuvarande exemplet är allokering i oberoende positioner eftersom ingen sluten slinga kan bildas vid de tilldelade cellerna.

Därför är det första villkoret inte nöjd och därför för att tillfredsställa första villkoret måste vi fördela en liten mängd E till de lediga cellerna som har lägsta transportkostnad. Det kan ses att t kan tilldelas i cell (2, 2) med en kostnad på 7 enheter och fortfarande kommer anslagen att vara kvar i oberoende position som beskrivs nedan i tabell 2.

Nu är antalet anslag m + n - 6 = 6 och de är i oberoende positioner. Skriv ner kostmatrisen vid tilldelade celler. (Tabell 3)

Initial kostnadsmatris för tilldelade celler. Skriv också värdena för u i och v j .

Det framgår av tabell 5 att cellutvärdering vid cell (1, 4) är negativ dvs -4, därför att transportkostnaden ytterligare reduceras genom att allokera vid cell (1, 4).

Låt oss skriva ned de ursprungliga anslagen och den föreslagna nya tilldelningen.

Det framgår av tabell 6 att om vi allokerar i cellen (1, 4) bildas en slinga som visas och vi fördelar 10 enheter så att tilldelningen i cellen (2, 4) försvinner som visas nedan i tabell 7. Ny fördelnings tabellen blir

Transportkostnad = 5X 2 + 10X 1 1 + 10X 7 + 15X 9 + 5X 4 + 18 + 5 = 435 enheter.

dvs transportkostnaden har sjunkit från 475 enheter till 435 enheter.

Kontrollera optimalt:

Låt oss se om denna lösning är optimal eller inte? För det igen måste två villkor kontrolleras, dvs

Antal fördelning = m + n-1 = 6 (nöjd)

Allokering i oberoende position (nöjd eftersom sluten slinga för tilldelade celler bildas inte) Skriv kostnad vid allokerade allas och värden på u i och v j .

Operationsforskning: Verktyg # 3. Uppdragsproblem:

Uppdragsproblem är en speciell typ av linjär programmeringsproblem som handlar om fördelningen av de olika resurserna till de olika aktiviteterna på en till en.

Det gör det på ett sådant sätt att kostnaden eller tiden som är involverad i processen är minimal och vinsten eller försäljningen är maximal. Även om problemet kan lösas med simplexmetod eller med transportmetod men uppdragsmodellen ger ett enklare tillvägagångssätt för dessa problem.

I en fabrik kan en handledare ha sex arbetstagare tillgängliga och sex jobb att skjuta. Han måste fatta beslut om vilket jobb som ska ges till vilken arbetare. Problemet är ett till ett. Detta är ett uppdragsproblem.

Uppdragsmodell:

Antag att det finns n underlättar och n jobb. Det är uppenbart att i det här fallet kommer det att finnas n uppdrag. Varje anläggning eller sägare kan utföra varje jobb, en i taget. Men det borde finnas viss procedur med vilken uppgift ska ske så att vinsten maximeras eller kostnaden eller tiderna minimeras.

I tabellen definieras Co ij som kostnaden när jobbet tilldelas arbetstagaren. Det kan noteras här att detta är ett speciellt fall av transportproblem när antalet rader är lika med antal kolumner.

Matematisk formulering:

Varje grundläggande möjlig lösning på ett uppdragsproblem består av (2n - 1) variabler, vari variablerna (n - 1) är noll; n är antal jobb eller antal anläggningar.

På grund av denna höga degeneration, om vi löser problemet med vanlig transportmetod, blir det ett komplicerat och tidskrävande arbete. Således erhålls en separat teknik för den. Innan du går till den absoluta metoden är det mycket viktigt att formulera problemet.

Antag att Xjj är en variabel som definieras som

Metod för att lösa problem (ungersk teknik):

Tänk på den objektiva funktionen av minimeringstypen.

Följande steg är inblandade i att lösa detta uppdragsproblem:

1. Leta reda på det minsta kostnadselementet i varje rad i det angivna kostnadsbordet med början på den första raden. Nu subtraheras detta minsta element från varje element i den raden. Så vi kommer att få minst en noll i varje rad i det här nya bordet.

2. Efter att ha byggt bordet (som vid steg 1) tar kolumnerna i tabellen. Börja från första kolumnen hitta det minsta kostnadselementet i varje kolumn. Nu subtrahera det minsta elementet från varje element i den kolumnen. Efter att ha utfört steg 1 och steg 2 kommer vi att få minst en noll i varje kolumn i reducerad kostnadstabell.

3. Nu görs uppdragen för det reducerade bordet på följande sätt:

(i) Rader undersöks successivt, tills raden med exakt singel (en) noll hittas. Uppgift görs till denna nollpunkt genom att placera kvadrat □ runt den och i motsvarande kolumn, korsas alla andra nollor (x) eftersom dessa inte kommer att användas för att göra någon annan uppgift i den här kolumnen. Steg utförs för varje rad.

(ii) Steg 3 (i) som nu utförs på kolumnerna enligt följande: Kolumner undersöks successivt tills en kolumn med exakt en noll hittas. Nu görs uppgift om denna nollpunkt genom att ställa torget runt det och samtidigt korsas alla andra nollor i motsvarande rader (x) steg utförs för varje kolumn.

(iii) Steg 3 (i) och 3 (ii) upprepas tills alla nollor är antingen märkta eller korsade. Om numret av markerade nollor eller de uppdrag som gjorts är lika med antal rader eller kolumner har optimal lösning uppnåtts. Det kommer att finnas exakt enstaka uppgift i varje eller kolumner utan uppgift. I det här fallet går vi till steg 4.

4. Rita i det här läget det minimala antalet linjer (horisontella och vertikala) som är nödvändiga för att täcka alla nollor i matrisen som erhållits i steg 3.

Följande förfarande antas:

(i) Markera (V) alla rader som inte har någon uppgift.

(ii) Markera nu (V) alla dessa kolumner som har noll i fältmarkerade rader.

(iii) Markera nu alla rader som inte redan är markerade och som har uppdrag i de markerade kolumnerna.

(iv) Alla steg, dvs 4 (1), 4 (2), 4 (3) upprepas tills inga fler rader eller kolumner kan markeras,

(v) Rita nu raka linjer som passerar genom alla omärkta rader och markerade kolumner. Det kan också noteras att i en nxn-matris kommer alltid mindre än 'n' linjer att täcka alla nollor om det inte finns någon lösning bland dem.

5. I steg 4, om antalet rader som är ritade är lika med n eller antalet rader, är det den optimala lösningen om inte, och sedan gå till steg 6.

6. Välj det minsta elementet bland alla de avtäckta elementen. Nu subtraheras detta element från alla de avtäckta elementen och läggs till elementet som ligger vid korsningen av två linjer. Detta är matrisen för färska uppdrag.

7. Upprepa proceduren från steg (3) tills antalet uppdrag blir lika med antalet rader eller antal kolumner.