Методика решения задачи методом искусственного базиса

В каждое i-ое ограничение вводим искусственную переменную x_n+i >0. Всего m новых искусственных переменных.

В целевую функцию F вводим m дополнительных отрицательных слагаемых вида:
-M*x_n+1 -M*x_n+2...-M*x_n+m,
где М - произвольная очень большая константа.

Получим новую задача линейного программирования вида:
F(x) = c₁х₁ +... + с_nx_n -M*x_n+1 -... -M*x_n+m -------≥ max
a_i,1x₁+... + a_i,nx_n +x_n+i = b_i, (i=1,m)
x_j >0, (j=1,n+m)
Новая система ограничений характерна тем, что искусственные переменные сразу можно взять в качестве базисных:
x_n+i = b_i - a_i,1x₁ -... - a_i,nx_n, (i=1,m)

4. Формируем начальное базисное решение новой М-задачи:
x^' = (0,... 0, b₁,... b_m)

5. Решаем М-задачу симплекс-методом

6. Анализируем решение М-задачи в соответствии со следующими

правилами:

· Если в оптимальном решении М-задачи: x^" = (x^"₁,... x^"_n, x^"_n+1,... x^"_n+m)
все искусственные переменные равны 0, то вектор x^" = (x^"₁,... x^"_n)
является оптимальным решением исходной задача линейного программирования.

· Если в оптимальном решении М-задачи хотя бы одна искусственная переменная не равна 0, то исходная задача линейного программирования не имеет решения в силу несовместимости ограничений.

· Если М-задача не имеет решения, то исходная задача линейного программирования также не имеет решения в силу неограниченности целевой функции на допустимом множестве.

Определение исходного опорного плана и исходной симплекс-таблицы, с которой начинаются все итерации.

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

.

Можно считать, что все , так как умножением соответствующего

ограничения на -1 у всегда можно сменить знак.

Возьмем очень большое число M и будем решать следующую вспомогательную задачу:

В качестве исходного опорного плана надо взять план

Коэффициенты разложения векторов . Исходная симплекс-таблица приобретает тогда вид:

Сформировать дополнительную строку, где стоят числа и :

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

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

Возможны два варианта.

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

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

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

Пример

Решить задачу линейного программирования

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

Исходная симплекс-таблица примет тогда вид: