Сызықтық бағдарламалаудың жалпы есебі және математикалық бағдарламалау есептерініңмодельдерін құру

Жасанды базисті симплекс әдісі (М-әдіс)

жүктеу/скачать 147,42 Kb.

бет	4/7
Дата	25.12.2023
өлшемі	147,42 Kb.
	#143277

1 2 3 4 5 6 7

Байланысты:
1 Сызықтық бағдарламалау

1.5 Сызықтық бағдарламалау есептерін Excel ортасында Поиск решения қондырмасының көмегімен шешу

1.4 Жасанды базисті симплекс әдісі (М-әдіс)

Сызықтық бағдарламалаудың бастапқы канондық есебінде (СБКЕ) бастапқы тірек жоспары жоқ болғанда жасанды базисті симплекс әдісі қолданылады.Мұндай жағдай бастапқы шектеуде «тең» немесе «үлкен немесе тең» деген таңбалары болғанда орын алады.

М-әдіс М-есебіне симплекс-әдісін қолдаудан тұрады. Ол бастпақы есепке бастапқы СБКЕ теңдеулер жүйесінің сол жағына жаңадан алынатын матрица сызықтық тәуелді емес бірлік векторларының жүйесінен тұратындай тиісті теріс емес жасанды айнымалылары бар жасанды бірлік векторларын қосудан құралады. Бастапқы есептің мақсатты функциясына оның максималдануы кезінде жасанды айнымалылардың қосындысына (-М) саны көбейтілген түріндегі қосылғыш қосылады, мұндағы М – жеткілікті үлкен оң сан, яғни базистен осы айнымалыларды алу үшін оларды мақсатты функцияға (-М) үлкен теріс коэффициенттерімен енгізеді.
Осылайша алынған есепте бастапқы тірек жоспары белгілі.
М-есебін шешу барысында симплекс-кестесінде жасанды векторларды олардың базистен шығуына байланысты сызып отыру керек. Егер жасанды векторлардың барлығы базистен шықса, онда бастапқы есептің теңдеулер жүйесіне ұқсас теңдеулер жүйесін аламыз. Егер М-есептің оңтайлы шешімінде жасанды айнымалылар болса және М-есебі шешілмейтін болса, онда бастапқы есеп те шешілмейді.
Мысалы. Симплекс әдісімен сызықтық бағдарламалау есебін шешу:
f(Х)=3х₁+3 х₂→ max
шектеулері:
Канондық формасы:
f(Х)=3х₁+3 х₂+0х₃+0х₄+0х₅ → max
шектеулері:
Шектеулер жүйесінде ішкі бірлік матрицасы жоқ.
СБКЕ бастапқы тірек жоспары жоқ. Тірек жоспарын табу үшін М-есебіне көшеміз:
f (Х)=3х₁+3 х₂+0х₃+0х₄+0х₅-Му → max
шектеулері:
Бастапқы (нольдік) 1.7 Х⁽⁰⁾=(0;0;8;0;2;1) симплекс кестесін құрайық. Бастапқы кестедегі (-2М-3)-ге тең ең кіші Δ_j мәні базиске енгізілетін векторына сәйкес келеді, ал жасанды Р векторы базистен шығарылады, өйткені оған ең кіші R _min=0,5 сәйкес келеді. Р сәйкес келетін бағана келесі симплекстік кестелерден сызылады.
Бірінші симплекс кестесінде жаңа Х⁽¹⁾= (0,5;0;7,5;0;1,5) тірек жоспары алынды, ол бастапқы есептің тірек жоспары болса да, оңтайлы болып табылмайды, өйткені симплекстік кестенің 4-ші жолында (кесте 1.7) екі теріс симплекс-айырмасы (-4,5 және -1,5) бар. Ең кіші симплекс-айырма векторына сәйкес келеді. Бұл алынған жоспар оңтайлы емсе екендігін білдіреді және оны базиске векторын енгізу арқылы жақсартуға болады.
Екінші симплекс кестесінде бастапқы есептің Х⁽²⁾= (3; 5; 0; 0; 9) оңтайлы жоспары алынды, себебі Δ_j ≥0. Мақсатты функцияның максимал мәні f(X) = 24. Алайда симплекстік кестенің соңғы жолының анализі базиске енбеген векторына нольдік симплекс-айырмасы сәйкес келетінін көрсетеді. векторын базиске енгізуге болады, бірақ мақсатты функцияның мәні ол кезде өзгермейді.
Кесте 1.7

