Оптимальное решение двойственной задачи | MegaDOCs

Оптимальное решение двойственной задачи

Оптимальное решение двойственной задачи

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

Соотношения между прямой и двойственной задачами

Метод 1

Элементы в вектор-строке исходных коэффициентов целевой функции должны быть перечислены в таком порядке, в каком базисные переменные перечислены в столбце "Базис" в симплекс-таблице.

Метод 2

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

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

Метод 3.

Заметим, что базисные переменные в оптимальной симплекс-таблице

в столбце "Базис" записаны в таком порядке, что сначала идет х2, а затем х,. Поэтому в вектор-строке первоначальных коэффициентов целевой функции коэффициенты этих двух переменных должны идти в том же порядке:(вектор коэффициентов) = (коэффициент при х2, коэффициент при *,) = A2,5). Оптимальное решение двойственной задачи вычисляется так:

Метод 4.

Поскольку двойственная задача имеет две переменные, необходимо два уравнения, чтобы найти их значения. Сначала посмотрим, как ограничения двойственной задачи связаны с переменными хА и R, составляющими первоначальный базис прямой задачи.

Переменная xt: у1 ≥ 0

Переменная R: у2 ≥-М.

Из симплекс-таблицы с оптимальным решением имеем

коэффициент в г-строке при х4 = 29/5

коэффициент в г-строке при R = -2/5 + М.

Теперь, следуя методу 4, получаем систему уравнений

Соотношения между прямой и двойственной задачами

Отметим, что каждое уравнение включает только одну неизвестную, поэтому решение двойственной задачи существует всегда и находится легко. Так бывает всегда, когда ограничения двойственной задачи связаны с начальными базисными переменными. Конечно же, ничего не мешает использовать другие переменные при построении уравнений, необходимых для определения значений переменных двойственной задачи. Например, ограничения, ассоциируемые с переменными х1 и *,, порождают следующие уравнения (проверьте!):

Решение этой системы уравнений также приводит к оптимальным значениям двойственной задачи у, = 29/5 и у2 = -2/5. Однако эти уравнения уже не так просты, как уравнения, ассоциируемые с переменными x4 и R. (Убедитесь самостоятельно, что уравнения, ассоциированные с любыми двумя переменными из множества x1, х2, х3, x4, R, дают одни и те же значения переменных двойственной задачи.)

1. Вычисление значений в столбцах ограничений симплекс-таблицы (как левой, так и правой частей ограничений).

2. Вычисление значений в 2-строке.

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

Вычисление значений z-строки. На произвольной симплекс-итерации значения коэффициентов в z-строке вычисляются по следующей формуле 2.

Экономическая интерпретация двойственности

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

Рассмотрим сначала вариант оптимума, т.е. когда z = w. Исходя из представления прямой задачи как модели распределения ресурсов, можно считать, что величина z соответствует величине дохода (в долларах3). Поскольку b1- общее доступное количество ресурса i, равенство z = w можно переписать следующим образом.

Доход(долл.)=∑ (количество ресурса i) x (доход(долл.) на единицу ресурса i).

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

Аналогично для любой пары допустимых решений прямой и двойственной задач неравенство z < w можно интерпретировать следующим образом:

доход < общая стоимость ресурсов.

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

мальным. Оптимум (максимальный доход) может быть достигнут только тогда, когда все потребляемые ресурсы использованы полностью. Если модель ЛП рассматривать более обще как модель некой системы, имеющую "вход" и "выход", то потребляемые ресурсы характеризуют "вход" этой системы, а получаемый доход— ее "выход". Система будет находиться в нестабильном (неоптимальном) состоянии, пока вход превышает выход. Устойчивое состояние системы характеризуется равенством входа и выхода.

Экономическая интерпретация двойственности

a) Сформулируйте задачу линейного программирования и с помощью про- граммы TORA найдите ее оптимальное решение.

b) Основываясь на двойственных ценах, приведенных программой TORA, определите возможное увеличение ежедневного фонда времени по каждой

технологической операции.

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

d) Возможно ли увеличение на 10% временного фонда операции пайки с со- хранением величины ее вклада в суммарный доход, определяемый текущей двойственной ценой?

Задача

Компания производит кожаные чехлы и сумки. На производство одного чехла требуется 8 м2 кожи и 12 часов рабочего времени, на производство сумки 2 м2 кожи и 5 часов рабочего времени. Текущие еженедельные ресурсы производства ограничены 1200 м2 кожи и 1850 часами рабочего времени.

Компания продает чехлы и сумки по цене 350 и 120 долл. соответственно.

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

Какова максимальная цена, по которой компании имеет смысл закупать дополнительную кожу? А какова допустимая максимальная цена дополнительных трудовых ресурсов?

Экономическая интерпретация ограничений двойственной задачи

Для интерпретации ограничений двойственной задачи используем формулу 2 из раздела. В соответствии с этим соотношением на любой итерации решения прямой задачи справедливо равенство

Условие оптимальности симплекс-метода в задаче максимизации говорит о том, что j-й вид деятельности (переменная xf), не представленный в текущем базисном решении, можно ввести в базис для увеличения дохода только тогда, когда коэффициент при Xj в z-строке (равный ) будет неотрицательным. В рамках предлагаемой экономической интерпретации это означает, что j-й вид деятельности должен быть представлен в базисном решении, если выполняется следующее неравенство.

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

j-го вида деятельности. В некоторых случаях разности используются непосредственно для вычисления коэффициентов в z-строке симплекс-таблицы (вместо метода Гаусса-Жордана). Такие вычисления используются в модифицированном симплекс-методе.162 страница!!!!