Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Определение двойственной задачи

Читайте также:
  1. C.4.1 Определение расширенных компонентов
  2. Cодержание и задачи планирования себестоимости
  3. I. Задачи статистического изучения вариации
  4. I. Медико-гигиеническое воспитание, цели, задачи, принципы.
  5. I. Определение.
  6. I. Основные задачи
  7. I. Понятие и задачи методики расследования по горячим следам.
  8. I. ПОНЯТИЕ, ПРЕДМЕТ, ЦЕЛИ И ЗАДАЧИ КУРСА. СТРУКТУРА КУРСА, ВЗАИМОСВЯЗЬ С ДРУГИМИ УЧЕБНЫМИ ДИСЦИПЛИНАМИ.
  9. I. Предмет и задачи курса
  10. I. Предмет, цели, задачи, принципы специальной психологии
  11. I. Предмет, цели, задачи, принципы специальной психологии
  12. I. Учет затрат в системе управления себестоимости продукции. Задачи учета затрат на производство.



ТЕМА 1.3 ПРЯМАЯ И ДВОЙСТВЕННАЯ ЗАДАЧИ ЛП. ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД.

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

(25)

при условиях

(26)

(27)

Определение 1.13Задача, состоящая в нахождении минимального значения функции

(28)

при условиях

(29)

(30)

называется двойственной по отношению к задаче (25) – (27). Задачи (25) – (27) и (28) – (30) образуют пару задач, называемую в линейном программировании двойственной парой. Сравнивая две сформулированные задачи, видим, что двойственная задача составляется согласно следующим правилам:

1. Целевая функция исходной задачи (25) – (27) задается на максимум, а целевая функция двойственной (28) – (30) – на минимум.

2. Матрица

(31)

составленная из коэффициентов при неизвестных в системе ограничений (33) исходной задачи – (27), и аналогичная матрица

(32)

в двойственной задаче (28) – (30) получаются друг из друга транспонированием (т. е. заменой строк столбцами, а столбцов – строками).

3. Число переменных в двойственной задаче (28) – (30) равно числу ограничений в системе (26) исходной задачи (25) – (27), а число ограничений в системе (29) двойственной задачи – числу переменных в исходной задаче.

4. Коэффициентами при неизвестных в целевой функции (28) двойственной задачи (28) – (30) являются свободные члены в системе (26) исходной задачи (25) – (27), а правыми частями в соотношениях системы (29) двойственной задачи – коэффициенты при неизвестных в целевой функции (25) исходной задачи.

5. Если переменная xj исходной задачи (25) – (27) может принимать только лишь положительные значения, то j–е условие в системе (29) двойственной задачи (28) – (30) является неравенством вида “”. Если же переменная xj может принимать как положительные, так и отрицательные значения, то 1 –соотношение в системе (27) представляет собой уравнение. Аналогичные связи имеют место между ограничениями (26) исходной задачи (25) – (27) и переменными двойственной задачи (28) – (30). Если i – соотношение в системе (26) исходной задачи является неравенством, то i–я переменная двойственной задачи . В противном случае переменная уj может принимать как положительные, так и отрицательные значения.

Двойственные пары задач обычно подразделяют на симметричные и несимметричные. В симметричной паре двойственных задач ограничения (26) прямой задачи и соотношения (29) двойственной задачи являются неравенствами вида “ ”. Таким образом, переменные обеих задач могут принимать только лишь неотрицательные значения.



Пример.Составить двойственную задачу по отношению к задаче, состоящей в максимизации функции

(33)

при условиях

(34)

(35)

Решение. Для данной задачи

и

Число переменных в двойственной задаче равно числу уравнений в системе (34), т. е. равно трем. Коэффициентами в целевой функции двойственной задачи являются свободные члены системы уравнений (34), т.е. числа 12, 24, 18.

Целевая функция исходной задачи (33) – (35) исследуется на максимум, а система условий (34) содержит только уравнения. Поэтому в двойственной задаче целевая функция исследуется на минимум, а ее переменные могут принимать любые значения (в том числе и отрицательные). Так как все три переменные исходной задачи (33) – (35) принимают только лишь неотрицательные значения, то в системе условий двойственной задачи должны быть три неравенства вида “ ”. Следовательно, для задачи (33) – (35) двойственная задача такова: найти минимум функции при условиях

 





Дата добавления: 2014-01-15; Просмотров: 82; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:



studopedia.su - Студопедия (2013 - 2017) год. Не является автором материалов, а предоставляет студентам возможность бесплатного обучения и использования! Последнее добавление ip: 54.162.139.105
Генерация страницы за: 0.019 сек.