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


Алғашқы жоспар құру. СБ есебі қойылған болсын.
Төмендегі функцияның барынша аз мәнін табу қажет.
F=C_1 X_1+C_2 X_2+...+C_n X_n
Шектеу жүйесінің m бірлік векторлары болсын деп ұйғарсақ, онда ол алғашқы m векторлар болады. Осыдан (1.1)-(1.3) есепті алғашқы m векторларға сәйкес түрлендіріп жазамыз:

Пән: Математика, Геометрия
Жұмыс түрі: Реферат
Көлемі: 5 бет
Бұл жұмыстың бағасы: 300 теңге




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

Алғашқы жоспар құру. СБ есебі қойылған болсын.
Төмендегі функцияның барынша аз мәнін табу қажет.
F=C1X1+C2X2+...+CnXn (1.1)
мына шектеулерде
a11 x1+a12x2+...+a1nxn=B1a21 x1+a22x2+...+a2nxn=B2 ... ... ... .. ... ... ... ... ... ... ... ..am1 x1+am2x2+...+amnxn3=Bm (1.2)

мұнда,
xj=0, i=1,2,..., m. (1.3)
Шектеу жүйесінің m бірлік векторлары болсын деп ұйғарсақ, онда ол алғашқы m векторлар болады. Осыдан (1.1)-(1.3) есепті алғашқы m векторларға сәйкес түрлендіріп жазамыз:
F=C1X1+C2X2+...+CnXn, (1.4)
мына шектеулерде
x1+a1, m+11xm+1+a1, m+21xm+2+...+a1n1xn=B11x2+a2, m+11xm+1+a2, m+21xm+2+...+a2n1xn=B21 ... ... ... ... ... ... ... ... ... ... ... xm+ am, m+11xm+1+am, m+21xm+2+...+amn1xn=Bm1 (1.5)

xj=0, j=1,2,..., n. (1.6)
Жүйені (1.5) векторлық формада жазамыз:
x1A1+x2A2+...+xmAm+xm+1Am+1+...xnAn =B (1.7)
A1=10...0, A2=01...0,... , Am=00...1, Am+1=a1.m+11a2.m+11...am.m+11,... ,

An=a1.n1a2.n1...am.n1, B=B11b21...bm1

A1,A2,...,Am векторлар - m өлшемді кеңістіктің сызықтық тәуелсіз бірлік векторлары. Сондықтан (1.7) өрнекте базистік айнымалылар ретінде x1,x2,...,xm. Ал еркін айнымалылар ретінде xm+1,xm+2,...,xn таңдаймыз, оларды нөлге теңестіріп, базистік айнымалыларды анықтаймыз. Мұнда Bi=0 (і= 1,2,...,m), ал A1,A2,...,Am бірлік векторлар екенін ескерсек, онда алғашқы жоспарды аламыз:
X0=(x1=b1; x2=b2; ...xm=bm; xm+1=0;...xn=0 (1.8)
Жоғарыдағы (1.7)-ден (1.8) жоспарды ескерсек, төмендегі жіктеу шығады:
x1A1+x2A2+...+xmAm=B, (1.9)
мұнда A1,A2,...,Am векторлар сызықтық тәуелсіз, демек, құрылған жоспар базис болып табылады.
1 - анықтама. Еркін белгісіздердің нөл мағыналарына сәйкес келетін шектеулер жүйесінің (1.2) шешімі базистік деп аталады.
Бастапқы негізге алынатын жоспарға (1.9) сүйене отырып, екінші негізге алынатын жоспарды қалай құруға болатынын қарастырамыз. Базиске кірмейтін кейбір вектор үшін, мысалы Am+1, жіктеудегі Xi,m+1 коэффициенттердің ең болмағанда біреуі оң болады деп ұйғарамыз.
x1,m+1A1+x2,m+1A2+...xm, m+1Am=Am+1
Жүйенің оң жағы В бөлікті осы айнымалының оң коэффициенттеріне, яғни Віаim+1 бөлеміз. Сөйтіп, xm+1 векторы жоспар немесе жаңа базис болып табылады. Есептің m-нен асатын базисі болмайды, сондықтан қазіргі бар базистің біреуін алып тастаймыз. Ол үшін Q=min(Віаim+1) таңдаймыз. Осы ең кіші мәні бірінші жолда тұрсын, яғни Q1=min(Віаim+1). Сонда жаңа базистік шешім аламыз X=(x2,x3,...,xm,xm+1). Бұл базистен x1 алып тастау, ал базиске xm+1 енгізу қажет екенін білдіреді. Демек, негізге алынатын жаңа оның орнына базиске енгізілетін айнымалының векторын таңдау қажет.
Оңтайлылық талаптары. СБ есебінің базистік шешімі бар деп ұйғарамыз. Бұл жағдайда есептің математикалық формасы төмендегідей болады:
x1A1+x2A2+...+xmAm=B, (1.10)
x1C1+x2C2+...+xmCm=F, (1.11)
Мұнда барлық xj=0, j= 1,2,...,n, ал F - осы жоспарға сәйкес келетін функцияның мәні. Егер сызықтық функциядағы Cj коэффициенті Aj векторға сәйкес келсе, онда Fj-Cj оңтайлылық өлшемі немесе сызықтық функцияның бағасы деп аталады.
Оңтайлылық өлшемі бағдарламадан шығарылатын қызметтің құнының сомасына тең болады, лдан жоспарға енгізілетін өнімнің бірлігінен түсетін кіріс алынып тасталады. Fj - мақсат функцияссының коэффициенттерін шектеулердегі айнымалылардың коэффициенттеріне көбейтіндісінің қосындысына, яғни,
Fj= iϵ1cj aij
cj - мақсат функциясының белгісіздер коэффициенттері.
Төмендегі теоремалар орын алады.
1 - теорема. Егер кейбір Aj векторы үшін төмендегі талап орындалса,
Fj-Cj=0,
онда Х0 жоспары функцияның максимумы үшін оңтайлы юолып табылады.
2 - теорема. Егер кейбір Aj векторы үшін төмендегі талап орындалса,
Fj-Cj=0
онда Х0 жоспары функцияның минимумы үшін оңтайлы болып табылады.
Демек, сызықтық функцияның максимумына сәйкес есептің жоспары оңтайлы болу үшін оның бағалары оң болуы қажетті әрі жеткілікті болады. Ал функцияның минимумы үшін оның бағалары теріс болуы қажетті әрі жеткілікті ... жалғасы
Ұқсас жұмыстар
Сызықтық бағдарламалау есебінің графикалық әдісі
Дезинсекция әдісі
Бақылау әдісі
Оқыту әдісі
Рынок әдісі
Жобалау әдісі
Қалыптау әдісі
Статистикалық сынақтар әдісі Монте-Карло әдісі
Клондау әдісі
Координаталар әдісі
Пәндер

Қазақ тілінде жазылған рефераттар, курстық жұмыстар, дипломдық жұмыстар бойынша біздің қор №1 болып табылады.

Байланыс

Qazaqstan
Phone: 777 614 50 20
WhatsApp: 777 614 50 20
Email: info@stud.kz
Көмек / Помощь
Арайлым
Біз міндетті түрде жауап береміз!
Мы обязательно ответим!
Жіберу / Отправить

Рахмет!
Хабарлама жіберілді. / Сообщение отправлено.

Email: info@stud.kz

Phone: 777 614 50 20
Жабу / Закрыть

Көмек / Помощь