LINEÆR PROGRAMMERING: HVA ER DET FOR MODELLER, BEGRENSNINGER, APPLIKASJONER - MATTE - 2026

Den lineære programmeringen er en matematisk metode som brukes for å optimalisere (maksimere eller minimere etter behov) en funksjon hvis variabler er begrenset, så lenge funksjonen og begrensningene er lineært avhengige variabler.

Generelt modellerer funksjonen som skal optimaliseres en praktisk situasjon, for eksempel fortjenesten til en produsent hvis inngang, arbeidskraft eller maskiner er begrenset.

Figur 1. Lineær programmering er mye brukt for å optimalisere fortjenesten. Kilde: Piqsels.

Et av de enkleste tilfellene er den for en lineær funksjon som skal maksimeres, som bare avhenger av to variabler, kalt beslutningsvariabler. Det kan være av formen:

Z = k ₁ x + k ₂ y

Med k ₁ og k ₂ konstant. Denne funksjonen er kjent som objektivfunksjonen. Selvfølgelig er det situasjoner som fortjener mer enn to variabler for studier, og er mer sammensatte:

Z = k ₁ x ₁ + k ₂ x ₂ + k ₃ x ₃ +….

Og begrensningene er også matematisk modellert av et system med ligninger eller ulikheter, like lineære i x og y.

Settet med løsninger i dette systemet kalles gjennomførbare løsninger eller gjennomførbare punkter. Og blant gjennomførbare punkter er det minst ett, som optimaliserer den objektive funksjonen.

Lineær programmering ble uavhengig utviklet av den amerikanske fysikeren og matematikeren George Dantzig (1914-2005) og den russiske matematikeren og økonomen Leonid Kantorovich (1912-1986) like etter andre verdenskrig.

Problemløsningsmetoden kjent som simplex-metoden er hjernen til Dantzig, som jobbet for det amerikanske flyvåpenet, Berkeley University og Stanford University.

Figur 2. Matematikere George Dantzig (til venstre) og Leonid Kantorovich (til høyre). Kilde: F. Zapata.

Lineære programmeringsmodeller

Elementene som er nødvendige for å etablere en lineær programmeringsmodell, egnet for en praktisk situasjon, er:

-Objektiv funksjon

-Beslutningsvariabler

-Begrensninger

I den objektive funksjonen definerer du hva du vil oppnå. Anta for eksempel at du vil maksimere overskuddet fra produksjonen av visse produkter. Deretter etableres "profit" -funksjonen, i henhold til prisen som produktene selges til.

I matematiske termer kan denne funksjonen uttrykkes forkortet ved bruk av summasjonsnotasjonen:

Z = ∑k _i x _i

I denne ligningen er k _i koeffisienter og x _i er beslutningsvariablene.

Avgjørelsesvariablene er elementene i systemet som kontrollen har hatt, og verdiene er positive reelle tall. I det foreslåtte eksemplet er beslutningsvariablene mengden av hvert produkt som skal produseres for å oppnå maksimal fortjeneste.

Til slutt har vi begrensningene, som er lineære ligninger eller ulikheter i forhold til beslutningsvariablene. De beskriver begrensningene i problemet, som er kjent og kan være for eksempel mengden råmateriale som er tilgjengelig i fremstillingen.

Typer begrensninger

Du kan ha et antall M begrensninger, fra j = 1 til j = M. Matematisk sett er begrensningene av tre typer:

1. A _j = ∑ a _ij . x _i
2. B _j ≥ ∑ b _ij . x _i
3. C _j ≤ ∑ c _ij . x _i

Den første begrensningen er av den lineære ligningstypen og betyr at verdien _Aj , som er kjent, må respekteres.

De to gjenværende restriksjonene er lineære ulikheter, og det betyr at de kjente verdiene _Bj og _Cj kan respekteres eller overskrides, når symbolet som vises er ≥ (større enn eller lik) eller respekteres eller ikke overskrides, hvis symbolet er ≤ (mindre enn eller lik).

Modelleksempel

Bruksområdene er svært forskjellige, alt fra forretningsadministrasjon til ernæring, men for å forstå metoden foreslås en enkel modell av en praktisk situasjon med to variabler nedenfor.

Et lokalt konditori er kjent for to spesialiteter: svartskogkake og sakripantinkake.

I forberedelsen krever de egg og sukker. For svarteskogen trenger du 9 egg og 500 g sukker, mens for sacripantinen trenger du 8 egg og 800 g sukker. De respektive salgsprisene er $ 8 og $ 10.

Problemet er: Hvor mange kaker av hver type må bakeriet lage for å maksimere overskuddet, vel vitende om at det har 10 kilo sukker og 144 egg?

Avgjørelsesvariabler

Avgjørelsesvariablene er "x" og "y", som tar reelle verdier:

-x: antall svarteskogkaker

-y: sacripantine kaker.

Begrensninger

Begrensningene gis ved at antall kaker er en positiv mengde og det er begrensede mengder råstoff for å tilberede dem.

Derfor, i matematisk form, tar disse begrensningene formen:

1. x ≥ 0
2. og ≥0
3. 9x + 8y ≤ 144
4. 0,5 x + 0,8 y <10

Begrensninger 1 og 2 utgjør tilstanden for ikke-negativitet tidligere utsatt, og alle ulikhetene som er reist er lineære. I begrensningene 3 og 4 er verdiene som ikke må overskrides: 144 egg og 10 kg sukker.

Objektiv funksjon

Endelig er den objektive funksjonen overskuddet som er oppnådd ved produksjon av "x" mengde svarteskogkaker pluss "y" mengde sacripantines. Det er bygget ved å multiplisere prisen med mengden kaker som er laget og legge til for hver type. Det er en lineær funksjon som vi vil kalle G (x, y):

G = 8x + 10y

Løsningsmetoder

De forskjellige løsningsmetodologiene inkluderer grafiske metoder, simplex-algoritmen og interiørpunktmetoden, for å nevne noen.

- Grafisk eller geometrisk metode

Når du har et tovariabelt problem som det i forrige seksjon, bestemmer begrensningene et polygonalt område i xy-planet, kalt det gjennomførbare området eller levedyktighetsområdet.

Figur 3. Det gjennomførbare området, der løsningen på optimaliseringsproblemet er funnet. Kilde: Wikimedia Commons.

Denne regionen er konstruert ved å bruke begrensningslinjene, som er linjene hentet fra ulikhetene i begrensningene, og fungerer bare med likhetstegnet.

Når det gjelder bakeriet som ønsker å optimalisere fortjenesten, er begrensningslinjene:

1. x = 0
2. y = 0
3. 9x + 8y = 144
4. 0,5 x + 0,8 y = 10

Alle punkter i regionen som er omsluttet av disse linjene er mulige løsninger, så det er uendelig mange av dem. Bortsett fra i tilfelle hvor det gjennomførbare området viser seg å være tomt, i hvilket tilfelle problemet ikke har noen løsning.

Heldigvis, for konditorproblemet er den gjennomførbare regionen ikke tom, vi har det nedenfor.

Figur 4. Det gjennomførbare området for kringleproblemet. Linjen med forsterkning 0 krysser opprinnelsen. Kilde: F. Zapata med Geogebra.

Den optimale løsningen, hvis den finnes, blir funnet ved hjelp av objektivfunksjonen. For eksempel når vi prøver å finne maksimal fortjeneste G, har vi følgende linje, som kalles iso-profit-linjen:

G = k ₁ x + k ₂ y → y = -k ₁ x / k ₂ + G / k ₂

Med denne linjen oppnår vi alle parene (x, y) som gir en gitt forsterkning G, så det er en familie av linjer i henhold til verdien av G, men alle med den samme skråningen -k ₁ / k ₂ , så de er parallelle linjer.

Den optimale løsningen

Nå kan det vises at den optimale løsningen av et lineært problem alltid er et ekstremt punkt eller toppunkt i det gjennomførbare området. Så:

Hvis linjen nærmest opprinnelsen har et helt segment til felles med den gjennomførbare regionen, sies det at det finnes uendelige løsninger. Denne saken oppstår hvis hellingen av iso-profit-linjen er lik den for noen av de andre linjene som begrenser regionen.

For bakverket vårt er kandidatens toppunkt A, B og C.

- Dantzigs enkle metode

Den grafiske eller geometriske metoden kan brukes for to variabler. Imidlertid er det mer komplisert når det er tre variabler, og umulig å bruke for et større antall variabler.

