Задачи линейного программирования транспортного типа. Горячев Л.В. - 8 стр.

UptoLike

ВУЗ: 

ДВФУ | Владивосток

Составители: 

Рубрика: 

8
Непосредственно из условий двойственности задачи следует, что ее допустимый план определяется с
точностью до const. Действительно, если W (v
1
,v
2
,...,v
n
, −u
1
, −u
2
,...,−u
m
)
T
— допустимый план,
то W
(v
1
+ h, v
2
+ h,...,v
n
+ h, −(u
1
+ h), −(u
2
+ h),...,−(u
m
+ h))
T
также допустим, в чем можно
убедиться подстановкой W
в условия.
Численный анализ Т.З. существенно опирается на следующий признак оптимальности
Теорема
. Для оптимальности опорного плана X = x
ij
транспортной задачи необходимо и
достаточно существование чисел v
1
,v
2
,...,v
n
, −u
1
, −u
2
,...,−u
m
таких, что v
j
− u
i
≤ c
ij
,i=
1, 2,...,m, j =1, 2,...,n и v
j
− u
i
= c
ij
, при x
ij
0.
Доказательство
. Необходимость. Если X
0
=
x
0
ij
— оптимальный опорный план, то ему отвеча-
ет система оценок столбцов матрицы A, которая удовлетворяет условиям, совпадающим с условиями
теоремы.
Достаточность. Пусть существует такая система чисел, что условия теоремы справедливы. Тогда
m
i=1
n
j=1
c
ij
x
0
ij
=
m
i=1
n
j=1
(v
j
− u
i
)x
0
ij
=
n
j=1
b
j
v
j
−
m
i=1
a
i
u
i
Равенство целевых функций сопряженных задач на допустимых планах свидетельствует об оп-
тимальности этих планов. Очевидно, что оптимальному опорному плану отвечает система потенци-
алов v
j
− u
i
(оптимальный план двойственной задачи), такая, что неравенства ≤ выполняются для
всех i и j, а базисным компонентам отвечают равенства. Мы уже отмечали, что базис невырожден-
ного опорного плана состоит из m + n − 1 вектора, таково же число базисных компонент. Значит
матрица невырожденного опорного плана X
0
=
x
0
ij
mn
содержит m + n − 1 положительных эле-
ментов. Опорный план обладает наглядным геометрическим свойством, которое легко обнаружить
на матрице плана.
Определение
. Компоненты плана образуют замкнутый маршрут (цикл), если их можно соеди-
нить горизонтальными и вертикальными отрезками так, что они образуют замкнутую цепочку.
Приведем примеры планов, содержащих цикл:
X
1
=
45 10
12
00
03
00
01
30
X
2
=
2
30
1
02
0 8 0
0
5 6
X
3
=
1 009
2
500
0 628
В матрице X
1
цикл образуют компоненты x
12
,x
42
,x
43
,x
13
, в матрице X
2
цикл образован компонен-
тами x
11
,x
21
,x
23
,x
43
,x
42
,x
12
, в матрице X
3
в цикле участвуют перевозки x
11
,x
21
,x
22
,x
32
,x
34
,x
14
.
Легко видеть, что векторы-условия A
ij
, отвечающие компонентам цикла, линейно-зависимы. На-
пример, для цикла X
2
вектора A
11
,A
12
,A
42
,A
43
,A
23
,A
21
линейно-зависимы. Действительно,
1
0
0
0
1
0
0
−
1
0
0
0
0
1
0
+
0
0
0
1
0
1
0
−
0
0
0
1
0
0
1
+
0
1
0
0
0
0
1
−
0
1
0
0
1
0
0
=0
Следствие
. Из компонент опорного плана нельзя составить цикл.
Метод потенциалов Т.З.
Метод потенциалов состоит из конечной последовательности однотипных итераций. Каждая
итерация состоит из двух этапов. На первом этапе опорный план, полученный на предыдущей
итерации, проверяется на оптимальность. Если он оказывается решением задачи, то процесс закан-
чивается. Если это не так, то переходим ко второму этапу. На этом этапе строится новый опорный
план перевозок, , который либо уменьшает транспортные издержки (невырожденный случай), либо
8

