Двойственный симплекс-метод и доказательство теоремы двойственности

ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД И ДОКАЗАТЕЛЬСТВО ТЕОРЕМЫ ДВОЙСТВЕННОСТИ

Содержание

1. ВаВа Двойственность в линейном программировании

2. Ва Несимметричные двойственные задачи. Теорема двойственности

3. Ва Симметричные двойственные задачи

4. Ва Виды математических моделей двойственных задач

5. Ва Двойственный симплексный метод

6. Ва Список используемой литературы

Двойственность в линейном программировании

Двойственная задача тесно связана задачей линейного программирования. Задача первоначальная называется исходной

Решение двойВнственной задачи может быть получено из решения исходной и наоборот

Связующим фактом этих двух задач являются коэффициВненты C j Ва функции исходной задачи. Данные коэффициенты называются свободными членами системы ограничений двойственной задачи. Коэффициенты B i систеВнмы ограничений исходной задачи называются коэффициентами двойственной задачи. Транспонированная матрица коэффициентов системы ограничений исходной задачи является матрицей коэффициентов системы ограниВнчений двойственной задачи

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

Ва У предприятия есть т видов ресурсов в количестве b i ( i = 1, 2, .., m ) единиц, из которых выпускается n видов продукции. На изготовление1 ед. i -й продукции тратится a ij ед. t-гo ресурса, ее стоимость составляет C j ед. Необходимо определить план выпуска продукции, обеспечивающий ее максимальный выпуск в стоимостном выражении. Примем за x j (j =1,2, .., n) количество ед. j -й продукций

Сформулируем исходную задачу. Определить вектор Х =( x 1 , x 2 , тАж, x n ), который удовлетворяет ограниВнчениям

a 11 x 1 + a 12 x 2 + тАж + a 1n x n РИ b 1,

a 21 x 1 + a 22 x 2 + тАж + a 2n x n РИ b 2, ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа x j i 0 (j =1,2, .., n)

тАжтАжтАжтАжтАжтАжтАжтАжтАжтАжтАжтАжтАж

a m 1 x 1 + a m 2 x 2 + тАж + a mn x n РИ b m ,

Ва

и состовляет максимальное значение линейной функции

Z = C 1 x 1 + C 2 x 2 + тАж + C n x n ,

Определим ресурсы, которые потребуются для изготовления товара. Обозначим за единицу стоимости ресурсов единицу стоимости выпускаемого товара. А через у i (j =1,2, .., m) стоимость единицы i -го ресурса. Т.е. стоимость всех затраченных ресурсов, которые используются для изобретения единицы j -й продукции, состовляет . Цена израсходованных ресурсов не должна превышать цены окончательного товара. Таким образом должно выполняться неравенство i C j , j =1,2, .., n. Цена имеющихся ресурсов составляет

Сформулируем Ва двойственную задачу

Необходимо определить вектор Y =( y 1 , y 2 , тАж, y n ), удовлетворяющий ограниВнчениям

a 11 y 1 + a 12 y 2 + тАж + a m1 y m РИ C 1,

a 12 y 1 + a 22 y 2 + тАж + a m2 y m РИ C 2, ВаВаВа y j i 0 (i =1,2, .., m)

тАжтАжтАжтАжтАжтАжтАжтАжтАжтАжтАжтАжтАж

a 1n y 1 + a 2n y 2 + тАж + a mn y m РИ C m ,

Вектор Ва Y =( y 1 , y 2 , тАж, y n ) состовляет минимальное значение линейной функции

f Ва = b 1 y 1 + b 2 y 2 + тАж + b m y m

Переменные у i называются оценками или учетными, неявными ценами

С экономической точки зрения двойственную задачу можно интерпретировать так: какова должна быть цена едиВнницы каждого из ресурсов, чтобы при заданных количествах ресурсов b i и величинах стоимости единицы продукции C i минимизировать общую стоимость затрат?

