Полная версия

Главная arrow Туризм arrow Основы функционирования систем сервиса

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

ДВОЙСТВЕННАЯ ЗАДАЧА

Составление двойственной задачи

В жизни всегда имеет место двойственность интересов. Так, производитель заинтересован в максимизации прибыли, а потребитель — в минимизации стоимости; в то же время они не могут существовать друг без друга. Рассмотрим данный феномен на примере задачи ЛП.

Основная задача ЛП формулируется следующим образом. Найти неотрицательные значения переменныххь х2,..., хп, Xj> О, / = 1, п, удовлетворяющих т условиям — равенствам или неравенствам:

и обращающих в максимум линейную функцию этих переменных

Значения коэффициентов я,у, bh Cj заданы, /= 1, 2,..., m,j = 1, 2,..., п.

Каждое линейное уравнение или неравенство можно записать в виде суммы:

а целевую функцию как

В матричных обозначениях задача может быть представлена в следующем виде: максимизировать функцию

при условиях

где

— векторы-столбцы п х 1 и т х 1;

— вектор-строка 1 х п

— матрица тхп.

В данной задаче неравенства типа < взяты для определенности. Задачу ЛП можно сформулировать с использованием неравенств типа > или равенств в стандартной форме. Более того, неравенства различных типов могут быть преобразованы к одному типу или к равенствам.

Рассмотрим задачу, двойственную к сформулированной. Двойственная симметричная задача формулируется следующим образом. Минимизировать

при условиях

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

а целевую функцию как

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

при условиях

где

— вектор-столбец т х 1.

Как видно, если в исходной задаче имеют место ограничения в виде неравенства типа >, а ЦФ минимизируется, то в двойственной задаче ограничения будут иметь вид неравенства типа <, а ЦФ максимизируется. Если исходная задача на поиск минимума, то двойственная — на поиск максимума и наоборот [3].

Пусть в прямой задаче ЛП ограничения заданы в форме равенств:

В матричной форме Ах = Ь.

Представим ограничения-равенства в виде системы равносильных неравенств:

В матричной форме Ах < Ь, Ах > Ь.

Умножим неравенство (9.15) на — 1 и получим исходную задачу ЛП в симметричной форме:

В матричной форме

Из двух матриц можно составить одну матрицу из двух блоков а из двух векторов-ограничений — один вектор из двух блоков

Для каждой системы ограничений введем двойственные переменные у! > 0 и у" > 0, такие, что у, = у! - у". В матричной форме переменные можно представить в виде двух векторов у' и у" и объединить их

Двойственная задача, согласно (9.9), (9.10), примет вид

В матричной форме

Обозначив ', задачу можно представить как

Переменная свободная, так как может принимать

положительные, отрицательные значения или может быть равной нулю.

Отметим различие допустимых множеств в исходной и двойственной задачах. В исходной задаче это подмножество пространства Rn, характеризуемое матрицей А и вектором ограничений Ь, а

в двойственной задаче это подмножество пространства Rm, определяемое транспонированной матрицей Ат и вектором с. Однако обе задачи содержат одни и те же исходные данные А, b и с.

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

  • 1) ЦФ исходной задачи задается на максимум, а ЦФ двойственной задачи — на минимум и наоборот;
  • 2) матрица тх п исходной задачи А = {Л заменяется на транспонированную матрицу Ат = [ajj размерностью пх т
  • 3) число переменных в двойственной задаче равно числу ограничений т в исходной задаче;
  • 4) каждому ограничению прямой задачи соответствует переменная двойственной задачи, а каждой переменной прямой задачи соответствует ограничение двойственной задачи;
  • 5) коэффициентами при неизвестных в ЦФ двойственной задачи являются свободные члены 6, в прямой задаче, а коэффициенты ЦФ прямой задачи становятся правыми частями неравенств двойственной задачи;
  • 6) если прямая задача на максимум, то ее система ограничений представляется в виде неравенств типа <. Двойственная задача решается на минимум, и ее система ограничений имеет вид неравенств типа >, и наоборот;
  • 7) если переменная х, исходной задачи может принимать только положительные значения, тоу'-е условие в системе двойственной задачи является неравенством вида >. Если переменная xt может принимать как положительные значения, так и отрицательные, то у'-е соотношение в системе представляет собой уравнение. Аналогичные связи имеют место между ограничениями исходной задачи и переменными двойственной задачи.

Для наглядности представим сформулированные правила в виде табл. 9.1, 9.2.

Таблица 9.1. Соотношения между переменными и коэффициентами прямой задачи (ПЗ) и двойственной задачи (ДЗ)

Перемен- ные ДЗ

Переменные ПЗ

Коэффициенты ЦФ ДЗ

*1

х2

*/

хп

Коэффициенты ЦФ ПЗ

О

«2

С/

сп

У

Элементы матрицы ПЗ и ДЗ

Ь

«и

«12

аМ

«1 л

У2

«21

«22

аУ

«2/

ь2

Ту

«,т

«У2

аи

«/и

bi

у'-е ограничение ПЗ

Ут

«ml

«m2

«ту

«тя

Ьщ

у'-е ограничение ДЗ

Таблица9.2. Соотношения между типами переменных и ограничений

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

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

Задача максимизации

Задача минимизации

Ограничения

Переменные

>

<0

<

>0

Окончание табл. 9.2

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

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

=

Свободная

Переменные

Ограничения

>0

>

<0

<

Свободная

=

В качестве конкретного примера преобразуем в соответствии с изложенными правилами двумерные задачи в двойственные задачи (см. § 7.2). Задача 1. О пошиве костюмов.

Так как в прямой задаче максимизировалась ЦФ, то в двойственной задаче необходимо ее минимизировать. Согласно (9.7), ЦФ будет иметь вид: ОДР для прямой задачи

Рис. 9.1. ОДР для прямой задачи

Так как ограничения в прямой задаче имеют знак < и переменные > 0, то ограничения в двойственной задаче должны иметь знак > и переменные должны быть > 0. В соответствии с (9.8) ограничения двойственной задачи имеют вид:

Область допустимых решений для прямой задачи показана на рис. 9.1. Напомним, что оптимальными значениями были х, = 300, х2 = 200 при максимуме ЦФ^= 1400.

Область допустимых решений двойственной задачи показана на рис. 9.2. Минимум достигается при у, = 0,28, у2 0,57 и составляет w = 1400.

ОДР для двойственной задачи

Рис. 9.2. ОДР для двойственной задачи

Задача 2. Расчет диеты (7.28). Согласно правилам преобразования, двойственная задача будет иметь вид:

Для прямой задачи решение имеет вид Целевая функция в точке минимума принимает значение /= 56,2. Двойственная задача имеет решение

Смысл полученных двойственных задач будет пояснен ниже.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>