Критерии оптимальности. Методы оптимизации перевозок грузов Какие проблемы решает

Выбор критерия зависит от: характера проблемы, наличной информации и требуемой точности нахождения оптимума.
Примерами локального критерия оптимальности транспортной задачи могут служить:
а) критерий минимума суммарного пробега (пригоден только для решения закрытых транспортных задач в пределах одного вида транспорта);
б) при оптимизации перевозок в пределах года обычным стоимостным критерием является сумма зависящих приведенных расходов:
C = Эзав + Эпер + Еп (К пс + C гр),
где Эзав - зависящие от движения эксплуатационные расходы,
Кпс - капитальные вложения в подвижной состав,
Сгр - стоимость грузов, находящихся в процессе перевозки,
Эпер - издержки по перевалкам;
в) при составлении оптимальных схем перевозок на перспективу возможно усиление пропускной способности линий в зависимости от размещения на них оптимальных грузопотоков. Поэтому в критерии оптимальности учитывается:
Кпост - затраты на необходимое развитие пропускной способности по по-стоянным устройствам,
Энез - независящие эксплуатационные расходы.
Тогда
C = Эзав + Энез + Еп(Кпс + Кпост + Cгр) ;
477
г) в некоторых случаях при решении открытых транспортных задач допускается использование в качестве критерия суммы издержек производства и та-рифных плат за перевозки;
д) в отдельных задачах по оптимизации срочных перевозок в качестве критерия выступает время: тонно-часы (вагоны-часы) пребывания груза в процессе перевозки или общее время завершения определенной перевозочной операции.
Из многих методов решения матричных задач наиболее распространенными являются: метод потенциалов (Л. А. Канторович и М.В. Говурин) и метод условно-оптимальных планов (А. Л. Лурье).
Метод условно-оптимальных планов относится к методам сокращения невязок:
в начальном варианте допускается нарушение основных ограничений транспортной задачи
X Xij = Bj (j = 1, 2, ... л); X Xij = Ai (i = 1, 2, ... m);
i j
допущенные невязки и разбалансировки устраняются путем внесения ряда поправок.
Основные этапы метода условно-оптимальных планов можно рассмотреть на примере некоторой транспортной задачи (см. табл. 17.1), требующей увязать ресурсы трех поставщиков А1, А2, A3 (строки табл. 17.1) с потребностями че-тырех потребителей В1^В4 (столбцы табл. 17.1). В правых верхних углах клеток матрицы показаны стоимости перевозки Су единицы груза от поставщика и потребителя Вj - оптимальное решение будет получено за четыре этапа реше-ния, которые называют приближениями задачи и также показаны в табл. 17.1.
Пример решения матричной транспортной задачи методом условно-оптимальных планов Номер прибли-жения Поставщик и Потребитель и его потребность, Bj Сумма по-ставок Разба-лансы Л,- его ресурс, ЛІ B 7 B2 9 B3 9 B4 5 ^xij J J A1 10 10/12 7 12/14 9 9/11 15/17 5 21 -11 1 A2 10 1 14
Г 20 8 9 50 9 +1 A3 10 12 15 20 25 0 +10 Aj 12-10=2 15-12=3 - 25-15=10 A1 10 12/13 4/15 9 11/12 17/18 5 14 -4 2 A2 10 14 1 20 8 9 50 9 +1 A3 10 12 7 15 20 25 7 +3 Aj - 1 - 8 A1 10 і ^ 13/15 5/17 6 2/14 8/20 5 11 -1 3 A2 10 14 1 20 8 9 50 9 +1 A3 10 2/14 7 15/17
3 20/22 25/27 10 -0 Aj 14-12=2 20-15=5 - 50-18=32 Aj 10 15 17 5 14 20 5 10 +0 4 A2 10 14 1 20 8 9 50 10 +0 A3 10 14
6 17 4 22 27 10 +0
Каждый этап решения состоит из 9-ти шагов (пунктов). 1. Построение начального варианта.
В столбцах 3-6 матрицы (табл. 17.1) находится клетка с минимальной стоимостью:
Сkj = min Cjj.
В эту клетку заносится поставка, равная полной потребности столбца:
Xkj = BJ.
При наличии нескольких клеток с минимальной стоимостью поставка Bj распределяется между ними произвольно.
В табл. 17.1 для первого, второго и четвертого столбцов минимальные стоимости обнаружены в первой строке (10, 12, 15), для третьего столбца - во второй (8).
Определение сумм поставок и невязок.
Находятся суммы поставок по каждой строке Z Xij и разности между ре-
J
сурсами поставщиков и предусмотренными поставками:
RI = 4 -z XIJ.
j
Разности Rj называются невязками или разбалансами. Так, в таблице, в приближении № 1 разбалансы показаны в последнем столбце и равны для трех поставщиков соответственно -11, +1, +10.
Проверка наличия отрицательных разбалансов.
Отсутствие отрицательных разбалансов говорит об оптимальности найденного варианта решения. В приближении № 1 табл. 17.1 первая строка имеет отрицательный разбаланс -11, поэтому поиск оптимального решения будет продолжен.
Классификация строк.
Строка i считается абсолютно недостаточной, если ее разбаланс отрицательный, и абсолютно избыточной, если разбаланс - положительный. При R = 0 строки классифицируются на относительно избыточные и относительно недостаточные согласно примечанию, которое будет указано ниже. В приближении № 1 (табл. 17.1) 1-я строка абсолютно недостаточная, 2-я и 3-я строки - абсолютно избыточные.
Преобразование матрицы стоимостей. Включает в себя следующие действия:
а) в каждом столбце, имеющем поставку в недостаточной строке, находится минимальная из стоимостей на пересечении с избыточными строками:
С rj = min Cj;
I gU ,
где U - множество абсолютно и относительно избыточных строк.
Например, в приближении № 1 в 1-м столбце наименьшая стоимость по избыточным строкам:
С r1 = min (14, 12) = 12.
Во 2-м столбце наименьшая стоимость по избыточным строкам Cr2 = min (20, 15), в 4-м - Cr4 = min (50, 25) = 25. В 3-м столбце Cr1 min по избыточным строкам не определяется, так как этот столбец не имеет поставки в единственной недостаточной 1-й строке;
б) в каждом столбце, имеющем поставку в недостаточной строке, определяется разность между минимальной стоимостью по избыточным строкам и минимальной стоимостью по столбцу в целом:
A j = C rj - C kj .
Значение Aj фиксируется во вспомогательной строке (строкаj в табл. 17.1).
Например, в приближении № 1 в 1-м столбце Aj = 12-10 = 2, во 2-м Aj = 15- = 12 = 3, в 4-м столбце Aj = 15-15 = 10. В 3-м столбце значение A3 не определено, так как поставка находится в избыточной строке;
в) находится наименьшее значение из всех Aj:
A = min Aj, которое прибавляется по всем стоимостям во всех недостаточных строках.
Так, для приближения № 1 получаем:
A = min (2, 3, 10) = 2.
Все стоимости в недостаточной 1-й строке увеличиваются на A = 2, в остальных не меняются. Значения стоимостей на этом этапе решения показываются дробью в правом верхнем углу клеток в недостаточных строках, причем в числителе дроби - первоначальное значение стоимости, в знаменателе - обновленное в соответствии с шагом 5 алгоритма решения задачи.
6. Нахождение связей строк, возникших в результате преобразования стоимостей в пункте 5.
Строка S считается связанной со строкой t при соблюдении 2-х условий:
а) в каком-либо столбце d имеется совпадение стоимостей
С sd = Ctd ;
б) в клетке sd имеется поставка
Xsd > 0.
481
При этих условиях существует направленная связь клеток:
sd ^ td.
При ручном выполнении расчетов связи удобно показывать стрелками на матрице.
Смысл понятия связи строк следующий. В рассматриваемом методе допустимыми для поставок являются клетки матриц с минимальными по столбцу стоимостями. После изменения стоимостей в матрице появляется новая допустимая клетка (иногда несколько), в которую может быть перенесена часть поставки из недостаточной строки.
Связь строк указывает возможное направление переноса поставки. Так, в приближении № 1 после изменения стоимостей в 1-й строке клетка 3.1 стала допустимой. Это означает возможность переноса поставки из клетки 1.1 в клетку 3.1, т.е. наличие связи между этими строками.
Нахождение последовательности (цепи) связей между абсолютно недостаточной и любой избыточной строками.
Цепь может состоять из одной или несколько связей и возникает после исполнения пункта 6. В нее всегда входит вновь образованная в этом пункте связь, начиная от которой удобно вести поиск цепи.
Например, в приближении № 3 новая связь появилась между клетками 3.1 и 2.1; от прежнего цикла (приближения) осталась связь клеток 1.2 и 3.2. Цепь от абсолютно недостаточной 1-й строки до избыточной 2-й строки проходит по клеткам 1.2-3.2 и 3.1-2.1. В приближении № 1 цепь состоит лишь из одной связи 1.1-3.1, так как эта связь начинается в абсолютно недостаточной и кончается в избыточной строке.
Определение величины переноса поставок AX, выполняемого одновременно по всем связям найденной цепи.
Эта величина равняется наименьшему из следующих чисел:
абсолютному значению разбаланса в недостаточной строке, где цепь начинается;
разбалансу в избыточной строке, где цепь кончается;
значению поставок во всех клетках, где начинаются связи, входящие в цепь:
нч
X
AX = min
/R /. R
нач кон
нч
где Xij - поставки в нечетных клетках цепи, если переписать их в порядке от недостающей строки к избыточной,
^нач, ^кон, - невязки в строках, где начинается и кончается цепь переноса поставок.
Например, величина переноса по цепи, найденной в приближении № 1, равна
AX = min (11, 10, 7) = 7, а по цепи, найденной в приближении № 3 -
AX = min (1,1,6,7) = 1.
9. Перенос поставок.
Найденное значение AX вычитается из поставок во всех нечетных по порядку клетках цепи и добавляется к поставкам во всех четных. В результате получается новый вариант плана, либо оптимальный, либо с меньшей по модулю суммой отрицательных разбалансов, чем предыдущий вариант. Далее метод условно-оптимальных планов предполагает переход к шагу 2 и циклическое продолжение шагов алгоритма до тех пор, пока в пункте не обнаружится, что отрицательных разбалансов больше нет и найденное решение оптимально.
Так, в приближении № 1 переносится 7 единиц поставок из клетки 1.1 в клетку 3.1 и происходит переход к приближению № 2.
При выполнении пункта 9 в приближении № 2 переносятся 3 единицы поставок из клетки 1.2 в клетку 3.2, и происходит переход к приближению № 3. В приближении № 3 единицы поставок переносятся из клетки 1.2 в клетку 3.2 и из клетки 3.1 - в клетку 2.1. Полученное в результате приближение № 4 после проверки на шаге 3 алгоритма решения оказывается оптимальным.
Решение матричной транспортной задачи с применением компьютеров позволяет использовать иной вариант метода условно-оптимальных планов - алгоритм дифференциальных рент, при котором переносы поставок по связям не делаются, а вместо этого на каждом цикле расчета все поставки распределяются заново по допустимым клеткам (с наименьшими по столбцу стоимостями, учитывая ранее выполненные изменения стоимости).
Для решения сетевых транспортных задач широко применяется метод потенциалов, который основан на свойстве потенциальности оптимального плана.
Пусть имеется некоторая схема потоков однородного ресурса (груза, порожних вагонов) по транспортной сети с ограниченной пропускной способностью звеньев. Пропускную способность звена r-s в направлении к s обозначим drs. Все звенья в зависимости от наличия потока х^ данного груза делятся на три категории:
базисные с потоками
пустые без потока данного груза xrs=0;
насыщенные xrs=drs.
Рассматривается однопродуктовая задача.
В многопродуктовой задаче насыщенными являются звенья с суммой потоков всех грузов, равной пропускной способности.
Если схема потоков оптимальна, всем вершинам сети могут быть присвоены потенциалы U, удовлетворяющие следующим условиям:
для базисных звеньев Us - Ur = Crs, (17.7)
где Crs - расстояние или издержки (в зависимости от используемого критерия) перевозки единицы груза от r до s;
для пустых звеньев Us - Ur для насыщенных звеньев Us - Ur > Crs.
Равенство Us - Ur = Crs во всех случаях допустимо и не противоречит оптимальности схемы. Нарушение условий (17.7) и (17.8), т.е. Us - Ur> Crs для пустого звена и Us - UrПри решении сетевой задачи вначале разрабатывается исходная схема потоков. Затем ведется циклический расчет по улучшению плана. Каждый цикл включает в себя присвоение потенциалов вершинам, проверку условий (17.7) и (17.8) и замещение схемы потоков.
1. Построение начального плана.
Начальная схема потоков должна удовлетворять следующим требованиям:
а) соблюдение условия баланса для всех вершин сети:
Z Xks -Z Xrk = Rk ;
(сдача) (прием) +погрузка выгрузка
б) непревышение пропускной способности звеньев, поток Xrs в) отсутствие замкнутых контуров, образованных базисными звеньями с потоками 0 Желательно построить начальную схему без явных нерациональностей (встречностей, кружностей), что позволит сократить число вводимых впоследствии поправок.
2. Присвоение потенциалов всем вершинам сети.
Какой-либо вершине, к которой примыкает хотя бы одно базисное звено, присваивается произвольный потенциал (число одного порядка с наибольшей дальностью перевозок). Затем присваиваются потенциалы остальным вершинам сети, следуя по всем базисным звеньям и используя равенство Us-Ur = Crs. При потоке от R^S вершине S присваивается потенциал Us=Ur+Crs (где Crs - длина звена). Если поток следует от S к R, то потенциал определяется по следующей формуле: Us=Ur - Crs.
Е -6
В этом случае имеющихся базисных звеньев недостаточно для присвоения потенциалов всем вершинам. Тогда вводятся n-1 нулевые потоки, связывающие между собой отдельные системы базисных звеньев. Звенья с нулевыми потоками считаются базисными и используются для присвоения потенциалов.
485
В процессе присвоения потенциалов может обнаружиться так называемый случай вырождения: совокупность (граф) базисных звеньев распадается на n несвязанных между собой систем. На рис. 17.10 показаны две такие системы: В-А-Г и Д-Б-Е.
В задаче с ограничениями пропускной способности компоненты базисного графа могут быть отделены друг от друга не только пустыми, но и насыщенными звеньями. Тогда вводятся условные нулевые резервы пропускной способности на некоторых насыщенных звеньях, которые далее считаются базисными.
3. Проверка соблюдения условий (17.7 и 17.8) на всех пустых и насыщенных звеньях сети.
280
200
+29
Если эти условия соблюдаются везде, то задача решена и план оптимален. При наличии нарушений-невязок Ну выбираем участок с наибольшей невязкой и переходим к пункту 4. На рис.17.11 показан начальный вариант плана сетевой транспортной задачи с ограничениями пропускной способности звеньев. Вершинам сети присвоены потенциалы. Проверка нужна для пустых звеньев А-Е, Е-Д и насыщенного звена Г-Д. Остальные звенья - базисные. Длины звеньев в направлении «туда» и «обратно» совпадают.
Условие 17.7 нарушено на звене А-Е: Ve - Ua = 440 - 220 = 220 > Cae = 200; Нае = 220 - 200 = 20. Условие (17.8) нарушено на звене Г-Д: Ud - Ur = 330 - 280 = 50 4. Поиск пути по базисным звеньям между вершинами-концами звена с невязкой.
Совокупность этого пути и звена с невязкой называется контуром. Для начального варианта на рисунке 17.11 контур составляют звенья Г-Д, Д-Ж, Ж-Б и Б-Г. Для второго варианта (см. рис. 17.12) в контур входят звенья А-Е, Е-В, В-Ж, Ж-Д, Д-Г, Г-А, для третьего варианта (см. рис. 17.13) контур состоит из звеньев Б-Ж, Ж-Б, В-Е, Е-А, А-Г и Г-Б.
280
200
+29 240
280
200
Дальнейшее действие зависит от того, является ли звено с невязкой пустым или насыщенным.
Классификация потоков контура.
а) Устанавливается направление потока на звене с невязкой от меньшего потенциала к большему;
б) все другие потоки в контуре делятся на попутные и встречные этому потоку. Так, для начального варианта (рис. 17.11) звенья Г-Д и Б-Г - попутные, а
Д-Ж и Ж-Б - встречные, во втором варианте (рис. 17.12) звенья А-Е, В-Ж, Ж-Д - попутные, а Е-В, Д-Г и Г-А - встречные, в третьем варианте (рис. 17.13) Б-Ж, В-Е, А-Г - попутные, а ЖБ, БА, ГБ - встречные.
Определение изменения потоков АХ. Изменение потоков:
а) для пустого звена с невязкой:

