Использование инструментов Excel для решения задач оптимизации

 

МИНИСТЕРСТВО СВЯЗИ И ИНФОРМАТИЗАЦИИ РЕСПУБЛИКИ БЕЛАРУСЬ

Учреждение образования

«ВЫСШИЙ ГОСУДАРСТВЕННЫЙ КОЛЛЕДЖ СВЯЗИ»

ФАКУЛЬТЕТ ЭКОНОМИКИ И ПОЧТЫ

КАФЕДРА ИНФОРМАТИКИ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ

Пояснительная записка к курсовому проекту

«Использование инструментов Excel для решения задач оптимизации»

по дисциплине

«Основы алгоритмизации и программирования»

Выполнила студентка гр. ПС-161

Д.Д.Одинцова

Руководитель преподаватель

Е.В. Новиков

Минск 2013

ВВЕДЕНИЕ

Оптимизация как процесс получения наилучших результатов при определенных начальных условиях находит в настоящее время самое широкое применение в науке, технике, экономике и других областях человеческой деятельности. Оптимизация - целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях.

Постановка задачи оптимизации предполагает существование конкурирующих свойств процесса. Выбор компромиссного варианта для указанных свойств и представляет собой процедуру решения оптимизационной задачи.

В зависимости от своей постановки, задачи оптимизации могут решаться различными методами, и наоборот - любой метод может применяться для решения многих задач. Методы оптимизации могут быть скалярными, векторными, поисковыми, аналитическими, а также вычислительными, теоретико-вероятностными и теоретико-игровыми.

Линейное программирование - один из первых и наиболее подробно изученных разделов математического программирования.

Линейное программирование применимо для построения математических моделей тех процессов, в основу которых может быть положена гипотеза линейного представления реального мира: экономических задач, задач управления и планирования, оптимального размещения оборудования и пр.

Задачами линейного программирования называются задачи, в которых линейны как целевая функция, так и ограничения в виде равенств и неравенств. Кратко задачу линейного программирования можно сформулировать следующим образом: найти вектор значений переменных, доставляющих экстремум линейной целевой функции при наборе ограничений в виде линейных равенств или неравенств.

В настоящее время линейное программирование является одним из наиболее употребительных аппаратов математической теории оптимального принятия решения. Для решения задач линейного программирования разработано сложное программное обеспечение, дающее возможность эффективно и надежно решать практические задачи больших объемов. В частности, и программный пакет Excel снабжен развитыми системами подготовки исходных данных, средствами их анализа и представления полученных результатов.

В данном курсовом проекте необходимо решить оптимизационную задачу линейного программирования по составлению оптимального плана перевозок, а также найти точки экстремума заданной функции.

1. ИССЛЕДОВАНИЕ ФУНКЦИИ

Дана следующая функция:

изменяется в пределах от 100 до 500, А = 127

Производная функции:

Решение задачи нужно реализовать с помощью табличного редактора Microsoft Excel.

Все необходимые данные занесем в таблицу. В столбце «B» внесем значения х с шагом равным 5. В столбце «C» находиться сама функция F(x). В столбце «D» будет находиться производная данной функции, т. е. в ячейку «D4» запишем формулу

«=(80*5,5*ПИ()/180*COS(5,5*B4*ПИ()/180)+120*6,5*ПИ()/180*

*COS(6,5*B4*ПИ()/180))*5»

В границах того интервала, где производная будет изменять свой знак с минуса на плюс, будет находиться минимум функции.

Найдем произведение двух соседних значений производной. Если полученное произведение будет меньше нуля, то на данном интервале будет находиться экстремум функции. В ячейку E5 запишем формулу «=D4*D5». Для нахождения минимумов функции в ячейку F5 запишем формулу =ЕСЛИ(E5>0;" ";ЕСЛИ(D5<0;" ";"МИНИМУМ")). Т. е. если произведение двух соседних значений производной больше нуля, то на данном интервале функция монотонно убывает или возрастает, иначе, если значение производной меньше или равно нулю, то на данном интервале находится минимум функции.

В столбце «B» (Х) внесем значения x, x изменяется от 100 до 500 с шагом равным 5. Следовательно, в первую строку столбца «B» введем значение 100, а в следующую сроку этого же столбца введем значение 105, выделим эти два значения и растянем до 500.

В столбце «С» запишем функцию F(x). Это значит, что в первую строку этого столбца запишем формулу:

,

где В4 - это ссылка на ячейку, содержащую «х».

