Транспортная задача линейного программирования. Бартеньев А.П - 4 стр.

UptoLike

Рубрика: 

4
Обозначим через х
ij
объем перевозок продукта от i-го по-
ставщика к j-ому потребителю. Тогда условия задачи удобно бу-
дет записать в виде следующей таблицы (табл. 1).
Таблица 1 Опорный вариант плана
Пункты потребления
Наличие
грузов
Пункты отправления
В
1
В
2
В
n
А
1
c
11
x
11
c
12
x
12
c
1n
x
1n
a
1
А
2
c
21
x
21
c
22
x
22
c
2n
x
2n
a
2
A
m
c
m1
x
m1
c
m2
x
m2
c
mn
x
mn
a
m
Потребность в грузах b
1
b
2
b
n
В качестве примера рассмотрим следующую задачу.
В хозяйстве имеются три навозохранилища, в которых хра-
нятся 1000т,1500 т и 920т навоза. Этот навоз нужно вывести на 5
полей: на первое 450т, на второе 640т, на третье 680т, на
четвертое 450т, на пятое 1200т. Расстояние от навозохрани-
лищ до полей задано матрицей
А=
36115
42264
13523
Для построения опорного плана транспортной задачи суще-
ствуют различные методы. Рассмотрим наиболее простой из них
метод северо-западного угла. Этот метод получил свое название
потому, что распределение поставок начинается с левой верхней
клетки, что соответствует северо-западу на географической кар-
те.
Начинаем заполнение таблицы с клетки К
11
, соответствую-
щей первому поставщику и первому потребителю. Удовлетворя-
ем потребности первого поля за счет запасов навоза в первом на-
возохранилище. В первом навозохранилище имеется 1000т наво-
за, а на первое поле его требуется вывезти 450т, то есть, а
1
> b
1
.
записываем в клетку К
11
450. исключаем первый столбец из рас-
смотрения. Из оставшейся части таблицы вновь выберем северо-
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
             Обозначим через хij объем перевозок продукта от i-го по-
         ставщика к j-ому потребителю. Тогда условия задачи удобно бу-
         дет записать в виде следующей таблицы (табл. 1).
         Таблица 1 – Опорный вариант плана


                                               Пункты потребления            Наличие
             Пункты отправления
                                                                              грузов
                                         В1         В2        …        Вn
                                         c11        c12                c1n
                      А1                                      …                a1
                                         x11        x12                x1n
                                         c21        c22                c2n
                      А2                                      …                a2
                                         x21        x22                x2n
                      …                  …          …         …        …       …
                                         cm1        cm2                cmn
                      Am                                      …                am
                                         xm1        xm2                xmn
             Потребность в грузах        b1         b2        …        bn

             В качестве примера рассмотрим следующую задачу.
             В хозяйстве имеются три навозохранилища, в которых хра-
         нятся 1000т,1500 т и 920т навоза. Этот навоз нужно вывести на 5
         полей: на первое – 450т, на второе – 640т, на третье – 680т, на
         четвертое – 450т, на пятое – 1200т. Расстояние от навозохрани-
         лищ до полей задано матрицей
                                             3 2 5 3 1
                                                       
                                         А=  4 6 2 2 4 
                                             5 1 1 6 3
                                                       
             Для построения опорного плана транспортной задачи суще-
         ствуют различные методы. Рассмотрим наиболее простой из них
         – метод северо-западного угла. Этот метод получил свое название
         потому, что распределение поставок начинается с левой верхней
         клетки, что соответствует северо-западу на географической кар-
         те.
             Начинаем заполнение таблицы с клетки К11, соответствую-
         щей первому поставщику и первому потребителю. Удовлетворя-
         ем потребности первого поля за счет запасов навоза в первом на-
         возохранилище. В первом навозохранилище имеется 1000т наво-
         за, а на первое поле его требуется вывезти 450т, то есть, а1> b1.
         записываем в клетку К11 450. исключаем первый столбец из рас-
         смотрения. Из оставшейся части таблицы вновь выберем северо-

         4

PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com