Заглавная страница
Избранные статьи
Случайная статья
Познавательные статьи
Новые добавления
Обратная связь

ТОП 10 на сайте

Приготовление дезинфицирующих растворов различной концентрации

Техника нижней прямой подачи мяча.

Франко-прусская война (причины и последствия)

Организация работы процедурного кабинета

Смысловое и механическое запоминание, их место и роль в усвоении знаний

Коммуникативные барьеры и пути их преодоления

Обработка изделий медицинского назначения многократного применения

Образцы текста публицистического стиля

Четыре типа изменения баланса

Задачи с ответами для Всероссийской олимпиады по праву

Мы поможем в написании ваших работ!

ЗНАЕТЕ ЛИ ВЫ?

Влияние общества на человека

Приготовление дезинфицирующих растворов различной концентрации

Практические работы по географии для 6 класса

Организация работы процедурного кабинета

Изменения в неживой природе осенью

Уборка процедурного кабинета

Сольфеджио. Все правила по сольфеджио

Балочные системы. Определение реакций опор и моментов защемления

Главная Избранные Случайная статья Познавательные Новые добавления Обратная связь FAQ

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

⇐ ПредыдущаяСтр 49 из 58Следующая ⇒

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

Необходимость изучения двойственной задачи ЛП (ДЗЛП) обусловлена следующими причинами. Во-первых, трудности в

решении задач ЛП зависят не от количества переменных n, а от количества ограничений m, определяющих число итераций симплекс-метода. Поэтому, если ПЗЛП, еще не приведенная к стандартной форме, содержит большое количество ограниче- ний (m > n), то в этом случае целесообразно перейти к ДЗЛП. Сформированная ДЗЛП будет иметь m переменных и n ограни- чений, т. е. количество итераций при этом уменьшится. Во-вто- рых, наличие связей между оптимальными решениями ПЗЛП и ДЗЛП позволили разработать двойственный симплекс-ме- тод, который находит применение при анализе чувствитель- ности задач ЛП и в процедурах целочисленного линейного про- граммирования.

При переходе к ДЗЛП в качестве исходной принимается стандартная форма прямой задачи ЛП. ДЗЛП формируется по следующим правилам:

1) каждому ограничению ПЗЛП соответствует переменная ДЗЛП yi, i = 1, …, m; правая часть ограничения ПЗЛП bi стано- вится коэффициентом ЦФ W(x) ДЗЛП при переменных yi;

2) каждой переменной ПЗЛП xj, j = 1, …, n, соответствует

ограничение ДЗЛП; коэффициенты ЦФ Z ПЗЛП cj становятся правыми частями ограничений ДЗЛП;

3) коэффициенты aij при переменных xj в ПЗЛП становятся коэффициентами при переменных yi в ДЗЛП.

При переходе к ДЗЛП происходит изменение направле-

ния оптимизации, ограничений и переменных, что отражено в табл. 9.5.

Таблица 9.5

Прямая задача ЛП в стандартной форме

Двойственная задача ЛП

ЦФ

Ограничения

Переменные

max

min

≥

Не имеют ограни- чений в знаке

min

max

≤

Пример 9.8. Дана прямая задача ЛП: найти max W(x) = x1 + 2x2

при ограничениях: x1 + x2 ≤ 8;

- x1 + x2 ≤ 2; x1 + x2 ≥ 4; x1, x2 ≥ 0.

Необходимо сформировать двойственную задачу ЛП.

Для построения ДЗЛП требуется прямую задачу привести к стандартной форме:

найти max W(x) = x1 + 2x2 + 0s1 + 0s2 + 0s3 − MR3

при ограничениях: x1 +	x2 +	s1		= 8 → y1;
- x1 +	x2 +		s2	= 2 → y2;
x1 +	x2 −		s3 + R3	= 4 → y3;
x1,	x2 ≥	0,	s1, s2,	s3 ≥ 0.
↓	↓	↓	↓ ↓	↓ ↓
1-е	2-е	3-е	4-е 5-е	6-е W(x)
огр.	огр.	огр.	огр. огр.	огр.

В соответствии с приведенными выше правилами сформи- рованная ДЗЛП имеет вид:

найти min W(x) = 8y1 + 2y2 + 4y3

при ограничениях: y1 − y2 + y3 ≥ 1,

y1 + y2 + y3 ≥ 2,

y1 ≥ 0, y2 ≥ 0, -y3 ≥ 0 (y3 ≤ 0), y3 ≥ -M.

По правилам, приведенным в табл. 9.5, двойственные пере- менные y1, y2, y3 не ограничены в знаке, однако введение оста- точных переменных в ПЗЛП приводит к появлению более жес- тких условий: y1 ≥ 0, y2 ≥ 0 — неотрицательности переменных. Для переменной y3 условие неограниченности в знаке остается в силе. Дело в том, что величина М имеет большое положитель- ное значение, поэтому ограничение y3 ≥ -M равносильно неогра- ниченности переменной y3 как в знаке, так и в значении.

При решении ДЗЛП ее необходимо представить в виде раз-

ности двух неотрицательных переменных: y3 = y3′ − y3″, y3′ ≥ 0, y3″ ≥ 0.

Между оптимальными решениями прямой и двойственной

задачами ЛП существует тесная взаимосвязь. Это означает,

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

