Жасанды базис әдісі

Жоспар
Кіріспе

1 Кіріспе
2 Жасанды базис әдісі

Қазіргі уақытта математика және қазіргі заманғы есептеу техникасының ең соңғы жетістіктері экономикалық зерттеулер мен жоспарлауда кеңінен қолдану үстінде. Бұған математиканың келесі бөлімдерінің дамуы: математикалық бағдарламалау, ойындар теориясы, жаппай қызмет көрсету теориясы, және тез жұмыс істейтін электрондық-есептеуіш техникасының қарқынды дамуы әсер етуде, математикалық әдістер арқылы экономикалық есептерді шешу және қою тәжірибесі қазірдің өзінде жеткілікті жинақталған. Әсіресе математикалық программалаудың мәнің құрайтын оңтайлы жоспарлау әдістері табысты дамуда.
Негізгі есептердің бірі болып оңтайлы жоспарлау жүйесін құру және халық шаруашылығын математикалық әдістер мен электронды-есептеу техникасын экономикада кең қолдану базасында басқару.
Экстремалды экономикалық есептерді шешуді үш кезеңге бөлуге болады: 1) экономикалық-математикалық моделін құру; 2) математикалық әдістердің бірімен оңтайлы шешім табу; 3) халық шаруашылығына іс жүзінде енгізу. Мұндай модельдерде есептің маңызды ерекшеліктері, нәтижеге және әсер етуі мүмкін шектейтін жағдайлар ескерілуі тиіс.
Математикалық бағдарламалау құрамдас бөліктері сызықтық, сызықтық емес және динамикалық бағдарламалау болып табылады. Алғаш рет сызықты бағдарламалау есептің қойылымы, жалпы километражды азайту мүмкіндігін беретін, оңтайлы тасымалдау жоспар ретінде, совет экономисі А. Н. Толстой (1930 ж.) жұмысында қолданылды. 1931 ж. венгр математик Б. Эгервари математикалық қойылымды қарады және сызықтық бағдарламалау есебін шешті, оның атауы "таңдау проблемасы" болды, ал шешу әдісі венгр әдісі атауын алды. Сызықты программалау есептерін жүйелі түрде зерттеу және оларды шешудің жалпы әдістерін әзірлеу кеңес ғылымы Л. В Канторовича (1939 ж.) еңбектерінде басталды, ол осы есептерді шешідің жалпы тәсілін ұсынды (рұқсат етілген көбейіткіштер). Ол сонымен қоса М. К. Гавуринмен бірге Гавуриным 1949 жылы потенциалдар әдісін әзірледі, ол көлік есептерін шешу кезінде қолданылады.
Сызықтық бағдарламалау әдістеріне шетелдік, ең алдымен американдық ғалымдардің көптеген жұмыстары арналды. 1941 ж. Хичкок көліктік есепті қойды. Негізгі сызықтық программалау есептерін шешу әдісі – симплексті әдіс - 1949 жылы Данцингпен жарияланған. Қазіргі уақытта сызықтық бағдарламалаудың әдістері, ол қолданылуы мүмкін, нақты экономикалық есептерді шешуді анықтау бағытында, және электронды-есептеуіш машиналарында есептерді шешу үшін ыңғайлы алгоритмдерқұру жолында дамып келе жатыр.
Сызықтық бағдарламалаудың дамуымен бірге, үлкен назар сызықтық емес бағдарламалау есептеріне аударылды, онда не мақсатты функция, не шектеу, не басқа біреуі сызықтық емес.

Пән: Математика, Геометрия
Жұмыс түрі: Материал
Тегін: Антиплагиат
Көлемі: 8 бет
Таңдаулыға:

Кіріспе