А исходную задачу определим следующим образом: сколько и. какой продукции x j Ва (j =1,2, .., n) необходимо произвести, чтобы при заданных стоимостях C j Ва (j =1,2, .., n) единицы продукции и размерах имеющихся ресурсов b i Ва (i =1,2, .., n) максимизировать выпуск продукции в стоимостном выражении

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

Несимметричные двойственные задачи. Теорема двойственности.

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

Ва Чтобы проще понимать постановку задачи будем интерпретировать ее в матричной форме

Сформулируем Ва двойственную задачу

Ва Необходимо определить матрицу-строку Y = ( y 1 , y 2 , тАж, y m ), которая максимизирует линейную функцию f = YA 0 Ва и удовлетворяет ограничениям (1.1) YA РИ С.

Сформулируем исходную задачу. Определить матрицу-столбец X = ( x 1 , x 2 , тАж, x n ), которая минимизирует линейную функцию Z = СХ и удовлетворяет ограничениям (1.2) AX = A 0 , Х i 0

Как в исходной так и в двойственной задачах А = ( a ij ) тАФ матрица коэффициентов системы ограничений, A 0 = ( b 1 , b 2 , тАж, b m ) тАФ матрица-столбец, C = ( c 1 , c 2 , тАж, c n ) - матрица-строка

Теорема двойственности устанавливает связь между оптимальными планами пары двойВнственных зада

Теорема двойственности гласит: если из пары двойственВнных задач одна обладает оптимальным планом, то и другая имеет реВншение, причем для экстремальных значений линейных функций выполВнняется соотношение min Z = max f . Если линейная функция одной из задач не ограничена, то другая не имеет решения

Доказательство. Будем считать, что исходная задача имеет оптимальный план. План определен симплексным методом. Можно считать, что конечный базис соВнстоит из т первых векторов A 1 , A 2 , .., A m . Таким образом, симплексВнная таблица примет вид, приведенный в табл. 1.1

Таблица 1.1

Ва i	Базис	С базиса	A 0	C 1	C 2	тАж	C m	C m+1	тАж	c n
A 1	A 2	тАж	A m	A m+1	тАж	A n
1 2 m	A 1 A 2 A m	C 1 C 2 C m	x 1 x 2 x m	1 0 0	0 1 0		0 0 1	x 1, m+1 x 2, m+1 x m, m+1	тАж тАж тАж	x 1n x 2n x mn
m+1	Z i - C j	Z 0	Z 1 тАУ C 1	Z 2 тАУ C 2		Z m тАУ C m	Z m+1 тАУ C m+1	тАж	Z n тАУ C n

Ва

Будем считать, что D является матрицей, составленной из компонент векторов конечного базиса A 1 , A 2 , .., A m . Ва Приведенная выше таблица состоит из коэффициВнентов разложения векторов A 1 , A 2 , .., A n исходной системы по вектоВнрам базиса. Ва В этой таблице каждому вектору A j соответствует Ва вектор X j

Найдем оптимальный план:

(1.3) ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа A 0 = DX*,

где X* = ( x * 1 , x * 2 , тАж, x * m )

Получим:

(1.4) A j = DX j ( j = 1,2, ,., n)

Ва - это матрица, составленная из коэффициентов разВнложения векторов А j ( j = 1, 2, .., n ), представленных в приведенной выше таблице

Используя соотношения (1.3) и (1.4), получаем:

(1.5) ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа A = D , Ва D -1 A = ,

(1.6) ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа A 0 =DX*; Ва D -1 A 0 = X*,

(1.7) ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа min Z= C*X*,

(1.8) ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа = C* тАФC РИ 0,

где С* = ( C * 1 , C * 2 , тАж, C * m ), С = ( C 1 , C 2 , тАж, C m , C m +1 , тАж, C n ), a Ва = (C*X 1 тАУ C 1 ; С*Х 2 Ва - С 2 , .., C*X n тАУ C n ) = (Z 1 тАУ С 1 ; Z 2 Ва - C 2 ; .., Z n тАФ C n ) тАФ вектор, компоненты которого неположительны, так как они совпадают с Z j тАФ C j Ва РИ 0, соответствующими оптимальному плану

Оптимальный план исходной задачи имеет вид X* = D -1 А 0 , поэтому оптимальный план двойственной задачи ищем в виде

(1.9) ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа Y* = C*D -1

Покажем, что Y* действительно план двойственной задачи. Для этого ограничения (1.2) запишем в виде неравенства YA тАФ С РИ 0, в левую часть которого подставим Y*. Тогда на основании (1.9), (1.5) и (1.8) получим

Y * А тАУ С = С* D -1 А тАУ С = С* Ва - С РИ 0,

откуда находим Y*A РИ С

Так как Y* удовлетворяет ограничениям (1.2), то это и есть план двойственной задачи. При этом плане значение линейной функции двойВнственной задачи f (Y*) = Y*A 0 . Учитывая соотношения (1.9), (1.6) и (1.7), имеем

(1.10) ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа f (Y*) = Y*A 0 = C * D -1 A 0 = C*X* = min Z(X)

Таким образом, значение линейной функции двойственной задачи от Y* численно равно минимальному значению линейной функции исходной задачи

Докажем теперь, что Y* является оптимальным планом. Умножим (1.1) на любой план Y двойственной задачи, а (1.2) тАФ на любой план X исходной задачи: YAX=YA 0 = f (Y), YAX РИ СХ = Z (X), отсюда следует, что для любых планов Х и Y выполняется неравенство

(1.11) ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа f (Y) РИ Z (X)

Этим же соотношением связаны и экстремальные значения max f (Y) РИ Ва min Z (Х). Из последнего неравенства заключаем, что максимальВнное значение линейной функции достигается только в случае, если max f (Y) = min Z (X), но это значение [см. (1.10)] f (Y) достигает при плане Y*, следовательно, план Y* тАФ оптимальный план двойственной задачи

Аналогично можно доказать, что если двойственная задача имеет решение, то исходная также обладает решением и имеет место соотноВншение max f (Y) = min Z (X)

Для доказательства второй части теоремы допустим, что линейная функция исходной задачи не ограничена снизу. Тогда из (1.11) следуВнет, что f ( Y ) РИ - ТР . Это выражение лишено смысла, следовательно, двойственная задача не имеет решений

Аналогично предположим, что линейная функция двойственной заВндачи не ограничена сверху. Тогда из (1.11) получаем, что Z (X) i + ТР . Это выражение также лишено смысла, поэтому исходная задача не имеВнет решений

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

Исходная задача. Найти минимальное значение линейной функВнции Z = x 2 тАУ x 4 тАУ 3 x 5 при ограничениях

Ва

x 1 + 2x 2 ВаВаВаВаВаВаВаВаВа - x 4 + x 5 Ва = 1,

- 4x 2 + x 3 + 2x 4 тАУ x 5 = 2, Ва x ij i 0 (j = 1, 2, тАж, 6)

ВаВа 3x 2 Ва + x 5 + x 6 = 5,

Здесь матрица-строка С = (0;. 1; 0; тАФ1; тАФ 3, 0), матрица-столбец

ВаВаВаВаВаВаВаВаВаВаВаВа 1 ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа 1 ВаВаВа 2 ВаВаВа 0 ВаВаВа -1 ВаВаВа 1 ВаВаВа 0

A 0 = ВаВаВаВаВа 2 ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа A = ВаВаВаВаВаВа 0 ВаВа -4 ВаВаВа 1 ВаВаВаВа 2 ВаВа -1 ВаВаВа 0

