Каталог :: Математика

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

                      ФИНАНСОВАЯ АКАДЕМИЯ ПРИ ПРАВИТЕЛЬСТВЕ                      
                              РОССИЙСКОЙ ФЕДЕРАЦИИ                              
                               Кафедра математики                               
     

КУРСОВАЯ

на тему: Двойственный симплекс-метод и доказательство теоремы двойственности. Студент группы МЭК 1-1 - А.С. Кормаков Научный руководитель - Солодовников А.С. МОСКВА – 2001 Содержание 1. Двойственность в линейном программировании................................3 2. Несимметричные двойственные задачи. Теорема двойственности....... 4 3. Симметричные двойственные задачи...........................................9 4. Виды математических моделей двойственных задач............................11 5. Двойственный симплексный метод............................................12 6. Список используемой литературы............................................14

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

Понятие двойственности. С каждой задачей линейного программирования тесно связана другая линейная задача, называемая двойственной. Первоначальная задача называется исходной. Связь исходной и двойственной задач состоит в том, что коэффици­енты Cj функции цели исходной задачи являются свободными членами системы ограничений двойственной задачи, свободные члены Bi систе­мы ограничений исходной задачи служат коэффициентами функции цели двойственной задачи, а матрица коэффициентов системы ограни­чений двойственной задачи является транспонированной матрицей коэффициентов системы ограничений исходной задачи. Решение двой­ственной задачи может быть получено из решения исходной и наоборот. В качестве примера рассмотрим задачу использования ресурсов. Предприятие имеет т видов ресурсов в количестве bi (i = 1, 2, ..., m) единиц, из которых производится n видов продукций. Для производ­ства 1 ед. i-й продукции расходуется aij ед. t-гo ресурса, а ее стоимость составляет Cj ед. Составить план выпуска продукции, обеспечивающий ее максимальный выпуск в стоимостном выражении. Обозначим через xj (j =1,2, ..., n) количество ед. j-й продукций, Тогда исходную задачу сформулируем так. Найти вектор Х =(x1, x2, ., xn), который удовлетворяет ограни­чениям a11x1 + a12x2 + . + a1nxn £ b1, a21x1 + a22x2 + . + a2nx n £ b2, xj ³ 0 (j =1,2, ..., n) ............. am1x1 + am2x2 + . + amnxn £ bm, и доставляет максимальное значение линейной функции Z = C1x1 + C2x2 + . + Cnxn, Оценим ресурсы, необходимые для изготовления продукции. За единицу стоимости ресурсов примем единицу стоимости выпускаемой продукции. Обозначим через у i (j =1,2, ..., m) стоимость единицы i-го ресурса. Тогда стоимость всех затраченных ресурсов, идущих на изготовление единицы j -й продукции, равна . Стоимость затрачен­ных ресурсов не может быть меньше стоимости окончательного продукта, поэтому должно выполняться неравенство ³ Cj, j =1,2, ..., n. Стоимость всех имеющихся ресурсов выразится величиной . Итак, двойственную задачу можно сформулировать следующим образом. Найти вектор Y =(y1, y2, ., yn), который удовлетворяет ограни­чениям a11y1 + a12y2 + . + am1ym £ C1, a12y1 + a22y2 + . + am2y m £ C2, yj ³ 0 (i =1,2, ..., m) ............. a1ny1 + a2ny2 + . + amnym £ Cm, и доставляет минимальное значение линейной функции f = b1y1 + b2y2 + . + bmym. Рассмотренные исходная и двойственная задачи могут быть эко­номически интерпретированы следующим образом. Исходная задача. Сколько и. какой продукции xj (j =1,2, ..., n) необходимо произвести, чтобы при заданных стоимостях C j (j =1,2, ..., n) единицы продукции и размерах имеющихся ресурсов bi (i =1,2, ..., n) максимизировать выпуск продукции в стоимостном выражении. Д в о й с т в е н н а я з а д а ч а. Какова должна быть цена еди­ницы каждого из ресурсов, чтобы при заданных количествах ресурсов bi и величинах стоимости единицы продукции Ci минимизировать общую стоимость затрат? Переменные уi называются оценками или учетными, неявными ценами. Многие задачи линейного программирования первоначально ста­вятся в виде исходных или двойственных задач, поэтому имеет смысл говорить о паре двойственных задач линейного программирования. 2. Несимметричные двойственные задачи. Теорема двойственности. В несимметричных двойственных задачах система ограничений исходной задачи задается в виде равенств, а двойственной — в виде нера­венств, причем в последней переменные могут быть и отрицательными. Для простоты доказательств постановку задачи условимся записывать в матричной форме. Исходная задача. Найти матрицу-столбец X = (x1, x 2, ., xn), которая удовлетворяет ограничениям (1.1) AX = A0, Х ³ 0 и минимизирует линейную функцию Z = СХ. Двойственная задача. Найти матрицу-строку Y = (y1, y 2, ., ym), которая удовлетворяет ограничениям (1.2) YA £ С и максимизирует линейную функцию f = YA0 В обеих задачах C = (c1, c2, ., cn) - матрица-строка, A0 = (b1, b2, ., b m) — матрица-столбец, А = (aij) — матрица коэффициентов системы ограничений. Связь между оптимальными планами пары двой­ственных задач устанавливает следующая теорема. Теорема (теорема двойственности). Если из пары двойствен­ных задач одна обладает оптимальным планом, то и другая имеет ре­шение, причем для экстремальных значений линейных функций выпол­няется соотношение min Z = max f. Если линейная функция одной из задач не ограничена, то другая не имеет решения. Д о к а з а т е л ь с т в о. Предположим, что исходная задача об­ладает оптимальным планом, который получен симплексным методом. Не нарушая общности, можно считать, что окончательный базис со­стоит из т первых векторов A1, A2, ..., Am. Тогда последняя симплекс­ная таблица имеет вид табл. 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 — матрица, составленная из компонент векторов оконча­тельного базиса A1, A2, ..., Am ; тогда табл. 1.1 состоит из коэффици­ентов разложения векторов A1 , A2, ..., An исходной системы по векто­рам базиса, т. е. каждому вектору Aj в этой таблице соответствует та­кой вектор Xj что (1.3) Aj = DXj (j= 1,2, ,.., n). Для оптимального плана получаем (1.4) A0 = DX*, где X* = (x*1, x*2, ., x*m). Обозначим через матрицу, составленную из коэффициентов раз­ложения векторов Аj (j = 1, 2, ..., n), записанных в табл. 1.1. Тогда, учитывая соотношения (1.3) и (1.4), получаем: (1.5) A = D, D-1A = , (1.6) A0=DX*; D-1A0 = 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*X1 – C1; С*Х2 - С2 , ..., C*Xn – Cn) = (Z1 – С1 ; Z2 - C2; ..., Zn — Cn) — вектор, компоненты которого неположительны, так как они совпадают с Zj Cj £ 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*A0. Учитывая соотношения (1.9), (1.6) и (1.7), имеем (1.10) f (Y*) = Y*A0 = C*D-1 A0 = C*X* = min Z(X). Таким образом, значение линейной функции двойственной задачи от Y* численно равно минимальному значению линейной функции исходной задачи. Докажем теперь, что Y* является оптимальным планом. Умножим (1.1) на любой план Y двойственной задачи, а (1.2) — на любой план X исходной задачи: YAX=YA0=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 = x 2 – 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

010-1-30

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

00-10130

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-70400

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-71-4000

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/30-11/300-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 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), т. е. yi = С*Х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, x 2, ., xn), которая удовлетворяет системе ограничений (1.12). АХ0, Х>0 и минимизирует линейную функцию Z = СХ. Двойственная задача. Найти матрицу-строку Y = (y1, y 2, ., yn), которая удовлетворяет системе ограничений YA £ C, Y ³ 0 и максимизирует линейную функцию f = YA0. Систему неравенств с помощью дополнительных переменных мож­но преобразовать в систему уравнений, поэтому всякую пару симмет­ричных двойственных задач можно преобразовать в пару несимметрич­ных, для которых теорема двойственности уже доказана. Используя симметричность, можно выбрать задачу, более удоб­ную для решения. Объем задачи, решаемой с помощью ЭВМ, ограни­чен числом включаемых строк, поэтому задача, довольно громоздкая в исходной постановке, может быть упрощена в двойственной формули­ровке. При вычислениях без помощи машин использование двойствен­ности упрощает вычисления. Исходная задача. Найти минимальное значение линейной функции 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), fmax = 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

2363000

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-3000

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 + 1Zi - Cj610-909600

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/210009/23/29/20

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

На основании рассмотренных несимметричных и симметричных двойственных задач можно заключить, что математические модели пары двойственных задач могут иметь один из следующих видов. Н е с и м м е т р и ч н ы е з а д а ч и (1) Исходная задача Двойственная задача Zmin = CX; fmax = YA0; AX = A0; YA £ С. X ³ 0. (2) Исходная задача Двойственная задача Zmax = CX; fmin = YA0; AX = A0; YA ³ С. X ³ 0. С и м м е т р и ч н ы е з а д а ч и (3) Исходная задача Двойственная задача Zmin = CX; fmax = YA0; AX ³ A0; YA £ С. X ³ 0. Y ³ 0. (4) Исходная задача Двойственная задача Zmax = CX; fmin = 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, Двойственная задача: fmin = -4x1 + 5x2 + 6x3 при ограничениях -y1 + y2 + 2y3 £ 2, y1 – 5y2 - y3 £ 1, yi ³ 0 (i = 1, 2, 3). 2y1 + y2 + 3y3 £ 5, Приведем без доказательства следующую теорему. Теорема 1.1. Если при подстановке компонент оптимального пла­на в систему ограничений исходной задачи i-e ограничение обращается в неравенство, то i-я компонента оптимального плана двойственной задачи равна нулю. Если i-я компонента оптимального плана двойственной задачи по­ложительна, то i-e ограничение исходной задачи удовлетворяется ее оптимальным решением как строгое равенство.

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

В п. 2 и п. 3 настоящего параграфа было показано, что для получения решения исходной задачи можно перейти к двой­ственной и используя оценки ее опти­мального плана, определить оптимальное решение исходной задачи. Переход к двойственной задаче не обязателен, так как если рассмо­треть первую симплексную таблицу с единичным дополнительным ба­зисом, то легко заметить, что в столбцах записана исходная задача, а в строках - двойственная. Причем оценками плана исходной задачи являются Сj а оценками плана двойственной задачи – bi. Решим "двойственную задачу по симплексной таблице, в которой записана ис­ходная задача; найдем оптимальный план двойственной задачи, а вместе с ним и оптимальный план исходной задачи. Этот метод носит на­звание двойственного симплексного метода, Пусть необходимо решить исходную задачу линейного программиро­вания, поставленную в общем виде: минимизировать функцию Z =СХ при АХ = A0, Х ³ 0. Тогда в двойственной задаче необходимо максимизировать функцию f = YA0 при YA £ С. Допустим, что выбран такой базис D = (A1 , А2, ..., Аi, ..., Аm), при котором хотя бы одна из компонент вектора Х = D-1 A0 = (x1, x2, ..., xi, ..., xm) отрицатель­ная (например, xi < 0), но для всех векторов Aj выполняется соотно­шение Zj – Cj £ 0 (i = 1,2, ..., n). Тогда на основании теоремы двойственности Y = Сбаз D-1 - план двойственной задачи. Этот план не оптимальный, так как, с одной стороны, при выбранном бази­се X содержит отрицательную компоненту и не является планом исходной задачи, а с другой стороны, оценки оптимального плана двой­ственной задачи должны быть неотрицательными. Таким образом, вектор Аi, соответствующий компоненте xi < 0, следует исключить из базиса исходной задачи, а вектор, соответствую­щий отрицательной оценке,— включить в базис двойственной задачи. Для выбора вектора, включаемого в базис исходной задачи, просмат­риваем i-ю строку: если в ней не содержатся xij < 0, то линейная функция двойственной задачи не ограничена на многограннике реше­ний, а исходная задача не имеет решений. Если же некоторые xij < 0, то для столбцов, содержащих эти отрицательные значения, вычисля­ем q0j= min (xi/xij) ³ 0 и определяем вектор, соответствующий max q0j(Zj — Cj) при решении исходной задачи на минимум и min q0j(Zj — Cj) при решении исходной задачи на максимум. Этот вектор и включаем в базис исходной задачи. Вектор, который необ­ходимо исключить из базиса исходной задачи, определяется направ­ляющей строкой. Если q0j= min (xi/xij) = 0, т. е. xi = 0, то xij берется за раз­решающий элемент только в том случае, если xij > 0. Такой выбор раз­решающего элемента на данном этапе не приводит к увеличению коли­чества отрицательных компонент вектора X. Процесс продолжаем до получения Х ³ 0; при этом находим оптимальный план двойственной задачи, следовательно, и оптимальный план исходной задачи. В процессе вычислений по алгоритму двойственного симплексного метода условие Z j – Cj £ 0 можно не учитывать до исключения всех х i < 0, затем оптимальный план находится обычным симплексным ме­тодом. Это удобно использовать, если все хi < 0; тогда для перехода к плану исходной, задачи за одну итерацию необходимо q0j определить не по минимуму, а по максимуму отношений, т. е. q0j= max (xi/xij) > 0. Двойственным симплексным методом можно решать задачи линей­ного программирования, системы ограничений которых при положи­тельном базисе содержат свободные члены любого знака. Этот метод позволяет уменьшить количество преобразований системы ограниче­ний, а также размеры симплексной таблицы.

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

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