taken lineaire programmering

2.1. Definitie en vormen van opname

In het geval dat alle beperkingen vergelijkingen zijn en alle variabelen voldoen aan de niet-negativiteitsvoorwaarde, wordt het lineaire programmeerprobleem genoemd canoniek. Het kan worden gepresenteerd in de vorm van een coördinaten-, vector- of matrixnotatie.

a) het canonieke LP-probleem in coördinatenvorm heeft de vorm:

,
.

Dit probleem kan worden geschreven met behulp van het sommatieteken:

,

,

,
,
.

b) het canonieke LP-probleem in vectorvorm heeft de vorm:

,

Waar
;
;

,
;;
.

c) het canonieke LP-probleem in matrixvorm heeft de vorm:

,
,

Waar
,,.

2.2. Vermindering van het algemene lineaire probleem

programmeren naar canonieke vorm

Bij het samenstellen van wiskundige modellen van economische problemen worden beperkingen vooral gevormd tot systemen van ongelijkheid. Daarom is het noodzakelijk om van deze naar stelsels van vergelijkingen te kunnen overstappen. Neem bijvoorbeeld de lineaire ongelijkheid

en voeg aan de linkerkant een bepaalde waarde toe
zodat ongelijkheid gelijkheid wordt.

Niet-negatieve variabele
een extra variabele genoemd. De volgende stelling vormt de basis voor de mogelijkheid van een dergelijke transformatie.

Stelling 2.2.1. Elke beslissing
ongelijkheid (2.2.1) komt overeen met een unieke oplossing voor vergelijking (2.2.2) en ongelijkheid
en, omgekeerd, voor elke oplossing van vergelijking (2.2.2)c
komt overeen met de oplossing
ongelijkheden (2.2.1).

Bewijs. Laten
oplossing van ongelijkheid (2.2.1). Dan. Laten we een getal nemen
. Dat is duidelijk
. Als we dit in vergelijking (2.2.2) invullen, krijgen we

Het eerste deel van de stelling is bewezen.

Laten we nu een vector zijn voldoet aan vergelijking (2.2.2) met
, dat wil zeggen, waarbij de niet-negatieve waarde aan de linkerkant van de laatste gelijkheid wordt weggegooid
, wij ontvangen enz.

De bewezen stelling vestigt dus feitelijk de mogelijkheid om elk LP-probleem naar een canonieke vorm te brengen. Om dit te doen, volstaat het om in elke beperking die de vorm heeft van een ongelijkheid een eigen aanvullende niet-negatieve variabele te introduceren. Bovendien zullen deze variabelen bij ongelijkheden van de vorm (1.2.1) verschijnen met het “+” teken, en bij ongelijkheden van de vorm (1.2.2) – met het “–” teken. Er worden aanvullende variabelen ingevoerd doelfunctie met nulcoëfficiënten en heeft daarom geen invloed op de waarde ervan.

Opmerking. In de toekomst zullen we de simplexmethode voor het canonieke LP-probleem presenteren bij het bestuderen van de objectieve functie voor een minimum. In die problemen waarbij je het maximale moet vinden
, is het voldoende om de functie te overwegen
, vind haar minimale waarde en bepaal vervolgens, door het teken in het tegenovergestelde te veranderen, de gewenste maximale waarde
.

3. Grafische methode voor het oplossen van problemen

lineaire programmering

3.1. Algemene concepten, voorbeelden

In gevallen waarin er slechts twee variabelen in het LP-probleem voorkomen, kunt u gebruiken grafische methode. Laat het nodig zijn om de maximale (minimale) waarde van de functie te vinden
onder beperkingen

(3.1.1)

Deze methode is gebaseerd op de mogelijkheid om het gebied van haalbare oplossingen voor een probleem grafisch weer te geven, d.w.z. bevredigend systeem (3.1.1), en het vinden van de optimale oplossing daartussen. Het gebied met haalbare oplossingen voor het probleem wordt geconstrueerd als het snijpunt (gemeenschappelijk deel) van de oplossingsgebieden van elk van de gegeven beperkingen (3.1.1). Elk van hen definieert een halfvlak met grens
,
. Om te bepalen welk van de twee halve vlakken het oplossingsdomein is, volstaat het om de coördinaten van elk punt dat niet op de lijn ligt in de ongelijkheid te vervangen: als hieraan voldaan is, dan is het oplossingsdomein het halfvlak met daarin dit punt Als niet aan de ongelijkheid wordt voldaan, is het oplossingsdomein een halfvlak dat het gegeven punt niet bevat.

Het snijpunt van deze halve vlakken vormt een bepaald gebied dat een oplossingspolygoon wordt genoemd en dat een convexe verzameling is. (Veronderstel dat het systeem van beperkingen consistent is en dat de polygoon van zijn oplossingen beperkt is.) Om de optimale oplossing tussen de haalbare oplossingen te vinden, worden niveaulijnen en referentierechte lijnen gebruikt.

Niveau lijn wordt een rechte lijn genoemd waarop het objectief functioneert neemt een constante waarde aan. De niveaulijnvergelijking heeft de vorm

, Waar
. Alle niveaulijnen lopen evenwijdig aan elkaar. Hun normaal
.

Referentielijn wordt een niveaulijn genoemd die ten minste één gemeenschappelijk punt heeft met het gebied van haalbare oplossingen, ten opzichte waarvan dit gebied zich in een van de halfvlakken bevindt (Fig. 1).

Waarden
toenemen in de richting van de vector
.
Daarom is het noodzakelijk om de niveaulijn te verplaatsen in de richting van deze vector evenwijdig aan zichzelf ten opzichte van de referentielijn 1 L in de richting van deze vector evenwijdig aan zichzelf ten opzichte van de referentielijn 2).

in de maximale taak en in de tegenovergestelde richting - in de minimale taak (tot aan de referentielijn
onder beperkingen

Laten we de oplossing van voorbeeld 1.1 geven. Bedenk dat we het maximum van de functie moeten vinden

Oplossing. Wij construeren een regio met haalbare oplossingen. We nummeren de beperkingen van het probleem. In een rechthoekig Cartesisch coördinatensysteem (Fig. 2) construeren we een rechte lijn

Om dit te doen, volstaat het om de coördinaten van elk punt dat niet op de lijn ligt, in de ongelijkheid te vervangen. Omdat het recht is gaat niet door de oorsprong, substituut
tot de eerste beperking. We verkrijgen een strikte ongelijkheid
. Daarom het punt
ligt in het halve vlak van oplossingen. Op dezelfde manier construeren we een rechte lijn

en het oplossingsdomein van de beperking (2). We vinden het gemeenschappelijke deel van de halve oplossingsvlakken, rekening houdend met beperkingen (3). We markeren het resulterende gebied van haalbare oplossingen in donkere kleur in figuur 2.

Een niveaulijn bouwen
en vector
, wat de richting van de toename van de functie aangeeft en loodrecht op de lijn

.
Niveau lijn
evenwijdig aan zichzelf in de richting bewegen
naar de referentielijn. We zien dat de doelfunctie op dit punt zijn maximum bereikt snijpunt van lijnen En
. Een stelsel vergelijkingen van deze lijnen oplossen
, krijgen we de coördinaten van het punt
,
. Daarom, en

optimale oplossing.
Voorbeeld 3.1. Zoek het minimum van een functie

onder een systeem van beperkingen
Oplossing. We construeren het gebied van haalbare oplossingen (zie figuur 3), vector
en een van de niveaulijnen
. Verplaats de waterpaslijn in de tegenovergestelde richting

, aangezien het probleem van het vinden van het minimum van een functie wordt opgelost. In dit geval loopt de referentielijn door punt A (Fig. 3), waarvan de coördinaten zullen worden gevonden uit de oplossing van het systeem
Dus,

. Laten we berekenen.
Opmerking. In feite hangt het af van het type domein van haalbare oplossingen en de objectieve functie

Een LP-probleem kan één oplossing hebben, een oneindig aantal oplossingen of helemaal geen oplossing.
onder beperkingen

Voorbeeld 3.2. Zoek het minimum van een functie
Oplossing. We construeren het gebied van haalbare oplossingen (zie figuur 3), vector Oplossing. Het construeren van het gebied van haalbare oplossingen, de normaal van vlakke lijnen , dat gemeenschappelijke punten heeft met dit gebied. Verplaats de niveaulijn in de richting tegengesteld aan de normale richting
, aangezien het probleem van het vinden van het minimum van een functie wordt opgelost. Normale of vlakke lijnen en de normaal van de grenslijn
, in de richting waarin de niveaulijnen bewegen, zijn evenwijdig, omdat hun coördinaten proportioneel zijn . Daarom valt de referentielijn samen met de grenslijn snijpunt van lijnen regio met haalbare oplossingen en loopt door twee hoekpunten van deze regio

(Afb. 4).
Het probleem heeft een oneindig aantal optimale oplossingen, die punten van het segment zijn
,
.

;
;

,
;
,
;

;
.

Deze punten

we vinden door de overeenkomstige stelsels vergelijkingen op te lossen:
Laten we berekenen.
,
.

Antwoord:

bij
Voorbeeld 3.3. Los een lineair programmeerprobleem op bewegen in de richting van het normaal. Vanwege het feit dat in deze richting het bereik van haalbare oplossingen niet beperkt is, gaat de niveaulijn naar oneindig (Fig. 5).

Het probleem heeft geen oplossing vanwege de onbegrensdheid van de objectieve functie.

we vinden door de overeenkomstige stelsels vergelijkingen op te lossen:
.

: Lineaire programmeerproblemen (LPP)

1. Lineaire programmering

2. Soorten lineaire programmeerproblemen

3. Formulieren voor het vastleggen van PAP's

4. Canonieke vorm van lineaire programmeerproblemen

Lineaire programmering

Lineair programmeren is een tak van wiskundig programmeren die wordt gebruikt bij het ontwikkelen van methoden voor het vinden van een extremum lineaire functies meerdere variabelen met lineair aanvullende beperkingen, opgelegd aan de variabelen.

Op basis van het soort problemen dat ze oplossen, zijn LP-methoden onderverdeeld in universeel en speciaal. Door te gebruiken universele methoden Eventuele lineaire programmeerproblemen (LPP) kunnen worden opgelost. Speciale houden rekening met de kenmerken van het probleemmodel, de objectieve functie en het systeem van beperkingen.

Het belangrijkste kenmerk van lineaire programmeerproblemen is dat het uiterste van de doelfunctie zich op de grens van het gebied van haalbare oplossingen bevindt.

Figuur 1 - Extremum van de objectieve functie

Het wiskundige model van de ZLP is als volgt geschreven:

max (of min) Z=z(X),(1)

ODR kan door het systeem worden weergegeven lineaire vergelijkingen of ongelijkheden.

Vector X = (x 1, x 2, .... x p) is een controlevector of controle-effect.

Een toelaatbaar plan X, waarin het optimaliteitscriterium Z=z(X) een extreme waarde bereikt, wordt optimaal genoemd en wordt aangegeven met X*, de extreme waarde van de objectieve functie met Z*=z(X*).

Soorten lineaire programmeerproblemen

Lineaire programmeermethoden worden veel gebruikt in industriële ondernemingen bij het optimaliseren van het productieprogramma, het verdelen ervan over werkplaatsen en over tijdsintervallen, bij het laden van uitrustingsassortimenten, het plannen van vrachtstromen, het bepalen van het omzetplan, enz.

Het meest voorkomende type taken is taak optimaal gebruik bronnen. Laat een productie-eenheid (werkplaats, onderneming, vereniging, enz.), gebaseerd op de marktomstandigheden, technische mogelijkheden en beschikbare hulpbronnen, kunnen n produceren verschillende soorten producten bekend onder nummers j.

Bij het produceren van producten wordt de onderneming beperkt door de beschikbare hulpbronnen, waarvan de hoeveelheid wordt aangegeven met m, en de vector van hulpbronnen B = (b 1, b 2, ..., b t). Er zijn ook technologische coëfficiënten a ij bekend, die de consumptiesnelheid van de i-de hulpbron voor de productie van een eenheid van het j-de product weergeven. Efficiëntie van de eenheidsuitvoer j-i-producten gekenmerkt door winst p j .

Het is vereist om het productieplan X = (x 1, x 2, ..., x p) te bepalen, waardoor de winst van de onderneming met gegeven middelen wordt gemaximaliseerd.

De objectieve functie ziet er als volgt uit

onder beperkingen

Vaak wordt het productassortiment vastgesteld door een hogere organisatie, d.w.z. de volumes ervan moeten binnen bepaalde grenzen D in j en D in j liggen: dan wordt de volgende beperking gesteld:

Het model van het probleem van optimaal gebruik van hulpbronnen ligt ten grondslag modellen voor het optimaliseren van het jaarlijkse productieprogramma van de onderneming. Het model bevat beperkingen op de bedrijfstijd van apparatuur.

Met dezelfde notatie schrijven we via b j en c j respectievelijk de verkoopprijs en de kosten per eenheid jde producten. Het volgende kan als optimaliteitscriterium worden beschouwd:

1) maximale winst

2) minimale productiekosten

3) maximale output in waardetermen (inkomsten uit productverkoop)

Voorbeeld. De onderneming kan vier soorten producten produceren: 1, 2, 3 en 4. De verkoop van elk volume is gegarandeerd. Gedurende het kwartaal beschikt de onderneming over een personeelsbestand van 100 manploegen, halffabrikaten met een gewicht van 260 kg en een machine-uitrusting van 370 machineploegen. Het verbruik van hulpbronnen en de winst per eenheid van elk type product worden weergegeven in Tabel 1.

Nodig:

a) opmaken wiskundig model de taak om een ​​productieplan te bepalen dat maximale winst zal opleveren;

b) los het probleem met de verpakkingseis op, zodat het aantal eenheden van het derde product 3 keer is meer kwantiteit eenheden eerst;

c) ontdek het optimale assortiment voor aanvullende voorwaarden: produceer minimaal 25 eenheden van het eerste product, niet meer dan 30 eenheden van het derde, en het tweede en vierde in een verhouding van 1:3.

Tabel 1

Initiële gegevens

Wiskundig model van het probleem:

objectieve functie:

max: Z=40x 1 +50x 2 +100x 3 +80x 4

met beperkingen:

a) voor arbeidsmiddelen:

2,5x 1 +2,5x 2 +2x 3 +1,5x 4 ? 100;

