meetod kunstlik alus(M-ülesanne).

Paljude põhiülesande kujul kirjutatud ja võrdlusplaanidega lineaarse programmeerimise ülesannete puhul ei ole vektorite P j hulgas alati m ühikvektorit.

Kaaluge järgmist probleemi:

Oletame, et peame leidma funktsiooni maksimumi

F = c 1 x 1 + c 2 x 2 + ……+ c n x n (1)

tingimustel

……………………………………… (2)

Kus b i  0 ( i=l, m), m<.>n ja vektorite P 1 , P 2 , …, P n hulgas pole m ühikulist.

Definitsioon. Funktsiooni maksimaalse väärtuse määramise ülesanne

F= c 1 x 1 + c 2 x 2 + ……+ c n x n -Mx n +1 - ... - Mx n + m (3)

tingimustel

……………………………………… (4)

kus M on mingi piisavalt suur positiivne arv, mille konkreetset väärtust tavaliselt ei täpsustata, nimetatakse ülesande (1) - (2) suhtes laiendatud probleemiks (M-ülesandeks).

Laiendatud ülesanne on võrdlusplaan

X=(0; 0; ...; 0; b1; b 2 ; ...;b m).

määratud ühikvektorite süsteemiga P n +1 ; R n+2 , … R p+t , moodustades aluse m-ro vektorruumile, mida nimetatakse kunstlik. Vektorid ise, aga ka muutujad x n + i ( i=l, m), kutsutakse kunstlik. Kuna laiendatud probleemil on referentsplaan, siis selle lahendus on leitav simpleks meetod.

Teoreem Kui optimaalselt X*=( x* 1 , x* 2 , ...; x*n , x* n +1 ; ...; x*n+m) laiendatud ülesanne (3) - (4) tehismuutujate väärtused x* n + i =0 ( i=1, m), See X*=( x* 1 , x* 2 , ...; x*n) on probleemi optimaalne plaan (1) - (2).

Seega, kui laiendatud probleemi jaoks leitud optimaalses plaanis on tehismuutujate väärtused võrdsed nulliga, siis saadakse algse probleemi optimaalne plaan.

Indeksijoone väärtused ∆ 0 , ∆ 1 , …, ∆ n koosnevad kahest osast, millest üks sõltub M, aga teine ​​mitte. Täitke simplekstabel, mis sisaldab ühe rea rohkem kui tavaline simplekstabel. Sel juhul sisaldab (m+2) rida koefitsiente M, ja (m+1)-ndas – terminid, mis ei sisalda M.Ühelt võrdlusplaanilt teisele liikumisel viiakse baasi (m+2)-nda rea ​​absoluutväärtuse suurimale negatiivsele arvule vastav vektor. Alusest välja jäetud tehisvektorit järgmises simplekstabelis ei kajastata. Simplekstabelite ümberarvutamine ühelt võrdlusplaanilt teisele liikumisel toimub vastavalt üldreeglid simpleks meetod.

Iteratiivne protsess piki (m+2)-joont jätkub kuni:

kas kõik tehisvektorid ei jäeta baasist välja;

või kõik tehisvektorid pole välistatud, kuid (m+2) rida ei sisalda enam negatiivseid elemente indeksites ∆ 1, ..., ∆ n.

Esimesel juhul vastab alus mõnele algülesande võrdlusplaanile ja selle optimaalse plaani määramine jätkub mööda (m+1)-ndat joont.

Teisel juhul, kui ∆ 0 väärtus on negatiivne, pole algsel ülesandel lahendust; kui ∆ 0 =0, siis on algülesande leitud võrdlusplaan degenereerunud ja alus sisaldab vähemalt ühte tehisbaasvektoritest.

Probleemile lahenduse leidmise etapid (1) - (2)

kunstlik alusmeetod:

Koostage laiendatud ülesanne (3) - (4).

Leidke laiendatud ülesande võrdlusplaan.

Kasutades tavalised arvutused Simpleksmeetod jätab tehismuutujad baasist välja. Selle tulemusena leitakse kas esialgse probleemi (1) - (2) võrdlusplaan või tuvastatakse selle lahendamatus.

Leitud ülesande võrdlusplaani (1) - (2) kasutades leiavad nad kas simpleksmeetodi abil algse probleemi optimaalse plaani või tuvastavad selle lahendamatuse.

Näide.

Leia funktsiooni miinimum F= - 2x 1 + 3x 2 - 6x 3 - x 4

n piirangutega:

2x 1 +x 2 -2x 3 +x 4 =24

x 1 +2x 2 +4x 3 ≤22

x 1 -x 2 +2x 3 ≥10

x i ≥0, i=1,4

Lahendus.

Paneme selle kirja see ülesanne põhiprobleemi kujul: leida funktsiooni maksimum F= 2x 1 - 3x 2 + 6x 3 + x 4

piirangutega:

2x 1 +x 2 -2x 3 +x 4 =24

x 1 +2x 2 +4x 3 +x 5 =22

x 1 -x 2 +2x 3 - x 6 = 10

x i ≥0, i=1, 6

Viimase ülesande võrrandisüsteemis arvestage tundmatute koefitsientide vektoreid:

Vektorite P 1 hulgast R 2 , ... P 6 ainult kaks üksikut (P 4 ja P 5). Seetõttu sisse vasak pool probleemipiirangusüsteemi kolmandast võrrandist lisame täiendava mittenegatiivse muutuja x 7 ja kaaluge funktsiooni maksimeerimise laiendatud probleemi

F= 2x 1 - 3x 2 + 6x 3 + x 4 - Мх7

piirangutega:

2x 1 +x 2 -2x 3 +x 4 =24

x 1 +2x 2 +4x 3 +x 5 =22

x 1 -x 2 +2x 3 - x 6 +x 7 = 10

Laiendatud ülesandel on võrdlusplaan X = (0; 0; 0; 24; 22; 0; 10), mis on defineeritud kolme ühikuvektori süsteemiga: P 4 , P 5 , P 7 .

Kahelise (adjungint) probleemi mõiste lineaarne programmeerimine.

Ehitusreeglid kahekordne probleem.

Iga lineaarse programmeerimise ülesandega (LPP), mida nimetatakse duaalprobleemiks (või adjointiks) võrreldes algse probleemiga, mida nimetatakse otseseks.

Duaalülesanne on konstrueeritud otsese probleemi suhtes, mis on kirjutatud standardvormis:

F=c 1 x 1 +c 2 x 2 +…+c n x n  max (3,6)

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,

………………………………

a k1 x 1 +a k2 x 2 +…+a kn x n ≤ =b k , (3.7)

a k+1,1 x 1 +a k+1,2 x 2 +…+a k+1,n x n =b k+1,

………………………………

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

x j ≥ 0, , l≤ n (3,8)

Funktsiooni minimaalse väärtuse leidmise probleem

L = b 1 y 1 + b 2 y 2 + … + b m y m (3,9)

tingimustel

a 11 a 1 + a 12 a 2 +…+ a m1 a m ≥ c 1

a 21 a 1 + a 22 a 2 +…+ a m2 a m ≥ c 2

………………………………

a 1 l y 1 + a 2 l y 2 +…+ a m l y m ≥ c l (3.10)

a l+1,1 y 1 + a l+1,2 y 2 +…+ a l+1, m y m = c l+1

………………………………

a m1 y 1 + a m2 y 2 +…+ a mn y m = c m

y i ≥ 0, , k ≤ m (3,11)

nimetatakse duaalseks probleemiga (3.6) – (3.8).

Topeltülesande koostamise reeglid on toodud tabelis:

ZLP struktuuriomadused	Lineaarse programmeerimise probleem
		Kahekordne
1. Objektiivne funktsioon	Maksimeerimine (max)	Minimeerimine (min)
2. Muutujate arv	n muutujat	Võrdne otseülesande piirangute arvuga (3.7), y i , s.o. m
3. Piirangute arv	m piirangud	Võrdne otseülesande muutujate arvuga x j , s.o n
4. Koefitsientide maatriks piirangute süsteemis
5. Muutujate koefitsiendid sihtfunktsioonis	c 1 , c 2, …, c n	b 1, b 2, …, b m
6. Parem pool piirangute süsteemid	b 1, b 2, …, b m	c 1 , c 2, …, c n
7. Märgid piirangute süsteemis	a) x j ≥ 0 - mittenegatiivsuse tingimus	j-ndal piirangul on märk “≥”
	b) muutujale x j ei kehtestata mittenegatiivsuse tingimust	J-ndal piirangul on märk “=”.
	c) i-ndal piirangul on märk “≤”	muutuja y i ≥0
	d) i-ndal piirangul on märk “=”.	muutujale y i ei kehtestata mittenegatiivsuse tingimust

Märkus

Otsene maksimumprobleem ja topeltmiinimumprobleem on vastastikku duaalsed probleemid. Seetõttu võime probleemi (3.9) – (3.11) pidada otseseks ZLP-ks ja probleemi (3.6) – (3.8) selle kaksikülesandeks. Sel juhul säilivad kahe PLP koostamise reeglid, ainult koos selle muudatusega, et miinimumprobleemi peetakse esialgseks.

Kui algne probleem on lahendatud max (min) juures ja piirangute süsteemis) i-e ( j-f) piirangul on märk “≤” (“≥”), siis duaalülesande konstrueerimiseks on vaja:

a) või korrutage mõlemad osad i th ( j-th) ebavõrdsus (-1) ja muutke märgiks "≤" ("≥")

b) või tuua i-e ( j-e) võrdsuse piiramine lisamuutuja x sisseviimisega n+ i ≥0

Lahendame ZLP vormis

Sel juhul üldine skeem simpleks meetod läbib mõningaid muudatusi. Nimelt:

1) Olgu mõne tugilahenduse alus ja sellele vastav simpleks laud. IN ülemine rida See tabel (veerupealkirjad) sisaldab vabu muutujaid; kõige parempoolsem veerg on vabaliikmete veerg ja kõige rohkem alumine rida on string objektiivne funktsioon ja seda nimetatakse suhteliste hinnangute vektoriks. Ülejäänud tabeli sisu on piirangumaatriksi veerud, mis vastavad vabade muutujate vastavatele veergudele. Suhteliste hinnangute vektori koordinaadid leitakse reegli järgi: sihtfunktsiooni põhimuutujate koefitsientide vektor korrutatakse skalaarselt i simplekstabeli veergu ja lahuta leitud arvust vastava vaba muutuja sihtfunktsiooni koefitsient.

2) Kui kõik suhtelised hinnangud (selle tabeli alumine rida) on mittenegatiivsed, siis on konstrueeritud optimaalne võrdluslahend.

3) Kui on negatiivne hinnang ja vastav veerg (lahutav) koosneb mittepositiivsetest elementidest, siis on sihtfunktsioon lahendamatu Z(X), see tähendab max  Z(X) ®+¥.

4) Vastasel juhul valige juhtelement (määrab juhtiva rea) ja sooritage sellega Jordani elimineerimise samm, liikudes uude simplekstabelisse, mida analüüsitakse nagu punktis 2).

Kunstlik alusmeetod

Kunstliku baasi meetodit kasutatakse LP-ülesannete lahendamiseks juhul, kui ülesandel puudub ühikvektorite baasil põhinev lähtelahendus.

Laske LP-probleemil järele anda kanooniline vorm, see tähendab, et sellel on vorm (2.1.1) ja selles puudub ühikupõhi. Selle ülesande jaoks koostame abiprobleemi (AP):

Siin w 1 , w 2 ,…, w m– kunstlikud muutujad. Kirjutame piirangud vektorkujul: A 1 x 1 +A 2 x 2 +…+A n x n+A n +1 w 1 +…+A n + m w m =B, Kus , , …, , , , …, , . Seega moodustavad vektorid , , … ühikulise aluse R m, ja kõik nendele vektoritele vastavad tehismuutujad on põhilised. Järgmisena konstrueeritakse tavaline simplekstabel. Kui ülesandel puudub lahendus eesmärgifunktsiooni piiramatuse tõttu, siis pole ka algülesandel samal põhjusel lahendust. Oletame, et vajalike simpleksmeetodist tuttavate teisenduste tulemusena saame VZ jaoks optimaalse simplekstabeli. See on ilmne maksimaalne väärtus sihtfunktsioon VZ on võrdne 0-ga, see tähendab max F=0. Kui max F<0, то исходная задача ЛП не имеет решения в силу несовместности системы ограничений. Предположим, что max F=0. Siis on võimalikud järgmised olukorrad:

1) kõik tehismuutujad said vabaks ja jäeti tabelist välja. Sel juhul kriipsutame maha tehismuutujatele ja viimasele reale vastavad veerud. Selle asemel määrame uue hinnangurea, kuid kasutades algset sihtfunktsiooni Z(X). Seega saame algse LP-ülesande algse simplekstabeli, millele rakendame simpleksmeetodit;

2) ülesande optimaalses lahenduses jääb põhiliseks vähemalt üks tehismuutuja. Seejärel:

a) kas kõik arvud ridadel, mis vastavad ülejäänud tehislikele põhimuutujatele, on võrdsed 0-ga;

b) või on vähemalt üks, mis erineb 0-st.

Esimesel juhul teeme sama, mis punktis 1). Teises valime juhtivaks elemendiks mis tahes nullist erineva elemendi ja sooritame Jordani elimineerimise sammu. Lõpliku arvu sammude järel jõuame kas punkti 1) või punkti 2) a).

Pange tähele, et kui vektorite hulgas A j , j=1,2,…,n, olid vektorid, mida sai baasi kaasata, siis sisestatakse tehismuutujad ainult nendesse piirangute süsteemi võrranditesse, milles alusmuutujat pole.

Näide. Maksimeeri funktsioon Z=x 1 +2x 2 -2x 3 piirangutega

