Геометрическая интерпретация двойственных задач.

Если число переменных в прямой и двойственной задачах, образующих данную пару, равно двум, то, используя геометрическую интерпретацию ЗЛП, можно легко найти решение данной меры задач. При этом имеет место один из следующих трех взаимно исключающих друг друга случаев: 1) обе задачи имеют планы; 2) планы имеет только одна задача; 3) для каждой задачи двойственной пары множество планов пусто.

П р и м е р 1. Z(x)=x₁–10x₂+2x₃–x₄+7x₅  max

2x₁–x₂  1,

x₁–x₂+2x₃–x₄+x₅  4,

x₂ +x_3–x₄ = 0,

x₁ –x₃ +2x₅ 3,

x₁0, x₃0.

Р е ш е н и е. Чтобы записать задачу, двойственную к данной, приведем систему ограничений к виду

2x₁ –x₂  1,

–x₁ +x₃ –2x₅–3,

–х₁+x₂ –2x₃+x₄ –4,

х₂ + x₃ –x₄ = 0,

x₁0, x₃0.

Теперь воспользуемся определением 1 и запишем задачу, двойственную к данной: Z^*(y)=y₁-3y₂-4y₃  min,

y₁–y₂ – y₃ 1,

–y₁ + y₃+2y₄ =–10,

y₂–2y₃ +y₄  2,

–2y₂ –y₃ = 7,

y₁0, y₂0, y₃0.

2.9. Метод искусственного базиса Идея и реализация метода искусственного базиса.

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

Если ограничения ЗЛП можно преобразовать к виду AXA₀ при А₀0, то система ограничений всегда содержит единичную матрицу. Многие ЗЛП, имеющие решения, не содержат единичной матрицы и не приводятся к указанному виду. В этом случае для решения задач применяется метод искусственного базиса. Рассмотрим общую ЗЛП.

Найти минимальное значение линейной функции Z=C₁x₁+C₂x₂+...+C_nx_n при ограничениях

,

где b_i  0 и система ограничений не содержит единичной матрицы. Для получения единичной матрицы к каждому равенству прибавим по одной переменной х_n+i  0 (i=1,2,..., m), которые назовем искусственными, и рассмотрим расширенную задачу, связанную с отысканием наименьшего значения линейной функции при ограничениях

Величина М предполагается достаточно большим положительным числом, если задача решается на отыскание минимального значения линейной функции, и достаточно малым отрицательным числом, если находится максимальное значение линейной функции. Единичные векторы A_n+1, A_n+2, ..., A_n+m, соответствующие искусственным переменным, образуют искусственный базис.

Для отыскания оптимального плана исходной задачи используют следующую теорему.

Т е о р е м а 1. Если в оптимальном плане =(x₁, x₂, ...,x_n, 0, ..., 0) расширенной задачи искусственные переменные x_n+i=0 (i=1,2,...,m), то план Х=(x₁, x₂, ..., x_n) является оптимальным планом исходной задачи.

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

При опорном плане Х=(0, 0, ..., b₁, b₂, ..., b_m) расширенной задачи значение линейной формы есть , а значения _i=Z_j-c_j равны . Таким образом, Z₀ и разности Z_j-c_j состоят из двух независимых частей, одна из которых зависит от М, а другая — нет. После вычисления Z₀ и _i их значения, а также исходные данные расширенной задачи заносят в таблицу, которая содержит на одну строку больше, чем обычная симплексная таблица, при этом в (m+2)-ю строку помещают коэффициенты при М, а в (m+1)-ю — слагаемые, не содержащие М.

При переходе от одного опорного плана к другому в базис вводят вектор, соответствующий наибольшему по абсолютной величине отрицательному числу (m+2)-й строки. Искусственный вектор, исключенный из базиса в результате некоторой итерации, в дальнейшем не имеет смысла вводить ни в один из последующих базисов и, следовательно, преобразование столбцов этого вектора излишне. Может случиться так, что в результате некоторой итерации ни один из искусственных векторов из базиса не будет исключен.

Процесс нахождения решения задачи методом искусственного базиса включает следующие основные этапы:

1. Составляют расширенную задачу.

2. Находят опорный план расширенной задачи.

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

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

П р и м е р 1. Найти минимум функции Z=–2x₁+3x₂–6x₃–x₄ при условиях

Р е ш е н и е. В системе уравнений последней задачи рассмотрим векторы из коэффициентов при неизвестных:

, , ,

,.

Среди векторов А₁, А₂, А₃, А₄, А₅, А₆ только два единичных. Поэтому в левую часть третьего уравнения системы ограничений задачи добавим дополнительную неотрицательную переменную х₇ и рассмотрим расширенную задачу, состоящую в максимизации функции

Z=2x₁–3x₂+6x₃+x₄–Мх₇

при условиях

Расширенная задача имеет опорный план Х=(0, 0, 0, 24, 22, 0, 10), определяемый системой трех единичных векторов: А₄, А₅, А₇.

табл.1

					2	-3	6		1	0		0	-М
i	Базис	Сб	A0		A1	A2	A3		A4	A5		A6	A7
1	A4	1	24		2	1	-2		1	0		0	0
2	A5	0	22		1	2	4		0	1		0	0
3	A7	-М	10		1	-1	2		0	0		-1	1
4			24		0	4	-8		0	0		0	0
5			-10		-1	1	-2		0	0		1	0

Составляем таблицу 1-й итерации (табл.1), содержащую пять строк. Для заполнения 4-й и 5-й строк находим Z₀ и значения разностей Z_j–c_j :

Z₀=24–10M; Z₁–c₁=0-M; Z₂ –c₂=4+M;

Z₃–c₃= –8–2M; Z₄–c₄=0; Z₅–c₆=0+M; Z₇– c₇=0.

Значения Z₀ и Z_j–c_j состоят из двух слагаемых, одно из которых содержит М, а другое — нет. Для удобства итерационного процесса число, состоящее при М, записываем в 5-й строке, а слагаемое, которое не содержит М, — в 4-й строке.

В 5-й строке табл.1 в столбцах векторов А_j имеется два отрицательных числа. Наличие этих чисел говорит о том, что данный опорный план расширенной задачи не является оптимальным. Переходим к новому опорному плану расширенной задачи. В базис вводим вектор А₃. Чтобы определить вектор, исключаемый из базиса, находим min(22/4; 10/2)=10/2. Следовательно, вектор А₇ исключаем из базиса. Этот вектор не имеет смысла вводить ни в один из последующих базисов, поэтому в дальнейшем столбец данного вектора не заполняется (табл.2 и 3).

Составим таблицу 2-й итерации (табл.2). Она содержит только четыре строки, так как искусственный вектор из базиса исключен.

табл.2

				2	-3	6	1	0	0
i	Базис	Сб	A0	A1	A2	A3	A4	A5	A6
1	A4	1	34	3	0	0	1	0	-1
2	A5	0	2	-1	4	0	0	1	2
3	A3	6	5	1/2	-1/2	1	0	0	-1/2
4			64	4	0	0	0	0	-4

Как видно из табл.2, для исходной задачи опорным является план Х=(0, 0, 5, 34, 2). Проверим его на оптимальность. В 4-й строке в столбце вектора А₆ имеется отрицательное число (–4). Следовательно, данный опорный план не является оптимальным и может быть улучшен благодаря введению в базис вектора А₆. Из базиса исключается вектор А₅. Составляем таблицу 3-й итерации.

табл.3

				2	-3	6	1	0	0
i	Базис	Сб	A0	A1	A2	A3	A4	A5	A6
1	A4	1	35	5/2	2	0	1	1/2	0
2	A6	0	1	-1/2	2	0	0	1/2	1
3	A3	6	11/2	1/4	1/2	1	0	1/4	0
4			68	2	8	0	0	2	0

В 4-й строке табл.3 среди чисел _j нет отрицательных. Это означает, что найденный новый опорный план исходной задачи Х^*=(0, 0, 11/2, 35, 0, 1) является оптимальным. При этом плане значение линейной формы Z_max=68.