5.2. Метод искусственного базиса
Метод искусственного базиса применяется для решения задач ЛП в случае, когда задача не имеет начального опорного решения с базисом из единичных векторов.
Пример
5.2. Минимизировать функцию
при ограничениях
Если
ввести дополнительные неотрицательные
переменные
,
,
,
,
то система ограничений примет вид:
(
5.2.1 )
Из
( 5.2.1 ) следует, что очевидного базисного
допустимого решения нет. Один из путей
преодоления этих трудностей состоит в
использовании того же симплекс-метода
для порождения базисного допустимого
решения. Изменим первые два ограничения
(два других не создают проблем) введением
в левую часть искусственных переменных
и
(
,
):
(
5.2.2 )
Тогда базисное решение (допустимый план) будет иметь вид:
,
а
,
,
,
.
Затем
симплекс-метод используется для
минимизации функции
.
Функция
называется искусственной целевой
функцией.
Этап
I задачи состоит в минимизации функции
.
Конечно, сначала надо выразить
через небазисные переменные, а именно
:
.
На этом этапе с функцией
проводятся те же действия, что и с
ограничениями. В результате получим,
что
при
.
При этом ограничения ( 5.2.2 ) равносильны
исходным ограничениям ( 5.2.1 ). Решение,
минимизирующее функцию
,
может быть использовано как начальное
базисное решение для функции
на II этапе. После того, как функция
,
игнорируем её и искусственные переменные.
Преобразования по методу Жордана-Гаусса
на этапе I приведены ниже (здесь мы
приводим полные симплекс-таблицы) (табл.
5.1)
Таблица 5.1
Базисные переменные |
Значения |
|
|
|
|
|
|
|
|
|
10 |
1 |
0 |
–1 |
0 |
0 |
0 |
1 |
0 |
|
5 |
0 |
1 |
0 |
–1 |
0 |
0 |
0 |
1 |
|
20 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
|
20 |
–1 |
4 |
0 |
0 |
0 |
1 |
0 |
0 |
|
0 |
3 |
4 |
0 |
0 |
0 |
0 |
0 |
0 |
|
15 |
1 |
1 |
–1 |
–1 |
0 |
0 |
0 |
0 |
|
|
|
|
|
|
|
|
|
|
|
10 |
1 |
0 |
–1 |
0 |
0 |
0 |
1 |
0 |
|
5 |
0 |
1 |
0 |
–1 |
0 |
0 |
0 |
1 |
|
10 |
0 |
1 |
1 |
0 |
1 |
0 |
–1 |
0 |
|
30 |
0 |
4 |
–1 |
0 |
0 |
1 |
1 |
0 |
|
–30 |
0 |
4 |
3 |
0 |
0 |
0 |
–3 |
0 |
|
5 |
0 |
1 |
0 |
–1 |
0 |
0 |
–1 |
0 |
|
|
|
|
|
|
|
|
|
|
|
10 |
1 |
0 |
–1 |
0 |
0 |
0 |
1 |
0 |
|
5 |
0 |
1 |
0 |
–1 |
0 |
0 |
0 |
1 |
|
5 |
0 |
0 |
1 |
1 |
1 |
0 |
–1 |
–1 |
|
10 |
0 |
0 |
–1 |
0 |
0 |
1 |
1 |
–4 |
|
–50 |
0 |
0 |
3 |
4 |
0 |
0 |
–3 |
–4 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
–1 |
–1 |
Теперь
можно минимизировать функцию
.
Начальное опорное решение имеет вид
.Решая эту задачу, получаем
,
,
,
,
.
Так
как
и
,
то ограничения, в которые эти переменные
входят, превращаются в строгие неравенства.