Математические методы исследования операций в экономике (стр. 14 из 37)

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

* В данном пункте используется та же система обозначений, что и в п. 1.4.1.

-Критерий оптимальности псевдоплана х в двойственном симплекс-методе заключается в том,

что х одновременно должен являться допустимым планом прямой задачи, т. е. все его

компоненты должны быть неотрицательны (х_j ≥ 0).

Обратно, если хотя бы одна из компонент псевдоплана является отрицательной, то процесс улучшения значения целевой функции может быть продолжен. Геометрическая иллюстрация данной ситуации приведена на рис. 1.13. Здесь на плоскости (для m = 2) изображена система столбцов ограничений КЗЛП, из которых {а¹, а²} образуют текущий базис. Как видно из рисунка, вектор ограничений имеет отрицательную координату по направлению, задаваемому вектором а¹. В то же время очевидны и те базисы (например, {а², а³}), в которых b будет иметь все положительные координаты. Однако это не всегда так. Пример на рис. 1.14 иллюстрирует случай отсутствия допустимых планов у прямой задачи: вектор b имеет отрицательную компоненту в текущем базисе {а¹, а²} по направлению а², а для всех остальных небазисных столбцов (а³, а⁴) данная координата является положительной, т. е. b и столбцы, являющиеся кандидатами на ввод в очередной базис, лежат в разных полуплоскостях, образуемых прямой, проходящей через вектор а¹,

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

-Таким образом, в двойственном симплекс-методе признаком отсутствия допустимых планов у

решаемой КЗЛП является неотрицательность каких-либо r-х компонент во всех столбцах а^j,

представленных в текущем базисе β (a_r,j(β) ≥ 0, j Î1:n)если b_r(β) < 0 l.*

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

С другой стороны, если b_r(β)<0 и в строке а_r(β) существуют отрицательные координаты, то псевдоплан можно улучшить выводя из базиса столбец, находящийся на r-м месте, и вводя в него некоторый вектор a^l, имеющий отрицательную r-ую координату. При наличии в векторе b(β) нескольких отрицательных компонент номер вектора, выводимого из базиса, обычно определяется строкой, содержащей наименьшую (наибольшую по модулю и отрицательную) компоненту.

Принцип выбора столбца, вводимого в базис, определяется необходимостью обеспечивать то, чтобы очередной базис определял опорную плоскость, ниже которой располагаются все небазисные векторы. Для этого требуется, чтобы оценки всех небазисных векторова_0,j(β) ( j ÎN(β)), вычисляемые по формулам

а_0,j(β) = -c_{j +} c(β)а^j(β)

(см. (1.26)), оставались положительными. Это, в свою очередь, означает, что номер вводимого столбца l должен быть определен таким образом. Чтобы

После выбора выводимого и вводимого векторов производится обычный пересчет симплекс-таблицы по формулам, аналогичным формулам (1.28)-(1.31), и процесс итеративно повторяется. В результате через конечное число шагов будет найден оптимальный план КЗЛП или установлен факт пустоты множества допустимых планов.

1.7.2. Алгоритм и табличная реализация двойственного симплекс-метода. Обобщая сказанное в предыдущем пункте, приведем в сжатом виде алгоритм двойственного симплекс-метода для решения КЗЛП.

0-этап. Нахождение исходного сопряженного (двойственно допустимого базиса). Результатом 0-этапа являются сопряженный базисβ⁽¹⁾и соответствующие ему псевдоплан x(β⁽¹⁾), матрица A(β⁽¹⁾) и вектор b(β⁽¹⁾), которые будут использованы на первой итерации. Полагаем номер текущей итерации q равным 1 и переходим к I-этапу.

I-этап. Стандартная итерация алгоритма — выполняется для очередного сопряженного базиса β^(q).

1°. Проверка оптимальности текущего псевдоплана: осуществляется просмотр значений b_i(β^(q)), iÎ1:m. Возможны два варианта:

1΄. Для всех iÎ1:m, b_i(β^(q)) ≥ 0. Тогда текущий псевдоплан x(β^(q)) одновременно является допустимым планом решаемой задачи, т. е. ее оптимальным планом. Вычислительный процесс закончен. Элементы оптимального плана х* определяются по формуле

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

1". Существует по меньшей мере один номер строки rÎ1:m, для которого b_r(β^(q))<0 . Следовательно, псевдоплан x(β^(q)) — неоптимален. Выбирается строка с номером r, такая, что

Она становится ведущей и определяет номер столбца N_r(β^(q)), который должен быть выведен из базиса. Переходим к пункту 2° алгоритма.

2°. Определение столбца, вводимого в базис. Рассматривается ведущая строка а_r(β^(q)). Возможны два варианта:

2'. Для всех jÎ1:nа_r,j(β^(q)) ≥ 0. Делается вывод об отсутствии допустимых планов у решаемой задачи (D = Ø) и завершается вычислительный процесс*.

* Очевидно, что для определения пустоты множества допустимых планов достаточно найти полностью неотрицательную строку а_i(β^(q)), соответствующую b_i(β^(q)) < 0.

2". В строке а_r(β^(q)) существует по крайней мере один элемент а_r,j(β^(q))<0. Согласно правилу (1.62) определяются l — номер столбца, вводимого в очередной базис. Переходим к пункту 3° алгоритма.

3°. Пересчет элементов матрицы А и столбца b относительно нового базиса. В соответствии с формулами (1.28)-(1.31) осуществляем расчет элементов матрицы задачи A и вектора ограничений b относительно нового базиса β^(q+1), который получается в результате вывода из базиса β^(q)столбца а^r и ввода в него столбца а^l. Полагаем номер текущей итерации q: = q+1 и переходим к первому пункту алгоритма.

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

1.7.3. Особенности применения двойственного симплекс-метода. Алгоритм двойственного симплекс-метода (как и остальные симплекс-алгоритмы) предполагает знание исходного сопряженного базиса. Очевидно, что в общем случае его нахождение является достаточно непростой задачей, сводящей на нет потенциальные преимущества двойственного алгоритма. Однако в ряде случаев исходный псевдоплан может быть определен достаточно легко.

Рассмотрим задачу минимизации:

при ограничениях

где

Приведем задачу (1.66)-(1.68) к канонической форме, введя фиктивные переменные х_n+1, х_n+2,..., х_n+m:

Задача, двойственная к (1.70)—(1.72), будет иметь вид:

Из (1.74)-(1.75) очевиден допустимый план двойственной задачи