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

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

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

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

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

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

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

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

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

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

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

3. Отчеты.

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

Отчеты бывают трех типов: по результатам (Answer), по устойчивости (Sensitivity), по пределам (Limit).

Тип выбирается по окончании поиска решений в диалоговом окне Результаты поиска решений (Solver results) в списке Отчеты (Reports). Можна выбрать сразу два или три типа с помощью мыши при нажатой клавиши <Ctrl>. Каждый отчет будет создан на отдельном рабочем листе.

Глава 3. Модели оптимизации

1. Линейные.

При решении оптимизационных задач с помощью Поиск решений (Solver) необходимо различать линейные и нелинейные модели. Под линейными понимаются модели, в которых связь между ограничениями на неизвестные и целевой ячейкой описывается линейными функциями. Общий вид линейной функции: Y=AX1+BX2+…+CXn, где A, B, C – константы, X1, X2, X3 – переменные, Y – результирующие значение.

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

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

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

Именно этот эффективный математический результат лежит в основе симплекс-метода – для поиска оптимума нужно в определенном порядке пересмотреть небольшое количество вершин, используя простой и эффективный алгоритм последовательного улучшения значения целевой функции. Мощные и эффективные средства линейного программирования определенным образом используются и в целочисленном программировании для решения более сложных задач оптимизации.
Если выражение для целевой ячейки и выражения для ограничений являются линейными, то можно применять быстрые и надежные методы поиска решения. Для использования именно линейных методов следует установить параметр Линейная модель (Assume Linear Model)  в окне Параметры поиска решений (Solver Options). Если этот параметр не установить, то даже для линейной задачи будут использоваться общие более медленные методы.

Ниже рассмотрены некоторые практические примеры задач оптимизации, которые относятся к линейным моделям:

А) Назначение на должность

Постановка задачи.

Название задачи и соответственной модели – о назначении (assignment problem) – непосредственно исходить от практической кадровой ситуации, когда претендентов нужно назначить на вакантные должности  наилучшим образом.

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

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

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

Особенность – наличие высокой оценки еще не гарантирует успех, поскольку целью оптимизации о назначении есть максимальный общий эффект.

Экономико-математическая модель.

1. Найти такую матрицу назначений, чтобы
2. Общий эффект=Матрица_оценок*Матрица_назначений - mах
3. При ограничениях: Назначено<=Всего_претендентов;

Занято=Всего_вакансий.

Матрица_назначений>=0.
Реализация в Excel.

Создаем таблицу с формулами, которые связывают план, ограничения и целевую функцию (Об_эффект):

                    в столбец Назначено вводим формулу сумы по сроках матрицы назначено;

                    в столбец Осталось вводим формулу Всего претендентов-Назначено;

                    в строку Занято вводим формулу сумы по столбцах матрицы назначено;

                    целевую ячейку заполняем формулой: =СУММПРОИЗВ (Матрица_оценок; Матрица_назначений).

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

Анализ результатов.

Оптимальный план назначений (смотри таблицу) обеспечивает общую эффективность 63.

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

Нормированные стоимости для нулевых назначений означают:

                    на сколько нужно увеличить оценку, чтобы можно было претендовать на назначение;

                    на сколько уменьшиться общая эффективность, если на должность будет назначен этот «невыгодный» претендент.[1]

Б) Расписание

Постановка задачи.

Расписание касается людей или машин, состояние которых на определенном этапе определяются двумя вариантами – человек в определенный день вышел/ не вышел, машина на определенной стадии работает/ не работает т. д. Соответственно, расписание имеет вид комбинаций типу 011100101.

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

Экономико-математическая модель.

1. Найти таблицу расписания такую, чтобы
2. Чтобы общие количество человек - min
3. При ограничениях: Всего задействованных человек = Потребностям в них; количество рабочих дней каждой работницы = 5, а также все неизвестные двоичного типа.

Реализация в Excel.

Создаем таблицу с формулами, которые связывают план, ограничения и целевую функцию (Количество):

                    в столбец Дни вводим формулу сумы по строкам матрицы расписания;

                    в строку Всего вводим формулу сумы по столбцам матрицы расписания;

                    в целевую ячейку Количество вводим формулу: =СУММ(Всего).

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

Анализ результатов.

В полученном результате видим, что данное расписание соответствует  нашим заданным ограничениям и при котором задействовано наименьшее количество работниц – это значит что наш план оптимальный.[2]

2. Сетевые модели.

В некоторых практических ситуациях для научности удобно использовать схемы, которые называют графами. Граф состоит с однородных объектов, которые называются узлами (англ. - node) и линий, которых называют дугами (англ. - arc), и связывают пары узлов между собой. Эти объекты – узлы и дуги – могут исполнять только роль схемы, определяя связи, в других случаях они имеют определенные характерные оценки, которые соответствуют поставленной задаче. В ориентированном графе эти линии имеют вид стрелок, указывая на ориентацию между узлами.

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

Ключевое слово «поток» определило в математическом программирование класс моделей потокового программирования (сетевого). Формирование этого направления припадает на 60-е года ХХ в. определено публикацией фундаментальной роботы Дж. Данцига, Л. Форда и Д. Фалкерсона. Оказалось, что если задачу можноа подать в графической форме в виде сетки, тогда можно с помощью довольно эффективных потоковых алгоритмов получить ее оптимальное решение на основе математических графов с меньшими затратами компьютерных ресурсов.

Ориентированный граф называют сеткой (network), где определяют:

                    внешний узел-источник, который имеет только выходящие дуги;

                    внешний узел-сток, который имеет только входящие дуги;

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

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

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

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