Linear Programming (LP): Study Notes

I denne artikkelen skal vi diskutere om Lineær programmering (LP): - 1. Begrep med lineær programmering 2. Bruksområder for lineær programmering 3. Antagelser om den lineære programmeringsmodellen 4. Formulering.

Konsept av lineær programmering:

Lineær programmering (LP) er en mye brukt matematisk optimaliseringsteknikk som ble utviklet i 1947 av George B. Dantzig for å løse planleggingsproblemer fra det amerikanske flyvåpenet. Selv om "programmering" av datamaskiner ikke er relatert til LP, har utviklingen av datamaskiner bidratt sterkt til suksessen til LP

I LP løses lineære ligninger igjen og igjen, hver gang man endrer en variabel til vi kommer frem til den endelige løsningen. I faktiske industrielle problemer er begrensningene for mange, og noen ganger dannes mer enn hundre lineære ligninger, hvis løsninger praktisk talt er umulige uten hjelp av en datamaskin.

Et stort antall økonomiske forretningsavgjørelser, for eksempel beste produktmiks av et firma, annonsering av budsjettmidler fordelt på konkurrerende medier, valg av beste produksjonsprosess, etc., kan analyseres og løses av LP. Alle forretningsrelaterte bekymringer har visse mål, f.eks. maksimering av overskudd, produksjon, salg, minimering av kostnader, etc.

Det algebraiske uttrykket til målet kalles en objektiv funksjon som må være lineær.

Optimaliseringen av den lineære objektive funksjonen må være underlagt begrensninger, som også er lineære algebraiske uttrykk i form av enten likheter eller ulikheter. Slike begrensninger må overholde 'ikke-negativitetsbegrensninger', da variablene ikke kan ha negative verdier. Oversettelsen av firmaets problemer til objektiv funksjon og et sett med lineære begrensninger kalles 'Formulering av LP'

Når problemet er formulert, kan det løses ved å bruke en rekke forskjellige teknikker der 'Grafisk løsning' og 'Simplex Method' er veldig populære.

Bruksområder for lineær programmering :

Økonomiske og forretningsmessige beslutninger omhandler ofte tildeling av knappe ressurser, for eksempel råstoff, penger, tid, rom, mennesker osv. Mellom konkurrerende prosjekter, enten for å maksimere noen mål, f.eks. Produksjon, avkastning på investeringsresultat, markedsandel, osv., eller minimere noen mål, f.eks. kostnader, avfall, forurensning, etc. LP kan brukes for å løse følgende praktiske industrielle problemer:

Jeg. Problemer med produktmiks :

Den optimale produktmiks som skal produseres med selskapets knappe arbeidskraft, anleggskapasitet, råvarer, økonomi, etc., kan analyseres og løses av LP La oss ta et næringsmiddelindustri som produserer tomatprodukter, for eksempel stuet tomat, tomatpuré, tomatsuppe, ketchup, tomatsaft, hermetiske tomater, etc.

Den kan produsere alle eller alle disse produktene samtidig, men det har begrenset tilførsel av tomater, tid / arbeidskraft, sukker, etc.

Hvert produkt har forskjellig gevinstbidrag, og det blir derfor et problem for ledelsen å bestemme hvor mye av hvert produkt som skal produseres. Videre kan ledelsen være interessert i å vite hvor mye de kan betale for ekstra enheter av faktorene som er begrenset i tilbudet. Disse spørsmålene kan besvares ved å bruke LP-teknikken.

ii. Kostholdsproblemer :

Dyrefôr produseres ved å blande et antall ingredienser som hver inneholder forskjellige proporsjoner protein, vitaminer, mineraler, etc. Dyrefôrene som produseres, må oppfylle visse ernæringsnivåer som er spesifisert av regjeringen, til den laveste kostnaden.

Produsentene vil kanskje vite økningen i kostnadene når ernæringsnivået til fôret økes. Dette problemet er også forbundet med farmasøytisk industri, gjødsel, plenfrø og kjæledyrfôrindustri. LP er et svar på slike problemer.

iii. Tildeling av annonseringsbudsjett :

Et firma har begrensede midler til å annonsere budsjettfordeling, for eksempel TV, radio, aviser, magasiner, regningstider, neonannonser, etc., og det vil gjerne vite hvor mye penger som skal tildeles hvilket medium for å få maksimal utbytte. TV-reklame kan igjen deles som dag- eller kveldsshow, avhengig av type publikum. Problemet med tildelingsmidler kan løses av LP

iv. Prosessvalg :

Dette problemet ligner på diettproblemer. Den omhandler produkt som kan produseres ved å bruke en (eller flere) av flere prosesser, som hver involverer forskjellige proporsjoner av forskjellige innganger. Et firma ønsker å produsere produktet ved å kombinere to eller flere prosesser og innganger på en slik måte at produksjonskostnadene minimeres. LP kan foreslå et svar på slike problemer.

v. Distribusjonsproblemer :

Mange firmaer har to eller flere anlegg der et bestemt produkt blir produsert og flere lagre på forskjellige steder for lagring av produktene før de sendes til forskjellige utsalgssteder.

Distribusjonskostnadene varierer også for forskjellige ruter som brukes fra produksjonsanlegg til lager og til salgssted. Ledelsen må bestemme leveringsoppdragene, det vil si hvor mange enheter som skal gå fra hvert salgssted, med et minimalt syn på fraktkostnader. Slike problemer kan løses ved transport og LP-teknikker.

vi. Problemer med oljebehandling og transport :

Store petroleumsfirmaer mottar råolje fra forskjellige kilder som de transporterer til flere raffinerier der forskjellige produkter produseres i fellesskap i krakkingsprosessen. LP brukes til å finne ut den optimale produktblandingen, den beste metoden for tildeling av råolje fra forskjellige kilder til de forskjellige raffineriene og transport av produkter til salgssteder. Dermed er LP mye brukt i petroleumsindustrien.

vii. Problemer med personaloppdrag :

Disse problemene ligner på distribusjonsproblemer. Et regnskapsfirma vil gjerne finne ut den beste metoden for å tildele revisjonspersonell til forskjellige revisjonsaktiviteter innenfor revisjonskontorets begrensninger, og samtidig oppfylle de faglige og økonomiske målene for kontorene. LP og tildelingsteknikker kan brukes til å løse slike problemer.

viii. Langsiktig kapasitetsplanlegging for elektriske verktøy :

Gode ​​planleggingsmodeller for lang rekkevidde er nødvendige for energirelaterte kompliserte problemer. Forespørsler om fremtidige år og informasjon om drifts- og investeringskostnader bør innarbeides i slike modeller. John R. McNamara utviklet en slik kapasitetsplanleggingsmodell for elektriske verktøy basert på LP for å minimere kostnadene for å tilfredsstille anslåtte krav.

Modellen er enkel, brukerorientert, og kan brukes til å løse problemer raskt. I tillegg kan disse LP brukes på forskjellige andre beslutningsområder.

Antagelser om den lineære programmeringsmodellen :

En LP-modell er basert på følgende forutsetninger.

1. Det må være et mål som et firma ønsker å maksimere eller minimere. Den objektive funksjonen (algebraisk) må være lineær. Flere mål kan også innarbeides i analysen.

2. Det må være alternativer tilgjengelig da det ikke kreves noen avgjørelse når et firma blir stilt overfor et enkelt handlingsforløp, f.eks. Hvis et produkt bare kan produseres etter en prosess, kreves ingen beslutning.

3. Den lineære objektive funksjonen må optimaliseres underlagt strukturelle begrensninger, f.eks. Materialer, tid, penger osv.: (Ressurser), anleggskapasitet, kontraktsmessige avtaler, juridiske hensyn, markedsføringskvoter, etc. Disse begrensningene kan uttrykkes algebraisk, enten som lineære ulikheter eller, lineære ligninger. I likhet med den objektive funksjonen, må begrensningene også være lineære funksjoner.

4. Variabler tar ikke negative verdier, og derfor er dette kjent som ikke-negativitetsbegrensning, dvs. verdien av beslutningsvariablene vil være enten null eller positiv.

Formulering av det lineære programmeringsproblemet :

La oss nå vurdere et produktmiksproblem. Et firma produserer to typer bokser, Type A og Type B. Behandlingstiden i minutter med sveising, pressing og plating på disse boksene er gitt nedenfor. Kapasiteten til disse avdelingene og bidragene til disse boksene er også gitt.

Hvor mange av A- og B-boksene skal produseres for å få et maksimalt bidrag?

Prosessen med å formulere LP-problemer innebærer transformasjon av den beskrivende informasjonen om situasjonene til matematiske utsagn. Følgende eksempel illustrerer poenget.

Oppgave 1:

La x 1 = antall type A-bokser, x 2 = antall type B-bokser. Den objektive funksjonen blir maksimalisering av Z = 30x 1 + 20x 2 der Z representerer fortjeneste og 30 og 20 er bidraget fra henholdsvis Type A og type B-bokser.

Det neste trinnet i formulering av et problem er å spesifisere begrensningene. Som x 1 og x 2 tar begge 3 minutter. for sveisedrift og totalt tilgjengelige minutter. i sveise avdeling er 60 minutter., vil kontrastligningen være som følger:

3x 1 + 3x 2 ≤ 60 (sveiseavdeling)

dvs. den totale min. kreves for å produsere x 1 og

x 2 bokser skal være mindre enn eller lik 60 minutter.

Tilsvarende er andre begrensningslikninger:

Hvis det bare er to variabler, kan problemet løses ved en enkel grafisk metode. Der mer enn to variabler er involvert, bruker vi 'Simplex Method'.

Grafisk løsning (maksimering) :

La oss løse det samme problemet grafisk. Her er bare to beslutningsvariabler, dvs. x 1 og x 2 involvert. Disse variablene er plottet langs x-aksen (horisontal) og y-aksen (vertikal).

For å plotte begrensningene på en graf, uttrykkes disse i form av følgende ligninger:

3x 1 + 3x 2 = 60 (1)

6x 1 + 2x 2 = 60 (2)

8x 1 = 60 (3)

Nå er OABCD i fig. 5.1 det konvekse området og punktene i O, A, B, C, D kalles de gjennomførbare løsningene på LP-problemet. Det er en grunnleggende teorem om LP som sier at den objektive funksjonen er optimalisert på et av hjørnepunktene, dvs. O, A, B, C, D. For maksimal fortjeneste er det bare disse hjørnepunktene, også kalt grunnleggende gjennomførbare løsninger, som skal evalueres.

Poengene kan også hentes direkte fra grafen.

Her Z = Rs. 450 (maks. Ved B når x 1 = 5 og x 2 = 15).

En alternativ metode for å oppnå den optimale basiske gjennomførbare løsningen er vist på fig. (5.2), som er det samme som fig. (5.1) med flere stiplede iso-profit linjer, dvs. L 1 L 1, L 2 L 2, L 3 L 3, etc. En iso-profit linje er en grafisk fremstilling av alle mulige kombinasjoner av to produkter som gir det samme profitt. Dette er parallelle linjer med samme helling. Det kan være uendelig mange slike linjer. Jo lenger en iso-profit-linje fra opprinnelsen er, desto større er fortjenesten.

Her velger vi et rimelig overskudd og tegner den objektive funksjonslinjen knyttet til denne fortjenesten. Deretter trekker vi iso-profit-linjen ut av løsningsområdet gradvis til den berører løsningsrommet bare på et ekstremt punkt. Nå kan vi finne den optimale fortjenesten og verdiene til beslutningsvariabelen fra graf.

Z = 30x 1 + 20x 2 (objektiv funksjon) er en lineær ligning av første grad. Hvis vi tar forskjellige verdier av Z, for eksempel 150, 300, 600 osv. Og plotter dem på grafen, vil linjene være parallelle.

L 1 L 1, L 2 L 2, L 3 L 3, er iso-profit linjene. L 3 L 3 berører løsningsområdet 0ABCD når som helst, dvs. B (5, 15).

. . . Z = Rs. 450 (optimal fortjeneste) og x 1 = 5 og x 2 = 15 (optimal produktmiks).

Grafisk løsning: Minimering :

La oss diskutere et minimeringsproblem.

Oppgave 2

En person trenger henholdsvis 10, 12 og 12 enheter kjemikalier A, B og C for hagen sin. Et flytende produkt inneholder henholdsvis 5, 2 og 1 A, B og C per krukke. Et tørt produkt inneholder 1, 2 og 4 enheter A, B og C per kartong. Hvis det flytende produktet selger for Rs. 3 per krukke og det tørre produktet selger for Rs. 2 per kartong, hvor mange av hver bør kjøpes for å minimere kostnadene og oppfylle kravene?

Løsning:

La x 1 = kjøp av flytende produkt og x 2 = kjøp av tørt produkt.

Den objektive funksjonen blir:

Minimer Z = 3x 1 + 2x 2 (1)

underlagt følgende begrensninger

For å plotte begrensningene på en graf, uttrykkes disse i form av følgende ligninger:

