2. Indførelse af naturlige grundvariable. Konstruktion af et simplex bord. Definition af nulplanen.

Enkel metode. Simplex-metodens algoritme.

Enkel metode- løsningsalgoritme optimeringsproblem lineær programmering ved at opregne hjørnerne af et konveks polyeder i flerdimensionelt rum. Metoden blev udviklet af den amerikanske matematiker George Danzig i 1947.

Ideen med simplex-metoden er, at det stillede beskrivende problem oversættes til matematisk form. Den matematiske formulering af problemet indeholder ligningen for objektivfunktionen, der angiver det ønskede resultat - bestemmelse af minimum eller maksimum af objektivfunktionen; systemer med lineære begrænsninger specificeret af ligheder eller uligheder. Modtaget matematisk beskrivelse føre til matrixform. Derefter reduceres matrixbeskrivelsen af ​​problemet til kanonisk form. Efter systemet lineære ligninger reduceret til kanonisk form, begynder vi at løse det lineære programmeringsproblem. Algoritmen til at løse dette problem består af en sekvens af konstruerende matricer. Hvert trin i løsningen bringer dig tættere på at opnå det ønskede resultat.

I simplex-metodens beregningsskema implementeres en ordnet proces, hvor der, startende fra et indledende tilladeligt hjørnepunkt (normalt oprindelsen), foretages successive overgange fra et tilladt yderpunkt til et andet, indtil et punkt svarende til den optimale løsning er fundet.

Simplex metode algoritme

1. Vi bringer systemet med restriktioner til kanonisk form(når systemet er begrænset). Desuden kan et enkelt grundlag identificeres i systemet.

2. Find originalen referenceplan(ikke-negative basisløsninger af KZLP-ligningssystemet). Hver af referenceplanerne er bestemt af et system af m lineært uafhængige vektorer indeholdt i et givet system af n vektorer EN 1 , EN 2 ,…, A n. Den øvre grænse for antallet af referenceplaner i en given opgave bestemmes af antallet af kombinationer Med nm);

3. Vi bygger simplex bord (simplex bord en matrix, der tjener som et middel til at opregne tilladelige basisløsninger af et (ikke-degenereret) lineært programmeringsproblem, når det løses ved hjælp af simpleksmetoden. Det er dannet ud fra matrixen af ​​koefficienter af et system af lineære programmeringsligninger reduceret til kanonisk form, dets sekventielle transformation ifølge den såkaldte simplex algoritme tillader et begrænset antal trin (iterationer) for at opnå det ønskede resultat - en plan, der giver en ekstrem værdi af den objektive funktion).

4. B simplex bord vi tjekker vektorerne for negativitet, dvs. vurderinger Zj – Сj skrevet i linjen skal være ≤ 0 (som minimum), Zj – Сj ≥ 0(til det maksimale). Hvis estimaterne opfylder optimalitetsbetingelserne, er problemet løst.

5. Hvis optimalitetsbetingelserne for nogle vektorer er overtrådt, så er det nødvendigt at indføre en vektor i grundlaget, der svarer til:

max[θ 0 j (Zj – Сj)] ; min[θ 0 j (Zj – Сj)] ; θ 0 j = min, Hvor x i> 0

Vektor element θ j som svarer θ 0 j kaldet eftergivende; rækken og kolonnen, hvori den er placeret, kaldes guiden; vektoren i guiderækken forlader basis.

6. Lad os finde ekspansionskoefficienten for alle vektorer i det nye grundlag. Lad os anvende Giordano Gauss-metoden

Lad os se efter den optimale referenceplan. Hvis estimatet opfylder optimalitetsbetingelserne, er problemet løst, hvis ikke, udføres trin 5-7.

2. Indførelse af naturlige grundvariable. Konstruktion af et simplex bord. Definition af nulplanen.

Simplex-metoden er mest effektiv til at løse komplekse opgaver og repræsenterer en iterativ (trin-for-trin) proces, der starter med nul(reference) løsning (vertex n-dimensionelt polyeder). Næste i søgningen optimal mulighed Planen forudsætter bevægelse langs hjørnepunkterne (hjørnepunkter på polyederet), indtil værdien af ​​den objektive funktion når den maksimale (minimum) værdi. Lad os overveje simplex-metodens algoritme ved at bruge eksemplet på et omsætningsplanlægningsproblem med begrænsede råmaterialeressourcer.

Firmaet sælger n produktgrupper, der har m begrænsede materielle og økonomiske ressourcer b i ≥0 (1 ≤ jeg≤ m). Alles ressourceomkostninger er kendt jeg- type produktion og salg af en enhed af varer fra hver gruppe, præsenteret i form af en matrix ( -en ij) og fortjenesten modtaget af virksomheden ved salg af en enhed af varer j-gruppe indgår i den objektive funktion Z(x). Den lineære programmeringsmetode er ikke forskellig fra system (1) - (2):

Z(X) = с 1 Х 1 + с 2 Х 2 + с 3 Х 3 + … +с n Х n →max(min) (1)

a 11 X 1 + a 12 X 2 +…a 1n X n ≤ b 1,

a 21 X 1 + a 22 X 2 +…a 2n X n ≤ b 2 (2)

a m1 X 1 + a m2 X 2 +…a mn X n ≤ b m,

X 1 ≥0 X 2 ≥0 X 3 ≥0 …X n ≥0

Stadierne til at løse problemet ved hjælp af simplex-metoden omfatter:

1) Udarbejdelse af en nulreferenceplan. Vi introducerer nye ikke-negative (grundlæggende) variable, takket være hvilke ulighedssystemet (2) bliver et ligningssystem:

