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

UptoLike

ВУЗ: 

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

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

Рубрика: 

5
Эта задача сводится к уже рассмотренной простой нумерацией множества пар индексов (i, j) одним
индексом k =1, 2,...,m· n.
Более сложной из известных двухиндексных Т.З. является следующая. Пусть в пунктах
A
1
,A
2
,...,A
m
производится (или хранится) некоторый однородный продукт, причем объем про-
изводства в пункте A
i
составляет a
i
единиц. Указанный продукт потребляется в пунктах
B
1
,B
2
,...,B
n
, причем объем потребления в пункте B
i
равен b
i
единиц. Допустим, что транспорт-
ные издержки, приходящиеся на единицу продукта при перевозке его из i-ого пункта производства
в j-ый пункт потребления составляют c
ij
денежный единиц. Требуется найти такой план перево-
зок (распределение продукта по потребителям), при котором потребности всех потребителей будут
удовлетворены, весь продукт будет вывезен и при этом суммарные транспортные затраты будут
минимальны.
Пусть x
ij
— количество продукта, транспортируемое из пункта A
i
в пункт B
j
, математическая
модель такой задачи имеет вид
m
i=1
n
j=1
c
ij
x
ij
− min (6)
при условиях
n
j=1
x
ij
= a
i
,i=1, 2,...,m (7)
m
i=1
x
ij
= b
j
,j=1, 2,...,n (8)
x
ij
≥ 0 (9)
Равенства (7) гарантируют полный вывоз продукта из всех пунктов производства, равенства (8)
означают полное удовлетворение потребителей, условия (9) естественны. Т.З. в такой постановке
определяется заданием вектора объемов производства a =(a
1
,a
2
,...,a
m
)
T
, вектора объема потреб-
ления b =(b
1
,b
2
,...,b
n
)
T
) и матрицы транспортных издержек
c =
c
11
c
12
... c
1n
c
21
c
22
... c
2n
.
.
.
.
.
.
.
.
.
c
m1
c
m2
... c
mn
План Т.З. также удобно записать в виде матрицы
X =
x
11
x
12
... x
1n
x
21
x
22
... x
2n
.
.
.
.
.
.
.
.
.
x
m1
x
m2
... x
mn
План X иногда называют планом перевозок, а компоненты x
ij
— перевозками. Для задания и
решения Т.З. удобно пользоваться таблицей
b
1
b
2
... b
n
a
1
c
11
,x
11
c
12
,x
12
... c
1n
,x
1n
a
2
c
21
,x
21
c
22
,x
22
... c
2n
,x
2n
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
a
m
c
m1
,x
m1
c
m2
,x
m2
... c
mn
,x
mn
Для того, чтобы понять специфичность условий Т.З., запишем ее в развернутом виде при m =
                                                                                                      5

Эта задача сводится к уже рассмотренной простой нумерацией множества пар индексов (i, j) одним
индексом k = 1, 2, . . . , m · n.
    Более сложной из известных двухиндексных Т.З. является следующая. Пусть в пунктах
A1 , A2 , . . . , Am производится (или хранится) некоторый однородный продукт, причем объем про-
изводства в пункте Ai составляет ai единиц. Указанный продукт потребляется в пунктах
B1 , B2 , . . . , Bn , причем объем потребления в пункте Bi равен bi единиц. Допустим, что транспорт-
ные издержки, приходящиеся на единицу продукта при перевозке его из i-ого пункта производства
в j-ый пункт потребления составляют cij денежный единиц. Требуется найти такой план перево-
зок (распределение продукта по потребителям), при котором потребности всех потребителей будут
удовлетворены, весь продукт будет вывезен и при этом суммарные транспортные затраты будут
минимальны.
    Пусть xij — количество продукта, транспортируемое из пункта Ai в пункт Bj , математическая
модель такой задачи имеет вид
                                             m  n
                                                    cij xij − min                                 (6)
                                             i=1 j=1

при условиях
                                     n
                                     
                                            xij = ai ,     i = 1, 2, . . . , m                       (7)
                                     j=1

                                     m
                                     
                                            xij = bj ,     j = 1, 2, . . . , n                       (8)
                                      i=1

                                                      xij ≥ 0                                        (9)

Равенства (7) гарантируют полный вывоз продукта из всех пунктов производства, равенства (8)
означают полное удовлетворение потребителей, условия (9) естественны. Т.З. в такой постановке
определяется заданием вектора объемов производства a = (a1 , a2 , . . . , am )T , вектора объема потреб-
ления b = (b1 , b2 , . . . , bn )T ) и матрицы транспортных издержек
                                                                                 
                                               c11       c12   ...         c1n
                                              c21       c22   ...         c2n    
                                                                                 
                                    c=         ..        ..                ..    
                                                .         .                 .    
                                              cm1      cm2     ...        cmn

   План Т.З. также удобно записать в виде матрицы
                                                                                 
                                               x11       x12    ...         x1n
                                              x21       x22    ...         x2n   
                                                                                 
                                   X=          ..        ..                 ..   
                                                .         .                  .   
                                              xm1        xm2    ...        xmn

   План X иногда называют планом перевозок, а компоненты xij — перевозками. Для задания и
решения Т.З. удобно пользоваться таблицей

                                        b1                b2          ...            bn
                             a1     c11 , x11         c12 , x12       ...         c1n , x1n
                             a2     c21 , x21         c22 , x22       ...         c2n , x2n
                              ..         ..                ..         .. .. ..         ..
                               .          .                 .          ...              .
                             am    cm1 , xm1         cm2 , xm2        ...        cmn , xmn

Для того, чтобы понять специфичность условий Т.З., запишем ее в развернутом виде при m =

Страницы