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

Вернуться в Математика

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



Содержание

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 называются оценками или учетными, неявными ценами.

Многие задачи линейного программирования первоначально ста­вятся в виде исходных или двойственных задач, поэтому имеет смысл говорить о паре двойственных задач линейного программирования

Добавить в Одноклассники    

 

Rambler's Top100