a 11 X 1 + a 12 X 2 +…a 1n X n + X n+1 = b 1

a 21 X 1 + a 22 X 2 +…a 2n X n + X n+2 = b 2 (3)

……………………………………..

a m1 X 1 + a m2 X 2 +…a mn X n + X n+m = b m,

Hvis vi tager inputvariablerne som kolonnevektorer, så repræsenterer de enkelt (grundlæggende) vektorer. Bemærk, at de grundlæggende variabler har en simpel fysisk betydning- Det her resten specifik ressource på lageret for en given produktionsplan, derfor kaldes dette grundlag naturlig. Vi løser system (3) med hensyn til de grundlæggende variable:

Xn+1 = b 1, -a 11 X 1 - a 12 X 2 -...a 1n X n

X n+2 = b 2 - a 21 X 1 - a 22 X 2 -...a 2n X n (4)

………………………………………..

X n+m = b m, - a m1 X 1 + a m2 X 2 +…a mn X n

Vi omskriver den objektive funktion i skemaet

Z(X) = 0-(-с 1 Х 1 -с 2 Х 2 -с 3 Х 3 -...-с n Х n) (5)

Hvis vi antager, at de nødvendige hovedvariable X 1 = X 2 = X 3 = ... = X n = 0, får vi en nulreferenceplan X = (0, 0, ...0, b 1, b 2, b 3 ... b m), hvor Z(X) = 0 (alle ressourcer på lager, intet produceret). Vi indtaster planen i en simplex-tabel.

Plan	Basis	Ci/Cj	Betyder X i	X 1	X 2	Xn	Xn+1	Xn+2	X n+ 3	Qmin
	Xn+1		b 1	en 11	en 12	en 13				b 1/a 12
Xn+2		b 2	en 21	en 22	en 23				b 2 / a 22
Xn+3		b 3	en 31	en 32	en 33				b 3 / a 32
Z(X) = 0	-C 1	- C 2	- C 3				Indeks. linje

2) Fra indekslinjens negative koefficienter vælger vi den største i absolut værdi, som bestemmer den førende kolonne og viser, hvilken variabel ved den næste iteration (trin) der vil flytte fra den primære (frie) til den grundlæggende (faktisk, den produktgruppe, hvis salg bringer maksimal indkomst). Derefter deler vi reserverne af råvarer b i med de tilsvarende omkostningskoefficienter, indtaster resultaterne i en tabel og bestemmer minimumsværdien Q min (den ressource, hvis reserve kraftigst begrænser output fra den valgte produktgruppe er valgt). Denne værdi vælger den indledende linje og variablen Xi, som ved næste trin (iteration) vil forlade grundlaget og blive fri.

3) Overgangen til ny plan udføres som følge af genberegning af simplekstabellen efter Jordan-Gauss metoden. Først erstatter vi X j i basis med X i i den forreste kolonne. Lad os dividere alle elementerne i den forreste linje med det opløselige element (RE), som et resultat af hvilket stedet for RE i den forreste linje vil være 1. Da X i er blevet grundlæggende, bør dens resterende koefficienter være lig med 0 Nye elementer i denne plan findes i henhold til rektangelreglen

NØ=SØ – (A*B)/RE (6)

Den resulterende plan evalueres ved hjælp af koefficienterne for indekslinjen: hvis de alle er positive, er planen optimal; hvis ikke, kan planen forbedres ved at udføre den næste iteration (trin).

Eksempel. 20 tusind rubler blev tildelt til køb af udstyr til produktionsstedet. Udstyret kan placeres på et areal på højst 72 kvm. Du kan bestille udstyr af to typer: type A, der kræver et produktionsareal på 6 kvm og giver 6 tusinde enheder. produkter per skift (pris 5.000 rubler) og type B, der kræver et areal på 12 kvm og producerer 3 tusinde enheder (pris 2.000 rubler). Hvad er den optimale plan for anskaffelse af udstyr at sikre maksimal ydeevne grund?

Lad os betegne mængden af ​​indkøbt udstyr af type A og B med henholdsvis X 1 og X 2.

Webstedets produktivitet ( objektiv funktion): Z(X) =6Х 1 +3Х 2.

De vigtigste begrænsninger hænger sammen

med kontanter: 5Х 1 +2Х 2 ≤ 20,

med produktionsstedsareal: 6Х 1 +12Х 2 ≤ 72.

Vi introducerer nye grundvariable X 3 (resten Penge efter køb af udstyr) og X 4 (restareal efter udstyrsplacering) og omskriv restriktionerne i form af et ligningssystem:

5X 1 +2X 2 +X 3 =20 (X 3 =20 – 5X 1 - 2X 2)

6X 1 +12X 2 +X 4 = 72 (X 4 =72 – 6X 1 – 12X 2)

I dette tilfælde er målfunktionen: Z(X) = 6Х 1 +3Х 2 +0Х 3 +0Х 4 .

Vi laver en reference (0.) plan: X = (0, 0, 20, 72), dvs. intet er købt endnu (ingen penge er brugt, pladsen er tom). At lave et simpleksbord

Plan	Basis	Ci/Cj	Betyder X i	X 1	X 2	X 3	X 4	Qmin
	X 3							20/5=4
X 4							72/6=12
Z(X) = 0	- 6	- 3			Indekslinje
	→X 1				0,4	0,2		4/0,4=10
X 4				9,6	-1,2		48/9,6=5
Z(X) = 6*4=24		-0,6	1,2		Indekslinje
	X 1					0,25	-1/24	-
