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

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

Содержание

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

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

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

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

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

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

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

Связь исходной и двойственной задач состоит в том, что коэффици­енты 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 + … + a2nxn £ 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 + … + am2ym £ C2, yj ³ 0 (i =1,2, ., m)

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

a1ny1 + a2ny2 + … + amnym £ Cm,

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

f = b1y1 + b2y2 + … + bmym.

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

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

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

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

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

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

Исходная задача. Найти матрицу-столбец 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.

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

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

Т а б л и ц а 1.1

Пусть D — матрица, составленная из компонент векторов оконча­тельного базиса A1, A2, ., Am; тогда табл. 1.1 состоит из коэффици­ентов разложения векторов A1, A2, ., An исходной системы по векто­рам базиса, т. е. каждому вектору Aj в этой таблице соответствует та­кой вектор Xj что