Решение задач оптимизации средствами программ Excel

И это правильно, ведь линейное программирование впервые возникло в Пентагоне (Министерстве обороны США), где работал его изобретатель Дж. Данциг, а исследование операций, что возникло во время Второй мировой войны, понятно, касалось в первую очередь военных операций. Вне сомнения, много научных идей в те годы получали дополнительную поддержку, если у них были заинтересованные военные круги, и линейное программирование — один из примеров такого подхода к развитию в СССР (и не только) научных исследований.

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

Никто из наших военных специалистов (среди них были инженеры, которые очень неплохо знали математику; некоторые из них были взяты в армию по окончании математических и физических факультетов), обычно, никогда не слышал о работах Л.В. Канторовича и это не странно - запрещение действовало безотказно. В 1957-1958 гг. они лишь начинали знакомиться с переводами американской литературы из линейного программирования и ведомости о работах Канторовича от тех, кто об этом знал, были откровением. (Хотя запрещение относительно самого Канторовича на то время как будто было снято, в условиях "холодной войны" между СССР и США его научные результаты определенное время оставались секретными и недоступными даже для наших специалистов. Именно поэтому о работе Канторовича из математической оптимизации, опубликованной еще в 1939 г. в малоизвестном университетском сборнике, в США узнали достаточно поздно.

То же с легализацией у нас линейного программирования возник и длился лет двадцать научный спор о приоритете открытия линейного программирования, но справедливость восторжествовала - Л. В. Канторович заслуженно стал Нобелевским лауреатом из экономики, хотя «отцом линейного программирования» в США по традиции называют Дж. Данцига.

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

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

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

Глава 2. Средства Excel

1. Создание таблиц.

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

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

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

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

Имеем классическую задачу когда фирма производит два вида продукции (товар А и товар Б) по определенной цене, на их производство требуется 4 вида ресурсов (ресурс 1, ресурс 2, ресурс 3, ресурс 4), которые есть в наличие на фирме в определенном количестве (Запас), также имеется информация сколько нужно каждого ресурса на производство единицы продукции, соответственно товара А и товара Б. Нужно найти,  то количество товара А и товара Б,  которое максимизирует доход (выручку) (см. рис.).

Далее нам надо сделать взаимосвязи между ограничениями, планом и целевой функцией. Для этого мы строим дополнительный столбец (Использовано), в котором вводим формулу СУММПРОИЗВ (Норма; План). Норма - это затраты определенного ресурса на производство единицы продукции товара А и Б, а План – количество продукции, которое мы ищем. В ячейки Доход вводим формулу СУММПРОИЗВ(Цена; План). Таким образом мы заполнили формулами столбец Использовано и ячейку Доход. Так как план это переменные от которых зависит количество использованных ресурсов и доход, то ячейки с формулами напрямую зависят от данных, которые там появятся в результате поиска решений.

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

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

2. Поиск решения.

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

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

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

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

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

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

Разработчик программы 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).

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

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

2. Выделите целевую ячейку, которая должна принять необходимое значение, и выберите команду:

- В Excel 2007 Данные/Анализ/Поиск решения;

- В Excel 2003 и ниже Tools > Solver (Сервис > Поиск решения). Поле Set Target Cell (Установить целевую ячейку) открывшегося диалогового окна надстройки Solver (Поиск решения) будет содержать адрес целевой ячейки.

3. Установите переключатели Equal To (Равной), задающие значение целевой ячейки, — Мах (максимальному значению), Min (минимальному значению) или Value of (значению). В последнем случае введите значение в поле справа.

4. Укажите в поле By Changing Cells (Изменяя ячейки), в каких ячейках программа должна изменять значения в поисках оптимального результата.

5. Создайте ограничения в списке Subject to the Constraints (Ограничения). Для этого щелкните на кнопке Add (Добавить) и в диалоговом окне Add Constraint (Добавление ограничения) определите ограничение.

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

7. Щелкнув на кнопке Solver (Выполнить), запустите процесс поиска решения.

8. Когда появится диалоговое окно Solver Results (Результаты поиска решения), выберите переключатель Keep Solve Solution (Сохранить найденное решение) или Restore Original Values (Восстановить исходные значения).

9. Щелкните на кнопке ОК.

Параметры средства Поиск решения

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

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

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

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

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

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

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