Lahendus. Teisendame algse lineaarse programmeerimise ülesande kanooniliseks (vt (2.1.1). Selleks lisame piirangutesse täiendavad mittenegatiivsed muutujad. Nimelt esimesse ebavõrdsusse - muutuja x 4 plussmärgiga, teine ​​- x 5 “-” märgiga (vt §2.2). Piirangute süsteem on järgmine:

Kirjutame selle süsteemi vektorkujul: A 1 x 1 +A 2 x 2 +A 3 x 3 +A 4 x 4 +A 5 x 5 =B, Kus

On ilmne, et selles piirangute süsteemis ei ole ühikupõhist. See tähendab, et vektorite hulgas A j pole kolme vajalikku ühikvektorit, mis peavad moodustama aluse R 3. Kuid pange tähele, et vektor A 4 on osa alusest. See vastab põhimuutujale x 4. On vaja leida veel kaks ühikvektorit. Selleks rakendame kunstliku baasi meetodit. Toome kunstlikud muutujad nendesse piiranguvõrranditesse, milles põhimuutujat ei esine x 4 ja koostage järgmine abiprobleem (AP):

F=-w 1 -w 2 ®max

Kus w 1 , w 2 – tehismuutujad. Õhusaastepiirangute süsteem vektorkujul on järgmine: A 1 x 1 +A 2 x 2 +A 3 x 3 +A 4 x 4 +A 5 x 5 +A 6 w 1 +A 7 w 2 =B, kus vektorid A j , j=1,2,3,4,5 on määratletud samamoodi nagu ülal, ja ja . Seega vektorid A 4 , A 6 , A 7 moodustavad aluse R 3 ja need vastavad põhimuutujatele (BP) – x 4 , w 1 , w 2. Kõik muud muutujad, nimelt x 1 , x 2 , x 3 , x 5 on kuulutatud vabaks (SP). Järgmisena rakendame õhu sisselaskeavale tavalist simpleksmeetodit. Nagu varemgi, vt §5.1, saadakse esialgne võrdlusprojekt vabadele muutujatele nulliga võrdsete väärtuste omistamisel. Sel juhul võtavad põhimuutujad väärtused, mis on võrdsed vabade koefitsientide veeru vastava rea ​​numbritega IN, see tähendab x 1 =x 2 =x 3 =x 5 = 0¸ a x 4 =8, w 1 =4, w 2 = 12. Koostame algsele võrdlusplaanile vastava simplekstabeli:

SP BP.	x 1	x 2	x 3	x 5	B
x 4		-3
w 1				-1
w 2		-2
F	-4		-3		-16

Selle tabeliga teostame simpleksmeetodi vajalikke teisendusi (vt §5.1), kuni saame optimaalse simplekstabeli või saame lahendamatuse. Meie puhul on juba teises etapis järgmine simplekstabel:

SP BP.	w 1	x 2	x 3	w 2	B
x 4	-0,5	-3	-0,5	-0,5
x 1	0,25		0,75	0,25
x 5	-0,75	-2
F

See tabel on EOI jaoks optimaalne. Samal ajal said kõik tehismuutujad vabaks ja max F=0. Näidismuutujatele ja viimasele reale vastavate veergude läbi kriipsutamine ning uue hinnangurea määramine algse eesmärgifunktsiooni abil Z(X), saame algse LP-ülesande algse simplekstabeli:

SP BP.	x 2	x 3	B
x 4	-3	-0,5
x 1		0,75
x 5	-2
Z	-2	2,75

Olles analüüsinud viimast tabelit, järeldame, et algsel LP-ülesandel puudub sihtfunktsiooni piiramatuse tõttu lahendus.

Näide. Funktsiooni minimeerimine piirangute all

Kui võtame kasutusele täiendavad mittenegatiivsed muutujad , , , , ja liigume edasi eesmärgifunktsiooni maksimumi leidmise ülesande juurde, on algne ülesanne järgmine:

Põhilahendus (lubatav plaan) on kujul: , a , , w 1 =10, w 2 =5. Ehitame lennuvälja jaoks esialgsele võrdlusplaanile vastava simplekstabeli:

SP BP.	x 1	x 2	x 3	x 4	B
w 1			-1
w 2				-1
x 5
x 6	-1
F	-1	-1			-15

Tehes teisendusi Jordani-Gaussi meetodi abil, saame teises etapis VZ (5.2.2) optimaalse simplekstabeli. Näidismuutujatele ja viimasele reale vastavate veergude läbikriipsutamine ning uue hinderea määramine eesmärgifunktsiooni abil Z 1 (X), saame ülesande (5.2.1) algse simplekstabeli.

Kunstliku baasmeetodi algoritmil on järgmised omadused:

1. Seoses sellega, et laiendatud ülesande esialgne võrdluslahend sisaldab sihtfunktsioonis koefitsiendiga sisalduvaid tehismuutujaid - M(maksimaalses ülesandes) või + M(minimaalses ülesandes) koosnevad tingimuste vektorite laienduste hinnangud kahest liikmest ja , millest üks ei sõltu M, ja teine oleneb M. Sest M suvaliselt suur võrreldes ühtsusega ( M>> 1), siis arvutamise esimeses etapis kasutatakse baasi sisestatud vektorite leidmiseks ainult hinnangute tingimusi. .

2. Võrdluslahenduse põhjal tuletatud tehismuutujatele vastavad vektorid jäetakse arvesse.

3. Pärast seda, kui kõik tehismuutujatele vastavad vektorid on baasist välja jäetud, jätkatakse arvutamist tavalisel simpleksmeetodil, kasutades hinnanguid, mis ei sõltu M.

4. Üleminek laiendatud ülesande lahendamiselt algülesande lahendamisele toimub ülaltoodud teoreemide 4.1-4.3 abil.

Näide 4.4. Lahendage lineaarse programmeerimise ülesanne kunstliku baasi meetodil

.

Lahendus. Loome laiendatud ülesande. Toome piirangute süsteemi võrrandite vasakpoolsetesse servadesse mittenegatiivsed tehismuutujad koefitsiendiga (alati) +1. Sisestatud tehismuutujad on mugav kirjutada võrranditest paremale. Esimesse võrrandisse sisestame , teise - . See probleem on maksimumi leidmise probleem, seetõttu sisestatakse need sihtfunktsiooni koefitsiendiga - M. Me saame

Probleemil on esialgne võrdluslahendus ühikupõhiselt .

Arvutame tingimusvektorite hinnangud võrdluslahendi ja sihtlahenduse sihtfunktsiooni väärtuse põhjal.

.
.

Lähteandmed salvestame simplekstabelisse (tabel 4.6).

Tabel 4.6

Samal ajal hinnanguid ja Arvutuste mugavuse huvides kirjutame kahes reas: esimeses - terminid, millest ei sõltu M, teises - tingimused , olenevalt M. Väärtused mugav tähistada ilma M, pidades siiski meeles, et see on seal olemas.

Esialgne tugilahendus ei ole optimaalne, kuna maksimaalse probleemi hinnangud on negatiivsed. Valime võrdluslahenduse baasi sisestatud vektori numbri ja baasist väljundi vektori numbri. Selleks arvutame iga negatiivse hinnanguga vektori baasi sisestamisel sihtfunktsiooni juurdekasvud ja leiame selle juurdekasvu maksimumi. Sel juhul on hinnangute tingimused (ilma M) jäetakse tähelepanuta nii kaua kui vähemalt üks tähtaeg (Koos M) ei erine nullist. Sellega seoses ei pruugi hinnangute tingimustega rida tabelis olla seni, kuni rida on olemas . Leiame kell k= 3.

Kolmandas veerus " " valime lahutuselemendiks teise rea koefitsiendi 1 ja teostame Jordani teisenduse.

Alusest tuletatud vektor jäetakse vaatlusest välja (kriipsutatud). Saame võrdluslahuse alusega (Tabel 4.7). Lahendus ei ole optimaalne, kuna on negatiivne hinnang = — 1.

Tabel 4.7

Veerus " " võtame lahenduseks ainsa positiivse elemendi ja liigume edasi uue võrdluslahenduse juurde alusega (Tabel 4.8).

Tabel 4.8

See etalonlahendus on laiendatud ülesande ainus optimaalne lahendus, kuna maksimumülesandes on hinnangud kõigi baasi mittekuuluvate vektorite kohta positiivsed. Teoreemi 4.1 kohaselt on ka algne probleem optimaalne lahendus, mis saadakse laiendatud ülesande optimaalsest lahendusest, jättes kõrvale null tehismuutuja, s.o. X* = (0,0,6,2).

Vastus:max Z(X) = -10 at .

Näide 4.5. Lahendage kunstliku baasmeetodi abil lineaarse programmeerimise ülesanne segapiirangutega

Lahendus. Me vähendame lineaarse programmeerimise probleemi kanooniline vorm. Selleks lisame esimesse ja kolmandasse piirangusse lisamuutujad. Me saame

.

Loome laiendatud ülesande, mille jaoks sisestame kunstlikud muutujad vastavalt teise ja kolmandasse võrrandisse. Me saame

Sellel laiendatud probleemil on esialgne tugilahendus

Ühikupõhiselt , . Arvutame võrdluslahenduse põhjal tingimusvektorite hinnangud ja kirjutame need simplekstabelisse samamoodi nagu eelmises näites. Lahendus ei ole optimaalne, kuna miinimumülesandes on vektorid ja positiivsed hinnangud. Tugilahenduste täiustamine. Igal võrdluslahendusel on oma tabel. Kõiki tabeleid saab kirjutada üksteise alla, liites need üheks tabelisse (tabel 4.9).

Tabel 4.9

Määrame, milline vektoritest või algse tugilahenduse alusele toob kaasa sihtfunktsiooni suurema vähenemise. Leiame kell k= 2, st parem on vektor baasi sisestada. Teise tugilahenduse saame koos alusega . Objektiivne funktsioon . See lahendus pole ka optimaalne, kuna vektoril on positiivne väärtus . Viime vektori baasi sisse, saame baasiga kolmanda võrdluslahendi . Objektiivne funktsioon . See lahendus on optimaalne, kuid mitte ainus, kuna baasi mittekuuluv vektor on nullhinnanguga. Seetõttu on vaja üle minna uuele etalonlahendusele, mis on samuti optimaalne. Selleks peate sisestama vektori baasi.

Liigume edasi neljanda võrdluslahenduse (optimaalse) juurde

Koos alusega , samal ajal . Laiendatud probleemi optimaalsetel lahendustel pole tehismuutujaid null. Seetõttu on (teoreemi 4.1 järgi) ka algülesandel kaks optimaalset lahendust Ja . Algülesande optimaalses lahenduses me lisamuutujaid ei kirjuta.

Vastus: juures , , , .

Sõna simpleks

Sõna simplex inglise tähtedega (translit) - simpleks

Sõna simpleks koosneb 8 tähest: e ja k l m p s s

Sõna simpleks tähendused. Mis on simpleks?

Lihtne

Simpleks (ladina keelest simplex - lihtne) (matemaatiline), lihtsaim kumer hulktahukas antud number mõõtmed n. Kui n = 3, on kolmemõõtmeline struktuur suvaline, sealhulgas ebakorrapärane tetraeeder.

TSB. - 1969-1978

Simpleks on kumer hulknurk n-mõõtmelises ruumis, millel on n+1 tippu, mis ei asu samal hüpertasandil. S. on eraldi klassina välja toodud, kuna n-mõõtmelises ruumis asuvad n punkti alati samal hüpertasandil.

slovar-lopatnikov.ru

SIMPLEX on kumer hulknurk n-mõõtmelises ruumis, millel on n+1 tippu, mis ei asu samal hüpertasandil. S. on eraldi klassina välja toodud, kuna n-mõõtmelises ruumis asuvad n punkti alati samal hüpertasandil.

Lopatnikov. - 2003

Sub simplex

Sub simplex Kasutusjuhised ja annustamine: Suukaudselt, söögi ajal või pärast sööki ja vajadusel enne magamaminekut. Enne kasutamist loksutage pudelit tugevalt.

ZLP lahendamine simpleksmeetodil kunstlikul alusel

Et suspensioon pipetist voolama hakkaks...

Sab simplex Toimeaine ›› Simetikoon* (Simethicone*) Ladinakeelne nimetus Sab simplex ATX:›› A02DA Karminatiivsed ravimid Farmakoloogiline rühm…

Ravimite sõnastik. — 2005

SAB® SIMPLEX (SAB® SIMPLEX) Valge kuni hallikasvalge värvusega suukaudne suspensioon, kergelt viskoosne, iseloomuliku puuviljase (vanilje-vaarika) lõhnaga. 100 ml simetikooni 6,919 g…

SHOCKE SIMPLEX

CHOQUET SIMPLEX on mittetühi kompaktne kumer hulk X lokaalselt kumeras ruumis E, millel on järgmine omadus: kui E on sisestatud ruumi hüpertasandina, tekib eenduv koonus.

Sheffield Simplex

"Sheffield-Simplex" - kerge kuulipilduja soomussõiduk Relvajõud Vene impeerium. Briti firma Sheffield-Simplex poolt välja töötatud enda sõiduauto šassii baasil...

en.wikipedia.org

Norditropin Simplex

Norditropin Simplexi näidustused: kasvupeetus lastel kasvuhormooni puudulikkuse või kroonilise neerupuudulikkuse tõttu (prepuberteedieas), Shereshevsky-Turneri sündroom...

NORDITROPIN® SIMPLEX® (NORDITROPIN SimpleXx) Lahus subkutaanseks manustamiseks 1,5 ml (1 kolbampull) somatropiin 10 mg 1,5 ml - padrunid (1) - kontuurirakkude pakend (1) - papppakendid.

Kataloog ravimid"Vidal"

STANDARD LIHTNE

STANDARD LIHTNE - 1) S. s - mõõtmega n ruumiline tippude punktid e i=(0,..., 1,..., 0), i=0,..., n (the. seade on sisse lülitatud i-s koht), st.

