Симплекс метод

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

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

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

КУРСОВАЯ

на тему:

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

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

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

МОСКВА – 2001

СОДЕРЖАНИЕ

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

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

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

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

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

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

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

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

Связь исходной и двойственной задач состоит в том, что коэффициенты 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₁, x₂, …, x_n), который удовлетворяет ограничениям

a₁₁x₁ + a₁₂x₂ + … + a_1nx_n ? b_1,

a₂₁x₁ + a₂₂x₂ + … + a_2nx_n ? b_2, x_j ? 0 (j =1,2, ..., n)

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

a_m1x₁ + a_m2x₂ + … + a_mnx_n ? b_m,

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

Z = C₁x₁ + C₂x₂ + … + C_nx_n,

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

Найти вектор Y =(y₁, y₂, …, y_n), который удовлетворяет ограничениям

a₁₁y₁ + a₁₂y₂ + … + a_m1y_m ? C_1,

a₁₂y₁ + a₂₂y₂ + … + a_m2y_m ? C_2, y_j ? 0 (i =1,2, ..., m)

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

a_1ny₁ + a_2ny₂ + … + a_mny_m ? C_m,

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

f = b₁y₁ + b₂y₂ + … + b_my_m.

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

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

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

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

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

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

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

Исходная задача. Найти матрицу-столбец X = (x₁, x₂, …, x_n), которая удовлетворяет ограничениям

(1.1) AX = A₀, Х ? 0

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

Двойственная задача. Найти матрицу-строку Y = (y₁, y₂, …, y_m), которая удовлетворяет ограничениям

(1.2) YA ? С

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

В обеих задачах C = (c₁, c₂, …, c_n) - матрица-строка, A₀ = (b₁, b₂, …, b_m) — матрица-столбец, А = (a_ij) — матрица коэффициентов системы ограничений. Связь между оптимальными планами пары двойственных задач устанавливает следующая теорема.

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

min Z = max f.

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

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

Т а б л и ц а 1.1

Базис

С базиса

A₀

C₁	C₂	…	C_m	C_m+1	…	c_n
A₁	A₂	…	A_m	A_m+1	…	A_n

A₁

A₂

A_m

C₁

C₂

C_m

x₁

x₂

x_m

...

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₀

Z₁ – C₁

Z₂ – C₂

...

Z_m – C_m

Z_m+1 – C_m+1

…

Z_n – C_n

Пусть D — матрица, составленная из компонент векторов окончательного базиса A₁, A₂, ..., A_m; тогда табл. 1.1 состоит из коэффициентов разложения векторов A₁, A₂, ..., A_n исходной системы по векторам базиса, т. е. каждому вектору A_j в этой таблице соответствует такой вектор X_j что

(1.3) A_j = DX_j (j= 1,2, ,.., n).

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

(1.4) A₀ = DX*,

где X* = (x*₁, x*₂, …, x*_m).

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

(1.5) A = D, D^-1A = ,

(1.6) A₀=DX*; D^-1A₀ = X*,

(1.7) min Z= C*X*,

(1.8) = C*—C ? 0,

где С* = (C*₁, C*₂, …, C*_m), С = (C₁, C₂, …, C_m, C_m+1, …, C_n), a = (C*X₁ – C₁; С*Х₂ - С₂, ..., C*X_n – C_n) = (Z₁ – С₁; Z₂ - C₂; ..., Z_n — C_n) — вектор, компоненты которого неположительны, так как они совпадают с Z_j — C_j ? 0, соответствующими оптимальному плану.

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

