Решение задачи математического программирования с помощью MS Excel

Решим задачу, формализованную в предыдущем пункте, с помощью средств MS Excel. Для этого выполним команды «Сервис» - «Поиск решения» («Tools» - «Solver»). Средство поиска решений является одной из надстроек Excel. Если в меню «Сервис» («Tools») отсутствует команда «Поиск решения» («Solver»), то для её установки необходимо выполнить команду «Сервис» - «Надстройки» - «Поиск решения» («Tools» - «Add-ins» - «Solver»).

Составим таблицу исходных данных. Отведём ячейки B13:Е13 под значения переменных x₁ – x₄(рис.2.1). В ячейку В14 введём формулу, для вычисления целевой функции:

=СУММПРОИЗВ(B9:E9;B13:E13) (2.15),

аргументами которой являются ссылки на соответствующие ячейки, содержащие значения исходных данных по себестоимости, и ссылки на ячейки, содержащие значения независимых переменных (рис.2.1). В ячейки В17:В21 введём левые части для ограничений №5-№9:

=СУММПРОИЗВ(B5:E5;$B$13:$E$13),

=СУММПРОИЗВ(B6:E6;$B$13:$E$13),

=СУММПРОИЗВ(B7:E7;$B$13:$E$13), (2.16)

=СУММПРОИЗВ(B8:E8;$B$13:$E$13);

=СУММПРОИЗВ($B$13:$E$13;B11:E11)

а правые части по этим ограничениям заданы ячейками F5:F8 и F11 таблицы исходных данных.

Рис.2.1. Подготовка информации для решения ЗЛП

После этого выберем команду «Сервис» - «Поиск решения» и заполним диалоговое окно, как показано на рис.2.2. В поле «Установить целевую ячейку» («Set Target Cell») диалогового окна «Поиск решения» («Solver») дается ссылка на ячейку с функцией, для которой 6удет определяться максимум, минимум или заданное значение. Для нашего случая в поле «Установить целевую ячейку» («Set Target Cell») вводится $B$14(рис.2.2).Тип взаимосвязи между решением и целевой ячейкой задается путем установки переключателя в группе «Равной» («Equal To»). Для нахождения максимального или минимального значения целевой функции этот переключатель ставится в положение «Максимальному значению» («Мах») или «Минимальному значению» («Min»), соответственно. Для нахождения значения целевой функции, заданного в поле группы «Равной» («Equal To»), переключатель ставится в положение «Значению» («Value of»). В нашей задаче установим переключатель в положение «Минимальному значению» («Min»), т.к. планируется производство, обеспечивающее минимальные затраты.

В поле «Изменяя ячейки» («By Changing Cells») указываются ячейки, которые должны изменяться в процессе поиска решения задачи, т. е. ячейки отведенные под переменные решаемой задачи. В нашем случае введем в поле «Изменяя ячейки» («By Changing Cells») диапазон $B$13:$E$13.

Рис.2.2. Пример заполнения диалогового окна Поиск решения

Ограничения, налагаемые на переменные задачи, отображаются в поле «Ограничения» («Subject to the Constraints»). Средство поиска решений допускает ограничения в виде равенств, неравенств, а также позволяет ввести требование целочисленности переменных. Ограничения добавляются по одному. Для ввода ограничений нажмите кнопку «Добавить» («Add») в диалогом окне «Поиск решения» («Solver») и в открывшемся диалоговом окне «Добавление ограничения» («Add Constraint») заполните поля. В нашей задаче ограничения №1-№4 заполняются на основе таблицы исходных данных, то есть соответствующего диапазона, содержащего информацию о допустимой нагрузке на рудник. Соответственно, в данном случае окно добавления ограничения выглядит следующим образом (рис 2.3).

Рис. 2.3. Диалоговое окно добавление ограничения

В поле Ссылка на ячейку («Cell Reference») введите левую часть ограничения — $В$1З:$Е$1З, а в поле «Ограничение» («Constraints») — правую часть, в нашем примере — $B$10:$E$10. С помощью раскрывающегося списка вводится тип соотношения между левой и правой частями ограничения. В нашем случае «<=». Таким образом, первые четыре ограничения модели введены. Нажмите кнопку «Добавить» («Add») в диалоговом окне «Добавление ограничения» («Add Constraint») и введите следующую группу ограничений, налагаемых на переменные. Нажатие кнопки ОК завершает ввод ограничений. Обратите внимание на то, что ограничения удобнее задавать в виде диапазонов, как это сделано в рассматриваемом примере.

