Оптимальный план перевозки продукции совхоза «Алексеевский»

Существует метод решения задачи коммивояжера, который дает оптимальное решение. Этот метод называется методом ветвей и границ. Решение задачи коммивояжера методом ветвей и границ по-другому называют алгоритмом Литтла.

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

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

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

Опишем алгоритм Литтла для нахождения минимального гамильтонова контура для графа с n вершинами. Граф представляют в виде матрицы его дуг. Если между вершинами Xi и Xj нет дуги, то ставится символ «∞».

Алгоритм Литтла для решения задачи коммивояжера можно сформулировать в виде следующих правил:

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

.

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

,

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

3. Суммируем элементы и , получим константу приведения

,

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

.

4. Находим степени нулей для приведенной по строкам и столбцам матрицы. Для этого мысленно нули в матице заменяем на знак «∞» и находим сумму минимальных элементов строки и столбца, соответствующих этому нулю. Записываем ее в правом верхнем углу клетки:

.

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

.

6. Разбиваем множество всех гамильтоновых контуров на два подмножества и . Подмножество гамильтоновых контуров содержит дугу , - ее не содержит. Для получения матрицы контуров , включающих дугу , вычеркиваем в матрице строку и столбец . Чтобы не допустить образования негамильтонова контура, заменим симметричный элемент на знак «∞».

7. Приводим матрицу гамильтоновых контуров . Пусть - константа ее приведения. Тогда нижняя граница множества определится так:

.

8. Находим множество гамильтоновых контуров , не включающих дугу . Исключение дуги достигается заменой элемента в матрице на ∞.

9. Делаем приведение матрицы гамильтоновых контуров . Пусть - константа ее приведения. Нижняя граница множества определится так:

.

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

Процесс разбиения множеств на подмножества сопровождается построением дерева ветвлений.

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

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

1.3. Математическая модель задачи коммивояжера

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

    (1)

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

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

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

, где , и .

2. Практическая часть

2.1. Решение задачи коммивояжера методом Литтла

При планировании перевозок возникает необходимость в определении кратчайших расстояний между предприятием и пунктами потребления грузов. Как уже было отмечено ранее, совхоз «Алексеевский» имеет 30 магазинов в городе Уфа. Месторасположение магазинов можно посмотреть по карте, которая представлена в приложении 1.

Так как город Уфа является «длинным» городом, то для упрощения будет рассмотрена только центральная часть города, на карте она обведена черным квадратом, маленький черный квадратик является точкой отчета, началом пути (см. приложение 1).

В центральной части совхоз «Алексеевский» имеет 10 магазинов. Найдем кратчайший путь грузовика. Для этого необходимо определить расстояния между этими 10 магазинами от начала пути, тогда получим матрицу 11 на 11 (см. таблицу 1).

Таблица 1. Матрица расстояний

1-10 – это нумерация магазинов, 0 – это начало пути.

Ресурс Интернет позволяет решать задачу коммивояжера методом Литтла онлайн. Такая возможность реализована на сайте «Задачи оптимизации» со свободным доступом [1]. Начальная страница сайта представлена в приложении 2.

Решив задачу методом Литтла, получим кратчайшее расстояние - 28,06 км: 0→2→5→3→6→7→8→10→9→4→1→0 (представлен на рисунке 1)

Рис.1. Граф-схема оптимального пути

2.2. Определение транспортных затрат

Предположим, что совхоз «Алексеевский» имеет одну грузовой автомобиль, имеющую следующие характеристики, представленные в таблице 2.

Таблица 2

Себестоимость автотранспортных перевозок определяется путем калькулирования затрат по всем статьям и элементам расходов. Как уже было отмечено ранее, все затраты делятся на две части: на начально-конечные (постоянные) и движенческие (переменные) операции. Определим эти затраты по отдельности.

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

      амортизационные отчисления автомобиля

      заработная плата водителя, охранника

      страховые взносы

      амортизация гаража

      транспортный налог.

1) Амортизацию посчитаем линейным способом. Линейный способ – годовая сумма начисления амортизационных отчислений определяется исходя из первоначальной стоимости объекта и нормы амортизации, исчисленной исходя из срока полезного использования этого объекта.

              Срок полезного использования равен 7 лет (84 месяца). Определим норму амортизации:

.

Амортизационные отчисления найдем по формуле:

(руб.),

где P- стоимость автомобиля.

(руб.)

2) Фонд заработной платы = заработная плата водителя + заработная плата охранника=8000+12000=20000 (руб.)

3) Отчисления на социальные нужды представляют собой страховые взносы и определяются в процентах от фонда заработной платы. Эти отчисления направляются в пенсионный фонд РФ, в фонд социального страхования РФ, в федеральный фонд обязательного медицинского страхования и территориальные фонды обязательного медицинского страхования.

              Ставка страховых взносов равно 26% от фонда заработной платы.

(руб.)

4) Амортизацию гаража посчитаем линейным способом. Срок полезного использования равен 40 лет (480 месяцев). Определим норму амортизации:

.

Вычислим амортизационные отчисления:

(руб.)

5) Налоговая ставка (100 л.с. до 150 л.с.) равна 40 руб. Номинальная мощность ГАЗ 3302 "ГАЗель" равна103 (140) кВт (л.с.). Соответственно транспортный налог равен:

(руб.)

Сведем результаты в таблицу, подсчитав расходы за день (см. Таблица 3).

Таблица 3