Verschillende vormen van LPP-notatie (algemeen, canoniek, symmetrisch)

laat een reactie achter 6,950

Pagina 1

De canonieke vorm van het probleem wordt gekenmerkt door de volgende drie kenmerken: 1) een homogeen stelsel van beperkingen in de vorm van een stelsel van vergelijkingen; 2) homogene voorwaarden van niet-negativiteit, die van toepassing zijn op alle variabelen die bij het probleem betrokken zijn, en 3) maximalisatie van een lineaire functie. In dit probleem worden alle drie deze functies geschonden.

De canonieke vorm van het lineaire programmeerprobleem is handig omdat het gemakkelijk is om het beginpunt van het haalbare gebied te vinden.

Beschouw de canonieke vorm van het lineaire programmeerprobleem en de Jordan-Gauss-eliminatiemethode.

De canonieke vorm van een lineair programmeerprobleem blijkt vaak handig te zijn.

Bij het transformeren van het systeem van beperkingen naar de canonieke vorm van het lineaire programmeerprobleem, moeten ongelijkheden (12) en (13) worden vervangen door gelijkheden. Hiervoor worden aanvullende niet-negatieve variabelen geïntroduceerd.

Bewijs dat paarsgewijs pendelende reële matrices gelijktijdig worden gereduceerd tot de canonieke vorm van probleem 1128 door een gelijkenistransformatie met behulp van een orthogonale matrix.

In wezen kan (4) - (5) worden beschouwd als de canonieke vorm van een niet-lineair programmeerprobleem, aangezien de methoden gepresenteerd in Ch. Gewoonlijk wordt bij problemen van niet-lineair programmeren de eis voor het gehele aantal variabelen niet naar voren gebracht.

Soorten beperkingen en methoden voor hun transformatie.

De canonieke vorm van het probleem wordt gekenmerkt door de homogeniteit van het stelsel van beperkingen in de vorm van een stelsel van vergelijkingen; het maximaliseren van de objectieve functie; de toestand van niet-negativiteit van alle variabelen die bij het probleem betrokken zijn.

De canonieke vorm van problemen voegt geen extra functies toe aan het beschouwde rekenschema.

Laten we eerst de tweede canonieke vorm van het minimumprobleem beschouwen.

Het simplex-meta-algoritme kan in twee fasen worden verdeeld. In de eerste fase wordt de basisoplossing gevonden door de variabelen te elimineren. Als het wordt gevonden, hebben we de canonieke vorm van het probleem voor de overgang naar de tweede fase. In de tweede fase wordt gecontroleerd of er een begrensd optimum is. Als die er is, worden de toelaatbare basisoplossingen bepaald en wordt de optimale gekozen.

Als het probleem in de canonieke vorm is opgelost, wordt slechts een deel van de in de tweede alinea geïntroduceerde bewerkingen gebruikt. Dus voor het canonieke minimumprobleem wordt alleen het geval van sectie 3.4.1 gerealiseerd, en alleen de bewerkingen van cyclische permutatie van kolommen, het vegen van een kolom door de verticale grenszone, correctie van structurele schendingen en een deel van de afkapbewerking zijn nodig zijn. Symmetrisch, wanneer het canonieke probleem maximaal wordt opgelost, wordt alleen het geval van paragraaf 3.4.2 gerealiseerd, en zijn bewerkingen van cyclische rijpermutatie, een rij door de horizontale grenszone vegen, het corrigeren van structurele schendingen en een ander deel van de inkortbewerking nodig . Anders voegt de canonieke vorm van het probleem geen extra bijzonderheden toe.

In het eerste deel van de inleiding werd getoond hoe een algemeen lineair programmeerprobleem kan worden teruggebracht tot een van de canonieke vormen. Voor canoniek (aan de andere kant is de beschrijving van de sequentiële verbeteringsmethode formeel vereenvoudigd, omdat het niet nodig is om twee varianten van schending van de optimaliteitsvoorwaarden en twee varianten van naar het volgende hoekpunt te gaan). toepassing van de methode op de canonieke vormen van het probleem blijkt de voorkeur te hebben, en in deze sectie zullen we ons concentreren op de varianten van de methode die verkregen zijn voor bepaalde lineaire programmeerproblemen.

Pagina's: 1

lineaire programmeerproblemen

2.1. Definitie en vorm van deelname

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 weergegeven in de vorm van coördinaten, vectoren of matrixnotaties.

a) het canonieke LP-probleem in coördinaatvorm 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. Reductie van het algemene lineaire probleem

programmeren naar canonieke vorm

Bij het samenstellen van wiskundige modellen van economische problemen worden beperkingen voornamelijk gevormd tot systemen van ongelijkheden. Daarom is het noodzakelijk om van hen over te gaan naar stelsels van vergelijkingen. Beschouw bijvoorbeeld de lineaire ongelijkheid

en wat waarde toevoegen aan de linkerkant ervan
zodat ongelijkheid gelijkheid wordt.

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

Stelling 2.2.1. op elke beslissing
ongelijkheid (2.2.1) komt overeen met een unieke oplossing van vergelijking (2.2.2) en de ongelijkheid
, en, omgekeerd, aan elke oplossing van vergelijking (2.2.2) met
match oplossing
ongelijkheid (2.2.1).

Een bewijs. laten zijn
oplossing van ongelijkheid (2.2.1). Vervolgens. Laten we het nummer nemen
... Het is duidelijk dat
... Substitueren in vergelijking (2.2.2), krijgen we

Het eerste deel van de stelling is bewezen.

Laat nu de vector voldoet aan vergelijking (2.2.2) met
, d.w.z. het weggooien van de niet-negatieve waarde aan de linkerkant van de laatste gelijkheid
, krijgen we, enz.

De bewezen stelling stelt dus feitelijk de mogelijkheid vast om elk LP-probleem tot de canonieke vorm te reduceren. Om dit te doen, volstaat het om een extra niet-negatieve variabele in elke beperking te introduceren, die de vorm heeft van een ongelijkheid. Bovendien komen deze variabelen in ongelijkheden van de vorm (1.2.1) binnen met het teken "+", en in ongelijkheden van de vorm (1.2.2) - met het teken "-". Extra variabelen worden in de doelfunctie geïntroduceerd met nulcoëfficiënten en hebben daarom geen invloed op de waarde ervan.

Opmerking. In wat volgt, zullen we de simplex-methode voor het canonieke LP-probleem in de studie van de objectieve functie voor een minimum beschrijven. In die taken waar je het maximale moet vinden
, het is voldoende om de functie te overwegen:
, vind de 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

lineair programmeren

3.1. Algemene concepten, voorbeelden

In gevallen waarin er slechts twee variabelen in het LP-probleem zijn, kan een grafische methode worden gebruikt om het op te lossen. Laat het nodig zijn om de maximale (minimale) waarde van de functie te vinden
met beperkingen

(3.1.1)

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

Het snijpunt van deze halve vlakken vormt een bepaald gebied, de oplossingspolygoon genoemd, wat een convexe verzameling is. (Stel dat het systeem van beperkingen compatibel is en dat de veelhoek van zijn oplossingen begrensd is.) Om de optimale oplossing te vinden tussen de haalbare oplossingen, worden niveaulijnen en steunlijnen gebruikt.

Niveau lijn heet de lijn waarop de objectieve functie een constante waarde aanneemt. De niveaulijnvergelijking heeft de vorm

, waar
... Alle niveaulijnen lopen evenwijdig aan elkaar. hun normale
.

Ondersteuningslijn: er wordt een niveaulijn genoemd, die ten minste één gemeenschappelijk punt heeft met het gebied van haalbare oplossingen, ten opzichte waarvan dit gebied in een van de halve vlakken ligt (Fig. 1).

De waarden
toename in de richting van de vector
... Daarom is het noodzakelijk om de waterpaslijn te verplaatsen
in de richting van deze vector evenwijdig aan zichzelf aan de referentielijn L 1 in het maximale probleem en in de tegenovergestelde richting - in het minimale probleem (naar de referentielijn L 2).

Laten we een oplossing geven voor voorbeeld 1.1. Bedenk dat je het maximum van de functie moet vinden
met beperkingen

Oplossing. We bouwen het gebied van haalbare oplossingen. Laten we de beperkingen van het probleem opsommen. In een rechthoekig Cartesisch coördinatensysteem (Fig. 2) bouwen we een rechte lijn

overeenkomend met beperking (1). We vinden welk van de halve vlakken waarin deze lijn het gehele coördinatenvlak verdeelt het domein is van oplossingen voor ongelijkheid (1).

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

en het oplossingsdomein van beperking (2). Vind het gemeenschappelijke deel van de halve vlakken van de oplossingen, rekening houdend met beperkingen (3). Het verkregen gebied van haalbare oplossingen wordt in Fig. 2 gemarkeerd met een donkere kleur.

Een niveaulijn bouwen
en vector
die de richting van de toename van de functie aangeeft en loodrecht op de rechte lijn

... Niveau lijn
parallel aan zichzelf in de richting bewegen
naar de referentielijn. We verkrijgen dat de objectieve functie zijn maximum bereikt op het punt
snijpunt van lijnen en ... Het stelsel vergelijkingen van deze rechte lijnen oplossen
, krijgen we de coördinaten van het punt
... daarom, en
,
optimale oplossing.

Voorbeeld 3.1. Vind het minimum van een functie
onder een systeem van beperkingen

Oplossing. We bouwen het gebied van toelaatbare oplossingen (zie Fig. 3), de vector
en een van de niveaulijnen
... Verplaats de waterpaslijn in de tegenovergestelde richting
, aangezien het probleem van het vinden van het minimum van de functie wordt opgelost. In dit geval gaat de steunlijn door punt A (Fig. 3), waarvan de coördinaten te vinden zijn in de oplossing van het systeem

Dus,
... Wij rekenen.

Opmerking. In feite is de vorm van het gebied van haalbare oplossingen en de doelfunctie
het LP-probleem kan een enkele oplossing hebben, een oneindige reeks oplossingen of geen enkele oplossing.

Voorbeeld 3.2. Vind het minimum van een functie
met beperkingen

Oplossing. We bouwen het gebied van toegestane oplossingen, de normaal van de niveaulijnen
en een van de niveaulijnen die raakvlakken heeft met dit gebied. De niveaulijn verplaatsen in de tegenovergestelde richting van de normale , aangezien het probleem van het vinden van het minimum van de functie wordt opgelost. Niveau lijn normaal
en de normaal van de grenslijn , in de richting waarin de niveaulijnen bewegen, zijn evenwijdig, omdat hun coördinaten evenredig zijn
... Daarom valt de steunlijn samen met de grenslijn gebied van haalbare oplossingen en loopt door twee hoekpunten van dit gebied en (afb. 4).

Het probleem heeft een oneindige reeks optimale oplossingen, die punten van het segment zijn
... deze punten
,
vinden we door de overeenkomstige stelsels van vergelijkingen op te lossen:

;
;

,
;
,
;

;
.

Wij rekenen.

Antwoord geven:
Bij
,
.

Voorbeeld 3.3. Los een lineair programmeerprobleem op

Oplossing. We bouwen de regio van haalbare oplossingen, de normale
en een van de niveaulijnen. In dit probleem is het nodig om het maximum van de doelfunctie te vinden, dus de niveaulijn bewegen in de richting van de normaal. Omdat in deze richting het gebied 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.

Antwoord geven:
.

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.

Uitspraak. 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) l-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 waren gericht op "meer", daarom introduceren we extra variabelen y 1, y 2, y 3 ≥ 0, ze moeten van de linkerkant worden afgetrokken om het gelijk te maken met 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 aangezien de bewering duidelijk is, 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 .

