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

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

К левым частям ограничения (4) добавляют неотрицательные искусственные переменные w_i.

В ЦФ искусственные переменные вводятся с коэффициентом +М в случае нахождения min и с коэффициентом -М в случае нахождения max.

Полученная задача всегда имеет предпочтительный вид. Такая задача называется М-задачей.

Предположим, в системе ограничений (2) все ограничения имеют непредпочтительный вид. Составим М-задачу при указанном положении:

M – большое положительное число.

ЗАМ: если имеются предпочтительные ограничения, то добавлять в него w_i не надо.

Теорема: если в оптимальном решении X ^* = (x ₁, …, x_n, w ₁, …, w_m) М-задачи все искусственные переменные w_i = 0, то решение X = (x ₁, …, x_n) является оптимальным решением для исходной задачи (2).

Рассмотрим задачу (2) с ограничениями типа (4):

(5)

Предположим, система (5) не имеет не предпочтительный вид. Введем искусственные переменные w_{n +1}, …, w_n+m так, чтобы (5) принял предпочтительный вид. (Если какое-нибудь равенство k в (5) имеет предпочтительный вид, то искусственную переменную w_n+k либо не вводим, либо считаем w_n+k = 0).

Составим следующую задачу:

(6)

Теорема: пусть задача (5) имеет допустимое решение. Решение X ^* = (x ₁, …, x_n, w_{n +1}, …, w_n+m) задачи (6) является оптимальным Û w_n+i = 0, i = 1.. m.

Теорема гарантирует равенство 0 всех искусственных переменных в оптимальном решении X ^* Þ X = (x ₁, …, x_n) является допустимым решением задачи (5), но, вообще говоря, оно не является оптимальным решением задачи, как это было в случае I метода искусственного базиса.

Однако на практике II метод имеет следующее применение. Предположим, оптимальное решение X ^* задачи (6) найдено СМ. Тогда ненулевым компонентам X ^* соответствуют линейно независимое векторы A_j. Так как ненулевыми компонентами по теореме могут быть только исходные переменные x_j, а не искусственные w_n+i, то решению X ^* соответствуют линейно независимые векторы из системы A_j. Если оказалось, что оптимальное решение X ^* не вырождено, то число линейно независимых векторов составляет базис. Этот базис и соответствующие ему переменные x_j могут быть приняты в качестве первоначального допустимого базисного решения задачи (5).

Таким образом, алгоритм метода:

1. задача (5) преобразуется в (6)

2. задача (6) решается СМ.

3. если решение X ^* не вырождено, то в последней таблице СМ вычеркиваются столбцы, соответствующие искусственным переменным и пересчитывается D _j. Полученная таблица будет являться исходной для решения задачи (5)

Дата добавления: 2015-01-03