В столбце «D» вносим значение постоянной производной.

В столбце «E5» записываем формулу, представляющую собой произведение строк производной D4*D5.

Для нахождения экстремума функции - минимум в строку «F5» записываем соответствующую формулу с помощью логической функции «ЕСЛИ». =ЕСЛИ(E5>0;"-";ЕСЛИ(D5<0;"-";"МИНИМУМ"))

Результаты произведенных расчетов приведены в таблице 1.

Таблица 1 - Исследование функции F(x)

Исследование функцииАXF(x)F'(X)ПРОИЗВЕДЕНИЕЭКСТРЕМУМ127100-126,65-14,53127105-121,7523,54-342,10МИНИМУМ127110-82,9651,581214,19-127115-24,5162,053200,72-12712034,6453,233303,17-12712576,9029,411565,83-12713091,33-0,79-23,27-12713576,54-27,4121,68-12714040,45-42,351160,97-127145-2,97-41,871773,48-127150-38,64-27,561153,85-127155-55,46-5,47150,79-127160-49,7716,06-87,89МИНИМУМ127165-26,1129,42472,47-1271704,8330,24889,48-12717530,2518,84569,76-12718040,000,000,00-12718530,25-18,840,00-1271904,83-30,24569,76-127195-26,11-29,42889,48-127200-49,77-16,06472,47-127205-55,465,47-87,89МИНИМУМ127210-38,6427,56150,79-127215-2,9741,871153,85-12722040,4542,351773,48-12722576,5427,411160,97-12723091,330,7921,68-12723576,90-29,41-23,27-12724034,64-53,231565,83-127245-24,51-62,053303,17-127250-82,96-51,583200,72-127255-121,75-23,541214,19-127260-126,6514,53-342,10МИНИМУМ127265-93,1051,35746,33-127270-28,2875,283865,94-12727550,3278,005872,06-127280119,8357,304469,06-127285158,6718,061034,88-127290153,35-28,87-521,41-127295102,95-69,792014,67-12730020,00-92,206434,83-127305-72,71-88,638172,17-127310-148,52-59,105238,66-127315-184,78-11,35671,10-127320-169,6041,23-468,19МИНИМУМ127325-105,7983,473441,92-127330-10,35102,848584,15-12733590,1393,239587,21-127340167,1056,895303,28-127345198,293,87220,31-127350174,29-50,79-196,70-127355101,42-91,474645,63-1273600,00-106,479738,00-127365-101,42-91,479738,00-127370-174,29-50,794645,63-127375-198,293,87-196,70МИНИМУМ127380-167,1056,89220,31-127385-90,1393,235303,28-12739010,35102,849587,21-127395105,7983,478584,15-127400169,6041,233441,92-127405184,78-11,35-468,19-127410148,52-59,10671,10-12741572,71-88,635238,66-127420-20,00-92,208172,17-127425-102,95-69,796434,83-127430-153,35-28,872014,67-127435-158,6718,06-521,41МИНИМУМ127440-119,8357,301034,88-127445-50,3278,004469,06-12745028,2875,285872,06-12745593,1051,353865,94-127460126,6514,53746,33-127465121,75-23,54-342,10-12747082,96-51,581214,19-12747524,51-62,053200,72-127480-34,64-53,233303,17-127485-76,90-29,411565,83-127490-91,330,79-23,27МИНИМУМ127495-76,5427,4121,68-127500-40,4542,351160,97-

По данным столбцов «А», «F(x)», «F(x)» построим график функции и ее производной.

координата компьютерный оптимизационный решение

Рисунок 1 - График функции и ее производной

Имеется 8 пересечений в интервалах (100;105); (155;160); (200;205); (255;260); (315;320); (370;375); (430;435); (485;490). Для нахождения точек пересечения воспользуемся методом половинного деления. Для этого для каждого интервала создадим таблицу состоящую из столбцов: Xн, Хк, Хср, F'(Xн), F'(Xк),F(Xср), F'(Xср),F(Xср).

Суть метода половинного деления заключается в следующем: берется интервал и делится пополам, затем определяется, на какой половине находится точка пересечения. Затем берется эта половина и снова делиться пополам. Эти действия повторяются до тех пор пока не получим необходимую нам точность.

Для первого интервала (100;105) в таблицу заносим данные. В первые строки столбца «Xн» заносим значение 100, столбца «Хк» - 105, столбца «Хср» - формулу среднего арифметического значений столбцов «Xн» и «Хк». В столбцы F'(Xн), F'(Xк),F(Xср) заносим производную соответственно от Xн, Хк, Хср .

