Linjär programmering är ett matematiskt begrepp som används för att hitta den optimala lösningen av den linjära funktionen. Denna metod använder enkla antaganden för att optimera den givna funktionen. Linjär programmering har en enorm verklig applikation och den används för att lösa olika typer av problem.

Linjär programmering används i olika branscher som sjöfartsindustrier, tillverkningsindustrier, transportindustrier, telekommunikationer och andra.

Termen linjär programmering består av två ord linjär och programmering, ordet linjär berättar förhållandet mellan olika typer av variabler av grad ett som används i ett problem och ordet programmering berättar steg-för-steg-proceduren för att lösa dessa problem.

I den här artikeln kommer vi att lära oss om linjär programmering, dess exempel, formler och andra begrepp i detalj.

Innehållsförteckning

• Vad är linjär programmering?
• Komponenter i linjär programmering
• Exempel på linjär programmering
• Linjära programmeringsproblem
• Typer av linjära programmeringsproblem
• Linjär programmeringsformel
• Hur löser man linjära programmeringsproblem?
• Linjära programmeringsmetoder
• Linjär programmering enkel metod
• Linjär programmering grafisk metod
• Linjär programmeringsapplikationer
• Vikten av linjär programmering
• Aktuella tillämpningar av linjär programmering
• Linjär programmering i operationsforskning
• Enkel metod

Vad är linjär programmering?

Linjär programmering eller Linjär optimering är en teknik som hjälper oss att hitta den optimala lösningen för ett givet problem, en optimal lösning är en lösning som är det bästa möjliga resultatet av ett givet problem.

Enkelt uttryckt är det metoden för att ta reda på hur man gör något på bästa möjliga sätt. Med begränsade resurser måste du utnyttja resurserna optimalt och uppnå bästa möjliga resultat i ett visst mål som lägsta kostnad, högsta marginal eller lägsta tid.

Situationen som kräver en sökning efter de bästa värdena på variablerna med vissa begränsningar är där vi använder linjära programmeringsproblem. Dessa situationer kan inte hanteras med vanliga kalkyler och numeriska tekniker.

Linjär programmeringsdefinition

Linjär programmering är den teknik som används för att optimera ett visst scenario. Att använda linjär programmering ger oss bästa möjliga resultat i en given situation. Den använder alla tillgängliga resurser på ett sätt så att de ger det optimala resultatet.

Komponenter i linjär programmering

De grundläggande komponenterna i ett linjär programmeringsproblem (LP) är:

• Beslutsvariabler: Variabler du vill bestämma för att uppnå den optimala lösningen.
• Målfunktion: M atematisk ekvation som representerar det mål du vill uppnå
• Begränsningar: Begränsningar eller restriktioner som dina beslutsvariabler måste följa.
• Icke-negativitetsbegränsningar: I några verkliga scenarier kan beslutsvariabler inte vara negativa

Ytterligare egenskaper hos linjär programmering

• Finitet: Antalet beslutsvariabler och begränsningar i ett LP-problem är ändligt.
• Linjäritet: Den objektiva funktionen och alla begränsningar måste vara linjära funktioner för beslutsvariablerna . Det betyder att graden av variabler bör vara en.

Exempel på linjär programmering

Vi kan förstå de situationer där linjär programmering tillämpas med hjälp av exemplet som diskuteras nedan,

Anta att en leveransman måste leverera 8 paket på en dag till de olika platserna i en stad. Han måste plocka alla paket från A och måste leverera dem till punkterna P, Q, R, S, T, U, V och W. Avståndet mellan dem anges med linjerna som visas i bilden nedan. Den kortaste vägen som leveransmannen följer beräknas med hjälp av konceptet linjär programmering.

plsql

Linjära programmeringsproblem

Linjära programmeringsproblem (LPP) innebära att optimera en linjär funktion för att hitta den optimala värdelösningen för funktionen. Det optimala värdet kan vara antingen maxvärdet eller minimivärdet.

I LPP kallas de linjära funktionerna objektiva funktioner. En objektiv funktion kan ha flera variabler, som är föremål för villkor och måste uppfylla linjära begränsningar .

Typer av linjära programmeringsproblem

Det finns många olika linjära programmeringsproblem (LPP) men vi kommer att behandla tre stora linjära programmeringsproblem i den här artikeln.

Tillverkningsproblem

Tillverkningsproblem är ett problem som handlar om antalet enheter som ska produceras eller säljas för att maximera vinsten när varje produkt kräver fast arbetskraft, maskintimmar och råmaterial.

Dietproblem

Den används för att beräkna antalet olika typer av beståndsdelar som ska ingå i kosten för att få lägsta kostnad, beroende på tillgången på mat och deras priser.

Transportproblem

Den används för att bestämma transportschemat för att hitta det billigaste sättet att transportera en produkt från anläggningar/fabriker belägna på olika platser till olika marknader.

Linjär programmeringsformel

Ett linjärt programmeringsproblem består av,

• Beslutsvariabler
• Objektiv funktion
• Begränsningar
• Icke-negativa begränsningar

Beslutsvariabler är variablerna x, och y, som bestämmer resultatet av det linjära programmeringsproblemet och representerar den slutliga lösningen.

De objektiv funktion , generellt representerad av Z, är den linjära funktion som måste optimeras enligt det givna villkoret för att få den slutliga lösningen.

De restriktioner påtvingade beslutsvariabler som begränsar deras värden kallas begränsningar.

Nu är den allmänna formeln för ett linjärt programmeringsproblem,

Objektiv funktion : Z = axe + by

Begränsningar: cx + dy ≥ e, px + qy ≤ r

Icke-negativa begränsningar: x ≥ 0, y ≥ 0

I ovanstående villkor är x och y beslutsvariablerna.

Hur löser man linjära programmeringsproblem?

Innan vi löser de linjära programmeringsproblemen måste vi först formulera problemen enligt standardparametrarna. Stegen för att lösa linjära programmeringsproblem är,

Steg 1: Markera beslutsvariablerna i problemet.

Steg 2: Bygg upp problemets objektiva funktion och kontrollera om funktionen behöver minimeras eller maximeras.

Steg 3: Skriv ner alla begränsningar för de linjära problemen.

Steg 4: Säkerställ icke-negativa begränsningar av beslutsvariablerna.

Steg 5: Lös nu det linjära programmeringsproblemet med vilken metod som helst, vanligtvis använder vi antingen simplex eller grafisk metod.

Linjära programmeringsmetoder

Vi använder olika metoder för att lösa linjära programmeringsproblem. De två vanligaste metoderna som används är,

• Enkel metod
• Grafisk metod

Låt oss lära oss om dessa två metoder i detalj i den här artikeln,

Linjär programmering enkel metod

En av de vanligaste metoderna för att lösa det linjära programmeringsproblemet är simplexmetoden. I denna metod upprepar vi ett specifikt villkor 'n' ett antal gånger tills en optimal lösning uppnås.

De steg som krävs för att lösa linjära programmeringsproblem med simplexmetoden är,

Steg 1: Formulera de linjära programmeringsproblemen utifrån de givna begränsningarna.

Steg 2: Konvertera alla de givna ojämlikheterna till ekvationer eller likheter för linjära programmeringsproblem genom att lägga till slack-variabeln till varje olikhet där det behövs.

Steg 3: Konstruera den initiala simplextabellen. Genom att representera varje begränsningsekvation i rad och skriva målfunktionen på den nedre raden. Den så erhållna tabellen kallas Simplex-tabellen.

Steg 4: Identifiera den största negativa posten i den nedre raden kolumnen för elementet med den högsta negativa posten kallas pivotkolumnen

