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

1.

Метод искусственного базиса
Цель метода искусственного базиса – построение
начального
БДП (либо установить отсутствие БДП).
b 0 , i 1, m
ЗЛП задана в канонической форме, (i
Этого всегда можно добиться, умножив уравнения на 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 ,..., x n , x n 1 , x n 2 ,..., xn 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