LINEAIRE PROGRAMMERING: WAAR IS HET VOOR, MODELLEN, BEPERKINGEN, TOEPASSINGEN - WISKUNDE - 2026

De lineaire programmering is een wiskundige methode die wordt gebruikt voor het optimaliseren (maximaliseren of minimaliseren geval) een functie waarvan de variabelen zijn beperkt, zo lang de functie en beperkingen lineair afhankelijke variabelen.

Over het algemeen modelleert de te optimaliseren functie een praktijksituatie, zoals de winst van een fabrikant wiens inputs, arbeidskrachten of machines beperkt zijn.

Figuur 1. Lineaire programmering wordt veel gebruikt om de winst te optimaliseren. Bron: Piqsels.

Een van de eenvoudigste gevallen is die van een lineaire functie die moet worden gemaximaliseerd, die alleen afhangt van twee variabelen, beslissingsvariabelen genaamd. Het kan de volgende vorm hebben:

Z = k ₁ X + k ₂ Y

Met k ₁ en k ₂ constant. Deze functie staat bekend als de objectieve functie. Natuurlijk zijn er situaties die meer dan twee variabelen verdienen om te studeren, omdat ze complexer zijn:

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

En de beperkingen worden ook wiskundig gemodelleerd door een systeem van vergelijkingen of ongelijkheden, even lineair in x en y.

De reeks oplossingen in dit systeem wordt haalbare oplossingen of haalbare punten genoemd. En onder de haalbare punten is er minstens één die de doelfunctie optimaliseert.

Lineaire programmering werd onafhankelijk ontwikkeld door de Amerikaanse natuurkundige en wiskundige George Dantzig (1914-2005) en de Russische wiskundige en econoom Leonid Kantorovich (1912-1986) kort na de Tweede Wereldoorlog.

De probleemoplossende methode die bekend staat als de simplex-methode is het geesteskind van Dantzig, die werkte voor de US Air Force, Berkeley University en Stanford University.

Figuur 2. Wiskundigen George Dantzig (links) en Leonid Kantorovich (rechts). Bron: F. Zapata.

Lineaire programmeermodellen

De elementen die nodig zijn om een ​​lineair programmeermodel op te stellen, geschikt voor een praktijksituatie, zijn:

-Objectieve functie

-Besluitvariabelen

-Beperkingen

In de doelfunctie definieer je wat je wilt bereiken. Stel dat u de winst uit de fabricage van bepaalde producten wilt maximaliseren. Vervolgens wordt de functie "winst" vastgesteld, afhankelijk van de prijs waartegen de producten worden verkocht.

In wiskundige termen kan deze functie worden afgekort met de sommatie-notatie:

Z = ∑k _ik X _ik

In deze vergelijking zijn k _i coëfficiënten en zijn x _i de beslissingsvariabelen.

De beslissingsvariabelen zijn de elementen van het systeem waarvan de controle bestaat en hun waarden zijn positieve reële getallen. In het voorgestelde voorbeeld zijn de beslissingsvariabelen de hoeveelheid van elk product dat moet worden vervaardigd om de maximale winst te behalen.

Ten slotte hebben we de beperkingen, die lineaire vergelijkingen of ongelijkheden zijn in termen van de beslissingsvariabelen. Ze beschrijven de beperkingen van het probleem, die bekend zijn en kunnen bijvoorbeeld de hoeveelheden grondstof zijn die bij de fabricage beschikbaar zijn.

Soorten beperkingen

U kunt een aantal M beperkingen hebben, beginnend bij j = 1 tot j = M. Wiskundig gezien zijn de beperkingen van drie soorten:

1. EEN _j = ∑ een _ij . x _ik
2. B _j ≥ ∑ b _ij . x _ik
3. C _j ≤ ∑ c _ij . x _ik

De eerste beperking is van het lineaire vergelijkingstype en betekent dat de waarde A _j , die bekend is, gerespecteerd moet worden.

De twee overige beperkingen zijn lineaire ongelijkheden en het betekent dat de bekende waarden B _j en C _j kunnen worden gerespecteerd of overschreden, wanneer het symbool dat verschijnt ≥ (groter dan of gelijk aan) of gerespecteerd of niet overschreden is, als het symbool ≤ is (minder dan of gelijk aan).

Model voorbeeld

De toepassingsgebieden zijn zeer divers, gaande van bedrijfskunde tot voeding, maar om de methode te begrijpen wordt hieronder een eenvoudig model van een praktijksituatie met twee variabelen voorgesteld.

