Реферат: Двойственный симплекс-метод и доказательство теоремы двойственности
Студент группы МЭК 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 минимизироватьобщую стоимость затрат?
--> ЧИТАТЬ ПОЛНОСТЬЮ <--