Решение задач математического программирования с использованием инструментов Microsoft Excel

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

В частности, для решения задач линейного программирования и анализа полученных результатов можно использовать модуль «Поиск решения» программы MS Excel пакета MS Office (в англоязычной версии MS Excel этот инструмент называется Solver).

В пакете MS Office версии до 2010 г. этот модуль доступен в меню «Сервис». Если он в меню отсутствует, нужно предварительно выбрать его в опции «Надстройки» меню «Сервис». В более поздних версиях MS Office для установки модуля необходимо в меню «Файл» (File) выбрать «Параметры» (Options), затем «Надстройки» (Add-Ins) и «Надстройки Excel» (ExcelAdd Ins), нажать на кнопку «Перейти» (Go) и в открывшемся диалоговом окне отметить «Поиск решения» (Solver). После этого модуль будет доступен в меню.

«Данные» {Data). Особенности и последовательность действий по применению инструмента «Поиск решения» рассмотрим на простом примере.

Пример 2.2. Агропромышленное предприятие владеет 1000 га пашни, 15 000 чел.-дней трудовых ресурсов, 6000 машино-смсн ресурса механизированного труда. Предполагается возделывание картофеля, зерновых и овощей с условием получения максимума товарной продукции в денежном выражении. Основные производственно-хозяйственные показатели для решения задачи приведены в табл. 2.2.

Таблица 2.2

Исходные данные для примера 2.2.

Решение. Формализуем поставленную задачу.

Искомые переменные: х_{ — площадь иод картофелем, га; х₂ — площадь иод зерновыми, га; х₃ — площадь под овощами, га.

Целевая функция:

Ограничения:

Решение в MS Excel

Рассмотрим поэтапное решение поставленной задачи в MS ЕхсеР.

Этап 1. Ввод данных.

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

В рассматриваемом примере созданная форма предполагает, что значения переменных xl, х2, хЗ будут заноситься в ячейки С4, С5, С6 соответственно; в ячейке С8 указывается вид целевой функции; в ячейках диапазона С11: С13 указываются левые части ограничений, а диапазона D11: D13 — правые части выражений для ограничений.

1.2. Ввод исходных данных и функциональных зависимостей в созданную форму. В соответствующие ячейки заносятся числовые данные и функциональные зависимости. Например, в ячейки С4, С5, С6 могут вводиться ориентировочные начальные значения площадей под соответствующие культуры (так как^[1]

в таблице MS Excel незаполненные ячейки считаются имеющими нулевое значение, то начальные значения переменных в случае решения линейных задач можно не вводить). В ячейке С8 должен быть указан вид целевой функции. Для нашего примера в ячейку С8 вводится следующее выражение:

В ячейках С11: С13 указываются левые части ограничений, т. е. для ячейки СИ: = С4 + С5 + С6; для ячейки С12: = б * С4 + С5 + 9,5 * С6; для ячейки С13: = 9 * С4 + 7 * С5 + 32 * С6. В ячейки D11:013 вводятся правые части выражений для ограничений задачи. Для нашего случая в эти ячейки мы вводим значения 1000, 6000 и 15 000 соответственно. Но в общем случае правые части ограничений могут иметь вид не числовых значений, а функциональных зависимостей и в соответствующие ячейки должны будут вводиться в виде формул. Результаты ввода исходных данных для рассматриваемого примера также представлены в табл. 2.3.

Для большей наглядности можно использовать режим представления формул. В пакете MS Office версии до 2010 г. для включения этого режима в меню «Сервис» нужно выбрать «Параметры», затем «Вид»; в поле «Параметры окна» выбрать «Формулы» и затем нажать ОК. В более поздних версиях MS Office ял я включения режима представления формул достаточно в меню «Формулы» (Formulas) выбрать и нажать кнопку «Показать формулы» (Show formulas). Результат ввода исходных данных в режиме отображения формул приведен в табл. 2.4.

1.3. Автоматизация ввода функциональных зависимостей. Действия, описанные в п. 1.1 и 1.2, целесообразно выполнять для относительно небольшого числа переменных и ограничений (2—3). Для большего количества переменных и ограничений ввод функциональных зависимостей и целевой функции можно автоматизировать. Для этого в отдельных ячейках таблицы MS Excel необходимо указать все коэффициенты с_{ и a_ijf входящие в выражения для целевой функции и ограничений, как это показано, например, в табл. 2.5 (включен режим отображения формул).

Созданная форма для ввода условий задачи предполагает, что значения независимых переменных располагаются в ячейках диапазона B4: D4, коэффициенты целевой функции — B7: D7, коэффициенты перед переменными в ограничениях — В11: Е>11, B12: D12, B13: D13.

Для автоматизации ввода зависимостей для целевой функции и ограничений целесообразно использовать функцию MS Excel «Сумма произведений» (СУММПРОИЗВ, SUMPRODUCT), которая перемножает соответствующие элементы заданных массивов и возвращает сумму их произведений. В форме, представленной в табл. 2.5, задать аргументы этой функции достаточно лишь один раз, например в ячейке значения целевой функции (Е7), а в ячейки правых частей ограничений данная функция просто копируется, причем ее аргументы изменяются автоматически. Но поскольку массив переменных входит в качестве аргумента во все функции и поэтому не должен изменяться, на всю группу ячеек значений переменных должны быть сделаны абсолютные (неизменяемые) ссылки. Для этого при адресации таких ячеек нужно использовать знак «$», как это указано в табл. 2.5.

Алгоритм использования функции СУММПРОИЗВ для ввода зависимостей из математической модели следующий.

• 1.3.1. Поместить курсор в ячейку Е7.
• 1.3.2. Курсором мыши нажать на кнопку «Вставка функции» (Insert Functions) на панели инструментов.
• 1.3.3. В появившемся окне «Мастер функций» (Insert Functions) выбрать раздел «Математические» (Math & Trig) из поля «Категория» (A category), затем «СУММПРОИЗВ» (SUMPRODUCT) из поля «Функция» (A function) и нажать кнопку ОК.
• 1.3.4. В появившемся после нажатия на кнопку ОК окне в поле «Массив1» (Array 1) ввести B$ 4:D$ 4, в поле «Массив2» (Array2) — B7: D7. Во все диалоговые окна MS Excel адреса ячеек удобно вводить не с клавиатуры, а мышью, протаскивая ее по тем ячейкам, адреса которых нужно ввести.
• 1.3.5. После нажатия на кнопку О К в ячейку Е7 будет введено значение целевой функции.

сл.

СУ)

Таблица 2.5

• 1.3.6. Копировать содержимое ячейки Е7 в буфер («Правка», «Копировать»), переместить курсор в ячейку Е11, ввести содержимое буфера («Правка», «Вставить»). В ячейку Е11 введено значение ограничение по площади пашни.
• 1.3.7. Копировать содержимое ячейки Е11 в ячейки Е12, Е13.

  Введение

  зависимостей для левых частей ограничений закончено.

Для правых частей ограничений (диапазон ячеек F11: F 13) можно использовать аналогичную процедуру, но так как правые части ограничений задаются условиями задачи чаще не функциональными, а числовыми значениями, то заполнение соответствующих ячеек лучше осуществлять, как это показывалось в п. 1.2.

Этап 2. Нахождение оптимального решения.

• 2.1. Открыть диалоговое окно «Поиск решения».
• 2.2. В соответствующих полях установить адрес целевой ячейки ($Е$ 7), режим оптимизации (поиск максимума), адреса ячеек со значениями искомых переменных ($B$ 4:$L)$ 4). Пользуясь кнопкой «Добавить», последовательно ввести все ограничения, указывая адрес ячейки для левой части ограничения, соответствующий знак и адрес ячейки для правой части ограничения.
• 2.3. Выбирается режим «Сделать переменные без ограничений неотрицательными» (установлено по умолчанию) и устанавливаются параметры оптимизации, например условия для решения задач оптимизации (нелинейных, линейных, целочисленных и др.). При необходимости можно установить значения ряда технических параметров (кнопка «Параметры»), например «Результаты итераций» (для отслеживания результатов на каждой итерации), а также параметров ограничения времени на решение задачи, числа итераций, точности решения, хотя их значения по умолчанию подходят для большинства решаемых задач.
• 2.4. После установления необходимых параметров нужно нажать на кнопку ОК в окне «Параметры поиска решения», затем на кнопку «Выполнить» в окне «Поиск решения». После нахождения оптимального решения на экране появляется диалоговое окно «Результаты поиска решения», а в соответствующих ячейках таблицы указываются полученные результаты для переменных, целевой функции и ограничений (табл. 2.6).