Matemaatiline entsüklopeedia. - 1977-1985

Kahekordne simpleksmeetod

Duaalsimpleksmeetodi abil saab lahendada lineaarse programmeerimise ülesande, mille võrrandisüsteemi vabaliikmeteks võivad olla suvalised arvud. Normaalses korras simpleksalgoritm plaan peab alati kehtima.

en.wikipedia.org

vene keel

Lihtne/.

Morfeemilise õigekirja sõnastik. - 2002

Otsi Loengud

Näide ülesande lahendamisest kunstliku baasi meetodil.

Leia funktsiooni miinimum F=-2×1+3×2 – 6×3 – x4 tingimustel

Lahendus. Kirjutame selle ülesande põhiülesande kujul: leia funktsiooni maksimum F1=2×1 – 3×2 + 6×3 + x4 tingimustel

Viimase ülesande võrrandisüsteemis arvestage tundmatute koefitsientide vektoreid:

A1= A2= A 3= A 4= A 5= A 6=

Vektorite hulgas A1,…, A 6 ainult kaks üksikut ( A 4 ja A 5). Seetõttu lisame piirangute süsteemi kolmanda võrrandi vasakule küljele täiendava mittenegatiivse muutuja x 7 ja kaaluge funktsiooni maksimeerimise laiendatud probleemi

