ВУЗ:
Составители:
Рубрика:
6
2,n=3.
c
11
x
11
+c
12
x
12
+c
13
x
13
+c
21
x
21
+c
22
x
22
+c
23
x
32
− min
x
11
+ x
12
+ x
13
= a
1
x
21
+ x
22
+ x
23
= a
2
x
11
+ x
21
= b
1
x
12
+ x
22
= b
2
x
12
++x
23
= b
3
x
ij
≥ 0,i=1, 2,...,m, j =1, 2,...,n
Матрица A коэффициентов ограничений имеет вид
A =
111000
000111
100100
010010
001001
,A
ij
=
0
···
0
1
0
···
0
1
···
0
i - я позиция
m + j - я позиция
Она сильно разряжена, ее вектор условий A
ij
имеет две отличные от нуля компоненты, равные
1, одна в i - ой позиции, а другая в m + j - ой позиции. Как следует из постановки, Т.З. имеет m · n
ограничений-равенств и m · n переменных. Отметим наиболее важные свойства Т.З.
Теорема
. Для разрешимости задачи (6)-(9) необходимо и достаточно выполнения условия балан-
са
m
i=1
a
i
=
n
j=1
b
j
Данное условие означает совпадение суммарного объема производства с суммарным объемом по-
требления. Транспортные задачи, для которых это условие выполняется, называются закрытыми.
Доказательство
. Необходимость. Предполагаем, что Т.З. разрешима. Это означает совместность
ее условий. Пусть набор X
∗
=
x
∗
ij
является планом, то есть удовлетворяет условиям (7) и (8).
Просуммируем условия (7) по i, а (8) – по j. В результате получим
m
i=1
n
j=1
x
∗
ij
=
m
i=1
a
i
и
m
i=1
n
j=1
x
∗
ij
=
m
i=1
b
i
откуда непосредственно следует равенство
a
i
=
b
j
.
Достаточность. Пусть условие баланса выполняется. Построим набор X
∗
= x
ij
|,гдеx
ij
=
a
i
b
k
α
,d=
a
i
=
b
j
. Очевидно, что построенный набор является планом Т.З. Действительно,
n
j=1
x
∗
ij
=
a
i
d
n
j=1
b
j
= a
i
,i=1, 2,...,m
m
i=1
x
∗
ij
=
b
j
d
m
i=1
a
i
= b
j
,j=1, 2,...,n
x
∗
ij
≥ 0,i=1, 2,...,m, j =1, 2,...,n
Таким образом множество допустимых планом Т.З. не пусто. Легко видеть, что оно также явля-
ется ограниченным, выпуклым и замкнутым (выпуклый компакт). Линейная форма на выпуклом
компакте ограничена снизу и достигает на нем своего минимума, то есть задача разрешима. Это
свидетельствует о достаточности условия баланса.
6
2, n = 3.
c11 x11 + c12 x12 + c13 x13 + c21 x21 +c22 x22 +c23 x32 − min
x11 + x12 + x13 = a1
x21 + x22 + x23 = a2
x11 + x21 = b1
x12 + x22 = b2
x12 + +x23 = b3
xij ≥ 0, i = 1, 2, . . . , m, j = 1, 2, . . . , n
Матрица A коэффициентов ограничений имеет вид
0
· · ·
0
111000
1 i - я позиция
0 0 0 1 1 1
0
A=
1 0 0 1 0 0, Aij =
· · ·
0 1 0 0 1 0
0
001001
1 m + j - я позиция
· · ·
0
Она сильно разряжена, ее вектор условий Aij имеет две отличные от нуля компоненты, равные
1, одна в i - ой позиции, а другая в m + j - ой позиции. Как следует из постановки, Т.З. имеет m · n
ограничений-равенств и m · n переменных. Отметим наиболее важные свойства Т.З.
Теорема. Для разрешимости задачи (6)-(9) необходимо и достаточно выполнения условия балан-
са
m n
ai = bj
i=1 j=1
Данное условие означает совпадение суммарного объема производства с суммарным объемом по-
требления. Транспортные задачи, для которых это условие выполняется, называются закрытыми.
Доказательство. Необходимость. Предполагаем, что Т.З. разрешима. Это означает совместность
ее условий. Пусть набор X ∗ = x∗ij является планом, то есть удовлетворяет условиям (7) и (8).
Просуммируем условия (7) по i, а (8) – по j. В результате получим
m
n m
m
n m
x∗ij = ai и x∗ij = bi
i=1 j=1 i=1 i=1 j=1 i=1
откуда непосредственно следует равенство ai = bj .
Достаточность. Пусть условие баланса выполняется. Построим набор X ∗ = xij |, где xij =
ai bk
, d= ai = bj . Очевидно, что построенный набор является планом Т.З. Действительно,
α
n
n
ai
x∗ij = bj = ai , i = 1, 2, . . . , m
j=1
d j=1
m m
bj
x∗ij = ai = bj , j = 1, 2, . . . , n
i=1
d i=1
x∗ij ≥ 0, i = 1, 2, . . . , m, j = 1, 2, . . . , n
Таким образом множество допустимых планом Т.З. не пусто. Легко видеть, что оно также явля-
ется ограниченным, выпуклым и замкнутым (выпуклый компакт). Линейная форма на выпуклом
компакте ограничена снизу и достигает на нем своего минимума, то есть задача разрешима. Это
свидетельствует о достаточности условия баланса.
Страницы
- « первая
- ‹ предыдущая
- …
- 4
- 5
- 6
- 7
- 8
- …
- следующая ›
- последняя »