voor halffabrikaten:

4x 1 +10x 2 +4x 3 +6x 4 ? 260;

voor werktuigmachines:

8x 1 +7x 2 +4x 3 +10x 4 ? 370;

niet-negativiteitsvoorwaarde:

b) de aanvullende eis voor de configuratie wordt uitgedrukt in de voorwaarde

3x 1 =x 3, d.w.z. 3x 1 x 3 =0;

c) laten we de randvoorwaarden en de configuratievoorwaarde als volgt weergeven: x 1 ?

x 3-30, 3*x 2 = x 4.

Het probleem van het plaatsen van bestellingen of het laden van verwisselbare groepen apparatuur. Het gaat over o verdeling van bestellingen tussen m (i=1,..., m) ondernemingen (winkels, machines, artiesten) met verschillende productie- en technologische kenmerken, maar uitwisselbaar in termen van het uitvoeren van bestellingen. Het is vereist om een ​​orderplaatsingsplan op te stellen waarin de taak zou worden voltooid en de efficiëntie-indicator een extreme waarde zou bereiken.

Laten we het probleem wiskundig formuleren. Stel dat er n soorten producten moeten worden geproduceerd met behulp van m homogene groepen apparatuur. Productieplan voor elk type product bepaalde periode gegeven door de verzameling x j (j=1,2, …n). Het vermogen van elk type apparatuur is beperkt en gelijk aan bi. De technologische matrix A=||a ij || is bekend, waarbij a ij het aantal eenheden van het j-de product is dat per tijdseenheid wordt geproduceerd i-de apparatuur. Matrix C is een kostenmatrix, waarbij c ij de kosten zijn die verband houden met de output jde eenheden producten op i-de apparatuur. X is een vector van het uitvoervolume.

Het probleemmodel zal de volgende vorm aannemen:

objectieve functie - minimalisering van de kosten voor de uitvoering van alle bestellingen

met beperkingen:

a) door apparatuurvermogen

b) voor productie

c) niet-negativiteitsconditie

Dit probleem wordt een distributief of distributieprobleem genoemd.

Indien voor sommige typen producten het plan mag worden overschreden, dan zal beperking (b) de vorm aannemen

Het volgende kan ook als doelwinst worden beschouwd:

a) maximale winst

b) minimale kosten van machinetijd

