|
Свойство двойственности задач ЛП.С каждой задачей ЛП связана другая задача, которая называется двойственной или сопряженной. Первоначальная задача ЛП называется исходной или прямой. Связь между прямой и двойственной задачами заключается в том, что решение одной из них может быть получено из решения другой. Несимметричные двойственные задачи. Исходная задача имеет вид:
, или, в матричной форме,
Двойственная задача в несимметричной форме имеет вид
или, в матричной форме,
Обратите внимание на то, что в несимметричной двойственной задаче не накладывается условие неотрицательности переменных. Если исходная задача линейного программирования записана в произвольной форме, то для записи двойственной задачи следует сначала записать исходную задачу в канонической или стандартной форме, а затем выписать двойственную задачу. Симметричные двойственные задачи Рассмотрим задачу линейного программирования в стандартной форме
, или, в матричной форме,
Рассмотрим теперь следующую задачу
, или, в матричной форме,
Пара задач (1) и (3) (или, в матричной форме, пара задач (2) и (4)) называются двойственными друг другу задачами в симметричной форме. Теоремы двойственности. Теорема 1: Если одна из двойственных задач имеет оптимальное решение, то другая также имеет оптимальное решение, причем для любых оптимальных решений выполняется равенство Если одна из двойственных задач неразрешима из-за (или , то другая задача также не имеет допустимых решений. Теорема 2: Для оптимальности допустимых решений и пары двойственных задач необходимо и достаточно, чтобы они удовлетворяли системе уравнений =0 0 Если в оптимальном решении одной из двойственных задач какая-либо переменная строго больше нуля, то соответствующее ей ограничение в другой двойственной задаче выполняется как строгое равенство, и наоборот, если при оптимальном решении одной из двойственных задач какое-либо ограничение выполняется как строгое неравенство, то соответствующая ему переменная в оптимальном решении другой задачи равна нулю. Виды математических моделей двойственных задач На основании рассмотренных несимметричных и симметричных двойственных задач можно заключить, что математические модели пары двойственных задач могут иметь один из следующих видов. Н е с и м м е т р и ч н ы е з а д а ч и (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. Таким образом, прежде чем записать двойственную задачу для данной исходной, систему ограничений исходной задачи необходимо привести к соответствующему виду. Транспортная задача. Транспортная задача – одна из распространенных задач линейного программирования. Её цель – разработка наиболее рациональных путей и способов транспортирования товаров, устранение чрезмерно дальних, встречных, повторных перевозок. Все это сокращает время продвижения товаров, уменьшает затраты предприятий, фирм, связанные с осуществлением процессов снабжения сырьем, материалами, топливом, оборудованием и т.д. Транспортные задачи бывают открытые и закрытые. Если сумма запасов груза равна суммарной потребности в нем, то транспортная задача называется закрытой. Если сумма запасов груза не равна суммарной потребности в нем, то транспортная задача является открытой. Транспортная задача называется закрытой, если выполняется условие баланса: суммарный объем производства равен суммарному объему потребления: . (3.1) Следнет обратить внимание на то, что математическая модель задает закрытую транспортную задачу. Открытая ТЗ имеет место в двух случаях. Первый случай. Суммарный объем производства меньше суммарного объема потребления: . (3.2) Известно, что для существования допустимого решения транспортной задачи необходимо и достаточно, чтобы задача была закрытой. Поэтому транспортную задачу открытого типа предварительно необходимо свести к закрытой, для чего вводится фиктивный пункт производства с номером m+1 с объемом производства: , (3.3) при этом полагают . Второй случай. Суммарный объем производства больше суммарного объема потребления: . (3.4) Для сведения ТЗ к закрытому типу вводят фиктивный пункт потребления с номером n+1 с объемом потребления: , (3.5) при этом полагают .
Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор... Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем... Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все... Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычислить, когда этот... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|