LINJÄR PROGRAMMERING: VAD ÄR DET FÖR, MODELLER, BEGRÄNSNINGAR, APPLIKATIONER - MATTE - 2026

Den linjära programmeringen är en matematisk metod som används för att optimera (maximera eller minimera vid behov) en funktion vars variabler är begränsade, så länge funktionen och begränsningarna är linjärt beroende variabler.

I allmänhet modellerar den funktion som ska optimeras en praktisk situation, till exempel vinsten för en tillverkare vars insatser, arbetskraft eller maskiner är begränsade.

Figur 1. Linjär programmering används ofta för att optimera vinsten. Källa: Piqsels.

Ett av de enklaste fallen är den för en linjär funktion som ska maximeras, som bara beror på två variabler, kallade beslutsvariabler. Det kan vara av formen:

Z = k ₁ x + k ₂ y

Med k ₁ och k ₂ konstant. Denna funktion kallas objektiv funktion. Naturligtvis finns det situationer som förtjänar mer än två variabler för studier, eftersom de är mer komplexa:

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

Och begränsningarna är också matematiskt modellerade av ett system med ekvationer eller ojämlikheter, lika linjära i x och y.

Uppsättningen av lösningar i detta system kallas genomförbara lösningar eller genomförbara punkter. Och bland de möjliga punkterna finns det åtminstone en, som optimerar objektivfunktionen.

Linjär programmering utvecklades oberoende av den amerikanska fysikern och matematikern George Dantzig (1914-2005) och den ryska matematikern och ekonomen Leonid Kantorovich (1912-1986) strax efter andra världskriget.

Den problemlösningsmetod som kallas simplex-metoden är Dantzigs hjärnsköld, som arbetade för US Air Force, Berkeley University och Stanford University.

Bild 2. Matematiker George Dantzig (vänster) och Leonid Kantorovich (höger). Källa: F. Zapata.

Linjära programmeringsmodeller

Elementen som krävs för att upprätta en linjär programmeringsmodell, lämplig för en praktisk situation, är:

-Objektiv funktion

-Beslutvariabler

-Restrictions

I objektivfunktionen definierar du vad du vill uppnå. Anta till exempel att du vill maximera vinsterna från tillverkningen av vissa produkter. Sedan fastställs "vinst" -funktionen, beroende på det pris till vilket produkterna säljs.

I matematiska termer kan denna funktion uttryckas förkortad med summanotation:

Z = ∑k _i x _i

I denna ekvation, k _jag är koefficienter och x _jag är beslutsvariabler.

Beslutsvariablerna är elementen i systemet vars kontroll har haft och deras värden är positiva verkliga siffror. I det föreslagna exemplet är beslutsvariablerna kvantiteten för varje produkt som ska tillverkas för att få maximal vinst.

Slutligen har vi begränsningarna, som är linjära ekvationer eller ojämlikheter när det gäller beslutsvariablerna. De beskriver begränsningarna i problemet, som är kända och kan till exempel vara mängden råmaterial som är tillgängligt vid tillverkningen.

Typer av begränsningar

Du kan ha ett antal M begränsningar, från j = 1 till j = M. Matematiskt är begränsningarna 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örsta begränsningen är av den linjära ekvationstypen och betyder att värdet _Aj , som är känt, måste respekteras.

De två återstående restriktionerna är linjära ojämlikheter och det betyder att de kända värdena _Bj och _Cj kan respekteras eller överskridas, när symbolen som visas är ≥ (större än eller lika med) eller respekteras eller inte överskrids, om symbolen är ≤ (mindre än eller lika med).

Modellexempel

Tillämpningsområdena är mycket olika, från affärsadministration till näring, men för att förstå metoden föreslås en enkel modell av en praktisk situation med två variabler nedan.

En lokal konditori är känd för två specialiteter: svartskogstårta och sacripantinkaka.

I beredningen kräver de ägg och socker. För svartskogen behöver du 9 ägg och 500 g socker, medan för sacripantinen behöver du 8 ägg och 800 g socker. De respektive försäljningspriserna är $ 8 och $ 10.

Problemet är: Hur många kakor av varje typ måste bageriet göra för att maximera sin vinst, medvetande om att det har 10 kilo socker och 144 ägg?

Beslutsvariabler

Beslutsvariablerna är "x" och "y", som tar verkliga värden:

-x: antalet svarta skogskakor

-y: kakor av sacripantintyp.

begränsningar

Begränsningarna ges av det faktum att antalet kakor är en positiv mängd och det finns begränsade mängder råmaterial för att förbereda dem.

Därför, i matematisk form, har dessa begränsningar formen:

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

Begränsningar 1 och 2 utgör villkoret för att tidigare inte utsatts för negativitet och alla ojämlikheter som uppstår är linjära. I begränsningar 3 och 4 finns värden som inte får överskridas: 144 ägg och 10 kg socker.

Objektiv funktion

Slutligen är den objektiva funktionen den vinst som erhålls vid tillverkning av "x" mängd svarta skogskakor plus "y" kvantitet sacripantines. Det byggs genom att multiplicera priset med mängden kakor som gjorts och lägga till för varje typ. Det är en linjär funktion som vi kommer att kalla G (x, y):

G = 8x + 10 år

Lösningsmetoder

De olika lösningsmetoderna inkluderar grafiska metoder, simplexalgoritmen och interiörpunktsmetoden, för att nämna några.

- Grafisk eller geometrisk metod

När du har ett tvåvariabelt problem som det i föregående avsnitt bestämmer begränsningarna ett polygonalt område i xy-planet, som kallas det genomförbara området eller livskraftsområdet.

