Решение задач оптимизации с помощью MS Excel

В Excel 2003 и ниже выберите команду Сервис/Надстройки, в появившемся диалоговом окне Надстройки установите флажок Поиск решения и щелкните на кнопке ОК. Если вслед за этим на экране появится диалоговое окно с предложением подтвердить ваши намерения, щелкните на кнопке Да. (Возможно, вам понадобится установочный компакт-диск Office).

Рисунок 2 - Наглядная таблица действий

Процедура поиска решения:

1. создать таблицу с формулами, которые устанавливают связи между ячейками;
2. выделить целевую ячейку, которая должна принять необходимое значение, и выберите команду:
3. установить переключатели Equal To (Равной), задающие значение целевой ячейки, — Мах (максимальному значению), Min (минимальному значению) или Value of (значению). В последнем случае введите значение в поле справа;
4. указать в поле By Changing Cells (Изменяя ячейки), в каких ячейках программа должна изменять значения в поисках оптимального результата;
5. создать ограничения в списке Subject to the Constraints (Ограничения). Для этого щелкните на кнопке Add (Добавить) и в диалоговом окне Add Constraint (Добавление ограничения) определите ограничение;

Рисунок 3 - Диалоговое окно надстройки Поиск решения

6. щелкнуть на кнопке на кнопке Options (Параметры), и в появившемся окне установите переключатель Неотрицательные значения (если переменные должны быть позитивными числами), Линейная модель (если задача, которую вы решаете, относится к линейным моделям);
7. щелкнув на кнопке Solver (Выполнить), запустить процесс поиска решений;

Рисунок 4 - Диалоговое окно Результаты поиска решений

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

Максимальное время - служит для ограничения времени, отпущенного на поиск решения задачи. В этом поле можно ввести время в секундах, не превышающее 32 767 (примерно девять часов); значение 100, используемое по умолчанию.

Рисунок 5 - Диалоговое окно Параметры поиска решений

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

Относительная погрешность - определяет точность вычислений. Чем меньше значение этого параметра, тем выше точность вычислений.

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

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

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

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

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

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

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

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

Оценка линейная - выберите этот переключатель для работы с линейной моделью.

Оценка квадратичная - выберите этот переключатель для работы с нелинейной моделью.

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

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

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

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

1.3 Использование сценариев в Excel

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

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

Диспетчер сценариев

Для создания нового сценария или работы с ранее созданными сценариями предназначено диалоговое окно Диспетчер сценариев, которое открывается с помощью команды Сервис - Сценарии.

Диалоговое  окно Диспетчер сценариев имеет  следующие элементы управления.

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

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

Создание нового сценария

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

Диалоговое  окно Добавление сценария содержит следующие  элементы управления:

• в поле ввода Название сценария необходимо ввести название сценария.
• в поле ввода Изменяемые ячейки вводятся адреса ячеек, содержащих изменяемые значения, которые будут сохранены в сценарии.
• в поле ввода Примечание вы вводите комментарии к создаваемому сценарию. Если вы не введете комментарии, то Excel автоматически создаст примечание, содержащее имя создателя сценария (по зарегистрированному имени пользователя компьютера) и дату его создания.
• если установить флажок запретить изменения, который находится в области Защита диалогового окна, то изменяемые значения в сценарии будут защищены от изменений при условии, что будет защищен рабочий лист. Отменить защиту можно в диалоговом окне Изменение сценария, сняв флажок запретить подразделе «Защита сценариев от изменений».

Если  установить флажок скрыть, то после установки защиты рабочего листа название данного сценария не будет отображаться в списке Сценарии диалогового окна Диспетчер сценариев.

После того как в диалоговом окне Добавление сценария щелкнуть на кнопке ОК, откроется следующее диалоговое окно Значения ячеек сценария, показанное. Это окно имеет по одному полю ввода для каждого изменяемого значения, где можно увидеть и при необходимости изменить эти значения.

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

1. выбрать команду Сервис - Сценарии.
2. в открывшемся диалоговом окне Диспетчер сценариев щелкнуть на кнопке Добавить.
3. в диалоговом окне Добавление сценария ввести название сценария в поле ввода Название сценария.
4. в поле ввода Изменяемые ячейки ввести адреса изменяемых ячеек (вручную или путем выделения их непосредственно на рабочем листе).
5. щелкнуть в диалоговом окне Добавление сценария на кнопке ОК.
6. в открывшемся диалоговом окне Значения ячеек сценария ввести значения для изменяемых ячеек.

Щелкнуть в диалоговом окне Значения ячеек сценария на кнопке Добавить, чтобы создать сценарий и вернуться в диалоговое окно Добавление сценария, либо на кнопке ОК, чтобы создать сценарий и вернуться в диалоговое окно Диспетчер сценариев

Работа со сценариями

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

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

Чтобы удалить  сценарий из текущего рабочего листа, в открытом диалоговом окне Диспетчер сценариев в списке Сценарии выберать сценарий, который необходимо удалить, и щелкните на кнопке Удалить [2].

1.4 Применение оптимизации

Задача  оптимизации кормового рациона:

На ферме  в качестве корма для животных используются два продукта - M и N.

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

Подсчитано, что  в 1 кг каждого продукта содержится:

• в продукте M - 150 ккалорий и 14 единиц жира;
• в продукте N - 200 ккалорий и 4 единицы жира.

Задача: разработать максимально дешевый рацион откорма животных, отвечающий этим условиям, если стоимость 1 кг продукта М составляет 1,5 руб., а 1 кг продукта N - 2,3 руб.

Экономико-математическая постановка задачи:

x₁ - количество продукта М в рационе; x₂ - количество продукта N в рационе.

• ограничение по количеству ккалорий:150x₁+200x₂>=200;
• ограничение по количеству жира:14x₁+4x₂<=14;
• неотрицательность переменных: x₁>=0; x₂>=0.