6 Технология решения линейной оптимизационной задачи в Excel

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

Задачи, решаемые с помощью оптимизатора, имеют три характерных признака: наличие (1) целевой ячейки, (2) изменяемых ячеек, (3) ограничивающих ячеек.

• Имеется единственная целевая ячейка. В нее пользователь должен ввести формулу, указав позднее в программном диалоге какой экстремум необходим (максимум или минимум). После завершения построения модели и инициализации расчета программа автоматически должна добиться для этой ячейки экстремального результата. Формула будет вычислять целевой показатель, например, чистую прибыль или издержки, при автоматическом варьировании значений других (изменяемых) ячеек. Для целевой ячейки в программном диалоге (а не в самой ячейке) можно установить и конкретное целевое значение, если для его достижения необходимо будет подбирать значения взаимосвязанных с ней ячеек. Иными словами, возможно решение обратных задач типа "Необходим миллион прибыли! Каким образом (how can) мы можем этого добиться?". Первый сценарий: сколько ресурса для этого потребуется при тех же ценах, или (второй сценарий) какой для этого должна быть цена продукции при тех же ресурсах, или (третий сценарий) какой должна быть цена ресурса при той же цене продукции? Задачи такого типа относят к how can-анализу.

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

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

Технология решения:

1) подготовительный (подготовка табличной модели до обращения к диалоговому окну оптимизатора, ввод данных и формул);

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

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

Инструментальные средства Excel

Программа Поиск решений (в оригинале Excel Solver) – дополнительная надстройка табличного процессора MS Excel, которая предназначена для решения определенных систем уравнений, линейных та нелинейных задач оптимизации, используется с 1991 года.

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

• количество неизвестных (decision variable) – 200;

• количество формульных ограничений (explicit constraint) на неизвестные – 100;

• количество предельных условий (simple constraint) на неизвестные – 400.

Общее же количество всех ячеек, занятых под описание оптимизационной проблемы, в программе Excel не может быть более 1000. Разработчик программы Solver компания Frontline System уже давно специализируется на разработке мощных и удобных способов оптимизации, встроенных в среду популярных табличных процессоров разнообразных фирм-производителей (MS Excel Solver, Adobe Quattro Pro, Lotus 1-2-3).

Высокая эффективность их применения объясняется интеграциею программы оптимизации и табличного бизнес-документа. Благодаря мировой популярности табличного процессора MS Excel встроенная в его среду программа Solver есть наиболее распространенным инструментом для поиска оптимальных решений в сфере современного бизнеса.

По умолчанию в Excel надстройка Поиск решения отключена. Чтобы активизировать ее в Excel 2007, щелкните значок Кнопка Microsoft Office , щелкните Параметры Excel, а затем выберите категорию Надстройки. В поле Управление выберите значение Надстройки Excel и нажмите кнопку Перейти. В поле Доступные надстройки установите флажок рядом с пунктом Поиск решения и нажмите кнопку ОК.

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

Инструментальные средства оптимизатора Excel представлены тремя диалоговыми окнами и их элементами (окнами, кнопками, переключателями, прокручиваемыми списками):

• Solver Parameters (Поиск решения или Параметры оптимизатора); Solver Parameters имеет вложенное диалоговое окно Options (Параметры поиска решения) и Add Constaint (Добавить ограничения);

• Solver Results (Результаты поиска решения).

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

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

Ниже даны краткие пояснения главных опций диалогового окна оптимизатора.

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

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

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

• ячейки ограничения (левая часть формулы);

• оператор отношения (средняя часть):

меньше или равно (<=),

равно (=),

больше или равно (>=),

целое (inf);

• значение ограничения (правая часть формулы), где может быть число или адрес ячейки. В случае использования адреса, в ячейке третьей части ограничения может быть только число (не формула).

Для продолжения ввода ограничений активизируется кнопка Add, которая очищает окно от переданной информации, т. е. подготавливает его к вводу нового ограничения. После ввода последнего ограничения следует активизировать кнопку ОК, которая возвращает вид основного диалогового окна Solver, где отражен прокручиваемый список всех введенных ограничений.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В средствах Options существует очень ценная для практиков возможность сохранения конкретной оптимизационной модели (Save model — Сохранить модель), а также возможность вызова (загрузки) ранее сохраненной модели (Load model - Загрузить модель). Таким способом удобно сохранять описание регулярно используемой оптимизационной проблемы, в состав которой входят все задействованные пользователем ячейки таблицы, формулы и ограничения. (Описание одной проблемы может занимать максимум 1000 ячеек.) Можно создавать библиотеку описаний оптимизационных проблем. Например, если вы ежемесячно оптимизируете программу производства по пяти разным табличным моделям, то вам важно сохранить их все после первого же решения, чтобы каждый месяц не описывать пять проблем заново, а вызывать модель и изменять в ней некоторые исходные данные или ограничения. Описание последней решенной проблемы всегда сохраняется автоматически, одновременно с сохранением электронной таблицы.

Reset - Отменить. Вернуть параметры меню Options к установкам по умолчанию, если вы их изменяли. (Внимание: различайте Restore и Reset.)

Restore - Восстановить. Restore восстанавливает исходное значение всех ячеек в табличной модели, т. е. существовавшее до запуска решения.

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

Cancel - Выход. Прервать диалог с оптимизатором.

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