Линейное программирование. Элементы теории, алгоритмы и примеры. Азарнова Т.В - 38 стр.

UptoLike

Рубрика: 

Линейное программирование
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