Решение задач оптимизации при ограничениях на ресурсы в MS EXCEL

МИНОБРНАУКИ РОССИИ



Федеральное государственное бюджетное образовательное учреждение высшего образования

«Чувашский государственный университет имени И. Н. Ульянова»



Факультет информатики и вычислительной техники

Кафедра компьютерных технологий





КУРСОВОЙ ПРОЕКТ

по дисциплине «Информатика и программирование»

на тему «Решение задач оптимизации при ограничениях на ресурсы в MS EXCEL»







Выполнил: студент 

группы КТ-31-17

Разуваев Михаил Александрович

Проверил: доцент Матвеев С.В





№________

__________







Чебоксары 
2017

Оглавление

Введение………………………………………………………………………………………………………………………………………………..3

		1	Решение оптимизационных задач в MS Excel	4

		1.1	Общий алгоритм решения	4

		1.2	Установка Поиска решения	5

		2	Примеры решения задач	9

		2.1	Пример 1	9

		2.2	Пример 2	11

		2.3	Пример 3	13

Заключение………………………………………………………………………………………………………………………………………….16

Литература……………………………………………………………………………………………………………………………………………17



    









		

		

		

		

		

		

		

		

		

		

		

		

		

		

		

		

		Введение

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

		К задачам, направленным на оптимизацию, относятся: 

		задачи, направленные на оптимальное планирование деятельности предприятий;

		задачи оптимального распределения трудовых ресурсов; 

		бинарные задачи распределения; 

		задачи оптимального прикрепления потребителей к поставщикам (транспортная); 

		задача оптимального составления смесей; 

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

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

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

			Использование математических моделей позволяет использоваться мощь ЭВМ для анализа приемлемых решений и поиска наиболее оптимального.

			Поиск решения является дополнительной надстройкой табличного процессора MS Excel (используется с 1991 года).

			Высокая эффективность применения поиска решений объясняется интеграцией программы оптимизации и табличного документа. Solver- встроенная в среду табличного процессора MS Excel, программа, которая является распространённым инструментом для поиска оптимальных решений в сфере бизнеса

		

		

		

		

		

		

		

Оптимизационные задачи в MS Excel

			Освоение работы с надстройкой «Поиск решений» даст преимущество в решении многих экономических задач: минимизация расходов при формировании состава сырья (например, на текстильных предприятиях), оптимизация раскроя (например, на швейных производствах), минимизация расходов при формировании штатного расписания, оптимизация расходов на изготовление при выборе ассортимента продукции, максимизация прибыли при формировании инвестиционной программы и др.

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

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

Общий алгоритм решения

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

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

			Поиск решения – это надстройка MS Excel. С помощью этой надстройки можно найти оптимальное решение с учётом ведённых пользователем ограничений. 

			Общий алгоритм решения оптимизационных задач в MS Excel:

		Составить математическую модель

		Вывести на рабочий лист Excel условия задачи:

		Создать таблицу на рабочем листе для ввода условий;

		Ввести исходные данные, функцию, условия

		Выполнить команду Данные-> Анализ-> Поиск решения.

		В диалоговом окне «Параметры поиска» указать параметры

		Полученные результаты нужно проанализировать

		

		

		

		

		

Установка Поиска решения

			Команда поиск решения находится в группе Анализ на вкладке Данные

		

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

		Для этого:

		На вкладке файл выберите команду Параметры, а затем – категорию Надстройки;

		В поле Управление выберите значение Надстройки Excel и нажмите кнопку Перейти;

		В поле Доступные надстройки установите флажок рядом с пунктом Поиск решения и нажмите кнопку ОК.

		

			После нажатия кнопки Поиск решения в группе Анализ, откроется диалоговое окно 

		

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

		Параметры задачи ограничиваются такими предельными показателями: 

		количество неизвестных – 200; 

		количество формульных ограничений на неизвестные – 100; 

		количество предельных условий на неизвестные – 400. 

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

			В поле Изменяя ячейки переменных указывается адрес блока ячеек, которые и будут решением.

			В область в соответствии с ограничениями вводятся ограничения на решение. Кнопки Добавить, Изменить, Удалить управляют ограничениями.

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

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

		Поиск решения в зависимости от типа решаемых задач, позволяет использовать методы: 

		Симплексный метод. Используется для линейных задач.

		Нелинейный метод обобщенного понижающего градиента (ОПГ).    Используется для гладких нелинейных задач

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

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

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

Ниже описаны основные параметры вкладки Все методы. 

Точность ограничения. Указывает точность выполнения ограничения. При задании меньшей точности задача будет решаться быстрее.

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

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

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

Максимальное время. Предоставляет возможность ограничить максимальное время решения задачи (в секундах). Если появится сообщение, что время на решение задачи истекло, то его можно добавить.

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

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

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































Примеры решения задач

Использование надстройки Поиск решения и сценариев

Пример 1

Введите в Excel данные из столбцов А-С из приведенной таблицы. Значения в столбце D рассчитайте по соответствующим формулам. 



А

В

C

D

1

Наименование

Цена за шт./ кг.

Количество

Всего

2

Яблоки

9р.

3

27р.

3

Апельсины

10р.

3

30р.

4

Печенье

35р.

1,5

53р.

5

Конфеты

40р.

2

80р.

6

Вино

25р.

3

75р.

7





Итого:

265р.



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

количество яблок не должно превышать 4-х кг; 

количество печенья - не менее 1кг.; 

количество вина - не меньше 3-х и не больше 6 бутылок; при этом значение этого параметра должно быть целое число. 

число. 

 

Для этого выполните следующие действия: 

Введите команду Данные – Поиск решения и в диалоговом окне Поиск решения установите следующие параметры: 

 

адрес целевой ячейки -$D$7 – общая сумма покупки; 

подбираемое для целевой ячейки значение – 400 р.; 

в поле Изменяя ячейки введите абсолютные адреса ячеек с количеством купленных яблок, печенья и вина – $С$2; $С$4; $С$6; 

введите описанные выше Ограничения для ячеек $С$2; $С$4; $С$6. 

 

По окончании оформления нажмите кнопку Выполнить 

В диалоговом окне Результаты поиска решения установите: Сохранить найденное решение; Отчет – результаты.  

Сохраните работу. 















Пример 2

Условие: Фирма производит несколько сортов йогурта. Условно – «1», «2» и «3». Реализовав 100 баночек йогурта «1», предприятие получает 200 рублей. «2» - 250 рублей. «3» - 300 рублей. Сбыт, налажен, но количество имеющегося сырья ограничено. Нужно найти, какой йогурт и в каком объеме необходимо делать, чтобы получить максимальный доход от продаж.

Известные данные (в т.ч. нормы расхода сырья) занесем в таблицу:



На основании этих данных составим рабочую таблицу:



Количество изделий нам пока неизвестно. Это переменные.

В столбец «Прибыль» внесены формулы: =200*B11, =250*В12, =300*В13.

Расход сырья ограничен (это ограничения). В ячейки внесены формулы: =16*B11+13*B12+10*B13 («молоко»); =3*B11+3*B12+3*B13 («закваска»); =0*B11+5*B12+3*B13 («амортизатор») и =0*B11+8*B12+6*B13 («сахар»). То есть мы норму расхода умножили на количество.

Цель – найти максимально возможную прибыль. Это ячейка С14.

Вносим параметры после активизации «Поиск решения»



После нажатия кнопки «Выполнить» программа выдает свое решение.



Оптимальный вариант – сконцентрироваться на выпуске йогурта «3» и «1». Йогурт «2» производить не стоит.

































Пример 3

Рассмотрим пример оптимизации транспортных расходов с помощью инструмента Excel «Поиск решений».

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

Необходимо оптимально распределить ездки в населенные пункты между транспортными компаниями таким образом, чтобы транспортные расходы были минимальными.

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

 

 Рис. 1. Расчет оптимальных перевозок

На рис. 1 расположены две таблицы: с исходными данными и расчетными данными. В ячейках D8:H11 расположены тарифы за 1 ездку в разрезе транспортных компаний до пунктов назначения, в ячейках D12:H12 — плановое количество ездок за период до пунктов назначения, в ячейках I8:I11 — удельный вес перевозок каждой транспортной компании в общем количестве планируемых перевозок за период. Эти ячейки для удобства не раскрашены. В ячейках J8:J12 и Н13 рассчитано число ездок по каждой транспортной компании и в целом за период. Формулы в этих ячейках выглядят следующим образом:

Ячейка Н13: =СУММ(D12:H12),

Ячейка J8: =I8*$H$13.

Данную формулу из ячейки J8 протаскиваем (копируем) в ячейки J9, J10, J11.

Ячейка J12: =СУММ(J8:J11).

Следующая таблица на листе посвящена расчету и называется «Расчет». Ячейки D19:Н22 предназначены для распределения количества ездок до пунктов назначения между транспортными компаниями. На рис. 1 в ячейках дано такое распределение, заполненное вручную. В ячейках D23:I27 рассчитаны суммы расходов на транспортные перевозки в разрезе транспортных компаний, оказывающих транспортные услуги, и пунктов назначений, а также итоги.

Приведем формулы, представленные в этих ячейках.

Значения в ячейках D24:Н27 получены перемножением количества ездок (ячейки D19:Н22) на тарифы (ячейки D8:Н12). В ячейку D24 запишем формулу:

=D19*D8.

Протащим (скопируем) формулу в ячейки D25:D27 и E24:Н27.

В ячейках D23:I23 формируются итоговые суммы транспортных услуг в разрезе пунктов назначения. Запишем в ячейку D23 формулу:

=СУММ(D24:D27).

Скопируем  эту формулу в ячейки Е23:I23.

В ячейках I24:I27 формируются итоговые суммы транспортных услуг в разрезе компаний, оказывающих эти услуги. Запишем в ячейку I24 формулу:

=СУММ(D24:H24).

Протащим (скопируем) ее в ячейки I25:I27.

Таким образом, стоимость транспортных расходов по компании в целом формируется в ячейке I23. В первоначальном расчете, представленном на рис. 1, данная сумма равна 35 790 руб.

Скопируем данный лист в эту же книгу. Далее необходимо приступить непосредственно к оптимизации. Задача — подобрать в ячейках D19:Н22 такие значения, чтобы в ячейке I23 была рассчитана минимальная сумма расходов на транспорт. Для этого воспользуемся инструментом «Поиск решений».

Для начала надо выбрать оптимизируемую ячейку (I23). Затем вызовем диалоговое окно «Поиск решений», представленное на рис. 2.

Это важно. Надстройку «Поиск решений» не всегда можно обнаружить в меню рабочего стола компьютера, так как она может быть не подключена. Для ее подключения необходимо выполнить ряд действий, которые аналогичны во всех версиях MS Office: «Сервис — Надстройки — Поиск решений (установить флажок)». Теперь данный инструмент можно будет найти на панели инструментов рабочего стола.

 

Рис. 2. Использование надстройки «Поиск решений»

В строке «Оптимизировать целевую функцию» будет стоять адрес оптимизируемой ячейки, в данном случае — $I$23. Выберем цель, поставив флажок «Минимум». В строке «Изменяя ячейки переменных» помещаются адреса ячеек, которые необходимо будет подобрать для достижения желаемого результата ($D$19:$Н$22).

В поле запишем ограничения в соответствии с ограничениями. Для этого воспользуемся кнопкой «Добавить», которая откроет окно «Добавить ограничения». Введем одно из ограничений:

$D$19:$H$22 = целое,

$D$12:$H$12 = $D$18:$H$18,

$J$8:$J$11 = $I$19:$I22.

Чтобы добавить следующее ограничение, в этом же окне нажмите на кнопку «Добавить». Результатом этого действия будет добавление текущего ограничения в список ограничений, а поля окна «Добавить ограничения» будут очищены для ввода следующего ограничения. После того как введено последнее из ограничений, необходимо нажать на кнопку «ОК».













ЗАКЛЮЧЕНИЕ 

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

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

Электронные таблицы MS Ехсеl имеют огромный набор возможностей. Однако обычно пользователь в своей работе применяет только их небольшую часть. Происходит это не только от незнания, но и от отсутствия в этом острой необходимости. И действительно, все функции, заложенные в Excel, можно условно разделить на те, знание которых просто необходимо знать, и те, изучать которые можно по мере надобности.











































Литература 

 

Акулич, И. Л. Математическое программирование в примерах и задачах : учеб. пособие / И. Л. Акулич. – СПб. : Лань, 2009. – 532 с. 

Васильев, А. Н. Финансовое моделирование и оптимизация средствами Excel2007 / А. Н. Васильев. – СПб. : Питер, 2009. – 320 с. 

Гарнаев, А. Ю. Microsoft Excel 2010: разработка приложений  / А. Ю. Гарнаев, Л. В. Рудикова. – СПб. : БХВ-Петербург, 2011. – 528 с. 

Глухов, В. В. Математические методы и модели для менеджмента : 

учеб. пособие / В. В. Глухов, М. Д. Медников, С. Б. Коробков. – СПб. : Лань, 2007. – 528 с. 

Иванов, И. Microsoft Excel 2010 для квалифицированного пользователя / И. Иванов. – М. : Академия АЙТИ, 2011. – 244 с. 

Леоненков, А. В. Решение задач оптимизации в среде MS Excel  / А. В. Леоненков. – СПб. : БХВ-Петербург, 2005. – 704 с. 

Пикуза, В. Экономические расчеты и бизнес-моделирование в Excel  / В. Пикуза. – СПб. : Питер, 2011. – 398 с. 

Решение задач оптимизации управления с помощью MS Excel 2010  // НОУ «ИНТУИТ» [Электронный ресурс]. – Режим доступа: http://www.intuit.ru/studies/courses/4751/1020/info (дата обращения: 09.12.2015). 

Справка и инструкции по Excel // Поддержка по Microsoft Office [Электронный ресурс]. – Режим доступа: http://office.microsoft.com/ruru/excel-help (дата обращения: 14.12.2015). 

Токарев, В. В. Модели и решения: исследование операций для экономистов, политологов и менеджеров / В. В. Токарев. – М. : ФИЗМАТЛИТ, 2014. – 408 с. 

Уокенбах, Дж. Формулы в Microsoft Excel 2010 : пер. с англ. / Дж. Уокенбах. – М. : И. Д. Вильямс, 2011. – 704 с. 

Уокенбах, Дж. Microsoft Excel 2010. Библия пользователя : пер. с англ. / Дж. Уокенбах. – М. : И. Д. Вильямс, 2011. – 912 с. 

Экономико-математические методы и модели. Компьютерные 

технологии решения : учеб. пособие / И. Л. Акулич, Е. И. Велесько, П. Ройш,  

В. Ф. Стрельчонок. – Минск : БГЭУ, 1986. – 348 с. 

 













































































		

		

		

19.......................