→X 2					-1/8	5/48	-
Z(X) =6*2+3*5=27			9/8	1/16	Indekslinje

Det er klart, at den førende søjle svarer til X 1, da den har det største indeks 6. Vi finder minimumsværdien af ​​Q min = 4 (den mest alvorlige ressourcebegrænsning) ved at definere en førende række, der viser, at X 3 er afledt af basisvariablerne , og X indtastes i stedet 1 . Vi genberegner elementerne i den førende linje, dividerer dem med 5, og ved hjælp af formel (6) bestemmer vi elementerne i den anden og indekslinie. Målfunktionen for 1. plan er lig med Z(X) = 6*4+3*0 = 24.

En af koefficienterne i indeksrækken for kolonne X 2 forbliver dog negativ -0,6, derfor er denne plan ikke optimal, og en anden iteration (trin) er påkrævet for at forbedre den. Vælg 2. kolonne som førende og minimumsværdi Q min = 5 vi definerer den førende linje med grundvariablen X 4. Efter at have udført de samme transformationer får vi den 2. plan, som vil være optimal, da alle indekskoefficienter er positive.

Lad os analysere de opnåede resultater. For en optimal løsning har den objektive funktion maksimal værdi 27 tusind rubler, mens begge ressourcer er taget ud af basen, er derfor helt brugt.

Lad os sørge for dette: 5*2+2*5 = 20 tusind rubler, 6*2+12*5=72 kvm. Den nødvendige løsning er X = (2; 5;0;0).Dette sker ikke altid.

Foredrag nr. 10

Emne: Enkel metode for problemer med kunstigt grundlag

Simplexløsningsmetoden er baseret på indførelse af yderligere (grundlæggende) variable, der gør det muligt at danne en enhedsmatrix. Hvis problembegrænsningerne præsenteres i form af uligheder:

a i1 X 1 + a i2 X 2 +…a i X n ≥ bi (1)

eller ligninger:

a i1 X 1 + a i2 X 2 +…a i X n = bi (1*),

så er det umuligt at få referenceplanen i den ønskede form. I dette tilfælde, for at overholde ligheder (1*), introducerer vi kunstigt grundlag Y i , og kunstige variable er ikke direkte relateret til opgavens indhold, men gør det muligt at konstruere en reference (start)plan:

a i1 X 1 + a i2 X 2 +…a i X n +Y i = bi (2)

Den objektive funktion ved maksimal løsning af problemet vil blive skrevet i formen:

Z(X) =∑C j X j +(-M)∑Y i (3),

når du som minimum løser et lignende problem:

Z(X)=∑C j X j +(M)∑Yi (3*),

hvor M er meget stor positivt tal, en slags straf for at bruge kunstige variable.

I tilfælde af uligheder (1) introducerer vi indledningsvis yderligere variable X n + i med et minustegn. Deres matrix vil ikke være ensartet, derfor introducerer vi i hver ulighed i systemet (1) kunstige variable У i:

a i1 X 1 +a i2 X 2 +…a i X n –X n+i +Y i =b i (4)

Objektivfunktionen i dette tilfælde er Z(X)=∑C j X j +0∑X n + i +(-M)∑Y i (for at finde maksimum). Ansøgning kunstigt grundlag giver simplex-metoden større fleksibilitet og gør, at den kan bruges til en lang række opgaver.

Eksempel . Bestem maksimum- og minimumsavanceværdierne for produktion af to typer produkter A og B, hvis produktionsomkostninger og rentabilitet fra salg af en produktenhed er angivet i tabellen. Hovedbetingelsen er fuld beskæftigelse af arbejdere på virksomheden.

Matematisk vil produktionsoutputbegrænsningerne blive skrevet i form af et blandet system:

1X 1 + 1X 2 ≤ 6,

2X 1 + 1X 2 =8.

Lad os introducere den grundlæggende variabel X 3 for den første ulighed, og den kunstige variabel Y 1 for den anden ligning:

1X 1 + 1X 2 + X 3 = 6,

2X 1 + 1 X 2 + Y1 = 8.

Lad os udtrykke X 3 og Y 1 fra det resulterende ligningssystem og for at bestemme maksimum, forestille os den objektive funktion:

Z(X)= 3X 1 + 2X 2 +0X 3 –MY 1 = 3X 1 + 2X 2 –M(8 -2X 1 –X 2)=

3X 1 + 2X 2 –8M +2MX 1 + MX 2 = (2M + 3)X 1 + (M + 2)X 2 -8M

For referenceplanen - X=(0,0,6,8). Lad os bygge en simplex-tabel:

Plan	Basis	Ci/Cj	Betyder X i	X 1	X 2	X 3	Y 1	Qmin
	X 3							6/1=6
Y 1	-M						8/2=4
Z(X) = -8M	-2M-3	-M-2			Indekslinje
	X 3				0,5		-0,5	2/0,5=4
→X 1				0,5		0,5	4/0,5=8
Z(X) = 3*4=12		- 0,5		M+1,5	Indekslinje
	→X 2						-1	-
X 1					-1		-
Z(X) =3*2+2*4=14				M+1	Indekslinje

Som regel begynder forbedring af referenceplanen med fjernelse af den kunstige variabel Y 1 fra basis. Den optimale plan X = (2,4,0,0) blev opnået i anden iteration med en maksimal indkomst på 14 tusind. gnide. , og koefficienterne for indeksrækken er ikke-negative. Det er let at verificere, at i denne opgave, med en optimal plan, er ressourcer fuldt ud brugt (2*1+4*1=6; 2*2+1*4=8).

