Прямая задача линейного программирования

Решение задач линейного программирования в Excel производится с помощью решающего блока Solver, вызываемого командой меню Сервис–Поиск решения.

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

Найти значения переменных , максимизирующих целевую функцию

при ограничениях:

Ввод исходных данных показан на рисунке.

Теперь необходимо ввести зависимости из математической модели. Эти зависимости представляют собой левые части ограничений и целевую функцию. Данную операцию можно выполнить с помощью функции СУММПРОИЗ, где в первый массив вводятся коэффициенты соответствующего ограничения, а во второй массив переменные , точнее ячейки, где им присвоены инициирующие значения - ячейки В10: Е10.

1. Из меню Сервис откройте окно Поиска решения.

2. В поле «Установить целевую ячейку» введите $F$10.

3. Из группы Равной выбрать переключатель - максимальное значение.

4. В поле области «Изменяя ячейки» введем ячейки с первоначальными значениями переменных -$В$10: $Е$ 10.

5. Нажав кнопку Добавить, открыть диалоговое окно Добавление ограничения.

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

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

После нажатия кнопки ОК вновь появится диалоговое окно Поиск решения. По нажатии кнопки Выполнить на экран выводится окно Результаты поиска решения.

Еслирешение не найдено, окно выведет соответствующее сообщение.

Если решение найдено, выделим все три типа отчетов, нажмем ОК,

и результат решения задачи появится на экране.

Для анализа полученного оптимального решения в Excel предусмотрены три типа отчетов: отчет по результатам, отчет по устойчивости и отчет по пределам.

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

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

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

В анализе переменных приведены следующие данные:

· результирующие значения переменных;

· нормированная стоимость, т.е. дополнительные двойственные переменные, которые показывают, насколько изменяется целевая функция при принудительном включении единицы этой переменной в оптимальное решение;

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

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

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

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

· теневые цены, т.е. двойственные оценки, которые показывают, как изменится целевая функция при изменении ресурсов на единицу;

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

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

Рассмотрим теперь ввод математической модели в матричном виде, не меняя приготовленной формы. Для этого необходимо ввести две матричных функции. В векторе ограничений левой части – ячейки F5: F7 – вводится функция умножения матрицы коэффициентов в ограничениях и транспонированного вектора переменных:

=МУМНОЖ(В5: Е7; ТРАНСП(В10: Е10)).

Целевая функция записывается как функция умножения вектора коэффициентов целевой функции на транспонированный вектор переменных: =МУМНОЖ(В4: Е4; ТРАНСП(В 10: Е 10)).

Ввод ограничений для оптимизационной задачи в матричном виде показан на рисунке.

Двойственная задача

Решим двойственную задачу. Схема формирования двойственной задачи следующая:

1. Коэффициенты бывшей целевой функции становятся правой частью ограничений.

2. Правая часть ограничений становится коэффициентами новой целевой функции.

3. Матрица коэффициентов ограничений транспонируется.

Ввод зависимостей для двойственной задачи показан на рисунке:

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

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

Результаты решения двойственной задачи приведены на рисунке ниже.

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