ТОР 5 статей: Методические подходы к анализу финансового состояния предприятия Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века Характеристика шлифовальных кругов и ее маркировка Служебные части речи. Предлог. Союз. Частицы КАТЕГОРИИ:
|
Экономическая интерпретация двойственной задачи. Постановка задачи двойственной к задаче ЛП с ограничениями типа равенств и неравенств.Для проведения содержательной интерпретации двойственной задачи (II) свяжем переменные двойственной задачи Пусть L* - максимальное значение дохода в задаче (I). Если запасы ресурсов , i=1,...,m изменить, то может измениться и максимальный доход L*. Это означает, что L* является функцией от ресурсов , i=1,...,m, т.е. Рассмотрим отношение приращения дохода к приращению i-го ресурса ; Тогда по определению частной производной функции Но по первой теореме двойственности оптимальное значение целевой функции прямой задачи совпадает с оптимальным значением целевой функции двойственной задачи Таким образом, оптимальное значение двойственной переменной числено равно дополнительному доходу при увеличении i-го ресурса на единицу, если величина является достаточно малой по сравнению с величиной Полученный вывод имеет очень важное практическое применение. Пусть L*- максимальное значение дохода в задаче (I), Тогда, изменяя i-й ресурс на единицу, получим новое значение максимального дохода по формуле или более общий вид Двойственные переменные называются оценками (теневыми ценами, ценностями) соответствующих ресурсов i=1,..., m, и характеризуют меру эффективности использования соответствующих ресурсов. Рассмотрим задачу ЛП (1) или, в матричной записи, (2) Задачей, двойственной к (1) (двойственной задачей), называется задача ЛП от переменных вида (3) или, в матричной записи, (4) где . Правила построения задачи (3) по форме записи задачи (1) таковы: в задаче (3) переменных столько же, сколько строк в матрице задачи (1). Матрица ограничений в (3) — транспортированная матрица . Вектор правой части ограничений в (3) служит вектором коэффициентов максимизируемой линейной форме в (1), при этом знаки неравенств меняются на равенство. Наоборот, в качестве целевой функции в (3) выступает линейная форма, коэффициентами которой задаются вектором правой части ограничений задачи (1), при этом максимизация меняется на минимизацию. На двойственные переменные накладывается условие неотрицательности. Задача (1), в отличии от двойственной задачи (3) называется прямой.
6. Основное неравенство двойственности. Для любых допустимых планов прямой и двойственной задачи ЛП справедливо неравенство: Доказательство: Не нашли, что искали? Воспользуйтесь поиском:
|