Enkel metode med kunstige variable eksempler. Løsning af lineære programmeringsproblemer ved hjælp af den kunstige basismetode

Løsningen af ​​problemet lineær programmering Simplexmetoden begynder med at finde en referenceplan.

Lad os overveje det tredje tilfælde med at konstruere den indledende referenceplan (den første og anden er beskrevet i afsnit 2.1).

Lad begrænsningssystemet have formen

Lad os gå videre til kanonisk form ved at indføre yderligere variabler
, som vi trækker fra venstre side af systemulighederne. Lad os få systemet

.

Nu har begrænsningssystemet ikke en foretrukken form, da yderligere variabler x n + jeg ind i venstre side (med b jeg 0) med koefficienter lig med –1. I dette tilfælde er den såkaldte kunstigt grundlag ved at gå til M-opgave.

Kunstige variable tilføjes til venstre side af lighedsbegrænsninger, der ikke har en foretrukken form w jeg. Variabler i målfunktionen w jeg indtastet med en koefficient M i tilfælde af løsning af problemet som minimum og med en koefficient – M– for det maksimale problem, hvor M- stor positivt tal. Det resulterende problem kaldes M-opgave, svarende til den originale. Hun har altid et foretrukket udseende.

Lad det originale lineære programmeringsproblem have formen

;
;

Imidlertid har ingen af ​​begrænsningerne en foretrukken variabel. M-opgave vil blive skrevet som følger:

;

I dette tilfælde refererer "–" indlogningsfunktionen (10) til det maksimale problem. Opgave (10)–(12) har en foretrukken form. Hendes initial referenceplan ligner

.

Hvis nogle af ligningerne (8) har en foretrukken form, bør kunstige variable ikke indføres i dem.

Sætning 5. Hvis det er optimalt x engros 

M-problemer (10)–(12) alle kunstige variable
så planen
er den optimale plan for det oprindelige problem (7)–(9).

Sætning 6 (et tegn på uforenelighed af begrænsningssystemet ) . Hvis det er optimalt M-problem, mindst en af ​​de kunstige variable er forskellig fra nul, så er systemet af begrænsninger for det oprindelige problem inkonsekvent.

Hvornår M-opgaveindekslinje simplex bord bryde det op i to. Den første linje indeholder de frie udtryk for udtrykkene
Og
, og i den anden – koefficienter indeholdende M. Optimitetstegnet kontrolleres først mod anden linje. Det bestemmer også den variabel, der skal indgå i grundlaget. Da kunstige variable er udelukket fra grundlaget, kan de tilsvarende kolonner af elementer udelades. Dette forklares med, at kunstige variable ikke returneres til grundlaget, og derfor vil de tilsvarende kolonner ikke længere være nødvendige. Efter at have elimineret alle kunstige variabler fra grundlaget, fortsætter processen med at finde den optimale plan ved at bruge den første linje objektiv funktion.

Eksempel 4. Løs et lineært programmeringsproblem ved hjælp af et kunstigt grundlag

Den første begrænsning har en foretrukken variabel x 3, men den anden er ikke. Derfor introducerer vi en kunstig variabel i den w 1 . Vi kommer til M- opgave

Lad os tilføje en betingelse M- problemer i en simplekstabel. 5. Den oprindelige referenceplan ser ud x 0 = (x 1 ;x 2 ;x 3 ;x 4 ;w 1) = (0; 0; 2; 0; 12),z(x 0) = 0 – 12M.

Tabel 5

	Med B
z j – c j

Lad os komme med de nødvendige forklaringer.

Det er praktisk at opdele indekslinjen i to. I den første af dem er de frie led for udtrykkene  0 = c B EN 0 и j =c B EN j –c j, og i den anden – koefficienter indeholdende M. For eksempel til bord. 5:

Vi kontrollerer først optimalitetstegnet ved hjælp af den anden linje i indekslinjen. Da der er negative vurderinger i det, planen x 0 er ikke optimalt.

Lad os gå videre til et nyt bord. 6.

Den løsende kolonne findes ved max(|–3 M|; |–4M|} = 4M, er opløsningslinjen bestemt af
. Derfor er 1 det aktiverende element.

Tabel 6

	Med B
z j – c j

Der er ingen negative vurderinger i indekslinjen. Derfor er referenceplanen (0; 2; 0; 0; 4) optimal ifølge optimalitetskriteriet. Men da i den optimale plan den kunstige variabel w 1 er ikke lig med 0, så ved sætning 6 er systemet af begrænsninger for det oprindelige problem inkonsekvent. Problemet har ingen løsning.

