Планирование транспортирования грузов

Транспортные процессы и системы ЛЕКЦИЯ «Планирование транспортирования грузов (транспортная задача)» Постановка задачи. В пунктах отправления (на полях) А1, А2, …, Аj, Ап имеется однородный груз (картофель), причем количество имеющегося в пункте Аj груза составляет аj единиц. Этот груз надо доставить в пункты получения (хранилища) Б1, Б2, …, Бi, …, Бт, причем количество доставляемого груза в пункт Бi должно быть равно вi единиц. Известны расстояние или стоимость перевозок lij между пунктами отправления и получения. Задача заключается в построении такого плана транспортирования груза, при котором потребность в грузе всех пунктов получения будет удовлетворена, весь груз из пунктов отправления будет вывезен и при этот будет обеспечен минимум транспортной работы (минимум стоимости перевозок). Исходные данные записывают в матрицу табл. 1. В матрице, в правом верхнем углу соответствующих клеток записаны расстояния в км, в нижней строке наличие груза у поставщиков А1, …, А4 и в правом столбце потребность в грузах получателей Б1, …, Б5. Если количество перевозимого груза обозначить через Х с первым индексом i – куда доставляется груз (пункты получения или получатели) и вторым индексом j – откуда доставляется груз (пункты отправления или отправители), то условия задачи можно записать в следующем виде: Х11 + Х12 + Х13 + Х14 = 40 Х21 + Х22 + Х23 + Х24 = 40 Х31+ Х32 + Х33 + Х34 = 80 …, (1) Х41 + Х42 + Х43 + Х44 = 40 Х51 + Х52 + Х53 + Х54 = 10 Х11 + Х21 + Х31 + Х41 + Х51 = 15 Х12 + Х22 + Х32 + Х42 + Х52 = 85 Х13+ Х23 + Х33 + Х43 + Х53 = 40 …, (2) Х14 + Х24 + Х34 + Х44 + Х54 = 70 Рmin = 8Х11 + 12Х12 + 15Х13 + 23Х14 + 7Х21 + 10Х22 + 14Х23 + 11Х24 + + 9Х31 + 11Х32 + 19Х33 +14Х34 + 16Х41 + 14Х42 + 16Х43 + 18Х44 + + 17Х51 + 20Х52 + 19Х53 + 20Х54 … (3) Уравнения (1), (2), (3) линейные. Уравнение в системе (1) отражает ограничения по количеству груза, доставляемому в пункты получения, а уравнения (2) – ограничения по количеству груза, вывозимого из пунктов отправления. Неизвестные в этих системах Х11, Х12 и так далее могут быть положительными или равными нулю (отрицательное значение неизвестных значит груз отправляется от получателя к отправителю). Таблица 1 Получатели Потенциалы Отправители Потребность в грузе, т U V А1 А2 А3 А4 Б1 8 12 15 23 40 Б2 7 10 14 11 40 Б3 9 11 19 14 80 Б4 16 14 16 18 40 Б5 17 20 19 20 10 Наличие груза, т 15 85 40 70 210 Уравнение (3) показывает, что при решении стремятся получить минимум транспортной работы. Сумма получаемых (потребных) грузов равна сумме наличных (отправляемых) грузов. В математической форме задача имеет следующую запись: - во все i-е пункты получения груза из j-го пункта отправления может быть вывезено только аj единиц груза: ; j = 1, 2, …, n; (4) - из всех j-х пунктов отправления i-му пункту получения должно быть доставлено только вi единиц груза: , i = 1, 2, …, m; (5) Общий объем транспортной работы (стоимости) должен быть минимальным → min, (6) а искомые переменные не могут быть отрицательными числами, т.е. Хij ≥ 0. Для совместимости систем уравнений (4) и (5) необходимо, чтобы соблюдался баланс, т.е. . В построенных системах (1) и (2) имеется 9 уравнений и 20 неизвестных . Возможно большое количество решений. Однако нужно решение, отвечающее условию (3), т.е. обеспечивающее минимум транспортной работы. Такое решение можно найти методами линейного программирования. Одна из групп методов основана на принципе последовательного улучшения плана, когда выбранный определенным образом первоначальный план, при помощи расчетов улучшается до тех пор, пока не станет оптимальным. Одним из методов этой группы является метод потенциалов. Первоначальное закрепление потребителей за поставщиками Закрепление необходимо провести так, чтобы среднее расстояние перевозок грузов было наименьшим, т.е. чтобы был минимум транспортной работы в тонно-километрах. Первоначальное распределение может быть проведено способом двойного предпочтения. Вначале выбирают и отмечают (знаком *) – наименьшее расстояние в каждой строке, а затем в каждом столбце. Клетку, имеющую две отметки, загружают, т.е. записывают в нее количество груза в первую очередь (табл. 2), затем загружают клетки отмеченные один раз. Нераспределенный груз записывается в неотмеченные клетки, расположенные на пересечении неудовлетворенных строки и столбца. Таблица 2 Получатели Потенциалы Отправители Потребность в грузе, т U V А1 А2 А3 А4 Б1 * 8 12 15 40 23 40 Б2 ** 7 15 * 10 25 * 14 * 11 40 Б3 * 9 11 20 19 14 60 80 Б4 16 * 14 40 16 18 40 Б5 * 17 20 19 20 10 10 Наличие груза, т 15 85 40 70 210 Количество груза, помещаемого в каждую клетку, определяется величиной наличия груза у соответствующего получателя. В клетку А1Б2 (табл. 2) помещаем 15 т, хотя потребность составляет 40 т, потому что отправитель А1 имеет всего 15 т. В клетку А2Б2 можно записать 25 т, т.к. после загрузки клетки А1Б2 у пункта Б2 осталось неудовлетворенная потребность 25 т. После распределения груза рассчитываем транспортную работу при данном распределении 15·7 + 25·10 + 20·11 + 40·14 + 40·15 + 60·14 + 10·20 = 2775 т·км. Для уменьшения транспортной работы рассмотрим возможность перемещения загрузки в клетки с меньшим расстоянием. Это достигается, если можно компенсировать такую передвижку в данной строке. При этом необходимо, чтобы сумма расстояний в клетках, у которых уменьшается загрузка, была бы больше суммы расстояний в клетках, в которых загрузка увеличивается. Количество передвигаемой загрузки должно быть равно меньшей загрузке из указанных в обеих клетках, откуда делается передвижка. Рассмотрим возможность передвижки загрузки в строке Б1 (табл. 2). Если из А3Б1 загрузку переместить в А1Б1, то это перемещение можно компенсировать только передвижкой загрузки А1Б2 в А3Б2. При этом, сумма расстояний, указанная в клетках откуда происходит перемещение 15 + 7 = 22, а куда происходит перемещение 8 + 14 = 22, т.е. суммы равны, значит не удовлетворяется ранее высказанное требование. Поэтому передвижение загрузки нецелесообразно. Проверка по всем строкам табл. 2 показывает, что целесообразным является передвижка из клетки А4Б3 и А2Б2 в клетки А2Б3 и А4Б2 соответственно (что показано сплошными стрелками). (Сумма расстояний 24 и 22). Количество передвигаемого груза здесь может быть не более 25 т. (Результаты передвижения показаны в табл. 3). Аналогично рассмотрим возможность улучшения распределения по столбцам. В табл. 3 – (показано сплошными стрелками) целесообразное улучшение распределения, а в табл. 4 показан результат передвижки по столбцам. Для варианта табл. 4 транспортная работа Р = 2710 т·км, что на 65 т·км меньше, чем для первоначального закрепления. Проверка оптимальности распределения Для проверки распределения находят специальные показатели для столбцов U и строк V называемые потенциалами. Для каждой загруженной клетки разность между соответствующими этой клетке потенциалами должны быть равна расстоянию, указанному в этой клетке, т.е. V – U = l. в связи с этим все потенциалы определяются по следующему правилу. Для одного из столбцов – отправителей потенциал U принимают равным 0. Этот столбец должен иметь наибольшее расстояние в загруженной клетке. Остальные потенциалы определяются по загруженным клеткам: для столбцов U = V – l, для строк V = U + l. Таблица 3 Получатели Потенциалы Отправители Потребность в грузе, т U V А1 А2 А3 А4 Б1 * 8 12 15 40 23 40 Б2 ** 7 15 * 10 * 14 11 25 40 Б3 9 11 45 19 14 35 80 Б4 16 14 40 16 18 40 Б5 17 20 19 20 70 10 Наличие груза, т 15 85 40 70 210 Так как загруженная клетка с наибольшим расстоянием находится в столбце А4(А4Б5), поэтому потенциал принимают U4 = 0. По загруженным клеткам определяют потенциал строк Б2, Б3, Б5: V2 = U4 + l4,2 = 0 + 11 = 11; V3 = U4 + l4,3 = 0 + 14 = 14; V5 = U4 + l4,5 = 0 + 20 = 20. По загруженным клеткам А1Б3, А2Б3 определяют потенциалы столбцов А1, А2: U1 = V3 – l1,3 = 14 – 9 = 5; U2 = V3 – l2,3 = 14 – 11 = 3. Таблица 4 Получатели Потенциалы Отправители Потребность в грузе, т U V А1 А2 А3 А4 Б1 * 8 12 15 40 23 40 Б2 7 10 14 11 40 40 Б3 9 15 11 45 19 14 20 80 Б4 16 14 40 16 18 40 Б5 17 20 19 20 10 10 Наличие груза, т 15 85 40 70 210 По загруженной клетке А2Б4 определяем потенциал строки Б4 V4 = U2 + l2,4 = 3 +14 = 17. Потенциалы V1 и U3 не определены. Для определения численных значений всех потенциалов необходимо, чтобы число загруженных клеток в матрице было равно n + m – 1, где n – число основных строк; m – число основных столбцов. В табл. 4 загружено 7, а нужно 5 + 4 – 1 = 8 клеток, т.е. не хватает одной загруженной клетки. Этого не должно быть, поэтому существует правило, если число загруженных клеток меньше n + m – 1, то искусственно загружают недостающее количество клеток, для чего в них записывают 0. В последующем с этой клеткой оперируют как с загруженной. Нуль ставят в ту клетку, которая лежит на пересечении строки и столбца не имеющих потенциала, со строкой или столбцом уже имеющих потенциалы. В табл. 5 нуль ставят в любую клетку строки Б1 или столбца А3. Выбираем клетку А1Б1, ставим туда 0. Определяем потенциалы V1 и U3: V1 = U1 + l1,1 = 5 + 8 = 13; U3 = V1 – l3,1 = 13 – 15 = - 2. В некоторых случаях после первоначального распределения потенциалы той или иной строки или столбца могут определяться неоднозначно. Если бы первоначальное распределение было не в соответствии с табл. 5, а в соответствии с табл. 6, то потенциал столбца А3 определялся бы неоднозначно по загруженной клетке А3Б1 (U3 = 15 – 15 = 0), а по загруженной клетке (А3Б2 (U3 = 1 – 14 = -3). Такого положения не должно быть. Потенциал должен определяться однозначно. Неоднозначное определение потенциалов возможно, если в матрице число загруженных клеток больше, чем n + m – 1, или при неправильном расположении загруженных клеток. В табл. 6 количество загруженных клеток 9 вместо 8. Таблица 5 Получатели Потенциалы Отправители Потребность в грузе, т U V А1 А2 А3 А4 5 3 - 2 Б1 13 8 ‑ 12 15 40 + 23 40 Б2 11 7 10 14 11 40 40 Б3 14 9 15 + 11 45 ‑ 19 14 20 80 Б4 17 16 14 40 + 16 ‑ 18 40 Б5 20 17 20 19 20 10 10 Наличие груза, т 15 85 40 70 210 Для устранения неоднозначности определения потенциала необходимо для одной из загруженных клеток. по которым определялся этот потенциал, построить, контур-замкнутую линию, состоящую из прямых горизонтальных и вертикальных отрезков, все вершины которой лежат в загруженных клетках. Каждой выбранной клетке может соответствовать только один контур. Контур строится следующим образом. Таблица 6 Получатели Потенциалы Отправители Потребность в грузе, т U V А1 А2 А3 А4 5 3 0; - 3 Б1 13 8 - 0 12 15 + 15 25 – 23 40 Б2 11 7 10 14 + 15 11 25 ‑ 40 Б3 14 9 15 11 30 – 19 14 35 + 80 Б4 17 16 14 40 16 18 40 Б5 20 17 20 19 20 10 10 Наличие груза, т 15 85 40 70 210 От клетки проводят линию по строчке или столбцу до загруженной клетки, которой должна соответствовать еще одна загруженная клетка под прямым углом. И так до тех пор, пока не замкнется в исходной клетке. Движение при построении контура совершается строго под прямым углом, причем в каждой строке и столбце, который находится в замкнутой линии в состав контура входят всегда по две клетки. Контур может быть различной формы. Число вершин всегда положительно. Пересечение горизонтальных и вертикальных линий не являются вершинами. Вершиной контура является лишь та загруженная клетка, где линии образуют прямой угол (в табл. 6 контур построен для клетки А3Б2). Далее составляется алгебраическая сумма из расстояний всех клеток находящихся в вершинах контура. Расстояниям попеременно присваивают знаки « + » и « – », начиная с расстояния выбранной клетки, которой присваивается знак « + ». Если сумма имеет положительное число, то выбранная для начала контура клетка вновь обозначается « + », а обозначения остальных вершин контура остается без изменения. Если сумма имеет отрицательное число, то выбранной клетке присваивается знак « – », а остальным вершинам попеременно знаки « + » « – ». Если сумма равна нулю, то выбранной клетке можно присвоить любой знак. Для контура (табл. 6), начиная с клетки А3Б2 сумма положительна (14 – 11 + 14 – 11 + 12 – 15 = 3), поэтому обозначения « + » и « – » оставляем прежними. Затем из всех вершин контура, обозначенных знаком « + », выбираем цифру наименьшей загрузки (15). Она вычитается из загрузки, указанной в клетках со знаком « + » и прибавляется к загрузке, указанной в клетках со знаком « – ». Такая операция приведет к ликвидации одной из загружены клеток и тем самым к однозначному определению потенциала. Кроме того, эта операция ликвидации лишних загруженных клеток приводит либо к сокращению числа т·км, либо (когда сумма расстояний равна нулю) не приводит к их увеличению. Если выполнить эту операцию в табл. 6, то будет получено распределение соответствующее табл. 5. Это позволит однозначно определить потенциалы, что сделано в табл. 5. После однозначного определения потенциалов рассматриваются все незагруженные клетки и среди них отыскиваются такие, для которых имеется положительное число d = V – U – l. Делаем расчеты для всех незагруженных клеток табл. 5. Клетки, имеющие d ≤ 0 из дальнейшего рассмотрения исключаем. В результате расчета устанавливаем, что в табл. 5 d > 0 имеют место для следующих клеток: А3Б4: d34 = 17 – (- 2) – 16 = 3; А3Б5: d35 = 20 – (- 2) – 19 = 3. Полученные значения записываются в левых верхних углах (в кружках) соответствующих клеток табл. 5. Наличие таких клеток показывает, что это распределение не оптимальное. Улучшение полученного распределения Для клетки с максимальным числом в кружке строиться контур. В табл. 5 контур построен для клетки А3Б4. Всем вершинам попеременно присвоены знаки « + » и « – », начиная с выбранной клетки которой присвоен знак « – ». Из всех клеток. имеющих знак « + », выбирают с цифрой наименьшей загрузки. Это клетка А1Б3 с загрузкой 15. Это количество груза отнимают от загрузки, указанной в клетках со знаком « + » и прибавляют к загрузке в клетках со знаком « – ». Полученное распределение загрузки записывают в новую матрицу, куда также переносят без изменений загрузки тех клеток, которые не явились вершинами контура (табл. 7). Таблица 7 Получатели Потенциалы Отправители Потребность в грузе, т U V А1 А2 А3 А4 8 3 1 Б1 16 8 15 12 – 15 25 + 23 40 Б2 11 7 10 14 11 40 40 Б3 14 9 11 60 19 14 20 80 Б4 17 16 14 25 + 16 15 – 18 40 Б5 20 17 20 19 20 10 10 Наличие груза, т 15 85 40 70 210 Далее с табл. 7 проделывают все операции, описанные ранее. Определяем потенциалы в табл. 7 и находим клетки с положительным значением d. Это клетка А2Б1, имеющая d = 1. Для нее строим контур, вершины которого, начиная с клетки А2Б1, попеременно обозначаем знаками « – » и « + ». Выбираем наименьшую загрузку со знаком « + ». Это загрузка 25 в клетках А3Б1 и А2Б4. При переносе этой загрузки из клеток со знаком « + » в клетки со знаком « – » в матрице одновременно освободятся две клетки. В этом случае необходимо в одной из освободившихся клеток после перестановки оставить нулевую загрузку. Это сделано в таблице 8, где в клетке А3Б1 стоит 0 и дано новое распределение. Однако анализ клетки А3Б5 в табл. 8 показывает, что оптимальный план еще не найден, т.к. для этой клетки d = 1. Таблица 8 Получатели Потенциалы Отправители Потребность в грузе, т U V А1 А2 А3 А4 7 3 Б1 15 8 15 12 25 – 15 + 23 40 Б2 11 7 10 14 11 40 40 Б3 14 9 11 60 + 19 14 20 – 80 Б4 16 16 14 16 40 18 40 Б5 20 17 20 19 ‑ 20 10 + 10 Наличие груза, т 15 85 40 70 210 Поэтому строим для нее контур и на его вершинах со знаком « + » выбираем клетку с наименьшей загрузкой. ею является клетка А3Б1, где загрузка равна нулю. С нулем обращаются как с реальной нагрузкой. Поэтому надо перенести в клетку А3Б5, а в остальных клетках от вычитания или прибавления нуля загрузка не измениться. Эти операции выполнены в табл. 9. Определяем потенциалы U и V и значения d для незагруженных клеток. Незагруженных клеток с положительными значениями d нет. Значит полученное распределение улучшить нельзя, т.е. оно оптимальное. Таким образом. вычисления ведутся последовательно до тех пор, пока имеются клетки с положительными значениями d. Их отсутствие показывает, что улучшить распределение нельзя, т.е. получено оптимальное решение. Сравнивая транспортную работу в предварительном распределении (табл. 2) равную 2775 т·км и окончательную (табл. 9) 2640 т·км видим, что она сокращена на 135 т·км. Таблица 9 Получатели Потенциалы Отправители Потребность в грузе, т U V А1 А2 А3 А4 7 3 1 Б1 15 8 15 12 25 15 23 40 Б2 11 7 10 14 11 40 40 Б3 14 9 11 60 + 19 14 20 – 80 Б4 17 16 14 – 16 40 + 18 40 Б5 20 17 20 19 – 20 10 + 10 Наличие груза, т 15 85 40 70 210 Часто такое оптимальное распределение не является единственно возможным. Если в матрице, где записано оптимальное распределение, имеются незагруженные клетки, для которых d = 0, то возможно получить и другие варианты распределения. Это делается путем построения контура с d = 0 и соответствующих перемещений всей наименьшей загрузки или части ее. Эти варианты тоже будут оптимальными, но закрепление потребителей за поставщиками будет иное. В табл. 9 для клетки А2Б4 d = 0. Строим для нее контур и присваиваем его вершинам знаки « – » « + ». Наименьшую загрузку в клетках со знаком « + », равную 10, перемещаем в соответствии с общими правилами. Новое распределение представлено в табл. 10. Здесь транспортные работы, как и в табл. 9 равна 2640 т·км. Таблица 10 Получатели Потенциалы Отправители Потребность в грузе, т U V А1 А2 А3 А4 7 3 1 Б1 15 8 15 12 25 15 23 40 Б2 11 7 10 14 11 40 40 Б3 14 9 11 50 19 14 30 80 Б4 17 16 14 10 16 30 18 40 Б5 20 17 20 19 10 20 10 Наличие груза, т 15 85 40 70 210 Возможность получить в некоторых случаях различные оптимальные решения может быть использована на практике. Так, если по решению в табл. 9 потребитель Б5 должен получать груз от отправителя А4, а это по каким-то причинам нежелательно, то по решению в табл. 10 этот потребитель получает груз от отправителя А3 при общем оптимальном распределении. В основу решения может быть положено не только получение минимального среднего расстояния в километрах, чему соответствует минимум транспортной работы в т·км. Критерием оптимальности можно принять минимум стоимости транспортирования, тогда в верхних правых углах клеток проставляются стоимости транспортирования между пунктами. Если нужно найти минимум затраченного времени на транспортирование, то соответственно в правых верхних углах клеток проставляется время транспортирования между пунктами и т.д. Кроме метода потенциалов широкое распространение получил модифицированный распределительный метод (МОДИ), который от метода потенциалов отличается лишь тем, что вместо разности потенциалов, вычисляется их сумма. Эта сумма должна быть равна расстоянию в соответствующих загруженных клетках. Для улучшения плана отыскивается такая незагруженная клетка, в которой расстояние будет меньше суммы двух соответствующих ей потенциалов. Все остальные операции по расчету оптимального плана производятся аналогично методу потенциалов.