АХ = min[ min X; min(d - x)], где d - пропускная способность звена.
Следовательно, поправка равна меньшей из двух величин: наименьшего встречного потока и наименьшего свободного остатка пропускной способности для попутных потоков;
б) для насыщенного звена с невязкой (в точности обратное правило):
> AX = min[ min X; min(d - x)], т.е. берутся наименьший попутный поток и наименьший из резервов пропускной способности для встречных потоков. При использовании правил (17.9) и (17.10) звено с невязкой учитывается в числе попутных. Для начального варианта величина изменения потоков АХ1 определится как минимальное из следующих величин:
AX1 = min[(20,8, (16 -11), (10 - 6)] = 4, так как звено с невязкой - пустое.
Для второго варианта величина изменения потоков АХ2 определится следующим образом:
AX2 = min[(15,16,22, 30, (16 -14), (16 -15)] = 1, так как звено с невязкой - насыщенное.
Для третьего варианта величина изменения потоков АХ3 определится так:
AX3 = min[(10,14,21, (16 -15), (30 -1)(30 - 4)] = 1, так как звено с невязкой - насыщенное.
7. Исправление плана.
а) при исправлении невязки на пустом звене потоки по всем попутным звеньям контура (включая звенья с невязкой) увеличиваются на АХ, а по встречным - уменьшаются на АХ;
б) при исправлении невязки на насыщенном звене, наоборот, потоки на всех попутных звеньях контура уменьшаются, а на встречных увеличиваются на АХ.
В расчете получается новый вариант плана, для которого заново определяются потенциалы, проверяется наличие невязок и т.д. (т.е. от пункта 7 переходим к пункту 2). Расчет заканчивается, когда в пункте 3 не будет обнаружено ни одной невязки, что и происходит в 4-м варианте решения, которое является оптимальным и показано на рис. 17.14.
200
Решение сетевой транспортной задачи непосредственно не содержит значений поставок по корреспонденциям, а дает лишь схему потоков по участкам. Поставки по корреспонденциям должны быть получены исходя из этой схемы, причем одной и той же оптимальной схеме потоков часто соответствует много вариантов поставок, равноценных по значению критерия оптимальности.
Такие равноценные оптимальные варианты называются альтернативными оптимумами. Например, в варианте на рис. 17.13 груз, прибывший от Б к Г, может быть выгружен в Г или направлен далее к Д в составе потока 15 единиц по участку Г-Д. При наличии альтернативных оптимумов из них можно выбрать более удобный или выгодный по соображениям, не учтенным в критерии оптимальности. Простота и наглядность нахождения большого числа альтернативных оптимумов является одним из преимуществ сетевой постановки транспортной задачи.

План перевозок

является оптимальным планом тогда и только тогда, когда найдется система платежей

для которой выполняются условия:

Доказательство. Сформулируем вторую теорему двойственности в терминах переменных транспортной задачи.

удовлетворяют ограничениям прямой задачи, а

удовлетворяют ограничениям двойственной задачи, то для оптимальности плана

необходимо и достаточно выполнение условий

Условие а) выполняется для любых допустимых решений прямой задачи, так как

