Метод искусственного базиса

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

Наличие единичной матрицы является не­обходимым условием при решении задач симплексным методом.

Если же ограничения задачи заданы в виде неравенств вида ≥ или уравнений

aij·xj ≥ b i и (или) aij·xj = b i

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

Для соблюдения равенств вводятся искусственные переменные у i равные 0

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

Такой базис называется искусствен­ным, а метод решения называется методом искусственного базиса.

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

Преобразование ограничений, в виде уравнений, рас­смотрим на примере:

7x1 + 2х2 + Зх3 = 25,

6х1 + 3х2 + 5х3 = 29,

4х2 + 2х3 = 31.

В систему равенств вводим искусственные переменные y1, y2, y3 с коэффициентами, равными 1, позволяющими образовать искусственный базис решения:

7х1 + 2х2 + Зх3 + l y 1 + О у 2 + О y 3 = 25,

6х1 + Эх; + 5хз + Oy1 + 1y2 + Оуз = 29,

O x 1 + 4 х 2 + 2 х 3 + O y 1 + Qy2 + 1 y 3 = 31.

Целевая функция имеет вид:

при решении задачи на максимум -

F(X) = c 1 x 1+ c2x2 + с 3 х 3+ (-M)y1+(-М)у2+(-М)у3 -> max;

при решении задачи на минимум —

F(X) = c 1 x 1 + c2x2 + с 3 х 3 + My1 + Му2 + Му3 -> min;

За использование искусственных переменных, вводимых в це­левую функцию, накладывается так называемый «штраф» величи­ной М, очень большое положительное число, которое обычно не задается (М -> ¥).

Преобразования ограничений в виде неравенств ≥ рассмо­трим на примере:

9 х 1 + 5 х 2 + З х 3 ≥ 30,

4 х 2 + х 3 ≥ 12,

11 x 1 + 10 х 3 ≥ 41.

Для получения уравнений вводим дополнительные пе­ременные х 4, х 5, х 6.

9 х 1 + 5 х 2 + З х 3 - х ₄ = 30,

4 х 2 + х 3 - х ₅ = 12,

11 x 1 + 10 х 3 - х ₆ = 41.

Поскольку на главной диагонали единичной матрицы не могут нахо-диться (-1), то в систему вводим искусственные переменные y 1, y 2, y 3 с коэффициентами (+1), которые образуют искусственный ба­зис решения

9 х 1 +5 х 2 +З х 3 —1 х ₄ —0 х ₅ —0 х ₆ +1y1 + 0y2 +0y3 = 30,

4 х 2 + х 3 — 0 х ₄ —1 х ₅ —0 х ₆ +0y1 + 1y2 +0y3 = 12,

11 x 1 + 10 х 3 — 0 х ₄ — 0 х ₅ — 1 х ₆ + 0y1 + 0y2 +1y3 = 41.

Целевая функция имеет вид:

при решении задачи на максимум -

F(X) = c 1 x 1+ c 2 х 2+ с 3 х 3+0 х 4+0 х 5+0 х 6+ (-M)y1+(-М)у2+(-М)у3 -> max;

при решении задачи на минимум -

F(X) = c 1 x 1+ c 2 х 2+ с 3 х 3+0 х 4+0 х 5+0 х 6+ My1+Му2+Му3 -> min;

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

Например, ограничения заданы в виде системы:

20 х 1 + 7 х 2 + 2 х 3 ≤ 43,

3 x 1 + 9 х 2 + 10 х 3 = 33,

6 x 1 + 12 х 2 + 7 х 3 ≥ 23.

Сначала образуем систему уравнений, для чего вводим в первое неравенство дополнительную переменную х 4, а в третье неравенст­во - дополнительную переменную х 5:

20 x 1 + 7 х 2 + 2 х 3 + 1 х 4 = 43,

З х 1 + 9 х 2 + 10 х 3 = 33,

6 х 1 + 12 х 2 + 7 х 3 - 1 х 5 = 23.

Для образования единичной матрицы вводим недостающие элементы: во второе уравнение искусственную переменную у1 а в третье — y 2:

20 x 1 + 7 х 2 + 2 х 3 — 0 x 5 + 1 х 4 + 0 y 1 + 0 y 2 = 43,

З х 1 + 9 х 2 + 10 х 3 — 0 x 5 + 0 х 4 + 1 y 1 + 0 y 2 = 33,

6 х 1 + 12 х 2 + 7 х 3 — 1 х 5 — 0 х 4 + 0 y 1 + 1 y 2 = 23.

Целевая функция имеет вид:

при решении задачи на максимум -

F(X) = c 1 x 1 + c 2 х 2 + с 3 х 3 + 0 х 4 + 0 х 5 + My1 + Му2 -> max;

при решении задачи на минимум -

F(X) = c 1 x 1 + c 2 х 2 + с 3 х 3 + 0 х 4 + 0 х 5 + My1 + Му2 -> min.

Поставленные таким образом задачи можно решать симплекс­ным методом.