ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД И ДОКАЗАТЕЛЬСТВО ТЕОРЕМЫ ДВОЙСТВЕННОСТИ Содержание 1. Двойственность в линейном программировании 2. Несимметричные двойственные задачи. Теорема двойственности 3. Симметричные двойственные задачи 4. Виды математических моделей двойственных задач 5. Двойственный симплексный метод 6. Список используемой литературы Двойственность в линейном программировании Двойственная задача тесно связана задачей линейного программирования. Задача первоначальная называется исходной Решение двойственной задачи может быть получено из решения исходной и наоборот Связующим фактом этих двух задач являются коэффициенты 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 1 , x 2 , …, x n ), который удовлетворяет ограничениям a 11 x 1 + a 12 x 2 + … + a 1n x n £ b 1, a 21 x 1 + a 22 x 2 + … + a 2n x n £ b 2, x j ³ 0 (j =1,2, ..., n) ………………………………… a m 1 x 1 + a m 2 x 2 + … + a mn x n £ b m ,
и состовляет максимальное значение линейной функции Z = C 1 x 1 + C 2 x 2 + … + C n x n , Определим ресурсы, которые потребуются для изготовления товара. Обозначим за единицу стоимости ресурсов единицу стоимости выпускаемого товара. А через у i (j =1,2, ..., m) стоимость единицы i -го ресурса. Т.е. стоимость всех затраченных ресурсов, которые используются для изобретения единицы j -й продукции, состовляет . Цена израсходованных ресурсов не должна превышать цены окончательного товара. Таким образом должно выполняться неравенство ³ C j , j =1,2, ..., n. Цена имеющихся ресурсов составляет Сформулируем двойственную задачу Необходимо определить вектор Y =( y 1 , y 2 , …, y n ), удовлетворяющий ограничениям a 11 y 1 + a 12 y 2 + … + a m1 y m £ C 1, a 12 y 1 + a 22 y 2 + … + a m2 y m £ C 2, y j ³ 0 (i =1,2, ..., m) ………………………………… a 1n y 1 + a 2n y 2 + … + a mn y m £ C m , Вектор Y =( y 1 , y 2 , …, y n ) состовляет минимальное значение линейной функции f = b 1 y 1 + b 2 y 2 + … + b m y m Переменные у i называются оценками или учетными, неявными ценами С экономической точки зрения двойственную задачу можно интерпретировать так: какова должна быть цена единицы каждого из ресурсов, чтобы при заданных количествах ресурсов b i и величинах стоимости единицы продукции C i минимизировать общую стоимость затрат? А исходную задачу определим следующим образом: сколько и. какой продукции x j (j =1,2, ..., n) необходимо произвести, чтобы при заданных стоимостях C j (j =1,2, ..., n) единицы продукции и размерах имеющихся ресурсов b i (i =1,2, ..., n) максимизировать выпуск продукции в стоимостном выражении Большинство задач линейного программирования изначально определяются как исходные или двойственные задачи. Сделав вывод можно говорить о паре двойственных задач линейного программирования Несимметричные двойственные задачи. Теорема двойственности. Система ограничений исходной задачи в несимметричных двойственных задачах определяется как равенство. Двойственная же задача задается, как неравенство, причем переменные могут быть и отрицательными Чтобы проще понимать постановку задачи будем интерпретировать ее в матричной форме Сформулируем двойственную задачу Необходимо определить матрицу-строку Y = ( y 1 , y 2 , …, y m ), которая максимизирует линейную функцию f = YA 0 и удовлетворяет ограничениям (1.1) YA £ С. Сформулируем исходную задачу. Определить матрицу-столбец X = ( x 1 , x 2 , …, x n ), которая минимизирует линейную функцию Z = СХ и удовлетворяет ограничениям (1.2) AX = A 0 , Х ³ 0 Как в исходной так и в двойственной задачах А = ( a ij ) — матрица коэффициентов системы ограничений, A 0 = ( b 1 , b 2 , …, b m ) — матрица-столбец, C = ( c 1 , c 2 , …, c n ) - матрица-строка Теорема двойственности устанавливает связь между оптимальными планами пары двойственных зада Теорема двойственности гласит: если из пары двойственных задач одна обладает оптимальным планом, то и другая имеет решение, причем для экстремальных значений линейных функций выполняется соотношение min Z = max f . Если линейная функция одной из задач не ограничена, то другая не имеет решения Доказательство. Будем считать, что исходная задача имеет оптимальный план. План определен симплексным методом. Можно считать, что конечный базис состоит из т первых векторов A 1 , A 2 , ..., A m . Таким образом, симплексная таблица примет вид, приведенный в табл. 1.1 Таблица 1.1 i Базис С базиса A 0 C 1 C 2 … C m C m+1 … c n
A 1 A 2 … A m A m+1 … A n
1 2 m A 1 A 2 A m C 1 C 2 C m x 1 x 2 x m 1 0 0 0 1 0
0 0 1 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 0 Z 1 – C 1 Z 2 – C 2
Z m – C m Z m+1 – C m+1 … Z n – C n
Будем считать, что D является матрицей, составленной из компонент векторов конечного базиса A 1 , A 2 , ..., A m . Приведенная выше таблица состоит из коэффициентов разложения векторов A 1 , A 2 , ..., A n исходной системы по векторам базиса. В этой таблице каждому вектору A j соответствует вектор X j Найдем оптимальный план: (1.3) A 0 = DX*, где X* = ( x * 1 , x * 2 , …, x * m ) Получим: (1.4) A j = DX j ( j = 1,2, ,.., n) - это матрица, составленная из коэффициентов разложения векторов А j ( j = 1, 2, ..., n ), представленных в приведенной выше таблице Используя соотношения (1.3) и (1.4), получаем: (1.5) A = D , D -1 A = , (1.6) A 0 =DX*; D -1 A 0 = X*, (1.7) min Z= C*X*, (1.8) = C* —C £ 0, где С* = ( C * 1 , C * 2 , …, C * m ), С = ( C 1 , C 2 , …, C m , C m +1 , …, C n ), a = (C*X 1 – C 1 ; С*Х 2 - С 2 , ..., C*X n – C n ) = (Z 1 – С 1 ; Z 2 - C 2 ; ..., Z n — C n ) — вектор, компоненты которого неположительны, так как они совпадают с Z j — C j £ 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*A 0 . Учитывая соотношения (1.9), (1.6) и (1.7), имеем (1.10) f (Y*) = Y*A 0 = C * D -1 A 0 = C*X* = min Z(X) Таким образом, значение линейной функции двойственной задачи от Y* численно равно минимальному значению линейной функции исходной задачи Докажем теперь, что Y* является оптимальным планом. Умножим (1.1) на любой план Y двойственной задачи, а (1.2) — на любой план X исходной задачи: YAX=YA 0 = 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 – x 4 – 3 x 5 при ограничениях