Når du håndterer problemer med mer enn to variabler, brukes simplex-metoden, som består av en serie algoritmer for å optimalisere de objektive funksjonene. Matriser og enkel aritmetikk brukes ofte til å utføre beregningene.

Simplex-metoden begynner med å velge en mulig løsning og sjekke om den er optimal. Hvis det er det, har vi allerede løst problemet, men hvis det ikke er det, fortsetter vi mot en løsning nærmere optimalisering. Hvis løsningen eksisterer, finner algoritmen den i noen få forsøk.

applikasjoner

Lineær og ikke-lineær programmering brukes på mange felt for å ta de beste beslutningene når det gjelder å redusere kostnader og øke fortjenesten, som ikke alltid er monetære, siden de kan måles i tide, for eksempel hvis du vil minimere den nødvendige tiden. å utføre en serie operasjoner.

Her er noen felt:

-I markedsføring brukes det til å finne den beste kombinasjonen av medier (sosiale nettverk, TV, presse og andre) for å annonsere et bestemt produkt.

-For tildeling av tilstrekkelige oppgaver til personalet i et selskap eller en fabrikk eller planlegger dem.

-I utvalg av den mest næringsrike maten og til lavest mulig pris i husdyr- og fjørfebransjen.

Løste øvelser

- Oppgave 1

Løs grafisk den lineære programmeringsmodellen hevet i de foregående seksjoner.

Løsning

Det er nødvendig å tegne verdisettet som er bestemt av systemet med begrensninger som er spesifisert i problemet:

1. x ≥ 0
2. og ≥0
3. 9x + 8y ≤ 144
4. 0,5 x + 0,8 y <10

Området gitt av ulikhetene 1 og 2 tilsvarer den første kvadranten på det kartesiske planet. Når det gjelder ulikhetene 3 og 4, begynner vi med å finne begrensningslinjene:

9x + 8y = 144

0,5 x + 0,8 y = 10 → 5x + 8 år = 100

Den gjennomførbare regionen er en firkantet side med toppunktene A, B, C og D.

Minste fortjeneste er 0, derfor er linjen 8x + 10y = 0 den nedre grensen og iso-profit-linjene har helning -8/10 = - 0,8.

Denne verdien er forskjellig fra skråningene til de andre begrensningslinjene, og siden det gjennomførbare området er avgrenset, eksisterer den unike løsningen.

Figur 5. Grafisk løsning av øvelse 1, som viser det gjennomførbare området og løsningen punkt C ved en av toppunktene i nevnte område. Kilde: F. Zapata.

Denne løsningen tilsvarer en skråningslinje -0,8 som går gjennom et av punktene A, B eller C, hvis koordinater er:

A (11; 5.625)

B (0; 12,5)

C (16, 0)

Optimal løsning

Vi beregner verdien av G for hvert av disse punktene:

- (11; 5,625): G _A = 8 x 11 + 10 x 5,625 = 144,25

- (0; 12,5): G _B = 8 x 0 + 10 x 12,5 = 125

- (16, 0): G _C = 8 x 16 + 10 x 0 = 128

Den høyeste fortjenesten er å produsere 11 svarteskogkaker og 5 625 sacripantinkaker. Denne løsningen stemmer overens med den som er funnet gjennom programvaren.

- Oppgave 2

Bekreft resultatet av forrige øvelse ved å bruke Solver-funksjonen som er tilgjengelig i de fleste regneark, for eksempel Excel eller LibreOffice Calc, som inneholder Simplex-algoritmen for optimalisering i lineær programmering.

Løsning

Figur 6. Detalj av løsningen fra oppgave 1 gjennom Libre Office Calc-regnearket. Kilde: F. Zapata.

Figur 7. Detalj av løsningen fra oppgave 1 gjennom Libre Office Calc-regnearket. Kilde: F. Zapata.

referanser

1. Strålende. Lineær programmering. Gjenopprettet fra: brilliant.org.
2. Eppen, G. 2000. Operations Research in Administrative Science. Femte. Edition. Prentice Hall.
3. Haeussler, E. 1992. Matematikk for ledelse og økonomi. Andre. Edition. Grupo Editorial Iberoamericana.
4. Hiru.eus. Lineær programmering. Gjenopprettet fra: hiru.eus.
5. Wikipedia. Lineær programmering. Gjenopprettet fra: es. wikipedia.org.