Een lokale patisserie staat bekend om twee specialiteiten: zwarte woudcake en sacripantine cake.

Bij de bereiding hebben ze eieren en suiker nodig. Voor het Zwarte Woud heb je 9 eieren en 500 g suiker nodig, terwijl je voor de sacripantine 8 eieren en 800 g suiker nodig hebt. De respectievelijke verkoopprijzen zijn $ 8 en $ 10.

Het probleem is: hoeveel cakes van elk type moet de bakkerij maken om zijn winst te maximaliseren, wetende dat hij 10 kilo suiker en 144 eieren heeft?

Beslissingsvariabelen

De beslissingsvariabelen zijn "x" en "y", die reële waarden aannemen:

-x: het aantal zwarte woudtaarten

-y: taarten van het sacripantine-type.

Beperkingen

De beperkingen worden gegeven door het feit dat het aantal cakes een positieve hoeveelheid is en dat er beperkte hoeveelheden grondstof zijn om ze te bereiden.

Daarom hebben deze beperkingen in wiskundige vorm de vorm:

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

Beperkingen 1 en 2 vormen de voorwaarde van niet-negativiteit die eerder werd blootgelegd, en alle opgeworpen ongelijkheden zijn lineair. In restricties 3 en 4 staan ​​de waarden die niet overschreden mogen worden: 144 eieren en 10 kg suiker.

Objectieve functie

Ten slotte is de objectieve functie de winst die wordt verkregen bij het vervaardigen van "x" hoeveelheid zwarte woudkoekjes plus "y" hoeveelheid sacripantines. Het wordt gebouwd door de prijs te vermenigvuldigen met het aantal gemaakte cakes en voor elk type toe te voegen. Het is een lineaire functie die we G (x, y) zullen noemen:

G = 8x + 10j

Oplossingsmethoden

De verschillende oplossingsmethoden omvatten grafische methoden, het simplex-algoritme en de interne puntmethode, om er maar een paar te noemen.

- Grafische of geometrische methode

Als je een probleem met twee variabelen hebt, zoals het probleem in de vorige sectie, bepalen de beperkingen een veelhoekig gebied in het xy-vlak, het haalbare gebied of levensvatbaarheidsgebied genoemd.

Figuur 3. De haalbare regio, waar de oplossing van het optimalisatieprobleem wordt gevonden. Bron: Wikimedia Commons.

Dit gebied is geconstrueerd met behulp van de restrictielijnen, dit zijn de lijnen die zijn verkregen uit de ongelijkheden van de restricties, die alleen werken met het gelijkheidsteken.

In het geval van de bakkerij die de winst wil optimaliseren, zijn de beperkende lijnen:

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

Alle punten in het gebied omsloten door deze lijnen zijn mogelijke oplossingen, dus er zijn er oneindig veel. Behalve in het geval dat het haalbare gebied leeg blijkt te zijn, dan heeft het gestelde probleem geen oplossing.

Gelukkig is voor het banketprobleem de haalbare regio niet leeg, we hebben het hieronder.

Figuur 4. De haalbare regio van het gebaksprobleem. De lijn met winst 0 kruist de oorsprong. Bron: F. Zapata met Geogebra.

De optimale oplossing, indien die bestaat, wordt gevonden met behulp van de doelfunctie. Als we bijvoorbeeld proberen de maximale winst G te vinden, hebben we de volgende regel, die de iso-profitregel wordt genoemd:

G = k ₁ X + k ₂ Y → Y = -k ₁ X / k ₂ + G / k ₂

Met deze lijn krijgen we alle paren (x, y) die een bepaalde versterking G geven, dus er is een familie van lijnen volgens de waarde van G, maar allemaal met dezelfde helling -k ₁ / k ₂ , dus ze zijn parallelle lijnen.

De optimale oplossing

Nu kan worden aangetoond dat de optimale oplossing van een lineair probleem altijd een extreem punt of hoekpunt van het haalbare gebied is. Zo:

Als de lijn die het dichtst bij de oorsprong ligt een heel segment gemeen heeft met het haalbare gebied, wordt er gezegd dat er oneindig veel oplossingen zijn. Dit geval doet zich voor als de helling van de iso-profitlijn gelijk is aan die van een van de andere lijnen die de regio begrenzen.

Voor ons gebak zijn de kandidaat-hoekpunten A, B en C.

