ВУЗ:
Составители:
Рубрика:
Линейное программирование
40
ab
i
i
m
j
j
n
==
∑∑
=
11
.
Такая задача называется закрытой транспортной задачей. Математиче-
ская постановка этой задачи имеет следующий вид
min
11
→
∑∑
==
m
i
n
j
ijij
xc (1)
при ограничениях
xaim
ij
j
n
i
=
∑
==
1
1, (2)
xbjn
ij
i
m
j
=
∑
==
1
1, (3)
ximjn
ij
≥
=
=
011,,,, (4)
где
x
ij
- количество продукта , перевозимое из пункта
A
i
в пункт
B
j
.
Без ограничения общности всегда можно считать, что
aim
i
>
=
01,,
и
njb
j
,1,0 =>
.
Задача (1)-(4) является задачей линейного программирования, записан-
ной в канонической форме. Она имеет
mn
переменных и
m
n
+
ограничений.
Любая допустимая точка задачи может быть записана в виде матрицы
()
Xx
xx
xx
ij
n
mmn
==
111
1
...
.........
...
.
Как известно, не любая задача линейного программирования имеет ре-
шение. Условия разрешимости транспортной задачи формулируются в сле-
дующей теореме.
Теорема 1. Для разрешимости транспортной задачи необходимо и
достаточно выполнение следующего условия баланса
ab
i
i
m
j
j
n
==
∑∑
=
11
.
Можно показать, что число независимых уравнений системы (2)-(3)
равно
m
n
+
−
1
. Отсюда, в частности , следует, что любая допустимая базис-
ная точка транспортной задачи содержит не более
m
n
+
−
1
положительных
координат.
Рассмотрим два метода нахождения исходной базисной точки для
транспортной задачи : метод "северо-западного угла " и метод минимального
элемента .
Линейное программирование m n ∑ ai = ∑ b j . i =1 j =1 Такая задача называется закрытой транспортной задачей. Математиче- ская постановка этой задачи имеет следующий вид m n ∑ ∑ cij xij → min (1) i =1 j =1 при ограничениях n ∑ x ij =ai i =1, m (2) j =1 m ∑ x ij =bj j =1, n (3) i =1 x ij ≥0 i =1, m, j =1, n , (4) где x ij - количество продукта, перевозимое из пункта A i в пункт B j . Без ограничения общности всегда можно считать, что ai >0, i =1, m и b j >0, j =1, n . Задача (1)-(4) является задачей линейного программирования, записан- ной в канонической форме. Она имеет mn переменных и m +n ограничений. Любая допустимая точка задачи может быть записана в виде матрицы � x 11 ... x 1n � � � ( ) X = x ij =� ... ... ... � . � x � � m1 ... x mn � Как известно, не любая задача линейного программирования имеет ре- шение. Условия разрешимости транспортной задачи формулируются в сле- дующей теореме. Теорема 1. Для разрешимости транспортной задачи необходимо и достаточно выполнение следующего условия баланса m n ∑ ai =∑ bj . i =1 j =1 Можно показать, что число независимых уравнений системы (2)-(3) равно m +n −1. Отсюда, в частности, следует, что любая допустимая базис- ная точка транспортной задачи содержит не более m +n −1 положительных координат. Рассмотрим два метода нахождения исходной базисной точки для транспортной задачи: метод "северо-западного угла" и метод минимального элемента. 40
Страницы
- « первая
- ‹ предыдущая
- …
- 36
- 37
- 38
- 39
- 40
- …
- следующая ›
- последняя »