№ симпкесте	Базис	С_Б		В	с₁=3		с₂=3		с₃=0		с₄=0		с₅=0		-М
					А₁		А₂		А₃		А₄		А₅		Р
0	А₃	0		8	1		1		1		0		0		0
	Р	-М		1	(2)		-1		0		-1		0		1
	А₅	0		2	1		-2		0		0		1		0
Δ_j				-М		-2М-3		М-3		0		М		0		0
1	А₃		0	7,5	0		(1,5)		1		0,5		0
	А₁		3	0,5	1		-0,5		0		-0,5		0
	А₅		0	1,5	0		-1,5		0		0,5		1
Δ_j				1,5		0		-4,5		0		-1,5		0
2	А₂		3	5	0		1		0,67		0,33		0
	А₁		3	3	1		0		0,33		-0,33		0
	А₅		0	9	0		0		1		(1)		1

Енді бір итерацияны орындайық: базиске орнына енгізейік. Есептеулер нәтижесі 1.8 кестесінде көрсетілген.

Кесте 1.8

№ симп кесте	Базис	С_Б	В	с₁=3	с₂=3	с₃=0	с₄=0	с₅=0
№ симп кесте	Базис	С_Б	В	А₁	А₂	А₃	А₄	А₅
3	А₂	3	2	0	1	0,33	0	-0,33
	А₁	3	6	1	0	0,67	0	0,33
	А₅	0	9	0	0	1	1	1
Δ_j			24	0	0	3	0	0

Үшінші симплекстік кестеде бастапқы есептің тағы бір Х(3) =(6;2;0;9;0) оңтайлы жоспары алынған және мақсатты функцияның максимал мәні f(X) = 24.

Жауабы. Екі оңтайлы жоспар алынған: Х(2)= (3; 5; 0; 0; 9)жәнеХ(3) =(6;2;0;9;0); f(X) = 24.

1.5 Сызықтық бағдарламалау есептерін Excel ортасында Поиск решения қондырмасының көмегімен шешу

Поиск решения – бұл оңтайлы есептерді шешуге көмектесетін Excel қондырмасы. Поиск решения диалогтық терезесінде негізгі параметрлері: шектеулер ұяшықтарын өзгерте отырп, мақсатты ұяшықты белгілеу.

Есепті шешу үшін:

шешім нәтижесі жазылатын ұяшықтар адресін көрсету (өзгертілетін ұяшықтарды көрсету);
бастапқы мәліметтерді енгізу;
мақсатты функцияның тәуелділіктерін енгізу;
шектеулер үшін тәуелділіктерді енгізу;
«Поиск решения» командасын іске қосу;
Мақсатты функция үшін ұяшықты белгілеу (мақсатты ұяшықты белгілеу);
Шектеулерді енгізу;
СБЕ есептерін шешу үшін параметрлерді енгізу.