(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₀. Учитывая соотношения (1.9), (1.6) и (1.7), имеем

(1.10) f (Y*) = Y*A₀ = C*D^-1 A₀ = C*X* = min Z(X).

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

Докажем теперь, что Y* является оптимальным планом. Умножим (1.1) на любой план Y двойственной задачи, а (1.2) — на любой план X исходной задачи: YAX=YA₀=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₂ – x₄ – 3x₅ при ограничениях

x₁ + 2x₂ - x₄ + x₅ = 1,

- 4x₂ + x₃ + 2x₄ – x₅ = 2, x_ij ? 0 (j = 1, 2, …, 6)

3x₂ + x₅ + x₆ = 5,

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

1 1 2 0 -1 1 0

A₀ = 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₁ + 2y₂ +5y₃ при ограничениях

y₁ ? 0,

2y₁ – 4y₂ + 3y₃ ? 1,

y₂ ? 0,

-y₁ + 2y₂ ? -1,

y₁ – y₂ + y₃ ? -3,

y₃ ? 0.

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

Базис

С базиса

A₀

0	1	0	-1	-3	0
A₁	A₂	A₃	A₄	A₅	A₆

A₁

A₃

A₆

-4

-1

m + 1

Z_i - C_j

-1

A₅

A₃

A₆

-3

-1

-2

-1

m + 1

Z_i - C_j

-3

-7

A₅

A₄

A₆

-3

-1

-2

-1

m + 1

Z_i - C_j

-15

-7

-4

A₅

A₄

A₂

-3

-1

11/3

1/3

-1/3

-2/3

1/3

-1/3

2/3

1/3

m + 1

Z_i - C_j

-46/3

-19/3

-11/3

-1/3

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

1 -1 2

D = (A₅, A₄, A₂) = -1 2 -4

1 0 3

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

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, если к ней прибавить соответствующее значение коэффициента линейной функции:

у₁ = — 19/3 + 0 = — 19/3; y₂ = -11/3 + 0 = -11/3; у₃ = -1/3+0 = -1/3. При этом плане max f = -46/3.

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

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

Исходная задача. Найти матрицу-столбец Х = (x₁, x₂, …, x_n), которая удовлетворяет системе ограничений

(1.12). АХ>А₀, Х>0

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

Двойственная задача. Найти матрицу-строку Y = (y₁, y₂, …, y_n), которая удовлетворяет системе ограничений YA ? C, Y ? 0 и максимизирует линейную функцию f = YA₀.

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

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

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

2x₁ + 2x₂ - x₃ ? 2,

x₁ - x₂ - 4x₃ ? -3, x_i ? 0 (i=1,2,3)

x₁ + x₂ - 2x₃ ? 6,

2x₁ + x₂ - 2x₃ ? 3,

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

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

2y₁ - y₂ + y₃ + 2y₄ ? 1,

2y₁ + y₂ + y₃ + y₄ ? 2,

-y₁+ 4y₂ - 2y₃ - 2y₄ ? 3,

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

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

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

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

Оптимальный план исходной задачи находим, используя оценки (m + 1)-й строки последней итерации, стоящие в столбцах A₅, A₆, A₇ : x₁ = 3/2 + 0 = 3/2; x₂ = 9/2 + 0 = 9/2; x₃ = 0 + 0 = 0. При оптимальном плане исходной задачи X* = (3/2; 9/2; 0) линейная функция достигает наименьшего значения: Z_min =21/2.

Т а б л и ц а 1.3

Базис

С базиса

A₀

2	3	6	3	0	0	0
A₁	A₂	A₃	A₄	A₅	A₆	A₇

A₅

A₃

A₇

-1

-2

-1

-2

m + 1

Z_i - C_j

-2

-3

-6

-3

A₃

A₆

A₇

-1

m + 1

Zi - Cj

-9

A₃

A₂

A₇

3/2

-1/2

m + 1

Z_i - C_j

21/2

9/2

3/2

9/2

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

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

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

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

Z_min = CX; f_max = YA₀;

AX = A₀; YA ? С.

X ? 0.

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

Z_max = CX; f_min = YA₀;

AX = A₀; YA ? С.

X ? 0.

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

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

Z_min = CX; f_max = YA₀;

AX ? A₀; YA ? С.

X ? 0. Y ? 0.

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

Z_max = CX; f_min = YA₀;

AX ? A₀; YA ? С.

X ? 0. Y ? 0.

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

Найти минимальное значение линейной функции Z = 2x₁ + x₂ + 5x₃ при ограничениях

x₁ – x₂ – x₃ ? 4,

x₁ – 5x₂ + x₃ ? 5, x_j ? 0 (j = 1, 2, 3).

2x₁ – x₂ + 3x₃ ?6,

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

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

Z_min = 2x₁ + x₂ + 5x₃ при ограничениях

-x₁ + x₂ + x₃ ? -4,

x₁ – 5x₂ + x₃ ? 5, x_j ? 0 (j = 1, 2, 3).

2x₁ – x₂ + 3x₃ ?6,

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

f_min = -4x₁ + 5x₂ + 6x₃ при ограничениях

-y₁ + y₂ + 2y₃ ? 2,

y₁ – 5y₂ - y₃ ? 1, y_i ? 0 (i = 1, 2, 3).

2y₁ + y₂ + 3y₃ ? 5,

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

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

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

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

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

Пусть необходимо решить исходную задачу линейного программирования, поставленную в общем виде: минимизировать функцию Z =СХ при АХ = A₀, Х ? 0. Тогда в двойственной задаче необходимо максимизировать функцию f = YA₀ при YA ? С. Допустим, что выбран такой базис D = (A₁, А₂, ..., А_i, ..., А_m), при котором хотя бы одна из компонент вектора Х = D^-1 A₀ = (x₁, x₂, ..., x_i, ..., x_m) отрицательная (например, x_i < 0), но для всех векторов A_j выполняется соотношение Z_j – C_j ? 0 (i = 1,2, ..., n). Тогда на основании теоремы двойственности Y = С_баз D^-1 - план двойственной задачи. Этот план не оптимальный, так как, с одной стороны, при выбранном базисе X содержит отрицательную компоненту и не является планом исходной задачи, а с другой стороны, оценки оптимального плана двойственной задачи должны быть неотрицательными.

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

Для выбора вектора, включаемого в базис исходной задачи, просматриваем i-ю строку: если в ней не содержатся x_ij < 0, то линейная функция двойственной задачи не ограничена на многограннике решений, а исходная задача не имеет решений. Если же некоторые x_ij < 0, то для столбцов, содержащих эти отрицательные значения, вычисляем q_0j= min (x_i/x_ij) ? 0 и определяем вектор, соответствующий max q_0j(Z_j — C_j) при решении исходной задачи на минимум и min q_0j(Z_j — C_j) при решении исходной задачи на максимум. Этот вектор и включаем в базис исходной задачи. Вектор, который необходимо исключить из базиса исходной задачи, определяется направляющей строкой.

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

В процессе вычислений по алгоритму двойственного симплексного метода условие Z_j – C_j ? 0 можно не учитывать до исключения всех х_i < 0, затем оптимальный план находится обычным симплексным методом. Это удобно использовать, если все х_i < 0; тогда для перехода к плану исходной, задачи за одну итерацию необходимо q_0j определить не по минимуму, а по максимуму отношений, т. е. q_0j= max (x_i/x_ij) > 0.

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

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

Симплекс метод

Похожие курсовые работы