Svar: der er ingen beslutning.

Eksempel 5. Løs problemet ved hjælp af et kunstigt grundlag

Lad os organisere optagelsen af ​​den oprindelige opgave. Multiplicer den anden ulighed med –1:

Lad os reducere problemet til dets kanoniske form. Vi får

Den første og fjerde begrænsning har foretrukne variabler, men den anden og tredje har ikke. Derfor introducerer vi kunstige variable i dem w 1 og w 2. Vi kommer til M- opgave

Lad os tilføje en betingelse M- problemer i en simplekstabel. 7. Den oprindelige referenceplan ser ud x 0 = (0; 0; 10; 0; 0; 4; 3; 9),z(x 0) = 0 + 12M.

Tabel 7

	Med B
z j – c j

Vi løser problemet til et minimum. Vi kontrollerer først optimalitetstegnet ved hjælp af den anden linje i indekslinjen. Da der er en positiv vurdering i det, planen x 0 er ikke optimalt. Lad os gå videre til et nyt bord. 8.

Tabel 8

		Med B

Indtil nu har vi grundigt overvejet problemet, hvis løsning blev udført på grundlag af simplexmetodens enkleste algoritme, da alle begrænsningerne var af formen mindre end eller lig med. I dette tilfælde yderligere opgavevariabler danne et enhedsgrundlag. Men det kan vise sig, at begrænsningssystemet præsenteres i kanonisk form, men det er ikke reduceret til et enhedsgrundlag.

Når man løser sådanne problemer, blev det indført kunstig basis metode. Det er især praktisk, når antallet af variable væsentligt overstiger antallet af ligninger.

Algoritme til at løse problemet simpleks metode Lad os se på et eksempel med et kunstigt grundlag.

Eksempel 1

Find det maksimale Z=4X1+2X2+X3

3Х1+2Х2+Х3=15

Хj³0, j=1,...,3

Lad os gå videre til den kanoniske form:

X1+X2+X3-X4=8

2Х1+Х2+Х3+Х5=8

3Х1+2Х2+Х3=15

Хj³0, j=1,...,5

Zmax=4X1+2X2+X3+0×X4+0×X5

Dette system restriktioner har ikke en enhedsbasis, da den yderligere variabel X4 har en koefficient på minus én, og den tredje begrænsning var repræsenteret af en ligning og ikke har en basisvariabel. For at have et enhedsgrundlag indfører vi i de tilsvarende restriktioner kunstige variable y1 og y2 med positive koefficienter (+1).

Det skal bemærkes, at kunstige variabler kun indføres til den matematiske formalisering af problemet. Derfor skal beregningsskemaet være sådan, at kunstige variable ikke kan indgå i den endelige løsning blandt grundvariablerne. Til dette formål indføres for kunstige variable i objektivfunktionen en koefficient M, der angiver en meget stort antal. I praksis (især når man løser et problem på en computer) tager de i stedet for M et specifikt stort tal, for eksempel 10000. Når man løser et problem til det maksimale, indtastes denne koefficient desuden i den objektive funktion med et minus tegn, og ved løsning til et minimum, med et plustegn. Nu skal vi løse T (M)-problemet, hvis objektivfunktion indeholder Z-opgavens objektivfunktion og kunstige variable med en koefficient ±M, dvs.

T=Z-M S yi, når man løser for maksimum af den objektive funktion og

T=Z+M S y, når man løser for minimum af objektivfunktionen

I vores tilfælde:

X1+X2+X3-X4+y1=8

2Х1+Х2+Х3+Х5=8

3Х1+2Х2+Х3+y2=15

Хj³0, j=1,...,5

Тmax= 4X1+2X2+X3+0×X4+0×X5 - M(y1+y2)

Dette problem er løst i simplex-tabeller, men for nemheds skyld er objektivfunktionen opdelt i 2 linjer:

I den første linje nedskriver vi estimater, der ikke indeholder koefficienten M;

Den anden linje indeholder estimater for hver fri variabel, der indeholder koefficienten M.

Beregningen af ​​elementerne (score) af disse to linjer udføres i henhold til formel (2). Eneste forskel:

Ved beregning af Z-rækkeestimater skal der tages hensyn til koefficienterne Cj, der indgår i Z-funktionen;

Ved beregning af M-line estimater tages der ikke højde for denne koefficient, og M tages ud som en fælles faktor.

For at T-opgaven og Z-opgaven er ens, er det nødvendigt, at yi er lig med nul. Derfor, så længe y i ikke er nul, vælges løsningskolonnen baseret på estimaterne i den anden række ved hjælp af simplex-metodens algoritme.

Først efter at alle y i bliver lig med nul, vil yderligere beregning blive udført ved hjælp af den første indekslinje, dvs. -almindelig Z-opgave.

Desuden, når den kunstige variabel er afledt fra basis, vil vi smide den ud af simplex-tabellen, og den næste simplex-tabel vil ikke have den tidligere opløsningskolonne.

Der er en sammenhæng mellem de optimale løsninger af M-problemet og Z-problemet, etableret ved følgende sætning:

1. Hvis i optimal løsning I M-problemet er alle kunstige variable (y i) lig med nul, så vil denne løsning være den optimale løsning på Z-problemet.

2. Hvis i den optimale løsning af M-problemet mindst én af de kunstige variable er forskellig fra nul, så har Z-problemet ingen løsning på grund af inkompatibiliteten af ​​systemet af begrænsninger.

3. Hvis M-problemet viser sig at være uløseligt (T®+¥ eller -¥), så er det oprindelige problem også uløseligt enten på grund af inkompatibiliteten af ​​systemet af begrænsninger eller fordi funktionen Z er ubegrænset.

Lad os lave den første simplex-tabel. Ved løsning ved hjælp af M-metoden kan opløsningskolonnen i M-rækken vælges ikke efter det største negative estimat i absolut værdi (når der løses for maksimum) og ikke efter det største positive estimat (når der løses for minimum) ), men ifølge den, der viser Y hurtigere fra basis. I i dette eksempel den løsende kolonne vil være kolonnen for den frie variabel X2 med en score på (-3).

Tabel 3.1.

Første simpleksbord

Påfyldning af Z-linjen udføres i henhold til formel (2):

a00 = 0 × 8– 0 = 0

a01 =0 × 2– 4 = -4

a02 =0 × 1– 2 = -2

a03 =0 × 1– 1 = -1

а02 =0 × 0– 0 = 0

Udfyldelse af M-linjen:

а¢00 = -М × 8 + (–М) × 15 = -23М

a¢01 = -M × 1 + (–M) × 3 = -4M

а¢02 = -М × 1 + (–М) × 2= -3М

а¢03 = -М × 1+ (–М) × 1 = -2М

а¢04 = -М ×(-1)+ (–М) × 0 = 1М

Vi tager M ud som en fælles faktor.

Den sidste kolonne i opløsningslinjen indeholder 0, så kolonnen i den frie variabel X4 overføres uden ændringer.

Tabel 3.2.

Andet simpleksbord

I den anden tabel får vi en degenereret løsning, da vi får to identiske minimale simplex-relationer. Derfor finder vi forholdet mellem elementerne i kolonnen ved siden af ​​den opløsende til elementerne i den opløsende kolonne under hensyntagen til tegnet.

Tabel 3.3.

Tredje simplex bord

Nu løser vi ved hjælp af den sædvanlige simplex-metode.

Tabel 3.4.

Fjerde simpleksbord

St.P	Cj
B.P.	Ci	ai0	X5	X4
X3				-1
X1
X2			-2	-1
Z

I evalueringslinjen er alle elementer ikke-negative værdier, derfor opnås den optimale løsning:

Zmax=15 Xopt(0,7,1,0,0)

Eksempel 2

Problemet blev løst til minimum (Z®min) af objektivfunktionen. Ved sidste iteration fik vi følgende tabel:

Tabel 3.5.

Seneste simplex bord

St.P	Cj
B.P.	Ci	ai0	X1	X3	X4
U1	M	-1/2	-1/2	-1/2	-1
X5		1/2	1/2	1/2
X2		15/2	3/2	1/2
Z			-1
	M	-1/2	-1/2	-1/2	-1

I T-problemet blev der opnået en optimal løsning, da der ikke er flere positive estimater i M-rækken, dvs. valget af en opløsende kolonne er umulig, og U1 er i grundlaget. I dette tilfælde har det oprindelige problem ingen løsning pga begrænsningssystemets uforenelighed.

En nødvendig betingelse for at bruge simplex-metoden er tilstedeværelsen af ​​en referenceplan, det vil sige en acceptabel grundlæggende løsning kanonisk system ligninger. For at gøre dette skal følgende betingelser være opfyldt:

• systemet skal have en kanonisk (trin)struktur;
• der er kun lighedsbegrænsninger;
• højre side af begrænsningerne er positive;
• problemvariablerne er positive.

Uden disse betingelser er det umuligt at få en referenceplan. Men i reelle problemer er de anførte betingelser ikke altid opfyldt.

Der er en særlig metode kaldet et kunstigt grundlag, som giver dig mulighed for at få en indledende referenceplan i ethvert lineært programmeringsproblem.

Lad det lineære programmeringsproblem reduceres til standardform:

Lad alle /? > 0, men nogle eller alle basisvariablerne er negative, X; 0. Der er derfor ingen referenceplan.

Lad os supplere begrænsningsligningerne med kunstige variable (vi antager, at alle x j j - 1, P).

Lad os introducere T variable (efter antal ligninger): x lM dem der er med nyt system vil være grundlæggende og negativ X-

Som et resultat får vi følgende tilsvarende problem.

Her er variablerne x n+i ikke har noget at gøre med oprindelige problem lineær programmering. De tjener kun til at opnå en referenceplan og kaldes kunstige variable. Og den nye

målfunktionen /(.t) er dannet for fuldstændigheden af ​​problemet.

I et optimalt referencedesign bør de kunstige variable være nul. Ellers vil betingelserne for det oprindelige problem blive overtrådt.

I den indledende referenceplan er de kunstige variable grundlæggende, det vil sige, at de ikke er lig med nul, og i den optimale plan skal de kunstige variable være lig nul. Det betyder, at kunstige variable optimalt bør blive frie. Denne oversættelse er hovedideen med metoden: oversættelsen af ​​kunstige variabler fra grundlæggende variabler til frie. Lad os se på mekanismen for en sådan oversættelse ved hjælp af et eksempel.

Lad os omskrive ZLP i standardform. For at gøre dette introducerer vi yderligere variabler x), x A, x 5, x 6 og skriv opgaven i kanonisk form.

Frie variable x, x 2 = 0, i hvilket tilfælde de grundlæggende variabler vil tage værdierne x 3 = -5, x 4 = -5, x 5 = 7, x 6 = 9. Da nogle af grundvariablerne er negative, er der derfor ingen referenceplan. For at opnå den indledende referenceplan introducerer vi variablerne x 7, x 8 i de to første begrænsningsligninger og formulerer et hjælpeproblem:

Det indledende grundlag er således

Simplex bord med kunstigt underlag

	x4

Lad os nedskrive rækkefølgen af ​​referenceplaner.

For de første tre trin A til beregnes kun ud fra kunstige variable, der indgår i den kunstige objektivfunktion /(x) = x 7 + x 8 med koefficient c, = 1.

I det tredje trin er kunstige variable udelukket, da alle A til er positive.

Så simplex-metoden med introduktion af kunstige variable inkluderer to faser.

Dannelse og beslutning hjælpeopgave LP med introduktion af kunstige variable. De kunstige variable i det indledende referencedesign er grundlæggende. En kunstig objektiv funktion omfatter kun kunstige variable. Ved modtagelse af tilstødende referenceplaner overfører vi kunstige variable fra basale til frie. Som et resultat blev den optimale referenceplan for hjælpeproblemet /(x) = 0 opnået.

Den optimale referenceplan for hjælpe-LP-problemet er den indledende referenceplan for hoved-LP-problemet. Problemet løses for den oprindelige objektivfunktion /(x) ved hjælp af den sædvanlige simpleksmetode.

Noter

• 1. Indførelse af kunstige variable er påkrævet i to tilfælde:
  • en række grundvariable x er negative i kanonisk form;
  • hvis det er svært at reducere til en kanonisk form, skal du blot tilføje en kunstig variabel til enhver begrænsningsligning.
• 2. Forekommer i praksis automatisk kontrol lineære programmeringsproblemer indeholder fra 500 til 1500 begrænsninger og mere end 1000 variabler. Det er klart, at problemer af denne dimension kun kan løses ved hjælp af en computer og en speciel software. Kompleksiteten af ​​algoritmen ligger i det faktum, at:
  • OPP kræver en kanonisk opfattelse;
  • PPP til problemer af denne størrelse kræver brug af store computere (og parallel computing), da simplex-metoden gemmer hele tabellen.
• 3. Simplexmetodens beregningsmæssige effektivitet kan vurderes ved hjælp af følgende indikatorer:
  • antal trin (tilstødende støtteplaner);
  • maskintidsomkostninger.

Der er sådanne teoretiske skøn for standard opgave lineær programmering med T restriktioner og variabler:

• gennemsnitligt antal trin * 2 T og ligger i området)