Steg 5: Dela posterna i kolumnen längst till höger med posterna i respektive pivotkolumn, exklusive posterna i den nedersta raden. Nu kallas raden som innehåller den minsta posten pivotraden. Pivotelementet erhålls genom skärningspunkten mellan pivotraden och pivotkolumnen.

Steg 6: Med hjälp av matrisoperation och med hjälp av pivotelementet gör alla poster i pivotkolumnen noll.

Steg 7: Kontrollera efter de icke-negativa posterna på den nedersta raden om det inte finns några negativa poster på den nedre raden, avsluta processen annars starta processen igen från steg 4.

Steg 8: Den slutliga simplextabellen som så erhålls ger lösningen på vårt problem.

Linjär programmering grafisk metod

Graphical Method är en annan metod än Simplex-metoden som används för att lösa linjära programmeringsproblem. Som namnet antyder använder denna metod grafer för att lösa de givna linjära programmeringsproblemen. Detta är den bästa metoden för att lösa linjära programmeringsproblem och kräver mindre ansträngning än simplexmetoden.

Medan vi använder denna metod plottar vi alla ojämlikheter som är utsatta för begränsningar i de givna linjära programmeringsproblemen. Så snart alla olikheter för den givna LPP plottas i XY-grafen ger den gemensamma regionen för alla olikheter den optimala lösningen. Alla hörnpunkter i den möjliga regionen beräknas och värdet av målfunktionen vid alla dessa punkter beräknas, sedan jämför vi dessa värden får vi den optimala lösningen av LPP.

Exempel: Hitta det maximala och minimala värdet för z = 6x + 9y när villkoren är,

• 2x + 3y ≤ 12
• x och y ≥ 0
• x + y ≤ 5

Lösning:

Steg 1 : Konvertera först inekvationerna till normala ekvationer. Därför blir ekvationerna 2x+3y = 0, x = 0, y = 0 och x + y = 5.

Steg 2 : Hitta punkterna där 2x + 3y och x + y = 5 skär x-axeln och y-axeln. För att hitta skärningspunkten för x-axeln sätt y = 0 i respektive ekvation och hitta punkten. På liknande sätt för y-axelns skärningspunkter sätt x = 0 i respektive ekvation.

Steg 3 : Rita de två linjerna som skär x-axeln och y-axeln. Vi finner att de två axlarna skär varandra vid (3,2).

Steg 4 : För x ≥ 0 och y ≥ 0 finner vi att båda ekvationerna följs. Därför kommer regionen att inkludera en områdesregion som omges av två axlar och båda linjerna inkluderar origo. Det plottade området visas nedan i figuren.

Steg 5 : Hitta Z för varje punkt och maxima och minima.

Koordinater	Z = 6x + 9y
(0,5)	Z = 45
(0,4)	Z = 36
(5,0)	Z = 30
(6,0)	Z = 36
(3.2)	Z = 36

Därför finner vi att Z = 6x + 9y är maximum vid (0,5) och minimum vid (5,0).

Linjär programmeringsapplikationer

Linjär programmering har tillämpningar inom olika områden. Den används för att hitta minimikostnaden för en process när alla begränsningar för problemen är givna. Den används för att optimera transportkostnaden för fordonet, etc. Olika tillämpningar av linjär programmering är

Ingenjörsindustrier

Engineering Industries använder linjär programmering för att lösa design- och tillverkningsproblem och för att få maximal effekt från ett givet tillstånd.

Produktionsindustrier

Tillverkningsindustrin använder linjär programmering för att maximera företagens vinst och för att minska tillverkningskostnaderna.

Energiindustrier

Energiföretag använder linjär programmering för att optimera sin produktion.

Transportindustrier

Linjär programmering används också inom transportindustrin för att hitta vägen för att minimera transportkostnaderna.

Vikten av linjär programmering

Linjär programmering har stor betydelse i olika branscher, den maximerar utmatningsvärdet samtidigt som ingångsvärdena minimeras enligt olika begränsningar.

