Использование надстройки «Поиск решения» Excel для решения задач оптимизации

Функциональность надстройки «Поиск решения»

Эта надстройка предназначена для решения задач оптимизации.

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

При этом выражение (формула) целевой функции размещается в одной из ячеек таблицы Excel, которая получает название «целевая ячейка». Напомним, что в русскоязычной документации и литературе сложилась традиция называть математические выражения формулами.

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

Каким образом представляются ограничения? В ячейках той же таблицы размещаются функции ограничений. Содержимым этих ячеек являются формулы, содержащие ссылки на влияющие ячейки, т. е. на ячейки всё тех же искомых переменных. Ограничения формируется с помощью кнопок «Добавить», «Изменить», «Удалить» окна «Поиск решения». При нажатии на кнопку «Добавить» появляется диалоговое окно «Добавление ограничения», с помощью которого и устанавливаются отношения между функциями ограничений и константами задачи. Формируемые отношения отображаются в списке с надписью «Ограничения: ».

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

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

3.2 Начальные значения искомых переменных – специфика
процедуры поиска решения

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

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

В иностранной литературе начальные значения искомых переменных имеют образное название – Guess Values – предполагаемые (угаданные) значения. Оно очень хорошо передаёт смысл начальных значений искомых переменных.

Естественно, возникает вопрос: а как задавать начальные значения искомых переменных? К счастью современные алгоритмы поиска решения настолько хороши, что практически снимают этот вопрос, поскольку допускают произвольные значения искомых переменных. Ну, конечно, здравый-то смысл нарушать не следует. А если подходить серьёзно, то начальные значения следует подбирать таким образом, чтобы ограничения задачи были выполнены, либо полностью, либо с небольшими нарушениями. Метод же здесь единственный – проб и ошибок. Как надоест пробовать, так можно и остановиться, даже если не все ограничения выполнены.

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

3.3 Способ использования файла Smpls.xls с образцами решения
задач

Способ проще некуда: открываешь книгу Excel, изучаешь элементы задачи и решаешь её.

Прежде всего, рекомендуем создать копию файла Smpls.xls, и работать именно с копией, – чтобы иметь возможность «начать сначала», в случае существенных изменений содержимого файла в процессе вычислений.

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

Вам остаётся только выбирать команду «Поиск решения» (в Excel 2003 это в меню «Сервис») и в появившемся окне нажимать на кнопку выполнить.

Все элементы окна «Поиск решения» просты по смыслу и легки в использовании (кроме кнопки «Предположить», но на неё не обращайте внимания).

Элементы окна «Поиск решения»

Установить целевую ячейку

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

Равно

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

Изменяя ячейки

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

Предположить

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

Ограничения

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

Добавить

Служит для отображения диалогового окна «Добавить ограничение».

Изменить

Служит для отображения диалоговое окна Изменить ограничение.

Удалить

Служит для снятия указанного ограничения.

Выполнить

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

Закрыть

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

Параметры

Служит для отображения диалогового окна «Параметры поиска решения», в котором можно загрузить или сохранить оптимизируемую модель и указать предусмотренные варианты поиска решения.

Восстановить

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

Авторы надстройки «Поиск решения»

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

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

Frontline Systems, Inc.

P.O. Box 4288

Incline Village, NV 89450-4288

(775) 831-0300

Адрес в Интернете: http: //www.frontsys.com

Электронная почта: info@frontsys.com

Авторские права на исполняемый код надстройки Microsoft Excel поиска решения версий 1990, 1991 и 1992 годов принадлежат Frontline Systems, Inc. Авторские права на версию 1989 года принадлежат Optimal Methods, Inc.

Пояснения к решаемым задачам

Поговорим об очевидном, потому что очевидное очевидно не сразу.

Настройка надстройки

Если вы не можете найти в системе меню Excel пункт «Поиск решения», то не расстраивайтесь. Если вы используете Microsoft Office Excel 2003, то вам повезло: идите в пункт меню «Сервис», и далее выбирайте пункт «Надстройки …» (этот-то пункт уж точно будет присутствовать). После этого появится диалоговое окно «Надстройки». В нём-то и поставьте галочку рядом со строкой «Поиск решения». После это давите не кнопку OK, и желаемый пункт «Поиск решения» появится в пункте меню «Сервис».

Если вы используете Microsoft Office Excel 2007 и выше, то вам повезло ещё больше: вы получаете шанс получше освоить современный (видимо, для оригиналов придуманный) интерфейс от Microsoft. А чтобы не лишать вас возможности получить удовольствие в полном объёме, я не буду описывать правило подключения надстройки «Поиск решения» по шагам, а только скажу, как это можно сделать: наберите в строке подсказки «Надстройки Поиск решения», и далее следуйте полученным инструкциям.

Задача «Планирование производства»

Суть задачи

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

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

Целевой функцией является ожидаемый доход – суммарная цена всех видов продукции, выпущенной в течение планового промежутка времени:
, где – доход от продукции -го вида, т. е. цена всего объёма выпущенной продукции -го вида, вычисляемая по формуле , , где – цена единицы продукции -го вида.

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

Целью планирования является максимизация целевой функции.

Константами задачи являются:

1) запасы каждого вида деталей на складе; предполагается, что в планируемом промежутке времени количество запасов не изменяется; математически совокупность запасов представляет собой вектор , где – количество видов комплектующих деталей, используемых в производстве, в Excel предстá вим столбцом данных;

2) нормы расхода комплектующих деталей на единицу каждого вида продукции; математически нормы расхода представляет собой матрицу , где – количество деталей -го вида, используемых для изготовления единицы продукции -го вида; в Excel предстá вим блоком (прямоугольником) данных;

3) цены на единицу каждого вида продукции; математически цены представляют собой вектор .

Вспомогательные функции задачи в текущем рассмотрении следующие:

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

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

Ограничения в рассматриваемом варианте задачи планирования имеют следующую семантику:

· количества деталей , использованных в процессе производства, не должны превышать запасы этих деталей на складе предприятия: , ;

· производимые объёмы продукции, конечно же, должны иметь положительные значения: , ( ).

⇐ Предыдущая 123 Следующая ⇒