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

                 n               m                          m                 n                             n +1              m
      • Если    ∑b < ∑ a
                j =1
                         j
                                 i =1
                                         i   , то bn +1 =   ∑ a − ∑b
                                                            i =1
                                                                    i
                                                                              j =1
                                                                                      j     , тогда         ∑b = ∑a ,
                                                                                                            j =1
                                                                                                                   j
                                                                                                                              i =1
                                                                                                                                     i


         причем ci ,n +1 = 0 ∀i .
                     n             m                               n                 m               n             m +1
      • Если     ∑b > ∑ a ,
                 j =1
                             j
                                  i =1
                                             i   то   a m +1 =     ∑b − ∑ a
                                                                   j =1
                                                                          j
                                                                                     i =1
                                                                                             i   ,   ∑b = ∑a
                                                                                                     j =1
                                                                                                             j
                                                                                                                       i =1
                                                                                                                               i     и

         cm+1, j = 0 ∀j .

      Впрочем, стоимость перевозок для фиктивного ПН, т.е. ci ,n+1 , может не
всегда быть равной нулю, а приравниваться стоимости складирования излиш-
ков продукции, так же как и для фиктивного ПО - cm+1, j может составить стои-
мость штрафов за недопоставку продукции.
      Транспортная задача представляет собой задачу линейного программиро-
вания и, естественно, ее можно решить с использованием метода последова-
тельного улучшения плана или метода последовательного уточнения оценок. В
этом случае основная трудность бывает связана с числом переменных задачи
(m×n) и числом ограничений (m+n). Поэтому специальные алгоритмы оказы-
ваются более эффективными. К таким алгоритмам относятся метод потен-
циалов и метод дифференциальных рент.
      Алгоритм метода потенциалов, его называют еще модифицированным
распределительным алгоритмом, начинает работу с некоторого опорного плана
транспортной задачи (допустимого плана перевозок). Для построения опорного
плана обычно используется один из трех методов: метод северо-западного уг-
ла, метод минимального элемента или метод аппроксимации Фогеля.
      Подробно эти методы освещаются в специальной литературе [1, 9]. Мы
же будем рассматривать решение транспортной задачи с использованием таб-
личного процессора Exel.

      Пример
      Четыре предприятия данного экономического района для производства
продукции используют три вида сырья. Потребности в сырье каждого из
предприятий соответственно равны 120, 50, 90 и 110 ед. Сырье сосредоточе-
но в трех местах его получения, а запасы соответственно равны 160, 140 и
170 ед. На каждое из предприятий сырье может завозиться из любого пункта
его получения. Тарифы перевозок являются известными величинами и задают-
ся матрицей издержек:
                                 ⎛7 8 1 2⎞
                                 ⎜          ⎟
                             С = ⎜4 5 9 8⎟ .
                                 ⎜9 2 3 6⎟
                                 ⎝          ⎠
     Составить такой план перевозок, при котором общая их стоимость яв-
ляется минимальной.

26