4. Решение задачи линейного программирования в табличном процессоре Excel

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

Рассмотрим пример.

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

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

1. Создание формы для ввода условий задачи.

2. Ввод исходных данных.

3. Ввод зависимостей из математической модели.

4. Ввод целевой функции, ограничений и граничных условий.

5. Решение задачи.

На рисунке 2 показаны: форма для ввода условий задачи, исходных данных, ограничений и целевой функции. В ячейку C3 вводим формулу: «=СУММПРОИЗВ(A$2:B$2;A3:B3)», а затем ее копируем в ячейки C4, C5, C6. Если задача содержит много ограничений и переменных, для отображения названий переменных при прокрутке, необходимо использовать команду «Закрепить области» из меню «Окно», предварительно выделив соответствующую строку.

Рисунок 1  Форма для ввода условий задачи, данных и зависимостей

После ввода данных в ячейки электронной таблицы выходим в диалоговое окно «Поиск решения»: «Сервис», «Поиск решения».

Рисунок 2  Диалоговое окно «Поиск решения»

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

Рисунок 3  Ввод ограничений

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

В диалоговом окне «Поиск решения» выбираем команду «Параметры».

Рисунок 4  Диалоговое окно «Параметры поиска решения»

Устанавливаем флажок «Линейная модель», что обеспечивает применение симплекс-метода. Так как значения переменных неотрицательные, то устанавливаем флажок «Неотрицательные значения». Указанные максимальное время и число итераций подходит для решения большинства задач. Остальные параметры оставляем также без изменений. Нажимаем на кнопку «OK» и выходим в диалоговое окно «Поиск решения». Переходим к решению задачи, для этого выбираем команду «Выполнить». После поиска оптимального решения на экране появляется: диалоговое окно «Результаты поиска решения».

Рисунок 5 Диалоговое окно «Результаты поиска решения»

Результаты решения записываются в ячейки электронной таблицы A2 и B2. Оптимальное решение равно:

X₁=7,2; X₂=1,6.

5. Анализ решения задачи линейного программирования в табличном процессоре Excel

Анализ оптимального решения начинается после успешного решения задачи. С помощью диалогового окна «Результаты поиска решения» можно вызвать отчеты трех типов:

1. Результаты;

2. Устойчивость;

3. Пределы;

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

Рисунок 6  Отчет по результатам

Рассмотрим отчет по результатам решения.

Отчет состоит из трех таблиц:

1. Таблица 1 приводит сведения о целевой функции. Во втором столбце приведено значение целевой функции до начала вычислений.

2. Таблица 2 приводит значения искомых переменных, полученных в результате решения задачи.

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

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

Отчет по устойчивости состоит из двух таблиц.

В первой таблице приводятся следующие результаты:

1. результат решения задачи;

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

Рисунок 7  Отчет по устойчивости

3. коэффициенты целевой функции;

4. предельные значения приращения коэффициентов ∆с_i целевой функции, при которых сохраняется набор переменных, входящих в оптимальное решение.

Во второй таблице приводятся аналогичные значения для ограничений:

1. величины использованных ресурсов;

2. теневые цены ресурсов;

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

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

1. приводятся значения x_i в оптимальном решении;

2. приводятся нижние пределы изменения значений x_i.

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

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

Рисунок 8  Отчет по пределам

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