Значения второй и последующих строк столбцов «Xн» и «Хк» будут зависеть от того, в какой половине будет точка пересечения. Поэтому в эти строки заносим формулы, созданные с помощью логической функции «ЕСЛИ», суть которых заключается в следующем: если произведение F'(Xн) и F(Xср) будет меньше или равно 0, то точка пересечения будет находиться на первой половине. Исходя из этого, начальной точкой будет начальная точка всего интервала, а конечной точкой уже станет среднее значение предыдущего интервала.

Результаты расчетов по первому интервалу представлены в таблице 2.

Таблица 2 - Метод половинного деления для интервала (100;105)

XнXкXсрF'(Xн)F'(Xк)F'(Xср)F(Xср)ПОГРЕШНОСТЬ100,00105,00102,50-2,914,711,02-128,99-0,34100,00102,50101,25-2,911,02-0,93-129,05-0,28101,25102,50101,88-0,931,020,05-129,330,00101,25101,88101,56-0,930,05-0,44-129,27-0,06101,56101,88101,72-0,440,05-0,19-129,32-0,01101,72101,88101,80-0,190,05-0,07-129,330,00101,80101,88101,84-0,070,05-0,01-129,330,00101,84101,88101,86-0,010,050,02-129,330,00101,84101,86101,85-0,010,020,00-129,330,00101,84101,85101,84-0,010,000,00-129,330,00101,84101,85101,840,000,000,00-129,330,00101,84101,84101,840,000,000,00-129,330,00101,84101,84101,840,000,000,00-129,330,00101,84101,84101,840,000,000,00-129,330,00101,84101,84101,840,000,000,00-129,330,00101,84101,84101,840,000,000,00-129,330,00101,84101,84101,840,000,000,00-129,330,00101,84101,84101,840,000,000,00-129,330,00101,84101,84101,840,000,000,00-129,330,00101,84101,84101,840,000,000,00-129,330,00101,84101,84101,840,000,000,00-129,330,00

График изменения погрешности при нахождении первой точки пересечения будет иметь следующий вид:

Рисунок 2 - Погрешность от количества шагов при нахождении первой точки пересечения

Результаты расчетов по второму интервалу представлены в таблице 3.

Таблица 3 - Метод половинного деления для интервала (155;160)

XнXкXсрF'(Xн)F'(Xк)F'(Xср)F(Xср)ПОГРЕШНОСТЬ155,00160,00157,50-1,093,211,18-55,33-0,78155,00157,50156,25-1,091,180,06-56,110,00155,00156,25155,63-1,090,06-0,52-55,97-0,14155,63156,25155,94-0,520,06-0,23-56,08-0,03155,94156,25156,09-0,230,06-0,08-56,110,00156,09156,25156,17-0,080,06-0,01-56,110,00156,17156,25156,21-0,010,060,02-56,110,00156,17156,21156,19-0,010,020,01-56,110,00156,17156,19156,18-0,010,010,00-56,110,00156,18156,19156,190,000,010,00-56,110,00156,18156,19156,180,000,000,00-56,110,00156,18156,19156,190,000,000,00-56,110,00156,19156,19156,190,000,000,00-56,110,00156,19156,19156,190,000,000,00-56,110,00156,19156,19156,190,000,000,00-56,110,00156,19156,19156,190,000,000,00-56,110,00156,19156,19156,190,000,000,00-56,110,00156,19156,19156,190,000,000,00-56,110,00156,19156,19156,190,000,000,00-56,110,00156,19156,19156,190,000,000,00-56,110,00

Рисунок 3 - Погрешность от количества шагов при нахождении первой точки пересечения

И так для каждого интервала.

Правильность нахождения координат точек можно проверить с помощью «Подбора параметра». Подбор параметра - это способ поиска определенного значения ячейки путем изменения значения в другой ячейке. Для этого из пункта меню «Сервис» выбираем «Подбор параметра». В открывшемся окне в поле «Установить в ячейке» ссылаемся на ячейку с данной нам функцией. В поле «Значение» указываем значение необходимого нам параметра. В поле «Изменяя значение ячейки» ссылаемся на ячейку со значением переменной, где указано ближайшее значение найденного интервала.

Проверка правильности нахождения точек пересечения по средствам «Подбора параметра» показала, что координаты точек, найденные методом половинного деления, оказались правильными.

