Verschillende vormen van schrijven van lineaire programmeerproblemen.

In het algemene geval wordt een lineair programmeerprobleem zo geschreven dat zowel vergelijkingen als ongelijkheden beperkingen zijn, en de variabelen zowel niet-negatief als willekeurig variabel kunnen zijn. In het geval dat alle beperkingen vergelijkingen zijn en alle variabelen voldoen aan de niet-negativiteitsvoorwaarde, wordt het lineaire programmeerprobleem canoniek genoemd. Het kan worden weergegeven in coördinaat-, vector- of matrixnotatie.

1. Het canonieke lineaire programmeerprobleem in coördinatennotatie heeft de vorm

.

In een meer compacte vorm kan dit probleem worden geschreven met behulp van het sommatieteken,

(1.7)

2. Het canonieke lineaire programmeerprobleem in vectornotatie heeft de vorm

(1.8)

waar ,

.

3. Het canonieke lineaire programmeerprobleem in matrixnotatie heeft de vorm

(1.9)

, .

Hier EEN- matrix van coëfficiënten van het stelsel vergelijkingen, x- de matrixkolom van de probleemvariabelen, - de matrixkolom van de rechterkant van het beperkingssysteem.

Vaak gebruikt worden lineaire programmeerproblemen genoemd symmetrisch, die in matrixnotatie de vorm hebben

(1.10)

(1.11)

1.4. Reductie van een algemeen lineair programmeerprobleem
naar de canonieke vorm

Bij de meeste methoden voor het oplossen van lineaire programmeerproblemen wordt aangenomen dat het systeem van beperkingen bestaat uit vergelijkingen en natuurlijke voorwaarden voor de niet-negativiteit van variabelen. Bij het samenstellen van wiskundige modellen van economische problemen worden beperkingen echter voornamelijk gevormd in systemen van ongelijkheden, daarom is het noodzakelijk om van een systeem van ongelijkheden naar een systeem van vergelijkingen te kunnen gaan. Daartoe bewijzen we de volgende stelling.

Stelling 1.1. Een ongelijkheid vervangen door een vergelijking. op elke beslissing ongelijkheden

er komt een unieke oplossing voor de vergelijking overeen

en ongelijkheid

, (1.14)

en omgekeerd, met elke oplossing van vergelijking (1.13) en ongelijkheid (1.14) komt er een unieke oplossing van ongelijkheid (1.12) overeen.

Bewijs. Laat Is een oplossing voor ongelijkheid (1.12), dan. We duiden het verschil tussen de rechter- en linkerkant van deze ongelijkheid aan met, d.w.z.

Klaarblijkelijk ... Laten we in vergelijking (1.13) in plaats van variabelen de waarden vervangen , we krijgen

Het voldoet dus aan vergelijking (1.13) en ongelijkheid (1.14). Dit betekent dat het eerste deel van de stelling is bewezen.

Laat het nu voldoen aan vergelijking (1.13) en ongelijkheid (1.14), dat wil zeggen, we hebben

EN

Als we de niet-negatieve hoeveelheid aan de linkerkant van de laatste gelijkheid weggooien, krijgen we

d.w.z. voldoet aan ongelijkheid (1.12). De stelling is bewezen.

Als de ongelijkheid, dan moet een extra niet-negatieve variabele in de linkerkant worden ingevoerd met een minteken, d.w.z.

Niet-negatieve variabelen die in ongelijkheidsbeperkingen worden geïntroduceerd om ze in vergelijkingen om te zetten, worden genoemd extra variabelen... Extra variabelen worden in de doelfunctie geïntroduceerd met nulcoëfficiënten en hebben daarom geen invloed op de waarde ervan.

In het geval dat het probleem willekeurig veranderende variabelen heeft, wordt een dergelijke variabele vervangen door het verschil van twee niet-negatieve variabelen, d.w.z. , waar en .

Soms wordt het nodig om het probleem te verplaatsen van het vinden van het minimum naar het vinden van het maximum, of omgekeerd. Om dit te doen, volstaat het om de tekens van alle coëfficiënten van de objectieve functie in het tegenovergestelde te veranderen en de rest van het probleem ongewijzigd te laten. De optimale oplossingen van de op deze manier verkregen maximale en minimale problemen vallen samen, en de waarden van de objectieve functies op de optimale oplossingen verschillen alleen in teken.

Voorbeeld 1.1. Breng het lineaire programmeerprobleem naar de canonieke vorm.

Oplossing... Laten we ons wenden tot het probleem van het vinden van het maximum van de objectieve functie. Om dit te doen, veranderen we de tekens van de objectieve functiecoëfficiënten. Om het systeem van beperkingen om te zetten in vergelijkingen van de tweede en derde ongelijkheden, introduceren we niet-negatieve extra variabelen (op het wiskundige model is deze bewerking gemarkeerd met de letter D). De variabele wordt aan de linkerkant van de tweede ongelijkheid geïntroduceerd met het "+"-teken, aangezien de ongelijkheid de vorm heeft. De variabele wordt ingevoerd aan de linkerkant van de derde ongelijkheid met het "-" teken, aangezien de ongelijkheid de vorm heeft. Variabelen worden in de doelfunctie ingevoerd met een coëfficiënt gelijk aan nul. De variabele die niet onderhevig is aan de niet-negativiteitsvoorwaarde wordt vervangen door het verschil , ... Het probleem in canonieke vorm schrijven

In sommige gevallen wordt het noodzakelijk om het canonieke probleem te herleiden tot een symmetrisch probleem. Laten we naar een voorbeeld kijken.

Voorbeeld 1.2. Verminder het lineaire programmeerprobleem tot een symmetrische vorm

In de oorspronkelijke setting kunnen LPP's verschillende vormen van opnemen toelaten. Dus bij sommige taken is het nodig om de doelfunctie te maximaliseren, in andere - om te minimaliseren; sommige lineaire beperkingen kunnen de vorm hebben van gelijkheden, andere als ongelijkheden, enzovoort.

Voor de uniformiteit van het LPP-record is de zgn canonieke vorm verslagen.

Ze zeggen dat ZLP in canonieke vorm is geschreven als het de volgende vorm heeft:

Let op de volgende kenmerken van de canonieke vorm:

1) het is vereist om de objectieve functie te minimaliseren;

2) alle lineaire beperkingen, behalve de eis van niet-negativiteit van variabelen, hebben de vorm van gelijkheden;

alle variabelen zijn onderworpen aan niet-negativiteitsvereisten.

Laten we laten zien dat elke LPP kan worden teruggebracht tot een canonieke vorm.

1) Als het in de LPP nodig is om de doelfunctie f te maximaliseren, dan zetten we g = - f en vereisen het minimaliseren van de functie g. We krijgen een nieuwe LPP, die equivalent is aan de originele in die zin dat elke optimale oplossing voor het oorspronkelijke probleem de optimale oplossing voor het nieuwe probleem zal zijn en vice versa.

2) Stel dat de LPP een lineaire beperking heeft van de vorm

We vervangen deze beperking door de volgende twee beperkingen:

waar z - een nieuwe variabele die in de doelfunctie wordt ingevoerd met een coëfficiënt van 0 (met andere woorden, de variabele z wordt niet in de doelfunctie ingevoerd). De waarde van de variabele z kan worden genegeerd na het oplossen van een nieuw probleem.

Evenzo wordt de weergavebeperking vervangen door twee beperkingen:

3) Stel dat in het LPP niet alle variabelen niet-negatief hoeven te zijn. Dan is elke variabele , waarop de eis van niet-negativiteit niet wordt opgelegd, kan worden weergegeven als het verschil van twee niet-negatieve variabelen:

Elk voorkomen van een variabele in de objectieve functie of beperkingen, vervangen we het verschil
... Nadat we het nieuwe probleem hebben opgelost met behulp van (2.6), keren we terug naar de vorige variabelen.

Met de aangegeven technieken wordt elke LPP herleid tot een canonieke vorm.

Voorbeeld. Breng naar canonieke vorm

Laten we de beschreven acties uitvoeren.

Nu krijgen we de ZLP in de canonieke vorm:

2.7. Het concept van het basisplan zlp.

Laat het ILP gegeven worden in de canonieke vorm (2,3 - 2,5). Stel dat het stelsel vergelijkingen (2.4) wordt teruggebracht tot Jordan-vorm met niet-negatieve rechterkant:

(2.6)

waar
.

Door de vrije variabelen gelijk te stellen aan nul, verkrijgen we de basisoplossing van systeem (2.4)

Door de conditie
de reeks waarden van variabelen (2.7) voldoet ook aan beperkingen (2.5). Daarom is (2.6) aanvaardbare beslissing van de LPP.

Een haalbare oplossing (2.7) heet basis toelaatbaar beslissing of basisplan van ZLP. Tegelijkertijd zeggen ze dat de variabelen
een toelaatbare basis vormen.

Het blijkt dat als de ODR geometrisch wordt weergegeven, elk ondersteuningsplan van de ZLP overeenkomt met het hoekpunt van het veelvlak. Daarom is de volgende stelling waar.

Als het LPP oplosbaar is, is er een optimaal ondersteuningsplan.

3. Simplex-methode voor het oplossen van zlp

3.1. Algemene kenmerken en hoofdfasen van de simplex-methode

De grondleggers van de simplex-methode zijn de Sovjet-wiskundige L.V. Kantorovich en de Amerikaanse wiskundige J. Danzig.

Elke LPP kan worden opgelost met de simplex-methode of de onbeslisbaarheid ervan kan worden gedetecteerd. Veel speciale klassen van LPP kunnen worden opgelost met andere methoden die efficiënter zijn voor deze klassen. Het voordeel van de simplex-methode is echter de veelzijdigheid ervan. Voor bijna alle computers zijn standaard programma's ontwikkeld voor het oplossen van de LPP volgens de simplex methode.

Laten we het algemene idee van de simplex-methode beschrijven.

We nemen aan dat de LPP in de canonieke vorm is geschreven en dat de objectieve functie geminimaliseerd moet worden. Zoals we al weten, moet het optimale plan worden gezocht bij de ondersteuningsplannen van het LPP. De simplex-methode herhaalt niet alle basislijnplannen (wat vaak onmogelijk zou zijn vanwege hun enorme aantal), maar, uitgaande van een aanvankelijk basislijnplan, gaat het sequentieel naar andere basislijnplannen met een afname van de doelfunctie. De simplex-methode stopt met werken wanneer ofwel het optimale basislijnplan is gevonden, of wanneer het probleem onbeslisbaar blijkt te zijn.

Bij het oplossen van LPP met behulp van de simplex methode zijn de volgende stappen te onderscheiden:

1) het LPP naar de canonieke vorm brengen;

2) reductie van het stelsel van lineaire vergelijkingen tot de Jordan-vorm met niet-negatieve rechterkant met een gelijktijdige controle op onbeslisbaarheid van de LPP vanwege de inconsistentie van het stelsel van lineaire beperkingen;

3) onderzoek van het basisplan voor optimalisatie;

4) onderzoek van de LPP op onbeslisbaarheid door onbegrensdheid van onderaf op de ODR van de objectieve functie;

5) overgang naar een nieuw, "beter" referentieplan.

Een analytische methode voor het oplossen van een lineair programmeerprobleem is: simplex methode. Voor de toepassing ervan moeten LP-problemen, die op verschillende manieren worden gepresenteerd, worden teruggebracht tot de canonieke vorm. Het lineaire programmeerprobleem, geschreven in de vorm (2.1.1) - (2.1.3), is een uitgebreide vorm van het schrijven van het algemene lineaire programmeerprobleem (LPP).

Het volgende probleem wordt het canonieke lineaire programmeerprobleem (LCPP) genoemd:

onder beperkingen in de vorm van gelijkheden,

Als het probleem in de vorm (2.3.1) - (2.3.4) voldoet aan de voorwaarde m = n, dan wordt de oplossing ervan gereduceerd tot het oplossen van het stelsel vergelijkingen

• (2.3.2). In dit geval heeft het probleem geen oplossingen als de voorwaarde
• (2.3.3) is niet voldaan of het stelsel vergelijkingen heeft geen oplossing.

voorwaarde t

• 1. Om te gaan van de taak van maximalisatie objectieve functie (2.3.1) to minimaliseringsprobleem genoeg neem alle coëfficiënten Cj objectieve functie met omgekeerde tekens en het resulterende probleem maximaal op te lossen. Na het vinden van het maximum, moet de waarde van de objectieve functie worden genomen met het tegenovergestelde teken. De optimale oplossing blijft hetzelfde.
• 2. Om te gaan van beperking zoals "minder dan of gelijk aan" tot gelijkheid het heeft nodig met een plusteken:

3. Om te gaan van een "groter dan of gelijk" beperking tot gelijkheid het heeft nodig een extra niet-negatieve variabele introduceren met een minteken:

In dit geval introduceert elke ongelijkheid zijn eigen (n +/) - Ik ben een extra variabele.

• 4. Alles gelijkheden met negatieve vrije termen worden gedeeld door-1 om aan voorwaarde (2.3.4) te voldoen.
• 5. Als voor een variabele Xj de niet-negativiteitsvoorwaarde wordt niet opgelegd, dan verander de variabelen Xj = x ".- X" x "j> 0, x "> 0. In het getransformeerde probleem alle variabelen zijn niet-negatief.

Er is een bewering dat elke LPP kan worden teruggebracht tot de canonieke vorm.

Voorbeeld 2.3.1. Laten we het probleem uit voorbeeld 2.2.2 omzetten in zijn canonieke vorm. De doelfunctie en het systeem van beperkingen zijn als volgt:

We introduceren in de eerste ongelijkheid een extra variabele jc 3> 0 met een "plus"-teken, in de tweede x 4> 0 met een minteken en in de derde x 5> 0 ook met een plusteken. Als resultaat krijgen we een systeem van beperkingen voor het probleem in de canonieke vorm:

Met deze beperkingen moet u de maximale waarde van de functie vinden:

Laten we eens kijken naar de economische betekenis van extra variabelen in het canonieke probleem van optimaal gebruik van hulpbronnen.