Når vi finder minimumsrentabiliteten, formulerer vi målfunktionen anderledes (+MY 1 indtastes som et led:

Z(X)= 3X 1 + 2X 2 +0X 3 +MY 1 = 3X 1 + 2X 2 +M(8 -2X 1 –X 2)=

3X 1 + 2X 2 +8M - 2MX 1 - MX 2 = (3 - 2M)X 1 + (2 - M)X 2 +8M

Referenceplanen er den samme, men indeksrækkekoefficienterne i simplekstabellen er forskellige. Den førende søjle, som før, er valgt af den største positive koefficient i absolut værdi for X 1, den førende række er bestemt af minimumsværdien af ​​Q min = 4. Ved den første iteration udledes den kunstige variabel Y 1 fra basis.

Plan	Basis	Ci/Cj	Betyder X i	X 1	X 2	X 3	Y 1	Qmin
	X 3							6/1=6
Y 1	M						8/2=4
Z(X) = 8M	2M-3	M-2			Indekslinje
	X 3				0,5		-0,5	2/0,5=4
→X 1				0,5		0,5	4/0,5=8
Z(X) = 3*4=12		- 0,5		-M+1,5	Indekslinje

De resulterende negative værdier af koefficienterne i indekslinjen X i angiver optimaliteten af ​​den 1. plan, mens minimumsindkomsten er 12 tusind rubler.

Det leveres kun af output fra produkt A (produkt B produceres ikke), råvarerne er ikke fuldt ud brugt (resten X 3 = 2t), mens hovedbetingelsen er opfyldt - arbejderne er fuldt beskæftiget i produktionen.

Foredrag nr. 11

Emne: Lukket transportproblem

1. Matematisk formulering af lukket transport problem. Bestemmelse af det nødvendige antal ukendte.

2. Stadier af fastlæggelse af en plan for løsning af et transportproblem.

Foredrag 3. Simplex borde. Simplex-metodens algoritme.

§ 3 ENKEL METODE

3.1. Generel idé om simplex-metoden. Geometrisk fortolkning

Den grafiske metode er anvendelig til en meget snæver klasse af lineære programmeringsproblemer: den kan effektivt løse problemer, der ikke indeholder mere end to variable. De grundlæggende teoremer for lineær programmering blev overvejet, hvoraf det følger, at hvis et lineært programmeringsproblem har optimal løsning, så svarer det til mindst ét ​​hjørnepunkt af løsningspolyederet og falder sammen, iflg i det mindste, med en af ​​de tilladte grundlæggende løsninger i begrænsningssystemet. Måden at løse ethvert lineært programmeringsproblem blev angivet: opregn endeligt nummer tilladelige grundlæggende løsninger af systemet af begrænsninger og vælg blandt dem den, som den objektive funktion gør den optimale løsning på. Geometrisk svarer dette til at opregne alle hjørnepunkterne i løsningspolyederet. En sådan udtømmende søgning vil i sidste ende føre til en optimal løsning (hvis den eksisterer), men dens praktiske implementering er forbundet med enorme vanskeligheder, da antallet af gennemførlige grundlæggende løsninger, selv om det er begrænset, kan være ekstremt stort for reelle problemer.

Antallet af tilladte basisløsninger, der skal søges, kan reduceres, hvis søgningen ikke udføres tilfældigt, men under hensyntagen til ændringer i den lineære funktion, dvs. at sikre, at hver næste løsning er "bedre" (eller i det mindste "ikke værre") end den forrige i henhold til værdierne af den lineære funktion (øge den, når du finder et maksimum, formindsk den, når du finder et minimum
). Denne søgning giver dig mulighed for at reducere antallet af trin, når du finder det optimale. Lad os forklare dette med et grafisk eksempel.

Lad området tilladte løsninger repræsenteret ved en polygon ABCDE. Lad os antage, at dets hjørnepunkt EN svarer til den oprindelige mulige basisløsning. En tilfældig søgning ville kræve afprøvning af fem mulige basisløsninger svarende til polygonens fem hjørnepunkter. Det fremgår dog tydeligt af tegningen, at efter toppen EN det er fordelagtigt at flytte til et nabopunkt I, og derefter til det optimale punkt MED. I stedet for fem gik vi kun gennem tre hjørner, hvilket konsekvent forbedrede den lineære funktion.

Idéen om konsekvent forbedring af løsningen dannede grundlaget universel metode løsning af lineære programmeringsproblemer - simpleksmetode eller metode til sekventiel forbedring af planen.

Simplexmetodens geometriske betydning består i en sekventiel overgang fra et toppunkt af begrænsningspolyederet (kaldet det indledende) til det naboliggende, hvor den lineære funktion tager den bedste (i hvert fald ikke den dårligste) værdi i forhold til målet med problemet; indtil den optimale løsning er fundet - det toppunkt, hvor den optimale værdi af målfunktionen er opnået (hvis problemet har et endeligt optimum).

Simplexmetoden blev først foreslået af den amerikanske videnskabsmand J. Danzig i 1949, men tilbage i 1939 blev ideerne til metoden udviklet af den russiske videnskabsmand L.V. Kantorovich.

Simplex-metoden, som gør det muligt at løse ethvert lineært programmeringsproblem, er universel. I øjeblikket bruges det til computerberegninger, men simple eksempler ved hjælp af simpleksmetoden kan løses manuelt.

For at implementere simplex-metoden - sekventiel forbedring af løsningen - er det nødvendigt at mestre tre hovedelementer:

en metode til at bestemme enhver indledende gennemførlig grundlæggende løsning på et problem;

reglen om overgang til den bedste (mere præcist, ikke værre) løsning;

kriterium for at kontrollere optimaliteten af ​​den fundne løsning.

For at bruge simpleksmetoden skal det lineære programmeringsproblem reduceres til kanonisk form, dvs. systemet af begrænsninger skal præsenteres i form af ligninger.

Litteraturen beskriver tilstrækkeligt detaljeret: at finde den indledende støtteplan (indledende tilladte basisløsning), også bruge den kunstige basismetode, finde den optimale støtteplan, løse problemer ved hjælp af simplekstabeller.

3.2. Simplex-metodens algoritme.

Lad os overveje løsningen af ​​ZLP ved hjælp af simplex-metoden og præsentere den i forhold til maksimeringsproblemet.

1. På baggrund af problemets betingelser sammenstilles dens matematiske model.

2. Den færdige model konverteres til den kanoniske form. I dette tilfælde kan et grundlag med en indledende referenceplan identificeres.

3. Den kanoniske model af problemet er skrevet i form af en simplekstabel, så alle frie termer er ikke-negative. Hvis den oprindelige referenceplan er valgt, skal du fortsætte til trin 5.

Simplex tabel: et system af begrænsningsligninger og en objektiv funktion indtastes i form af udtryk, der er løst i forhold til startgrundlaget. En linje, der indeholder koefficienterne for den objektive funktion
, hedder
– en streng eller en streng af målfunktionen.

4. Find den indledende referenceplan ved at udføre simplekstransformationer med positive opløsningselementer svarende til minimumssimplexrelationerne og uden at tage hensyn til elementernes fortegn
-linjer. Hvis der under transformationerne stødes på en 0-række, hvis elementer, bortset fra det frie led, er nuller, så er systemet af begrænsningsligninger for problemet inkonsistent. Hvis vi støder på en 0-række, hvor der udover det frie led ikke er andre positive elementer, så har systemet af restriktive ligninger ingen ikke-negative løsninger.

Vi vil kalde reduktionen af ​​systemet (2.55), (2.56) til et nyt grundlag simplex transformation . Hvis en simplekstransformation betragtes som en formel algebraisk operation, så kan man bemærke, at som et resultat af denne operation omfordeles roller mellem to variable inkluderet i et bestemt system lineære funktioner: den ene variabel går fra afhængig til uafhængig, og den anden går tværtimod fra uafhængig til afhængig. Denne operation er kendt i algebra som Jordan eliminationstrin.

5. Den fundne indledende støtteplan undersøges for optimalitet:

a) hvis i
– der er ingen negative elementer i rækken (friterminen ikke medregnet), så er planen optimal. Hvis der ikke er nuller, så er der kun én optimal plan; hvis der er mindst et nul, så er der et uendeligt antal optimale planer;