Таблица 2.6

Результаты решения задачи.

Возможны случаи, когда оптимальное решение задачи оптимизации при заданных условиях не может быть найдено. В этом случае выводится одно из следующих сообщений: «Поиск не может найти подходящею решения» или «Значения целевой ячейки не сходятся». Это означает, что условия задачи оказываются несовместными (противоречивыми), поэтому нельзя найти решение, которое удовлетворяло бы всем ограничениям при заданной точности. В таком случае следует проверить и при необходимости скорректировать ограничения, после чего снова запустить процедуру поиска решения. Если появляется сообщение «Условия для линейной модели не удовлетворяются», необходимо выключить режим «Линейная модель» и вновь запустить процедуру поиска решения.

Этап 3. Генерация отчетов о решении оптимизационной задачи.

Анализ полученных результатов можно проводить, используя так называемые двойственные оценки, известные из теории оптимизации. Для этого необходимы дополнительные отчеты, создаваемые в окне «Результаты поиска решения». Можно создать отчеты трех типов: отчет по результатам, отчет по устойчивости, отчет по пределам. Для генерации одного или нескольких отчетов нужно выбрать в окне «Результаты поиска решения» названия нужных отчетов и нажать кнопку ОК (при выборе нескольких отчетов удерживайте клавишу Ctrl).

В отчете по результатам (табл. 2.7) показаны значения целевой функции и искомых переменных до и после вычислений, а также результаты по ограничениям (использованию ресурсов). В графе «Разница» показывается количество неиспользованного ресурса. Если ресурс используется полностью, то его статус определен как «связанное», при неполном использовании — «не связан».

