9. Основные теоремы двойственности

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

Теорема 1. Если одна из пары двойственных задач имеет решение, то и другая имеет решение, причём оптимальные значения целевых функций совпадают: F_max = Z_min. Если же одна из пары двойственных задач не имеет решения из-за неограниченности целевой функции (F_max → ∞ или Z_min → - ∞), то и другая не имеет решения ввиду несовместности системы ограничений.

Теорема 2. Допустимые решения Х = и Y = являются оптимальными решениями пары двойственных задач тогда и только тогда, когда выполняются следующие равенства:

;

.

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

Пример 11. Решить ЗЛП:

F(Х) = → max,

.

Решение. Составим для данной ЗЛП двойственную. Так как она будет зависеть от двух переменных, то решим её графическим методом. Затем, используя теоремы двойственности найдём решение исходной задачи.

Исходная ЗЛП является канонической (в системе ограничений только уравнения), поэтому, пользуясь алгоритмом составления несимметричной двойственной задачи, получим следующую пару двойственных задач:

Исходная ЗЛП	Двойственная ЗЛП
F(Х) = → max,	Z(Y) = → min,

Решение двойственной задачи графическим методом представлено на рис. 3.

ОДР данной задачи – неограниченная область с вершиной A; на рис. 3 она заштрихована.

Нормальный вектор = (9; 25). Перпендикулярно вектору строим линию уровня = 0. Перемещаем её в направлении вектора до первой точки А (7,2; 2,8), в которой она касается ОДР.

А

Рис. 3. Решение двойственной задачи графическим методом

Минимум достигается в вершине А. .

По 1-й теореме двойственности .

По 2-й теореме двойственности найдём оптимальное решение (х₁, х₂, х₃) исходной задачи. Для этого подставим найденное оптимальное решение двойственной задачи y₁ = 7,2; y₂ = 2,8 в систему ограничений двойственной задачи:

Так как х₁ = 0, то система ограничений исходной задачи принимает вид:

Решение данной системы: х₂ = 12,2; х₃ = 15,4. Следовательно, получено оптимальное решение исходной задачи: (0; 12,2; 15,4). При этом

.

10. Двойственный симплексный метод

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

Пусть ЗЛП задана в канонической форме .

Почти допустимым опорным решением (ПДОР) ЗЛП называется такой n-мерный вектор Х = , который удовлетворяет системе ограничений (1) задачи, не удовлетворяет условиям неотрицательности и для которого векторы условий, соответствующие отличным от нуля координатам, линейно независимы.

В двойственном симплекс-методе рассматривают ПДОР, при которых оценки разложений векторов условий по базису ПДОР соответствуют признаку оптимальности, т.е.

• в задаче на максимум ≥ 0 ;

• в задаче на минимум ≤ 0 .

Признак оптимальности ПДОР: ПДОР оптимально, если оно является допустимым.

Если в ЗЛП на максимум (минимум) для ПДОР с неотрицательными (неположительными) оценками хотя бы одна координата < 0, а среди коэффициентов (j = 1, 2, …, n) разложений векторов условий по базису данного решения есть хотя бы один отрицательный , то решение может быть улучшено. Новое ПДОР получается, если базисную переменную х_l заменить на х_k. Номер k находят из условия

= , d_lj < 0. (13)

Признак отсутствия решения ЗЛП ввиду несовместности системы ограничений: если для ПДОР существует хотя бы одна отрицательная координата < 0, а среди коэффициентов (j = 1, 2, …, n) разложений векторов условий по базису данного решения нет отрицательных, то ЗЛП не имеет решений ввиду несовместности системы ограничений.

Алгоритм двойственного симплекс-метода

1) Привести ЗЛП к каноническому виду.

2) Найти ПДОР с базисом из единичных векторов. Вычислить оценки векторов условий по базису этого решения. Если они соответствуют признаку оптимальности, то решить ЗЛП двойственным симплекс-методом.

3) Если ПДОР не имеет отрицательных координат, то оптимальное решение получено.

4) Если ПДОР имеет отрицательную координату < 0, а среди коэффициентов (j = 1, 2, …, n) разложений векторов условий по базису данного решения нет отрицательных ( ), то ЗЛП не имеет решений ввиду несовместности системы ограничений.

5) Если хотя бы одна координата ПДОР < 0, а среди коэффициентов (j = 1, 2, …, n) разложений векторов условий по базису данного решения есть хотя бы один отрицательный , то следует перейти к новому решению. Номер k вектора, вводимого в базис, находят из условия (5.20). Номер l вектора, выводимого из базиса, находят из условия:

• в задаче на максимум;

• в задаче на минимум.

Перейти к выполнению пункта 3 данного алгоритма.

Алгоритм закончит работу через конечное число шагов (оптимальное ОР будет получено при выполнении 3-го или 4-го пунктов). Расчёты оформляются в симплекс-таблицы.

Пример 10. Решить ЗЛП двойственным симплекс-методом.

F(Х) = → max,