При сопоставлении результатов, полученных методами половинного деления и с помощью подбора параметра, определили, что метод подбора параметра лучше, так как экономиться время и результаты представляются всего одной таблицей.

. РЕШЕНИЕ ТРАНСПАРТНОЙ ЗАДАЧИ С ПОМОЩЬЮ СРЕДСТВ EXCEL

Экономико-математические задачи, цель которых состоит в нахождении наилучшего, то есть оптимального с точки зрения одного или нескольких критериев варианта использования имеющихся ресурсов, называются оптимизационными.

Оптимизационные задачи решаются с помощью оптимизационных моделей методами математического программирования.

Математическое программирование - это раздел прикладной математики, который изучает задачи оптимизации и методы их решения с ориентацией на современные средства компьютерной техники.

Структура оптимизационной модели включает целевую функцию, области допустимых решений и системы ограничений, определяющих эту область.

Область допустимых решений - это область, в пределах которой осуществляется выбор решений. В экономических задачах она ограничена наличными ресурсами и условиями, которые записываются в виде системы ограничений, состоящей из уравнений и неравенств.

Главная задача математического программирования - это нахождение экстремума функций при выполнении указанных ограничений. Если система ограничений несовместима, то область допустимых решений является пустой.

Сущность задач оптимизации: определить значение переменных х1, х2,..., хn, которые обеспечивают экстремум целевой функции Е, с учетом ограничений, наложенных на аргументы этой функции.

"Поиск решения" позволяет задавать ограничения для изменяемых ячеек. Подобного рода условия называются ограничениями для решаемой задачи. "Поиск решения" доставляет не заранее известный конкретный результат для целевой функции, а отыскивает оптимальное (минимальное или максимальное), т.е. наилучшее из возможных решение.

Условие задачи:

На складах w1, w2, w3 хранятся соответственно 15, 25, 20 кроватей, которые должны быть распределены по четырем магазинам ml, m2, m3, m4, где требуется 20, 12, 5 и 9 кроватей. Пусть стоимость перевозки одной кровати со склада в магазин задается следующей таблицей в условных единицах:

СкладМагазинmlm2m3m4W12224W23113W33634

Как следует планировать перевозку для минимизации стоимости?

Обозначим искомые объемы перевозок от поставщиков к потребителям следующим образом:

а11 - количество кроватей, перевезенных с первого склада первому магазину;

а12 - количество кроватей, перевезенных с первого склада второму магазину;

а13 - количество кроватей, перевезенных с первого склада третьему магазину;

а14 - количество кроватей, перевезенных с первого склада четвертому магазину;

а21 - количество кроватей, перевезенных со второго склада первому магазину;

а22 - количество кроватей, перевезенных со второго склада второму магазину;

а23 - количество кроватей, перевезенных со второго склада третьему магазину;

а24 - количество кроватей, перевезенных со второго склада четвертому магазину;

а31 - количество кроватей, перевезенных с третьего склада первому магазину;

а32 - количество кроватей, перевезенных с третьего склада второму магазину;

а33 - количество кроватей, перевезенных с третьего склада третьему магазину;

а34 - количество кроватей, перевезенных с третьего склада четвертому магазину.

Формулируем целевую функцию, которая представляет собой сумму произведений количества кроватей, перевозимых с конкретного склада конкретному магазину на стоимость перевозки одной кровати. Для составления оптимального плана перевозки целевая ячейка должна быть минимальной, так как затраты на перевозку должны быть минимальными.

Затраты на перевозку составят:

Z=2*а11 + 2*а12 + 2*a13 + 4*а14 + 3*а21 + 1*а22 + 1*a23+ 3*а24 + 3*а31 + 6*а32 + 3*a33+ 4*а34.

Изменяя значения параметров и удовлетворяя всем ограничениям, получим минимальные затраты на перевозку кроватей.

Вводим формулы в ячейки:

В ячейку I15: =C15+D15+E15+F15+G15. Это объемы поставок с первого склада.

В ячейку I16: =C16+D16+E16+F16+G16. Это объемы поставок со второго склада.

В ячейку I17: =C17+D17+E17+F17+G17. Это объемы поставок с третьего склада.

В ячейку С19: =C15+C16+C17. Это суммарная потребность первого магазина в кроватях.

В ячейку D19: =D15+D16+D17. Это суммарная потребность второго магазина в кроватях.

В ячейку E19: =E15+E16+E17. Это суммарная потребность третьего магазина в кроватях.

В ячейку F19: =F15+F16+F17. Это суммарная потребность четвертого магазина в кроватях.