Отчет по устойчивости (табл. 2.8) характеризует устойчивость полученного решения при изменениях коэффициентов целевой функции и ограничений. В разделе «Изменяемые ячейки» приводятся оптимальные значения переменных («Результ. значение»). Показатель «Нормированная стоимость» (в некоторых версиях MS Excel — «Редуцированная стоимость») характеризует, насколь;

Таблица 2.7

Отчет по результатам.

Отчет по устойчивости.

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

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

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

Этап 4. Экономическая интерпретация и анализ полученного решения.

Из табл. 2.7 следует, что оптимальный план предполагает возделывание картофеля (х_г = 464,79 га) и овощей (х₃ = 338,03 га) на площади 802,82 га, что обеспечит получение максимальной прибыли в размере 13 318 309,9 ден. ед. Производство зерновых при заданных условиях оказывается неэффективным. В табл. 2.8 показано, что при введении в оптимальный план посева 1 га зерновых конечный результат уменьшится на 1408,45 ден. ед. Из табл. 2.7 и 2.8 следует, что недоиспользование пашни составляет 197,18 га. Трудовые ресурсы и ресурОтчет о пределах.

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

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

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

Рассмотрим возможность применения модели транспортной задачи для анализа проблемы взаимодействия участников инновационно-предпринимательской экосистемы (ИПЭС). Ключевыми участниками ИПЭС считаются государство (регулятор инновационно-предпринимательской активности), вузы и научно-исследовательские центры (разработчики новых идей и технологий), инвесторы (бизнес-ангелы, венчурные компании, банки), промышленные предприятия (реализующие инновационные продукты) [27]. От эффективности функционирования ИПЭС (в первую очередь — взаимодействия ее участников) зависят результативность производства и реализации новых идей. Это сложная проблема, не сводимая к простой математической задаче, а требующая нелинейного, многоэтапного, конструктивного диалога для достижения системного компромисса интересов, целей и стратегий участников^[2]. Одним из предметов обсуждения участников ИПЭС является выделение и распределение финансовых средств на разработку и реализацию новых проектов.

В качестве ориентира {benchmark) для решения задачи распределения ресурсов нескольких субъектов на различные инвестиционные проекты может выступать решение транспортной задачи [27].

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

правительство — 7 млн руб.; университет 1 — 1 млн руб.; университет 2 — 2 млн руб.; предприятие 1—3 млн руб.; предприятие 2 — 5 млн руб.; инвестор 1 — 15 млн руб.; инвестор 2 — 10 млн руб.

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

Характеристики реализации данных проектов представлены в табл. 2.10.

Таблица 2.10

Исходные данные для примера 2.3.

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

Решение в MS Excel

Макет решения представлен на рис. 2.2.

В ячейках диапазона 133:1310 расположены имеющиеся ресурсы организаций. В ячейках диапазона Е4: Р7 расположены характеристики проектов, включающие затраты и ожидаемый доход. Ячейки диапазона B14: L20 содержат распределение ресурсов организаций на все 11 проектов, включая безрисковый. В ячейках диапазона N14: N21 расположены имеющиеся ресурсы организаций.

О) го.

Рис. 2.2. Макет решения задачи.

В каждую ячейку диапазона 014:021 внесены формулы «=СУММ (В14:Ы4)», «=СУММ (В15:Ы5)»,"=СУММ (В21:Е21)". Данные формулы отражают ресурсы организаций, выделенные на реализацию проектов. В каждую ячейку диапазона Р14: Р21 внесены формулы «N14 — 014», «N15 — 015»,"N21 — 021″. Данные формулы отражают остаток средств организаций. В ячейках диапазона В24: М24 отражены необходимые затраты на реализацию каждого проекта. В ячейках диапазона В25: М25 отражены затраты, произведенные организациями на каждый из проектов. В каждую из данных ячеек внесены формулы «СУММ (В15:В21)», «СУММ (С15:С21)», …, «СУММ (М15:М21>>. В ячейки диапазона В26: К26 включена вероятность реализации данного проекта. В каждую из данных ячеек внесены формулы «=ЕСЛИ (В25/В24>=0;В25/В24;0)», «=ЕСЛИ (С25/С24>=0;С25/С24;0)», …, «=ЕСЛИ (К25/К24>=0;К25/К24;0)». В ячейках диапазона В31: М32 отражены реальный и ожидаемый доходы от проектов.

Для решения используем модуль «Поиск решения» (рис. 2.3).

Рис. 23. Применение модуля «:Поиск решения».

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

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

В качестве изменяемых ячеек указываем диапазон $B$ 15:$L$ 21, чтобы найти оптимальное распределение ресурсов организаций.

На рис. 2.4 представлены результаты выполнения поиска решения по распределению ресурсов. Исходя из данного решения должны быть реализованы проекты с номерами 1, 3, 5, 7, 9. Ожидаемый доход в таком случае составит 119,475 дсн. сд.

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

Рис. 2.4. Результаты решения задачи.

• [1] На основе материалов учебного пособия [8].
• [2] В более сложной постановке эта задача и возможности ее решения рассмотрены в параграфе 3.5.