Численные методы. Корнюшин П.Н. - 64 стр.

                                                       64


расход по перевозке 1 т груза из пункта Ai в пункт Bj составляет cij руб. Требуется составить такой
план перевозок, при котором обеспечивается полная разгрузка всех пунктов отправления, полное
удовлетворение потребностей всех пунктов назначения и при котором суммарные расходы по
перевозке были бы наименьшими.
        Заметим, что в указанной постановке решение задачи возможно лишь при условии, что
количество груза во всех пунктах отправления равно общей потребности во всех пунктах
назначения: a1+a2+…+am= b1+b2+…+bn. Будем считать, что это условие выполняется. В этой
постановке задачу называют классической транспортной задачей.
        Представим математическую модель задачи.
        Допустим, что принят такой план, при котором из пункта Ai в пункт Bj перевозится xij
тонн (i=1, 2,…, m; j=1, 2,…, n). Тогда суммарные расходы по перевозке составят:
                                   Z = c11 x11 + c12 x12 + ... + c1n x1n +
                                   + c21 x21 + c22 x22 + ... + c2 n x 2 n +
                                     + ..................................... +
                                   + cm1 x m1 + cm 2 xm 2 + ... + cmn xmn .
       Минимизируем это выражение:
                             Z = c11 x11 + c12 x12 + ... + c1n x1n +
                              + c21 x21 + c22 x22 + ... + c2 n x2 n +
                                                                                       (4)
                                 + ..................................... +
                          + cm1 x m1 + cm 2 xm 2 + ... + cmn xmn → min,
т.е. потребуем, чтобы суммарные расходы по перевозке были минимальными. Это будет целевая
функция задачи. Надо найти такой план xij (i=1, 2,…, m; j=1, 2,…, n), который минимизирует
функцию Z.
        Запишем теперь ограничения. Их здесь будет две группы. В одной выразим требование,
состоящее в том, что все пункты отправления полностью разгружаются, что даст уравнения:
                                 x11 + x12 + ... + x1n = a1 ;
                                x 21 + x22 + ... + x 2 n = a 2 ;
                                                                                 (5)
                                     ..........................
                                xm1 + xm 2 + ... + x mn = am .
       Далее, выразим требование, состоящее в том, что потребности во всех пунктах назначения
полностью удовлетворяются; это даст уравнения
                                  x11 + x21 + ... + xm1 = b1 ;
                                  x12 + x22 + ... + xm 2 = b2 ;
                                                                           (6)
                                      ..........................
                                  x1n + x2 n + ... + xmn = bn .
       Наконец, следует записать, что все перевозки неотрицательны:
                                x11 ≥ 0, x12 ≥ 0,..., x1n ≥ 0;
                               x21 ≥ 0, x22 ≥ 0,..., x 2 n ≥ 0;
                                                                                 (7)
                                  .................................
                               xm1 ≥ 0, xm 2 ≥ 0,..., x mn ≥ 0.
       Таким образом, соотношения (4) – (7) составляют математическую модель транспортной
задачи. Она отличается от моделей предыдущих задач, во-первых, тем, что для параметров
управления, составляющих план, введены двойные индексы. Но это несущественно; можно было и
здесь пользоваться одиночными индексами, но это было бы менее наглядно. Существенно то, что
ограничения выражаются здесь равенствами (5) – (6), а не неравенствами, как в предыдущих
задачах. Кроме того, эти равенства имеют специфическую структуру. Благодаря этому для
транспортной задачи линейного программирования удается создать и специфические методы
решения. Следует, однако, иметь в виду, что общее строение математической модели