Математическая запись задачи. Обозначим через Xij количество порожняка в автомобиле - ездках предназначенного к отправке из пункта разгрузки Бj в пункт погрузки Ai, тогда суммарный холостой пробег автомобиля из всех пунктов с наличием порожняка во все пункты его подачи будет иметь вид n m S S Xij lij min. 1 j1 i1 Условие полного удовлетворения спроса на порожняк каждого пункта отправления за счт подачи его из разных пунктов с наличием порожняка выглядит так n S Xij ai, где i 1,2 m. 2 j1 Весь порожняк из каждого пункта назначения должен быть подан в пункт отправления под погрузку, т.е. m S Xij bj, где j 1,2 n. 3 i1 Очевидно, что количество автомобилей не может быть отрицательным числом, т.е. Xij 0, при i 1,2 m, j 1,2 n. 4 Таким образом, в математической форме транспортная задача формулируется так Определить значение переменных Xij минимизирующих линейную форму, выраженную 1, при ограничениях, указанных в 2,3,4. Необходимо равенство общей потребности получателей и наличия груза у поставщиков или отправителей m n S bj S аj 5 i1 j1 Это равенство является необходимым и достаточным условием для совместимости уравнений 2,3. Цель решения выражается уравнением 1 найти минимальный суммарный холостой пробег автомобилей. Задачу, выраженную формулами 1 5 принято называть задачей минимизации холостых пробегов автомобилей. 3.3. Метод совмещнных планов.
Для решения задачи разработан метод совмещнных планов.
С его помощью она решается в три этапа.
На первом этапе решают задачу минимизации холостых пробегов автомобилей, в результате чего находят оптимальный план возврата порожняка под погрузку после разгрузки.
Составление оптимального плана отражено в блок-схеме алгоритма метода потенциалов на рисунке 1. На втором этапе из грузопотока линий перевозок заданных заявкой на перевозки и линий оптимального плана возврата порожняка, найденного на первом этапе, составляют схему кольцевых и маятниковых маршрутов движения автомобилей, в совокупности обеспечивающих минимум холостых пробегов автомобилей при выполнении заданных перевозок.
На третьем этапе найденные маршруты прикрепляют к АТП автотранспортному предприятию, после чего разрабатывают сменно-суточные задания водителям по каждому маршруту. Составление матрицы условий Составление допустимого исходного плана Подсчт числа занятых клеток в матрице N и сравнение с mn-1 N mn-1 N mn-1 Ликвидация лишних занятых клетокNmn-1Создание недостающих занятых клеток Расчт индексов Проверка незанятых клеток на потенциальность Построение цепочки возможных перемещений загрузок Расчт знаков и - по вершинам цепочки Поиск наименьшей среди загрузок, отмеченных знаком - Изменение загрузки на вершинах цепочки Решение закончено оптимальный план составлен Потенциальных клеток нет Рис. 1. Блок-схема алгоритма метода потенциалов. 4.