Симплекс әдісі

4.1-кесте

Бұл кестені математика тілінде  матрица деп те атайды, ал 1-ші тік графада тұрған сандарды матрицаның 1-ші бағанасының элементтері, 2-ші графада тұрған сандарды матрицаның 2-ші бағанасының элементтері және т.б.с.с., ал 1-ші жатық графада тұрған сандардың матрицаның 1-ші жолының элементтері дейді және т.б.с.с.

Есепті шешуді симплекс кестені талдаудан бастайды, яғни шешуші бағананы, шешуші жолды және және шешуші элементті анықтайды. Әдебиеттерде бұл көрсеткіштерді әртүрлі айтады. Бұл көрсеткіштерді бағыттаушы бағана, бағыттаушы жол немесе бас элемент деп атайды. Бұл көрсеткіштерді бағыттаушы бағана, бағыттаушы жол немесе бас элемент деп атайық. Симплекс кестені талдау бағыттаушы бағананы анықтаудан басталады. Есепті шешу мынадай алгоритм бойынша жүргізіледі:

1. m+1 жолдың теріс таңбалы элементтерінің ішінен абсолюттік шамасы ең үлкенін таңдайды:

 Max |-C|=C k.-C<0.

                                             J=i.n

Осы бағана бағыттаушы бағана деп аталады да, к-мен белгіленеді. Бағыттаушы бағананы табудағы мақсат-негізгі белгісіздердің ішіндегі базиске енетінін ан.ықтау. Олай болса, X k базистік белгісіздердің қатарына енеді. Геометрияның заңы бойынша базистің саны берілген теңдеу тсаны m-нен артпауы керек, ендеше базистік белгісіздердің бірі базистік құрамынан шығып, Xk-нің орнына баруы керек, былайша айтқанда, олар өзара орын ауыстырады. Орын ауыстырудан бұрын, базистік белгісіздердің құрамының шығатын белгісізді анықтайық.

2. Бос мүшелер бағынасындағы (bi) базистік белгісіздердің жолында жатқан әр санды бағыттауыш бағанасында (k) орналасқан элементтерге бөледі де, ішіндегі ең кіші бөліндіні анықтайды, яғни:

 

                               Min      b1       b2    bm          br

a ik>0   a1k    a2k   amk        ark      i€m

 

демек ең кіші қатынас r–ші жатық жолда жатыр екен делік, онда r –ші жатық жолды бағыттауыш жол деп атайды. Бағыттауыш бағанмен бағыттауыш жолдың қиылысуында жатқан элементті бас элемент деп атайды да, ark деп белгілейді. Бағыттаушы жатық жолдың нөмірі r-мен белгіленеді де, Yr-дің базистік белгісіз базистан шығарылатыны анықталынады.

3. Енді X1 және Yr –дің орындарын ауыстырып жаңа кесте тұрғызу жолын қарастырайық, яғни бір базистен екінші базиске және m+1 жатық жолдары бар жаңа матрица құруымыз керек. Мұндағы негізгі матрицаны А деп белгілесек, онда А матрицасының өлшемі m*n болады, былайша айтқанда, А матрицасы m*n элементтен тұрады. Ал егер А матрицасына соңғы бос мүшелер бағанасын b1, b2, ..., bm қоссақ, ондағы шыққан матрицаны кеңейтілген матрица дейді де, А1 арқылы белгілейді. Осы матрица жөніндегі түсініктен кейін 1-ші кестені пайдаланып, бір базистен екінші базисқа көшу жолын қарастыралық. Ол үшін, тең алдымен, шешімнің оптималды шартына түсініктеме берейік, яғни, былайша айтқанда оптималды төбеге жеткенімізді қалай білеміз.

Сызықтық бағдарламалау  есебінің оптималдық шарты жөнінде  мынадай теорема белгілі: егер мына жағдайда Z → max табылған шешімде ( мысалы, Yi=bi>0, Cj=0) мақсат функциясының коэффициенттері Cj, яғни m+1 жатық жолдың ( бос мүшелер бағанасындағы элементті қоспағанда) барлық элементтері оң болса ( мына жағдайда Z → min, керісінше, барлық элементтер теріс болуға тиіс), онда осы шешім оптималды делінеді. (Ескерту: Бұл теореманың математикалық дәлелденуі тәжірибелік есептер шығару барысында өзінен-өзі түсінікті болады).

Жоғарыдағы теоремада  берілген оптималды шешімнің шарты  бойынша, 1-ші кестедегі шешім Yi=bi>0, Хj=0, j=1,..., n) оптималды шешімді бермейді, себебі мақсат функциясының коэффициенттерінің барлығы, теріс таңбалы сандар (- Сj<0).

Симплекс әдісінің негізгі мақсаты – бастапқы шешімді ( жоспарды) бірте – бірте жақсарта отырып, ең пайдалы ( оптималды) жоспарға жету.

