Лекция 5. Решение оптимизационных задач в электронной таблице Excel

Цель: Рассмотреть систематизированные основы знаний по использования электронной таблицы Excel для решение оптимизационных задач.

5.1. Основные этапы решения оптимизационных задач в Excel

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

1. Разработка математической модели.

2. Перенос модель в электронную таблицу.

3. Решение оптимизационной задач с помощь программы надстройки ПОИСК РЕШЕНИЯ

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

Этап 1. Разработка математической модели.

Пример 1 (задача о смесях). Стандартом предусмотрено, что октановое число автомобильного бензина А-76 должно быть не ниже 76, а содержание серы в нем – не более 0,3%. Для изготовления такого бензина на заводе используется смесь из четырех компонентов. Данные о ресурсах смешиваемых компонентов, их себестоимости и их октановом числе, а также о содержании серы приведены в таблице

Характеристика	Компонент автомобильного бензина
	№ 1	№2	№ 3	№4
Октановое число	68	72	80	90
Содержание серы, %	0,35	0,35	0,3	0,2
Ресурсы, т	700	600	500	300
Себестоимость, ден.ед./т	40	45	60	90

Требуется определить, сколько тонн каждого компонента следует использовать для получения 1000 т автомобильного бензина А-76, чтобы его себестоимость была минимальной.

Решение. Для решения этой задачи сформулируем ее экономико-математическую модель, т.е. сформулируем задачу математически. Введем необходимые обозначения: пусть x_j (j = 1,2,3,4) – количество в смеси компонента с номером j. С учетом этих обозначений имеем задачу (критерий оптимальности – «минимум себестоимости»):

min f() = 40x₁ + 45x2 + 60x₃ + 90x₄,

x₁ + х₂ + х₃ + x₄ = 1000, (1)

68x₁ + 72x₂ + 80x₃ + 90x₄  76 • 1000, (2)

0,35x₁ + 0,35x₂ + 0,3x₃ + 0,2x₄ ≤ 0,3 • 1000, (3)

x₁  700,

x₂  600,

x₃  500,

x₄  300,

x_j  0, j = 1,2,3,4.

Функциональное ограничение (1) отражает необходимость получения заданного количества смеси (1 000 т), (2) и (3) – ограничения по октановому числу и содержанию серы в смеси, остальные – ограничения на имеющиеся объемы соответствующих ресурсов (компонентов). Прямые ограничения очевидны, но принципиально важны для выбора метода решения.

Полученная математическая задача – задача линейного программирования.

Этап 2. Перенос модель в электронную таблицу.

Такой перенос может быть реализован в виде последовательности следующих 5 шагов.

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

2. Зарезервируйте отдельную ячейку для каждой независимой переменной алгебраической модели.

Для рассматриваемой задачи предлагается следующий вид таблицы данных:

3. Заполните таблицу исходными данными (значениями параметров и знаками ограничений):

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

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

Этап 3. Решение оптимизационной задач с помощь программы надстройки ПОИСК РЕШЕНИЯ

Программа ПОИСК РЕШЕНИЯ используется для решения задач линейного и нелинейного программирования.

Прежде всего следует заметить, что программа ПОИСК РЕШЕНИЯ оперирует с тремя основными компонентами построенной в ЭТ оптимизируемой модели:

• ячейкой, содержащей целевую функцию задачи (ячейка G5);

• изменяемыми ячейками, содержащими независимые переменные (С4:F4);

• ячейками, содержащими левые части ограничений на имеющиеся ресурсы, простые ограничения на независимые переменные и знаки ограничений (в Табл. 7.12 это - ячейки G10:I23).

Постановка задачи осуществляется в диалоговом окне Поиск решения, где пользователю предлагается указать ряд параметров (см. Рис. 7.1).

Рис. 7.1. Диалоговое окно "Поиск решения"

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

При нажатии кнопки Предположить EXCEL выделяет область ячеек, на которые прямо или косвенно ссылается целевая ячейка. Для того, чтобы задать ограничения, следует нажать на кнопку Добавить. В результате откроется следующее диалоговое окно - Добавить ограничение (см. Рис. 7.2). В левом поле этого диалогового окна следует указать адрес ячейки, содержимое которой должно удовлетворять заданному ограничению.

Рис. 7. 2. Диалоговое окно "Добавить ограничение"

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

В нашем примере необходимо задать таким образом 11 ограничений.

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

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

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

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

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

Рис. 7. 3. Диалоговое окно "Параметры поиска решения"

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

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

Рис. 7.4. Диалоговое окно "Результаты поиска решения"

Если установлена опция Восстановить исходные значения и не задано составление отчета, то найденные значения будут удалены.

Найденные значения могут быть также сохранены как сценарий.

При задании режима составления отчета следует выбрать тип отчета в соответствующем поле.

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

Итак, мы получили результат: программа определила значения объемов производства для каждого вида продукции и соответствующее значение целевой функции, выражающее получаемую при этом прибыль (см. Табл. 7.13).

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