Эквивалентные постановки задач ЛП

Общая постановка:

n

j =1

 n

cjxj→ max(min),

j =1 aijxj≤ bi,i ∈ I 1

n

n





 j =1 aij xj = bi,i ∈ I 2

 j =1 aijxj≥ bi,i ∈ I 3

 j 1

x ≥ 0, j ∈ N,





 xj∈ R, j ∈ N 2,

 xj≤ 0, j ∈ N 3,

где cj, aij, bi – заданные числовые параметры, множества I 1, I 2и I 3попарно не пересе- каются, I 1 ∪ I 2 ∪ I 3= { 1 ,..., m}, R – множество действительных чисел, множества N 1, N 2 и N 3 попарно не пересекаются, и N 1 ∪ N 2 ∪ N 3 = { 1 ,..., n}. Cуществует несколько

эквивалентных постановок задач ЛП:

– Задачи максимизации и минимизации. Для перехода от одной задачи к другой коэффи- циенты целевой функции можно умножить на -1.

– Задачи с ограничениями типа ”=”, ” ≤ ” и ” ≥ ”. Для перехода от ограничения ” ≤ ” к ограни-

чению ” ≥ ” и наоборот достаточно домножать соответствующее ограничение на -1. Огра-

ничение типа ”=” может быть представлено в виде двух ограничений ” ≤ ” и ” ≥ ” с той же

левой и правой частью. Для перехода от ограничений типа ”=” к ограничениям типа ≤

можно применить метод Гаусса. Например, рассмотрим задачу

−x 1 − x 2 + x 5 → min

 x 1 + x 2 = 1



 x 2 − 2 x 3 = − 3

−

x 3 x 4 + x 5 = 1





 xj≥ 0

При помощи метода Гаусса выделяем единичную подматрицу в матрице ограничений.

																		-2
		-2			-3	⇒			-2			-3	⇒				-2		-1
			-1							-1							-1

Эквивалентная задача

 x 1 = 2 − (2 x 4 − 2 x 5) ≥ 0



x 2 = − 1 − (− 2 x 4 + 2 x 5) ≥ 0

 x 3 = 1 − (−x 4 + x 5) ≥ 0

− 2 + 2 x 4 − 2 x 5 − 1 + 2 x 4 − 2 x 5 + x 5 = − 3 + 4 x 4 − 3 x 5 → min

 2 x 4



− 2 x 5 ≤ 2

 − 2 x 4 + 2 x 5 ≤ − 1

 −x 4 + x 5 ≤ 1

 x 4, x 5 ≥ 0

Для перехода от ограничений типа ≤ к ограничениям типа = достаточно ввести дополни- тельные неотрицательные переменные, по одной для каждого ограничения ≤. Эти пере-

менные войдут в целевую функцию с нулевыми коэффициентами.

Переменная xj∈ R может быть представлена в виде двух новых неотрицательных пере-

менных: xj = x + − x−, x + ≥ 0, x− ≥ 0.

j j j j

Для каждой задачи ЛП можно сформулировать двойственную ей задачу. Рассмотрим задачу максимизации с ограничениями ” ≤ ”. Представим эту задачу в матричной форме:

cx → max, Ax ≤ b,

где c = (c 1 ,..., cn) – вектор-строка, x = (x 1 ,..., xn) T – вектор-столбец, A = ||aij|| – матрица размерности m × n, b = (b 1 ,..., bm) T – вектор-столбец. Отметим, что ограничения x ≥ 0 отсутствуют. Они могут быть войти в ограничения Ax ≤ b путем введения эквивалентных ограничений −x ≤ 0. Введем в рассмотрение двойственную ей задачу:

yb → min,

yA = c, y ≥ 0,

где y = (y 1 ,..., ym) – вектор-строка двойственных переменных или потенциалов. Пусть Ai обозначает строку i матрицы A, а Aj – столбец j этой же матрицы. Соответствие между компонентами прямой и двойственной задач представлено в следую- щей таблице.

Прямая задача	Двойственная задача
max {cx} Aix≤ bi,i ∈ I 1 Aix = bi,i ∈ I 2 xj≥ 0, j ∈ N 1 xj∈ R, j ∈ N 2 xj ≤ 0, j ∈ N 3	min {yb} yi≥ 0, i ∈ I 1 yi ∈ R, i ∈ I 2 yAj≥ cj, j ∈ N 1 yAj = cj, j ∈ N 2 yAj≤ cj, j ∈ N 3

Теорема 1 (Теорема двойственности) Справедливо одно из следующих утверждений:

а) обе задачи, прямая и двойственная ей, имеют допустимые решения и

max {cx} = min {yb},

б) если одна из задач, прямая и двойственная ей, не имеет допустимого решения а другая имеет, то целевая функция другой задачи не ограничена.

в) обе задачи не имеют допустимых решений.

Теорема 2 (О дополняющей нежесткости) Пусть x и y – допустимые решения прямой и двойственной задач соответственно. Тогда следующие условия а), б) и в) эквивалент- ны:

а) x и y оптимальные решения прямой и двойственной задач, б) cx = yb,

в) (условие дополняющей нежесткости) yi (Aix− bi)= 0 i = 1 ,..., m, и (yAj− cj) xj = 0,

j = 1 ,..., n.

Из этой теоремы, например, следует, что если решения прямой и двойственной задач допу- стимы и выполняется условие в) дополняющей нежесткости, то эти решения оптимальны. Оптимальное решение прямой задачи может быть получено из оптимального решения двойственной задачи. Например, рассмотрим задачу

4 x 1 − 3 x 2 − 6 x 3 − x 4 → max,



 − 2 x 1 − x 2 + 5 x 3 + 2 x 4 ≥ 2

− 3 x 1 + x 2 − x 3 − x 4 ≥ 1

 xi≥ 0, i = 1, 2, 3, 4

Построим двойственную ей задачу

2 y 1 + y 2 → min,

 − 2 y 1 − 3 y 2 ≥ 4

 −y 1 + y 2 ≥ − 3







5 y 1 − y 2 ≥ − 6



 2 y 1 − y 2 ≥ − 1

 yj ≥ 0, j = 1, 2

Решим двойственную задачу графически: y∗ = (− 9 / 4 ,− 21 / 4), z∗ = − 39 / 4. Оптимальное

решение определяется пересечением линий, соответствующих ограничению 2 и 3 двой-

ственной задачи. Эти ограничения выполняются как строгие равенства, а остальные - как нестрогие. Тогда по условию дополняющей нежесткости должно выполняться x∗ = 0,

4 = 0, x 2 и x 3 могут быть найдены из равенств −x 2 + 5 x 3 = 2 и x 2 − x 3 = 1 (рассмат-

x∗ ∗ ∗

∗ ∗ ∗ ∗

риваем подматрицу матрицы прямой задачи, состоящую из столбцов 2 и 3). Получаем

x∗ = (0, 7 / 4, 3 / 4, 0).

Дата добавления: 2015-07-08