←предыдущая следующая→
1 2 3
ФИНАНСОВАЯ АКАДЕМИЯ ПРИ ПРАВИТЕЛЬСТВЕ
РОССИЙСКОЙ ФЕДЕРАЦИИ
Кафедра математики
КУРСОВАЯ
на тему:
Двойственный симплекс-метод и доказательство теоремы двойст-венности.
Студент группы МЭК 1-1 - А.С. Кормаков
Научный руководитель - Солодовников А.С.
МОСКВА – 2001
СОДЕРЖАНИЕ
1. Двойственность в линейном программировании 3
2. Несимметричные двойственные задачи. Теорема двойственности. 4
3. Симметричные двойственные задачи 9
4. Виды математических моделей двойственных задач 11
5. Двойственный симплексный метод 12
6. Список используемой литературы 14
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-й продукции, равна . Стоимость затрачен¬ных ресурсов не может быть меньше стоимости окончательного продукта, поэтому должно выполняться не-равенство 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 называются оценками или учетными, неявными ценами.
Многие задачи линейного программирования первоначально ста¬вятся в виде исходных или двойственных задач, поэтому имеет смысл говорить о паре двойственных задач линейного программирования.
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
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 — матрица, составленная из компонент векторов оконча¬тельного базиса 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).
Обозначим через матрицу, составленную из коэффициентов раз¬ложения векторов Аj (j = 1, 2, ..., n), записанных в табл. 1.1. Тогда, учитывая соотношения (1.3) и (1.4), получа-ем:
(1.5) A = D , D-1A = ,
(1.6) A0=DX*; D-1A0 = X*,
(1.7) min Z= C*X*,
(1.8) = C* —C 0,
где С* = (C*1, C*2, …, C*m), С = (C1, C2, …, Cm, Cm+1, …, Cn), a = (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А – С = С* - С 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).
Таким образом, значение линейной функции
←предыдущая следующая→
1 2 3