Условие b) можно расписать как следствие о дополняющей нежесткости, а именно

Итак, для базисных переменных

имеем равенство

а для небазисных переменных

достаточно выполнения допустимости двойственных переменных

Таким образом имеем условия 1) и 2) критерия.

Критерий доказан.

9.5 Построение опорного плана транспортной задачи

Методы решения транспортной задачи сводятся к простым операциям с транспортной таблицей, которая имеет вид:

Базисными клетками транспортной таблицы являются клетки с от-

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

1) сумма перевозок в каждой строке равна запасу в данной

2) сумма перевозок в каждом столбце равна соответствующему

столбцу спросу

Опорный план транспортной задачи содержит не более n+m-1

отличных от нуля перевозок

Опорный план называется вырожденным , если число ненулевых перевозок

меньше и n+m-1, опорный план - невырожден , если число

ненулевых перевозок равно n+m-1.

Рассмотрим способы построения опорного плана в невырожденном и вырожденном случаях.

Метод севево-западного угла

Рассмотрим "северо-западный угол" незаполненной таблицы, то

есть клетку, соответствующую первому поставщику и первому потребителю.

Возможны три случая.

Это означает, что первый поставщик отгрузил весь произведенный продукт первому потребителю и его

запас равен нулю, поэтому

При этом неудовлетворенный спрос в первом пункте потребления равен

то есть спрос первого потребителя полностью удовлетворен и поэтому

а остаток продукта в первом пункте производства равен

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

поэтому условно считается, что выбывает только поставщик,

а спрос потребителя остается неудовлетворенным и равным нулю.

После этого рассматриваем северо-западный угол оставшейся не-

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

через n+m-1 шагов получим опорный план.

10. Математическая модель транспортной задачи. Открытые и закрытые задачи. Допустимый, опорный и оптимальный планы перевозок.

Под названием «транспортная задача» объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.

Открытая и закрытая транспортные задачи. Выделяют два типа ТЗ: открытая ТЗ и закрытая ТЗ.

Транспортная задача называется закрытой, если выполняется условие баланса : суммарный объем производства равен суммарному объему потребления:

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

Открытая ТЗ имеет место в двух случаях.

Первый случай. Суммарный объем производства меньше суммарного объема потребления:

Известно, что для существования допустимого решения транспортной задачи необходимо и достаточно, чтобы задача была закрытой. Поэтому транспортную задачу открытого типа предварительно необходимо свести к закрытой, для чего вводится фиктивный пункт производства с номером m+1 с объемом производства:

, (3.3)

при этом полагают .

Второй случай. Суммарный объем производства больше суммарного объема потребления:

Для сведения ТЗ к закрытому типу вводят фиктивный пункт потребления с номером n+1 с объемом потребления:

, (3.5)

при этом полагают .

Методы решения.

· Как задача линейного программирования ТЗ может быть решена симплекс методом .

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

11. Построение начального (опорного) плана перевозок по методу северо–западного угла и по методу наименьшей стоимости.

1.Метод северо-западного угла. При нахождении опорного плана на каждом шаге рассматривают первый из оставшихся пунктов отправления и первый из оставшихся пунктов назначения. Заполнение клеток таблицы условий начинается с левой верхней клетки для неизвестного («северо-западный угол») и заканчивается клеткой для неизвестного, т.е. как бы по диагонали таблицы.

2. Метод наименьшей стоимости. Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую и в клетку , которая ей соответствует, помещают меньшее из чисел и , затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс размещения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.

Транспортная задача

Постановка транспортной задачи

Транспортная задача (Т-задача) является одной из наиболее распространенных специальных задач ЛП. Первая строгая постановка Т-задачи принадлежит Ф. Хичкоку, поэтому в зарубежной литературе ее часто называют проблемой Хичкока.

Первый точный метод решения Т-задачи разработан Л. В. Канторовичем и М. К. Гавуриным.

Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления (заводы, склады, базы и т.д.) в n пунктов назначения (магазины). При этом, из каждого пункта отправления (производства) возможно транспортировка продукта в любой пункт назначения (потребления). В качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки.

Выбор критерия оптимальности

При решении транспортной задачи выбор критерия оптимальности имеет важное значение. Как известно, оценка экономической эффективности примерного плана может определятся по тому или иному критерию, положенного в основу расчета плана. Этот критерий является экономическим показателем, характеризующим качество плана. До настоящего времени нет общепринятого единого критерия всесторонне учитывающего экономические факторы. При решении транспортной задачи, в качестве критерия оптимальности в различных случаях используют следующие показатели:

1) Объем работы транспорта (критерий - расстояние в т/км). Минимум пробега удобен для оценки планов перевозок, поскольку расстояние перевозки определяется легко и точно для любого направления. Поэтому критерию нельзя решать транспортные задачи с участием многих видов транспорта. С успехом применяется при решении транспортных задач для автомобильного транспорта. При разработке оптимальных схем перевозки однородных грузов автомобилями.

2) Тарифная плата за перевозку груза (критерий - тарифы провозных плат). Позволяет получить схему перевозок, наилучшую с точки зрения хозрасчетных показателей предприятия. Все надбавки, а также существующие льготные тарифы затрудняют его использование.

3) Эксплутационные расходы на транспортировку грузов (критерий - себестоимость эксплутационных расходов). Более верно отражает экономичность перевозок различными видами транспорта. Позволяет делать обоснованные выводы о целесообразности переключения с одного вида транспорта на другой.

4) Сроки доставки грузов (критерий - затраты времени).

5) Приведенные затраты (с учетом эксплуатационных расходов, зависящих от размеров движения и капиталовложения в подвижной состав).

6) Приведенные затраты (с учетом полных эксплуатационных расходов капиталовложений на строительство объектов в подвижной состав).

,

где - эксплутационные издержки,

Расчетный коэффициент эффективности капиталовложения,

Капитальные вложения, приходящие на 1 т груза на протяжении участка,

Т - время следования,

Ц - цена одной тоны груза.

Позволяет более полно производить оценку рационализации разных вариантов планов перевозок, с достаточно полной выраженностью количественно-одновременное влияние нескольких экономических факторов.

Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза. Обозначим через тарифы перевозки единицы груза из i-го пункта отправления в j-й пункт назначения, через – запасы груза в i-м пункте отправления, через – потребности в грузе в j–м пункте назначения, а через – количество единиц груза, перевозимого из i-го пункта отправления в j-й пункт назначения. Тогда математическая постановка задачи состоит в определении минимального значения функции

при условиях

(2)

(3)

(4)

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

Таким образом, Т-задача представляет собой задачу ЛП с m*n числом переменных, и m + n числом ограничений - равенств.

Очевидно, общее наличие груза у поставщиков равно , а общая потребность в грузе в пунктах назначения равна единиц. Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, т. е.

то модель такой транспортной задачи называется закрытой или сбалансированной .

Существует ряд практических задач, в которых условие баланса не выполняется. Такие модели называются открытыми . Возможные два случая:

В первом случае полное удовлетворение спроса невозможно .

Такую задачу можно привести к обычной транспортной задаче следующим образом. В случае превышения потребности над запасом, т. е. вводится фиктивный (m +1)–й пункт отправления с запасом груза и тарифы полагаются равными нулю:

Тогда требуется минимизировать

при условиях

Рассмотрим теперь второй случай .

Аналогично, при вводится фиктивный (n +1)–й пункт назначения с потребностью и соответствующие тарифы считаются равными нулю:

Тогда соответствующая Т-задача запишется так:

Минимизировать

при условиях:

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

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

В некоторых случаях нужно задать, что по каким-либо маршрутам нельзя перевозить продукцию. Тогда стоимости перевозок по этим маршрутам задаются так, чтобы они превышали самые высокие стоимости возможных перевозок (для того, чтобы было невыгодно везти по недоступным маршрутам) – при решении задачи на минимум. На максимум – наоборот.

Иногда нужно учесть, что между какими-то пунктами отправки и какими-то пунктами потребления заключены договора на фиксированные объемы поставки, то надо исключить объем гарантированной поставки из дальнейшего рассмотрения. Для этого объем гарантированной поставки вычитается из следующих величин:

· из запаса соответствующего пункта отправки;

· из потребности соответствующего пункта назначения.

Пример.

Четыре предприятия данного экономического района для производства продукции используют три вида сырья. Потребности в сырье каждого из предприятий соответственно равны 120, 50, 190 и 110 ед. Сырье сосредоточено в трех местах его получения, а запасы соответственно равны 160, 140, 170 ед. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок являются известными величинами и задаются матрицей

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.

Решение. Обозначим через количество единиц сырья, перевозимого из i–го пункта его получения на j–е предприятие. Тогда условия доставки и вывоза необходимого и имеющегося сырья обеспечиваются за счет выполнения следующих равенств:

(6)

При данном плане перевозок общая стоимость перевозок составит

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

Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления (поставщики) A1, A2, . . ., Am в n пунктов потребления (потребители) B1, B2, . . . Bn так, чтобы:

Вывезти все грузы от поставщиков;

Удовлетворить спрос каждого потребителя;

Обеспечить минимальные суммарные транспортные расходы на перевозку всех грузов.

Рассмотрим транспортную задачу, в качестве критерия оптимальности которой используется минимальная стоимость перевозки всего груза .

Обозначим:

ai - наличие груза в i -ом пункте отправления https://pandia.ru/text/78/103/images/image205_0.gif" width="81" height="27 src=">;

сij - стоимость перевозки единицы груза из i -ого пункта отправления в j -ый пункт потребления (тариф перевозки);

xij - количество груза, перевозимого из i -ого пункта отправления в j -ый пункт назначения, назначения, xij ≥ 0.

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

Запишем математическую модель транспортной задачи.

Требуется определить матрицу ) , которая удовлетворяет следующим условиям:

Https://pandia.ru/text/78/103/images/image210_0.gif" width="74" height="45">.gif" width="47" height="21">.gif" width="63" height="20"> (5.3)

и доставляет минимальное значение целевой функции

L () = https://pandia.ru/text/78/103/images/image215_0.gif" width="36" height="24"> удовлетворяют системе линейных уравнений (5.1), (5.2) и условию неотрицательности, то обеспечивается доставка необходимого груза каждому потребителю, вывоз имеющегося груза от всех поставщиков, а также исключаются обратные перевозки.

Определение 1. Всякое неотрицательное решение систем линейных уравнений (5.1) и (5.2), определенное матрицей ) называется допустимым планом транспортной задачи .

Определение 2. План ) https://pandia.ru/text/78/103/images/image218_0.gif" width="23" height="24"> , называется базисным или опорным.

Определение 4. Если в опорном плане число отличных от нуля значений переменных https://pandia.ru/text/78/103/images/image219_0.gif" width="55" height="22">.gif" width="55" height="22"> > , вводится фиктивный (n+ 1) –ый пункт назначения с потребностью bn +1 = − https://pandia.ru/text/78/103/images/image221_0.gif" width="83 height=22" height="22">

Если < https://pandia.ru/text/78/103/images/image220_0.gif" width="56 height=25" height="25">.gif" width="79" height="22 src=">

Рассмотрим один из методов построения первого опорного плана транспортной задачи – метод минимальной стоимости или наилучшего элемента матрицы удельных затрат.

Определение 6. Наилучшим элементом матрицы удельных затрат (тарифов) будем называть наименьший тариф, если задача поставлена на минимум целевой функции, наибольший тариф – если задача поставлена на максимум.

Алгоритм построения первого опорного плана.

1. Среди матрицы удельных затрат находим наилучший тариф.

2. Клетку распределительной таблицы с выбранным тарифом заполняем максимально возможным объемом груза с учетом ограничений по строке и столбцу. При этом либо весь груз вывозится от поставщика, либо полностью удовлетворяется потребность потребителя. Строка или столбец таблицы вычеркивается из рассмотрения и в дальнейшем распределении не участвует.

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

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

Дальнейшее улучшение первого опорного плана транспортной задачи и получение оптимального плана производим методом потенциалов.

Теорема 3 . План ) транспортной задачи является оптимальным, если существует система (m + n) чисел ui и vj (называемых потенциалами), удовлетворяющая условиям:

(5.6)

(5.7)

Потенциалы ui и vj являются переменными двойственной задачи, составленной к исходной транспортной задаче, и обозначают оценку единицы груза в пунктах отправления и назначения соответственно.

Обозначим: ) оценка свободной (незанятой) клетки таблицы.

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

Алгоритм метода потенциалов

1. Построение первого опорного плана транспортной задачи методом минимальной стоимости.

2. Проверка вырожденности плана .

Потенциалы могут быть рассчитаны только для невырожденного плана. Если число занятых клеток в опорном плане (число базисных переменных) меньше, чем (m+n−1), то вносим нуль в одну из свободных клеток таблицы так, чтобы общее число занятых клеток стало равным (m+n−1). Нуль вводят в клетку с наилучшим тарифом, которая принадлежит строке или столбцу. Одновременно вычеркиваемых при составлении первого опорного плана. При этом фиктивно занятая нулем клетка таблицы не должна образовывать замкнутого прямоугольного контура с другими занятыми клетками таблицы.

3. Расчет значения функции цели (5.4) путем суммирования произведений тарифов (удельных затрат) на объемы перевозимого груза по всем занятым клеткам таблицы.

4. Проверка оптимальности плана.

Определяем потенциалы . Для каждой занятой клетки записываем уравнение , в результате получаем систему (m + n−1) уравнений с (m + n) переменными.

Так как число переменных больше числа уравнений, то полученная система не определена и имеет бесчисленное множество решений..gif" width="70" height="22">, тогда остальные потенциалы определяются однозначно, а их значения заносятся в дополнительные строку и столбец распределительной таблицы.

Для каждой свободной клетки определяем оценки https://pandia.ru/text/78/103/images/image233.gif" width="72 height=24" height="24">(задача решается на минимум целевой функции), то оптимальный план найден. Если хотя бы одна оценка свободной клетки не удовлетворяет условию оптимальности, то необходимо план улучшить, осуществив перераспределение груза.

5.

Из всех положительных оценок свободных клеток выбираем наибольшую (задача поставлена на минимум); из всех отрицательных – наибольшую по абсолютной величине (задача поставлена на максимум). Клетку, которой соответствует наибольшая оценка, следует заполнить, т. е. направить в нее груз. Заполняя выбранную клетку, необходимо изменить объем поставок, записанных в ряде других занятых клеток и связанных с заполняемой так называемым циклом.

Циклом или прямоугольным контуром в распределительной таблице транспортной задачи называется ломанная линия, вершины которой расположены в занятых клетках таблицы, а звенья – вдоль строк и столбцов, причем в каждой вершине цикла встречаются ровна два звена, одно из которых находится в строке, другое – в столбце. Если ломанная линия, образующая цикл, пересекается, то точки пересечения не являются вершинами. Для каждой свободной клетки можно построить единственный цикл.

Вершинам цикла, начиная от вершины, находящейся в выбранной клетке на загрузку, присваиваем поочередно знаки «+» и «−» . будем назвать эти клетки плюсовыми и минусовыми.

Из объемов груза, стоящих в минусовых клетках, выбираем наименьшее и обозначим его θ. Перераспределяем величину θ по контуру, прибавляя θ к соответствующим объемам груза, стоящим в плюсовых клетках, и вычитаем θ из объемов груза, находящихся в минусовых клетках таблицы. В результате клетка, которая была свободной и выбрана на загрузку, становится занятой, а одна из занятых клеток контура – свободной.

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

Замечания.

1. Если в минусовых клетках построенного цикла находятся два или несколько одинаковых минимальных значений , то при перераспределении объемов груза освобождается не одна, а две или несколько клеток. В этом случае план становится вырожденным. Для продолжения решения необходимо одну или несколько одновременно освобождающихся клеток таблицы занять нулем, причем предпочтение отдается клеткам с наилучшим тарифом. Нулей вводят столько, чтобы во вновь полученном опорном плане число занятых клеток (базисных переменных) было ровно (m + n−1).

2. Если в оптимальном плане транспортной задачи оценка для некоторой свободной клетки равна нулю ) , то задача имеет множество оптимальных планов. Для клетки с нулевой оценкой можно построить цикл и перераспределить груз. В результате полученный план будет также оптимальным и иметь такое же значение целевой функции.

3. Значение целевой функции на каждой итерации можно рассчитать следующим образом:

(задача поставлена на минимум),

(задача поставлена на максимум),

где - величина перемещаемого по контуру объема груза;

Оценка свободной клетки, в которую направляется груз при переходе к новому опорному плану;

− значение функции цели на k-ой итерации;

− значение функции цели на предыдущей итерации.

Пример.

На трех складах оптовой базы имеется однородный груз в количествах 40, 80 и 80 единиц. Этот груз необходимо перевезти в четыре магазина, каждый из которых должен получить соответственно 70, 20, 60 и 60 единиц. Стоимости доставки единицы груза (тарифы) из каждого склада ) во все магазины ) заданы матрицей .

Составить план перевозок однородного груза с минимальными транспортными затратами (числа условные).

Решение.

1. Проверим необходимое и достаточное условие разрешимости задачи:

40+80+80 = 200,

70+20+60+60 = 210.

Как видно, суммарная потребность груза превышает его запасы на складах оптовой базы. Следовательно, модель транспортной задачи является открытой и в исходном виде решения не имеет. Для получения закрытой модели введем дополнительный (фиктивный) склад А4 с запасом груза, равным а 4 = 210 – 200 = 10 ед. тарифы перевозки единицы груза из склада А4 во все магазины полагаем равными нулю.

Все исходные данные заносим в таблицу 7.

						Запасы
	A 1
	A 2		3
	A 3
	A 4
Потребности					210 210

2. Построение первого опорного плана методом минимальной стоимости.

