Свойство двойственности задач ЛП.

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

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

Исходная задачаимеет вид:

(5)

,

или, в матричной форме,

(6)

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

(7)

или, в матричной форме,

(8)

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

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

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

(1)

,

или, в матричной форме,

(2)

Рассмотрим теперь следующую задачу

(3)

,

или, в матричной форме,

(4)

Пара задач (1) и (3) (или, в матричной форме, пара задач (2) и (4)) называются двойственнымидруг другу задачами в симметричной форме.

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

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

Если одна из двойственных задач неразрешима из-за (или , то другая задача также не имеет допустимых решений.

Теорема 2: Для оптимальности допустимых решений и пары двойственных задач необходимо и достаточно, чтобы они удовлетворяли системе уравнений

=0

0

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

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

На основании рассмотренных несимметричных и симметричных двойственных задач можно заключить, что математические модели пары двойственных задач могут иметь один из следующих видов.

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

(1) Исходная задача Двойственная задача

Z_min = CX;f_max = YA₀;

AX = A₀; YA £ С.

X³ 0.

(2) Исходная задача Двойственная задача

Z_max = CX;f_min = YA₀;

AX = A₀; YA ³С.

X³ 0.

С и м м е т р и ч н ы е з а д а ч и

(3) Исходная задача Двойственная задача

Z_min = CX;f_max = YA₀;

AX³A₀; YA £ С.

X³ 0. Y³ 0.

(4) Исходная задача Двойственная задача

Z_max = CX;f_min = YA₀;

AX£A₀; YA ³С.

X³ 0. Y³ 0.

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

Транспортная задача.

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

Если сумма запасов груза равна суммарной потребности в нем, то транспортная задача называется закрытой. Если сумма запасов груза не равна суммарной потребности в нем, то транспортная задача является открытой.

Транспортная задача называется закрытой, если выполняется условие баланса : суммарный объем производства равен суммарному объему потребления:

. (3.1)

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

Открытая ТЗ имеет место в двух случаях.

Первый случай. Суммарный объем производства меньше суммарного объема потребления:

. (3.2)

Известно, что для существования допустимого решения транспортной задачи необходимо и достаточно, чтобы задача была закрытой. Поэтому транспортную задачу открытого типа предварительно необходимо свести к закрытой, для чего вводится фиктивный пункт производства с номером m+1 с объемом производства:

, (3.3)

при этом полагают .

Второй случай. Суммарный объем производства больше суммарного объема потребления:

. (3.4)

Для сведения ТЗ к закрытому типу вводят фиктивный пункт потребления с номером n+1 с объемом потребления:

, (3.5)

при этом полагают .

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