Технология решения задач линейного программирования с помощью Поиска решений приложения Excel (стр. 2 из 5)

Поле Сходимость результатов поиска решения применяется только к нелинейным задачам. Когда относительное изменение значения в целевой ячейке за последние пять итераций становится меньше числа, указанного в поле Сходимость, поиск прекращается. Условием сходимости служит дробь из интервала от 0 (нуля) до 1. Лучшую сходимость характеризует большее количество десятичных знаков, например, 0,0001 – это меньшее относительное изменение, чем 0,01. Чем меньше его значение, тем выше точность результатов. Лучшая сходимость требует больше времени на поиск оптимального решения.

Флажок Линейная модель служит для ускорения поиска решения линейной задачи оптимизации или линейной аппроксимации нелинейной задачи.

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

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

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

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

Линейная служит для использования линейной экстраполяции вдоль касательного вектора.

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

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

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

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

Кнопки Метод поиска служат для выбора алгоритма оптимизации (метод Ньютона или сопряжённых градиентов).

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

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

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

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

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

Сохранение и загрузка модели

1. Сохранение модели оптимизации

1. В меню Сервис выберите команду Поиск решения.
2. Нажмите кнопку Параметры.
3. Нажмите кнопку Сохранить модель. Появляется окно Сохранить модель, рис. 4.
4. В поле Задайте область модели введите ссылку на верхнюю ячейку столбца, в котором хотите разместить модель оптимизации.

Рис. 4. Диалоговое окно Сохранить модель.

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

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

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

2. Загрузка модели оптимизации

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

1 В меню Сервис выберите команду Поиск решения.

2. Нажмите кнопку Параметры.

3. Нажмите кнопку Загрузить модель. Появляется окно, аналогичное окну Сохранить модель.

4. Введите ссылку на область модели.

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

Вычисления и результаты решения задачи

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

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

Чтобы прервать поиск решения, нажмите клавишу ESC. Microsoft Excel пересчитает лист с учётом найденных значений влияющих ячеек.

По окончании счёта появляется диалоговое окно Результаты поиска решения, рис. 5.

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

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

Поле Тип отчёта служит для указания типа отчёта, размещаемого на отдельном листе книги.

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

Отчёт Устойчивость используется для создания отчёта, содержащего сведения о чувствительности решения к малым изменениям в формуле модели или в формулах ограничений. Такой отчёт не создаётся для моделей, значения в которых ограничены множеством целых чисел. В случае нелинейных моделей отчёт содержит данные для градиентов и множителей Лагранжа. В отчёт по нелинейным моделям включаются ограниченные затраты, фиктивные цены, а также диапазоны ограничений.

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

К сожалению, эти отчёты очень неудобны. Они перегружены плохо читаемыми абсолютными ссылками со знаками доллара. Желает лучшего и перевод с английского на русский.

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

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

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

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

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

На экране появится диалоговое окно Текущее состояние поиска решения, рис. 6, а влияющие ячейки листа изменят свои значения.

Чтобы остановить поиск решения и вывести на экран диалоговое окно Результаты поиска решения, нажмите кнопку Стоп.

Рис.6. Диалоговое окно Текущее состояние поиска решения.

Чтобы выполнить следующую итерацию и просмотреть её результаты, нажмите кнопку Продолжить.

Возникающие проблемы и сообщения процедуры поиска решения

Оптимальное решение не найдено

Поиск решения может остановиться до достижения оптимального решения по следующим причинам.

Пользователь прервал процесс поиска.

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