b) hvis c
– der er mindst et negativt element i rækken, som svarer til en kolonne af ikke-positive elementer, så
;

c) hvis i
– rækken har mindst et negativt element, og dens kolonne har mindst et positivt element, så kan du flytte til et nyt referenceplan, tættere på optimalt. For at gøre dette skal den angivne kolonne udpeges som en opløsningskolonne, ved at bruge det minimale simpleksforhold, find den løsende række og udfør en simplekstransformation. Den resulterende referenceplan undersøges igen for optimalitet. Den beskrevne proces gentages, indtil der opnås en optimal plan, eller indtil problemets uløselighed er fastslået.

Kolonnen med koefficienter for en variabel, der er inkluderet i grundlaget, kaldes opløsning. Således vælges en variabel, der er indtastet i basis (eller vælges en løsende kolonne) af det negative element
-strenge, giver vi stigende funktion
.

Det er lidt sværere at bestemme den variabel, der skal udelukkes fra grundlaget. For at gøre dette sammensætter de forholdet mellem frie udtryk og de positive elementer i den løsende kolonne (sådanne relationer kaldes simplex) og finder den mindste blandt dem, som bestemmer rækken (opløsning), der indeholder den udelukkede variabel. Valget af en variabel, der er udelukket fra grundlaget (eller valget af en opløsende linje) i henhold til den minimale simplex-relation garanterer, som det allerede er fastslået, positiviteten af ​​basiskomponenterne i den nye referenceplan.

I punkt 3 i algoritmen antages det, at alle elementer i kolonnen frie termer er ikke-negative. Dette krav er ikke nødvendigt, men hvis det er opfyldt, udføres alle efterfølgende simplex-transformationer kun med positive opløsningselementer, hvilket er praktisk til beregninger. Hvis der er negative tal i kolonnen med frie termer, vælges det løsende element som følger:

1) se f.eks. på linjen, der svarer til et negativt friled – en række, og vælg et hvilket som helst negativt element i den, og den tilsvarende kolonne tages som løsende (vi antager, at problemets begrænsninger er konsistente);

2) opgør relationerne mellem elementerne i kolonnen af ​​frie termer til de tilsvarende elementer i den løsende kolonne, der har de samme tegn (simplekse relationer);

3) vælg den mindste af simpleksrelationerne. Dette vil bestemme aktiveringsstrengen. Lad det f.eks. R-linje;

4) i skæringspunktet mellem den løsende kolonne og rækken findes et opløsende element. Hvis elementet er tilladeligt –strenge, så efter simplex-transformationen vil den frie led for denne streng blive positiv. Ellers vender vi i næste trin igen til -linje. Hvis problemet kan løses, vil der efter et vist antal trin ikke være nogen negative elementer tilbage i kolonnen med frie udtryk.

