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

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

Рассмотрим двойственную задачу в общей постановке.

1. Пусть ограничения исходной задачи имеют вид:

а₁₁х₁+а₁₂х₂+…+а_1nx_n ≤ b₁

а₂₁х₁+а₂₂х₂+…+а_2nx_n ≤ b₂

………………………….

a_m1х₁+а_m2х₂+…+а_mnx_n ≤ b_m

x_i ≥ 0, i=1,2,…,n

На множестве решений этой системы требуется максимизировать функцию

F = c₁x₁+c₂x₂+…+c_nx_n.

Двойственной для этой задачи будет задача с ограничениями:

а₁₁z₁+а₂₁z₂+…+а_m1z_m ≤ c₁

а₁₂z₁+а₂₂z₂+…+а_m2z_m ≤ c₂

………………………….

a_1nz₁+а_2nz₂+…+а_mnz_n ≤ c_n

y_i ≥ 0, i=1,2,…,m

и минимизируемой целевой функцией

F_g = b₁z₁+b₂z₂+…+b_mz_m.

Сравнивая обе задачи, нетрудно заметить, что:

1. Матрица из коэффициентов при переменных в исходной задаче

и аналогичная матрица в двойственной задаче

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

2. В исходной задаче n переменных и m ограничений, в двойственной – m переменных

и n ограничений.

3. Каждому i-му ограничению исходной задачи соответствует переменная двойственной задачи (Z_i), которую определяют как двойственную переменную. Первому ограничению исходной задачи соответствует двойственная переменная Z₁, второму – Z₂, ограничению m - Z_m.

4. Каждой переменной исходной задачи соответствует ограничение двойственной задачи. В исходной системе n переменных: х₁, х₂,…, х_n. Следовательно, двойственная задача должна иметь n ограничений.

5. В правых частях систем ограничений каждой из задач стоят коэффициенты целевой функции, взятой из другой задачи.

6. В систему ограничений исходной задачи входят неравенства типа ≤, причем в задаче требуется максимизировать целевую функцию F. В систему ограничений двойственной задачи входят неравенства типа ≥.

7. Максимизация целевой функции исходной задачи заменяется минимизацией целевой функции двойственной задачи, при этом:

max F = min F_д (2.23)

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

	x1	x2	x3	…………..	xn
z1	a11	a12	a13	…………..	a1n	b1
z2	a21	a22	a23	…………..	a2n	b2
z3	a31	a32	a33	…………..	a3n	y3
………..	…………	…………	…………	…………..	…………	………….
zm	am1	am2	am3	…………..	amn	bm
	C1	C2	C3	…………..	Cn	ci bi

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

Чтобы получить, например, первое ограничение двойственной задачи, надо найти сумму произведений чисел, стоящих в столбце под х₁, на соответствующие переменные первого столбца:

а₁₁z₁+a₂₁z₂+…+a_m1z_m,

при условии, что эта сумма не меньше с₁, т.е:

а₁₁z₁+a₂₁z₂+…+a_m1z_m ≥ с₁.

Аналогично составляются и остальные ограничения для двойственной задачи.

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

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

Рассмотрим на примере, как составляется двойственная задача. Пусть имеется исходная задача:

F = 4x₁+5x₂+9x₃ → max

x₁+x₂+2x₃ ≤ 16 (2.24)

7x₁+5x₂+3x₃ ≤ 25

x_j ≥ 0 (j=1,2,3)

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

Матрица коэффициентов исходной задачи:

Следовательно, транспонированная матрица:

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

Таким образом для рассматриваемой исходной задачи (2.24) можно записать двойственную задачу:

F_д = 16z₁+25z₂ → min

z₁+7z₂ ≥ 4

z₁+5z₂ ≥ 5

2z₁+3z₂ ≥ 9

z_i ≥ 0 (i=1,2)

В общем виде можно записать, что исходной задаче:

(2.25)

x_j ≥ 0; i=1,…m; j=1,…n

Соответствует двойственная задача:

(2.26)

z_i ≥ 0; i=1,…m; j=1,…n

Сформулированное понятие двойственность находит широкое практическое применение. Это, во-первых, связано с упрощением получения решения задачи линейного программирования, которое может быть сведено к решению двойственной задачи. Такое сведение особенно выгодно тогда, когда число ограничений исходной задачи велико и значительно превышает число переменных. Нужно заметить, что объем вычислений в задачах линейного программирования при использовании для решения симплексного метода прежде всего определяется числом ограничений.

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