Среди тарифов минимальным или наилучшим является С14 =1. В клетку А1В4 направляем максимально возможный груз, равный min{60,40} = 40. Тогда x 14 = 40. Из склада А1 весь груз вывезен, но потребность четвертого магазина неудовлетворенна на 20 ед. строка А1 выходит из рассмотрения.

Среди оставшихся тарифов минимальный элемент - С23 = 2. В клетку А2В3 направляем груз min{60,80} = 60. При этом столбец В3 выходит из рассмотрения, а из склада А2 не вывезено 20 ед.

Из оставшихся элементов минимальный С22 = 3. В клетку А2В2 направляем груз в количестве min{20,20} = 20. При этом столбец одновременно вычеркиваются строка А2 и столбец В2.

Выбираем минимальный элемент С31 = 4. В клетку А3В1 направляем груз, равный min{70,80} = 70. При этом столбец В1 выходит из рассмотрения, а из склада А3 не вывезено 10 ед. Оставшийся груз с третьего склада направляем в летку А3В4, x 34 = 10. Потребность четвертого магазина не удовлетворена на 10 ед. направим от фиктивного поставщика – склад А4 10 ед. груза в клетку А4В4, x 44 = 10.

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

3. Проверка вырожденности плана.

Число занятых клеток или базисных переменных в первом опорном плане равно шести. план транспортной задачи является вырожденным, так как число базисных переменных в невырожденном плане равно m + n – 1 = 4 + 4 – 1 = 7. Для продолжения решения задачи опорный план необходимо дополнить введением фиктивной перевозки, т. е. занять нулем одну из свободных клеток.

При построении первого опорного плана одновременно были вычеркнуты строка А2 и столбец В2, поэтому произошло вырождение плана. На право фиктивной перевозки претендуют свободные клетки строки А2 и столбца В2, которые имеют минимальный тариф и не образуют с занятыми клетками замкнутого прямоугольного контура. Такими клетками являются А2В4 и А3В2. Нуль направляем в клетку А2В4.

4. Расчет значения целевой функции.

Значение целевой функции первого опорного плана определяем путем суммирования произведений тарифов на объемы перевозимого груза по всем занятым клеткам таблицы.

L(Х1) = 4∙70 + 3∙20 + 2∙60 + 1∙40 + 3∙0 + 6∙10 + 0∙10 = 560 (тыс. руб.).

5. Проверка условия оптимальности.

Рассчитаем потенциалы по занятым клеткам таблицы из условия: https://pandia.ru/text/78/103/images/image260_0.gif" width="139" height="22">Так как число неизвестных потенциалов больше числа уравнений (m + n > m + n – 1), то один из потенциалов принимаем равным нулю..gif" width="115 height=154" height="154">

Полагая , получим https://pandia.ru/text/78/103/images/image265_0.gif" width="82" height="22">, ,https://pandia.ru/text/78/103/images/image268_0.gif" width="193" height="22">

Рассчитанные потенциалы заносим в таблицу 7. Подсчитаем оценки свободных клеток.

https://pandia.ru/text/78/103/images/image270_0.gif" width="167" height="22 src=">,

https://pandia.ru/text/78/103/images/image272_0.gif" width="210" height="22 src=">,

https://pandia.ru/text/78/103/images/image274_0.gif" width="183" height="22 src=">,

https://pandia.ru/text/78/103/images/image276_0.gif" width="153" height="22 src=">,

Первый опорный план не является оптимальным, так как имеются положительные оценки свободных клеток и . Выбираем максимальную положительную оценку свободной клетки - .

6. Построение нового опорного плана.

Для клетки А3В2 построим прямоугольный замкнутый контур 0таблица 7) и проведем перераспределение груза контуру. Вершинам контура, начиная от вершины, находящейся в свободной клетке А3В2,присваиваем поочередно знаки «+» и «−» .

Из объемов груза, стоящих в минусовых клетках, выбираем наименьшее, т. е. θ = min(20,10) = 10. Прибавляем значение θ = 10 к объемам груза, стоящих в плюсовых клетках, вычитаем из объемов груза, стоящих в минусовых клетках замкнутого контура. В результате получим новый опорный план, приведенный в таблице 8.

Одним из направлений организации транспортной логистики является оптимизация не только расходов по задействованию автотранспортных средств на предприятии, но также и оптимизации самих перевозок.

Дорогие читатели! Статья рассказывает о типовых способах решения юридических вопросов, но каждый случай индивидуален. Если вы хотите узнать, как решить именно Вашу проблему - обращайтесь к консультанту:

ЗАЯВКИ И ЗВОНКИ ПРИНИМАЮТСЯ КРУГЛОСУТОЧНО и БЕЗ ВЫХОДНЫХ ДНЕЙ .

Это быстро и БЕСПЛАТНО !

Изучение того, какие ставятся задачи для такой деятельности в организации, позволяет не путаться в понятиях и вести эффективную хозяйственную деятельность.

И, действительно, современные методы позволяют спрогнозировать большое количество перевозок по предприятию, каковы они ни были бы – дальнобойными, международными или же межрегиональными.

Что это такое

Оптимизация автотранспортных перевозок – это использование методов и технологий, позволяющих максимально точно рассчитать время управления маршрутами и расходами, связанными с перевозками.

Решать подобные задачи можно при помощи расчетов, производимых сотрудниками транспортного отдела, складов, управленческих подразделений по контролю запасов и другие отделы, при помощи компьютерной программы. Использует на практике сейчас – и то и другое.

Определяя понятие оптимизации автоперевозок, можно подчеркнуть – постоянное, регулярное усовершенствование системы перевозки (доставки, загрузки/выгрузки) грузов клиентов.

Такие технологии на сегодня специалистами предлагаются в форме программного обеспечения. Установка и пользование компьютерной программой, способной точно рассчитывать маршруты, расходы, направления и другие нюансы, позволяет не содержать большой штат в транспортном отделе. А некоторые организации уже даже не имеют такового вовсе.

Достаточно обучить оператора-диспетчера или бухгалтера работать в данном сервисе, и предприятие будет полностью обеспечено эффективным решением экспедиторских, посреднических и других задач.

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

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

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

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

Какие проблемы решает

Многие предприятия, занимающиеся грузоперевозками, стараются найти пути решения для следующих вопросов:

1. Как определить оптимальность маршрутов?
2. Насколько можно максимально наметить короткие пути для доставки груза?
3. На чем, как и где можно сэкономить?
4. Как распорядиться ведением хозяйственной деятельности и контроля маршрутов, если диспетчера нет на месте или диспетчер – новичок в работе? И другие вопросы.

