LINEÆR PROGRAMMERING: HVAD ER DET TIL MODELLER, BEGRÆNSNINGER, APPLIKATIONER - MATEMATIK - 2025

Den lineære programmering er en matematisk metode, der bruges til at optimere (maksimere eller minimere efter behov) en funktion, hvis variabler er begrænset, så længe funktionen og begrænsningerne er lineært afhængige variabler.

Generelt modelleres funktionen, der skal optimeres, en praktisk situation, såsom fortjenesten for en producent, hvis input, arbejde eller maskiner er begrænset.

Figur 1. Lineær programmering er vidt brugt til at optimere overskuddet. Kilde: Piqsels.

Et af de enkleste tilfælde er den af ​​en lineær funktion, der skal maksimeres, som kun afhænger af to variabler, kaldet beslutningsvariabler. Det kan være af formen:

Z = k ₁ x + k ₂ y

Med k ₁ og k ₂ konstant. Denne funktion kaldes objektivfunktionen. Der er selvfølgelig situationer, der fortjener mere end to variabler til undersøgelse, idet de er mere komplekse:

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

Og begrænsningerne er også matematisk modelleret af et system af ligninger eller uligheder, lige lineære i x og y.

Sættet af løsninger i dette system kaldes gennemførlige løsninger eller gennemførlige punkter. Og blandt de gennemførlige punkter er der mindst et, der optimerer den objektive funktion.

Lineær programmering blev uafhængigt udviklet af den amerikanske fysiker og matematiker George Dantzig (1914-2005) og den russiske matematiker og økonom Leonid Kantorovich (1912-1986) kort efter 2. verdenskrig.

Den problemløsningsmetode, der kaldes simplex-metoden, er Dantzigs hjerneregn, der arbejdede for US Air Force, Berkeley University og Stanford University.

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

Lineære programmeringsmodeller

Elementerne, der er nødvendige for at etablere en lineær programmeringsmodel, der er egnet til en praktisk situation, er:

-Objektiv funktion

- Beslutningsvariabler

-Restrictions

I den objektive funktion definerer du, hvad du vil opnå. Antag f.eks., At du vil maksimere overskuddet ved fremstilling af visse produkter. Derefter etableres "profit" -funktionen i henhold til den pris, hvorpå produkterne sælges.

I matematiske termer kan denne funktion udtrykkes forkortet ved hjælp af summationsnotationen:

Z = ∑k _i x _i

I denne ligning, k _jeg er koefficienter og x _jeg er beslutningsprocesserne variabler.

Beslutningsvariablerne er elementerne i det system, hvis kontrol er haft, og deres værdier er positive reelle tal. I det foreslåede eksempel er beslutningsvariablerne mængden af ​​hvert produkt, der skal fremstilles for at opnå den maksimale fortjeneste.

Endelig har vi begrænsningerne, som er lineære ligninger eller uligheder i forhold til beslutningsvariablerne. De beskriver begrænsningerne til problemet, som er kendt og kan for eksempel være de mængder råmateriale, der er tilgængelig ved fremstillingen.

Typer af begrænsninger

Du kan have et antal M begrænsninger, der starter fra j = 1 til j = M. Matematisk er begrænsningerne af 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 begrænsning er af den lineære ligningstype og betyder, at værdien _Aj, som er kendt, skal respekteres.

De to resterende begrænsninger er lineære uligheder, og det betyder, at de kendte værdier _Bj og _Cj kan respekteres eller overskrides, når symbolet, der vises, er ≥ (større end eller lig med) eller respekteres eller ikke overskrides, hvis symbolet er ≤ (mindre end eller lig med).

Modeleksempel

Anvendelsesområderne er meget forskellige og spænder fra forretningsadministration til ernæring, men for at forstå metoden foreslås en simpel model for en praktisk situation med to variabler nedenfor.

En lokal konditori er kendt for to specialiteter: sort skovkage og sacripantin-kage.

