Учебная работа № 1391. Двойственный симплексметод и доказательство теоремы двойственности

1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (6 оценок, среднее: 4,67 из 5)
Загрузка...

Учебная работа № 1391. Двойственный симплексметод и доказательство теоремы двойственности

ФИНАНСОВАЯ АКАДЕМИЯ ПРИ ПРАВИТЕЛЬСТВЕ

РОССИЙСКОЙ ФЕДЕРАЦИИ

Кафедра математики

КУРСОВАЯ

на тему:

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

Студент группы МЭК 11 А.С. Кормаков

Научный руководитель Солодовников А.С.

МОСКВА – 2001

Содержание

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

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

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

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

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

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

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

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

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

В качестве примера рассмотрим задачу использования ресурсов. Предприятие имеет т видов ресурсов в количестве bi (i = 1, 2, …, m ) единиц, из которых производится n видов продукций. Для производ­ства 1 ед. i й продукции расходуется aij ед. tгo ресурса, а ее стоимость составляет Cj ед. Составить план выпуска продукции, обеспечивающий ее максимальный выпуск в стоимостном выражении. Обозначим через xj (j =1,2, …, n) количество ед. j й продукций, Тогда исходную задачу сформулируем так.

Найти вектор Х =(x1 , x2 , …, xn ), который удовлетворяет ограни­чениям

a11 x1 + a12 x2 + … + a1n xn £ b1,

a21 x1 + a22 x2 + … + a2n xn £ b2, xj ³ 0 (j =1,2, …, n)

…………………………………

am1 x1 + am2 x2 + … + amn xn £ bm,

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

Z = C1 x1 + C2 x2 + … + Cn xn ,

Оценим ресурсы, необходимые для изготовления продукции. За единицу стоимости ресурсов примем единицу стоимости выпускаемой продукции. Обозначим через у i (j =1,2, …, m) стоимость единицы i горесурса. Тогда стоимость всех затраченных ресурсов, идущих на изготовление единицы j й продукции, равна . Стоимость затрачен­ных ресурсов не может быть меньше стоимости окончательного продукта, поэтому должно выполняться неравенство ³Cj , j =1,2, …, n . Стоимость всех имеющихся ресурсов выразится величиной . Итак, двойственную задачу можно сформулировать следующим образом.

Найти вектор Y =(y1 , y2 , …, yn ), который удовлетворяет ограни­чениям

a11 y1 + a12 y2 + … + am1 ym £ C1,

a12 y1 + a22 y2 + … + am2 ym £ C2, yj ³ 0 (i =1,2, …, m)

…………………………………

a1n y1 + a2n y2 + … + amn ym £ Cm,

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

f = b1 y1 + b2 y2 + … + bm ym .

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

Исходная задача. Сколько и. какой продукции xj (j =1,2, …, n) необходимо произвести, чтобы при заданных стоимостях Cj (j =1,2, …, n) единицы продукции и размерах имеющихся ресурсов bi (i =1,2, …, n) максимизировать выпуск продукции в стоимостном выражении.

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

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

Многие задачи линейного программирования первоначально ста­вятся в виде исходных или двойственных задач, поэтому имеет смысл говорить о паре двойственных задач линейного программирования.

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

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

Исходная задача. Найти матрицустолбец X = (x1 , x2 , …, xn ), которая удовлетворяет ограничениям

(1.1) AX = A0 , Х ³0

и минимизирует линейную функцию Z = СХ .

Двойственная задача. Найти матрицустроку Y = (y1 , y2 , …, ym ), которая удовлетворяет ограничениям

(1.2) YA £ С

и максимизирует линейную функцию f = YA0

В обеих задачах C = (c1 , c2 , …, cn ) матрицастрока, A0 = (b1 , b2 , …, bm ) — матрицастолбец, А = (aij ) — матрица коэффициентов системы ограничений. Связь между оптимальными планами пары двой­ственных задач устанавливает следующая теорема.

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

min Z = max f.

Если линейная функция одной из задач не ограничена, то другая не имеет решения.

Д о к а з а т е л ь с т в о. Предположим, что исходная задача об­ладает оптимальным планом, который получен симплексным методом. Не нарушая общности, можно считать, что окончательный базис со­стоит из т первых векторов A 1 , A 2 , …, A m . Тогда последняя симплекс­ная таблица имеет вид табл. 1.1.

Т а б л и ц а 1.1

i Базис С базиса A0 C1 C2 Cm Cm+1 cn
A1 A2 Am Am+1 An

1

2

.

.

.

m

A1

A2

.

.

.

Am

C1

C2

.

.

.

Cm

x1

x2

.

.

.

xm

1

0

.

.

.

0

0

1

.

.

.

0

.

.

.

.

0

0

.

.

.

1

x1, m+1

x2, m+1

.

.

.

xm, m+1

.

.

.

x1n

x2n

.

.

.

xmn

m+1 Zi Cj Z0 Z1 – C1 Z2 – C2 Zm – Cm Zm+1 – Cm+1 Zn – Cn

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

(1.3) Aj = DXj (j= 1,2, ,.., n).

Для оптимального плана получаем

(1.4) A 0 =DX* ,

где X* = ( x * 1 , x * 2 , …, x * m ) .

Обозначим через матрицу, составленную из коэффициентов раз­ложения векторов А j (j = 1, 2, …, n), записанных в табл. 1.1. Тогда, учитывая соотношения (1.3) и (1.4), получаем:

(1.5) A =D , D1 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 ),С = (C1 , C2 , …, Cm , Cm+1 , …, Cn ), a = (C*X 1 – C1 ; С*Х 2 С2 , …, C*X n – Cn ) = (Z1 –С1 ; Z2 C2 ; …, Zn — Cn ) — вектор, компоненты которого неположительны, так как они совпадают с ZjCj £ 0, соответствующими оптимальному плану.

Оптимальный план исходной задачи имеет вид X* =D1 А 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*D1 A0 =C*X*=minZ(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) ³ +¥. Это выражение также лишено смысла, поэтому исходная задача не име­ет решений.

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

Исходная задача. Найти минимальное значение линейной функ­ции Z = x2 – x4 – 3x5 при ограничениях

x1 + 2x2 x4 + x5 = 1,

4x2 + x3 + 2x4 – x5 = 2, xij ³ 0 (j = 1, 2, …, 6)

3x2 + x5 + x6 = 5,

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

1 1 2 0 1 1 0

A0 = 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 = y1 + 2y2 +5y3 при ограничениях

y1 £ 0,

2y1 – 4y2 + 3y3 £ 1,

y2 £ 0,

y1 + 2y2 £ 1,

y1 – y2 + y3 £ 3,

y3 £ 0.

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

i Базис С базиса A0 0 1 0 1 3 0
A1 A2 A3 A4 A5 A6

1

2

3

A1

A3

A6

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 Zi Cj 0 0 1 0 1 3 0

1

2

3

A5

A3

A6

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 Zi Cj 3 3 7 0 4 0 0

1

2

3

A5

A4

A6

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 Zi Cj 15 7 1 4 0 0 0

1

2

3

A5

A4

A2

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 Zi Cj 46/3 19/3 0 11/3 0 0 1/3

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

1 1 2

D = ( A5 , A4 , A2 ) = 1 2 4

1 0 3

Обратная матрица D 1 образована из коэффициентов, стоящих в столбцах A1 , A3 , A6 четвертой итерации:

2 1 0

D1 = 1/3 1/3 2/3

2/3 1/3 1/3

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

2 1 0