Теперь нажмите кнопку «Параметры» («Options») в диалоговом окне «Поиск решения» («Solver»), для того чтобы проверить, какие параметры заданы для поиска решений. В открывшемся диалоговом окне «Параметры поиска решения» («Solver Options») (рис.2.4) можно изменять условия и варианты поиска решения исследуемой задачи, а также загружать и сохранять оптимизируемые модели.

Рис. 2.4. Установка параметров в диалоговом окне «Параметры поиска решения»

Рассмотрим элементы этого окна. Поле «Максимальное время» («Max Time») служит для ограничения времени, отпускаемого на поиск решения задачи. Поле «Предельное число итераций» («Iteration») служит для ограничения числа промежуточных вычислений. Поля «Относительная погрешность» («Precision») и «Допустимое отклонение» («Tolerance») служат для задания точности, с которой ищется решение. Рекомендуется после нахождения решения с величинами данных параметров, заданными по умолчанию, повторить вычисления с большей точностью и меньшим допустимым отклонением и сравнить с первоначальным решением. Использование подобной проверки особенно рекомендуется для задач с требованием целочисленности переменных.

Флажок «Линейная модель» («Assume Linear model») служит для поиска решения линейной задачи оптимизации или линейной аппроксимации нелинейной задачи. В нашем случае все ограничения и целевая функция линейны (представляют собой многочлены первой степени), следовательно флажок необходимо установить. В случае нелинейной задачи этот флажок должен быть сброшен.

Флажок «Показывать результаты итераций» («Show Iteration Results») служит для приостановки поиска решения и просмотра результатов отдельных итераций.

Флажок «Неотрицательные значения» накладывает дополнительные ограничения на изменяемые переменные, требуя их неотрицательности - то есть фактически его установка аналогична введению ограничений через диалоговое окно ввода ограничений, где знак неравенства «>=», а правая часть неравенства – «0». Данный флажок необходим, чтобы выполнить ограничения №10-№13 задачи.

Флажок «Автоматическое масштабирование» («Use Automatic Scaling») служит для включения автоматической нормализации входных и выходных значений, качественно различающихся по величине, например, при максимизации прибыли в процентах по отношению к вложениям, исчисляемым в миллионах рублей.

Группа «Оценка» («Estimates») служит для выбора метода экстраполяции. Группа «Разности» («Derivatives») служит для выбора метода численного дифференцирования. Группа «Метод поиска» («Search») служит для выбора алгоритма оптимизации.

По нажатии кнопки «Выполнить» диалогового окна «Поиск решения» (рис.2.2) происходит выполнение алгоритма поиска оптимального решения заданной модели задачи. В результате получаем следующее решение задачи (рис 2.5).

В нашем случае объёмы добычи по рудникам составили соответственно: по первому 6,85 тыс.т, по второму 12 тыс.т, по третьему 2,27 тыс.т, по четвёртому 6 тыс.т, при этом выполняются все ограничения, а суммарные затраты минимальны и равны 25,26 тыс.руб.

Рис. 2.5. Результаты решения задачи планирования производства

Варианты для выполнения лабораторной работы №2

Задание

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

Подставьте необходимые значения переменных для соответствующих вариантов выполнения задания из таблицы 2.2 и решите задачу с использованием MS Excel.

Таблица 2.2

Вариант №	Рассматриваемые рудники[2]	Задание по количеству металла в концентрате по видам металла, т
Вид металла
Рудник №1	Рудник №2	Рудник №3	Рудник №4
				-
			-
		-
	-
				-
			-
		-
	-
				-
			-
		-
	-
				-
			-
		-
	-
				-
			-
		-
	-
				-
			-
		-
	-

6.Рекомендуемая литература

1. Гарнаев А.Ю. Использование MS Excel и VBA в экономике и финансах. – СПб.:БХВ – Санкт-Петербург, 2000. – С. 112-120.

2. Резниченко С.С., Ашихмин А.А. Математические методы и моделирование в горной промышленности. – М.: МГГУ, 1997. – С.71-77.

3. Резниченко С.С., Ашихмин А.А., Подольский М.П., Стрельцова Т.В. Сборник конкретных ситуаций и задач для самостоятельной работы по курсу «Математическое программирование и моделирование». – М.:МГГУ, 1988. – С.2-6.