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

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ

ОРЕНБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ МЕНЕДЖМЕНТА

Реферат

по дисциплине «Математические методы принятия управленческих решений»

на тему: «Двойственность линейного программирования»

Выполнила студентка

очной формы обучения

специальности «Менеджмент организации»

третьего курса 32 группы

Шумакова Ю. А.

Проверила

Кочетова Л.А.

Оренбург

2009

Содержание

Введение………………………………………………………………..…….3

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

моделей……………………………………………………………………….4

2. Основные теоремы двойственности……………………………………..6

3. Решение двойственных задач…………………………………………….7

4.Экономический анализ задач с использованием теории двойственности……………………………………………………………….….12

5. Стратегическое планирование выпуска изделий с учетом имеющихся ресурсов…………………………………………………………………………..14

Заключение…………………………………………………...……………..18

Библиографический список……………………………………………......19

Введение

Двойственность в линейном программировании - принцип, заключающийся в том, что для каждой задачи линейного программирования можно сформулировать двойственную задачу.

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

Теория математического линейного программирования позволяет не только получать оптимальные планы с помощью эффективных вычислительных процедур, но и делать ряд экономически содержательных выводов, основанных на свойствах задачи, которая является двойственной по отношению к исходной ЗЛП.

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

Различают симметричные, несимметричные и смешанные двойственные задачи.

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

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

Дана исходная задача

L (x) = c1x1 + c2x2 +…+ cnxn → max

при ограничениях:

a11x1 + a12x2 + … + a1nxn ≤ b1 │ y1 ,

a21x1 + a22x2 + … + a2nxn ≤ b2 │ y2 ,

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

am1x1 + am2x2 + … + amnxn ≤ bm │ ym ,

xj≥0 , j = 1,n , i = 1,m.

Задача дана в неканоническом виде. Составим математическую модель двойственной задачи, для этого:

- каждому неравенству системы ограничений исходной задачи приводим в соответствие переменную yi ;

- составляем целевую функцию, коэффициентами которой являются свободные члены системы ограничений исходной задачи;

- составляем систему ограничений. Коэффициенты системы ограничений образуют транспонированную матрицу коэффициентов системы ограничений исходной задачи. Знаки неравенств меняются на противоположные;

- свободными членами системы ограничений являются коэффициенты целевой функции исходной задачи. Все переменные двойственной задачи неотрицательны.

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

S(y) = b1y1 + b2y2 +…+ bmym → min

при ограничениях:

a11y1 + a12y2 + … + am1ym ≤ c1 ,

a12y1 + a21y2 + … + am2ym ≤ c2 ,

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

a1ny1 + a2ny2 + … + amnym ≤ cn ,

yj ≥0 , i = 1,m , j = 1,n.

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

Дана исходная задача

L (x) = c1x1 + c2x2 +…+ cnxn → max

при ограничениях:

a11x1 + a12x2 + … + a1nxn = b1 │ y1 ,

a21x1 + a22x2 + … + a2nxn = b2 │ y2 ,

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

am1x1 + am2x2 + … + amnxn = bm │ ym ,

xj ≥0 , j = 1,n.

Задача дана в каноническом виде. Составим математическую модель двойственной задачи.

Для ее составления пользуемся тем же правилом, что и для составления симметричной задачи, с учетом следующих особенностей:

- ограничениями двойственной задачи будут неравенства. Если в целевой функции двойственной задачи требуется найти минимум, то знак неравенства ≥, если максимум, то ≤ ;

- переменные yi - произвольные по знаку.

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

S(y) = b1y1 + b2y2 +…+ bmym → min

при ограничениях:

a11y1 + a21y2 + … + am1ym ≥ c1 ,

a12y1 + a22y2 + … + am2ym ≥ c2 ,

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

a1ny1 + a2ny2 + … + amnxn ≥ cn ,

yj ≥0 , i = 1,m , j = 1,n.

yi – произвольные по знаку, i = 1,m.

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

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

2. Основные теоремы двойственности

ТЕОРЕМА 1. Если

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать