Элементы модели

Искомые неизвестные	Целевая функция
u₁, u₂, u₃, u₄	Z(u)=400u₁+365u₂+100u₃+350u₄
Ограничения
0,6u₁+0,4u₂+u₃+0u ≥16 0,5u₁+0,8u₂-u₃+u₄≥14 u₁, u₂, u₃, u₄≥0

 

Симметрия исходной и двойственной задач хорошо видна из сводной таблицы параметров и элементов решения этих двух задач (табл.4.3). Как видно из этой таблицы, в исходной задаче две переменные и четыре ограничения; в двойственной-наоборот: четыре переменные и два ограничения. Исходная задача-это задача на максимум прибыли производителя продуктов; двойственная-на минимум издержек покупателя ресурсов.

Целевая функция исходной задачи формируется как сумма произведений строки переменных (количество продуктов разного типа x₁,x₂) на строку прибылей от производства единицы каждого продукта; целевая функция двойственной задачи - как сумма произведений столбца переменных (теневых цен ресурсов u₁-u₄) на столбец запасов этих ресурсов.

Аналогично ограничение на расход каждого из используемых ресурсов в исходной задаче формируется как сумма произведений строки переменных (x₁,x₂) на расход данного ресурса при производстве единицы каждого продукта. Ограничение на выручку от продажи ресурсов, идущих на производство данного продукта в двойственной задаче, формируется как сумма произведений столбца теневых цен (u₁-u₄) на столбец расходов каждого из используемых ресурсов на производство единицы данного продукта.

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

 

Таблица 4.3

 

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

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 (4.2)

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; (4.3)

u_i≥0; i=1, m;

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

 

2. Левая часть ограничения двойственной задачи (4.3), соответствующая переменной x_j, представляет собой сумму произведений коэффициентов столбца при переменной х_jограничений прямой задачи (4.2) на соответствующие им двойственные переменные. В качестве правой части этого же ограничения берется коэффициент целевой функции при переменной 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. (4.4)

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

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