I dets forberedelse kræver de æg og sukker. Til den sorte skov har du brug for 9 æg og 500 g sukker, mens til sacripantinen har du brug for 8 æg og 800 g sukker. De respektive salgspriser er $ 8 og $ 10.

Problemet er: Hvor mange kager af hver type skal bageriet lave for at maksimere overskuddet, vel vidende at det har 10 kilo sukker og 144 æg?

Beslutningsvariabler

Beslutningsvariablerne er "x" og "y", der tager reelle værdier:

-x: antallet af sort skovkager

-y: sacripantin kager.

Begrænsninger

Begrænsningerne er givet ved, at antallet af kager er en positiv mængde, og der er begrænsede mængder råmateriale til at tilberede dem.

Derfor, i matematisk form, har disse begrænsninger form:

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

Begrænsninger 1 og 2 udgør betingelsen for ikke-negativitet, der tidligere var udsat for, og alle de hævede uligheder er lineære. I begrænsningerne 3 og 4 er de værdier, der ikke må overskrides: 144 æg og 10 kg sukker.

Objektiv funktion

Endelig er den objektive funktion den fortjeneste, der opnås ved fremstilling af "x" -mængde sort skovkager plus "y" -mængde sacripantiner. Det er bygget ved at multiplicere prisen med den mængde kager, der er lavet og tilføje for hver type. Det er en lineær funktion, som vi vil kalde G (x, y):

G = 8x + 10y

Opløsningsmetoder

De forskellige opløsningsmetodologier inkluderer grafiske metoder, simplex-algoritmen og den indre punktmetode, for at nævne nogle få.

- Grafisk eller geometrisk metode

Når du har et tovariabelt problem som det i det foregående afsnit, bestemmer begrænsningerne et polygonalt område i xy-planet, kaldet det gennemførlige område eller levedygtighedsregion.

Figur 3. Det gennemførlige område, hvor løsningen af ​​optimeringsproblemet findes. Kilde: Wikimedia Commons.

Denne region er konstrueret ved hjælp af restriktionslinjer, som er linjerne opnået fra ulighederne i begrænsningerne, og fungerer kun med lighedstegnet.

For bageriet, der ønsker at optimere overskuddet, er begrænsningslinjerne:

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

Alle punkter i regionen omgivet af disse linjer er mulige løsninger, så der er uendeligt mange af dem. Undtagen i det tilfælde, hvor det gennemførlige område viser sig at være tomt, i hvilket tilfælde det stillede problem ikke har nogen løsning.

Heldigvis for det konditoriske problem er den gennemførlige region ikke tom, vi har det nedenfor.

Figur 4. Det gennemførlige område af wienerbrødsproblemet. Linjen med forstærkning 0 krydser oprindelsen. Kilde: F. Zapata med Geogebra.

Den optimale løsning, hvis den findes, findes ved hjælp af objektivfunktionen. For eksempel, når vi prøver at finde den maksimale fortjeneste G, har vi følgende linje, der kaldes iso-profit-linjen:

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

Med denne linje opnår vi alle par (x, y), der giver en given forstærkning G, så der er en familie af linjer i henhold til værdien af ​​G, men alle med den samme hældning -k ₁ / k ₂, så de er parallelle linjer.

Den optimale løsning

Nu kan det vises, at den optimale løsning af et lineært problem altid er et ekstremt punkt eller toppunkt i den gennemførlige region. Så:

Hvis linjen tættest på oprindelsen har et helt segment til fælles med det gennemførlige område, siges det, at der er uendelige løsninger. Dette tilfælde opstår, hvis iso-profit-linjens hældning er lig med en af ​​de andre linjer, der begrænser regionen.

For vores konditor er kandidathøjdepunkterne A, B og C.

- Dantzigs enkle metode

Den grafiske eller geometriske metode er anvendelig for to variabler. Det er dog mere kompliceret, når der er tre variabler, og umulig at bruge til et større antal variabler.

