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

Двойственная задача проблемы Reddy Mikks

Для прямой задачи (2) производства красок компании Reddy Mikks двойственной является следующая задача линейного программирования

Так как оптимальным решением прямой задачи является , то оптимальным решением этой двойственной задачи является следующее: .

Оптимальное решение двойственной задачи показывает, что стоимость единицы первого ресурса (сырье A) составляет $750 за тонну, второго (сырье B) — $500 за тонну. Эти значения совпадают со значениями, полученными выше в 3.4 графическим способом, и справедливы, если значение первого ресурса увеличивается не более чем на 12 тонн, а второго — не более чем на 0,67 тонн. Таким образом, увеличение запаса первого ресурса с 24 до 36 тонн приведет к увеличению дохода на величину . Аналогичное увеличение запаса второго ресурса с 6 до 6,67 тонн приводит к увеличению дохода на величину . Еще раз подчеркнем, что подобные расчеты справедливы только тогда, когда увеличение запасов используемых ресурсов не выходит за полученные выше интервалы значений.

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

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

ТЕМА 5 Постановка и решение задач линейного программирования с помощью стандартного программного обеспечения

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

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

Рис. 4 Пример построения таблицы Excel для задачи о красках

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

Изменяемые ячейки (переменные). Отведем в таблице место для значений переменных. Каждой переменной соответствует одна ячейка (т.н. изменяемая ячейка). Выделим область ячеек B16:C16, соответствующих переменным, красной рамкой — в этих ячейках мы получим оптимальный производственный план. В начале решения в эти ячейки вводятся произвольные значения.

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

=СУММПРОИЗВ(B16:C16;B11:C11)

Функция СУММПРОИЗВ находится в категории «Математические». Аргументам функции являются массивы (диапазоны ячеек) одинаковой длины. Значение функции равно сумме произведений соответствующих элементов массивов.

Затраты ресурсов (ограничения). Для вычисления объемов ресурсов, затраченных при данном производственном плане, в ячейку D6 введена следующая формула

=СУММПРОИЗВ(В6:С6;$B$16:$С$16)

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

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

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

Дата добавления: 2014-12-29