ВУЗ:
Составители:
Рубрика:
14
m
i=1
λ
ij
x
ij
= b
j
,j=1, 2,...,n (15)
x
ij
≥ 0,i=1, 2,...,m, j =1, 2,...,n. (16)
Такую задачу принято называть распределительной или обобщенной транспортной. Она часто воз-
никает в практике планирования транспортных перевозок, где требуется найти план закрепления
самолетов (судов, автомобилей) за направлением так, чтобы задание по объему перевозок на каж-
дом направлении было выполнено, а суммарные транспортные расходы были минимальны.
В других вариантах Р.З. условия (14)–(15) имеют смешанный вид. Р.З. имеет m · n переменных
и m + n ограничений. Вектор-столбец условий A
ij
, отвечающий переменной x
ij
, также содержит не
более двух отличных от нуля компонент: i –йи(m + n) – й. Р.З. удобно записать в матричном виде
b
1
b
2
... b
n
a
1
c
11
λ
11
c
12
λ
12
... c
1n
λ
1n
x
11
x
12
... x
1n
a
2
c
21
λ
21
c
22
λ
22
... c
2n
λ
2n
x
21
x
22
... x
2n
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
a
m
c
m1
λ
m1
c
m2
λ
m2
... c
mn
λ
mn
x
m1
x
m2
... x
mn
Если коэффициенты λ
ij
= α
i
β
j
, i =(1,m), j =(1,n), то Р.З. легко сводится к Т.З. заменой перемен-
ных (Показать!). Ранг матрицы условий больше распределительной задачи в общем случае (если
ранг матрицы A больше 1) равен m + n. Это значит, что базис распределительной задачи состоит
из m+n линейно-независимых векторов, а невырожденный опорный план имеет m+n положитель-
ных компонент. Отсюда решение двойственных соотношений для определения потенциалов строк и
столбцов, отвечающих рассматриваемому опорному плану, несколько усложняется.
Задача, двойственная к (13)–(16), имеет вид
n
j=1
b
j
v
j
−
m
i=1
a
i
u
i
λ
ij
v
j
− u
i
≤ c
ij
,i=(1,m),j=(1,n)
u
i
≥ 0,i=(1,m)
Как и для Т.З., опорный план X распределительной задачи является оптимальным, если отвечаю-
щая ему система потенциалов v
j
, u
i
удовлетворяет условиям
c
ij
− λ
ij
+ u
i
≥ 0,i=(1,m),j=(1,n)
u
i
≥ 0
В случае нарушения хотя бы одного условия опорный план должен быть улучшен. Отыскание
опорного исходного плана основано на тех же соображениях, что и метод минимального элемента
для транспортной задачи.
Начиная с произвольной позиции (i
1
,j
1
) искомой матрицы плана X,положим
x
i
1
j
1
=
min{a
i
,b
j
1
/λ
i
1
j
1
}, если λi
1
j
1
> 0
a
i
, если λi
1
j
1
≤ 0
Если x
i
1
j
1
= a
i
1
, то полагаем x
i
1
j
=0для j = j
1
, если x
i
1
j
1
=
b
j
1
λ
i
1
j
1
,тоx
i
1
j
1
=0для i = i
1
.Вслучае
равенства a
i
1
=
b
j
1
λ
i
1
j
1
, которое имеет место в случае невырожденности, нулями дополняется либо
i
1
– я строка, либо j
1
– й столбец матрицы плана.
Правые части ограничений (14)–(15) преобразуются:
a
i
=
a
i
, если i = i
1
a
i
− x
i
1
j
1
, если i = i
1
14
m
λij xij = bj , j = 1, 2, . . . , n (15)
i=1
xij ≥ 0, i = 1, 2, . . . , m, j = 1, 2, . . . , n. (16)
Такую задачу принято называть распределительной или обобщенной транспортной. Она часто воз-
никает в практике планирования транспортных перевозок, где требуется найти план закрепления
самолетов (судов, автомобилей) за направлением так, чтобы задание по объему перевозок на каж-
дом направлении было выполнено, а суммарные транспортные расходы были минимальны.
В других вариантах Р.З. условия (14)–(15) имеют смешанный вид. Р.З. имеет m · n переменных
и m + n ограничений. Вектор-столбец условий Aij , отвечающий переменной xij , также содержит не
более двух отличных от нуля компонент: i – й и (m + n) – й. Р.З. удобно записать в матричном виде
b1 b2 ... bn
a1 c11 λ11 c12 λ12 ... c1n λ1n
x11 x12 ... x1n
a2 c21 λ21 c22 λ22 ... c2n λ2n
x21 x22 ... x2n
.. .. .. .. ..
. . . . .
am cm1 λm1 cm2 λm2 ... cmn λmn
xm1 xm2 ... xmn
Если коэффициенты λij = αi βj , i = (1, m), j = (1, n), то Р.З. легко сводится к Т.З. заменой перемен-
ных (Показать!). Ранг матрицы условий больше распределительной задачи в общем случае (если
ранг матрицы A больше 1) равен m + n. Это значит, что базис распределительной задачи состоит
из m + n линейно-независимых векторов, а невырожденный опорный план имеет m + n положитель-
ных компонент. Отсюда решение двойственных соотношений для определения потенциалов строк и
столбцов, отвечающих рассматриваемому опорному плану, несколько усложняется.
Задача, двойственная к (13)–(16), имеет вид
n
m
bj vj − ai ui
j=1 i=1
λij vj − ui ≤ cij , i = (1, m), j = (1, n)
ui ≥ 0, i = (1, m)
Как и для Т.З., опорный план X распределительной задачи является оптимальным, если отвечаю-
щая ему система потенциалов vj , ui удовлетворяет условиям
cij − λij + ui ≥ 0, i = (1, m), j = (1, n)
ui ≥ 0
В случае нарушения хотя бы одного условия опорный план должен быть улучшен. Отыскание
опорного исходного плана основано на тех же соображениях, что и метод минимального элемента
для транспортной задачи.
Начиная с произвольной позиции (i1 , j1 ) искомой матрицы плана X, положим
min{ai , bj1 /λi1 j1 }, если λi1 j1 > 0
xi1 j1 =
ai , если λi1 j1 ≤ 0
bj 1
Если xi1 j1 = ai1 , то полагаем xi1 j = 0 для j = j1 , если xi1 j1 = λi1 j1 , то xi1 j1 = 0 для i = i1 . В случае
bj 1
равенства ai1 = , которое имеет место в случае невырожденности, нулями дополняется либо
λi1 j1
i1 – я строка, либо j1 – й столбец матрицы плана.
Правые части ограничений (14)–(15) преобразуются:
ai , если i = i1
ai =
ai − xi1 j1 , если i = i1