Når man håndterer problemer med mere end to variabler, anvendes simplex-metoden, der består af en række algoritmer for at optimere de objektive funktioner. Matrixer og enkel aritmetik bruges ofte til at udføre beregningerne.

Simplex-metoden begynder med at vælge en gennemførlig løsning og kontrollere, om den er optimal. Hvis det er tilfældet, har vi allerede løst problemet, men hvis det ikke er det, fortsætter vi hen imod en løsning, der er tættere på optimering. Hvis løsningen findes, finder algoritmen den i nogle få forsøg.

Applikationer

Lineær og ikke-lineær programmering anvendes på mange felter for at tage de bedste beslutninger med hensyn til at reducere omkostninger og øge overskuddet, som ikke altid er monetært, da de f.eks. Kan måles i tid, hvis du vil minimere den nødvendige tid. at udføre en række operationer.

Her er nogle felter:

-I markedsføring bruges det til at finde den bedste kombination af medier (sociale netværk, tv, presse og andre) til at annoncere et bestemt produkt.

-For tildelingen af ​​tilstrækkelige opgaver til personalet i en virksomhed eller fabrik eller planlægning til dem.

-I udvælgelsen af ​​den mest næringsrige mad og til de laveste omkostninger i husdyr- og fjerkræsektoren.

Løst øvelser

- Øvelse 1

Løs grafisk den lineære programmeringsmodel, der er rejst i de foregående afsnit.

Løsning

Det er nødvendigt at tegne værdisættet, der er bestemt af systemet med begrænsninger, der er specificeret i problemet:

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

Området, der er givet ved uligheder 1 og 2, svarer til den første kvadrant på det kartesiske plan. Med hensyn til uligheder 3 og 4 begynder vi med at finde begrænsningslinjerne:

9x + 8y = 144

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

Den gennemførlige region er et firsidet, hvis vertikale punkter er A, B, C og D.

Minimumsgevinsten er 0, derfor er linjen 8x + 10y = 0 den nedre grænse, og iso-profitlinjerne har hældning -8/10 = - 0,8.

Denne værdi er forskellig fra skråningerne for de andre restriktionslinjer, og da det gennemførlige område er afgrænset, eksisterer den unikke løsning.

Figur 5. Grafisk løsning af øvelse 1, der viser det gennemførlige område og opløsningspunktet C ved en af ​​toppunktene i nævnte område. Kilde: F. Zapata.

Denne løsning svarer til en hældningslinje -0,8, der passerer gennem et af punkterne A, B eller C, hvis koordinater er:

A (11; 5,625)

B (0; 12,5)

C (16, 0)

Optimal løsning

Vi beregner værdien af ​​G for hvert af disse punkter:

- (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øjeste fortjeneste findes ved fremstilling af 11 sortskovkager og 5.625 sacripantinkager. Denne løsning stemmer overens med den, der findes gennem softwaren.

- Øvelse 2

Bekræft resultatet af den foregående øvelse ved hjælp af Solver-funktionen, der er tilgængelig i de fleste regneark, f.eks. Excel eller LibreOffice Calc, der indeholder Simplex-algoritmen til optimering i lineær programmering.

Løsning

Figur 6. Detalje om løsningen fra øvelse 1 gennem Libre Office Calc-regnearket. Kilde: F. Zapata.

Figur 7. Detalje om løsningen fra øvelse 1 gennem Libre Office Calc-regnearket. Kilde: F. Zapata.

Referencer

1. Strålende. Lineær programmering. Gendannet fra: brilliant.org.
2. Eppen, G. 2000. Operations Research in Administrative Science. 5.. Edition. Prentice Hall.
3. Haeussler, E. 1992. Matematik til ledelse og økonomi. 2nd. Edition. Grupo Redaktion Iberoamericana.
4. Hiru.eus. Lineær programmering. Gendannes fra: hiru.eus.
5. Wikipedia. Lineær programmering. Gendannes fra: es. wikipedia.org.