Her ligger løsningsområdet utenfor linjene (2) ', (3)' og (4) 'som vist ved det skyggelagte området i fig. (5.3).

Deretter flytter vi iso-profit-linjen mot opprinnelsen til det siste punktet på grensen til løsningsområdet er nådd, dvs. B (her).

Koordinatene til B kan også oppnås ved å løse ligningene (2) 'og (3)' som følger:

Nå er Z minimum på B = 3 X 1 + 2 X 5 = Rs. 13. Koordinatene til B kan også fås direkte fra grafen.

Simplex-metoden :

Komplekse LP-problemer kan ikke løses ved hjelp av grafiske løsninger. For slike problemer bruker vi simplex-metoden. La oss diskutere et enkelt maksimeringsproblem.

Oppgave 1

ABC Manufacturing Company kan lage to produkter P 1 og P 2 . Hvert produkt krever tid på en skjæremaskin og en etterbehandlingsmaskin.

Antall tilgjengelige klippetimer per uke er 390 og antall tilgjengelige ferdiggjøringstimer per uke er 810. Hvor mye av hvert produkt skal produseres for å oppnå maksimal fortjeneste for selskapet?

Løsning:

La

x 1 = Utgang av produktet P 1 ;

x 2 = Utgang av produktet P 2 ;

x 3 = Slack variabel, dvs. ubrukte skjæringstimer;

x 4 = Slakk variabel, dvs. ubrukte sluttid;

og

Z = Optimal fortjeneste.

Nå blir objektivfunksjonen: Maksimer Z = 6x 1 + 4x 2 + 0x 3 + 0x 4 underlagt begrensningene:

Ettersom alle verdiene for ( Cj - Zj ), dvs. indekserien til Pass II er enten null, eller, negativ, er den optimale løsningen oppnådd.

Produsentene må produsere henholdsvis 120 enheter per uke og 150 enheter per uke med P 1 og P 2 for å få maksimalt bidrag, dvs. Rs. 1320.

Beregninger :

Beregningsprosessen følger noen få trinn. Disse blir forklart nedenfor.

Starttabell :

Sett rhs for ligninger (2) og (3) i henholdsvis CC 'og DC' firkanter. Sett koeffisientene til x 1, x 2, x 3 og x 4 i ligning (2) i henholdsvis CD ', CE', CF 'og CG' firkanter. På samme måte sett koeffisienten x 1, x 2, x 3 og x 4 i ligning (3) i henholdsvis DD ', DE', DF 'og DG' firkanter. Sett de slakke variablene, x 3 og x 4, og deres bidrag 0 og 0, som vist i ligning (1) i henholdsvis CB ', DB', CA 'og DA' firkanter.

Z j radberegninger

EC 'kvadrat = 390 x 0 + 810 x = 0

ED 'kvadrat = 2 x 0 + 3 x 0 = 0 og så videre.

C j - Z j radberegninger

FD 'kvadrat = 6 - 0 = 6 (dvs. AD' - FD ')

FE 'square = 4 - 0 = 4 og så videre.

Pass I-beregninger:

Pass II-beregninger:

Ligner på Pass I

Indeksradene (dvs. C j - Z j ) i Pass II for slakkvariablene, dvs. X 3 og X 4, har en betydelig økonomisk tolkning. Deres absolutte verdier, dvs. 2 og 2/3 her, viser mengden endring i den optimale verdien av objektivfunksjonen som ville oppstå fra å slappe av den tilsvarende begrensningen med en enhet.

Denne verdien er kjent som 'skyggepris'. Derfor kan vi si at hvis en ekstra times kuttetid var tilgjengelig, kunne ABC-produksjonsbedriften øke overskuddet med Rs. 2, dvs. skyggeprisen for kuttetid er Rs. 2. Tilsvarende er skyggeprisen for etterbehandlingstid Rs. 2/3.

Ytterligere aspekter ved Simplex-metoden :

Big-M-metoden :

Så langt har vi diskutert om mindre enn eller lik type begrensninger. Men mange problemer har begrensninger av likhetstrekk, eller større enn eller lik ulikheter. La oss ta et problem og løse det.

Oppgave 1:

Maksimer gevinstfunksjonen og gi din kommentar:

Løsning :

Vi introduserer slakkvariabler x 4 og x 5 og kunstig variabel x 6, og vi har objektiv funksjon:

