Математические методы исследования в экономике

      а) расчетную транспортную сеть

      б) переменные Х_rs для каждой дуги

      в) уравнение (2.3) для каждой вершины

      г) целевую функцию (2.4) с коэффициентами С_rs, равными расстояниям или показателям стоимости перевозок по дугам сети.

      Описанная модель сетевой задачи не учитывает  пропускной способности участков сети - для этого вводится дополнительное ограничение:

      Х_rs < d_rs  (2.5)

      где d_rs – пропускная способность участка сети r-s в направлении от r к s.

      С учетом (2.5) получаем сетевую транспортную задачу с ограничением пропускной способности в простейшем виде (для перевозки одного груза).

      Сетевая и матричная модели в большинстве  случаев взаимозаменяемы.

      Но  есть и особые ситуации, так, например, при большом числе потребителей и поставщиков преимущество имеет сетевая постановка задачи; эта же форма применяется при оптимизации перевозок с учетом ограничений пропускной способности участков транспортной сети.

      Оптимизацию планирования перевозок взаимозаменяемых грузов удобнее производить в матричной форме и т.д.

      Критерии  оптимальности:

      Выбор критерия зависит от: характера проблемы, наличной информации и требуемой  точности нахождения оптимума.

      Примерами локального критерия оптимальности  транспортной задачи могут служить:

      а) критерий минимума суммарного пробега (пригоден только для решения закрытых транспортных задач в пределах одного вида транспорта).

      б) при оптимизации перевозок в  пределах года обычным стоимостным  критерием является сумма зависящих приведенных расходов:

      С = Э_зав + Э_пер + Е_n (К_пс + C_гр)

      где Э_зав – зависящие от движения эксплуатационные расходы;

      К_пс – капитальные вложения в подвижной состав;

      С_гр – стоимость грузов, находящихся в процессе перевозки;

        Э_пер – издержки по перевалкам.

      в) При составлении оптимальных  схем перевозок на перспективу возможно усиление пропускной способности линий  в зависимости от размещения на них  оптимальных грузопотоков. Поэтому  в критерии оптимальности учитывается:

      К_пост. – затраты на необходимое развитие пропускной способности по постоянным устройствам;

      Э_нез – независящие эксплуатационные расходы.

      С =  Э_зав + Э_нез + Е_п + (К_пс + К_пост. + С_гр)

      г) в некоторых случаях при решение  открытых транспортных задач допускается  использование в качестве критерия - суммы издержек производства и тарифных плат за перевозки.

      д) в отдельных задачах по оптимизации  срочных перевозок в качестве критерия выступает время: тонно-часы (вагоны-часы) пребывания груза в  процессе перевозки или общее  время завершения определенной перевозочной операции.

 

      2.2. Решение матричных  транспортных задач  методом условно-оптимальных  планов

      Из  многих методов решения матричных  задач наиболее распространенными  является

• метод потенциалов (Канторович П.А. и Говорин М.В.)
• метод условно- оптимальных планов (Лурье А.Л.)

Метод условно- оптимальны планов относится  к методам сокращения невязок:

• в начальном варианте допускается нарушение основных ограничений транспортной задачи;
• Σ Х_ij = B_i (j=1,2, … n);
• Σ X_ij = A_i (i= 1,2, … m);
• допущенные невязки и разбалансировки устраняются путем внесения ряда поправок.

      Основные  этапы метода условно- оптимальных  планов рассмотрим на примере некоторой  транспортной задачи (таблицы 2.1.), требующей  увязать ресурсы трёх поставщиков  А1, А2, АЗ,А4 (строки таблицы 2.1.) с потребностями четырёх потребителей В1÷В6 (столбцы таблицы 2.1). В правых верхних углах клеток матрицы 2.1 показаны, стоимости перевозки С_ij единицы груза от поставщика А_i и потребителя В_j — оптимальное решение будет получено за четыре этапа решения, которые называются приближениями задачи и также показаны в таблице 2.1

      Каждый  этап решения состоит из следующих  девяти шагов (пунктов):

      Порядок вычислений

      1. Построение начального  варианта.

      В каждом столбце матрицы (2.1) находится  клетка с минимальной стоимостью:

      С_kj = min С_ij

      В эту клетку заносится поставка, равная полной потребности столбца:

      X_ki = B_ij

      При наличии нескольких клеток с минимальной  стоимостью поставка B_i распределяется между ними произвольно.

      В таблице 2.1 для первого, второго и  третьего столбца минимальные стоимости обнаружены в первой строке (390, 220, 130), для четвертого, пятого и шестого столбца – во второй строке (160, 430, 420).

 

      2. Определение сумм  поставок в невязках

      Находятся суммы поставок по каждой строке ΣХ_ij и разности между ресурсами поставщиков и предусмотренными поставками

      R_i = A_i – Σ X_ij

      Разности  R называются невязками или разбалансами Так, в таблице, в приближение № 1 разбалансы показаны в последнем столбце и равны для четырёх поставщиков соответственно -183, -67, +100, +150.

      Приближение № 2 (-83, -67, -0, +150)

      Приближение № 3 (-56, -67, -0, +123)

      Приближение № 4 ( -56, -25, -0, +81)

      Приближение № 5 ( 0, -25, -0, +25)

      Приближение № 6 ( 0, 0, 0, 0)

 

      3. Проверка наличия  отрицательных разбалансов.

      Отсутствие. отрицательных разбапансов говорит об оптимальности найденного варианта решения (прибл. № 6). в приближение № 1 таблицы 2.1. первая строка. имеет отрицательный раэбаланс  -183, поэтому поиск оптимального решения будет продолжен.

 

      4. Классификация строк.

      Строка  i считается абсолютно недостаточной, если её разбаланс отрицательный и абсолютно избыточной если разбаланс положительный. При R=0 строки классифицируются на относительно избыточные и относительно недостаточные. В приближение № 1 (таблицу 2.1.) 1-я, 2-я строки абсолютно недостаточные, 3-я, 4-я строки абсолютно избыточные.

      Приближение № 2 - 1-я, 2-я  строки абсолютно недостаточные, 3-я, 4-я строки абсолютно избыточные.

      Приближение № 3 - 1-я, 2-я и 3-я  строки абсолютно  недостаточные,  4-я строка абсолютно  избыточна.

      Приближение № 4 - 1-я, 2-я и 3-я  строки абсолютно недостаточные,  4-я строка абсолютно избыточна.

      Приближение № 5 - 1-я строка абсолютно достаточна; 2-я и 3-я  строки абсолютно недостаточные,  4-я строка абсолютно избыточна.

      Приложение  № 6 – все строки достаточны.

 

      5. Преобразование матрицы  стоимостей.

      - включает в себя следующие  действия:

      а) В каждом столбце, имеющем поставку в недостаточной строке, находится  минимальная из стоимостей на пересечении  с избыточными строками:

      С_rj = min С_ij

      I є U , где U – множество абсолютно и относительно избыточных строк.

      Например: в приближение № 1 в первом столбце  наименьшая стоимость по избыточным строкам:

      С_r1 = min (970, 1090)=970.

      Во  втором столбце наименьшая стоимость  по избыточным строкам С _r2 (1120,1260) = 1120, в третьем С_r3, (1090, 1190)=1090. В четвертом, пятом, шестом столбцах С_rj min по избыточным строкам не определяется, т.к. эти столбцы не имеют поставки в единственной недостаточной первой строке.

      Приближение № 2  в 1-ом столбце наименьшая стоимость  по избыточным строкам:

      С_r1 = min (1090)=1090.

      Во  втором столбце наименьшая стоимость  по избыточным строкам С _r2 (1260) = 1260, в третьем С_r3, (1190)=1190.

      Приближение № 3  в 3-ем столбце наименьшая стоимость  по избыточным строкам:

      С_r3 = min (940)=940.

      В четвертом столбце наименьшая стоимость по избыточным строкам С _r4 (1210) = 1210, в пятом С_r5, (1160)=1160.

      Приближение № 4  во 2-ом столбце наименьшая стоимость  по избыточным строкам:

      С_r2 = min (1260)=1260.

      В третьем столбце наименьшая стоимость  по избыточным строкам С _r3 (1190) = 1190.

      Приближение № 5  во 4-ом столбце наименьшая стоимость  по избыточным строкам:

      С_r4 = min (1760, 940)=940.

      В пятом столбце наименьшая стоимость  по избыточным строкам С _r5 (1480, 1210) = 1210.

 

      б) в каждом столбце, имеющем поставку в недостаточной строке, определяется разность между минимальной стоимостью по избыточным строкам и минимальной стоимостью по столбцу в целом.

      Δ_j = C_rj – C_kj

      Значение  Δ_j фиксируется во вспомогательной строке (строка в таблице 2.1.)

      Например, в приближение № 1 в первом столбце Δ_j = 970-390 = 580,  во втором стелбце Δ_j = 1120-220 = 900, в третьем столбце Δ_j = 1090-130 =960. В четвертом, пятом, шестом столбцах значение Δ не определяется т.к. поставка находится в избыточной строке.

      Приложение  № 2 в первом столбце Δ_j = 1090-970 = 120,  во втором столбце Δ_j = 1260-800 = 460, в третьем столбце Δ_j = 1190-710 = 480. В четвертом, пятом, шестом столбцах значение Δ не определяется.

      Приложение  № 3 в четвертом столбце Δ_j = 940-860 = 80,  в пятом столбце Δ_j = 1210-1130 = 80, в шестом столбце Δ_j = 1160-1120 = 40. В первом, втором, третьем столбцах значение Δ не определяется.

      Приложение  № 4 во втором столбце Δ_j = 1260-960 = 300, в третьем столбце Δ_j = 1190-870 = 320. В первом, четвертом, пятом, шестом столбцах значение Δ не определяется.

      Приложение № 5 в четвертом столбце Δ_j = 1760-1200 = 560,  в пятом столбце Δ_j = 1480-1470 = 10. В первом, втором, третьем, шестом столбцах значение Δ не определяется.

      Приложение  № 6 – значение Δ  не определяется.

      в) находится наименьшее значение из всех Δ_j

      Δ = min Δ_j, которое прибавляется по всем стоимостям во всех недостаточных строках.

      Так, для приближения № 1 получаем:

      Δ = min (580, 900, 960) = 580

      Все стоимости в недостаточной первой строке увеличиваю на Δ=580, в остальных  не меняются. Значения стоимостей на этом этапе решения показываются дробью в правом верхнем углу клеток в недостаточных строках, причём в числителе дроби – первоначальное значение стоимости, в знаменателе – обновлённое в соответствии с шагом 5 алгоритма решения задачи.

      Для приближения № 2 - Δ = min (120, 460, 480) = 120