ВаВаВаВаВаВаВаВаВаВаВаВа 3 ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа ВаВаВаВа 0 ВаВаВа 3 ВаВаВа 0 ВаВаВаВа 0 ВаВаВа 1 ВаВаВа 1

Ва

ВаВаВаВаВаВаВаВаВаВаВаВаВа 1 ВаВаВаВа 0 ВаВаВаВа 0

ВаВаВаВаВаВаВаВаВаВаВаВаВа 2 ВаВаВа -4 ВаВаВаВа 3

A тАЩтАЩ = ВаВаВаВаВаВа 0 ВаВаВаВа 1 ВаВаВаВа 0

ВаВаВаВаВаВаВаВаВаВаВаВа -1 ВаВаВаВа 2 ВаВаВаВа 0

ВаВаВаВаВаВаВаВаВаВаВаВаВа 1 ВаВаВа -1 ВаВаВаВа 0

ВаВаВаВаВаВаВаВаВаВаВаВаВа 0 ВаВаВаВа 0 ВаВаВаВа 1

Двойственная задача. Найти максимальное значение линейной функции f = y 1 + 2 y 2 +5 y 3 при ограничениях

Ва y 1 РИ 0,

2y 1 тАУ 4y 2 + 3y 3 РИ 1,

ВаВаВаВаВаВаВаВаВаВа y 2 ВаВаВаВаВаВаВаВаВаВа РИ 0,

-y 1 + 2y 2 ВаВаВаВаВаВаВаВаВаВа РИ -1,

y 1 тАУ ВаВа y 2 + ВаВаВа y 3 Ва РИ -3, ВаВа y 3 Ва РИ 0

Решение исходной задачи ВаВа находим ВаВа симплексным ВаВа методом (табл. 1.2)

i	Базис	С базиса	A 0	0	1	0	-1	-3	0
A 1	A 2	A 3	A 4	A 5	A 6
1 2 3	A 1 A 3 A 6	0 0 0	1 2 5	1 0 0	2 -4 3	0 1 0	-1 2 0	1 -1 1	0 0 1
m + 1	Z i - C j	0	0	-1	0	1	3	0
1 2 3	A 5 A 3 A 6	-3 0 0	1 3 4	1 1 -1	2 -2 1	0 1 0	-1 1 1	1 0 0	0 0 1
m + 1	Z i - C j	-3	-3	-7	0	4	0	0
1 2 3	A 5 A 4 A 6	-3 -1 0	4 3 1	2 1 -2	0 -2 3	1 1 -1	0 1 0	1 0 0	0 0 1
m + 1	Z i - C j	-15	-7	1	-4	0	0	0
1 2 3	A 5 A 4 A 2	-3 -1 1	4 11/3 1/3	3 -1/3 -2/3	0 0 1	1 1/3 -1/3	0 1 0	1 0 0	0 2/3 1/3
m + 1	Z i - C j	-46/3	-19/3	0	-11/3	0	0	-1/3

Оптимальный план исходной задачи X* = (0; 1/3; 0; 11/3; 4; 0), при котором Z min = - 46/3, получен в четвертой итерации табл. 1.2. Используя эту итерацию, найдем оптимальный план двойственной задачи. Согласно теореме двойственности оптимальный план двойственВнной задачи находится из соотношения Y* = C*D -1 , где матрица D -1 - матрица, обратная матрице, составленной из компонент векторов, вхоВндящих в последний базис, при котором получен оптимальный план исходной задачи. В последний базис входят векторы A 5 , A 4 , A 2 ; значит,

ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа 1 Ва -1 ВаВаВа 2

D = ( A 5 , A 4 , A 2 ) = ВаВаВаВаВа -1 ВаВа 2 ВаВа -4

ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа ВаВаВаВаВаВаВаВаВаВаВа 1 ВаВа 0 ВаВаВа 3

Обратная матрица D -1 образована из коэффициентов, стоящих в столбцах A 1 , A 3 , A 6 четвертой итерации:

