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

1.

Метод искусственного базиса
Цель метода искусственного базиса – построение
начального
БДП (либо установить отсутствие БДП).
b(i 0 , i 1, m
ЗЛП задана в канонической форме,
Этого всегда можно добиться, умножив уравнения на 1):
С ( х) c1 x1 c 2 x 2 ... c n x n max
a11 x1 a12 x 2 ... a1n x n b1
a x a x ... a x b
21 1
22 2
2n n
2
.............................................
a m1 x1 a m 2 x 2 ... a mn x n bm
x1 , x 2 , ..., x n 0
(1)

2.

Вспомогательная задача к ЗЛП (1):
b1
a11 x1 a12 x 2 ... a1n x n x n 1
a x a x ... a x x
b2
21 1
22 2
2n n
n 2
.....................................................
a m1 x1 a m 2 x 2 ... a mn x n
x n m bm
x1 , x 2 ,..., x n , x n 1 , x n 2 ,..., x n m 0
~ ~
С ( х ) x x ... x
max
n 1
n 2
(2)
n m
Вектор составлен из естественных переменных ЗЛП
(1.) и искусственных переменных, введенных в ЗЛП (2):
~
х ( x1 , x2 ,..., xn , x n 1 , x n 2 ,..., x n m )
естественн ые
переменные
искусствен ные
переменные

3.

Искусственные
переменные
не
несут
никакого
экономического смысла. Они необходимы только для
поиска начального БДП.
Единичные векторы An+1, An+2, …, An+m
образуют
искусственный базис системы ограничений ЗЛП (2).
Они представляют собой единичную матрицу размера
m m.
В ЗЛП (2) мы имеем начальный БДП, в котором
первые n координат равны нулю.
Пусть множество допустимых планов задачи (1) - D1,
а множество допустимых планов задачи (2) - D2.

4.

Теорема. (О существовании плана ЗЛП).
*
~
х ( x1* ,..., xn* , xn* 1 ,..., xn* m )
Пусть
оптимальный план ЗЛП (2), тогда:
~ ~*
1. Если С ( х ) 0
x * ( x1* , x 2* ,..., x n*,) то план
*
*
*
*
x
(
x
,
x
,...,
x
является планом задачи (1),1 т.е.2
n)
2. Если
D1.
~ ~*
С ( х ) 0 , то ЗЛП (1) не имеет допустимых
планов, т.е. D1 есть пустое множество (D1 = ).
Замечание.
Вспомогательная
имеет оптимальный план.
задача
(2)
всегда

5.

П р и м е р: Рассмотрим ЗЛП:
C ( х) 2 x1 x2 min
x1 x2 14
x1 x2 8
x1 , x2 0
Приведем данную ЗЛП к каноническому виду:
C1 ( x) 2 x1 x2 max
x1 x2 x3 14
x1 x2 x4 8
x1 , x2 , x3 , x4 0

6.

Единичного базиса нет, поэтому построим
вспомогательную задачу, предварительно введя
две искусственные переменные х5 0 и х6 0.
~ ~
C ( х ) x5 x6 max
x1 x2 x3 х5 14
x1 x2 x4 х6 8
x1 , x2 , x3 , x4 0

7.

-2
1
0
0
х
х
0
0
0
0
-1
-1
с
Базис
A0=b
А1
А2
А3
А4
А5
А6
-1
-1
А5
А6
14
8
1
1
1
-1
-1
0
0
-1
1
0
0
1
/ j
-22
-2
0
1
1
0
0
А5
А1
6
8
0
1
2
-1
-1
0
1
-1
1
0
-1
1
/ j
-6
0
-2
1
-1
0
2
А2
А1
3
11
0
1
1
0
-0,5
-0,5
0,5
-0,5
0,5
0,5
-0,5
0,5
/ j
0
0
0
0
0
1
1
А2
А1
3
11
0
1
1
0
-0,5
-0,5
0,5
-0,5
/ j
-19
0
0
0,5
1,5
0
1
-1
0
0
0
1
-2

8.

Решив
данную
вспомогательную
задачу
симплекс-методом, мы найдем ее оптимальный
план и значение целевой функции на этом плане:
~ ~*
*
~
х (11; 3; 0; 0; 0; 0)
С(х ) 0
Оптимальный план вспомогательной задачи есть
начальный БДП основной задачи. После чего
необходимо
приступить
к
ее
решению
также
симплекс-методом. Оптимальный план основной задачи:
х* = (11; 3; 0; 0); С1(х*) = – 19;
С(х*) = 19

9.

Признак неограниченности целевой функции
ЗЛП в канонической форме:
С ( х) (с, х) max
Aх b
х 0
(1)
Пусть х0 = (х10, х20,…, хn0) - БДП задачи (1)
Ax0
= b эквивалентно
n
0
A
x
j j b
j 1
- носитель плана, следовательно или в матричной форме записи:
A x b
0
0
A
x
i i b
i
(2)
,

10.

В уравнении (2) хσ0 представляет часть
исходного вектора х0 , из которого удалены
нулевые (свободные) компоненты. Для плана х0
можно построить симплекс-таблицу, причем
предположим, что среди двойственных оценок
имеются отрицательные , т.е. план не
оптимальный.

11.

Теорема. О неразрешимости ЗЛП.
Если для некоторого БДП х0 существует k и все
элементы k-го вектор-столбца меньше или равны нулю,
т.е.
aik 0
, i , то ЗЛП неразрешима. Другими
словами, в данной ситуации целевая функция не
ограничена на допустимом множестве, т. е. С(х) .

12.

Пример:
С ( х) x1 x2 max
x1 x2 x3 1
x1 2 x2 x4 0
x1 2 x2 x5 3
x j 0, j 1,5
Единичный базис состоит из векторов А3, А4, А5.
Вырожденный БДП х0 = (0; 0; 1; 0; 3).

13.

Решение ЗЛП
с
0
0
Базис
A3
1
1
0
0
0
A1
A3
1
0
A4
0
1
A5
0
0
A0=b
1
0
-1
1
A2
1
-2
-1
-1*
0
2
-1
-1
0
0
1
0
0
1
1
0
0
0
A4
A5
0
С(х)/ j
A3
3
0
1
1
0
A1
A5
0
3
1
0
-2
0
0
0
1
1
0
1
С(х)/ j
0
0
-3
0
1
0

14.

На второй итерации 2 = -3 0. Вводим в базис
вектор А2, однако координаты этого вектора . На
основании только что доказанной теоремы можно
сделать заключение, что данная ЗЛП неразрешима,
она не имеет оптимальных планов, а ее целевая
функция
планов.
С(х) → +∞ на множестве допустимых