Y = С* D1 = (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; y2 = 11/3 + 0 = 11/3; у 3 = 1/3+0 = 1/3. При этом плане max f = 46/3.

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

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

Исходная задача. Найти матрицустолбец Х = (x1 , x2 , …, xn ), которая удовлетворяет системе ограничений

(1.12). АХ0 , Х >0

и минимизирует линейнуюфункцию Z = СХ.

Двойственная задача. Найти матрицустроку Y = (y1 , y2 , …, yn ), которая удовлетворяет системе ограничений YA £C , Y ³0 и максимизирует линейную функцию f = YA 0 .

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

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

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

2x1 + 2x2 x3 ³ 2,

x1 x2 4x3 £ 3, xi ³ 0 (i=1,2,3)

x1 + x2 2x3 ³ 6,

2x1 + x2 2x3 ³ 3,

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

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

2y1 y2 + y3 + 2y4 £ 1,

2y1 + y2 + y3 + y4 ³ 2,

y1 + 4y2 2y3 2y4 ³ 3,

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

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

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

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

Оптимальный план исходной задачи находим, используя оценки ( m + 1)й строки последней итерации, стоящие в столбцах A5 , A6 , A7 : x1 = 3/2 + 0 = 3/2; x2 = 9/2 + 0 = 9/2; x3 = 0+ 0 = 0. При оптимальном плане исходной задачи X* = (3/2; 9/2; 0) линейная функ­ция достигает наименьшего значения: Zmin =21/2.

Т а б л и ц а 1.3

i Базис С базиса A0 2 3 6 3 0 0 0
A1 A2 A3 A4 A5 A6 A7

1

2

3

A5

A3

A7

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 Zi Cj 0 2 3 6 3 0 0 0

1

2

3

A3

A6

A7

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

A3

A2

A7

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 Zi Cj 21/2 10 0 0 9/2 3/2 9/2 0

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

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

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

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

Zmin = CX; f max = YA0 ;

AX = A0 ; YA £ С .

X ³ 0.

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

Zmax = CX; f min = YA0 ;

AX = A0 ; YA ³ С .

X ³ 0.

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

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

Zmin = CX; f max = YA0 ;

AX ³A0 ; YA £ С .

X ³ 0. Y ³ 0.

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

Zmax = CX; f min = YA0 ;

AX £A0 ; YA ³ С .

X ³ 0. Y ³ 0.

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

Найти минимальное значение линейной функции Z = 2x1 + x2 + 5x3 при ограничениях

x1 – x2 – x3 £ 4,

x1 – 5x2 + x3 ³ 5, xj ³ 0 (j = 1, 2, 3).

2x1 – x2 + 3x3 ³6,

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

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

Zmin = 2x1 + x2 + 5x3 при ограничениях

x1 + x2 + x3 ³ 4,

x1 – 5x2 + x3 ³ 5, xj ³ 0 (j = 1, 2, 3).

2x1 – x2 + 3x3 ³6,

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

f min = 4x1 + 5x2 + 6x3 при ограничениях

y1 + y2 + 2y3 £ 2,

y1 – 5y2 y3 £ 1, yi ³ 0 (i = 1, 2, 3).

2y1 + y2 + 3y3 £ 5,

Приведем без доказательства следующую теорему. Теорема 1.1. Если при подстановке компонент оптимального пла­на в систему ограничений исходной задачи ie ограничение обращается в неравенство, то iя компонента оптимального плана двойственной задачи равна нулю.

Если iя компонента оптимального плана двойственной задачи по­ложительна, то ie ограничение исходной задачи удовлетворяется ее оптимальным решением как строгое равенство.

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

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

Переход к двойственной задаче не обязателен, так как если рассмо­треть первую симплексную таблицу с единичным дополнительным ба­зисом, то легко заметить, что в столбцах записана исходная задача, а в строках двойственная. Причем оценками плана исходной задачи являются С j а оценками плана двойственной задачи – bi . Решим «двойственную задачу по симплексной таблице, в которой записана ис­ходная задача; найдем оптимальный план двойственной задачи, а вместе с ним и оптимальный план исходной задачи. Этот метод носит на­звание двойственного симплексного метода,

Пусть необходимо решить исходную задачу линейного программиро­вания, поставленную в общем виде: минимизировать функцию Z =СХ при АХ = A0 , Х ³ 0. Тогда в двойственной задаче необходимо максимизировать функцию f = YA 0 при YA £ С. Допустим, что выбран такой базис D = (A 1 , А 2 , …, А i , …, А m ), при котором хотя бы одна из компонент вектора Х = D 1 A0 = (x1 , x2 , …, xi , …, xm ) отрицатель­ная (например, xi < 0), но для всех векторов Aj выполняется соотно­шение Zj – Cj £ 0 (i = 1,2, …, n). Тогда на основании теоремы двойственности Y = С баз D1 план двойственной задачи. Этот план не оптимальный, так как, с одной стороны, при выбранном бази­се X содержит отрицательную компоненту и не является планом исходной задачи, а с другой стороны, оценки оптимального плана двой­ственной задачи должны быть неотрицательными.

Таким образом, вектор Аi , соответствующий компоненте xi < 0, следует исключить из базиса исходной задачи, а вектор, соответствую­щий отрицательной оценке,— включить в базис двойственной задачи.

Для выбора вектора, включаемого в базис исходной задачи, просмат­риваем i ю строку: если в ней не содержатся x ij < 0, то линейная функция двойственной задачи не ограничена на многограннике реше­ний, а исходная задача не имеет решений. Если же некоторые x ij < 0, то для столбцов, содержащих эти отрицательные значения, вычисля­ем q0j = min (xi /xij ) ³ 0 и определяем вектор, соответствующий maxq0j (Zj — Cj ) при решении исходной задачи на минимум и minq0j (Zj — Cj )при решении исходной задачи на максимум. Этот вектор и включаем в базис исходной задачи. Вектор, который необ­ходимо исключить из базиса исходной задачи, определяется направ­ляющей строкой.

Если q0j = min (xi /xij ) = 0, т. е. xi = 0, то x ij берется за раз­решающий элемент только в том случае, если x ij > 0. Такой выбор раз­решающего элемента на данном этапе не приводит к увеличению коли­чества отрицательных компонент вектора X . Процесс продолжаем до получения Х ³ 0; при этом находим оптимальный план двойственной задачи, следовательно, и оптимальный план исходной задачи.

В процессе вычислений по алгоритму двойственного симплексного метода условие Zj – Cj £ 0 можно не учитывать до исключения всех х i < 0, затем оптимальный план находится обычным симплексным ме­тодом. Это удобно использовать, если все х i < 0; тогда для перехода к плану исходной, задачи за одну итерацию необходимо q0j определить не по минимуму, а по максимуму отношений, т. е. q0j = max (xi /xij ) > 0.

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

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

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

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

Учебная работа № 1391. Двойственный симплексметод и доказательство теоремы двойственности