Hvis en bestemt reel produktionssituation sættes i form af en PLP, så har de yderligere variabler, der skal introduceres i modellen i processen med at konvertere den til den kanoniske form, altid en vis økonomisk betydning.

Simplexmetoden består i at finde og teste et toppunkt (vinkel), der er en løsning på LP-problemet. På hvert trin vælger metoden et toppunkt og dets tilsvarende variable, som sikrer bevægelse til minimum (maksimum) med højeste hastighed. Den valgte variabel erstatter den anden, mest restriktive. Simplex-metoden giver dig også mulighed for at afgøre, om der findes en løsning. Algoritmen, der implementerer simplex-metoden, kan skrives som:

Trin 1. Et bestemt toppunkt i ODR bestemmes, svarende til de grundlæggende tilladelige løsninger (variabler) fundet ved udtræk fra matrixen T- lineært uafhængige kolonner og lig med nul alle andre variabler svarende til andre kolonner i matrixen.

Trin 2. Udvalgt fra alle mulige resterende p - t kanter svarende til ikke-grundlæggende variable, en kant (variabel), der, når man bevæger sig langs den, fører til det hurtigste fald i den objektive funktion.

Trin 3. Det er, som om der udføres en bevægelse fra det indledende toppunkt langs den valgte kant til et andet toppunkt, hvilket giver en ny løsning, der har en lavere CF-værdi. Et nyt toppunkt dannes ved at erstatte basisvariablen (kant) med en ny basisvariabel (kant).

Søjlerne og elementerne i vektorer er normalt ordnet og skrevet i form af en simplex-tabel, hvis dannelse vil blive vist nedenfor.

Simplex-metoden løser LP-problemet i standardform.

Minimer (maksimer) funktionen under betingelserne x > 0; Ax = b.

Matrix A er ægte og har dimensionen T x" og rang T.

Den formulerede LP-opgave kan også skrives i skemaet

Baseret på registreringen af ​​LP-problemet i formen (8Л), kan vi sige, at den udvidede matrix

dimensioner (t+ 1) (n + 2) svarer til løsninger[x/] t.

Lad os repræsentere matrix A som et sæt kolonner

