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

Студент группы МЭК 1-1 - А.С. Кормаков

Научный руководитель - Солодовников А.С.

МОСКВА – 2001

Содержание

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

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

3. Симметричные двойственные задачи........................................................ 9

4. Виды математических моделей двойственных задач........................... 11

5. Двойственный симплексный метод........................................................... 12

6. Список используемой литературы............................................................ 14

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

Понятие двойственности. С каждой задачей линейного программирования тесно связана другая линейная задача, называемая двойственной. Первоначальная задача называется исходной.

Связь исходной и двойственной задач состоит в том, что коэффици­енты Cj функции цели исходной задачи являются свободными членами системы ограничений двойственной задачи, свободные члены B i систе­мы ограничений исходной задачи служаткоэффициентами функции цели двойственной задачи, а матрица коэффициентов системы ограни­чений двойственной задачи является транспонированной матрицей коэффициентов системы ограничений исходной задачи. Решение двой­ственной задачи может быть получено из решения исходной и наоборот.

В качестве примера рассмотрим задачу использования ресурсов. Предприятие имеет т видов ресурсов в количестве bi (i = 1, 2, ..., m ) единиц, из которых производится n видов продукций. Для производ­ства 1 ед. i -й продукции расходуется aij ед. t-гo ресурса, а ее стоимость составляет Cj ед. Составить план выпуска продукции, обеспечивающий ее максимальный выпуск в стоимостном выражении. Обозначим через xj (j =1,2, ..., n) количество ед. j -й продукций, Тогда исходную задачу сформулируем так.

Найти вектор Х =(x1 , x2 , …, xn ), который удовлетворяет ограни­чениям

a11 x1 + a12 x2 + … + a1n xn £ b1,

a21 x1 + a22 x2 + … + a2n xn £ b2, xj ³ 0 (j =1,2, ..., n)

…………………………………

am1 x1 + am2 x2 + … + amn xn £ bm,

и доставляет максимальное значение линейной функции

Z = C1 x1 + C2 x2 + … + Cn xn ,

Оценим ресурсы, необходимые для изготовления продукции. За единицу стоимости ресурсов примем единицу стоимости выпускаемой продукции. Обозначим через у i (j =1,2, ..., m) стоимость единицы i- горесурса. Тогда стоимость всех затраченных ресурсов, идущих на изготовление единицы j -й продукции, равна . Стоимость затрачен­ных ресурсов не может быть меньше стоимости окончательного продукта, поэтому должно выполняться неравенство ³Cj , j =1,2, ..., n . Стоимость всех имеющихся ресурсов выразится величиной . Итак, двойственную задачу можно сформулировать следующим образом.

Найти вектор Y =(y1 , y2 , …, yn ), который удовлетворяет ограни­чениям

a11 y1 + a12 y2 + … + am1 ym £ C1,

a12 y1 + a22 y2 + … + am2 ym £ C2, yj ³ 0 (i =1,2, ..., m)

…………………………………

a1n y1 + a2n y2 + … + amn ym £ Cm,

и доставляет минимальное значение линейной функции

f = b1 y1 + b2 y2 + … + bm ym .

Рассмотренные исходная и двойственная задачи могут быть эко­номически интерпретированы следующим образом.

Исходная задача. Сколько и. какой продукции xj (j =1,2, ..., n) необходимо произвести, чтобы при заданных стоимостях Cj (j =1,2, ..., n) единицы продукции и размерах имеющихся ресурсов bi (i =1,2, ..., n) максимизировать выпуск продукции в стоимостном выражении.

Двойственная задача. Какова должна быть цена еди­ницы каждого из ресурсов, чтобы при заданных количествах ресурсов b i и величинах стоимости единицы продукции C i минимизироватьобщую стоимость затрат?

--> ЧИТАТЬ ПОЛНОСТЬЮ <--

К-во Просмотров: 329
Бесплатно скачать Реферат: Двойственный симплекс-метод и доказательство теоремы двойственности