F=2×1 – 3×2 + 6×3 + x4 – Mx7

tingimustel

Laiendatud ülesandel on võrdlusplaan X=(0; 0; 0; 24; 22; 0; 10), mis on defineeritud kolmest ühikuvektorist koosneva süsteemiga: A 4 , A5 , A7 .

Tabel 1

i	Alus	Сσ	A0	-3	—M
A1	A2	A3	A4	A5	A6	P7
A4	-2
A5
A7	—M	-1	-1
m+1			-8
m+2			-10	-1	-2

Koostame viit rida sisaldava iteratsiooni I tabeli (1). 4. ja 5. rea täitmiseks leiame F 0 ja erinevuse väärtused zj – cj(j=):

F 0 = 24-10M;

z1–c1= 0–M;

z2–c2 = 4+M;

z3–c3= –8–2M;

z4–c4=0+M;

z5–c5=0+M;

z6–c6= 0+M;

z7–c7=0+M;

Väärtused F 0 ja zj–cj koosneb kahest terminist, millest üks sisaldab M, ja teine ​​mitte.

Iteratiivse protsessi mugavuse huvides on arv, mis koosneb M, kirjutage 5. reale ja termin, mis ei sisalda M, – 4. real.

Tabeli 1 5. real vektorite veergudes Аj (j= ) on kaks negatiivset arvu (-1 Ja -2). Nende numbrite olemasolu näitab, et see laiendatud probleemi võrdlusplaan ei ole optimaalne. Liigume edasi laiendatud probleemi uue võrdlusplaani juurde.

