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

                                                     65


транспортной задачи остается прежним: 1) имеется целевая функция (линейная относительно
параметров управления), которую нужно оптимизировать подбором соответствующего плана; 2)
имеются ограничения, выражаемые линейными зависимостями от параметров управления (от
переменных, составляющих план); 3) от параметров управления требуется, чтобы они были
неотрицательными.
       Замечание. Транспортную задачу можно ставить на минимум времени. Она приобретает
тогда несколько иную структуру, но сводится к задаче линейного программирования.

                        3. Расстановочная (распределительная) задача

        Пусть имеется m типов автомашин, которые должны осуществлять грузоперевозки на n
линиях. Пусть объем перевозок на этих линиях составляет соответственно Q1, Q2,…, Qn тонно-
километров. Известно, что если автомобиль i-го типа использовать на j-й линии, то его провозная
способность составит Pij тонно-километров за весь планируемый период (если автомобиль какого-
то типа нельзя использовать на некоторой линии, то его провозная способность на этой линии
полагается равной нулю).
        Можно поставить различные оптимизационные задачи при расстановке автомобилей.
Поставим, например, задачу о такой расстановке, при которой достигается минимум
эксплуатационных расходов при выполнении заданных объемов перевозок на линиях. В качестве
параметров управления примем доли эксплуатационного периода, отведенные для работы
имеющегося парка автомобилей на тех или иных линиях. Пусть xij –доля эксплуатационного
периода, отведенная для работы i-го типа автомобиля на j-й линии (i=1, 2,…, m; j=1, 2,…, n). Эти
mn дробей xij (они безразмерные) и составляют план расстановки (далее будем полагать во всех
обозначениях с двумя индексами: на первом месте – номер типа автомобиля, на втором – номер
линии).
        Если эксплуатация i-го типа автомобиля на j-й линии в течение всего периода требует
расхода Rij руб., то в течение отведенного по плану времени он составит Rijxij руб. Значит,
эксплуатационные расходы при намеченном плане составят сумму
                           Z = R11 x11 + R12 x12 + ... + R1n x1n +
                           + R21 x21 + R22 x22 + ... + R2 n x2 n +
                                                                               (8)
                             + ..................................... +
                           + Rm1 x m1 + Rm 2 x m 2 + ... + Rmn xmn .
       Эта линейная функция Z от mn переменных xIJ и есть целевая функция задачи.
       Запишем математические соотношения, выражающие ограничения. Их будет две группы.
В первую группу запишем требования, состоящие в том, что сумма долей планируемого периода,
намеченных для работы каждого типа автомобиля на разных линиях, не может быть больше
единицы:
                                 x11 + x12 + ... + x1n ≤ 1;
                                x21 + x22 + ... + x2 n ≤ 1;
                                                                         (9)
                                   ..........................
                                xm1 + xm 2 + ... + xmn ≤ 1.
       Затем следует математически выразить требование, предъявленное заданными объемами
перевозок Q1, Q2,…, Qn на каждой линии. Получим:
                            P11 x11 + P21 x21 + ... + Pm1 xm1 = Q1 ;
                           P12 x12 + P22 x22 + ... + Pm 2 xm 2 = Q2 ;
                                                                               (10)
                                      ..........................
                           P1n x1n + P2 n x2 n + ... + Pmn xmn = Qn .
       Наконец, запишем, что все величины xij неотрицательны: