Студопедия
МОТОСАФАРИ и МОТОТУРЫ АФРИКА !!!

Авиадвигателестроения Административное право Административное право Беларусии Алгебра Архитектура Безопасность жизнедеятельности Введение в профессию «психолог» Введение в экономику культуры Высшая математика Геология Геоморфология Гидрология и гидрометрии Гидросистемы и гидромашины История Украины Культурология Культурология Логика Маркетинг Машиностроение Медицинская психология Менеджмент Металлы и сварка Методы и средства измерений электрических величин Мировая экономика Начертательная геометрия Основы экономической теории Охрана труда Пожарная тактика Процессы и структуры мышления Профессиональная психология Психология Психология менеджмента Современные фундаментальные и прикладные исследования в приборостроении Социальная психология Социально-философская проблематика Социология Статистика Теоретические основы информатики Теория автоматического регулирования Теория вероятности Транспортное право Туроператор Уголовное право Уголовный процесс Управление современным производством Физика Физические явления Философия Холодильные установки Экология Экономика История экономики Основы экономики Экономика предприятия Экономическая история Экономическая теория Экономический анализ Развитие экономики ЕС Чрезвычайные ситуации ВКонтакте Одноклассники Мой Мир Фейсбук LiveJournal Instagram

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




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

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

F = C1X1 + C2X2+…+CnXn (1)

при условиях

(2)

xj≥0 (j=1,n) (3)

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

F*=b1y1+b2y2+…+bmym (4.)

при условиях

(5)

yi≥0 (i=1,m) ( 6)

называется двойственной задачей по отношению к задаче (1) – (3)..

Задачи (1) – (3) и (4) – (6) образуют пару задач, называемую в линейном программировании двойственной парой.

Сравнивая две сформулированные задачи, видим, что двойственная задача по отношению к исходной составляется согласно следующим правилам:

1. Целевая функция исходной задача задается на max , а целевая функция двойственной задачи на min .

2. Матрица:

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

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

3. Число переменных в двойственной задаче равно числу соотношений в системе ( 2) исходной задачи, а число ограничений в системе(5) двойственной задачи равно числу переменных в исходной задаче.

4. Коэффициентами при неизвестных целевой функции двойственной задачи являются свободные члены системы (2) исходной задачи, а правыми частями в системе ограничений двойственной задачи – коэффициенты при неизвестных в целевой функции исходной задачи .

5. Если переменная xj исходной задачи может принимать лишь положительные значения, то j-тое условие в системе (5) двойственной задачи является неравенством вида «≥». Если же переменная xj может принимать как положительные так и отрицательные значения, то j-тое соотношение в системе (5) является уравнением.

6. Если i-е соотношение в системе (2) исходной задачи является неравенством, то i-тая переменная двойственной задачи yi≥0 . В противном случае переменная yi может принимать как положительные так и отрицательные значения.

Двойственные пары задач обычно подразделяются на симметричные и несимметричные.

В симметричной паре двойственной задачи ограничения вида (2) исходной задачи и соотношения (5) двойственной задачи являются неравенствами вида « ≤», т.е переменные обеих задач могут принимать только неотрицательные значения.





Дата добавления: 2015-04-20; просмотров: 1356; Опубликованный материал нарушает авторские права? | Защита персональных данных


Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Да какие ж вы математики, если запаролиться нормально не можете??? 8811 - | 7629 - или читать все...

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

  1. Алгоритм – точное предписание о порядке выполнения действий для получения решения по данной задаче и задачам, подобным данной.
  2. Аналитические свойства входного сопротивления линейного пассивного двухполюсника
  3. Билет 45.Языки программирования.
  4. Билет 47.Системы программирования.
  5. Билет 48.Основные конструкции языка программирования .
  6. Билет 60.Объекты в языке программирования.
  7. В чем заключается особенность базовых конструкций структурного программирования?
  8. В чем соль открытого программирования
  9. Вопрос 14. Численное дифференцирование. Задача Коши. Численное дифференцирование с использованием формулы Тейлора
  10. Вопрос 39. Задача Дирихле для уравнения Лапласа.
  11. Вопрос 3: Задача на применение закона Ома для участка цепи.
  12. Вопрос 3: Задача на расчет сопротивления проводника по его удельному сопротивлению, длине и площади поперечного сечения


 

3.233.239.102 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.


Генерация страницы за: 0.001 сек.