Da matrix A har rang T, så bliver der T lineært uafhængige kolonner i matrix A, for eksempel (a V1 ,...,a V/i Betragt en vektor x° > 0, således at det hele p - t elementer er 0 og Ax° = b. Lad disse være elementer med tal..., i n _ m . Lad os også antage, at placeringen aw af lineært uafhængige søjler i matrix A svarer til placeringen af ​​ikke-nul elementer i vektorerne 0. Geometrisk betyder dette ifølge udsagn 3 i § 7.6, at x° er toppunktet (vinklen) af ODR og derudover opfylder givne forhold. Denne løsning kaldes tilladt basisløsning. Vinklerne på det tilladte sæt er tilladte basisløsninger.

Husk på, at sættet af grundlæggende løsninger indeholder al den information, der er nødvendig for den optimale løsning af LP-problemet. For den todimensionelle sag behandlet i § 7.6 er basisløsningerne alle 6 punkter, og de tilladte basisløsninger er punkterne L, V, Si 0.

Således kan enhver vektor x svarende til x° skrives som

Hvor x i- en vektor, hvis elementer svarer til lineært uafhængige søjler i matrix A; xF - vektor med nul elementer.

Lad os definere vektorerne på samme måde

Variabler, der er elementer i en vektor x i, hedder grundlæggende variabler, og de variable, der er elementer i vektoren x F hedder gratis (ikke-grundlæggende) variable.

Fordi x°F=0, så vil værdien af ​​objektivfunktionen for startvektoren x° være lig med

hvor /° er værdien af ​​/ ved punkt x°.

Løsning (8.1) på formen [x°/°]t for x > 0 kaldes indlysende (eksplicit) løsning. Hvis vi således sætter ikke-grundlæggende variable lig med nul, får vi en oplagt løsning.

For nemheds skyld, lad os omarrangere T lineært uafhængige kolonner af matrix A til venstre side og skriv matrixen i formen

Her svarer matrix B T lineært uafhængige kolonner har dimension tx t og rang T, og matrixen F

er th (p - t) matrix. Da matrix B består af lineært uafhængige søjler, har den en invers B -1 og detB φ 0. Bemærk, at for at danne matrix B kan du vælge hvilken som helst T lineært uafhængige søjler af matrix A.

Lad os repræsentere problem (8.1) under hensyntagen til den introducerede notation

Denne repræsentation svarer til den udvidede matrix. Lad os antage det

hvorfra følger

Hvis vektor x V vil være en løsning til systemet Bx d = b, så vil det være den grundlæggende løsning. Hvis uligheden holder V= B-1 b > O, så x i vil være en acceptabel løsning.

Således opfylder den nuværende løsning følgende ligning:

Lad os overveje matrix (8.4). De grundlæggende variable vil blive præsenteret i eksplicit form, hvis vi erstatter matricen B med identitetsmatrix I. Multiplicerer vi den første række af matrix (8.4) til venstre med B~ 1, får vi

hvor B_1 b > O, dvs. T De øverste elementer i højre kolonne er ikke-negative og repræsenterer den aktuelle værdi af variablerne.

På venstre side øverste linje Resultatet er en enhedsmatrix: B -1 B = I. Denne præsentation meget praktisk, fordi når man multiplicerer med en vektor x i hver variabel vil være på en separat linje.

Dermed, grundlæggende løsning, som vi vil betragte som tilladt og svarende til grundlaget B, er x m = [x i 0], hvor x i == B_1 b. Den grundlæggende løsning er et resultat af den antagelse, at x F = 0. Men hvis xF* 0, så kan x^ beregnes som x 5 = = B~"b - B^"Fx/r. Ved at erstatte dette udtryk med den objektive funktion (omkostningsfunktionen), får vi

Da det er nødvendigt at bestemme omkostningernes afhængighed af ikke-grundlæggende variable, hvoraf den ene er inkluderet i de grundlæggende, bør bundlinjen under matrix I være nul. For at gøre dette gange vi i (8.7) den første række (af matricen) med fra til og tilføj det med den anden

hvor er værdien af ​​den objektive funktion for det indledende århundrede

torus x 0 fra (8.3).

Matrix (8.8) kaldes simplex bord. At bringe hende til denne art er den indledende fase af simplex-algoritmen. Under udførelsen af ​​algoritmen foretages en overgang fra en tabel til en anden, indtil det nederste højre element i tabellen bliver maksimum eller minimum.

Ved at bruge et simpleksbord er det nemt at se en gennemførlig løsning. Variabler x F svarer til nul submatrix, variable x i- enhedsmatrix:

Lad os antage, at LP-problemet er blevet reduceret til standardform, simplekstabellen er blevet beregnet, og den initiale basisløsning svarende til toppunktet for løsningspolyederet er valgt.

Derefter - løsning på problem (8.1). Så

som b > Åh, dette er en grundlæggende acceptabel løsning.

Lad os præsentere matrix (8.9) i en mere bekvem form, idet vi beholder den grundlæggende notation:

Lad os separat overveje problemerne med maksimering og minimering.

Lad os overveje en universel metode til at løse det kanoniske lineære programmeringsproblem

Med n variabler og m lighedsbegrænsninger, kendt som simpleksmetoden.

Sættet af planer for et kanonisk problem er et konveks polyedrisk sæt med et begrænset antal hjørnepunkter. Og hvis dette problem har en optimal løsning, opnås det i det mindste på et hjørnepunkt.

Ethvert hjørnepunkt er knyttet til en grundlæggende plan af problemet, hvor variablerne er lig nul, og de resterende variable svarer til lineært uafhængige kolonner i betingelsesmatrixen. Disse lineært uafhængige kolonner danner en ikke-singular basismatrix.

Iteration over alle hjørnepunkter er beregningsmæssigt dyrt og derfor ineffektivt. I 1947 foreslog J. Danzig en velordnet procedure for opregning af hjørnepunkter, hvor det er nok kun at undersøge en lille del af dem for at finde den optimale løsning. Denne procedure kaldes simpleks metode.

J. Danzig foreslog kun at erstatte én vektor i basismatrixen, når man bevægede sig fra et yderpunkt til et andet. Det betyder, at vi under en sådan overgang skal udelukke en af ​​de grundlæggende variable - gør den ikke-grundlæggende ( lig med nul), og indfør i stedet en ny variabel blandt de ikke-grundlæggende (nul) - gør den grundlæggende (positiv).

Det viser sig, at geometrisk set fører en sådan udskiftning til en overgang fra et hjørnepunkt til et tilstødende (nabo) forbundet med forrige punkt fælles kant.

Af alle nabopunkter vælges det, hvor målfunktionen øges mest. Da antallet af hjørnepunkter er endeligt, gennem et endeligt antal overgange toppunktet med højeste værdi objektiv funktion, eller ubegrænsetheden af ​​den objektive funktion vil blive etableret på et ubegrænset sæt planer.

Simplexmetodens generelle skema består af følgende hovedtrin.

· trin 0. Bestemmelse af startgrundlaget og det tilsvarende starthjørnepunkt (basislinje).

· trin 1. Kontrollerer den aktuelle baseline for optimalitet . Hvis optimalitetskriteriet er opfyldt, At planen er optimal, og løsningen er komplet. Ellers gå til trin 2.

· trin 2. At finde variablen indført i de grundlæggende. (Fra betingelsen om at øge den objektive funktion).

· trin 3. At finde en variabel, der er udelukket fra de grundlæggende variable (Fra betingelsen om at bevare problemets begrænsninger).

· trin 4 . Find koordinaterne for den nye basislinje (tilstødende hjørnepunkt). Gå til trin 1.

Gentagne trin 1-4 danner en iteration af simpleksmetoden.

Af dette diagram følger det, at for det første, for at starte simplex-metoden, skal du have en form for hjørnepunkt - en indledende grundplan, og for det andet skal du være i stand til at undersøge det aktuelle hjørnepunkt for optimalitet uden at beregne alle tilstødende hjørner. Disse problemer løses let, hvis det kanoniske LP-problem har en speciel form.

Definition. Vi vil sige, at det kanoniske LP-problem har en "foretrukken form" if

1. højre side af ligningerne, .

2. betingelsesmatrixen indeholder en enhedsundermatrix af størrelse

Med andre ord, i enhver ligning er der en variabel med en koefficient lig med én, mangler i de andre ligninger. Den første betingelse er ikke byrdefuld, da det i tilfælde af en negativ højre side af en ligning er nok at gange den med (-1). I et problem af den foretrukne type er det meget enkelt at finde den indledende baseline.

Eksempel 2.1.

Tilstandsmatrix EN og vektoren af ​​højre side af begrænsningerne b ligner

EN målvektor c = (1, -3, 0, 4, 2).

En basismatrix er umiddelbart indlysende: med enhedsvektorer af betingelser.

Derfor vælger du som grundvariable x 1 , x 3 ,x 5 , og indsætte ligningssystemet x 2 = x 4 = 0 (ikke-grundlæggende variable) , vi finder det med det samme x 1 = 10,x 3 = 20,x 5 = 8, så den indledende baseline x 0 = (10, 0, 20, 0, 8). Vi ser, at værdierne af de grundlæggende variable er lig med højre side af begrænsningerne. Heraf er det klart, at højresiden skal være positiv b jeg .

I fremtiden vil vi kombinere de grundlæggende variable til en vektor x B.

Således i kanonisk problem af den foretrukne form tages identitetsundermatricen som den indledende basismatrix EN B = E, og de tilsvarende basisvariabler er lig med højre side af begrænsningerne:

x B = b.

For en grundplan af denne type kan der formuleres et optimalitetskriterium, som er simpelt nok at teste. Lad os introducere mængderne

? j = < с B , A j > - c j , j = 1,...,n,(2.1)

Hvor Med B- vektor af koefficienter for den objektive funktion for grundlæggende variable x B , EN j -j- th tilstand matrix kolonne, c j -j- den objektive funktions koefficient. Forskelle ? j kaldes simpleksforskelle eller simpleksestimater.

Optimalitetskriterium for grundplanen. Hvis for en grundplan med en enhed basis matrix alle simpleksestimater er ikke-negative, så er denne plan optimal.

Lad os anvende dette kriterium for at kontrollere optimaliteten af ​​den grundlæggende plan x 0 = (10, 0, 20, 0, 8) fra eksempel 2.1.

Da i denne henseende vektoren af ​​grundlæggende variable x B =(x 1 , x 3 ,x 5 ), At Med B = (c 1 , c 3 ,c 5 ) = (1, 0, 2).

Derfor,

? 1 = < с B , A 1 > - c 1 = 1 1 + 0 0 + 2 0 - 1= 0,

2 = < сБ, A2 >- c2 = 1 3 + 0 1 + 2 2 - (-3) = 10,

? 3 = < с B , A 3 > - c 3 = 1 0 + 0 1 + 2 0 - 0= 0,

? 4 = < с B , A 4 > - c 4 = 1 (-1) + 0 5 + 2 1 - 4= -3,

? 5 = < с B , A 5 > - c 5 = 1 0 + 0 0 + 2 1 - 2= 0.

Siden vurderingen ? 4 < 0, то базисный план x 0 ikke optimalt. Bemærk, at simpleksestimaterne svarende til grundvariablerne altid er lig med nul, så det er tilstrækkeligt kun at kontrollere de ikke-grundlæggende estimater.

Ideen om simplex-metoden

Enkel metode

I det foregående afsnit blev det vist, at hvis et lineært programmeringsproblem har en optimal løsning, så er en af ​​de optimale løsninger en tilladelig grundlæggende løsning på dets system af begrænsninger, som svarer til et eller andet hjørnepunkt af polyederen af ​​tilladte løsninger af system. Det blev vist, hvordan man finder denne optimale løsning ved hjælp af en begrænset søgning af grundlæggende løsninger til problemets begrænsninger. Men efterhånden som dimensionen n af problembegrænsningssystemet øges, vokser mængden af ​​beregninger til løsning af problemet ved hjælp af metoden med udtømmende opregning af grundlæggende løsninger eksponentielt og bliver uegnede i praksis. Det er muligt at organisere en opregning af kun gennemførlige basisløsninger og kraftigt reducere antallet af opregnede løsninger, hvis hver efterfølgende tilladelige basisløsning vælges, så den tilsvarende værdi af den objektive funktion forbedres eller i det mindste ikke forringes. Denne tilgang giver dig mulighed for at reducere antallet af trin, når du skal finde den optimale basisløsning. Lad os forklare denne idé grafisk.

Lad polygonen ABCDEFGH repræsentere sættet af tilladte løsninger af PLP med to variable og vektoren – gradient af den objektive funktion.

Vi skal finde det punkt i denne polygon, hvor objektivfunktionen får den mindste værdi. Lad den indledende tilladte grundløsning af problemet svarende til hjørnepunktet B bestemmes. Efter en fuldstændig søgning af alle tilladelige grundløsninger vil det være nødvendigt at undersøge otte sådanne løsninger svarende til polygonens otte hjørnepunkter. Det fremgår dog tydeligt af figuren, at under hensyntagen til gradientens retning er det mere rentabelt at gå til nabotoppunktet C og derefter til nabotoppunktet D, hvilket svarer til den optimale grundlæggende løsning af problemet. I stedet for otte løsninger skal der således kun overvejes tre gennemførlige basisløsninger.

Ideen om sekventiel forbedring af løsningen danner grundlaget for den universelle metode til løsning af lineære programmeringsproblemer – simpleks metode.

Geometrisk betydning Simplex-metoden består i at udføre en sekventiel overgang fra et toppunkt af polyederen af ​​mulige løsninger på problemet til det tilstødende, hvor objektivfunktionen har en værdi, der ikke er dårligere end ved det foregående toppunkt. Denne overgang fortsætter, indtil der er fundet en optimal løsning, eller det opdages, at problemet ikke har en.

Simplexmetoden og dens navn blev først foreslået af den amerikanske matematiker John Dantzig i 1947, selvom ideerne til metoden blev udgivet af den russiske matematiker L.V. Kantorovich tilbage i 1939 i artiklen " Matematiske metoder organisation og produktionsplanlægning."

Simplexmetoden består af tre hovedelementer.