В ячейку G19: =G15+G16+G17. Это сумма всех невостребованных кроватей.

Тогда в ячейку C20 запишем формулу для нахождения минимальных затрат на перевозку: =C6*C15+C7*C16+C8*C17+D7*D16+D6*D15+D8*D17+

+E6*E15+E7*E16+E8*E17+F6*F15+F7*F16+F8*F17+G15*G6+G7*G16+G8*G17

После создания целевой ячейки для решения задачи воспользуемся поиском решения. В поле «Установить целевую» дается ссылка на ячейку с функцией, для которой будет находиться минимум.

В поле «Изменяя ячейки» выделяем диапазон ячеек (C15;G17).

Далее составляем ограничения на потребность в кроватях:

для первого магазина: а11 + а21 + a31 =20

для второго магазина: a12 + а22 + а32 =12

для третьего магазина: а13 + а23 + a33 =5

для четвертого магазина: а14 + а24 + a34 =9

количество невостребованных кроватей: а15 + а25 + a35 =14.

Составляем ограничения на вместимость складов:

для первого склада: а11 + а12 + a13+ а14 + а15 =15

для второго склада: а21 + а22 + a23+ а24 + а25 =20

для третьего склада: а31 + а32 + a33+ а34 + a35 =25

Все значения, которые будут найдены, должны быть целыми числами и неотрицательными. Потребности магазинов должны быть удовлетворены полностью, однако количество кроватей не должно превышать количества кроватей, находящихся на складах.

После этого нажимаем кнопку «Выполнить» и на экране отображается оптимальное решение данной задачи.

Полученный результат представлен в таблице 4.

Таблица 4 - Результат решения задачи

Из таблицы видно, что потребности магазинов были полностью удовлетворены. А затраты на перевозку кроватей оказались минимальными и составили 95 условных единиц.

Проверим найденный план на оптимальность. Для этого найдем потенциалы строк и столбцов.

СкладыМагазиныВместимость складовUm1m2m3m4Остаткиw1150000150w2012530200w3500614251Потребность2012591460V2113-1

Найдем оценки пустых ячеек:

S12 =2-(0+1)=1

S13 =2-(0+1)=1

S14 =4-(0+3)=1

S15 =0-(0-1)=1

S21 =3-(0+2)=1

S25 =0-(0-1)=1

S32 =6-(1+1)=4

S33 =3-(1+1)=1

Так как оценки пустых ячеек больше нуля, то найденный план оптимален. Следовательно, решение, полученное с помощью возможностей Excel (с помощью поиска решения), является оптимальным.

ЗАКЛЮЧЕНИЕ

В данной курсовой работе были решены оптимизационные задачи с использованием программных средств Excel.

В ходе решения первой задачи был построен график функции F(x) в заданном диапазоне значений переменной Х. Были найдены интервалы значений переменной Х, в пределах которых функция принимает минимальные значения. С использованием метода половинного деления были найдены значения переменной, при которых функция принимает минимальные значения, в соответствии с заданной точностью вычислений, равной 0,0001. Проверка правильности вычислений была осуществлена с помощью «Подбора параметра».

Решение второй задачи осуществлялось с помощью «Поиска решений» средствами Excel. Была составлена целевая функция и ограничения (соответствующие условию задачи). В результате был найден оптимальный план решения задачи.

ЛИТЕРАТУРА

1.Новиков Е.В., Лавшук О.А. Решение оптимизационных задач средствами Excel. Методическое пособие по дисциплине «Вычислительная техника и программное обеспечение» для студентов специальностей 1-45 01 04 - Почтовая связь.

2.Левкович О.А., Шелкоплясов Е.С., Шелкоплясова Т.Н. Основы компьютерной грамотности. Учебное пособие. - М.: «Тетрасистемс»,2005 -514с.

.3. Е.К. Овчаренко, О.П. Ильина, Е.В. Балыбердин. Финансово-экономические расчеты в Excel. Издание 2-е, дополненное - М.: Информационно-издательский дом «Филинъ», 1998.-184 с.

МИНИСТЕРСТВО СВЯЗИ И ИНФОРМАТИЗАЦИИ РЕСПУБЛИКИ БЕЛАРУСЬ Учреждение образования «ВЫСШИЙ ГОСУДАРСТВЕННЫЙ КОЛЛЕДЖ СВЯЗИ» ФАКУЛЬТЕТ ЭКОНОМИКИ И П

Больше работ по теме: