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

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

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

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

КУРСОВАЯ

на тему:

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

Студент группы МЭК 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

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₁, 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*,