Регистрация


Рубрики


Ссылка на сайт:
Двойственность

2.3. Двойственность.

2.3.1. Двойственная задача ЛП.

Рассмотрим прямую задачу ЛП.

(15)

Двойственной задачей ЛП для прямой задачи (15) является:

(16)

Обозначим - i-ю строку матрицы А и aj - j-й столбец матрицы A. Пусть строки матрицы определяют коэффициенты отдельных ограничений прямой задачи. Тогда двойственная задача определяется следующим образом:

Прямая задача

Двойственная задача

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

Теорема. Если прямая задача ЛП имеет оптимальное решение, то двойственная задача также имеет оптимальное решение, при этом значения их целевых функций равны.

Теорема. Задача, двойственная к двойственной задаче ЛП, совпадает с прямой задачей ЛП.

Теорема. Если дана пара, состоящая из прямой и двойственной задач ЛП, то возможна одна из трех ситуаций, отображенных в следующей таблице.

двойствен-

ная

прямая

конечный

оптимум

неограничена

недопустима

конечный

оптимум

1

_

_

неограничена

_

_

3

недопустима

_

3

2

2.3.2. Двойственная информация в таблице.

Предположим, что решение задачи (15) мы начинаем с таблицы, в левой части которой стоит единичная матрица (см. рис.2). На произвольной итерации симплекс-метода мы имеем таблицу, где на месте единичной матрицы стоит матрица B-1,где B - матрица, составленная из столбцов исходной матрицы A, соответствующих текущему БДР (см. рис.3 ).

I

рис.2. Исходная таблица. рис.3. Таблица текущей итерации

Нулевая строка текущей таблицы симплекс-метода, согласно (10), задается вектором

(17)

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

где B - соответствует оптимальному решению прямой задачи. Из (17) получим

(18)

Учитывая, что левая часть матрицы A является единичной матрицей, запишем первые m компонент вектора

Отсюда следует, что решение двойственной задачи может быть получено на основе информации заключительной таблицы симплекс-метода

В заключении отметим, что на произвольном шаге симплекс-метода для базисных столбцов Aj выполняется соотношение

, (19)

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

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

Рассмотрим прямую задачу, как задачу распределения ограниченных ресурсов с целевой функцией, подлежащей максимизации. Ниже приведены формулировки прямой и двойственной задачи.

Прямая задача Двойственная задача

Условия прямой задачи можно интерпретировать следующим образом. Коэффициент cj - прибыль, приходящаяся на единицу продукции j - го вида производственной деятельности. Расход ресурса i , запасы которого ограничены величиной bi, на единицу продукции j - го вида равен aij единицам этого ресурса.

Переменные двойственной задачи yi интерпретируются как внутренняя

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

Сумму можно рассматривать как суммарную оценку всех ресурсов j - го способа производства. Ограничения двойственной задачи можно интерпретировать следующим образом :



Пожаловаться

Материал из рубрики: Мои статьи
5
рейтинг рассчитывается на оценке от 1 до 5

Мои другие материалы