ВаВаВаВаВаВаВаВаВаВаВаВаВаВа 2 ВаВаВаВаВаВа 1 ВаВаВаВаВаВа 0

D -1 = ВаВаВаВа -1/3 ВаВаВа 1/3 ВаВаВа 2/3

ВаВаВаВаВаВаВаВаВаВаВаВа -2/3 ВаВа -1/3 ВаВаВа 1/3

Из этой же итерации следует С* = (тАФ 3; тАФ1; 1). Таким образом

Ва

Ва Ва ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа ВаВаВа 2 ВаВаВаВаВаВа 1 ВаВаВаВаВаВа 0

ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа Y = С* D -1 = (-3; -1; 1) ВаВаВаВаВа -1/3 ВаВаВа 1/3 ВаВаВа 2/3

ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа -2/3 ВаВа -1/3 ВаВаВа 1/3

Y*=(-19/3; -11/3; -1/3),

т. е. y i = С*Х i , где Х i тАФ коэффициенты разложения последней итеВнрации, стоящие в столбцах векторов первоначального единичного базиса

Итак, i -ю двойственную переменную можно получить из значения оценки ( m + 1)-й строки, стоящей против соответствующего вектора, входившего в первоначальный единичный бази c , если к ней прибаВнвить соответствующее значение коэффициента линейной функции:

у 1 = тАФ 19/3 + 0 = тАФ 19/3; Ва y 2 = -11/3 + 0 = -11/3; у 3 = -1/3+0 = -1/3. При этом плане max f = -46/3

Симметричные двойственные задачи

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

Исходная задача. Найти матрицу-столбец Х = ( x 1 , x 2 , тАж, x n ), которая удовлетворяет системе ограничений

(1.12). ВаВа АХ>А 0 , Х>0 и минимизирует линейную функцию Z = СХ

Двойственная задача. Найти матрицу-строку Y = ( y 1 , y 2 , тАж, y n ), которая удовлетворяет системе ограничений YA РИ C, Y i 0 и максимизирует линейную функцию f = YA 0

Систему неравенств с помощью дополнительных переменных можВнно преобразовать в систему уравнений, поэтому всякую пару симметВнричных двойственных задач можно преобразовать в пару несимметричВнных, для которых теорема двойственности уже доказана

Используя симметричность, можно выбрать задачу, более удобВнную для решения. Объем задачи, решаемой с помощью ЭВМ, ограниВнчен числом включаемых строк, поэтому задача, довольно громоздкая в исходной постановке, может быть упрощена в двойственной формулиВнровке. При вычислениях без помощи машин использование двойственВнности упрощает вычисления

Исходная задача. Найти минимальное значение линейной функции Z = x 1 + 2 x 2 + 3 x 3 при ограничениях

Ва 2x 1 + 2x 2 - x 3 i 2,

ВаВа x 1 - x 2 - 4x 3 Ва РИ -3, ВаВаВаВаВаВаВаВаВаВаВа x i i 0 (i=1,2,3)

ВаВа x 1 + x 2 - 2x 3 i 6,

Ва 2 x 1 + x 2 - 2 x 3 i 3,

Очевидно, для того чтобы записать двойственную задачу, сначала необходимо систему ограничений исходной задачи привести к виду (1.12). Для этого второе неравенство следует умножить на -1

Двойственная задача. Найти максимум линейной функции f = 2 y 1 + 3 y 2 + 6 y 3 + 3 y 4 при ограничениях

2y 1 Ва - y 2 Ва + y 3 + 2y 4 Ва РИ 1,

2y 1 + y 2 Ва + y 3 + Ва y 4 ВаВа i 2,

Ва -y 1 + 4y 2 - 2y 3 - 2y 4 i 3,

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

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

Двойственную задачу решаем симплексным методом (табл. 1.3)

Оптимальный план двойственной задачи Y* = (0; 1/2; 3/2; 0), f max = 21/2

Оптимальный план исходной задачи находим, используя оценки ( m + 1)-й строки последней итерации, стоящие в столбцах A 5 , A 6 , A 7 : x 1 = 3/2 + 0 = 3/2; x 2 = 9/2 + 0 = 9/2; x 3 = 0 + 0 = 0. При оптимальном плане исходной задачи X* = (3/2; 9/2; 0) линейная функВнция достигает наименьшего значения: Z min =21/2

Т а б л и ц а 1.3

i	Базис	С базиса	A 0	2	3	6	3	0	0	0
A 1	A 2	A 3	A 4	A 5	A 6	A 7
1 2 3	A 5 A 3 A 7	0 0 0	1 2 3	2 2 -1	-1 1 4	1 1 -2	2 -1 -2	1 0 0	0 1 0	0 0 1
m + 1	Z i - C j	0	-2	-3	-6	-3	0	0	0
1 2 3	A 3 A 6 A 7	6 0 0	1 1 5	2 0 3	-1 2 6	1 0 0	2 -1 2	1 -1 2	0 1 0	0 0 1
m + 1	Zi - Cj	6	10	-9	0	9	6	0	0
1 2 3	A 3 A 2 A 7	6 3 0	3/2 РЕ 2	2 0 3	0 1 0	1 0 0	3/2 -1/2 4	РЕ -1/2 5	РЕ РЕ 3	0 0 1
m + 1	Z i - C j	21/2	10	0	0	9/2	3/2	9/2	0

Ва

Виды математических моделей двойственных задач

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

Симметричные задачи

(1) Исходная задача ВаВаВаВаВаВаВаВаВаВаВа Двойственная задача

ВаВаВаВаВаВаВаВаВаВа Z min = CX; ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа ВаВа f max = YA 0 ;

ВаВаВаВаВаВаВаВаВаВаВа AX i A 0 ; ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа YA РИ С

ВаВаВаВаВаВаВаВаВаВаВаВа X i 0. ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа Y i 0

Ва (2) Исходная задача ВаВаВаВаВаВаВаВаВаВаВаВа Двойственная задача

ВаВаВаВаВаВаВаВаВаВа Z max = CX; ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа f min = YA 0 ;

ВаВаВаВаВаВаВаВаВаВаВа AX РИ A 0 ; ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа YA i С

ВаВаВаВаВаВаВаВаВаВаВаВа X i 0. ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа Y i 0

Несимметричные задачи

(3) Исходная задача ВаВаВаВаВаВаВаВаВаВаВа Двойственная задача

ВаВаВаВаВаВаВаВа Z min = CX ; ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа f max = YA 0 ;

ВаВаВаВаВаВаВаВаВаВаВа AX = A 0 ; ВаВаВаВаВаВаВаВаВаВаВаВаВа ВаВаВаВаВаВаВаВаВаВаВаВа YA РИ С

ВаВаВаВаВаВаВаВаВаВаВаВа X i 0

(4) Исходная задача ВаВаВаВаВаВаВаВаВаВаВа Двойственная задача

ВаВаВаВаВаВаВаВаВаВа Z max = CX; ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа f min = YA 0 ;

ВаВаВаВаВаВаВаВаВаВаВа AX = A 0 ; ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа YA i С

ВаВаВаВаВаВаВаВаВаВаВаВа X i 0

Ва

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

Приведем пример математичеВнской модели двойственной задачи для следующей исходной

Следует определить минимальное значение линейной функции Z = 2 x 1 + x 2 + 5 x 3 при ограничениях:

x 1 тАУ Ва x 2 тАУ ВаВа x 3 Ва РИ 4,

x 1 тАУ Ва 5 x 2 + x 3 Ва i 5, ВаВа x j i 0 ( j = 1, 2, 3)

2 x 1 тАУ x 2 + 3 x 3 i 6,

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

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

Исходная задача:

Z min = 2 x 1 + x 2 + 5 x 3 при ограничениях

- x 1 + Ва x 2 + ВаВа x 3 i -4,

x 1 тАУ Ва 5 x 2 + x 3 Ва i 5, ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа x j i 0 ( j = 1, 2, 3)

2 x 1 тАУ x 2 + 3 x 3 i 6,

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

f min = -4 x 1 + 5 x 2 + 6 x 3 при ограничениях

-y 1 + Ва y 2 + Ва 2y 3 РИ 2,

y 1 Ва тАУ 5y 2 Ва - Ва y 3 Ва РИ 1, ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа y i i 0 (i = 1, 2, 3)

2y 1 + y 2 + 3y 3 РИ 5,

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

Двойственный симплексный метод

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

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

b i являются оценками плана двойственной задачи. С j являются оценками плана исходной задачи

Найдем решение двойственной задачи по симплексной таблице. В симплексной таблице прописана исВнходная задача. Также определим оптимальный план двойственной задачи. Также найдем и оптимальный план исходной задачи

Такой метод принято называть двойственным симплексным методом

Допустим Ва нужно определить исходную задачу линейного программироВнвания, которая поставлена в общем виде: минимизировать функцию Z =СХ при АХ = A 0 , Х i 0. Значит в двойственной задаче следует максимизировать функцию f = YA 0 при YA РИ С. Пусть определен следующий базис D = (A 1 , А 2 , .., А i , .., А m ),. Причем в нем хотя бы одна из компонент вектора Х = D -1 A 0 = (x 1 , x 2 , .., x i , .., x m ) отрицательВнная. Для всех векторов A j используется следующее соотноВншение Z j тАУ C j РИ 0 (i = 1,2, .., n )

Пользуясь теоремой двойственности, Y = С баз D -1 является планом двойственной задачи. Этот план не оптимальный. Потому что оценки оптимального плана двойВнственной задачи должны быть неотрицательными и выбранный базиВнс X содержит отрицательную компоненту и не является планом исходной задачи, а с другой стороны

Поэтому, следует исключить из базиса исходной задачи вектор А i , который соответствует компоненте x i < 0. Ва Данный вектор относится к отрицательной оценке, его необходимо включить в базис двойственной задачи

ПросматВнриваем i -ю строку для выбора вектора, включаемого в базис исходной задачи. Т.е. если строка не имеет Ва x ij < 0, тогда линейная функция двойственной задачи не ограничена на многограннике решеВнний. Поэтому нет решений исходной задачи

В противном случае для столбцов, имеющих отрицательные значения, определяем q 0 j = min ( x i / x ij ) i 0 . Также находим вектор, который соответствует min q 0 j (Z j тАФ C j ) при решении исходной задачи на максимум, а также max q 0 j (Z j тАФ C j ) при значении исходной задачи на минимум

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

Допустим, что q 0 j = min ( x i / x ij ) = 0, т. е. x i = 0, тогда x ij Ва выбирается как разВнрешающий элемент, но лишь тогда, когда x ij > 0

Данный подход к решению задачи не приводит к росту колиВнчества отрицательных компонент вектора X. Пока не будет получено Х i 0, процесс не прекращается

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

Используя при решении, алгоритм двойственного симплексного метода условие Z j тАУ C j РИ 0 допускается не учитывать, пока не будут исключены все х i < 0

Обычным симплексным меВнтодом определяется оптимальный план. Этот метод обычно используется при условии, что все х i < 0. Чтобы перейти к плану исходной, задачи за одну итерацию надо определить q 0 j = m ax ( x i / x ij ) > 0

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

Список используемой литературы

Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. тАЬНаукатАЭ, 1980 г

Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. тАЬФинансы и статистикатАЭ, 1998 г

Вместе с этим смотрят:

Декарт
Десятично-двоичный сумматор
Десятичные дроби
Дзета-функция Римана