Непосредственно из условий двойственности задачи следует, что ее допустимый план определяется с
точностью до const. Действительно, если W (v1 , v2 , . . . , vn , −u1 , −u2 , . . . , −um )T — допустимый план,
то W  (v1 + h, v2 + h, . . . , vn + h, −(u1 + h), −(u2 + h), . . . , −(um + h))T также допустим, в чем можно
убедиться подстановкой W  в условия.
    Численный анализ Т.З. существенно опирается на следующий признак оптимальности
    Теорема. Для оптимальности опорного плана X = xij  транспортной задачи необходимо и
достаточно существование чисел v1 , v2 , . . . , vn , −u1 , −u2 , . . . , −um таких, что vj − ui ≤ cij , i =
1, 2, . . . , m, j = 1, 2, . . . , n и vj − ui = cij , при xij 0.
    Доказательство. Необходимость. Если X 0 = x0ij — оптимальный опорный план, то ему отвеча-
ет система оценок столбцов матрицы A, которая удовлетворяет условиям, совпадающим с условиями
теоремы.
    Достаточность. Пусть существует такая система чисел, что условия теоремы справедливы. Тогда
                           m 
                            n                    m 
                                                   n                          n
                                                                                              m
                                                                                               
                                     cij x0ij =             (vj − ui )x0ij =         bj vj −         ai ui
                           i=1 j=1                i=1 j=1                      j=1             i=1

   Равенство целевых функций сопряженных задач на допустимых планах свидетельствует об оп-
тимальности этих планов. Очевидно, что оптимальному опорному плану отвечает система потенци-
алов vj − ui (оптимальный план двойственной задачи), такая, что неравенства ≤ выполняются для
всех i и j, а базисным компонентам отвечают равенства. Мы уже отмечали, что базис невырожден-
ного опорного плана состоит из m + n − 1 вектора, таково же число базисных компонент. Значит
матрица невырожденного опорного плана X 0 = x0ij mn содержит m + n − 1 положительных эле-
ментов. Опорный план обладает наглядным геометрическим свойством, которое легко обнаружить
на матрице плана.
   Определение. Компоненты плана образуют замкнутый маршрут (цикл), если их можно соеди-
нить горизонтальными и вертикальными отрезками так, что они образуют замкнутую цепочку.
Приведем примеры планов, содержащих цикл:

                                  4   5   1   0                  2   3   0
                                                                                          1     0 0 9
                                  1   2   0   0                  1   0   2
                         X1 =                        X2 =                      X3 =       2     5 0 0
                                  0   3   0   0                  0   8   0
                                                                                          0     6 2 8
                                  0   1   3   0                  0   5   6

В матрице X1 цикл образуют компоненты x12 , x42 , x43 , x13 , в матрице X2 цикл образован компонен-
тами x11 , x21 , x23 , x43 , x42 , x12 , в матрице X3 в цикле участвуют перевозки x11 , x21 , x22 , x32 , x34 , x14 .
Легко видеть, что векторы-условия Aij , отвечающие компонентам цикла, линейно-зависимы. На-
пример, для цикла X2 вектора A11 , A12 , A42 , A43 , A23 , A21 линейно-зависимы. Действительно,
                                            
                                    1        1      0       0      0      0
                                 0 0 0 0 1 1
                                            
                                 0 0 0 0 0 0
                                            
                                 0 − 0 + 1 − 1 + 0 − 0 = 0
                                            
                                 1 0 0 0 0 1
                                            
                                 0 1 1 0 0 0
                                    0        0      0       1      1      0

    Следствие. Из компонент опорного плана нельзя составить цикл.

                                              Метод потенциалов Т.З.

   Метод потенциалов состоит из конечной последовательности однотипных итераций. Каждая
итерация состоит из двух этапов. На первом этапе опорный план, полученный на предыдущей
итерации, проверяется на оптимальность. Если он оказывается решением задачи, то процесс закан-
чивается. Если это не так, то переходим ко второму этапу. На этом этапе строится новый опорный
план перевозок, , который либо уменьшает транспортные издержки (невырожденный случай), либо

Страницы