Математические основы теории двойственности

Сформулируем правила составления двойственной задачи к стандартной форме записи прямой задачи ЛП.

1. Каждому ограничению исходной задачи ставится в соответствие переменная двойственной задачи

u₁↔a₁₁x₁+…+a₁_jx_j+…+a_1nx_n≤b₁;

u_i↔a_i₁x₁+…+a_ijx_j+…+a_inx_n≤b_i

u_m↔a_m₁x₁+…+a_mjx_j+…+a_mnx_n≤b_m (3.7)

x_j≥0; j=1, n

F(x) x=c₁x₁+…+c_jx_j+…+c_nx_n→max

Каждой переменной исходной задачи ставится в соответствие ограничение двойственной задачи

x₁↔a₁₁u₁+…+a_i1u_i+…+a_m₁u_m ≥ c₁;

x_j↔a₁_ju₁+…+a_iju_i+…+a_mju_m ≥ c_j;

x_n↔a₁_nu₁+…+a_inu_i+…+a_mnu_m ≥ c_n; (3.8)

u_i≥0; i=1, m;

Z (u)=b₁u₁+…+b_iu_i+…+b_mu_m→min

2. Левая часть ограничения двойственной задачи (3.8), соответствующая переменной x_j, представляет собой сумму произведений коэффициентов столбца при переменной х_j ограничений прямой задачи (3.7) на соответствующие им двойственные переменные. В качестве правой части этого же ограничения берется коэффициент целевой функции при переменной x _j прямой задачи. Между левой и правой частями ограничения двойственной задачи ставится знак ≥.

3. Граничные условия на переменные двойственной задачи заключается в требовании их не отрицательности u_i≥0; i=1,m.

4. Целевая функция двойственной задачи представляет собой сумму произведений правых частей ограничений прямой задачи на соответствующие им двойственные переменные и ориентируется на минимум.

Эти правила можно применить при построении задачи, двойственной к прямой, после ее приведения к нижеприведенной стандартной форме записи задачи линейного программирования.

Найти u=(u₁,…u_i,…,u_m);

-a₁₁u₁-…-a_i₁u_i-…-a_m₁u_m≤-c₁;

-a₁_ju₁-…-a_iju_i-…-a_mju_m≤-c_j;

-a₁_nu₁-…-a_inu_i-…-a_mnu_m≤-c_n;

u_i≥0; i=1,m;

Z (u)’= -b₁u₁-…-b_iu_i-…-b_mu_m→max. (3.9)

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

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