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

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

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

КУРСОВАЯ

на тему:

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

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

Пусть 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.