Kunstlik alusmeetod.

Sisestame vektori baasi A3. Alusest välja jäetud vektori määramiseks leiame θ=min(22/4; 10/2)=10/2. Seetõttu vektor A7 alusest välja jäetud. Seda vektorit ei ole mõtet sisestada ühtegi järgnevasse baasi, mistõttu edaspidi selle vektori veergu ei täideta (tabelid 2 ja 3).

Koostame iteratsiooni tabeli II (tabel 2). See sisaldab ainult nelja rida, kuna tehisvektor on baasist välja jäetud.

Tabel2

i	Alus	Сσ	A0	-3
A1	A2	A3	A4	A5	A6
A4	-1
A5	-1
A3	1/2	-1/2	-1/2
m+1			-4

Nagu tabelist näha. 2, algse probleemi puhul on viide plaan X=(0;0;5;34;2).

Kontrollime selle optimaalsust. Selleks kaaluge 4. rea elemente. Selles reas vektori veerus A6 on negatiivne arv (-4). Järelikult ei ole see võrdlusplaan optimaalne ja seda saab vektori kasutuselevõtuga täiustada A6. Vektor jäetakse alusest välja A5. Koostame iteratsiooni tabeli III.

Tabel 3

Tabeli 3 4. real numbrite hulgas ∆j ei mingeid negatiivseid. See tähendab, et leiti algse probleemi uus võrdlusplaan X*=(0; 0; 11/2; 35; 0; 1) on optimaalne. Selle plaani puhul on lineaarse vormi väärtus Fmax = 68.

Selle probleemi saab lahendada ühe tabeli abil, kuhu kõik iteratsioonid järjestikku salvestatakse.

©2015-2018 poisk-ru.ru
Kõik õigused kuuluvad nende autoritele. See sait ei pretendeeri autorlusele, vaid pakub tasuta kasutamine.
Autoriõiguste rikkumine ja isikuandmete rikkumine

Seni oleme kõikehõlmavalt käsitlenud probleemi, mille lahendamine viidi läbi simpleksmeetodi lihtsaima algoritmi alusel, kuna kõik piirangud olid kujult väiksemad või võrdsed. Sel juhul täiendav ülesande muutujad moodustavad üksuse aluse. Kuid võib selguda, et piirangute süsteem esitatakse kanoonilisel kujul, kuid see ei ole taandatud ühikupõhiseks.

Selliste probleemide lahendamisel võeti see kasutusele kunstlik alusmeetod. See on eriti mugav, kui muutujate arv ületab oluliselt võrrandite arvu.

Vaatleme näite abil ülesande lahendamise algoritmi, kasutades kunstlikul alusel simpleksmeetodit.

Näide 1

Leidke maksimaalne Z=4X1+2X2+X3

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

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

Liigume edasi kanoonilise vormi juurde:

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

See süsteem piirangutel ei ole ühikulist alust, kuna lisamuutuja X4 koefitsient on miinus üks ja kolmas piirang esitati võrrandiga ja sellel ei ole alusmuutujat. Ühikupõhiseks toome sisse vastavad piirangud kunstlikud muutujad y1 ja y2 positiivsete koefitsientidega (+1).

