Решение задач на тему: Двойственность в линейном программировании. Несимметричные двойственные задачи. Теорема

Введение

Решение исходной задачи находим симплексным методом (табл. 1.2)

i Базис С базиса А 0 0 1 0 -1 -3 0 А 1 А 2 А 3 А 4 А 5 А 6 1

1 m + 1 Z i - С j 0 0 -1 0 1 3 0 1

1 m + 1 Z i - С j -3 -3 -7 0 4 0 0 1

1 m + 1 Z i - С j -15 -7 1 -4 0 0 0 1

1/3 m + 1 Z i - С j -46/3 -19/3 0 -11/3 0 0 -1/3 Оптимальный план исходной задачи X* = (0; 1/3; 0; 11/3; 4; 0), при котором Z min = - 46/3, получен в четвертой итерации табл. 1.2. Используя эту итерацию, найдем оптимальный план двойственной задачи. Согласно теореме двойственности оптимальный план двойствен ной задачи находится из соотношения Y* = С*D -1 , где матрица D -1 - матрица, обратная матрице, составленной из компонент векторов, вхо дящих в последний базис, при котором получен оптимальный план исходной задачи. В последний базис входят векторы А 5 , А 4 , А 2 ; значит,

Обратная матрица D -1 образована из коэффициентов, стоящих в столбцах А 1 , А 3 , А 6 четвертой итерации:

Из этой же итерации следует С* = (- 3; -1; 1). Таким образом

Y = С* D -1 = (-3; -1; 1) -1/3 1/3 2/3

т. е. y i = С*Х i , где Х i - коэффициенты разложения последней ите рации, стоящие в столбцах векторов первоначального единичного базиса

Итак, i -ю двойственную переменную можно получить из значения оценки ( m + 1)-й строки, стоящей против соответствующего вектора, входившего в первоначальный единичный бази с , если к ней приба вить соответствующее значение коэффициента линейной функции:

у 1 = - 19/3 + 0 = - 19/3; y 2 = -11/3 + 0 = -11/3; у 3 = -1/3+0 = -1/3. При этом плане max f = -46/3

Оглавление

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

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

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

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

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

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

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

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

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

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

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

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

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

Список литературы

Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. "Наука", 1980 г

Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. "Финансы и статистика", 1998 г