на тему рефераты Информационно-образоательный портал
Рефераты, курсовые, дипломы, научные работы,
на тему рефераты
на тему рефераты
МЕНЮ|
на тему рефераты
поиск
Курсовая: Двойственный симплекс-метод и доказательство теоремы двойственности

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

ФИНАНСОВАЯ АКАДЕМИЯ ПРИ ПРАВИТЕЛЬСТВЕ РОССИЙСКОЙ ФЕДЕРАЦИИ Кафедра математики

КУРСОВАЯ

на тему: Двойственный симплекс-метод и доказательство теоремы двойственности. Студент группы МЭК 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 + . + a2nx n £ 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 + . + am2y m £ C2, yj ³ 0 (i =1,2, ..., m) ............. a1ny1 + a2ny2 + . + amnym £ Cm, и доставляет минимальное значение линейной функции f = b1y1 + b2y2 + . + bmym. Рассмотренные исходная и двойственная задачи могут быть эко­номически интерпретированы следующим образом. Исходная задача. Сколько и. какой продукции xj (j =1,2, ..., n) необходимо произвести, чтобы при заданных стоимостях C j (j =1,2, ..., n) единицы продукции и размерах имеющихся ресурсов bi (i =1,2, ..., n) максимизировать выпуск продукции в стоимостном выражении. Д в о й с т в е н н а я з а д а ч а. Какова должна быть цена еди­ницы каждого из ресурсов, чтобы при заданных количествах ресурсов bi и величинах стоимости единицы продукции Ci минимизировать общую стоимость затрат? Переменные уi называются оценками или учетными, неявными ценами. Многие задачи линейного программирования первоначально ста­вятся в виде исходных или двойственных задач, поэтому имеет смысл говорить о паре двойственных задач линейного программирования. 2. Несимметричные двойственные задачи. Теорема двойственности. В несимметричных двойственных задачах система ограничений исходной задачи задается в виде равенств, а двойственной — в виде нера­венств, причем в последней переменные могут быть и отрицательными. Для простоты доказательств постановку задачи условимся записывать в матричной форме. Исходная задача. Найти матрицу-столбец X = (x1, x 2, ., xn), которая удовлетворяет ограничениям (1.1) AX = A0, Х ³ 0 и минимизирует линейную функцию Z = СХ. Двойственная задача. Найти матрицу-строку Y = (y1, y 2, ., ym), которая удовлетворяет ограничениям (1.2) YA £ С и максимизирует линейную функцию f = YA0 В обеих задачах C = (c1, c2, ., cn) - матрица-строка, A0 = (b1, b2, ., b m) — матрица-столбец, А = (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). Таким образом, значение линейной функции двойственной задачи от 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) ³ +¥. Это выражение также лишено смысла, поэтому исходная задача не име­ет решений. Доказанная теорема позволяет при решении одной из двойственных задач находить оптимальный план другой. Исходная задача. Найти минимальное значение линейной функ­ции Z = x 2 – x4 – 3x5 при ограничениях Курсовая: Двойственный симплекс-метод и доказательство теоремы двойственности x1 + 2x2 - x4 + x5 = 1, - 4x2 + x3 + 2x4 – x5 = 2, xij ³ 0 (j = 1, 2, ., 6) 3x2 + x5 + x6 = 5, Здесь матрица-строка С = (0;. 1; 0; —1; — 3, 0), матрица-столбец Курсовая: Двойственный симплекс-метод и доказательство теоремы двойственности Курсовая: Двойственный симплекс-метод и доказательство теоремы двойственности 1 1 2 0 -1 1 0 A0 = 2 A = 0 -4 1 2 -1 0 3 0 3 0 0 1 1 Курсовая: Двойственный симплекс-метод и доказательство теоремы двойственности 1 0 0 2 -4 3 A’’ = 0 1 0 -1 2 0 1 -1 0 0 0 1 Двойственная задача. Найти максимальное значение линейной функции f = y1 + 2y2 +5y3 при ограничениях Курсовая: Двойственный симплекс-метод и доказательство теоремы двойственности y1 £ 0, 2y1 – 4y2 + 3y3 £ 1, y2 £ 0, -y1 + 2y2 £ -1, y1 – y2 + y3 £ -3, y3 £ 0. Решение исходной задачи находим симплексным методом (табл. 1.2).
iБазис

С базиса

A0

010-1-30

A1

A2

A3

A4

A5

A6

1

2

3

A1

A3

A6

0

0

0

1

2

5

1

0

0

2

-4

3

0

1

0

-1

2

0

1

-1

1

0

0

1

m + 1

Zi - Cj

00-10130

1

2

3

A5

A3

A6

-3

0

0

1

3

4

1

1

-1

2

-2

1

0

1

0

-1

1

1

1

0

0

0

0

1

m + 1

Zi - Cj

-3-3-70400

1

2

3

A5

A4

A6

-3

-1

0

4

3

1

2

1

-2

0

-2

3

1

1

-1

0

1

0

1

0

0

0

0

1

m + 1

Zi - Cj

-15-71-4000

1

2

3

A5

A4

A2

-3

-1

1

4

11/3

1/3

3

-1/3

-2/3

0

0

1

1

1/3

-1/3

0

1

0

1

0

0

0

2/3

1/3

m + 1

Zi - Cj

-46/3-19/30-11/300-1/3

Страницы: 1, 2



© 2003-2013
Рефераты бесплатно, курсовые, рефераты биология, большая бибилиотека рефератов, дипломы, научные работы, рефераты право, рефераты, рефераты скачать, рефераты литература, курсовые работы, реферат, доклады, рефераты медицина, рефераты на тему, сочинения, реферат бесплатно, рефераты авиация, рефераты психология, рефераты математика, рефераты кулинария, рефераты логистика, рефераты анатомия, рефераты маркетинг, рефераты релиния, рефераты социология, рефераты менеджемент.