Многие практические задачи линейного
программирования не содержат в
системе ограничений единичных векторов, из координат которых можно было
бы построить единичную матрицу. Встречаются также случаи, когда система
ограничений задачи представляет собой ограничения вида неравенств
. В этих случаях для построения исходного базисного решения
приходится вводить искусственные базисные переменные, которые преобразуют в
систему канонического вида. Пусть задана следующая задача.
Минимизировать линейную форму
Z = c1x1 + c2x2 + … + c n x n
при
ограничениях
![]()

(2.5.1)
x j
0 (j=1,
2,…, n, n+1, n+2, …, n+ m ).
Если система ограничений (2.5.1) содержит
единичные векторы, их следует включить в искусственный базис. Это уменьшит
количество вводимых искусственных переменных и сократит число необходимых для
решений итераций. В этом случае будет решаться задача с неполным искусственным базисом. Если система
ограничений (2.5.1) не содержит единичных векторов, тогда имеем
задачу с полным искусственным базисом.
По отношению к исходной задаче
составляем так называемую расширенную задачу:
минимизировать
линейную форму
Z = c1x1 + c2x2 + … + cnxn + Mxn+1 + Mxn+2 +…+ M x n+ m (2.5.2)
при следующих ограничениях:
(2.5.3)
x j
0 (j = 1,
2, …, n, n+1, n+2, …, n+ m).
Система уравнений (2.5.3) получена из
системы (2.5.1) введением неотрицательных искусственных
переменных.
В соотношении(2.5.2) коэффициент М
при искусственных переменных - произвольно большое число. Соотношениями (2.5.2) и (2.5.3) определяется
новая, так называемая М-задача, которую можно решить симплексным методом. Через
конечное число итераций будет найдено ее оптимальное решение или установлено,
что задача не имеет решения.
Между М-задачей и исходной
задачей существует определенная зависимость. В случае
неразрешимости М-задачи исходная задача или неразрешима, или линейная форма ее
не ограничена. Если в оптимальном решении М-задачи все искусственные переменные
равны нулю, то вектор
= (x1, x2, …, x n) является оптимальным решением исходной
задачи. Если же хотя бы одна из искусственных переменных отлична от нуля,
исходная задача не имеет решения.
Нужно заметить, что в случае, когда
в базисе будут содержаться искусственные векторы, разности Zj - cj будут линейными функциями от М. Причем
каждая из разностей Zj - cj состоит из двух независимых друг от друга
частей, одна из которых зависит от М. Результаты вычислений сводятся в таблицу.
Здесь введены обозначения bi = x n+ i, aij = xij, i=1, 2,…, m. Предполагается
задача с полным искусственным базисом
n+1,
n+2, …,
n+ m, которому
соответствует исходный план
= (0, 0,…,0, xn+1, xn+2, …, x n+ m).
Обработка таблицы производится аналогично первой итерации симплексного процесса с той лишь разницей , что критерий оптимальности плана проверяется по (m+2)-й строке.
Просматривается (m+2)-я строка, и вектор, вводимый в базис, определяется наибольшим положительным
элементом этой строки. Если окажется, что все искусственные векторы выведены
из базиса, то дальше применяется обычный симплексный метод, при
этом искусственные векторы можно в итерацию не вводить.
Первая итерация
|
i |
Базис |
сi |
|
C1 |
C2 |
… |
C k |
… |
C n |
|
|
|
… |
|
… |
|
||||
|
1 |
|
M |
Xn+1 |
X11 |
X12 |
… |
X1k |
… |
X1n |
|
2 |
|
M |
Xn+2 |
X21 |
X22 |
… |
X2k |
… |
X2n |
|
… |
… |
… |
… |
… |
… |
… |
… |
… |
… |
|
L |
|
M |
X n+
|
Xl1 |
Xl2 |
… |
X l
k |
… |
X l
n |
|
… |
… |
… |
… |
… |
… |
… |
… |
… |
… |
|
M |
|
M |
X n+
m |
Xm1 |
Xm2 |
…. |
X m k |
… |
X m
n |
|
M+1 |
Z j-c
j |
|
0 |
-c1 |
-c2 |
… |
-
c k |
… |
-c
n |
|
m+2 |
|
|
|
|
… |
|
… |
|
Проиллюстрируем метод искусственного базиса примерами.
Пример 1. Минимизировать линейную форму
z = -x1+2x2 + x3+3x4-x5 при следующих
ограничениях:

x j
0 (j=1, 2,
3, 4, 5).
Решение.
Поскольку условие задачи
содержит единичны вектор
1, необходимо ввести два
дополнительных вектора
6 и
7. Тогда задача будет поставлена так. Минимизировать
линейную форму Z = -x1 +2x2 + x3 +3x4-
-x5+Mx6+Mx7 при следующих ограничениях:
x j
0 (j=1, 2,
3, 4, 5, 6, 7).
Исходным планом является
=(x 1,x 2,x 3, x4,x5,x6,x7)=(6,
0, 0, 0, 0, 6, 5).
Исходный
план ![]()
|
i |
Базис |
Сi |
|
-1 |
2 |
1 |
3 |
-1 |
|
|
|
|
|
|
||||
|
1 |
|
-1 |
6 |
1 |
2 |
3 |
2 |
-1 |
|
2 |
|
M |
6 |
0 |
2 |
4 |
-4 |
2 |
|
3 |
|
M |
5 |
0 |
1 |
1 |
1 |
1 |
|
4 |
Z1j-cj |
|
-6 |
0 |
-4 |
-4 |
-5 |
2 |
|
5 |
|
11 |
0 |
3 |
5 |
-3 |
3 |
Значение линейной формы, соответствующее плану
=(x 1,x 2,x 3, x4,x5,x6,x7) = (6,
0, 0, 0, 0, 6, 5), равно –6+11М.
В 5-й строке максимальным
элементом является элемент (5; 3), равный5; таким образом, вектор
3
необходимо ввести в базис.
Определяем
=![]()
= min(
,
,
)=
;
следовательно, вектор
нужно исключить из
базиса.
Получаем план
= (x 1, x 2, x 3, x4, x5, x6, x7)=(
, 0,
, 0, 0, 0,
).
План ![]()
|
I |
Базис |
Сi |
|
-1 |
2 |
1 |
3 |
-1 |
|
|
|
|
|
|
||||
|
1 |
|
-1 |
|
1 |
|
0 |
5 |
- |
|
2 |
|
1 |
|
0 |
|
1 |
-1 |
|
|
3 |
|
M |
|
0 |
|
0 |
2 |
|
|
4 |
|
|
0 |
0 |
-2 |
0 |
-9 |
4 |
|
5 |
|
|
0 |
|
0 |
2 |
|
В 5-й строке
максимальным элементом является элемент (5;4), равный 2;
следовательно, вектор
4 необходимо ввести в базис. Так
как
= min(
,
)= =
; вектор
нужно исключить
из базиса.
Получаем
новый план
= (x 1,x 2,x 3, x4,x5,x6,x7) = (0, 0,
,
,0, 0,
) со значением
линейной формы, равной
+
М.
В 5-й строке максимальное
значение, равное
, соответствует
вектору
; следовательно,
вектор
нужно ввести в базис. Так
как
=![]()
![]()
=
, вектор
следует исключить из базиса.
Преобразовав приведенный
план, получим план
=(x 1,x 2,x 3, x4,x5,x6,x7)=
=(0, 0,
,
,
, 0, 0). Значение линейной формы
при плане
равно
.
План ![]()
|
i |
Базис |
С i |
|
-1 |
2 |
1 |
3 |
-1 |
|
|
|
|
|
|
||||
|
1 |
|
3 |
|
|
|
0 |
1 |
- |
|
2 |
|
1 |
|
|
|
1 |
0 |
0 |
|
3 |
|
M |
|
- |
|
0 |
0 |
|
|
4 |
|
|
|
|
- |
0 |
0 |
- |
|
5 |
|
|
- |
|
0 |
0 |
|
План
|
i |
Базис |
С i |
|
-1 |
2 |
1 |
3 |
-1 |
|
|
|
|
|
|
||||
|
1 |
|
3 |
|
|
|
0 |
1 |
0 |
|
2 |
|
1 |
|
|
|
1 |
0 |
0 |
|
3 |
|
-1 |
|
- |
|
0 |
0 |
1 |
|
4 |
Z44-cj |
Z0= |
|
-1 |
0 |
0 |
0 |
|
Вектор
1 следует
ввести в базис, так как
(Zj - cj) = Z1 - c1 =
.
= min(![]()
![]()
, ![]()
![]()
) = ![]()
![]()
= 9; следовательно,
вектор
3 нужно исключить из базиса.
Получаем
новый план
= (x 1, x 2, x 3, x4, x5, x6, x7) = (9, 0, 0,
,
, 0, 0). Значение линейной формы при плане
равно -
.
План ![]()
|
i |
Базис |
С i |
|
-1 |
2 |
1 |
3 |
-1 |
|
|
|
|
|
|
||||
|
1 |
|
3 |
|
0 |
0 |
|
1 |
0 |
|
2 |
|
-1 |
9 |
1 |
3 |
5 |
0 |
0 |
|
3 |
|
-1 |
|
0 |
1 |
4 |
0 |
1 |
|
4 |
Z4V-cj |
|
0 |
-6 |
-9 |
0 |
0 |
|
В индексной
строке 4 все разности ZVj - cj
0, т.е. критерий оптимальности для плана
выполняется.
Получили значение
линейной формы zmin=
= -
при плане
= (x 1, x 2, x 3, x4, x5, x6, x7) = (9, 0, 0,
,
, 0, 0).