Команда меню Поиск решения

В Microsoft Excel и Quattro уже давно существуют средства оптимизации. В состав Excel входит инструмент для нахождения экстремума функций — команда Поиск решения.

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

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

В процедуре поиска решения Microsoft Excel используется алгоритм нелинейной оптимизации Generalized Reduced Gradient (GRG2), разработанный Леоном Ласдоном (Leon Lasdon, University of Texas at Austin) и Аланом Уореном (Allan Waren, Cleveland State University).

Алгоритмы симплексного метода и метода ветвей и границ для решения линейных и целочисленных задач с ограничениями разработаны Джоном Уотсоном (John Watson) и Деном Филстра (Dan Fylstra) из Frontline Systems, Inc.

Рассмотрим использование команды Поиск решения на примере классической транспортной задачи. Пусть в трех пунктах имеется по a_i(j=1, 2, 3) тонн груза, которые все надо доставить в три пункта назначения поb_j(j=1, 2, 3) тонн груза. Стоимость доставки из пунктаiв пунктjобозначимc_ij, а величину груза перевозимого из пунктаiв пунктjобозначимx_ij.

Откроем новую книгу в Microsoft Excel. Назовем ее Transportation. Создадим модель на листе Лист1. Разместим вектор a_iв диапазоне $E$2:$E$4, векторb_jв диапазоне $B$1:$D$1, матрицу в диапазоне $B$6:$D$8, а для переменных модели отведем диапазон $B$2:$D$4. Заполним вектора и матрицы, как показано на рис. 4.20.. Переменным модели пока присвоим произвольные значения.

Заполним окно команды Поиск решения (Solver) как показано на рис. 4.20. В строке формул видна формула, расположенная в целевой ячейке, ограничения видны в поле Ограничения (SubjecttotheConstraints).

Если параметры команды оставить, как показано на рис. 4.21, то решение не будет найдено, о чем и появится сообщение, см. рис. 4.22. Следует включить флажки Линейная модель и Неотрицательные значения. Тогда решение будет найдено, о чем появится сообщение. Найденное решение можно сохранить на листе, см. рис. 4.23. Также можно получить отчет о найденном решении, см. рис. 4.24.

Рис. 4.20. Транспортная задача

Рис. 4.21. Диалоговое окно Параметры надстройки Поиск решения

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

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

Рис. 4.24. Отчет Результаты Поиска решения

Если команда Поиск решения отсутствует в меню Сервис, следует установить надстройку «Поиск решения», используя команду Надстройки в меню Сервис.

Рис. 4.25. Установка надстройки «Поиск решения»

Если надстройки «Поиск решения» нет в окне Доступные надстройки, то нажмите кнопку Обзор, чтобы найти надстройку. Если найти надстройку не удалось, то скорее всего придется переустановить Microsoft Excel, добавив необходимые компоненты.

В поставку Microsoft Excel входит SOLVSAMP.XLSкнига примеров по использованию надстройки «Поиск решения». Во всех приводимых в этой книге примерах обе части ограничений представляют собой простейшие формулы. Левая часть ограничения, как того требует Microsoft Excel, содержит ссылку на ячейку или диапазон. Правая часть состоит из константы или ссылки на ячейку или диапазон. Ни в одном примере в качестве правой части ограничения не используется формула, возвращающая численное значение. Ни в одном примере в ограничениях не используются функции. По-видимому, если возникает необходимость в ограничениях, содержащих вычисления, то вычисления желательно проводить в ячейках листа электронной таблицы. В задаваемых при Поиске решения ограничениях следует использовать ссылки на те ячейки, где собственно и проводятся вычисления.