Главная    Почта    Новости    Каталог    Одноклассники    Погода    Работа    Игры     Рефераты     Карты
  
по Казнету new!
по каталогу
в рефератах

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



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

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

    Понятие двойственности. С каждой задачей линейного программирования
тесно связана другая линейная задача, называемая двойственной.
Первоначальная задача называется исходной.
    Связь исходной и двойственной задач состоит в том, что коэффициенты 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-й
продукции, равна [pic]. Стоимость затраченных ресурсов не может быть меньше
стоимости окончательного продукта, поэтому должно выполняться неравенство
[pic]( Cj, j =1,2, ..., n. Стоимость всех имеющихся ресурсов выразится
величиной [pic]. Итак, двойственную задачу  можно сформулировать следующим
образом.
    Найти вектор 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 называются оценками или учетными, неявными ценами.
Многие задачи линейного программирования первоначально ставятся в виде
исходных или двойственных задач, поэтому имеет смысл говорить о паре
двойственных задач линейного программирования.

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

    В несимметричных двойственных задачах система ограничений исходной
задачи задается в виде равенств, а двойственной — в виде неравенств, причем
в последней переменные могут быть и отрицательными. Для простоты
доказательств постановку задачи условимся записывать в матричной форме.
    Исходная задача. Найти матрицу-столбец 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



|i    |Базис|С    |A0|C1       |C2       |… |Cm       |Cm+1    |… |cn   |
|     |     |базис|  |         |         |  |         |        |  |     |
|     |     |а    |  |         |         |  |         |        |  |     |
|     |     |     |  |A1       |A2       |… |Am       |Am+1    |… |An   |
|1    |A1   |C1   |x1|1        |0        |..|0        |x1, m+1 |… |x1n  |
|2    |A2   |C2   |  |0        |1        |. |0        |x2, m+1 |… |x2n  |
|.    |.    |.    |x2|.        |.        |..|.        |.       |. |.    |
|.    |.    |.    |  |.        |.        |. |.        |.       |. |.    |
|.    |.    |.    |. |.        |.        |. |.        |.       |. |.    |
|m    |Am   |Cm   |. |0        |0        |. |1        |xm, m+1 |… |xmn  |
|     |     |     |. |         |         |. |         |        |  |     |
|     |     |     |xm|         |         |. |         |        |  |     |
|m+1  |Zi - Cj     |Z0|Z1 – C1  |Z2 – C2  |..|Zm – Cm  |Zm+1 –  |… |Zn – |
|     |            |  |         |         |. |         |Cm+1    |  |Cn   |


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

    (1.3)                   Aj = DXj (j= 1,2, ,.., n).
    Для оптимального плана получаем
    (1.4)                   A0 = DX*,
    где X* = (x*1, x*2, …, x*m).
    Обозначим через [pic] матрицу, составленную из коэффициентов разложения
векторов Аj (j = 1, 2, ..., n), записанных в табл. 1.1. Тогда, учитывая
соотношения (1.3) и (1.4), получаем:

    (1.5)                      A = D[pic],  D-1A = [pic],
    (1.6)                    A0=DX*;  D-1A0 = X*,
    (1.7)                        min Z= C*X*,
    (1.8)                        [pic]= C*[pic]—C ( 0,

    где С* = (C*1, C*2, …, C*m), С = (C1, C2, …, Cm, Cm+1, …, Cn), a [pic]
= (C*X1 – C1; С*Х2  - С2, ..., C*Xn – Cn) = (Z1 – С1; Z2  - C2; ..., Zn —
Cn) — вектор, компоненты которого неположительны, так как они совпадают с
Zj — Cj  ( 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А – С = С* [pic] - С ( 0,
    откуда находим Y*A ( С.
    Так как Y* удовлетворяет ограничениям (1.2), то это и есть план
двойственной задачи. При этом плане значение линейной функции двойственной
задачи f (Y*) = Y*A0. Учитывая соотношения (1.9), (1.6) и (1.7), имеем
    (1.10)                   f (Y*) = Y*A0 = C*D-1 A0 = C*X* = min Z(X).
    Таким образом, значение линейной функции двойственной задачи от Y*
численно равно минимальному значению линейной функции исходной задачи.
    Докажем теперь, что Y* является оптимальным планом. Умножим (1.1) на
любой план Y двойственной задачи, а (1.2) — на любой план X исходной
задачи: YAX=YA0=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) ( +(. Это выражение
также лишено смысла, поэтому исходная задача не имеет решений.
    Доказанная теорема позволяет при решении одной из двойственных задач
находить оптимальный п
123
скачать работу


 Другие рефераты
Казахстан в средневековье
Самоубийство
Царь Иван Грозный
Античная мифология и ее влияние на современность


 

Отправка СМС бесплатно

На правах рекламы


ZERO.kz
 
Модератор сайта RESURS.KZ