Поиск решения командасын қосу.
Мақсатты функция үшін ұяшықты белгілеу. Поиск решения терезесінің элементтерінің мағынасын түсіндірейік.
Мақсатты ұяшықты белгілеу – мәнін максималдандыру, немесе минималдандыру, немесе нақты бір мәнге теңестіруді қажет ететін мақсатты ұяшықты анықтайды. Мұнда мақсатты функция жазылған ұяшықтың адресін енгізу керек. Ұяшықтың адресін $С$3 енгізіңіз.
Есептің шартына байланысты мақсатты функцияның түрін енгізіңіз. Ол үшін мақсатты функция максимал немесе минимал мәнге тең бе, соны анықтау керек.
Изменяя ячейки – өзгертілетін ұяшықтарды анықтайды. Өзгертілетін ұяшық – бұл шешімді табу барысында қажетті нәтижеге жету үшін өзгертілуі мүмкін ұяшық. Өзгертілетін ұяшықтардың санын 200-ге дейін қоюға болады. Ізделінетін айнымалылардың адрестерін $А$2:$В$2 енгізіңіз.
Предположить – «Установить целевую ячейку» терезесіндегі формулаға тура немесе жанама тәуелділігі бар барлық формуласыз ұяшықтарды тауып, «Изменяя ячейки» терезесіндегі сілтемелерге орналастырылады.
Ограничения – берілген есептің ағымдағы шектеулерін тізбектейді.
Добавить – берілген есепке шектеулерді қосуға болатын «Добавление ограничения» диалогтық терезесін шығарады.
Изменить – берілген шектеулерді өзгертуге болатын «Изменение ограничения» диалогтық терезесін шақырады.
Удалить – белгіленген шектеуді жояды.
7. Шектеулерді енгізу.
«Добавить» пернесіне бағдар. Ссылка на ячейку – мәндері шектелетін ұяшықты немесе ұяшықтардың интервалын анықтайды. Ограничение — «Ссылка на ячейку» терезесінің құрамына қойылатын шартты анықтайды. Ссылка на ячейку жолында $С$4 адресін енгізіңіз. Введите знак ограничения:ұяшық (немесе интервал) және тізімнің оң жағындағы терезеде енгізілетін шектеудің арасындағы қатынасты тізімнен таңдап енгізіңіз. Ограничение жолында $D$4 адресін енгізіңіз. Содан кейін «Добавить» және қалған шектеулерді жоғарыда келтірілген алгоритм бойынша енгізу қажет.
8.Сызықтық бағдарламалау есебін шешу үшін параметрлерді енгізу.
Поиск решения диалогтық терезесінде тышқан бағдарын Параметры пернесіне қойыңыз. Осы терезедегі командалардың көмегімен оңтайландыру есептерінің барлық класстарын шешуге қажеттішарттарды енгізуге болады. Сызықтық және сызықтық емес есептердің параметрлерін анықтауға болады. Диалогтық терезедегі параметрлердің әрқайсысы көптеген есептерге келетін бастапқы әдепкі (по умолчанию) мәнге ие.
Максимальное время – есептің шешімін табуға берілетін уақытты шектеуге арналған. Мұнда 32767 аспайтын уақытты (секундпен) енгізуге болады; 100 мәні әдепте қойылып, көптеген қарапайым есептерге келеді.
Предельное число итераций – шешімді табуға кететін уақытты итерациялар санын шектеу жолымен шектейді. Бұл мән 32767 дейінгі бүтін оң сан болу керек.
Относительная погрешность – шешімді табу кезіндегі шешімнің дәлдігін орнатады. Мұнда енгізілетін сан «Ограничение» ұяшығының мәні қажетті теңдікті қанағаттандыратынын немесе белгіленген шекараларда табылатынын анықтау кезінде қолданылады; 0 мен 1 арасындағы бөлшек сан болуы керек (шеттерін санамағанда); әдепкі мәні 0,000001 тең; егер сан бөлшектері кіші болса (мысалы, 0,0001), онда кіші дәлдікті көрсетеді. Неғұрлым жоғары дәлдік (сан кіші болған сайын) анықталса, шешімді табуға соғұрлым көп уақыт қажет етіледі.
Допустимое отклонение – өзгертілетін ұяшықтар бүтін сандар жиынымен берілгенде оңтайлы шешімнен ауытқитын шаманы енгізу үшін қолданылады.Ауытқу неғұрлым үлкен болса (мүмкін болатын ауытқу процентпен), шешу барысы соғұрлым тез болады. Бүтінсанды шектеулер берілмесе, ауытқуларды енгізудің мағынасы жоқ.
Сходимость – сызықтық емес есептерге ғана қолданылады. Мақсатты ұяшықтағы мәннің салыстырмалы өзгеруі соңғы бес итерацияда Сходимость жолындағы көрсетілген саннан кіші болғанда, іздеу тоқтатылады. Параметр 0 мен 1 арасындағы мәндерді қабылдайды.
Жақсы жинақтылықты неғұрлым көп ондық таңбалар сипаттайды, мысалы: 0,0001 салыстырмалы өзгерімі 0,01 қарағанда кіші. Жақсы жинақтылық оңтайлы шешімді табуғу көбірек уақытты қажет етеді.
Линейная модель – шешімді табу барысын тездетеді. Бұл команда барлық байланыстар сызықтық болғанда ғана қолданылады.
Показывать результаты итераций – шешімді табуды үзіп, әр итерациядан кейін нәтижелерді көрсетеді.
Автоматическое масштабирование –автоматты масштабты қосады. Бұл енгізу (Изменяя ячейки) және шығару (Установить целевую ячейку және Ограничения) параметрлері шамалары бойынша қатты өзгешеленгенде пайдалы; мысалы, кірісті максимизациялау процентпен және миллион тенгемен есептелетін қаржы жұмсау.
Оценки –әр бірөлшемді іздеуде негізгі айнымалылардың бастапқы бағаларын алу үшін қолданылатын тәсіл: линейная – жанама вектордың бойындағы сызықтық экстраполяцияны қолданады; квадратичная – квадраттық экстарполяцияны қолданады.
Разности –мақсатты және шектейтін функциялардың дербес туындыларын бағалау кезіндегі туындыны есептеу тәсілі: прямые – әдепкіде осы дифференциалдау тәсілі қойылған; центральные –жұмыс бетінде көбірек есептеуді қажет етеді, бірақ Поиск решения шешімді жақсарта алмайтыны туралы хабарлама алынған жағдайларда, көмектесуі мүмкін.
Метод поиска –әр итерацияда қандай алгоритм қолданылатынын анықтайды. Әдістердің бірін көрсету керек: Ньютон –өздігінен қойылған; сопряженного градиента –Ньютон әдісіне қарағанда азрақ жадыны, бірақ нақты дәлдікке жету үшін әдетте көбірек итерациянықажет етеді. Егер есептеулер көлемі өте көп және жадыны үнемді пайдалану маңызды болса, осы әдісті қолданған дұрыс.
Загрузить модель –Загрузить модель диалогтық терезесін шығарады, онда үлгінін қайсысын қолдануды көрсетуге болады.
Сохранить модель –Сохранить модель диалогтық терезесін шығарады, онда таңдаған үлгіні қай жерде сақтауға болатынын көрсетеді. Сохранить модель пернесін тек біреуден артық Поиск решения үлгісі берілген жұмыс бетімен сақтайтын жағдайда қолдану керек.Поиск решения бірінші үлгісі жұмыс бетімен бірге автоматты түрде сақталады.
Линейная модель (бұл симплекс әдісті қолдануды қамтамасыз етеді) және Неотрицательные значения терезелерінде жалаушаларды қосыңыз.
Тышқан сілтеуішін ОК пернесіне қойыңыз. Экранда Поиск решения диалогтық терезесі шығады.
Тышқан сілтеуішін Выполнить пернесіне қойыңыз. Шешімді іздеу нәтижелері және t мәндері мен мақсатты функцияның максимал мәні жазылған СЗ ұяшығы үшін АЗ:ВЗ толтырылған ұшықтары бар бастапқы кесте.
Результаты поиска решения диалогтық терезесі қажетті шешімге ең жақын ұяшықтардың мәндерін қолданып, соңғы есептеудің нәтижелерін шығарады. Поиск решения шешімді іздеу әрекеттерін тоқтатқан кезде, Результаты поиска диалогтық терезесінің жоғарғы жағында біткені туралы хабарлама беріледі.
Ерекше жағдайлар:
1) «Значения целевой ячейки не сходятся» хабарламасы алынды. Бұл хабарлама мақсатты функция шектелмеген жағдайда беріледі.
2) «Поиск не может найти подходящего решения»хабарламасы алынды. Мұндай хабарлама шектеулер жүйесінің бірлеспеген жағдайында көрсетіледі.

жүктеу/скачать 147,42 Kb.

Достарыңызбен бөлісу:

1 2 3 4 5 6 7