Тема 1.2. Электронные таблицы. Решение задач оптимизации в MS Excel (базовая часть).

Цели и задачи.

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

Справочный материал.

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

В математике под оптимизацией понимают задачу поиска экстремума (минимума или максимума) некоторой целевой функции в заданной области пространства размерности n, ограниченной набором линейных (нелинейных) равенств (неравенств).

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

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

В математическую модель входит:

- набор переменных X = (x₁,x₂,….,x_n), изменяя значения которых можно найти оптимальное решение (план задачи);

- целевая функция, зависящая от X и позволяющая численно оценить оптимальность выбранного решения;

- условия (ограничения), которым обязано удовлетворять выбранное решение.

На оптимальном решении целевая функция принимает экстремальное значение (минимум или максимум). В качестве целевой функции в задаче может подразумеваться прибыль предприятия, затраты производства, объём выпуска продукции, стоимость перевозки грузов и т. п. – любая величина, выраженная через набор значений X (это могут быть различные ресурсы, имеющиеся в распоряжении в конкретный момент - материальные, трудовые, финансовые, технологические и т.п.). Условия обычно задаются исходя из ограниченности ресурсов.

В общем виде математическая модель задачи оптимизации выглядит так:

найти значение X=(x₁,x₂,….,x_n), на котором целевая функция f(X) достигает минимума (максимума)

при ограничениях в виде равенств

g_i(X)=b_i, i=1,…m

и (или) в виде неравенств

g_j(X) £ b_j, и (или) g_j(X)³ b_j, j=1,…k.

Число неизвестных n называют размерностью задачи. Также на практике на вектор неизвестных X для упрощения накладывается ограничение неотрицательности: x_i≥ 0, (i= 1,…, n).

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

Электронные таблицы MS Excel имеют встроенные средства решения задач поиска экстремума функции, оформленные в виде надстройки Поиск решения. Перед началом работы убедитесь, что данная надстройка присутствует на вкладке ленты Данные в группе Анализ. Включить надстройки в MS Excel 2010 можно через меню Файл - Параметры в группе Управление надстройками по кнопке Перейти (рис. 3).

Рис. 3. Окно включения надстройки Поиск решения в MS Excel 2010.

Если в окне на рис. 3 пункт Поиск решения отсутствует, требуется переустановка пакета MS Office.

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

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

Здесь указы­вают ограничения в виде равенств или неравенств

Здесь указы­вают адрес ячейки, со­дер­жащей формулу с целевой функ­цией

Рис. 4. Окно режима Поиска решения MS Excel 2010.

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

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

Рис. 5. Окно добавления ограничений в режиме Поиска решения.

Более подробно примеры использования поиска решение рассмотрены в [10].

Примеры задач и образцы их решения.

Задача 1.2.1. Решить задачу оптимизации при заданных ограничениях:

Решение.

Данная задача оптимизации является линейной.

Для работы в режиме Поиска решения предварительно разместим в отдельных ячейках листа книги MS Excel коэффициенты c_i при неизвестных x_i целевой функции f(X) (в примере они равны 1), коэффициенты a_j,i при неизвестных в ограничениях - неравенствах и правые части b_j (i=1,2, j=1,2,3). Отдельно можно ввести знаки ограничений (исключительно для удобства восприятия информации).

Далее укажем ячейки – переменные для неизвестных (x₁, x₂). Им можно задать произвольные значения (в том числе нулевые), или оставить пустыми. Решением задачи является рассчитываемый надстройкой Поиск решения набор пере­менных X = (x₁, x₂), обеспечивающий максимальное значение целевой функции f(X)=x₁+x₂ (ее формула также размещается в отдельной ячейке) и удовлетворяющий заданной системе ограничений - неравенств.

Следующим этапом подготовки задачи к решению является запись в ячейки математических выражений, связывающих между собой коэффициенты и неизвестные. Поскольку все зависимости в задаче линейные, в качестве формулы достаточно записать сумму произведений соответствующих коэффициентов и неизвестных, ссылаясь на выделенные для них ячейки. Удобно воспользоваться встроенной функцией СУММПРОИЗВ (диапазон1; диапазон2), которая перемножает соответствующие элементы заданных диапазонов и возвращает сумму их произведений.

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

1. Заполняем ячейки листа книги MS Excel по заданному образцу (см. рис. 6).

2. Вызываем окно режима Поиска решения.

Далее:

- указываем адрес ячейки с целевой функцией (абсолютная ссылка на формулу в ячейке $B$9);

- указываем, какое значение должна принимать целевая функция (максимум);

- указываем, какие ячейки можно изменять в процессе оптимизации ($B$6:$C$6);

- добавляем ограничения (если ограничения имеют одинаковый знак неравенства, можно использовать ссылки на диапазоны – $I$3:$I$4<= $K$3:$K$4, $I$5>= $K$5).

Если есть требование целочисленности или неотрицательности неизвестных, его также нужно учесть.

3. Выбираем метод решения (для линейных задач).

4. Нажимаем Найти решение.

5. Найденное оптимальное решение находится в ячейках B6 и C6.

Скриншоты листа книги MS Excel 2010 с размещенными в нем данными для решения задачи оптимизации в двух режимах (отображения формул и результатов) показаны на рис. 6 и 7. Получить скриншот (копию экрана) можно с помощью буфера обмена нажатием клавиши PrintScreen (PrnScr) и выбором команды Вставить. В Windows 7 для аналогичного действия предусмотрен инструмент Ножницы. Переключение режима Показать формулы в MS Excel 2010 расположено на вкладке ленты Формулы.

Рис. 6. Данные для решения задачи в режиме отображения формул.

Рис.7. Данные для решения задачи в режиме отображения значений.

Вид окна режима Поиска решения с установленными параметрами и найденное решение показаны на рис. 8 и 9.

Рис. 8. Окно режима Поиска решения с установленными параметрами.

Рис. 9. Вид листа книги MS Excel с найденным решением задачи оптимизации.

 

Ответ: оптимальными значениям параметров задачи являются x₁=6 и x₂=1, целевая функция при заданных ограничениях имеет максимальное значение, равное 7.

 

 

Индивидуальные варианты задач по Теме 1.2 " Электронные таблицы.Решение оптимизационных задач в MS Excel ".

Задача 1.2.1.

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

при ограничениях: .

Вариант/ Параметры
с1			-1		-1	-2		-1
с2		-1			-2			-1									-10		-2	-1
a11			-1					-1	-3	-1				-3		-1	-1			-2
a12						-2		-2						-1	-1	-4			-2
b1								-2	-6					-9		-8
a21	-2	-3	-2	-3	-3	-2	-2	-2			-4	-5	-2	-1	-3		-1		-1
a22		-2	-3									-4		-2				-3	-2	-2
b2		-6	-6									-20		-8					-2	-8
a31	-2	-1		-1	-1	-1		-2			-1			-1
a32			-3				-2		-4	-2	-3	-1	-3	-6	-1	-2
b3											-9	-5		-12		-5
a41				-1						-1
a42							-1
b4				-2			-2			-2

 

Задача 1.2.2.

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

при ограничениях: .

Вариант/ Параметры
с1						-3	-2	-1		-2		-6			-4	-2
с2	-2		-1	-1			-2			-1	-13				-2		-2			-20
с3		-1			-1			-1		-1	-6						-10		-4	-5
с4		-1			-1	-1			-1						-1
a11							-2			-3	-1		-3			-1
a12	-1				-1			-1				-1		-2	-1	-1			-3	-5
a13		-7				-1			-1	-1	-3	-1	-1	-3			-1
a14		-1	-3	-1				-1						-1	-2
b1											-1	-2	-5	-1
a21			-1					-1					-1	-1		-1			-1
a22	-3		-2			-2			-1		-2	-1	-1	-3			-2			-4
a23		-1			-3								-2	-1	-1		-2		-1	-1
a24	-1			-1								-1
b2											-1	-1	-10			-6	-1