SHPORA.net :: PDA

[ Back ]

Существование зависимости между решениями прямой и двойственной задач характеризуются следующими леммами и теоремами двойственности.

Лемма 11.1 (основное неравенство теории двойственности). Если – некоторый план исходной задачи, а – произвольный план двойственной задачи, то значение целевой функции исходной задачи при плане всегда не превосходит значение целевой функции двойственной задачи при плане , т.е.

Лемма 11.2. Если и – допустимые решения взаимно двойственных задач, для которых выполняется равенство , то – оптимальное решение исходной задачи, а – оптимальное решение двойственной задачи.

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

.

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

Из этой теоремы вытекают необходимые и достаточные условия:

a) разрешимости задач – существование хотя бы одного допустимого плана у каждой задачи;

б) оптимальности допустимых планов X и Y – выполнение равенства F(X) = T(Y).

Теорема 11.2. Вторая теорема двойственности (теорема о дополнительной нежесткости). Для того чтобы два допустимых решения и пары двойственных задач были их оптимальными решениями, необходимо и достаточно, чтобы они удовлетворяли системе уравнений

(*)

(**)

Данная теорема позволяет:

a) установить оптимальность решения одной задачи по свойствам решения двойственной;

б) найти оптимальное решение одной задачи по решению двойственной.

Теорема верна для симметричной двойственной пары. Для задач в канонической и общей формах соотношения (*) и (**) верны только для ограничений в виде неравенств и для неотрицательных переменных.

Полученные выше результаты непосредственно характеризуют взаимосвязь прямой и двойственной задач:

1. В оптимуме



2. На любой итерации процесса решения прямой задачи



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

Двойственные оценки могут быть использованы для определения приоритета используемых ресурсов в соответствии с их вкладом в величину целевой функции.

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

(Прибыль) < (Общая ценность ресурсов).

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

Чтобы дать представление о соответствующих обозначениях, часто встречающихся в литературе по линейному программированию, введем следующее определение:



– суммарная оценка ресурсов, используемых при производстве единицы продукции -го вида.

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

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



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

ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД

Из результатов предыдущих пунктов следует, что для получения решения исходной задачи можно перейти к двойственной и, используя оценки ее оптимального плана, определить оптимальное решение исходной задачи.

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

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

Рассматривая это условие с учетом двойственности, можно записать

.

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

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

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

Пример. Найти минимум функции

при ограничениях



.

Перейдем к канонической форме:



при ограничениях





Начальная симплекс-таблица имеет вид



Базисные

переменные x1 x2 x3 x4 x5 Решение

x3

x4

x5 –3

–4

1 –1

–3

2 1

0

0 0

1

0 0

0

1 –3

–6

3

–2 –1 0 0 0 0

Начальное базисное решение оптимальное, но не допустимое.

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

Условие допустимости. В качестве исключаемой переменной выбирается наибольшая по абсолютной величине отрицательная базисная переменная (при наличии альтернатив выбор делается произвольно). Если все базисные переменные неотрицательные, процесс вычислений заканчивается, так как полученное решение допустимое и оптимальное.

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

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

В рассматриваемом примере исключаемой переменной является . Отношения, вычисленные для определения новой базисной переменной, приведены в следующей таблице:

Переменные x1 x2 x3 x4 x5

-уравнение

x4-уравнение –2

–4 –1

–3 0

0 0

1 0

0

Отношение – – –

В качестве включаемой переменной выбирается x2. Последующее преобразование строк приводит к новой симплекс-таблице:

Базисные

переменные x1 x2 x3 x4 x5 Решение

x3

x2

x5



0

1

0 1

0

0



0

0

1 –1

2

–1

0 0 0 2

Новое решение также оптимальное, но все еще недопустимое. В качестве новой исключаемой переменной выберем (произвольно) x3. Определим включаемую переменную.

Переменные x1 x2 x3 x4 x5

-уравнение

x4-уравнение

0

0 0

1

0

0

отношение – – 1 –

Вводимой в базис переменной является x1 и в результате получим следующую симплекс-таблицу:

Базисные

переменные x1 x2 x3 x4 x5 Решение

x1

x2

x5 1

0

0 0

1

0



–1



1 0

0

1



0

0 0 0

Полученное решение x1= , x2= является оптимальным и допустимым.

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