Методы условной оптимизации: Рекомендации к выполнению лабораторных и практических работ. Шипилов С.А. - 25 стр.

                 2.2. Транспортная задача линейного программирования

       Линейные транспортные задачи составляют особый класс задач ЛП. Об-
щая постановка транспортной задачи состоит в определении оптимального
плана перевозок некоторого однородного груза из m пунктов отправления (ПО)
A1, A2, …,Am в n пунктов назначения (ПН) B1, B2, …,Bm. При этом в качестве
критерия оптимальности обычно берется либо минимальная стоимость перево-
зок всего груза, либо минимальное время его доставки. Рассмотрим транспорт-
ную задачу, в качестве критерия оптимальности которой взята минимальная
стоимость перевозок всего груза. Обозначим через cij тарифы перевозки едини-
цы груза из i – того ПО в j – тый ПН, через ai – запасы груза в i – том ПО, через
bj – потребности в грузе в j – том ПН, а через xij – количество единиц груза, пе-
ревозимого из i – того ПО в j – тый ПН. Предполагается, что транспортные рас-
ходы пропорциональны перевозимому количеству продукции, т.е. перевозка k
единиц продукции вызывает расходы cij k.
       Тогда математическая постановка задачи состоит в определении мини-
мального значения целевой функции
                                                      m     n
                                           f (x) = ∑∑ cij xij                                                 (10)
                                                      i =1 j =1
при условиях
                                           m
                                          ∑ xij = b j ,           j = 1, n ,                                  (11)
                                           i =1
                                             n
                                          ∑ xij = ai ,            i = 1, m ,                                  (12)
                                           j =1

                             xij ≥ 0 , i = 1, m , j = 1, n .            (13)
      Поскольку переменные xij удовлетворяют системам линейных уравнений
(11) и(12) и условию неотрицательности (13), обеспечиваются доставка необхо-
димого количества груза в каждый из ПН, вывоз имеющегося груза из всех ПО,
а также исключаются обратные перевозки.
                                                                                                     m
      Очевидно, общее количество груза у поставщиков равно                                           ∑ ai , а общая
                                                                                                     i =1
                                                  n
потребность в грузе в ПН равна                 ∑ b j единиц. Если общая потребность в грузе в
                                               j =1
                                                                               n          m
пунктах назначения равна запасу груза в ПО, т.е.                               ∑ b = ∑ a , то модель та-
                                                                               j =1
                                                                                      j
                                                                                          i =1
                                                                                                 i


кой транспортной задачи называется закрытого типа. Если модель открытого
     ⎛   n             m          ⎞
типа ⎜
     ⎜   ∑      bj ≠   ∑      ai ⎟⎟ , то ее всегда можно привести к закрытому типу введени-
     ⎝   j =1          i =1       ⎠
ем фиктивного ПН или фиктивного ПО:

                                                                                                                25