Xk мен Yr-дің орнын ауыстыру жұмысы берілген ( 4.6) теңдеулердің ішінен r-ші теңдеуді тауып, оны Xk-ның мәнін қалған теңдеулерге енгізу, яғни (4.6) жүйенің r-ші теңдеуі былай жазылады:

Yr=br-ar1Xr-ar2X2-ar3X3-…-arnXn

 

 

 

 

 

 

Тәжірибелік есептерді  Симплекс әдісімен шығару.

 

Біз алдыңғы тақырыпта  Симплекс әдісінің жалпы алгоритмін қарастырдық, енді осы алгоритмдерді  пайдаланып, бірнеше тәжірибелік есептерді шешіп, оған талдау берелік.

Жоғарыдағы тақырыпта сан мәнінде қарастырылған мысалға Симплекс алгоритмін қолданайық. Төмендегі шектеуші шарттарды қанағаттандыратын:

0,4X1+2X2 ‹ 400

                       0,9X1+1,2X2‹360,               (4.7)

10X1+4X2‹3200,

                       X1›0, XZ2›0               (4.8)

Мына мақсат функциясының ең үлкен мәнін табу  керек:

Z (X1X2)=1,2X1+4,8X2→ min       (4.9)

Симплекс әдісінің алгоритмі  бойынша (4.7) теңсіздіктердің сол жағына қосымша оң белгісіздер қосу арқылы теңдікке айналдырамыз:

0,4X1+2X2+y1 ‹ 400

                       0,9X1+1,2X2+y2‹360,               (4.10)

10X1+4X2+y3‹3200,

                             X1 › 0, X2 › 0, y1› 0,  y2 › 0,  y3› 0.                   (4.11)

Экономикалық мағынада  y1,  y2 және y3-қолданылған станоктардың уақыты. Олай болса y1,  y2 және y3 өндіріс орнына ешбір пайда келтірмейді, былайша айтқанда, пайдасы нөлге тең, демек:

Z (X1X2)= 1,2X1+4,8X2+0 y1+ 0y2 + 0 y3=

                                  =1,2X1+4,8X2→ min                                (4.11)

Сонымен біз (4.7)- (4.9)есептің орнына (4.10)- (4.11)есебін шешетін болдық. Егер (4.10) теңдеуін y1,  y2 және y3 арқылы шешетін болсақ:

y1=400+0,4(-X1)+2(-X2)

               y2=360+0,9(-X1)+1,2(-X2)         (4.13)

y3=3200+10(-X1)+4(-X3)

шығады.

Мұндағы X1=0, X2=0 десек, онда y1=400, y2=360, y3=3200 болады, бұл сандар (4.10)- (4.12) теңдіктерін толық қанағаттандырадығ ендеше бұларды алғашқы шешім ретінде қабылдауға болады. Бұл жағдайда Z(X1X2)=0 болады. Есептің мақсаты, бастапқы жоспарды бірте-бірте жақсарта отырып, ең пайдалы жоспарға жету. Симплекс әдісі бойынша есептердің шешімін шешімін Симплекс кестелер арқылы ізденген өте тисмді. Жоғарыда сызықтық бағдарлдамалау есептернің оптималды шешімі бір кестеден екінші кестеге, одан үшінші т.б.с.с. кестелерге көшу арқылы табылатыны баяндалады. Сондықтан (4.12) (4.13) жүйелердің коэффициенттері арқылы кесте құрамыз:

 

№1	X1	X2	bi
y1	0,4	2	400
y1	0,9	1,2	360
y1	10	4	3200
Z	-1,2	-4,8	0

 

Бұл кестедегі жоспар оптималды  жоспарды бермейді. Өйткені есеп мақсат функциясының үлкен мәнін табуға беріліп отыр, ал кестедегі соңғы жолдың элементтері (-1,2;-4,8) теріс таңбалы.  Бұл жоспарды жақсартуға болады,  ол үшін бір базистік белгісізбен базистік емес белгісіздердің орындарын ауыстырамыз, яғни бір базистік белгісіздерге көшеміз. Базистік емес белгісіздердің қайсысы базиске ену керек екендігін білу үшін, соңғы жатық тжолдың теріс элементтерінің ішінен ең кіші элементін іздейміз.

Max (|-1,2|,|-4,8|)=4,8

Бұл сан 2-ші бағанға сәйкес, ендеше бағыттаушы бағана ретінде к=2 аламыз, демек Х2 базиске енеді.

Базистың  құрамынан  шығатын базистік белгісізді анықтайық.

                Ол ушін     min 400  260   3200        200

                                            2       1,2      4

 

Бүл қатынастардың ең кішісі 1-ші  жатық жолда жатыр,  демек багыттаушы жатық жол r = 1 болады да, Х₁ мен у₁ орындарымен ауыстыратыны анықталады. Олардың орындарын ауыстырғанда, жаңа базиске сәйкес матрицаның барлық элкменттері өзгереді. Оларды төмендегі агоритм арқылы өзгертемізде, келесі кестеге сәйкес орындарга жазамыз.

