|
Свойство двойственности задач ЛП.С каждой задачей ЛП связана другая задача, которая называется двойственной или сопряженной. Первоначальная задача ЛП называется исходной или прямой. Связь между прямой и двойственной задачами заключается в том, что решение одной из них может быть получено из решения другой. Несимметричные двойственные задачи. Исходная задача имеет вид:
или, в матричной форме,
Двойственная задача в несимметричной форме имеет вид
или, в матричной форме,
Обратите внимание на то, что в несимметричной двойственной задаче не накладывается условие неотрицательности переменных. Если исходная задача линейного программирования записана в произвольной форме, то для записи двойственной задачи следует сначала записать исходную задачу в канонической или стандартной форме, а затем выписать двойственную задачу. Симметричные двойственные задачи Рассмотрим задачу линейного программирования в стандартной форме
или, в матричной форме,
Рассмотрим теперь следующую задачу
или, в матричной форме,
Пара задач (1) и (3) (или, в матричной форме, пара задач (2) и (4)) называются двойственными друг другу задачами в симметричной форме. Теоремы двойственности. Теорема 1: Если одна из двойственных задач имеет оптимальное решение, то другая также имеет оптимальное решение, причем для любых оптимальных решений Если одна из двойственных задач неразрешима из-за Теорема 2: Для оптимальности допустимых решений
Если в оптимальном решении одной из двойственных задач какая-либо переменная строго больше нуля, то соответствующее ей ограничение в другой двойственной задаче выполняется как строгое равенство, и наоборот, если при оптимальном решении одной из двойственных задач какое-либо ограничение выполняется как строгое неравенство, то соответствующая ему переменная в оптимальном решении другой задачи равна нулю. Виды математических моделей двойственных задач На основании рассмотренных несимметричных и симметричных двойственных задач можно заключить, что математические модели пары двойственных задач могут иметь один из следующих видов. Н е с и м м е т р и ч н ы е з а д а ч и (1) Исходная задача Двойственная задача Zmin = CX; f max = YA0; AX = A0; YA £ С. X ³ 0. (2) Исходная задача Двойственная задача Zmax = CX; f min = YA0; AX = A0; YA ³С. X ³ 0. С и м м е т р и ч н ы е з а д а ч и (3) Исходная задача Двойственная задача Zmin = CX; f max = YA0; AX ³ A0; YA £ С. X ³ 0. Y³ 0. (4) Исходная задача Двойственная задача Zmax = CX; f min = YA0; AX £ A0; YA ³С. X ³ 0. Y³ 0. Таким образом, прежде чем записать двойственную задачу для данной исходной, систему ограничений исходной задачи необходимо привести к соответствующему виду. Транспортная задача. Транспортная задача – одна из распространенных задач линейного программирования. Её цель – разработка наиболее рациональных путей и способов транспортирования товаров, устранение чрезмерно дальних, встречных, повторных перевозок. Все это сокращает время продвижения товаров, уменьшает затраты предприятий, фирм, связанные с осуществлением процессов снабжения сырьем, материалами, топливом, оборудованием и т.д. Транспортные задачи бывают открытые и закрытые. Если сумма запасов груза равна суммарной потребности в нем, то транспортная задача называется закрытой. Если сумма запасов груза не равна суммарной потребности в нем, то транспортная задача является открытой. Транспортная задача называется закрытой, если выполняется условие баланса: суммарный объем производства равен суммарному объему потребления: Следнет обратить внимание на то, что математическая модель задает закрытую транспортную задачу. Открытая ТЗ имеет место в двух случаях. Первый случай. Суммарный объем производства меньше суммарного объема потребления: Известно, что для существования допустимого решения транспортной задачи необходимо и достаточно, чтобы задача была закрытой. Поэтому транспортную задачу открытого типа предварительно необходимо свести к закрытой, для чего вводится фиктивный пункт производства с номером m+1 с объемом производства: при этом полагают Второй случай. Суммарный объем производства больше суммарного объема потребления: Для сведения ТЗ к закрытому типу вводят фиктивный пункт потребления с номером n+1 с объемом потребления: при этом полагают
![]() ![]() Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам... ![]() ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между... ![]() Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право... ![]() Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|