Определение оптимальной схемы транспортировки сырья

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

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

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

Особенности задачи:

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

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

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

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

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

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

Укрупненная блок-схема алгоритма решения задачи представлена на рисунке 1. Блок-схемы основных процедур моделирования – на рисунках 2 и 3.

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

Формула (1) записана в предположении, что 60% горючего расходуется на преодоление сопротивления воздуха, а 40% - на преодоление сопротивления дороги.

Значительную роль в процессе организации вычислений играют управляющие матрицы.

43

Матрица состояния пунктов забора сырья (таблица 1) содержит информацию о находящихся в этих пунктах объемах молока и постоянно модифицируется моделирующим алгоритмом по мере забора сырья молоковозами.

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

В матрицу, представленную таблицей 6, заносятся результаты расчетов по формуле 1. Значения, заносимые в матрицу таблицы 4, есть ни что иное как суммы содержимого соответствующих строк предыдущей матрицы.

44

Таблица 5 - Последовательность заездов в пункты забора сырья

Таблица 6 - Матрица промежуточных затрат (по рейсам)

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