Nókis filialí «Kompyuter injiniring» qánigeligi

2.2. Sızıqlı programmalastırıw máselelerin sheshiwde simpleks usıl algoritmı hám programması.

Simpleks usılı izbe-iz jaqınlasıw usılı járdeminde x1, x2,... xn ózgeriwshilerdiń sonday optimal ma`nisin tabadıki, bul bahalar maqset funksiyasına maksimal (yamasa minimal ) baha beredi.

Tómendegi sızıqlı programmalastırıw máselesi berilgen bolsın :

Máseleni sheshiw ushın simpleks keste quramız hám simpleks usılı ideyasın beriw ushın berilgen máseleni tómendegishe kanonik formada jazamız.

Bul jerde x_n+i- azat ózgeriwshiler dep ataladı. Olardı qolaylıq, hám basqa ózgeriwshilerden parıqlaw ushın uyqas túrde y₁, y₂,... y_m dep belgileymiz hám tómendegi belgilewlerdi kiritemiz b_i0=b_i; b_i,j=a_i,j; b_0j=c_j. Bul belgilewler tiykarında tómendegi simpleks keste dep atalıwshı kesteni dúzemiz.

BO‘	1	-x1	-x2	. . .	-xs	. . .	-xn
y1	b10	b11	b12	. . .	b1s	. . .	b1n
y2	b20	b21	b22	. . .	b2s	. . .	b2n
. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .
ys	br0	br1	br2	. . .	brs	. . .	brn
. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .
ym	bm0	bm1	bm2	. . .	bms	. . .	bmn
Z	b00	b01	b02	. . .	b0s	. . .	b0n

Sızıqlı programmalastırıw máselesin simpleks usıl járdeminde sheshiw eki basqıshdan ibarat :
1. Baslanǵısh tayansh plandı tabıw.
2. Tayansh planlar ishinen máseleniń optimal planın tabıw.


Máseleniń tayansh planın dúziw.
Baslanǵısh tayansh plandı tabıw tómendegi algoritm boyınsha atqarıladı :
1. Simpleks kesteden sheshiwshi elementti tabıw :
1. 1. Sheshiwshi elementti tabıw aldın sheshiwshi ústindi tabıwdan baslanadı. Onıń ushın azat hadlar ústinine qaraladı. Eger azat xadlar ústinindegi elementler hámmesi oń bolsa, bul baslanǵısh plan tayansh plan boladı hám ekinshi etapga ótiledi. Eger keri element ámeldegi bolsa, olardan modul boyınsha eń úlkeni saylanadı (eger bir bolsa sol element ózi alınadı ). Mısal ushın bul element b_r0 bolsın. Sol b_r0 element turǵan r qatar qaraladı. Eger qatar elementlerinen hámmesi oń bolsa, máseleniń sheshimi ámeldegi bolmaydı (bul halda esaplawlar sol orında toqtatıladı ). Eger qatarda keri element ámeldegi bolsa, olardan modul boyınsha eń úlkeni saylanadı (eger bir bolsa ózi alınadı ). Sol element turǵan ústin sheshiwshi ústin dep ataladı. Mısal ushın bul s -shi ústin bolsın.
1. 2. Sheshiwshi qatar tabıladı. Azat xadlar sheshiwshi ústin elementlerine bólip shıǵıladı hám olardan ońlarınıń eń kichigi saylanadı, yaǵnıy:

Mısalı ushın, bul koefficientler ishinde ońlardıń eń kishisi b_r0/b_rs bolsın. Ol halda sol b_rs element turǵan qatar sheshiwshi qatar dep ataladı, b_rs elementtiń ózi bolsa sheshiwshi element boladı.
2. Sheshiwshi ústin hám qatar ózgeriwshileri orınları almastırıladı, (yaǵnıy x_s hám y_s jańa kestede orınların almasadı ).
3. Kestede simpleks almastırıw atqarıladı.
3. 1. Sheshiwshi ústin elementleri sheshiwshi elementke bolıp shıǵılıp jańa kestege jazıladı, yaǵnıy:
3. 2. Sheshiwshi qatar elementleri sheshiwshi elementke bólip shıǵılıp jańa kestege jazıladı, yaǵnıy:
3. 3. Sheshiwshi element 1 ge teńlestirilip ózine bólinedi, yaǵnıy:
3. 4. Jańa simpleks kesteniń qalǵan elementleri tómendegi formula arqalı tabıladı.
yaki

Jańa kestede b´_bj -elementti esaplawda eski kesteden b_ij, b_is, b_rj, b_rs elementlerin tabıw tómendegishe boladı :

B_ij - b´_ij elementtiń eski kestedegi oǵan uyqas element;
B_is –b_ij element turǵan qatar menen b_r sheshiwshi element ústini kesilispesindegi element;
B_rj –b_ij element turǵan ústin menen b_rs sheshiwshi element qatarı kesilispesindegi element;
B_rs - sheshiwshi element.

BO‘	1	-x1	-x2	. . .	-yr	. . .	-xn
y1	b’10	b’11	b’12	. . .	b’1s	. . .	b’1n
y2	b’20	b’21	b’22	. . .	b’2s	. . .	b’2n
. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .
xs	b’r0	b’r1	b’r2	. . .	b’rs	. . .	b’rn
. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .
ym	b'm0	b’m1	b’m2	. . .	b’ms	. . .	b’mn
Z	b’00	b’01	b’02	. . .	b’0s	. . .	b’0n

4. Jańa tabılǵan simpleks kestede tayansh plan ámeldegi bolsa ekinshi basqıshqa, yaǵnıy optimal plandı tabıwǵa ótiledi, keri jaǵdayda joqarıdaǵı process jańa keste ushın tok, tayansh plan tabılǵansha qayta tákirarlanadı.

Máseleniń optimal planın tabıw.
Eger 1 basqıshdan alınǵan tayansh plannıń simpleks keste degi Z-qatar elementleri (azat hadi b´₀₀ den tısqarı ) hámmesi oń bolsa, bul alınǵan baslanǵısh tayansh plan birden-bir hám ol máseleniń optimal planı (sheshimi) boladı. Eger Z qatardaǵı hámme oń elementlerden keminde birewi nolge teń bolsa, ol halda máseleniń sheksiz kóp optimal planı ámeldegi boladı. Eger Z qatardaǵı elementlerden hesh bolmaǵanda birewi keri bolsa, optimal plan tómendegi algoritim boyınsha tabıladı :
1. Sheshiwshi elementti tabıw.
1. 1. Sheshiwshi ústin tabıladı. Z-qatardaǵı keri elementlerdiń modul boyınsha eń úlkeni (bir bolsa ózi) saylanadı. Sol element turǵan ústin sheshiwshi ústin boladı.
1. 2. Sheshiwshi qatar tabıladı. Azat hadlar elementleri sheshiwshi ústin elementlerine bólip shıǵıladı hám olardan ońlarınıń eń kishisi alınadı, yaǵnıy birinshi basqıshdıń 1. 2 punktindegi sıyaqlı. Bul sanǵa uyqas keliwshi ústindegi element sheshiwshi element hám sol element turǵan qatar bolsa sheshiwshi qatar boladı.
2. Sheshiwshi qatar hám ústin ózgeriwshileri óz jayların almastıradı.
3. Kestede simpleks almastırıw atqarıladı. Simpleks almastırıw 1- basqıshdaǵı 3. 1, 3. 2, 3. 3, 3. 4 punktler sıyaqlı atqarıladı.
4. Jańa tabılǵan kesteniń Z qatarı qaraladı. Eger Z qatardaǵı hámme elementler oń bolsa, alınǵan aqırǵı plan máseleniń optimal planı boladı. Keri jaǵdayda joqarıdaǵı 1, 2, 3 punktler taǵı tákirarlanadı, bul prosses optimal plan tabılǵansha dawam etedi.
Túsindirme: Sızıqlı programmalastırıw máselesinde, eger maqset funksiyasınıń minumimi ızlense joqarıdaǵı 1-shi basqısh tolıqlay orınlı bolıp, 2-basqıshda bolsa tek Z -qatar elementleri keri jaǵdayǵa keltiriliwi kerek, yaǵnıy teris jaǵday boladı.

1-mısal:

z=5x₁-x₂+3x₃
Sızıqlı funksiyaǵa maksimum mánis beretuǵın


x₁+x₂+x_3Ј2
4x₁+2x₂+x_3Ј3
x₁-x₂+2x_3Ј-1
-3x₁+2x₂-2x_3Ј5
x_1і0, x_{2 і}0,x_3і0
Shegaralıq sistemanıń múmkin bolǵan sheshimleri salasında belgisizler tabılsın. Shegaralıq sistemanı kanonik kóriniste tómendegishe jazıp alamız :
x₁+x₂+x₃+x₄=2
4x₁+2x₂+x₃+x₅=3
x₁-x₂+2x₃+x₆=-1
-3x₁+2x₂-2x₃+x₇=5
x_1і0, x_{2 і}0,x_3і0

Teńlemede bazis ózgeriwshilerdi simpleks ózgeriwshilerden parıqlaw ushın х₄=у₁ , х₅=у₂ , х₆=у₃ , х₇=у₄ belgilewlerdi kiritemiz hám Simpleks keste dúzemiz.

So‘ Bo‘	1	-х1	-х2	- х3
у1	2	1	1	1
у2	3	4	2	1
у3	-1	1	-1	2
у4	5	-3	2	-2
Z	0	-5	1	-3

Ózgeriwshilerdiń keri bolmaw shárti berilgenligin esapqa alıp, tuwrıdan-tuwrı tayansh sheshimdi tabıwǵa kirisiwemiz. Azat hadlar ishinde -1 keri belgili koefficiyent bar. Sol qatardan belgisi keri bolǵan modul boyınsha eń úlken elementti tabamız. Ol x₂ ústinindegi -1 element bolıp tabıladı. Qaǵıydaǵa qaray oń koefficientler ishinen eń kishisin tabamız:

+min2/1, 3/2, -1/-1, 5/2}=1/1

Sonday eken, oǵan uyqas element x₂ ústinindegi -1 element. Bul element sheshiwshi element boladı. Endi Simpleks almastırıw etip, tómendegi kesteni dúzemiz.

So‘ Bo‘	1	-х1	-y3	- х3
у1	1	2	1	3
у2	1	6	2	5
x2	1	-1	-1	-2
у4	3	-1	2	2
z	-1	-4	1	-1

Bul kesteden kórinip turıptı, olda azat hadlar oń, sol sebep tayansh plan bar. Endi optimal sheshimin tabıw ushın Z qatarına qaraymız. Bul qatarda eki keri belgili koefficiyent bar. Olardan modul boyınsha ma`nisi úlken bolǵan koefficiyentti tańlap alamız, ol -4 elementi bolıp tabıladı. Qaǵıydaǵa qaray sheshiwshi elementti anıqlap jańa keste dúzemiz: +min1/2, 1/6, 1/-1, 3/-1}=1/6
Oǵan uyqas element x₁ ústinindegi 6 element. Bul element sheshiwshi element boladı. Endi Simpleks almastırıw etip, tómendegi kesteni dúzemiz.

So‘ Bo‘	1	-y2	-y3	- х3
У1	2/3	-1/3	1/3	4/3
X1	1/6	1/6	1/3	5/6
X2	7/6	1/6	-2/3	-7/6
У4	19/6	1/6	7/3	17/6
Z	-1/3	2/3	7/3	7/3

Azat hadlar hám Z qatarındaǵı koefficiyentler oń. Sonday eken, optimal sheshim tapildi, yaǵnıy у₂=у₃=х₃=0 hám х₁=1/6, х₂=7/6 bolǵanda Z dıń maksimal ma`nisi -1/3 ge teń boladı, yaǵnıy z=-1/3.