≥ 0, i = 1, 2, 3, 4.

Решение. Задача является канонической. Составим симплекс-таблицу (табл. 6)

Таблица 6

Базис			2 6 2 -1				Свободные коэффициенты
			х1	х2	х3	х4
х3 х4	2 -1		2 -1	3 -2	1 0	0 1	30 -10
			3	2	0	0	70
х3 х2		2 6	1/2 1/2	0 1	1 0	3/2 -1/2	15 5
			2	0	0	1	60

1 шаг. На первом шаге двойственного симплекс-метода (первая часть табл. 6) базисные переменные - х₃, х₄; свободные переменные - х₁, х₂. Во 2-м столбце записаны коэффициенты целевой функции при базисных переменных х₃, х₄.

Число 30∙2 + (- 10)∙(- 1) = 70 записано в последней строке последнего столбца первой части табл. 16.

;

.

Числа , записаны в последней строке первой части табл. 16 в столбцах, соответствующих свободным переменным х₁, х₂. Оценки базисных переменных х₃, х₄ равны нулю.

По последнему столбцу записываем первое полученное опорное решение (0, 0, 30, - 10). Значение целевой функции F(0, 0, 30, - 10) = 70.

В строке оценок все числа неотрицательные, следовательно, получено ПДОР (0, 0, 30, - 10). Оно не является допустимым (т.к. х₄ < 0), по признаку оптимальности ПДОР не является оптимальным.

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

Сначала выберем уравнение, в котором заменяется базисная переменная. Чтобы целевая функция уменьшилась, правая часть и соответствующий опорный элемент должны быть отрицательными. У нас есть только одна отрицательная правая часть (во 2-м уравнении), поэтому заменим переменную во 2-м уравнении.

Номер k переменной найдём из условия (13):

.

В качестве базисной переменной выбираем х₂.

Во 2-й строке первой части табл. 14 базисная переменная х₄ заменяется на х₂. Опорный элемент таблицы d₂₂ = - 2 (выделен полужирным курсивом).

2 шаг. Во второй части табл. 6 базисные переменные - х₃, х₂; свободные переменные - х₁, х₄. Пересчитываем коэффициенты при неизвестных, свободные члены. Оценки:

15∙2 + 5∙6 = 60;

;

.

По последнему столбцу записываем 2-е полученное ОР (0, 5, 15, 0). Оно является допустимым и оптимальным, F_max(0, 5, 15, 0) = 60.

Заметим, что для заданной ЗЛП можно составить двойственную к ней и по полученному решению исходной задачи записать оптимальное решение двойственной ЗЛП.

Имеем следующую несимметричную пару двойственных задач.

Исходная ЗЛП	Двойственная ЗЛП
F(Х) = → max,	Z(Y) = → min,

По 1-й теореме двойственности Z_min = F_max = 60. Оптимальное решение двойственной ЗЛП: (2, 0).

Контрольные вопросы:

1. Расскажите общий принцип приведения ЗЛП к канонической форме.

2. Дайте определение опорного решения. Каким образом оно находится? Когда опорное решение будет являться вырожденным (невырожденным)?

3. Каким образом осуществляется переход к новому опорному решению? Объясните правило прямоугольника.

4. Каким образом можно выразить целевую функцию через свободные переменные?

5. Перечислите признаки неограниченности целевой функции.

6. Перечислите признаки оптимальности опорного решения.

7. Объясните суть симплексного метода, расскажите алгоритм решения симплексным методом.

8. Дайте определение двойственной задачи. Перечислите и охарактеризуйте каждый из видов двойственных задач.

9. Объясните алгоритмы составления симметричной и несимметричной двойственных задач.

10. Назовите основные теоремы двойственности.

11. Объясните суть и алгоритм двойственного симплексного метода.

Литература:

1. Высшая математика для экономистов: Учебник для вузов / Н.Ш. Кремер, Б.А. Путко, И.М. Тришин, М.Н.Фридман. Под ред. Н.Ш. Кремера. – М.: ЮНИТИ, 2005. – 471 с.

2. Общий курс высшей математики для экономистов: Учебник. / Под ред. В.И. Ермакова. –М.: ИНФРА-М, 2006. – 655 с.

3. Сборник задач по высшей математике для экономистов: Учебное пособие / Под ред.В.И. Ермакова. М.: ИНФРА-М, 2006. – 574 с.

4. Данко П.Е., Попов А.Г., Кожевникова Т.Я. Высшая математика в упражнениях и задачах. Ч. 1, 2. – М.: Оникс 21 век: Мир и образование, 2005. – 304 с. Ч. 1; – 416 с. Ч. 2.

5. Математика в экономике: Учебник: В 2-х ч. / А.С. Солодовников, В.А. Бабайцев, А.В. Браилов, И.Г. Шандара. – М.: Финансы и статистика, 2006.

6. Шипачев В.С. Высшая математика: Учебник для студ. вузов – М.: Высшая школа, 2007. – 479 с.