В состав п переменных х} входят также дополнительные переменные. Стандартная форма задачи ЛП предполагает выполнение следующих условий.

1. Все ограничения записаны в виде равенств с неотрицательной правой частью.

2. Все переменные неотрицательны.

3. Оптимизация определяется как максимизация или минимизация целевой функции.

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

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

1. Каждому из т ограничений прямой задачи соответствует переменная двойственной задачи.

2. Каждой из п переменных прямой задачи соответствует ограничение двойственной задачи.

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

4. Коэффициенты целевой функции двойственной задачи равны правым частям ограничений прямой задачи.

Графически эти правила представлены в табл. 4.1.

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

Таблица 4.2. Правила определения типа оптимизации и ограничений

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

Пример 4.1.1

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

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

Максимизировать z= 5xi + 12х2+4хз

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

Xi + 2X2 +Хз < 10,

2xi - хг + Зхз = 8,

Х1, Х2, Хз > 0.

Максимизировать

2= 5x1 + 12X2 + 4хз + Ох*

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

Х1 + 2X2 + Хз + х4 = 10, 2xi - хг + Зхз + 0х4 = 8,

Х1, Х2, Хз, Х4 0.

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

Минимизировать w = 10у, + 8у2

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

у, + 2у2>5, 2ух-у2>\2, у1 + 3у3>4,

у. + 0у, > 0, }

} => (у, > 0, у, - свободная переменная). у у2 -свободные]

Пример 4.1.2

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

Минимизировать г = 15xi + 12х2 Минимизировать z= 15xi + 12хг + Охз + 0х< при ограничениях при ограничениях

Х1 + 2X2 3, Х1 + 2X2 - Хз + 0X4= 3, /1

2xi - 4x2 < 5, 2xi - 4X2 + Охз + х4 = 5, уг

X1,X2>0. X1, Х2, Хз, Х4>0.

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

Максимизировать w = 3yt + 5у2

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

У, + 2у2<15, 2у,-4у2<12, -уОСилиуО), У20,

у у2 - свободные переменные (избыточное условие).

Пример 4.1.3

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

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

Двойственные переменные

Максимизировать г = 5xi + 6x2

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

xi + 2x2 = 5, -х1 + 5x2 > 3,

4xi + 7x2 < 8,

xi - свободная,

x2>0.

Подстановка дг, = дг* - х~ приводит к задаче:

максимизировать г = 5дг* - 5дг, + 6х2 при ограничениях

дг,+ - х[ + 2хг = 5,

- д,+ + дг, + 5x2 - хз =3,

4дг* - 4дг, + 7x2 + х4 = 8, дг,+, дг, , х2 > 0.

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

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

Минимизировать w = 5yl + Зу2 + 8у3

у,-у,+4у3>5 1 -у, + у2-4у3>-5\

2у1 + 5у2+7у3>6,

-у2>0у2<0,

У3*0,

у, - свободная переменная,

у2, у, - свободные переменные (избыточное условие).

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

УПРАЖНЕНИЯ 4.1

1. Для задачи из примера 4.1.1 запишите двойственную задачу, предполагая, что определяется не максимум целевой функции, а ее минимум.

2. В примере 4.1.2 сформулируйте двойственную задачу, предполагая, что в прямой задаче этого примера добавлено третье ограничение Зхх + х2 = 4.

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

4. Запишите двойственные задачи для следующих прямых задач ЛП.

a) Максимизировать z = -5л:, + 2х2

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