4. Такрорланувчи кадам.
б) (6) даги a'1j, a'2j,..., a'mj сонлар орасида мусбатлари бор. Масалан, a'kj0 булсин. У холда xk=b'k-a'kjxj да xj га b'k/a'kj дан катта киймат бериш мумкин эмас, акс холда xk0 булиб колади. Бунда bk' a'kj 0 эканлиги равшан. Бундай касрлар a'kj орасида энг кичик bi/aij булиб, a'ij сон хал килувчи элементдир. Кискалик учун bi/aij=p белгилаш киритамиз. (6) да xi ни p - гача орттира оламиз, акс холда xi0 булишини курдик. Озод ноъмалумларга.
(Z) xm+1=xm+2=...=xj-1=xj+1=...=xn=0, xj=p (7) кийматларни бериб, базис номаълумларни куйдагича аниклаймиз.
x1=b'1-a'1p
x2=b'2-a'2p
................
(8) xi=b'i-a'ijp
...............
xm=b'jn- a'mjp
Энди янги Б2 базисга утамиз:
Б2={x1,x2,..., xi,..., 0,0,..., 0}
Бу базис ечим (7) ва (8) дан тузилади ва унга мос Z (Б2) нинг киймати куйидагига тенг булади;
Z=(Б2)=c'o-c'j (Б1) , c'j0
Энди (3) система ва максад функция (4) ни янги базис Б2 га мослаб езамиз.
Бунинг учун (3) даги
xi=b'i-(a'im+1xm+1+...+a'ijxj+...+a'inxn)
тенгламани xj-га нисбатан ечамиз.
xj=b'/aij-(a'im+1/a'ij xm+1+ a'im+2/a'ij+...+ 1/a'ij xi+...+a'in/a'ij xn)
ва бу ифодани (3) нинг колган тенгламаларига куямиз. Хосил булган янги системани куйдаги куринишда езамиз.
x1=b''1-(a''1m+1xm+1+a''1m+2xm+2+...+a''1ixi+...+ a''1nxn)
x2=b''2-(a''2m+1xm+1+a''2m+2xm+2+...+a''2ix2+...+a''2mxn)
(4) ..............................................................................
xj=b''j (a''jm+1xm+1+...+ a''jnxn)
xm=b''m-(a''mm+1xm+1+a''mm+2xmm+2+...+a''mn xn)
Бу базиснинг ифодаларини (4) га куйиб, уни куйидаги куринишга келтирамиз
Z=c''o-(c''m+1xm+1+c'm+2xm+2+...+c''jxj +...+c''nxn)
Шу билан процесснинг биринчи боскичи тугади.
Кейинги боскич, яна шу боскични такрорлашдан иборат.
5. Симплекс усулни бажариш жараёни.
Шундай килиб симплекс учул куйидаги процессни ифодалайди:
1. Чекланишли тенгламалари системаси (2) ни (3) куринишга, максад функция (1) ни эса (4) куринишга келтирамиз.
2. Агар (4) да барча c'm+1,c'm+2,c'n коэффициентлар манфий булса, Б1 базис нинг {b'1,b'2,...,b'm,0,0,...,0} ечими оптимал булиб, бу ечимда Z(Б) =с'о минимумга эришади.
3. (4) да c'm+1,c'm+2,...,c'n лар орасида мусбатлари мавжуд, маслан c'j0 десак, xm+1=xm+2=...=xj-1=xj+1=...=xn=0 xj0 кийматларда (3) система (6) куринишни олади. Агар (6) да барча коэффициентлар мусбат булмаган min z=- келаб чикади, яъни z функция минимумга эришмайди.
(6) даги akj k=1,m коэффициентларнинг мусбатлари мавжуд, яъни a'2j0 десак, b'r/a'rj сонлар орасидаги энг кичиги булган b'i/a'ij оламиз. (3) системанинг xi га нисбатан езилган тенгламасидан xi ни аниклаб, (3) системани янги Б2={x1,x2,...,xi,...,xm,0,...,0} базис ечимга нисбатан езиб 0 ни хосил киламиз, максад функция (4) ни эса (10) куринишда ифодалаймиз. Янги ноъмалумлар x1,x2,...,xj-1, xi,xj+1,...,xn дан иборат булади.
Мисол. Ушбу
2x1+3x2+x3=19
2x1+x2+x4=13 (1)
3x2+x5=15
3x1+x6=18
системанинг мусбат ечимлари орасидан
(2) Z=-7x1-5x2 функцияга минимум берувчи ечимини топинг.
Ечиш. Системани x3,x4,x5 ва x6 номаълумларга нисбатан ечамиз, яъни
x3=19-2x1-3x2
x4=13-x2-2x1
x5=15-3x2 (3)
x6=18-3x1
Бу ерда x3,x4,x5,x6 лар базис x1=x2=0 да x3=19, x4=13 , x5=15 , x6=18 келиб чикади. Шундай килиб, базис деб аталган куйидаги
Б1={0,0,19,13,15,18}
уринли ечимга эга буламиз. Z=-(7x1+5x2)
(2) функциянинг бу ечимга мос киймати
Z(Б1) =-7·0-5·0=0; булади.
(2) дан Куриниб турибдики х1 ва х2 нинг кийматлари ошиши билан Z - камаяди. Яна (2) дан 5х2 га нисбатан 7х1 да Z тезрок камайишини курамиз. Шу сабабли х2=0 х10 деб олиб х1га х1=6 киймат берамиз (чунки х60 18-3х0 х16) х1 булганда х3 х4, х50 ва х6,х2=0, х1=6 да х30, х40, х5 ва х6=0 булади
Энди янги х1,x3,x4,x5 базисга утиш кулай булиб x1,x3,x4,x5 - га нисбатан ечамиз.
x1=6-1/3x6
x3=7+2/3 x6-3x2 (4)
x4=1+2/3 x6-x2
x5=15-3x2
(2) -Z-нинг бунга мос ифодаси
Z=-42+7/3 x6-5x2 (5)
x6=0 , x2=0 булганда куйдаги уринли ечимга эга буламиз
Б2{6,0,7,1,15,0}
базис ечим бунда
Z (Б1)= -42 Z (Б1)
Лекин Z функция х2- ошиши билан камаяди.
х6- ошиши билан ошади. Шунинг учун х6=0 ва 0х21 деб оламиз чунки х2 да х40 булади
х1,х2,х3,х5- базисга утиш учун ушбу системани хосил киламиз.
x1=6-1/3 x6
x2=1+2/3 x6-x4
(6) x3=7+2/3 x6-3(1+2/3x6-x4)=4-4/3x6+3x4
x5=15-3(1+2/3x6-x4)=12-2x6+3x4
Бунинг иккинчи тенгламасини Z=-42+7/3x6-5x2 га олиб бориб куйсак куйидагига эга буламиз
Z=-47+5x4-x6 (7)
x4=0, x6=0 булганда янги базис ечим
Б3={6,1,4,0,15,0}
ни хосил киламиз. Бу ечимда
Z (Б3)=-47
Энди (7) эътибор берсак, х6 ортганда Z нинг камайишини курамиз. Бирок х4=0 да х10, х20, х30, х50 шартлар бузулмаслиги учун (6) дан х6ни 3 гача ортиришимиз мумкин х63 булса х30 х6=3 да х3=0 булади.
х1,х2,х5,х6 базисга утиш учун (6) дан ушбу тенгликни хосил киламиз.
х6=3+9/4 x4-3/4x3
x1=5-3/4 x4+1/4x3
x2=3+3/2 x4-3/4x4
x5=6-3/2 x4 -3/2x3
Бу ифодани (7) га куйсак
Z=-47+5x4-3-9/4x4+3/4 x3=-50+3/4x3+11/4x4
x3=0, x4=0 булганда Б4={5,3,0,0,6,3}
Бу ечимда Z нинг киймати
Z(Б4)=-50 х3 ва х4 ларнинг коэффициентлари Z(Бn)=-50 оптимал ечим экан.
Саволлар.
1.Симплекс усулда кандай дастурлаштириш масалалари ечилади?
2.Базис номаълумлар деб кандай номаълумлага айтилади?
3.Эркли номаълумлар деб кандай номаълумларга айтилади?
4.Качон симплекс усулда ечилаётган масаланинг ечими йук деб айтилади?
5.Симплекс усулда ечиш качонгача давом этади?
6.Симплекс усулда качон минимумга эришилган дейилади?
7.Симплекс усулда качон максимумга эришилган дейилади?
8Симплекс усулнинг мураккаблик томонлари нимада?
9.Киритилган кушимча номаълум кандай маънога эга?
10.Озод хадлар манфий булаши мумкинми?
|