- De simplex-methode van Dantzig

De grafische of geometrische methode is van toepassing op twee variabelen. Het is echter ingewikkelder als er drie variabelen zijn en onmogelijk te gebruiken voor een groter aantal variabelen.

Bij problemen met meer dan twee variabelen wordt de simplex-methode gebruikt, die bestaat uit een reeks algoritmen om de objectieve functies te optimaliseren. Matrices en eenvoudige rekenkunde worden vaak gebruikt om de berekeningen uit te voeren.

De simplex-methode begint met het kiezen van een haalbare oplossing en het controleren of deze optimaal is. Als dat het geval is, hebben we het probleem al opgelost, maar als dat niet het geval is, gaan we verder naar een oplossing die dichter bij optimalisatie ligt. Als de oplossing bestaat, vindt het algoritme deze in een paar pogingen.

Toepassingen

Lineaire en niet-lineaire programmering worden op veel gebieden toegepast om de beste beslissingen te nemen in termen van kostenverlaging en hogere winsten, die niet altijd geldelijk zijn, omdat ze in de tijd kunnen worden gemeten, bijvoorbeeld als u de benodigde tijd wilt minimaliseren om een ​​reeks bewerkingen uit te voeren.

Hier zijn enkele velden:

-In marketing wordt het gebruikt om de beste combinatie van media (sociale netwerken, televisie, pers en andere) te vinden om reclame te maken voor een bepaald product.

-Voor de toewijzing van adequate taken aan het personeel van een bedrijf of fabriek of roosters aan hen.

-Bij de selectie van het meest voedzame voedsel en tegen de laagste kosten in de vee- en pluimvee-industrie.

Opgeloste oefeningen

- Oefening 1

Los het lineaire programmeermodel op in de voorgaande secties grafisch op.

Oplossing

Het is noodzakelijk om een ​​grafiek te maken van de reeks waarden die is bepaald door het systeem van beperkingen dat in het probleem is gespecificeerd:

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

Het gebied gegeven door ongelijkheden 1 en 2 komt overeen met het eerste kwadrant van het cartesische vlak. Met betrekking tot ongelijkheden 3 en 4, beginnen we met het vinden van de restrictielijnen:

9x + 8y = 144

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

Het haalbare gebied is een vierhoek waarvan de hoekpunten punten A, B, C en D zijn.

De minimale winst is 0, daarom is de lijn 8x + 10y = 0 de ondergrens en hebben de iso-profitlijnen een helling van -8/10 = - 0,8.

Deze waarde verschilt van de hellingen van de andere restrictielijnen en aangezien het haalbare gebied begrensd is, bestaat de unieke oplossing.

Figuur 5. Grafische oplossing van oefening 1, met het haalbare gebied en het oplossingspunt C op een van de hoekpunten van dat gebied. Bron: F. Zapata.

Deze oplossing komt overeen met een hellingslijn -0,8 die door een van de punten A, B of C loopt, waarvan de coördinaten zijn:

A (11; 5.625)

B (0; 12,5)

C (16, 0)

Optimale oplossing

We berekenen de waarde van G voor elk van deze punten:

- (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

De hoogste winst wordt behaald bij het vervaardigen van 11 zwarte woudkoekjes en 5.625 sacripantijnse koeken. Deze oplossing komt overeen met de oplossing die via de software is gevonden.

- Oefening 2

Controleer het resultaat van de vorige oefening met behulp van de Oplosser-functie die beschikbaar is in de meeste spreadsheets, zoals Excel of LibreOffice Calc, die het Simplex-algoritme bevatten voor optimalisatie in lineaire programmering.

Oplossing

Figuur 6. Detail van de oplossing van oefening 1 tot en met het Libre Office Calc-spreadsheet. Bron: F. Zapata.

Figuur 7. Detail van de oplossing van oefening 1 tot en met het Libre Office Calc-spreadsheet. Bron: F. Zapata.

Referenties

1. Briljant. Lineair programmeren. Hersteld van: brilliant.org.
2. Eppen, G. 2000. Operationeel onderzoek in administratieve wetenschappen. 5e. Editie. Prentice Hall.
3. Haeussler, E. 1992. Wiskunde voor management en economie. 2e. Editie. Grupo Hoofdartikel Iberoamericana.
4. Hiru.eus. Lineair programmeren. Hersteld van: hiru.eus.
5. Wikipedia. Lineair programmeren. Hersteld van: es. wikipedia.org.