Omdat Elk model bevat vereenvoudigende premissen; voor de juiste toepassing van de verkregen resultaten is een duidelijk begrip van de essentie van deze vereenvoudigingen noodzakelijk, wat ons uiteindelijk in staat stelt een conclusie te trekken over de toelaatbaarheid of niet-ontvankelijkheid ervan. De belangrijkste vereenvoudiging in de beschouwde modellen is de aanname van een direct proportionele (lineaire) relatie tussen de volumes van het hulpbronnenverbruik en de productievolumes, die wordt gespecificeerd met behulp van kostennormen a ij . Het is duidelijk dat aan deze veronderstelling niet altijd wordt voldaan. De consumptievolumes van veel hulpbronnen (bijvoorbeeld vaste activa) veranderen dus abrupt - afhankelijk van veranderingen in het productieprogramma X. Andere vereenvoudigende premissen omvatten aannames over de onafhankelijkheid van prijzen j van volumes x j, die alleen voor bepaalde grenzen gelden. van hun verandering. Het is ook belangrijk om deze ‘kwetsbare’ punten te kennen, omdat ze fundamentele richtingen aangeven voor verbetering van het model.

PAP-registratieformulieren

Er zijn 3 vormen van PAP-opname:

1) in de vorm van functies

max(of min)Z=,max(of min)Z=,

2) vectorvorm

(scalair product van vectoren)

onder beperkingen

A 1 x 1 +A 2 x 2 +..+A n x n = B

Waar zijn de vectoren

C = (C 1, C 2 .. C n), X = (X 1, X 2 .. X n), en.

3) matrixvorm

onder beperkingen

waarbij C = (c 1, c 2,...c n),

Canonieke vorm van lineaire programmeerproblemen

Als alle beperkingen in een lineair programmeerprobleem vergelijkingen zijn en niet-negativiteitsvoorwaarden worden opgelegd aan alle variabelen x j, dan wordt het een lineair programmeerprobleem in canonieke vorm of een canoniek lineair programmeerprobleem (CLP) genoemd.

onder beperkingen

Om van de ZLP naar de CLLP te gaan, is het noodzakelijk om van ongelijkheidsbeperkingen naar gelijkheidsbeperkingen over te gaan en variabelen te vervangen die niet voldoen aan de niet-negativiteitsvoorwaarden.

Regels voor het brengen van ZLP naar canonieke vorm:

1) als er beperkingen zijn rechterkant negatief, dan moet deze limiet worden vermenigvuldigd met -1;

2) als er ongelijkheden zijn tussen de beperkingen, worden deze door het introduceren van aanvullende niet-negatieve variabelen omgezet in gelijkheden;

3) als een variabele xk geen tekenbeperkingen heeft, wordt deze in de objectieve functie en in alle beperkingen vervangen door het verschil tussen twee nieuwe niet-negatieve variabelen: xk=x * k - xl, waarbij l de samenvattende index is, x * k>=, xl >=0.

Laten we eens kijken naar een voorbeeld. Laten we het naar de canonieke vorm brengen:

Laten we nivelleringsvariabelen x 4, x 5, x 6 introduceren in elke vergelijking van het systeem van beperkingen. Het systeem zal worden geschreven in de vorm van gelijkheden, en in de eerste en derde vergelijkingen van het systeem van beperkingen worden de variabelen x 4, x 6 geïntroduceerd in linkerkant met een “+” teken, en x 5 met een “-” teken wordt ingevoerd in de tweede vergelijking.

De vrije termen in de canonieke vorm moeten positief zijn; vermenigvuldig hiervoor de laatste twee vergelijkingen met -1:

In de canonieke vorm van het schrijven van lineaire programmeerproblemen moeten alle variabelen in het systeem van beperkingen niet-negatief zijn. Laten we dat aannemen

Vervanging deze uitdrukking in het systeem van beperkingen en de objectieve functie en door de variabelen in oplopende indexvolgorde te schrijven, verkrijgen we een lineair programmeerprobleem gepresenteerd in canonieke vorm:

optimalisatie simplex lineaire programmering

Het schrijven van de objectieve functie en het systeem van beperkingen in diverse taken lineaire programmering is niet hetzelfde: bij sommige problemen is het nodig om het minimum van de objectieve functie te vinden, en bij andere - het maximum; in sommige gevallen zijn de vereiste variabelen afhankelijk van één index, en in andere gevallen van twee; bij sommige problemen worden de beperkingen gespecificeerd in de vorm van een systeem lineaire ongelijkheden, en in andere – in de vorm van een systeem van lineaire vergelijkingen. In de praktijk is het ook mogelijk om problemen te hebben waarbij sommige beperkingen de vorm hebben van lineaire ongelijkheden, en sommige de vorm hebben van lineaire vergelijkingen. Bovendien vereisen niet alle problemen niet-negativiteit van variabelen.