Uitgang. 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).

Elk lineair programmeerprobleem kan worden teruggebracht tot een lineair programmeerprobleem in canonieke vorm. Om dit te doen, moet je in het algemeen het probleem van maximalisatie kunnen herleiden tot het probleem van minimalisatie; ga van ongelijkheidsbeperkingen naar gelijkheidsbeperkingen en vervang variabelen die niet voldoen aan de niet-negativiteitsvoorwaarde. Maximalisatie van een functie is gelijk aan minimalisatie van dezelfde functie, genomen met het tegenovergestelde teken, en vice versa.

De regel voor het reduceren van een lineair programmeerprobleem tot de canonieke vorm is als volgt:

als het in het oorspronkelijke probleem vereist is om het maximum van een lineaire functie te bepalen, dan moet je het teken veranderen en het minimum van deze functie zoeken;
als de rechterkant van de beperkingen negatief is, moet deze beperking worden vermenigvuldigd met -1;
als er ongelijkheden zijn tussen de beperkingen, dan worden ze door het introduceren van extra niet-negatieve variabelen omgezet in gelijkheden;
als een of andere variabele x j geen tekenbeperkingen heeft, dan wordt het (in de objectieve functie en in alle beperkingen) vervangen door het verschil tussen twee nieuwe niet-negatieve variabelen:
x 3 = x 3 + - x 3 - , waar x 3 +, x 3 - ≥ 0 .

voorbeeld 1... Het lineaire programmeerprobleem terugbrengen tot de canonieke vorm:

min L = 2x 1 + x 2 - x 3;
2x 2 - x 3 ≤ 5;
x 1 + x 2 - x 3 -1;
2x 1 - x 2 ≤ -3;
x 1 0; x 2 0; x 3 ≥ 0.

We introduceren in elke vergelijking van het systeem van beperkingen de nivelleringsvariabelen x 4, x 5, x 6... Het systeem wordt geschreven in de vorm van gelijkheden, en in de eerste en derde vergelijking van het systeem van beperkingen de variabelen x 4, x 6 worden aan de linkerkant ingevoerd met het "+"-teken, en in de tweede vergelijking de variabele x 5 ingevoerd met een "-" teken.

2x 2 - x 3 + x 4 = 5;
x 1 + x 2 - x 3 - x 5 = -1;
2x 1 - x 2 + x 6 = -3;
x 4 ≥ 0; x 5 0; x 6 ≥ 0.

Vrije termen in canonieke vorm moeten positief zijn, hiervoor vermenigvuldigen we de laatste twee vergelijkingen met -1:

2x 2 - x 3 + x 4 = 5;
-x 1 - x 2 + x 3 + x 5 = 1;
-2x 1 + x 2 - x 6 = 3.

In de canonieke vorm van het schrijven van lineaire programmeerproblemen moeten alle variabelen in het systeem van beperkingen negatief zijn. Laten we aannemen dat x 1 = x 1 "- x 7 , waar x 1 "≥ 0, x 7 ≥ 0 .

Door deze uitdrukking in het systeem van beperkingen en de objectieve functie in te voeren en de variabelen in oplopende volgorde van de index te schrijven, krijgen we een lineair programmeerprobleem gepresenteerd in de canonieke vorm:

Lmin = 2x 1"+ x 2 - x 3 - 2x 7;
2x 2 - x 3 + x 4 = 5;
-x 1 "- x 2 + x 3 + x 5 + x 7 = 1;
-2x 1"+ x 2 - x 6 + 2x 7 = 3;
x 1 "≥ 0; x ik ≥ 0, ik = 2, 3, 4, 5, 6, 7.

Optimaliteitsvoorwaarde voor het basisplan van het canonieke LP-probleem. Simplex-methode en zijn convergentie.

De simplex-methode is: universeel, omdat het je in staat stelt om bijna elk lineair programmeerprobleem op te lossen dat is geschreven in canonieke vorm.

Het idee van de simplex methode consequente verbetering van het plan, ligt in het feit dat, uitgaande van een initiële ondersteuningsoplossing, consequent gerichte beweging door de ondersteunende oplossingen van het probleem naar de optimale.

De waarde van de doelfunctie neemt bij deze beweging voor taken niet maximaal af.

Aangezien het aantal ondersteuningsoplossingen eindig is, verkrijgen we na een eindig aantal stappen de optimale ondersteuningsoplossing.

Een niet-negatieve basisoplossing wordt een referentieoplossing genoemd.

Simplex Methode Algoritme

1. Het wiskundige model van het probleem zou moeten zijn: canoniek. Als het niet-canoniek is, moet het in de canonieke vorm worden gebracht.

2. Zoek de originele ondersteuningsoplossing en controleer deze op optimaalheid.
Vul hiervoor de simplextabel 1 in.
We vullen alle rijen van de tabel van de 1e stap in volgens de gegevens van het systeem van beperkingen en de doelfunctie.

De volgende gevallen zijn mogelijk bij het oplossen van problemen op: maximaal:

1. Als alle coëfficiënten van de laatste rij van de simplextabel Dj 0, dan gevonden

oplossing optimaal.

2 Indien ten minste één coëfficiënt Dj £ 0, maar voor de overeenkomstige variabele is er geen enkele positieve evaluatieratio, dan is de oplossing we stoppen met taken, aangezien F (X) ® , d.w.z. de objectieve functie is niet beperkt op het gebied van haalbare oplossingen.

Als ten minste één coëfficiënt van de laatste rij negatief is, en voor de corresponderende variabele is er ten minste één positieve evaluatieve relatie, dan moet je gaan naar een andere referentieoplossing.

4.E indien er zijn verschillende negatieve coëfficiënten in de laatste regel, dan naar de kolom met basisvariabelen(Bp) introduceren dat variabele wat overeenkomt met de grootste negatieve coëfficiënt in absolute waarde.

5. Indien ten minste één coëfficiënt Dk< 0 ,dan k - dat kolom die we accepteren voor de presentator.

6. Voor leidende lijn we accepteren degene die overeenkomt met minimaal gratis lid houding bi naar positieve coëfficiënten leidend, k - dat kolom.

7. Een element dat zich op het snijpunt van voorlooprijen en een kolom bevindt, heet leidend element.

Simplextabel vullen 2 :

· vul de basiskolom met nullen en enen

· herschrijf de leidende regel door deze te delen door het leidende element

Als de eerste rij nullen heeft, kunnen de bijbehorende kolommen worden overgebracht naar de volgende simplex-tabel

· de rest van de coëfficiënten worden gevonden door de regel "rechthoek"

We krijgen een nieuwe ondersteuningsoplossing, die we controleren voor optimaal:

Als alle coëfficiënten van de laatste rij Dj 0, dan de gevonden oplossing maximaal.

Zo niet, vul dan de simplextabel van stap 8 in, enzovoort.

Als de objectieve functie V (X) vereist vinden minimale waarde, dan het criterium optimaliteit van het probleem is een niet-positieve kansen NS j voor alle j = 1,2, ... n.

Convergentie van de simplex-methode. Degeneratie bij LP-problemen. De belangrijkste eigenschap van elk computationeel algoritme is convergentie, dat wil zeggen de mogelijkheid om in de loop van de toepassing de gewenste resultaten (met een bepaalde nauwkeurigheid) in een eindig aantal stappen (iteraties) te verkrijgen.

Het is gemakkelijk in te zien dat problemen met de convergentie van de simplex-methode mogelijk kunnen optreden in het stadium van het kiezen van de waarde van r (item 2 ") in het geval dat dezelfde minimumwaarden van de verhouding

wordt voor meerdere rijen van de tabel T (q) tegelijkertijd bereikt. Dan zal bij de volgende iteratie kolom b (β (q + 1)) nul elementen bevatten.

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.