LP är mycket applicerbart när vi har flera villkor när vi löser ett problem och vi måste optimera resultatet av problemet, det vill säga antingen måste vi hitta minimi- eller maximivärdet enligt ett givet villkor.

Läs mer,

• Linjära ojämlikheter
• Algebraisk lösning av linjära ojämlikheter

Linjära programmeringsproblem

Problem 1: Ett företag tillverkar och säljer två typer av produkter och produktionskostnaden för varje enhet a och b är rupier 200 respektive 150 rupier varje produktenhet ger en vinst på 20 rupier och varje enhet av produkt b ger en vinst på 15 rupier vid försäljning . Företaget uppskattar den månatliga efterfrågan på A och B till maximalt den skördade enheten i hela produktionsbudgeten för månaden är satt till rupier 50 000. Hur många enheter ska företaget tillverka för att få maximal vinst på sin månatliga försäljning från en och b?

Lösning:

Låt x = antalet enheter av typ A

y = Antal enheter av typ B

Maximera Z = 40x + 50y

Med förbehåll för begränsningarna

3x + y ≤ 9

x + 2y ≤ 8

och x, y ≥ 0

Tänk på ekvationen,

3x + y = 9

x = 3

y = 0

och x + 2y = 8

x = 8

y = 0

Nu kan vi bestämma det maximala värdet för Z genom att utvärdera värdet på Z vid de fyra punkterna (hörn) som visas nedan

Vertices	Z = 40x + 50y
(0, 0)	Z = 40 × 0 + 50 × 0 = Rs. 0
(3, 0)	Z = 40 × 3 + 50 × 0 = Rs. 120
(0, 4)	Z = 40 × 0 + 50 × 4 = Rs. 200
(23)	Z = 40 × 2 + 50 × 3 = Rs. 230

Maximal vinst, Z = Rs. 230

∴ Antal enheter av typ A är 2 och antalet enheter av typ B är 3.

Problem 2: Maximera Z = 3x + 4y.

Med förbehåll för begränsningar, x + y ≤ 450, 2x + y ≤ 600 och x, y ≤ 0.

Lösning:

Vi har från det givna

Begränsningar (1)

X + Y = 450

funktioner i java

Att sätta x = 0, ⇒ 0 + y = 450 ⇒ y = 450

Att sätta y = 0, ⇒ x + 0 = 450 ⇒ x = 450

Från, Begränsningar (2)

2x + y = 600

Att sätta x = 0, ⇒ 0 + y = 600 ⇒ y = 600

Att sätta y = 0, ⇒ 2x + 0 = 600 ⇒ x = 300

Nu har vi punktkoordinaten Z = 3x + 4y

Därför är den optimala lösningens maximala Z = 1800 vid koordinaten x = 0 och y = 450. Grafen ges nedan.

Aktuella tillämpningar av linjär programmering

Linjär programmering, en kraftfull matematisk teknik, används för att lösa optimeringsproblem i olika branscher. Här är några moderna applikationer:

• Supply Chain Optimering : Linjär programmering hjälper företag att minimera kostnaderna och maximera effektiviteten i sina leveranskedjor. Det används för att bestämma de mest kostnadseffektiva transportvägarna, lagerdrift och lagerhanteringsstrategier.
• Energihushållning : Inom energisektorn används linjär programmering för att optimera mixen av energiproduktionsmetoder. Detta inkluderar att balansera traditionella energikällor med förnybara för att minska kostnader och miljöpåverkan samtidigt som efterfrågan tillgodoses.
• Telekommunikationsnätverksdesign : Linjär programmering hjälper till att designa effektiva telekommunikationsnätverk. Det hjälper till att allokera bandbredd, designa nätverkslayouter och optimera dataflödet för att säkerställa höghastighetskommunikation till lägre kostnader.
• Finansiell planering : Företag och finansanalytiker använder linjär programmering för portföljoptimering, riskhantering och kapitalbudgetering. Det hjälper till att fatta investeringsbeslut som maximerar avkastningen samtidigt som risken minimeras.
• Sjukvårdslogistik : Inom sjukvården tillämpas linjär programmering för att optimera allokeringen av resurser, såsom sjukhussängar, medicinsk personal och utrustning. Det är avgörande för att förbättra patientvården, minska väntetiderna och hantera kostnader effektivt.
• Optimering av tillverkningsprocessen : Linjär programmering används för att bestämma de optimala produktionsnivåerna för flera produkter inom en tillverkningsanläggning, med hänsyn till begränsningar som arbetskraft, material och maskintillgänglighet.
• Jordbruksplanering : Jordbrukare och jordbruksplanerare använder linjär programmering för att besluta om val av gröda, markanvändning och resursallokering för att maximera avkastningen och vinsten samtidigt som de sparar resurser.
• Schemaläggning av flygbolagsbesättning : Flygbolag använder linjär programmering för att schemalägga besättningar effektivt, vilket säkerställer att flygningar är bemannade i enlighet med föreskrifter och minimerar driftskostnaderna.

Dessa applikationer visar mångsidigheten och kraften hos linjär programmering för att lösa komplexa optimeringsproblem inom olika sektorer, vilket visar dess relevans i dagens datadrivna värld.

Linjär programmering i operationsforskning

• Kärnverktyg : Linjär programmering är ett grundläggande verktyg i operationsforskning för att optimera resurser.
• Beslutsfattande : Hjälper till att fatta de bästa besluten angående resursallokering, maximera vinster eller minimera kostnader.
• Breda applikationer : Används inom olika områden som logistik, tillverkning, ekonomi och hälsovård för att lösa komplexa problem.
• Modellera verkliga problem : Förvandlar verkliga problem till matematiska modeller för att hitta de mest effektiva lösningarna.

Enkel metod

• Optimeringsalgoritm : Simplex-metoden är en kraftfull algoritm som används i linjär programmering för att hitta den optimala lösningen på linjära ojämlikheter.
• Steg-för-steg tillvägagångssätt : Den rör sig iterativt mot den bästa lösningen genom att navigera i kanterna av den genomförbara regionen som definieras av begränsningar.
• Effektivitet : Känd för sin effektivitet i att lösa storskaliga linjära programmeringsproblem.
• Mångsidighet : Tillämpligt inom olika domäner som kostplanering, nätverksflöden, produktionsschemaläggning och mer, vilket visar upp dess mångsidighet.

Linjär programmering – Vanliga frågor

Vad är linjär programmering?

Linjär programmering är ett matematiskt koncept som används för att optimera ett givet linjärt problem som har en mängd olika begränsningar. Med hjälp av linjär programmering ger vi den optimala effekten av det givna problemet

Vad är linjära programmeringsproblem?

Linjära programmeringsproblem (LPP) är de problem som ger den optimala lösningen för de givna förhållandena.

Vad är linjär programmeringsformel?

Allmänna linjära programmeringsformler är,

• Målfunktion: Z = axe + by
• Begränsningar: px + qy ≤ r, sx + ty ≤ u
• Icke-negativa begränsningar: x ≥ 0, y ≥ 0

Vilka är de olika typerna av linjär programmering?

Olika typer av linjära programmeringsmetoder är,

• Linjär programmering med enkel metod
• Linjär programmering med R-metoden
• Linjär programmering med grafisk metod

Vilka är kraven för linjär programmering?

Olika krav för linjär programmeringsproblem är,

• Linjäritet
• Objektiv funktion
• Begränsningar
• Icke-negativitet

Vilka är fördelarna med linjär programmering?

Olika fördelar med linjär programmering är,

• Det ger den optimala lösningen på ett givet linjärt problem.
• Det är lätt att använda och ger alltid konsekventa resultat
• Det hjälper till att maximera vinsten och minska insatskostnaden.