Бағытаушы бағанымен (х₁) бағытаушы жолдын қиылысында  тұрған элкмент бас элемент деп аталатыны белгілі, олай болса бұл элемент а_rk  немесе а_12=2. Осы әрекеттерден кейін жаңа кесте құқрамыз. Төменде жаңа кестенің элементтерін анықтау алгоритмі келтірілген.

1. Бас  элементтің орнында тұратын жаңа элемент:

  (r=1, r=2), a =                        a  =       =     =0.5.

2. Бағыттаушы жатық жолға сәйкес жолдағы элементтер:

a =     a  =     =     =0.2;  b  =     =      = 200.

3. Бағыттаушы бағанға сәйкес бағандағы элементтер:

a =-    ; a  =     =-     =-0.6;

a  =      =-      =-2; C  =-   =-    =2,4

 

4. Жаңа кестенің қалған элементтері мына формула арқылы анықталады:

Осы табылған элементтер арқылы жаңа кесте құрылды.

 

aij  =a ij -   ; (i=1,m+1; i=r, j=1,n+1, j=k);

a21  =a21-        =0.9-       =0.66;

b2=b2-        =360-        =120;

a31  =a31-    =10-     =9.2;

b3  =b3-      =3200-     =2400;

C1=C1-      =-1.2-       =-1.2+0.96=-0.24;

Z =Z-     =0-        =960.

 

 

Осы табылған элементтер арқылы жаңа кесте құрылады.

№2	X1	Y1	Бос мүшелер
X2	0.2	0.5	200
Y2	0.6	-0.5	120
Y3	9.2	-2.0	2400
Z1	-0.24	2.4	960

 

Сонымен жаңа базистік белгісіздер: X2=200, y2=120, y3=2400 бұл жағдайда мақсат функциясының мәні Z =960 мың теңге болады. Алдыңғы базистік шешімнен неге жеткенімізді баяндайық. Екінші заттан 200 дана жасау керек, бұл жағдайда өндіріс орны 960 мың теңге пайда табады, ал екінші топтағы станоктардың 120 сағат, үшінші топ станоктарының 2400 сағат уақыты пайдаланылмай қалады. Табылған жоспар оптималдық шешімді бермейді, себебі соңғы индекс жолындағы элементтер ішінде әлі де болса теріс таңбалысы бар. Табылған кестеге жоғарыдағы әдісті қолдансақ, жаңа 4.4-кестесін аламыз:

 

№3	X1	Y1	Бос мүшелер
X2	-0,33	0.7	160
X1	1,8	-1.0	200
Y3	-15,0	7,2	560
Z1	0,40	2.16	1008

 

Жаңа базис X2=160, X1=200, y3=560. Бұл жағдайда мақсат функциясының мәні  Z=1008 мың теңге, жоспар оптималды, өйткені соңғы жатық жолдың барлық элементтері оң сандар. Сонымен оптималды шешім бойынша барлық элементтері оң сандар. Сонымен оптималды шешім бойынша 1-ші заттан X1=200 дана, 2-ші X2=160 дана жасау керек. Бірақ 3-ші топтағы станоктардың 560 сағат уақытты пайдаланылмай қалады. Егер өндіріс орны шынында да 1008 мың теңге пайда табу үшін 3-ші топтағы станоктардың біразын сатып немесе басқа жұмысқа пайдаланғандары жөн. Ал өндіріс көлемін кеңейткісі келсе, онда 1-ші және 2-ші топтардағы станоктарға қосымша станоктар сатып алу керек. Сонымен өндіріс орнының бар қорларды пайдалана отырып, қандай заттан қанша өнім өндіргенде көп пайда таба алатынын білдік.

2-ші бөлімде қарастырылған  тағы бір есепті осы әдіспен  шығарайық. Мына төмендегі шектеулердегі  қанағаттандыратын:

X1+X2 ‹ 9000

                       4X1+40X2‹110.000,               (4.7)

1.5X1+10X2‹30.000,

                                                        X1›0, X2›0,  

  Z= 140X1+640X2  мақсат функциясының ең үлкен мәнін іздейік.

Шешуі: Бұл есепті бірден симплекс кестесіне түсірейік.

 4,5-кесте

№1	X1	X2	Bi
y1	1	1	9000
y1	4	40	110000
y1	1,5	10	3000
Z	-140	-640	0

 

Екінші базиске өтейік.

4,6 –кесте

№2	X1	Y1	Bi
X2	0.9	-0.025	6250
Y2	0.1	0.025	2750
Y3	0,5	-0.25	2500
Z1	-76	16	1760,000

 

Бұл кестеде әлі оптималды  шешімі бермейді, өйткені соңғы жатық  жолдың элементтерінің ішінде теріс  сан бар.