Tuleb märkida, et tehismuutujad võetakse kasutusele ainult ülesande matemaatiliseks vormistamiseks. Seetõttu peab arvutusskeem olema selline, et põhimuutujate hulka ei saaks lõpplahenduses kaasata kunstlikke muutujaid. Selleks võetakse sihtfunktsiooni tehismuutujate jaoks kasutusele koefitsient M, mis tähistab väga suur hulk. Praktikas (eriti arvutis ülesande lahendamisel) võtavad nad M asemel konkreetse suure arvu, näiteks 10000. Veelgi enam, ülesande maksimaalsel lahendamisel sisestatakse see koefitsient sihtfunktsiooni miinusega. märgiga ja miinimumini lahendamisel plussmärgiga. Nüüd lahendame T (M)-ülesande, mille eesmärkfunktsioon sisaldab Z-ülesande sihtfunktsiooni ja tehismuutujaid koefitsiendiga ±M, s.o.

T=Z-M S yi, sihifunktsiooni maksimumi lahendamisel ja

T=Z+M S y, sihifunktsiooni miinimumi lahendamisel

Meie puhul:

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)

See probleem on lahendatud simplekstabelites, kuid mugavuse huvides on eesmärkfunktsioon jagatud kaheks reale:

Esimesele reale kirjutame üles hinnangud, mis ei sisalda koefitsienti M;

Teine rida sisaldab hinnanguid iga vaba muutuja kohta, mis sisaldab koefitsienti M.

Nende kahe rea elementide (skooride) arvutamine toimub vastavalt valemile (2). Ainus erinevus:

Z-rea hinnangute arvutamisel tuleb arvestada Z-funktsioonis sisalduvate koefitsientidega Cj;

M-rea hinnangute arvutamisel seda koefitsienti arvesse ei võeta ja M võetakse ühise tegurina välja.

Selleks, et T-ülesanne ja Z-ülesanne oleksid võrdsed, on vaja, et yi oleks võrdne nulliga. Seega, kuni y i ei ole null, valitakse lahendusveerg teise rea hinnangute põhjal, kasutades simpleksmeetodi algoritmi.

Alles pärast seda, kui kõik y i on võrdsed nulliga, tehakse edasine arvutus esimese indeksirea abil, st. - tavaline Z-ülesanne.

Veelgi enam, kui tehismuutuja tuletatakse baasist, viskame selle simplekstabelist välja ja järgmisel simplekstabelis ei ole endist lahutusveergu.

M-ülesande ja Z-ülesande optimaalsete lahenduste vahel on seos, mis on kindlaks tehtud järgnevaga teoreem:

1. Kui M-ülesande optimaalses lahenduses on kõik tehismuutujad (y i) võrdsed nulliga, siis on see lahendus Z-ülesande optimaalne lahendus.

2. Kui M-ülesande optimaalses lahenduses erineb vähemalt üks tehismuutujatest nullist, siis Z-ülesandel puudub lahendus piirangute süsteemi mitteühilduvuse tõttu.

3. Kui M-ülesanne osutub lahendamatuks (T®+¥ või -¥), siis on ka algülesanne lahendamatu kas piirangute süsteemi mitteühilduvuse või funktsiooni Z piiramatuse tõttu.

Loome esimese simplekstabeli. M-meetodil lahendamisel saab M-reas valida lahendava veeru mitte kõige suurema järgi absoluutväärtus negatiivne hinnang (maksimumi lahendamisel) ja mitte suurima positiivse hinnangu järgi (miinimum lahendamisel), vaid selle järgi, mis Y-i kiiremini baasist eemaldab. IN selles näites Lahutav veerg on vaba muutuja X2 veerg hindega (-3).

Tabel 3.1.

Esiteks simpleks laud

Z-joone täitmine toimub vastavalt valemile (2):

a00 = 0 × 8– 0 = 0

a01 =0 × 2–4 = -4

a02 =0 × 1–2 = -2

a03 =0 × 1–1 = -1

a02 =0 × 0–0 = 0

M-rea täitmine:

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

а¢01 = -М × 1 + (–М) × 3= -4М

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

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

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

Me võtame ühise tegurina välja M.

Lahutusrea viimane veerg sisaldab 0, seega kantakse vaba muutuja X4 veerg ilma muudatusteta.

Tabel 3.2.

Teine simplekstabel

Teises tabelis saame degenereerunud lahendi, kuna saame kaks identset minimaalset simpleksseost. Seetõttu leiame lahendava kõrval oleva veeru elementide seose lahendava veeru elementidega, võttes arvesse märki.

Tabel 3.3.

Kolmas simplekstabel

Nüüd lahendame tavalise simpleksmeetodi abil.

Tabel 3.4.

Neljas simplekstabel

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

Hindamisreal on kõik elemendid mittenegatiivsed, seega saadakse optimaalne lahendus:

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

Näide2

Ülesanne lahendati sihtfunktsiooni miinimumini (Z®min). Viimasel iteratsioonil saime järgmise tabeli:

Tabel 3.5.

Uusim simplekstabel

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

T-ülesandes saadi optimaalne lahendus, kuna M-real pole enam positiivseid hinnanguid, s.t. Lahutava veeru valik on võimatu ja U1 on baasis. Sel juhul pole algsel probleemil lahendust piirangute süsteemi kokkusobimatus.