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

Способы представления сетки в Еxcel:

                    Матрица смежности – квадратная матрица связи типа «каждый-с-каждым» размером n?n, де n – число узлов. Элемент такой матрицы принимает не нулевое значение (расстояние, затраты), если существует дуга между узлами, или 0 в противоположном случае. Эта матрица полностью определяет структуру сетки. Для анализа и расчётов используется аппарат матричной и линейной алгебры. Этот способ используется при решении классической транспортной задачи, задачи коммивояжера, то есть там, где количество дуг значительно превышает количество узлов. Например, для описания графа, который состоит из 15 узлов и, соответственно, 225 дуг, лучше применить матрицу для компактной записи данных.

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

Для сетевых моделей оптимизации фундаментальным есть принцип сохранения потока в любом узле (экономисты называют это балансом), а именно: сума потоков на выходе узла равно суме потоков на его входе плюс потенциал узла (+предложение/ -спрос).

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

А) Кратчайший путь

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

Задана сеть у виде ориентированного графа с 11 узлов и 18 дуг. Нужно найти кратчайший путь от узла-источника (Киев) к узлу-стоку (Вена). Начальные данные, ограничение и результат представим в виде двух строк: узлов с 11 элементов и дуг с 18 элементов.

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

1. Найти вектор дуг (если дуга равна 1, то она входит в кратчайший путь, если 0 – не входит), такой, чтобы:
2. Общая длина пути = Длина*Дуга - min
3. При условии сохранения балансу потоков для каждого узла: для узла-источника – Выходят – Входят = 1; для промежуточных узлов - Выходят – Входят = 0; для узла –стока - Выходят – Входят = -1; все неизвестные больше нуля.

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

В таблице для дуг определяем диапазон для неизвестных (Дуга) и вычисляем значение целевой ячейки (Об_длина) за формулой =СУММПРОИЗВ(Дуга; Длина).

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

Для вычисления потока в узлах используют функцию вычисления сумы величин, координаты которых удовлетворяют определенные условия (то есть, если определенная величина принадлежит соответствующему множеству). В Excel такую процедуру исполняет функция =СУММЕСЛИ(). Например, сума входящих потоков узла определяется за формулой =СУММЕСЛИ(Все концы дуг; узел; потоки), то есть, суммируются потоки по тем дугам, концы которых совпадают с поточным узлом.

За формулой =СУММЕСЛИ(Все начала дуг; узел; потоки) суммируют выходящие потоки.

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

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

Кратчайший  путь с Киева в Вену 11, 5, если мы будим ехать таким путем: Киев-Минск-Талин-Копенгагин-Париж-Вена.

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

Теневые цены для узлов определяют частичные кратчайшие пути от узла-источника (Киев) ко всем остальным узлам, включая узел-сток (Вена). Таким образом, теневые цены этой задачи соответствует сетевой задачи про оптимальное покрытие сетки. Это результат может быть полезным для транспортного предприятия, где нужно найти кратчайшие маршруты от начального ко всем остальным определенного региона.[3]

3. Динамические.

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

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

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

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

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

А) Замена оборудования

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

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

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

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

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

1. Найти такой план замены, чтобы
2. Общие затраты = Норма * План - min
3. При ограничениях: Сума по строкам первого года = 1 (Покупка в первый год); Сума по столбцам последнего года = 1 (эксплуатация до последнего года); Сума по строкам промежуточных годов = Сума про столбцам промежуточных годов; План >= 0.

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

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

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

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

Оптимальный план: машину покупают в начале 1-го года и эксплуатируют ее до 3 года, в 3-ем году замена и эксплуатация на протяжении 2-ох лет, минимальные общие затраты составляют 6,2 д. ед.

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

Теневые цены ограничений указывают на варианты снижения целевой ячейки.[4]

4. Нелинейные модели.

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

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

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

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

ІІІ. Задачи нелинейного программирования общего вида, где достигается локальный оптимум, среди которых ищут глобальный оптимум.

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

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

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

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

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

А) План производства

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