Når begrensningen hvis av ≥-typen, må vi trekke fra en slakk variabel for å få en likhetsbegrensning. For å generere en første grunnleggende mulig løsning med slike ≥ begrensninger, blir en "kunstig variabel" lagt til hver av disse begrensningene. I motsetning til slakkvariabler har kunstige variabler ingen økonomisk betydning og brukes bare for å etablere en innledende grunnleggende mulig løsning.

Siden denne variabelen ikke har noen økonomisk betydning, ønsker vi ikke at den skal vises i den endelige løsningsmiksen. Følgelig tildeler vi en veldig stor negativ verdi i objektivfunksjonen. I ligningen vår (1) er M et vilkårlig stort positivt tall.

Se nå tabell 5.2. Som, er alle verdiene for den endelige indeksen ( Cj - Zj ) raden enten negativ eller null, den optimale løsningen er nådd.

. . . x 1 = 900, x 2 = 1000, x 3 = 0 og Z (maksimum = 62.400.

Beregninger ligner på det forrige problemet.

Oppgave 2.

Bruk Big-M-metoden for å maksimere Z = 6x 1 + 4x 2 underlagt begrensninger

Gi to forskjellige løsninger, hvis løsningen ikke er unik.

Løsning:

Vi introduserer slakkvariabler x 3 og x 4, overskuddsvariabler x 5 og kunstig variabel x 6, og vi får begrensningene som

Og objektivfunksjonen er: Maksimer Z = 6x 1 + 4x 2 + 0x 3 + 0x 4 + 0x 5 - Mx 6

Få nå løsningen ved å eliminere big-M.

Minimeringsproblem :

Så lenge har vi diskutert om maksimaliseringsproblemer. Men i mange praktiske situasjoner må den objektive funksjonen minimeres. Her konverterer vi minimeringsproblemet til et maksimeringsproblem ved å bruke følgende uttrykk.

Minimer Z = - Maksimer (-Z).

Deretter maksimerer vi (-Z) som før og tar den negative verdien av maksimerer (-Z).

Oppgave 3.

Bruk Big-M-metoden for å minimere Z = 15x 1 + 12x 2 underlagt begrensningene:

Løsning:

Vi introduserer overskuddsvariabler x 3 og x 4 og kunstige variabler x 5 og x 6

Minimer Z = 15x 1 + 12x 2 + 0x 3 + 0x 4 + Mx 5 + Mx 6

underlagt begrensninger

Nå, minimer Z = - Maksimer (-Z). Her maksimerer du (-Z) = -15x 1 - 12x 2 - 0x 3 - 0x 4 - Mx 5 - Mx 6 .

Bruk deretter Big-M-metoden for å løse maksimere (-Z). Den optimale verdien av minimere Z = den negative verdien av maksimere (-Z).

Den generelle matematiske uttalelsen om LP-modellen :

Dual :

Hvert lineært programmeringsproblem har et andre komplementært LP-problem som kalles 'dual'. Det opprinnelige problemet kalles 'primal'. Løsningen av 'primal' kan oppnås ved å løse enten 'dual' eller 'primal'. Hvis 'primal' er et maksimeringsproblem, er 'dual' et minimeringsproblem og omvendt.

Forholdet mellom det primære og det dobbelte :

Oppgave 1.

Primal problem:

Maksimer z = 60x 1 + 80x 2,

I begge tilfeller er z (maks.) = Α (min), y 1 og y 2 de 'doble' variablene. Vi kan løse de 'doble' problemene ved hjelp av grafisk eller enkelksidig metode.

Følsomhetsanalyse :

Etter å ha fått den optimale løsningen av et LP-problem, kan det hende at vi studerer endringene i den optimale løsningen med endringer i parameterne til problemet.

Følgende endringer kan gjøres:

(1) Endre koeffisienter for objektivfunksjonen.

(2) Endre koeffektivitet av variablene på lhs av begrensningene.

(3) Endre tallene på rmene til begrensningene.

(4) Legg til / trekk fra nye variabler og

(5) Legg til / trekk fra begrensninger, etc.

Denne studien er signifikant ettersom den viser hvor sensitiv den aktuelle optimale løsningen på parametrene er. Ledelsen kan være villig til å kjenne variasjonen i parametrene som ikke påvirker den optimale løsningen som er undersøkt.

Denne studien av et LP-problem kalles "sensitivitetsanalyse". Det meste av analysen gjøres ved hjelp av datakoder. Vi skal kunne tolke utdataene fra slike koder, f.eks. LPGOGO-kode osv.

 

Legg Igjen Din Kommentar