Het rekening houden met een dergelijke verscheidenheid aan lineaire programmeerproblemen vereist de ontwikkeling van speciale methoden voor het oplossen van individuele klassen ervan. Wij zullen onze aandacht richten op studeren algemene eigenschappen en lineaire programmeermethoden geschreven in zogenaamde canonieke vorm.

Als bij een lineair programmeerprobleem het systeem van initiële beperkingen de vorm aanneemt van vergelijkingen zoals

en je moet het maximum van de lineaire objectieve functie vinden

dan wordt aangenomen dat het lineaire programmeerprobleem in canonieke vorm is geschreven.

Elk lineair programmeerprobleem kan eenvoudig worden teruggebracht tot een canonieke vorm. In het algemene geval is het hiervoor voldoende om ten eerste het probleem van het minimaliseren van de objectieve functie te kunnen reduceren tot het probleem van het maximaliseren ervan, ten tweede om van ongelijkheidsbeperkingen naar gelijkheidsbeperkingen te gaan, en ten derde de variabelen te veranderen die niet onderworpen aan de niet-negativiteitsvoorwaarde.

In het geval dat u het minimum van een functie moet vinden , kunnen we doorgaan met het vinden van het maximum van de functie , aangezien de volgende bewering waar is:
.

De ongelijkheidsbeperking van het oorspronkelijke probleem, dat de vorm heeft van “ ", kan worden omgezet in een vergelijkingsbeperking door een extra niet-negatieve variabele aan de linkerkant toe te voegen, en een ongelijkheidsbeperking van de vorm " ” – door een extra niet-negatieve variabele van de linkerkant af te trekken.

Merk op dat het aantal geïntroduceerde aanvullende niet-negatieve variabelen altijd gelijk is aan het aantal ongelijkheden in het oorspronkelijke systeem van beperkingen.

De extra geïntroduceerde variabelen hebben een zeer specifieke economische betekenis. Dus als de beperkingen van het oorspronkelijke lineaire programmeringsprobleem de kosten en beschikbaarheid van productiemiddelen weerspiegelen, dan numerieke waarde de extra variabele toont de hoeveelheid van de overeenkomstige ongebruikte hulpbron.

Merk ook op dat als een variabele niet voldoet aan de niet-negativiteitsvoorwaarde, dan moet deze worden vervangen door twee niet-negatieve variabelen En , aanvaard
.

Voorbeeld. Schrijf het volgende lineaire optimalisatieprobleem in canonieke vorm: vind het minimum van de functie
onder beperkingen

Oplossing

In dit probleem moet je het minimum van de objectieve functie vinden, en het systeem van beperkingen omvat vier ongelijkheden. Om het in canonieke vorm te schrijven, moet je overgaan van ongelijkheidsbeperkingen naar vergelijkingsbeperkingen, en ook de objectieve functie transformeren.

Aangezien het aantal ongelijkheden dat is opgenomen in het systeem van beperkingen van het probleem vier is, moet deze transitie worden uitgevoerd met de introductie van vier extra niet-negatieve variabelen. Bovendien staat er in de tweede en vierde ongelijkheid een teken “ ", dus voegen we extra variabelen toe aan de linkerkant. In de eerste en derde ongelijkheid staat een teken “ “, wat betekent dat we extra variabelen van hun linkerkant aftrekken.

We transformeren ook de objectieve functie, veranderen alle tekens in het tegenovergestelde en vinden het maximum ervan.

Dus, deze taak lineaire programmering zal in de volgende canonieke vorm worden geschreven:

Zoek het maximum van een functie

onder beperkingen

Canonieke vorm van ZLP- lineair programmeerprobleem van de vorm ax = b waarbij a de coëfficiëntenmatrix is, en b de beperkingsvector.

Doel van de dienst. De online calculator is ontworpen voor de overstap van een PPP naar een KZLP. Het probleem in een canonieke vorm brengen betekent dat alle beperkingen de vorm van gelijkheid zullen hebben door het introduceren van aanvullende variabelen.
Als er aan geen enkele variabele x j een beperking wordt opgelegd, wordt deze vervangen door het verschil van aanvullende variabelen, x j = x j1 - x j2, x j1 ≥ 0, x j2 ≥ 0.

Instructies. Selecteer het aantal variabelen en het aantal rijen (aantal beperkingen). De resulterende oplossing wordt opgeslagen in een Word-bestand.

Aantal variabelen 2 3 4 5 6 7 8 9 10
Aantal rijen (aantal beperkingen) 2 3 4 5 6 7 8 9 10

Hoe je een lineair programmeerprobleem kunt reduceren tot een canonieke vorm

Het wiskundige model van de ZLP wordt genoemd eenvoudig, als de beperkingen daarin worden gepresenteerd in de vorm van vergelijkingen, op voorwaarde dat de variabelen niet-negatief zijn.

Het wiskundige model wordt genoemd canoniek, als het systeem van beperkingen wordt gepresenteerd in de vorm van een systeem van m lineair onafhankelijke vergelijkingen (systeemrang r = m), wordt het systeem toegewezen eenheidsbasis worden vrije variabelen gedefinieerd en wordt de doelfunctie uitgedrukt in termen van vrije variabelen. In dit geval zijn de rechterkanten van de vergelijkingen niet-negatief (b i ≥ 0).

Variabelen die zijn opgenomen in een van de vergelijkingen van het systeem met een coëfficiënt van één en afwezig zijn in andere vergelijkingen, worden genoemd fundamentele onbekenden en alle anderen - vrij.

De oplossing voor het systeem wordt genoemd eenvoudig, als de vrije variabelen daarin gelijk zijn aan 0, en de vorm heeft:
X basen = (0, 0; b 1 , …, b m), f(X basen) = c 0

Basis oplossing is het hoekpunt van de reeks oplossingen van het systeem, d.w.z. definieert het hoekpunt van de oplossingspolygoon van het model. Een van dergelijke oplossingen is die waarin de objectieve functie plaatsvindt optimale waarde.

Een basisoplossing wordt een referentieoplossing genoemd als deze toelaatbaar is, d.w.z. alle rechterkanten van de systeemvergelijkingen (of ongelijkheden) zijn positief bi ≥ 0.

De compacte vorm van het canonieke model is:
BIJL = geb
X ≥ 0
Z = CX(max)

Het concept van een ontvankelijke oplossing, het gebied van ontvankelijke oplossingen, optimale oplossing lineaire programmeerproblemen.
Definitie 1. Een vector X die voldoet aan het systeem van ZLP-beperkingen, inclusief de eventuele niet-negativiteitsvoorwaarden, wordt een toelaatbare oplossing voor de ZLP genoemd.
Definitie 2. De verzameling van alle toelaatbare oplossingen vormt de regio van toelaatbare oplossingen (ADA) van de PLP.
Definitie 3. Een haalbare oplossing waarvoor de doelfunctie een maximum (of minimum) bereikt, wordt een optimale oplossing genoemd.

Voorbeeld nr. 1. Reduceer het volgende LP-probleem naar de canonieke vorm: F(X) = 5x 1 + 3x 2 → max onder de beperkingen:
2x 1 + 3x 2 ≤20
3x 1 + x 2 ≤15
4x 1 ≤16
3x 2 ≤12
Het model is ingeschreven standaard formulier. Laten we niet-negatieve balansvariabelen x 3 , x 4 , x 5 , x 6 introduceren, die we toevoegen aan de linkerkant van de ongelijkheidsbeperkingen. We introduceren alle aanvullende variabelen in de objectieve functie met coëfficiënten gelijk aan nul:
In de eerste betekenisongelijkheid (≤) introduceren we de basisvariabele x 3 . In de 2e betekenisongelijkheid (≤) introduceren we de basisvariabele x 4 . In de derde ongelijkheid introduceren we de basisvariabele x 5 . In de 4e ongelijkheid - de basisvariabele x 6. Wij krijgen canonieke vorm modellen:
2x 1 + 3x 2 + 1x 3 + 0x 4 + 0x 5 + 0x 6 = 20
3x 1 + 1x 2 + 0x 3 + 1x 4 + 0x 5 + 0x 6 = 15
4x 1 + 0x 2 + 0x 3 + 0x 4 + 1x 5 + 0x 6 = 16
0x 1 + 3x 2 + 0x 3 + 0x 4 + 0x 5 + 1x 6 = 12
F(X) = 5x 1 + 3x 2 + 0x 3 + 0x 4 + 0x 5 + 0x 6 → maximaal

Voorbeeld nr. 2. Zoek twee referentieoplossingen van het systeem
x 1 + 2x 4 - 2x 5 = 4
x 3 + 3x 4 + x 5 = 5
x 2 + 3x 5 = 2