Lineær programmering er et matematisk konsept som brukes for å finne den optimale løsningen av den lineære funksjonen. Denne metoden bruker enkle forutsetninger for å optimalisere den gitte funksjonen. Lineær programmering har en enorm applikasjon i den virkelige verden, og den brukes til å løse ulike typer problemer.

Lineær programmering brukes i ulike bransjer som skipsfart, produksjonsindustri, transportindustri, telekommunikasjon og andre.

Begrepet lineær programmering består av to ord lineær og programmering, ordet lineær forteller forholdet mellom ulike typer variabler av grad en som brukes i et problem, og ordet programmering forteller oss trinn-for-trinn-prosedyren for å løse disse problemene.

I denne artikkelen vil vi lære om lineær programmering, dens eksempler, formler og andre konsepter i detalj.

Innholdsfortegnelse

• Hva er lineær programmering?
• Komponenter i lineær programmering
• Eksempler på lineær programmering
• Lineære programmeringsproblemer
• Typer lineære programmeringsproblemer
• Lineær programmeringsformel
• Hvordan løse lineære programmeringsproblemer?
• Lineære programmeringsmetoder
• Lineær programmering enkel metode
• Lineær programmering grafisk metode
• Lineær programmeringsapplikasjoner
• Viktigheten av lineær programmering
• Oppdaterte anvendelser av lineær programmering
• Lineær programmering i operasjonsforskning
• Enkel metode

Hva er lineær programmering?

Lineær programmering eller Lineær optimalisering er en teknikk som hjelper oss å finne den optimale løsningen for et gitt problem, en optimal løsning er en løsning som er best mulig utfall av et gitt spesielt problem.

Enkelt sagt er det metoden for å finne ut hvordan man gjør noe på best mulig måte. Med begrensede ressurser må du utnytte ressursene optimalt og oppnå best mulig resultat i et bestemt mål som minst kostnad, høyeste margin eller minst tid.

Situasjonen som krever et søk etter de beste verdiene av variablene underlagt visse begrensninger, er der vi bruker lineære programmeringsproblemer. Disse situasjonene kan ikke håndteres med vanlige beregninger og numeriske teknikker.

Lineær programmeringsdefinisjon

Lineær programmering er teknikken som brukes for å optimalisere et bestemt scenario. Ved å bruke lineær programmering får vi best mulig resultat i en gitt situasjon. Den bruker alle tilgjengelige ressurser på en måte slik at de gir det optimale resultatet.

Komponenter i lineær programmering

De grunnleggende komponentene i et lineært programmeringsproblem (LP) er:

• Beslutningsvariabler: Variabler du ønsker å bestemme for å oppnå den optimale løsningen.
• Målfunksjon: M atematisk ligning som representerer målet du ønsker å oppnå
• Begrensninger: Begrensninger eller restriksjoner som beslutningsvariablene dine må følge.
• Ikke-negativitetsbegrensninger: I noen i virkelige scenarier, kan beslutningsvariabler ikke være negative

Ytterligere kjennetegn ved lineær programmering

• Begrensethet: Antall beslutningsvariabler og begrensninger i et LP-problem er begrenset.
• Linearitet: Objektfunksjonen og alle begrensninger må være lineære funksjoner av beslutningsvariablene . Det betyr at graden av variabler skal være én.

Eksempler på lineær programmering

Vi kan forstå situasjonene der lineær programmering brukes ved hjelp av eksemplet diskutert nedenfor,

Anta at en leveringsmann må levere 8 pakker på en dag til de forskjellige stedene i en by. Han må plukke alle pakkene fra A og må levere dem til punktene P, Q, R, S, T, U, V og W. Avstanden mellom dem er angitt ved hjelp av linjene som vist på bildet nedenfor. Den korteste veien som følges av leveringsmannen beregnes ved hjelp av konseptet lineær programmering.

lytteport

Lineære programmeringsproblemer

Lineære programmeringsproblemer (LPP) innebære å optimalisere en lineær funksjon for å finne den optimale verdiløsningen for funksjonen. Den optimale verdien kan enten være maksimumsverdien eller minimumsverdien.

I LPP kalles de lineære funksjonene objektive funksjoner. En objektiv funksjon kan ha flere variabler, som er underlagt betingelser og må tilfredsstille lineære begrensninger .

Typer lineære programmeringsproblemer

Det er mange forskjellige lineære programmeringsproblemer (LPP), men vi vil behandle tre store lineære programmeringsproblemer i denne artikkelen.

Produksjonsproblemer

Produksjonsproblemer er et problem som omhandler antall enheter som skal produseres eller selges for å maksimere fortjenesten når hvert produkt krever fast arbeidskraft, maskintimer og råvarer.

Diettproblemer

Den brukes til å beregne antall forskjellige typer bestanddeler som skal inkluderes i dietten for å få minimumskostnaden, avhengig av tilgjengeligheten av mat og prisene deres.

Transportproblemer

Den brukes til å bestemme transportplanen for å finne den billigste måten å transportere et produkt fra anlegg/fabrikker på forskjellige steder til forskjellige markeder.

Lineær programmeringsformel

Et lineært programmeringsproblem består av,

• Beslutningsvariabler
• Objektiv funksjon
• Begrensninger
• Ikke-negative restriksjoner

Beslutningsvariabler er variablene x, og y, som bestemmer resultatet av det lineære programmeringsproblemet og representerer den endelige løsningen.

De objektiv funksjon , vanligvis representert ved Z, er den lineære funksjonen som må optimaliseres i henhold til den gitte betingelsen for å få den endelige løsningen.

De begrensninger pålagt beslutningsvariabler som begrenser verdiene deres, kalles begrensninger.

Nå er den generelle formelen for et lineært programmeringsproblem,

Objektiv funksjon : Z = akse + by

Begrensninger: cx + dy ≥ e, px + qy ≤ r

Ikke-negative restriksjoner: x ≥ 0, y ≥ 0

I betingelsen ovenfor er x, og y beslutningsvariablene.

Hvordan løse lineære programmeringsproblemer?

Før vi løser de lineære programmeringsproblemene, må vi først formulere problemene i henhold til standardparametrene. Trinnene for å løse lineære programmeringsproblemer er,

Trinn 1: Merk beslutningsvariablene i oppgaven.

Steg 2: Bygg den objektive funksjonen til problemet og sjekk om funksjonen må minimeres eller maksimeres.

Trinn 3: Skriv ned alle begrensningene til de lineære problemene.

Trinn 4: Sørg for ikke-negative begrensninger av beslutningsvariablene.

Trinn 5: Løs nå det lineære programmeringsproblemet ved å bruke hvilken som helst metode, vanligvis bruker vi enten den simplekse eller grafiske metoden.

Lineære programmeringsmetoder

Vi bruker ulike metoder for å løse lineære programmeringsproblemer. De to vanligste metodene som brukes er,

• Enkel metode
• Grafisk metode

La oss lære om disse to metodene i detalj i denne artikkelen,

Lineær programmering enkel metode

En av de vanligste metodene for å løse det lineære programmeringsproblemet er simpleksmetoden. I denne metoden gjentar vi en spesifikk betingelse 'n' flere ganger til en optimal løsning er oppnådd.

Trinnene som kreves for å løse lineære programmeringsproblemer ved hjelp av simpleksmetoden er,

Trinn 1: Formuler de lineære programmeringsproblemene basert på de gitte begrensningene.

Steg 2: Konverter alle de gitte ulikhetene til ligninger eller likheter for de lineære programmeringsproblemene ved å legge til slakkvariabelen til hver ulikhet der det er nødvendig.

Trinn 3: Konstruer den første simplekstabellen. Ved å representere hver begrensningsligning på rad og skrive målfunksjonen på den nederste raden. Tabellen som er oppnådd på denne måten kalles Simplex-tabellen.

Trinn 4: Identifiser den største negative oppføringen i den nederste raden kolonnen til elementet med den høyeste negative oppføringen kalles pivotkolonnen

Trinn 5: Del oppføringene i kolonnen lengst til høyre med oppføringene i den respektive pivotkolonnen, unntatt oppføringene i den nederste raden. Nå kalles raden som inneholder den minste oppføringen pivotraden. Pivotelementet oppnås ved skjæringspunktet mellom pivotraden og pivotkolonnen.

Trinn 6: Ved hjelp av matriseoperasjon og ved hjelp av pivotelementet, gjør alle oppføringene i pivotkolonnen null.

Trinn 7: Se etter de ikke-negative oppføringene i den nederste raden hvis det ikke er noen negative oppføringer i den nederste raden, avslutt prosessen ellers start prosessen på nytt fra trinn 4.

Trinn 8: Den endelige simplekstabellen som er oppnådd på denne måten gir løsningen på problemet vårt.

Lineær programmering grafisk metode

Graphical Method er en annen metode enn Simplex-metoden som brukes til å løse lineære programmeringsproblemer. Som navnet antyder bruker denne metoden grafer for å løse de gitte lineære programmeringsproblemene. Dette er den beste metoden for å løse lineære programmeringsproblemer og krever mindre innsats enn simpleksmetoden.

Mens vi bruker denne metoden plotter vi alle ulikhetene som er utsatt for begrensninger i de gitte lineære programmeringsproblemene. Så snart alle ulikhetene til den gitte LPP er plottet i XY-grafen, gir fellesområdet for alle ulikhetene den optimale løsningen. Alle hjørnepunktene til den gjennomførbare regionen beregnes og verdien av målfunksjonen på alle disse punktene beregnes, og ved å sammenligne disse verdiene får vi den optimale løsningen av LPP.

Eksempel: Finn den maksimale og minimale verdien av z = 6x + 9y når begrensningsbetingelsene er,

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

Løsning:

Trinn 1 : Konverter først ligningene til normale ligninger. Derfor vil ligningene være 2x+3y = 0, x = 0, y = 0 og x + y = 5.

Steg 2 : Finn punktene der 2x + 3y og x + y = 5 kutter x-aksen og y-aksen. For å finne skjæringspunktet til x-aksen, sett y = 0 i den respektive ligningen og finn punktet. Tilsvarende for y-aksens skjæringspunkter, sett x = 0 i den respektive ligningen.

Trinn 3 : Tegn de to linjene som skjærer x-aksen og y-aksen. Vi finner at de to aksene skjærer hverandre ved (3,2).

Trinn 4 : For x ≥ 0 og y ≥ 0 finner vi at begge likningene følges. Derfor vil regionen inkludere en områderegion omsluttet av to akser og begge linjer inkludert origo. Det plottede området er vist nedenfor i figuren.

Trinn 5 : Finn Z for hvert punkt og maksima og 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

Derfor finner vi at Z = 6x + 9y er maksimum ved (0,5) og minimum ved (5,0).

Lineær programmeringsapplikasjoner

Lineær programmering har applikasjoner innen ulike felt. Den brukes til å finne minimumskostnaden for en prosess når alle begrensningene til problemene er gitt. Den brukes til å optimalisere transportkostnadene for kjøretøyet, etc. Ulike anvendelser av lineær programmering er

Ingeniørindustri

Engineering Industries bruker lineær programmering for å løse design- og produksjonsproblemer og for å få maksimal effekt fra en gitt tilstand.

Produksjonsindustri

Produksjonsindustrien bruker lineær programmering for å maksimere fortjenesten til selskapene og redusere produksjonskostnadene.

Energiindustri

Energiselskaper bruker lineær programmering for å optimalisere produksjonen.

Transportindustri

Lineær programmering brukes også i transportnæringer for å finne veien for å minimere transportkostnadene.

Viktigheten av lineær programmering

Lineær programmering har stor betydning i ulike bransjer, den maksimerer utgangsverdien mens den minimerer inngangsverdiene i henhold til ulike begrensninger.

LP er svært anvendelig når vi har flere forhold mens vi løser et problem, og vi må optimalisere resultatet av problemet, dvs. enten må vi finne minimums- eller maksimumsverdien i henhold til en gitt tilstand.

sammenligning av løve og tiger

Les mer,

• Lineære ulikheter
• Algebraisk løsning av lineære ulikheter

Lineære programmeringsproblemer

Oppgave 1: Et selskap produserer og selger to typer produkter, og produksjonskostnadene for hver enhet a og b er henholdsvis 200 og 150 rupi hver produktenhet gir en fortjeneste på 20 rupi og hver enhet av produkt b gir en fortjeneste på 15 rupi ved salg . Selskapet estimerer den månedlige etterspørselen til A og B til maksimalt den høstede enheten i hele produksjonsbudsjettet for måneden er satt til rupi 50 000. Hvor mange enheter bør selskapet produsere for å oppnå maksimal fortjeneste på sitt månedlige salg fra en og b?

Løsning:

La x = antall enheter av type A

y = Antall enheter av type B

Maksimer Z = 40x + 50y

Med forbehold om begrensningene

3x + y ≤ 9

x + 2y ≤ 8

og x, y ≥ 0

Tenk på ligningen,

3x + y = 9

x = 3

y = 0

og x + 2y = 8

x = 8

y = 0

Nå kan vi bestemme den maksimale verdien av Z ved å evaluere verdien av Z ved de fire punktene (verteksene) er vist nedenfor

Topppunkter	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

Maksimal fortjeneste, Z = Rs. 230

∴ Antall enheter av type A er 2 og antall enheter av type B er 3.

Oppgave 2: Maksimer Z = 3x + 4y.

Med forbehold om begrensninger, x + y ≤ 450, 2x + y ≤ 600 og x, y ≤ 0.

Løsning:

Vi har fra det gitte

Begrensninger (1)

X + Y = 450

Setter x = 0, ⇒ 0 + y = 450 ⇒ y = 450

Setter y = 0, ⇒ x + 0 = 450 ⇒ x = 450

Fra, Begrensninger (2)

2x + y = 600

Setter x = 0, ⇒ 0 + y = 600 ⇒ y = 600

Setter y = 0, ⇒ 2x + 0 = 600 ⇒ x = 300

Nå har vi punktkoordinaten Z = 3x + 4y

Derfor er den optimale løsningsmaksimum Z = 1800 ved koordinat x = 0 og y = 450. Grafen er gitt nedenfor.

Oppdaterte anvendelser av lineær programmering

Lineær programmering, en kraftig matematisk teknikk, brukes til å løse optimaliseringsproblemer i ulike bransjer. Her er noen moderne applikasjoner:

• Optimalisering av forsyningskjede : Lineær programmering hjelper bedrifter med å minimere kostnader og maksimere effektiviteten i sine forsyningskjeder. Den brukes til å bestemme de mest kostnadseffektive transportrutene, lagerdrift og lagerstyringsstrategier.
• Energiledelse : I energisektoren brukes lineær programmering for å optimalisere blandingen av energiproduksjonsmetoder. Dette inkluderer å balansere tradisjonelle energikilder med fornybare for å redusere kostnader og miljøpåvirkning samtidig som etterspørselen dekkes.
• Telekommunikasjonsnettverksdesign : Lineær programmering hjelper til med å designe effektive telekommunikasjonsnettverk. Det hjelper til med å tildele båndbredde, designe nettverksoppsett og optimalisere dataflyten for å sikre høyhastighetskommunikasjon til lavere kostnader.
• Finansiell planlegging : Bedrifter og finansanalytikere bruker lineær programmering for porteføljeoptimalisering, risikostyring og kapitalbudsjettering. Det hjelper med å ta investeringsbeslutninger som maksimerer avkastningen samtidig som risikoen minimeres.
• Helselogistikk : I helsevesenet brukes lineær programmering for å optimalisere allokeringen av ressurser, slik som sykehussenger, medisinsk personell og utstyr. Det er avgjørende for å forbedre pasientbehandlingen, redusere ventetiden og administrere kostnadene effektivt.
• Optimalisering av produksjonsprosessen : Lineær programmering brukes til å bestemme de optimale produksjonsnivåene for flere produkter innenfor et produksjonsanlegg, med tanke på begrensninger som arbeidskraft, materialer og maskintilgjengelighet.
• Landbruksplanlegging : Bønder og landbruksplanleggere bruker lineær programmering for å bestemme avlingsvalg, arealbruk og ressursallokering for å maksimere utbytte og fortjeneste samtidig som de sparer ressursene.
• Planlegging av flyselskapets mannskap : Flyselskaper bruker lineær programmering for å planlegge mannskaper effektivt, og sikrer at flyreiser er bemannet i samsvar med regelverket og minimerer driftskostnadene.

Disse applikasjonene demonstrerer allsidigheten og kraften til lineær programmering for å løse komplekse optimaliseringsproblemer på tvers av ulike sektorer, og viser dens relevans i dagens datadrevne verden.

Lineær programmering i operasjonsforskning

• Kjerneverktøy : Lineær programmering er et grunnleggende verktøy i operasjonsforskning for å optimalisere ressurser.
• Beslutningstaking : Hjelper med å ta de beste beslutningene angående ressursallokering, maksimere fortjeneste eller minimere kostnader.
• Brede applikasjoner : Brukes i ulike felt som logistikk, produksjon, finans og helsetjenester for å løse komplekse problemer.
• Modellering av virkelige verdensproblemer : Transformerer virkelige problemer til matematiske modeller for å finne de mest effektive løsningene.

Enkel metode

• Optimaliseringsalgoritme : Simplex-metoden er en kraftig algoritme som brukes i lineær programmering for å finne den optimale løsningen på lineære ulikheter.
• Steg-for-trinn tilnærming : Den beveger seg iterativt mot den beste løsningen ved å navigere i kantene av den gjennomførbare regionen definert av begrensninger.
• Effektivitet : Kjent for sin effektivitet i å løse store lineære programmeringsproblemer.
• Allsidighet : Gjelder i ulike domener som kostholdsplanlegging, nettverksflyter, produksjonsplanlegging og mer, og viser allsidigheten.

Lineær programmering – vanlige spørsmål

Hva er lineær programmering?

Lineær programmering er et matematisk konsept som brukes til å optimalisere et gitt lineært problem som har en rekke begrensninger. Ved å bruke lineær programmering får vi det optimale resultatet av det gitte problemet

Hva er problemer med lineær programmering?

Lineære programmeringsproblemer (LPP) er problemene som gir den optimale løsningen på de gitte forholdene.

Hva er lineær programmeringsformel?

Generelle lineære programmeringsformler er,

• Objektiv funksjon: Z = akse + by
• Begrensninger: px + qy ≤ r, sx + ty ≤ u
• Ikke-negative restriksjoner: x ≥ 0, y ≥ 0

Hva er de forskjellige typene lineær programmering?

Ulike typer lineære programmeringsmetoder er,

• Lineær programmering med enkel metode
• Lineær programmering ved R-metoden
• Lineær programmering ved grafisk metode

Hva er kravene til lineær programmering?

Ulike krav til lineære programmeringsproblemer er,

• Linearitet
• Objektiv funksjon
• Begrensninger
• Ikke-negativitet

Hva er fordelene med lineær programmering?

Ulike fordeler med lineær programmering er,

• Det gir den optimale løsningen på et gitt lineært problem.
• Den er enkel å bruke og gir alltid konsistente resultater
• Det bidrar til å maksimere fortjenesten og redusere innsatskostnadene.