Voorbeeld 2.3.2. Optimaal gebruik van middelen (tapijtprobleem)[17 J.

De fabriek beschikt over een bepaalde hoeveelheid van drie soorten middelen: arbeid (80 mandagen), grondstoffen (480 kg) en uitrusting (130 werktuigmachines). De fabriek kan vier soorten tapijten produceren. Informatie over het aantal eenheden van elk middel dat nodig is voor de productie van één tapijt van elk type, en over de inkomsten die de onderneming ontvangt uit een eenheid van elk type goederen, wordt gegeven in de tabel. 2.3.1.

Het is vereist om een ​​​​dergelijk productieplan te vinden, waarin de totale kosten maximaal zullen zijn.

Economisch en wiskundig model van het probleem Variabelen: x x, x 2, x 3, x 4 - het aantal tapijten van elk type. Objectieve functie - dit zijn de totale productiekosten die moeten worden gemaximaliseerd:

Resourcelimieten:

Laten we het probleem terugbrengen tot de canonieke vorm door extra variabelen x 5 in te voeren, x 6 en x7:

Verder zal worden aangetoond dat het optimale productieplan de vector is X * =(0; 30; 10; 0), de objectieve functiewaarde is 150, d.w.z. om de totale productiekosten te maximaliseren, moeten 30 tapijten van het tweede type en 10 tapijten van het derde type worden geproduceerd. Vervang de optimale waarden van de vector x in de beperkingen van de KZLP:

We krijgen dat de middelen "arbeid" en "apparatuur" volledig worden gebruikt, de hulpbron "grondstoffen" is in overvloed:

In dit geval x in blijkt dat er nog 200 kg grondstof over is.

Dus de belangrijkste variabelen x v x 2, x 3, x l bedoel het aantal tapijten van elk type en aanvullende variabelen x 5, x 6 hun 7 - de hoeveelheid onderbenutte middelen.

Antwoord. Optimaal productieplan X * = (0; 30;

10; 0).

Plan, of aanvaardbare beslissing, KZLP heet een vector X =(jc p x 2 ,..., x nee) voldoen aan voorwaarden (2.3.2) - (2.3.4).

Als alle componenten van de basisoplossing van het systeem van beperkingen van de KZLP niet-negatief zijn, wordt zo'n oplossing genoemd referentiebeslissing of basisplan. Het aantal positieve componenten van het referentieplan mag niet groter zijn dan T.

Het basisplan heet niet gedegenereerd, als het bevat: t positieve componenten, anders heet het ontaarden.

Optimaal plan of optimale oplossing LPP wordt een plan genoemd dat de grootste (kleinste) waarde van de lineaire functie (2.3.1) levert.

De verzameling van alle plannen van het LPP (als ze bestaan) is een convex veelvlak. Met elke hoek (uiterste) punt van het veelvlak van oplossingen komt er overeen basisplan(niet-negatieve basisoplossingen van het KZLP-stelsel van vergelijkingen). Elke baseline wordt gedefinieerd door het systeem t lineair onafhankelijke vectoren in dit systeem van P vectoren Д, Д, ..., een blz. Als er een optimaal ontwerp is, dan is er een hoekpunt van de oplossing polytoop waarop de lineaire functie zijn grootste (kleinste) waarde bereikt.

Om het optimale plan te vinden, volstaat het om alleen de ondersteuningsplannen te onderzoeken. De bovengrens van het aantal referentieplannen in een taak wordt bepaald door het aantal combinaties C t p (zie paragraaf 1.4).

Voorbeeld 2.3.3. Verkrijg een oplossing voor het probleem van het optimale gebruik van beperkte middelen (los de LP P op):

Oplossing. Laten we het probleem terugbrengen tot de canonieke vorm door extra variabelen te introduceren x3, x 4 en x 5:

Laten we alle ondersteuningsplannen van het systeem van beperkingen van deze KZLP vinden (l? - 5; / 77 - 3); hun aantal is niet groter dan 10:

Met behulp van de Jordan-Gauss-methode (zie paragraaf 1.4) schrijven we alle basisoplossingen van het stelsel vergelijkingen uit (tabel 2.3.2).

Onder de tien basisoplossingen zijn er vijf basisoplossingen:

De aangegeven referentieplannen in Fig. 1 corresponderen respectievelijk met de volgende hoekpunten en de waarden van de CF daarin:

Rijst. 2.3.1.

Volgens de theorie LP de optimale oplossing is opgenomen in de referentieplannen.

De doelfunctie bereikt dus de maximale waarde gelijk aan 2300 op het punt V op het referentievlak X5 = (70; 80; 0; 60; 0).

Antwoord. Optimaal taakplan: x (= 70, x 2 = 80, de waarde van de objectieve functie f (x v x 2) = 2300.

canonieke vorm Als het nodig is om de doelfunctie te maximaliseren, zijn alle beperkingen van het systeem vergelijkingen en wordt de niet-negativiteitsvoorwaarde opgelegd aan alle variabelen.

Het lineaire programmeerprobleem wordt gegeven in symmetrische vorm Als het nodig is om de doelfunctie te maximaliseren, zijn alle beperkingen van het systeem ongelijkheden "" (of om de doelfunctie te minimaliseren, zijn alle beperkingen van het systeem ongelijkheden "") en wordt de niet-negativiteitsvoorwaarde opgelegd aan alle variabelen.

De reeks getallen wordt genoemd ontvankelijke beslissing (plan) als het voldoet aan het LPP-systeem van beperkingen.

De verzameling van alle mogelijke oplossingen heet domein van haalbare oplossingen(ODR).

Een haalbare oplossing waarvoor de maximale (minimale) waarde van de functie wordt bereikt, wordt genoemd optimaal plan van de LPP.

De termen "plan" en "optimaal plan" zijn ontstaan ​​uit economische toepassingen.

Alle drie de vormen van LPP-notatie zijn equivalent in die zin dat er algoritmen zijn voor de overgang van de ene vorm naar de andere. Dus als er een manier is om een ​​probleem in een van de vormen op te lossen, dan kunt u altijd het optimale plan bepalen voor een probleem dat in een andere vorm wordt gegeven. Het probleem in de symmetrische vorm wordt opgelost door de grafische methode en in de canonieke vorm door de simplex-methode.

Laten we eens kijken naar algoritmen voor de overgang van de ene vorm naar de andere.

• 
  Symmetrisch  canoniek. De overgang wordt uitgevoerd door een extra niet-negatieve variabele toe te voegen aan de linkerkant van elke ongelijkheid. Als de ongelijkheid “≤” was, dan wordt de balansvariabele toegevoegd aan de linkerkant van de ongelijkheid met een “+” teken. Als de ongelijkheid "" was, dan wordt de balansvariabele toegevoegd aan de linkerkant van de ongelijkheid met een "-" teken. De nieuwe variabelen die zijn geïntroduceerd heten balans... Het probleem van het minimaliseren van de functie Z wordt vervangen door het probleem van het maximaliseren van de functie (–Z) en er wordt gebruikt dat min Z = –max (–Z).
• 
  Canoniek symmetrisch. Om zo'n overgang te implementeren, wordt een algemene oplossing van het stelsel vergelijkingen - beperkingen gevonden, de doelfunctie wordt uitgedrukt in termen van vrije variabelen. Verder, door gebruik te maken van de niet-negativiteit van de basisvariabelen, kan men ze uitsluiten van het probleem. De symmetrische vorm van het probleem zal ongelijkheden bevatten die alleen betrekking hebben op vrije variabelen en een objectieve functie die alleen afhankelijk is van vrije variabelen. De waarden van de basisvariabelen worden gevonden uit de algemene oplossing van het oorspronkelijke stelsel vergelijkingen.
• 
  Algemeen  canoniek. Elke variabele die niet aan de niet-negativiteitsvoorwaarde is onderworpen, wordt weergegeven als het verschil van twee nieuwe niet-negatieve variabelen. De ongelijkheden worden omgezet in vergelijkingen door een balansvariabele in de linkerzijde van elke ongelijkheid in te voeren op dezelfde manier als beschreven bij de overgang van symmetrische naar canonieke vorm. Het probleem van het minimaliseren van de functie Z wordt vervangen door het probleem van het maximaliseren van de functie (–Z) op dezelfde manier als beschreven bij het overgaan van de symmetrische naar de canonieke vorm.

1. Een grafische methode voor het oplossen van een lineair programmeerprobleem

De set van punten heet convex als voor twee punten van de set het een segment bevat dat ze verbindt.

voorbeeld 1

De volgende puntenreeksen in het vlak zijn convex:

De volgende puntenreeksen in het vlak zijn niet convex:

Stelling 1 Het snijpunt van een willekeurig aantal convexe verzamelingen is een convexe verzameling.

Stelling 2 Laat er twee willekeurige punten zijn en in de ruimte R N... Dan voor elk punt van het segment [ PQ] moet worden uitgevoerd:.waar.

hypervlak in de ruimte R N is een verzameling punten die aan de vergelijking voldoet. Merk op dat in het tweedimensionale geval het hypervlak een rechte lijn is.

Halve ruimte is een reeks punten die voldoet aan een van de ongelijkheden of. Het hypervlak verdeelt de punten van de ruimte in twee halve ruimten. In het tweedimensionale geval is het hypervlak een halfvlak.

Stelling 3 De halve ruimte is een convexe verzameling.

Gevolg Het snijpunt van een willekeurig aantal halve ruimten is een convexe verzameling.

veelvlak het snijpunt van een of meer halve ruimten wordt genoemd. Een veelvlak in het tweedimensionale geval wordt een veelhoek genoemd.

Voorbeeld 2

De volgende sets zijn polygonen.

Beperkte set

Onbeperkt aantal

Een punt

Lege set

Een punt van een convexe verzameling heet hoekig als het niet binnen een lijnsegment ligt dat twee andere punten uit de verzameling verbindt.

Voorbeeld 3

De hoekpunten van een driehoek zijn de hoekpunten (er zijn er drie). De hoekpunten van een cirkel zijn de punten van de cirkel die hem begrenst (er zijn er oneindig veel).

Het hoekpunt van een veelvlak wordt het genoemd top.

Beschouw een LPP gegeven in een symmetrische vorm.

Stelling 4 Het optimale ontwerp van de LPP komt overeen met het hoekpunt van de oplossing polytoop bepaald door zijn systeem van beperkingen.

Een lineair programmeerprobleem van de vorm ax = b waarbij a een matrix van coëfficiënten is, b een vector van beperkingen.
Voorbeeld:

In elk LP-probleem worden de waarden van de variabelen gezocht onder de voorwaarde dat:

• deze waarden voldoen aan een bepaald stelsel van lineaire vergelijkingen of ongelijkheden;
• bij deze waarden zou de doelfunctie minimaal of maximaal zijn.

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

Een van de universele LP-methoden is de simplex-methode, die echter kan worden toegepast als het LP-probleem een ​​canonieke vorm heeft.

Definitie... Het LP-probleem heeft een canonieke vorm als alle beperkingen van het systeem alleen uit vergelijkingen bestaan ​​(behalve ongelijkheden die de niet-negativiteit van variabelen uitdrukken) en de objectieve functie moet worden geminimaliseerd.
Een voorbeeld van zo'n LP-probleem in canonieke vorm is probleem 1 - een evenwichtig transportprobleem met een systeem van beperkingen (1) en een objectieve functie (2).
Bij de meeste economische problemen omvat het systeem van beperkingen aanvankelijk echter niet alleen vergelijkingen, maar ook ongelijkheden.

Stelling. Elk algemeen LP-probleem kan worden teruggebracht tot een canonieke vorm.
De reductie van het algemene LP-probleem tot de canonieke vorm wordt bereikt door nieuwe (ze worden aanvullende) variabelen te introduceren.
Het systeem van beperkingen (3) van dit probleem bestaat uit vier ongelijkheden. Door extra variabelen in te voeren ja 1 ≥ 0, ja 2 ≥ 0, ja 3 ≥ 0, ja 4 ≥ 0, u kunt naar het systeem van beperkingen gaan:

Deze extra variabelen ja ik heb een absoluut duidelijke economische betekenis, namelijk de hoeveelheid ongebruikte bedrijfstijd (stilstand van de machine) I-de soort).
Als machines van het eerste type bijvoorbeeld alle 18 uur werkten, dan is x + y = 18, dus y 1 = 0. Maar we erkennen de mogelijkheid van onvolledig gebruik van de bedrijfstijd van de eerste machine x + ja<18. В этом случае ja 1 wordt positief en kan worden beschouwd als een niet-gebruikte tijdslimiet. Als u bijvoorbeeld de oplossing voor dit probleem kent uit paragraaf 3.3.2, x = 12, ja= 6, kunnen we uit het systeem van beperkingen (3.9) concluderen dat ja 1 = ja 2 = ja 3 = 0, en ja 4 = 12 - 6 = 6. Dat wil zeggen, machines van het eerste, tweede, derde type gebruiken hun arbeidstijd volledig. Maar de vierde auto is slechts half beladen, 6 uur, en staat stil volgens het opgegeven optimale plan. Misschien wil het hoofd van de onderneming na dergelijke conclusies het met ander werk laden, het voor deze tijd verhuren, enz.
Dus door extra variabelen te introduceren, kunnen we elke beperking van het ongelijkheidstype reduceren tot een vergelijking.

Denk aan het mengselprobleem. Het systeem van beperkingen is als volgt:
De ongelijkheden werden naar "meer" gekeerd, daarom moeten extra variabelen y 1, y 2, y 3 ≥ 0 worden geïntroduceerd en moeten ze van de linkerkant worden afgetrokken om ze gelijk te maken aan de rechterkant. We krijgen het systeem van beperkingen in de canonieke vorm:
De variabelen y i zullen ook economisch zinvol zijn. Als u zich de praktische inhoud van het probleem herinnert, betekent de variabele y 1 de hoeveelheid overtollige stof A in het mengsel, y 2 - de hoeveelheid overtollige stof V in het mengsel, ja 3 - overschot MET in het mengsel.
Het probleem van het vinden van de maximale waarde van de doelfunctie kan worden teruggebracht tot het vinden van het minimum voor de functie - F gezien de vanzelfsprekendheid van de bewering max F = –min (- F). Kijk naar de foto: als op een gegeven moment x= x 0 functie ja= F(x) zijn maximum bereikt, dan is de functie ja= –F(x), symmetrisch om de as OS, op hetzelfde punt x 0 bereikt een minimum, en F maximaal = - (- F min) bij x = x 0 .

Gevolgtrekking. Om het LP-probleem in een canonieke vorm weer te geven, is het noodzakelijk:

• ongelijkheden die zijn opgenomen in het systeem van beperkingen van het probleem, worden omgezet in vergelijkingen door extra variabelen te introduceren;
• als de objectieve functie F→ max (gemaximaliseerd), het wordt vervangen door een functie - F→ min (die is geminimaliseerd).