Software & Systems

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

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

В векторно-матричной форме основную задачу при наличии упомянутых выше ограничений можно представить в виде вектора переменных состояния:.

Функция цели: .

Ограничения:  .

Дуальная задача имеет математическую интерпретацию в виде вектора переменных состояния: .

Функция цели:

.

Ограничения:  .

Приведенные выше уравнения представлены в форме, пригодной для выполнения расчетов ЛП с помощью функции linprog пакета Optimization Toolbox среды MatLAB.

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

Основная задача: c1=[3 1]; A1=[3 2; -4 1]; b1=[24 -8]′; A1eq=[1 -2]; b1eq=0.

Нижняя и верхняя границы переменных состояния основной задачи: lb1=[0 1]′; ub1=[inf 3]′.

В режиме прямых вычислений получим решение задачи ЛП: [x1,z1]=linprog(c1,A1,b1,A1eq, b1eq,lb1,ub1).

В результате минимум z1=8 при значении вектора x1=[2.2857 1.1429]′.

Дуальная задача: с2=[24 -8 0]; A2=[-3 4 -1]; b2=[3]; A2eq=[2 1 -2]; b2eq=[-1].

Верхнюю и нижнюю границы u(2) вектора переменных состояния дуальной задачи  определим путем подстановки в условие-равенство двух ограничений равенств: A2eq=[2 1 -2; c2], b2eq=[-1 c1*lb] и A2eq=[2 1 -2; c2], b2eq=[-1 c1*x1], где х1=[2.2851 1.1429]′ – оптимальное решение основной задачи.

В результате находим решение для случая, когда нижняя и верхняя границы вектора u при вариации u(2) равны:

lb2=[0  0.2024  0]′, ub2=[inf  1 inf]′.

Используем их при записи функции linprog для решения дуальной задачи: [u,z2]=linprog(c2, A2,b2,A2eq,b2eq,lb2,ub2).

Окончательно имеем: u=[0 1 1]′, Z2=-z2=8.000.

Заметим, что Z2=-z2 принято согласно правилам перехода от основного к дуальному варианту решения.

Таким образом, элементу вектора  в дуальной задаче соответствует u(2) с ограничениями .