Предыдущая страница реферата | 1  2  3  4  5  6  7  8 | Следующая страница реферата

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).

Рекомендуем скачать другие рефераты по теме: реферат на тему закон, учет реферат.





Предыдущая страница реферата | 1  2  3  4  5  6  7  8 | Следующая страница реферата