Читать реферат по математике: "ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД И ДОКАЗАТЕЛЬСТВО ТЕОРЕМЫ ДВОЙСТВЕННОСТИ" Страница 1

(Назад) (Cкачать работу)

Содержание

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

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

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

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

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

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

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

Двойственная задача тесно связана задачей линейного программирования. Задача первоначальная называется исходной

Решение двой­ственной задачи может быть получено из решения исходной и наоборот

Связующим фактом этих двух задач являются коэффици­енты C j   функции исходной задачи. Данные коэффициенты называются свободными членами системы ограничений двойственной задачи. Коэффициенты B i систе­мы ограничений исходной задачи называются коэффициентами двойственной задачи. Транспонированная матрица коэффициентов системы ограничений исходной задачи является матрицей коэффициентов системы ограни­чений двойственной задачи

Рассмотрим задачу использования ресурсов

  У предприятия есть т видов ресурсов в количестве b i ( i = 1, 2, ..., m ) единиц, из которых выпускается n видов продукции. На изготовление1 ед. i -й продукции тратится a ij ед. t-гo ресурса, ее стоимость составляет C j ед. Необходимо определить план выпуска продукции, обеспечивающий ее максимальный выпуск в стоимостном выражении. Примем за x j (j =1,2, ..., n) количество ед. j -й продукций

Сформулируем исходную задачу. Определить вектор Х =( x 1 , x 2 , …, x n ), который удовлетворяет ограни­чениям

a 11 x 1 + a 12 x 2 + … + a 1n x n £ b 1,

a 21 x 1 + a 22 x 2 + … + a 2n x n £ b 2,                        x j ³ 0 (j =1,2, ..., n)

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

a m 1 x 1 + a m 2 x 2 + … + a mn x n £ b m , и состовляет максимальное значение линейной функции

Z = C 1 x 1 + C 2 x 2 + … + C n x n ,

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

Сформулируем   двойственную задачу

Необходимо определить вектор Y =( y 1 , y 2 , …, y n ), удовлетворяющий ограни­чениям

a 11 y 1 + a 12 y 2 + … + a m1 y m £ C 1,

a 12 y 1 + a 22 y 2 + … + a m2 y m £ C 2,     y j ³ 0 (i =1,2, ..., m)

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

a 1n y 1 + a 2n y 2 + … + a mn y m £ C m ,

Вектор   Y =( y 1 , y 2 , …, y n ) состовляет минимальное значение линейной функции

f   = b 1 y 1 + b 2 y 2 + … + b m y m

Переменные у i называются оценками или учетными, неявными ценами

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

А исходную задачу определим следующим образом: сколько и. какой продукции x j   (j =1,2, ..., n) необходимо произвести, чтобы при заданных стоимостях C j   (j =1,2, ..., n) единицы продукции и размерах имеющихся ресурсов b i  

Похожие работы