Рассмотрим эту связь на прямой и двойственной задачах примера 9.8. В табл. 9.6 и 9.7 приведены оптимальные решения соответственно прямой и двойственной задач ЛП. Из сравнения таблиц можно установить следующее. Во-первых, в точке, со- ответствующей оптимальным решениям обеих задач, выполня- ется равенство: max W(x) = min W(x). В задаче максимизации ЦФ последовательно увеличивается от начального значения до оптимального W(x) = 13. В задаче минимизации ЦФ уменьшает- ся от начального значения до оптимального W(x) = 13. Из этого следует, что процессы максимизации и минимизации сходят- ся в некоторой “точке равновесия”, после достижения которой ЦФ задач улучшить невозможно. Такая точка достигается при равенстве значений ЦФ и соответствует их оптимальным зна- чениям. Во-вторых, базисные решения ПЗЛП можно получить непосредственно из оптимальной симплекс-таблицы ДЗЛП, и наоборот. В табл. 9.4 темным цветом выделены переменные начального базиса прямой задачи и коэффициенты при них в Z-строке. Этим переменным соответствуют 3-е, 4-е и 6-е огра- ничения ДЗЛП (y1 ≥ 0, y2 ≥ 0, y3 ≥ -M).

Двойственные переменные определяются по следующему

правилу: коэффициент при начальной базисной переменной в оптимальном Z-уравнении ПЗЛП равен разности между левой и правой частями ограничения ДЗЛП, ассоциированного с данной начальной переменной. В данном случае 3/2 = y1 − 0, 1/2 = y2 − 0, M = y3 + M. Отсюда, y1 = 3/2, y2 = 1/2 и y3 = 0, в справедливости чего можно убедиться, сравнив эти значения двойственных пе- ременных с оптимальным решением ДЗЛП в табл. 9.6.

Аналогичным образом могут быть получены значения пе-

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

при построении двойственной к ДЗЛП задачи переменной R1 бу- дет соответствовать переменная x1 прямой задачи, а переменной R2 — переменная x2 прямой задачи с условиями x1 ≥ M и x2 ≥ M.

Таблица 9.6

Базис	x 1	x 2	s 1	s 2	s 3	R 3	Решение
Z	0	0	3/2	1/2	0	M	13
s 3	0	0	1	0	1	-1	4
x 2	0	1	1/2	1/2	0	0	5
x 1	1	0	1/2	-1/2	0	0	3

Значения переменных ПЗЛП определяются по следующе- му правилу: коэффициенты в оптимальном Z-уравнении равны разности между левыми и правыми частями соответствующих ограничений прямой задачи, ассоциированных с начальными переменными ДЗЛП. В данном случае имеем: 3 − M = x1 − M, 5 − M = x2 − M, откуда x1 = 3 и x2 = 5, что соответствует опти- мальному решению ПЗЛП в табл. 9.7.

Таблица 9.7

Базис	y 1	y 2	y 3′	y 3″	s 1	R 1	s 2	R 2	Решение
Z	0	0	0	0	-3	3 − M	-5	5 − M	13
y 1	1	0	-1	0	-1/2	1/2	-1/2	1/2	3/2
y 2	0	1	0	-1	1/2	-1/2	-1/2	1/2	1/2

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

1) преобразование всех ограничений задачи ЛП в ограни- чения типа ≤, при этом часть ограничений будет иметь отри-

цательные правые части; для всех ограничений вводятся оста- точные переменные;

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

3) проверка условия оптимальности, которая заключается в выборе переменной, включаемой в состав базисных на очеред- ной итерации. Для этого вычисляются отношения коэффици- ентов Z-строки к соответствующим коэффициентам ведущей строки. Отношения с положительным или нулевым значени- ем знаменателя не учитываются. В задаче минимизации ЦФ вводимой переменной должно соответствовать наименьшее из указанных отношений, а в задачах максимизации ЦФ — от- ношение, наименьшее по абсолютной величине. Задача ЛП не имеет решения, если знаменатели всех отношений равны нулю или положительны;

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

Пример 9.9. Найти min W(x) = 2x1 + x2 при ограничениях 3x1 + x2 ≥ 3;

4x1 + 3x2 ≥ 6;

x1 + 2x2 ≤ 3; x1, x2 ≥ 0.

После преобразований получим следующую задачу:

3x1 +	x2 + s1			= -3;
4x1 +	3x2	+ s2		= -6;
x1 +	2x2		+ s3	= 3;

найти min W(x) = 2x1 + x2 + 0s1 + 0s2 + 0s3 при ограничениях

x1, x2 ≥ 0, s1, s2, s3 ≥ 0.

Начальная симплекс-таблица представлена в табл. 9.8.

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

Таблица 9.8

Базис	x 1	x 2	s 1	s 2	s 3	Решение
Z	-2	-1	0	0	0	0
s 1	-3	-1	1	0	0	-3
s 2	-4	-3	0	1	0	-6
s 3	1	2	0	0	1	3

Включаемой в состав базисных является переменная x2, для которой характерно минимальное отношение коэффици- ента Z-строки к коэффициенту ведущей строки — 1/3 (для пе- ременной x1 это отношение составляет 1/2 > 1/3). Далее выпол- няется процедура пересчета симплекс-таблицы.