Любая задача содержит в себе не только суть проблемы, что требуется решения, но и сам способ ее урегулирования и улучшения.

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

1. В некоторых случаях ограничение количества тары, а также размеров грузоперевозочных машин.
2. Сведение к минимуму перепогрузок с одного транспортного средства в другое, из одной тары для транспортировки в другую.
3. Организация удобства погрузочных или разгрузочных работ в самом кузове грузовика.
4. Автоматизация маркировки грузов либо полное исключение такового освобождает процесс доставки от затягивания сроков перевозки.
5. Укрупнения количества единиц или самого груза в целом по машине, с механизацией разгрузки на месте у заказчика.
6. Учет типа машины для лучшей грузовместимости.
7. Добиться того, чтобы грузы имели одинаковый размер от заказа к заказу.
8. Сделать частоту поставок больше, при этом не увеличивать стоимость единицы груза, который перевозится.
9. Снижение затрат на процесс упаковки перевозимого товара вместе с тем, чтобы максимально сохранить его целостность в процессе перемещения из одной точки в другую.
10. Стандартизация подбора типов машин под каждый заказ, его размер.
11. Быстро определить, какие поставки клиентам максимальные, а какие – минимальные.
12. Сведение к минимуму затрат на перевозку бракованного товара, возвратной продукции.
13. Путем системы распределения сократить брак, возникающий в процессе перевозок.
14. Снизить величину времени, затрачиваемую на каждый транзит груза.
15. Уменьшение времени, затрачиваемого на каждый простой, который происходит по естественным причинам – загрузка/разгрузка.
16. Сведение к минимуму затрат, что приходятся на доставку груза клиенту.
17. Сделать равномерным поток движения грузовых поставок. Особенно это касается сезонной специфики.
18. Если речь идет о партиях поставок, тогда желательно использовать минимум количества машин, задействованных для этих целей.
19. Сортировка грузов таким образом, чтобы максимально его вместить в машину.
20. Снижение времени, затрачиваемого на поступление и получение той или иной информации касательно грузов, заявок на поставку и самой транспортировки. Например:
    • сведения о простое;
    • оперативная информация о месте нахождения грузовиков;
    • когда прибыла машина в пункт назначения (время указывается с точностью до секунд);
    • своевременное сообщение диспетчеру о поломках в пути или иных возникших препятствиях к благополучному прибытию в пункт назначения и другое.

Таким образом, мы понимаем, что помимо проблем напрямую, которые очевидны сразу, существуют также и косвенные причины снижения эффективности работы в сфере транспортных перевозок.

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

Или же, если были допущены ошибки в требованиях к плану перевозок – тогда вполне очевидно, что водитель может, либо сбиться с курса, либо не учесть особенности сроков доставки и другие проблемы.

Методы оптимизации транспортных перевозок

Современное практическое применение множества задач позволило отобрать сегодня одну из наиболее оптимальных методик – это эвристический метод.

Подход заключается в основном не в акценте на эффективность маршрута, а в максимально приближении самого решения задачи в целом, что ставит предприятия на основе клиентского заказа.

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

Однако эвристика лишена гибкости, а потому ее современные логисты еще дорабатывают. Одно, несомненно – за данным методом явно видится будущее для наиболее эффективного транспортного перемещения.

Определим несколько наиболее активных методов, которыми пользуются на сегодня транспортники:

1. Исследование операций.
2. Линейное математическое программирование (ЛП):
   • применение линейных уравнений при расчетах – линейной функцией от элементов путей решения является целевая (эффективная) функция L (х);
   • линейные равенства/неравенства представляют собой ограничительные условия для возможных решений;
   • целевой функцией является самое большее ил меньшее значение, которое ищут в математическом программировании, учитывая ограничения;
   • ограничения могут встречаться строгими (ровно столько и никак иначе) и нестрогими (не более или не менее какого-то ориентировочного значения).
3. Техника северо-западных углов (эвристика).
4. Методика мини-тарификации (эвристика).
5. Метод Фогеля (эвристика).
6. Способ коммивояжера.
7. Применение алгоритма Свира (или еще как говорят – «дворника-очистителя», задачи решаются нематематической эвристикой).

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

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

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

Эвристика позволяет расставить в матрице значения, начиная с левой ячейки вверху. И начинается расстановка с наименьшей цены, более дешевых заказов в сторону увеличения.

Такой принцип используется также и в методе минимальных тарифов, но только тогда от угла не расставляют значения. Так можно отыскать необходимые решения – от предварительных до окончательных оптимальных итогов.

В технике Фогеля предполагают наличие некое вспомогательного коэффициента, который следует рассчитать как по строке, так и по столбцу матрицы.

Коэффициент будет равняться разности тарифов (двух самых минимальных), которые имеются в строке или столбце. Распределение коэффициентов следует по принципу «от наибольшего к наименьшему».

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

Это говорит о том, что в условиях задач по принципу коммивояжера будут выставляться критерии выгоды по стоимости маршрута. Технически это выглядит следующим образом – на протяжении всего рейса грузовик должен проходить каждый город один раз.

Поэтому из-за большого скопления в одном заказе точек по маршруту такую задачу нельзя решить методов исследования операций. Здесь самым выгодным будет именно эвристический подход.

Как организована на предприятии

При практическом решении транспортно-грузовых задач требуется согласовать все нюансы. Нужно правильно спланировать маршруты, погрузку товаров, его своевременную разгрузку, возврат машины и прочие моменты, касающиеся операции в целом.

А для этого предпринимают следующие шаги:

1. Организация координационного отдела или постановка задачи перед одним сотрудником-координатором (чаще всего таковым является начальник или менеджер ).
2. Смежная работа между отделами, издание соответствующих распоряжений и приказов и иное взаимодействие между отделами.
3. Совместное планирование маршрутов, согласование и реализация этих планов, построение графиков между отделами или подразделениями.
4. Установка между операциями единых показателей таким образом, чтобы достичь более функциональной работы.
5. При необходимости привлекается руководство для налаживания связей между подразделениями, отделами предприятия.
6. Обязанности между отделами и сотрудниками должны быть четко разделены.
7. Если возникают какие-либо споры, тогда должны быть обозначены те лица, которые будут уполномочены принимать окончательные решения.
8. Организовать единое информационное поле, которое бы показывало состояние маршрутов и грузоперевозок.

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