Теоретические положения. С каждой задачей ЛП связана другая линейная задача, называемая двойственной

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

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

С помощью свойств задачи, двойственной к прямой задаче ЛП, можно делать ряд экономически содержательных выводов.

Переменные двойственной задачи у_i называют двойственными оценками, или теневыми ценами, или «ценами» ресурсов, или объективно обусловленными оценками.

Задача, двойственная по отношению к прямой задаче, составляется согласно правилам, представленным в таблице 6.1 [1–5].

Таблица 6.1 – Соответствие двойственных задач ЛП

Исходная (прямая) задача	Двойственная задача
Целевая функция F (x) → max	Целевая функция F ′(x) → min
Константы в правых частях ограничений	Коэффициенты целевой функции
Коэффициенты целевой функции	Константы в правых частях ограничений
j -й столбец коэффициентов в ограничениях	j -я строка коэффициентов в ограничениях
j -я строка коэффициентов в ограничениях	j -й столбец коэффициентов в ограничениях
j -я неотрицательная переменная	j -e неравенство вида ≥
j -я переменная без ограничений в знаке	j -e ограничение вида =
i -e ограничение вида ≤	i -я неотрицательная переменная
i -e ограничение вида =	i -я переменная без ограничений в знаке

Если задачу ЛП рассматривать как задачу об использовании ресурсов (сырья), то параметры задачи имеют следующий смысл. В прямой задаче – количество единиц j -го продукта; – стоимость единицы j -го продукта; – ресурс j -го продукта. В двойственной задаче теневая цена – стоимость единицы i -го сырья. Стоимость всех ресурсов .

Чувствительность экономико-математической модели – это зависимость оптимального решения от изменения параметров исходной задачи.

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

1 Анализ сокращения или увеличения ресурсов:

а) на сколько можно увеличить (при ограничениях типа ) или уменьшить (при ограничениях типа ) запас дефицитного ресурса для улучшения оптимального значения целевой функции (ЦФ)?

б) на сколько можно уменьшить (при ограничениях типа ) или увеличить (при ограничениях типа ) запас недефицитного ресурса при сохранении полученного оптимального значения ЦФ?

2 Изменение запаса какого из ресурсов наиболее выгодно?

3 Анализ изменения коэффициентов ЦФ: каков диапазон изменения коэффициентов ЦФ, при котором не меняется оптимальное решение?

Пример – Необходимо составить модель двойственной задачи для прямой задачи, приведенной в примере к теме 5.

Модель прямой задачи: Модель двойственной задачи:

Применяя надстройку Excel Поиск решения, кроме нахождения оптимального решения, можно получить три листа с отчетами: Отчет по результатам, Отчет по пределам, Отчет по устойчивости. Анализируя эти отчеты (рисунки 6.1 – 6.3), можно получить ответы на все вышеперечисленные вопросы. Отчеты по устойчивости и о пределах не создаются для моделей, значения переменных в которых ограничены множеством целых чисел.

Отчет по результатам (рисунок 6.1) с остоит из 3 таблиц.

Рисунок 6.1 – Лист отчета по результатам

1 Целевая ячейка. В ней отображается начальное значение целевой функции и оптимальное (результат). В данной задаче – 0 и 358 тыс. д. е.

2 Изменяемые ячейки. В ней отражены исходные значения переменных и результирующие (оптимальные).

Если изделие вошло в оптимальный план (х_j > 0) (конфеты «Зубр» и

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

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

Если значение изменяемой ячейки равно 0, то это означает, что данная продукция (конфеты «Зайка» и «Белочка») не входит в оптимальное решение (оптимальный план выпуска продукции) и считается нерентабельной, поскольку стоимость ресурсов, затраченных на производство данного вида конфет, больше его прибыли. Для проверки этого утверждения можно подставить в ограничения двойственной задачи значения двойственных оценок (рисунок 6.3):

3 Ограничения. Кроме имени ограничения, ячейки, в которую вписана левая часть ограничения, в ней отображены следующие столбцы.

Значение – значение левой части ограничения при оптимальном плане, т. е. сколько фактически использовано ресурса. Например, какао – 50 т, орехи – 32,67 т, сахар – 70 т.

Формула – отображаются формула и знак ограничения (≤).

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

Разница – отображена разность между значением переменной в найденном оптимальном решении и заданным для нее граничным условием (правой частью ограничения), т. е. количество оставшегося не использованным ресурса. Ресурс «орехи» не использован в количестве 32,33 т.

Таблица Ограничения отчета по результатам дает информацию для анализа возможного изменения запасов недефицитных ресурсов при сохранении полученного оптимального значения целевой функции. Так, если на ресурс наложено ограничение типа ≥, то в графе Разница указывается количество ресурса, на которое была превышена минимально необходимая норма. Если на ресурс наложено ограничение типа , то в графе Разница указывается количество ресурса, которое не используется при реализации оптимального решения. Из задачи следует, что запас недефицитного ресурса «орехи» можно уменьшить на 32,33 т и это никак не повлияет на оптимальное решение (выпуск 6 т конфет «Зубр» и 17,333 т конфет «Мишка»).

Отчет по устойчивости (рисунок 6.2) состоит из двух таблиц.

Рисунок 6.2 – Лист отчета по устойчивости

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

Результирующее значение – это оптимальный план.

Нормированная стоимость – показывает, на сколько изменится значение целевой функции после принудительного включения единицы этой продукции в оптимальный план. Таким образом, значение, например, для конфет «Зайка» (–2,2) показывает, что значение целевой функции уменьшится на 2,2 тыс. д. е., если значение переменной х ₃ (конфеты «Зайка») увеличить на единицу в оптимальном плане (с 0 до 1 т). Это означает, что если, несмотря на оптимальное решение, потребовать включить в план выпуска 1 т конфет «Зайка», то новый план выпуска (6,6 т конфет «Зубр», 15,06 т конфет «Мишка», 1 т конфет «Зайка») принесет прибыль 355,8 р./мес., что на 2,2 тыс. д. е. меньше, чем в прежнем оптимальном решении 358 тыс. д. е. Если продукт рентабелен, то нормированная стоимость будет равна 0 (для конфет «Зубр» и «Мишка»).

Целевой коэффициент – значения коэффициентов целевой функции.

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

Например, если прибыль от конфет «Зубр» увеличится на 3,66 и более тыс. д. е. (например, станет равной 28,67 тыс. д. е.), то изменится набор переменных, входящих в оптимальное решение – в оптимальный план выпуска войдут уже конфеты «Зубр» и «Зайка», а не «Зубр» и «Мишка». Если прибыль будет снижаться на величину до 1,33 тыс. д. е., (т. е.

до значения 23,667 тыс. д. е.), то оптимальное решение останется прежним.

Допустимое увеличение прибыли от конфет «Зайка» равно

2,2 тыс. д. е., а допустимое уменьшение – практически не ограничено (1·10³⁰). Это означает, что если прибыль от конфет «Зайка» возрастет более чем на 2,2 тыс. д. е., например, станет равной 12,3 тыс. д. е., то оптимальное решение изменится – в оптимальный план выпуска войдут уже конфеты «Зубр» и «Зайка», а не «Зубр» и «Мишка», а если прибыль будет снижаться вплоть до нуля, то оптимальное решение останется прежним.

2 Ограничения. Кроме имени переменных и адресов ячеек, в данной таблице присутствуют следующие столбцы.

Результирующее значение – отображает значение левой части ограничения в оптимальном плане, т. е. сколько фактически использовано ресурса.

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

Теневая цена показывает, на сколько изменится значение целевой функции в оптимальном решении при увеличении запаса ресурса на единицу. Если наличие, например, третьего ресурса (сахар) составит не 70, а 69 т, то значение целевой функции уменьшится на 1,4 тыс. д. е. и станет равным 356,6 тыс. д. е. При увеличении запаса сахара на единицу значение целевой функции 358 тыс. д. е. увеличится на 1,4 тыс. д. е. На сколько бы ни изменялся запас избыточного (недефицитного) ресурса в допустимых пределах, значение целевой функции не изменится.

Теневая цена ресурса позволяет также ответить на вопрос: запас какого ресурса выгоднее в первую очередь увеличивать? Увеличение запаса какао на 1 т приведет к увеличению значения целевой функции на 5,2 тыс. д. е., т. е. до 363,2 тыс. д. е., а увеличение запаса сахара на 1 т приведет к увеличению значения целевой функции на 1,4 тыс. д. е., т. е. до 359,4 тыс. д. е. Поэтому выгоднее в первую очередь увеличивать запас наиболее дефицитного ресурса, имеющего самую высокую теневую цену, т. е. какао.

Ограничение Правая часть – запас ресурса по условию задачи.

Допустимое увеличение, допустимое уменьшение – показывают, на сколько можно изменить правую часть ограничения, сохранив при этом оптимальное решение (выпуск конфет «Зубр» и «Мишка»). Например, увеличение запаса сахара до 101 т (больше чем на 30 т) приведет к тому, что в оптимальный план войдут уже конфеты «Мишка» и «Зайка».

Используя отчет по устойчивости, можно оценить рентабельность нового продукта. Например, требуется оценить целесообразность введения в план производства пятого вида конфет «Мираж», нормы затрат ресурсов которого соответственно равны 5 (какао), 6 (орехи) и 7 (сахар) т, а прибыль от реализации одной тонны конфет составит 35 тыс. д. е. Для этого необходимо рассчитать стоимость ресурсов, расходуемых на 1 т конфет «Мираж», т. е. следует просуммировать произведения теневых цен

и норм затрат соответствующих ресурсов при выпуске этих конфет:

5·5,2 + 6·0 + 7·1,4 = 35,8 тыс. д. е.

Затраты на выпуск конфет «Мираж» превышают прибыль, получаемую за нее, и выпускать эти конфеты нецелесообразно. Эта продукция будет рентабельной при получении прибыли больше, чем 35,8 тыс. д. е.

Отчет по пределам (рисунок 6.3) состоит из двух таблиц:

1) оптимальное значение целевой ячейки;

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

Рисунок 6.3 – Лист отчета по пределам

Значение – оптимальное значение переменной.

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

Целевой результат – это значение целевой ячейки, когда значение изменяемой ячейки равно ее нижнему или верхнему пределу.

Например, если принять, что конфеты «Зубр» выпускаться не будут (т. е. взять нижний предел 0 т), то при выпуске 17,33 т. конфет «Мишка», 0 т конфет «Зайка» и 0 т «Белочка» прибыль (целевая функция) будет равняться 208 тыс. д. е. Для проверки этого утверждения необходимо записать целевую функцию – умножить значения всех коэффициентов целевой функции на значения переменных и просуммировать их:

25·0 + 12·17,33 + 10·0 + 11·0 = 208 тыс. д. е.