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

Построение двойственной задачи

Задача на минимум и максимум строятся по разному:

1. Исходная задача на максимум:

a. Каждому ограничению, кроме ограничению в знаке, ставятся в соответствии двойственная переменная u_i (двойственная переменная).

b. Функция цели двойственной задачи – это сумма произведений правой части на двойственную переменную. Ищется минимум L двойственного

c. Если Ui соответствует ограничению меньше или равно, то в двойственной больше или равно и наоборот, а если u_i равеству, то в двойственной любой знак.

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

Пример 1,

2. Исходные задачи на минимум: все наоборот.

a. Тоже самое

b. Тоже самое, но на максимум

c. Знаки наоборот

d. Неравенства наоборот

Пример 2,

ОРДЗ u_опт дает нам стоимость правых частей ограничений, которые называются теневой ценой правых частей или ресурсов (shadow price).

Пусть задача на максимум:

Если теневая цена u_опт действительна (смотри дальше), то это предельная цена покупки (продажи) ресурса для интенсивных стратегий, т.е. если реальная цена u_i^реал <= u_i^{опт(тен)} то есть смысл покупать ресурс , если u_i^реал => u_i^{опт(тен)},есть смысл продавать ресурс. При этом если мы покупали а единиц ресурса действие теневой цены распространяется на это, то в результате сделки мы получим новый доход L^опт….. при этом если задача на минимум, то имеет те же самые соотношения, только наоборот и L оптимальное при корректной сделке будет уменьшаться. Для задачи на минимум при ограничении больше или равно (сдерживающее ограничение) мы должны уменьшать правую часть, чтобы уменьшить L оптимальное на минимум. Теневая цена и даст предельную цену корректности такого уменьшения, т.е. теневая цена – сколько (предельно) платить за такое уменьшение.