Қазіргі уақытта математика және қазіргі заманғы есептеу техникасының ең соңғы жетістіктері экономикалық зерттеулер мен жоспарлауда кеңінен қолдану үстінде. Бұған математиканың келесі бөлімдерінің дамуы: математикалық бағдарламалау, ойындар теориясы, жаппай қызмет көрсету теориясы, және тез жұмыс істейтін электрондық-есептеуіш техникасының қарқынды дамуы әсер етуде, математикалық әдістер арқылы экономикалық есептерді шешу және қою тәжірибесі қазірдің өзінде жеткілікті жинақталған. Әсіресе математикалық программалаудың мәнің құрайтын оңтайлы жоспарлау әдістері табысты дамуда.
Негізгі есептердің бірі болып оңтайлы жоспарлау жүйесін құру және халық шаруашылығын математикалық әдістер мен электронды-есептеу техникасын экономикада кең қолдану базасында басқару.
Экстремалды экономикалық есептерді шешуді үш кезеңге бөлуге болады: 1) экономикалық-математикалық моделін құру; 2) математикалық әдістердің бірімен оңтайлы шешім табу; 3) халық шаруашылығына іс жүзінде енгізу. Мұндай модельдерде есептің маңызды ерекшеліктері, нәтижеге және әсер етуі мүмкін шектейтін жағдайлар ескерілуі тиіс.
Математикалық бағдарламалау құрамдас бөліктері сызықтық, сызықтық емес және динамикалық бағдарламалау болып табылады. Алғаш рет сызықты бағдарламалау есептің қойылымы, жалпы километражды азайту мүмкіндігін беретін, оңтайлы тасымалдау жоспар ретінде, совет экономисі А. Н. Толстой (1930 ж.) жұмысында қолданылды. 1931 ж. венгр математик Б. Эгервари математикалық қойылымды қарады және сызықтық бағдарламалау есебін шешті, оның атауы "таңдау проблемасы" болды, ал шешу әдісі венгр әдісі атауын алды. Сызықты программалау есептерін жүйелі түрде зерттеу және оларды шешудің жалпы әдістерін әзірлеу кеңес ғылымы Л. В Канторовича (1939 ж.) еңбектерінде басталды, ол осы есептерді шешідің жалпы тәсілін ұсынды (рұқсат етілген көбейіткіштер). Ол сонымен қоса М. К. Гавуринмен бірге Гавуриным 1949 жылы потенциалдар әдісін әзірледі, ол көлік есептерін шешу кезінде қолданылады.
Сызықтық бағдарламалау әдістеріне шетелдік, ең алдымен американдық ғалымдардің көптеген жұмыстары арналды. 1941 ж. Хичкок көліктік есепті қойды. Негізгі сызықтық программалау есептерін шешу әдісі - симплексті әдіс - 1949 жылы Данцингпен жарияланған. Қазіргі уақытта сызықтық бағдарламалаудың әдістері, ол қолданылуы мүмкін, нақты экономикалық есептерді шешуді анықтау бағытында, және электронды-есептеуіш машиналарында есептерді шешу үшін ыңғайлы алгоритмдерқұру жолында дамып келе жатыр.
Сызықтық бағдарламалаудың дамуымен бірге, үлкен назар сызықтық емес бағдарламалау есептеріне аударылды, онда не мақсатты функция, не шектеу, не басқа біреуі сызықтық емес.
Экономикалық үдерістерді зерттеу кезінде көптеген жағдайларда сызықтық емес орын алады, олардың сызықтық есептермен аппроксимациясы, тек қана соңғысы жақсы зерттелген және олар үшін алгоритмдер әзірленгенімен түсіндіріледі. Тіпті ең оңай көліктік есептің өзі егер, бірлік жүкті тасымалдау құны оның жалпы санына байланысты болған жағдайда сызықтық емес түрде болады.
Бірқатар сызықтық және сызықтық емес бағдарламалау есептерінде экономикалық процесс уақытқа - бірнеше кезеңдерге тәуелді. Мұндай есептерді шешу кезінде (олар көпкезеңді деп аталады) процестің дамуын кезең-кезеңмен ескеру қажет. Мұндай көп кезеңді есептер динамикалық бағдарламалау есептеріне жатады.
Осылайша, динамикалық бағдарламалау көпкезеңді есептердің оңтайлы шешіммін табу математикалық теориясы ретінде айқындалады.
Сызықтық, сызықтық емес және динамикалық бағдарламалау әр түрлі басқарылатын процестердің оңтайлы шешімдерін табудың сандық әдістеріне жатады.

Жасанды базис әдісі
Жоғары көрсетілгендей, сызықтық программалау есебінің шектеулер m тәртібінің жалғыз матрицасына ие болса, осылайша есептеулердің кері емес оң бөлеіктерде бастапқа жоспар анықталған, осындан шыға келе симплексті әдістің көмегімен оңтайлы жоспар табылады.
Егер, сызықтық программалау есебінің шектеулерің АХ = A0 кезінде A0 = 0түріне түрлендіруге болса, онда шектеулер жүйесі әрқашан жалғыз матрицаға ие. Көптеген шешімі бар сызықтық бағдарламалау есептері, жалғыз матрицаға ие емес және аталған түрге жүргізілмейді. Бұл жағдайда жасанды базис әдісі қолданылады. Сызықтық бағдарламаудың жалпы есебін қарастырайық.
Сызықтық функцияның минималды мәнің келесі шектеулерде табу Z = C1x1+ C2x2+ ... Cnxn
a11x1 + a12x2+ ...+a1nxn=b1
a21x1 + a22x2+ ...+a2nxn=b2
... ... ... ... ... ... ... ... ... ...
am1x1 + am2x2+ ...+amnxn=bm
xj=0, (i = 1, 2, ..., n)

онда b1 = 0 және шектеу жүйесінде бірлік матрица жоқ. Бірлік матрицаны а лу үшін әрбір теңдікке бір айнымалыxn+1= 0 (i = 1, 2, ..., m) қосайық оларды жасанды деп атайық, және кеңейтілген есепті қарастырайық
Егер есеп сызықтық функцияның ең төменгі маңызың анықтауға шешілсе, M шамасы жеткілікті үлкен оң сан болып көзделеді, және жеткілікті кіші теріс санмен, егер сызықтық функцияның максималды мәні болса. Бірлі-жарым векторлар Аn+1, Аn+2, ... Аn+m, жасанды айнымалыға тиісті болып, жасанды базисті құрайды.
Бастапқы міндеттің оңтайлы жоспарын табу үшін келесі теореманы пайдаланады.
Теорема 1.14. Егер оңтайлы жоспарда X = x1, x2 ... , xn, 0, ... , 0) кеңейтілген есептер жасанды айнымалыларxn+1= 0(i = 1, 2, ..., m), онда жоспар X = (x1, x2 ... , xn) бастапқы міндеттің оңтайлы жоспары болып табылады.
Дәлел. Ескереміз, егер жоспар X кеңейтілген есептің оңтайлы жоспар болса, онда жоспар X -- бастапқы есептің жоспары, бұнда Z (X) = Z (X). Функция мәндерінің теңдігі, жоспар X X жоспардан соңғы нөлге тең компоненттермен ерекшеленеді.
Жоспар X бастапқы есептің оңтайлы жоспары екенің дәлелдейміз. Мысалы, Х оңтайлы жоспар емес болып табылады. Онда келесі оңтайлы жоспар X* = (x1*, x2* ... .., xn*) бар, ол үшін Z (X*) Z (X). Осындан вектор үшін X* = (x1*, x2* ... .., xn*,0 ... ,0), кеңейтілген есептің жоспары болып табылатын:

Z (X*) = Z (X*) Z (X) = Z (X)
немесе

Z (X*)Z (X)
Осылайша, кеңейтілген есептің X жоспары оңтайлы емес болып табылады, бұл теорема талаптарына қарама-қайшы.
Кеңейтілген есепке симплексті әдісті пайдалану жоспарды құруды қамтамасыз етеді, онда әрбір жасанды айнымалыларxn+1 =0. Егер бастапқы есеп жоспары болмаса, онда кеңейтілген есептің оңтайлы шешімі кем дегенде бір xn+1 0 бар.
Егер М шамасы алдын-ала көрсетілмесе, кеңейтілген есептің оңтайлы жоспарын табу үшін, симплексті кесте құрумен симплексті әдісі қолданылады, және ол бір жолға ие.
Итерациды процессті (m +2) ші жолында барлық жасанды векторлар базистан алып тастау үшін жүргізеді, содан кейін оңтайлы жоспар табу процесін (m +1) -ші жол бойынша жалғастырады.

Мысал. Сызықтық функцияның максималды мәнің келесі шектеулерде табу Z = 5x1 + 3x2 + 4x3 - x4
x1+ 3x2+ 2x3+ 2x4=3 xj=0,
2x1+ 2x2+ x3+ x4= 8 (i = 1, 2, 3, 4).

Шешімі. Шектеулер жүйесі бірлік матрицаға ие емес. Әрбір теңдеуге бір кері емес жасанды айнымалыны (тиісіншеx5=0,, x6=0,) қосайық және кеңейтілген міндетке көшейік.
Сызықтық функцияның максималды мәнің келесі шектеулерде табуZ = 5x1+ 3x2+ 4x3 - x4 - Mx5- Mx6
x1+ 3x2+ 2x3+ 2x4+ x5=3 xj=0,
2x1+ 2x2+ x3+ x4+ x6 = 3 (i = 1, 2, ..., 6).

Немесе векторлы формада:
A1x1+ A2x2+ A3x3 + A4x4 + A5x5 + A6x6 = A6
Базиске бірен-саран векторларды A5, A6 таңдаймыз, олар жасанды базисті құрайды. Бос белгісіздерді нөлге теңестіре x1 = x2 = x3 = x4=0, кеңейтілген есептің бастапқы тірек жоспарын аламыз X0= (0; 0; 0; 0; 3; 3) оған жіктеу сәйкес келеді.

x5A5 +x6 A6 = A0
Симплексті кесте (кесте. ... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.