Figur 3. Det genomförbara området, där lösningen av optimeringsproblemet hittas. Källa: Wikimedia Commons.

Denna region är konstruerad med hjälp av restriktionslinjerna, som är linjerna erhållna från ojämlikheterna i restriktionerna, och arbetar endast med jämställdhetstecknet.

När det gäller bageriet som vill optimera vinsten är begränsningslinjerna:

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

Alla punkter i området som omges av dessa linjer är möjliga lösningar, så det finns oändligt många av dem. Förutom i det fall det genomförbara området visar sig vara tomt, i vilket fall det problem som uppstår har ingen lösning.

Lyckligtvis för det bakverksproblemet är den genomförbara regionen inte tom, vi har det nedan.

Bild 4. Det genomförbara området för bakelseproblemet. Linjen med förstärkning 0 korsar ursprunget. Källa: F. Zapata med Geogebra.

Den optimala lösningen, om den finns, hittas med hjälp av objektivfunktionen. Till exempel när vi försöker hitta den maximala vinsten G har vi följande rad, som kallas iso-vinstlinjen:

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

Med denna linje erhåller vi alla par (x, y) som ger en given förstärkning G, så det finns en familj av linjer enligt det värde på G, men alla med samma lutning -k ₁ / k ₂ , så att de är parallella linjer.

Den optimala lösningen

Nu kan det visas att den optimala lösningen av ett linjärt problem alltid är en extrem punkt eller topp i det genomförbara området. Så:

Om linjen närmast ursprunget har ett helt segment gemensamt med den genomförbara regionen sägs det att det finns oändliga lösningar. Detta fall inträffar om lutningen för iso-vinstlinjen är lika med den för någon av de andra linjerna som begränsar regionen.

För våra konditorier är kandidatpunkterna A, B och C.

- Dantzigs enkla metod

Den grafiska eller geometriska metoden är tillämplig för två variabler. Det är emellertid mer komplicerat när det finns tre variabler och omöjligt att använda för ett större antal variabler.

När man hanterar problem med mer än två variabler används simplexmetoden, som består av en serie algoritmer för att optimera de objektiva funktionerna. Matriser och enkel aritmetik används ofta för att utföra beräkningarna.

Simplexmetoden börjar med att välja en genomförbar lösning och kontrollera om den är optimal. Om det är så har vi redan löst problemet, men om det inte är det, fortsätter vi mot en lösning som är närmare optimeringen. Om lösningen finns hittar algoritmen den i några försök.

tillämpningar

Linjär och icke-linjär programmering används på många områden för att fatta de bästa besluten när det gäller att sänka kostnaderna och öka vinsterna, som inte alltid är monetära, eftersom de kan mätas i tid, till exempel om du vill minimera den nödvändiga tiden. att genomföra en serie operationer.

Här är några fält:

-Marknadsföring används för att hitta den bästa kombinationen av media (sociala nätverk, TV, press och andra) för att marknadsföra en viss produkt.

-För tilldelning av adekvata uppgifter till personal i ett företag eller fabrik eller scheman till dem.

-I urvalet av den mest näringsrika maten och till lägsta kostnad i boskap- och fjäderfäindustrin.

Lösta övningar

- Övning 1

Lös grafiskt den linjära programmeringsmodellen som tas upp i de föregående avsnitten.

Lösning

Det är nödvändigt att kartlägga den uppsättning värden som bestäms av systemet med begränsningar som anges i problemet:

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

Området som ges av ojämlikheterna 1 och 2 motsvarar den första kvadranten på det kartesiska planet. När det gäller ojämlikhet 3 och 4 börjar vi med att hitta begränsningslinjerna:

9x + 8y = 144

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

Den genomförbara regionen är en fyrkantig vars vertikaler är punkterna A, B, C och D.

Minsta vinst är 0, därför är linjen 8x + 10y = 0 den nedre gränsen och iso-vinstlinjerna har lutning -8/10 = - 0,8.

Detta värde skiljer sig från sluttningarna för de andra begränsningslinjerna och eftersom det genomförbara området är begränsat finns den unika lösningen.

Figur 5. Grafisk lösning av övning 1, som visar det genomförbara området och lösningspunkten C vid en av topparna i nämnda region. Källa: F. Zapata.

Denna lösning motsvarar en lutningslinje -0,8 som passerar genom någon av punkterna A, B eller C, vars koordinater är:

A (11; 5,625)

B (0; 12,5)

C (16, 0)

Optimal lösning

Vi beräknar värdet på G för var och en av dessa 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ögsta vinsten hittas som tillverkar 11 svarta skogskakor och 5 625 sacripantinkakor. Denna lösning överensstämmer med den som hittas via programvaran.

- Övning 2

Verifiera resultatet av den föregående övningen genom att använda Solver-funktionen som finns i de flesta kalkylark, t.ex. Excel eller LibreOffice Calc, som innehåller Simplex-algoritmen för optimering i linjär programmering.

Lösning

Bild 6. Detalj av lösningen från övning 1 till Libre Office Calc-kalkylbladet. Källa: F. Zapata.

Bild 7. Detalj av lösningen från övning 1 till Libre Office Calc-kalkylbladet. Källa: F. Zapata.

referenser

1. Lysande. Linjär programmering. Återställd från: brilliant.org.
2. Eppen, G. 2000. Operations Research in Administrative Science. 5:e. Utgåva. Prentice Hall.
3. Haeussler, E. 1992. Matematik för ledning och ekonomi. 2:a. Utgåva. Grupo Redaktion Iberoamericana.
4. Hiru.eus. Linjär programmering. Återställd från: hiru.eus.
5. Wikipedia. Linjär programmering. Återställd från: es. wikipedia.org.