В статье рассматривается модель транспортировки однородных грузов из пунктов постоянной дислокации (производства) в пункты назначения через промежуточные стадии с временным критерием. Примерами таких задач могут служить многостадийное производство, какого то продукта (например, молочное производство) или многоэтапная передислокация сил (средств) к местам выполнения задач (в т.ч. и промежуточных).
Задача заключается в составлении такого плана перевозок, при котором весь продукт (груз) вывозится и полностью обрабатывается, полностью используются возможности пунктов промежуточной обработки и удовлетворяются потребности всех пунктов назначения, а время всей операции минимально. Задачи этого класса не распадаются на одностадийные. По результатам ряда вычислительных экспериментов установлено, что общее время операции, получаемое суммированием решений одностадийных задач, в среднем на 15% и более может превышать общее время существующего оптимального решения.
В рассматриваемой задаче возможны три основных правила вывоза обработанного продукта из пунктов промежуточной обработки:
1) по окончании обработки полуфабриката на всех промежуточных пунктах рассматриваемой стадии;
2) по готовности очередной партии продукта, доставленной ранее из какого-либо пункта отправления (транзитные перевозки);
3) по окончании обработки продукта, назначенного в рассматриваемый пункт промежуточной обработки (перевозки с накоплением).
Решение в соответствии с первым правилом интереса не представляет, т.к. в этом случае оптимальное решение может быть найдено последовательным решением независимых одностадийных задач известными методами [1, с.117]. Наиболее интересен второй вариант вывоза обработанного продукта, так как в этом случае возможно получения решения лучшего по сравнению с первым вариантом, о чем говорилось ранее, а кроме того это решение служит основой для выработки оптимального плана по третьему варианту.
Для простоты изложения рассмотрим двустадийную модель, поскольку, ее обобщение для случая многостадийной обработки не вносит существенных изменений в алгоритм. Пусть xijk — количество продукта, доставляемое из пункта Ai в Bk через пункт обработки Qj. Для ясности изложения будем полагать, что время обработки полуфабриката на всех промежуточных пунктах не зависит от объема поступившей партии и входит во время доставки этой партии из i-й базы в j-й пункт промежуточной обработки. Требуется определить план перевозок ||xijk||, при котором достигается минимум целевой функции
(1)
где tijk=t’ij+t’’jk — время доставки из i-го пункта в k-й пункт назначения, через j-й пункт промежуточной обработки;
tijk(xijk)— функция, определяемая следующим образом:
при транзитных перевозках;
при перевозках с накоплением.
При этом должны быть выполнены условия
(2)
Необходимое и достаточное условие решения задачи
(3)
Для поиска оптимального решения предлагается определить нижнюю границу целевой функции t*, с помощью которой затем вычислить ограничения на величину перевозимого продукта по каждому маршруту dijk по правилу
и решить задачу о максимальном потоке в сети с ограниченными пропускными способностями коммуникаций венгерским методом.
Если в результате решения задачи о потоке все столбцы матрицы перевозок окажутся закрытыми, то оптимальное решение найдено. В противном случае значение целевой функции увеличивается до величины следующего по возрастанию времени tijk (на величину Dt), и вновь решается задача о максимальном транспортном потоке и т.д.
(5)
Невыполнение первого условия свидетельствует о невозможности вывоза всего продукта из исходных пунктов, невыполнение второго — о невозможности полного удовлетворения пунктов назначения, невыполнение третьего о невозможности полного удовлетворения потребностей пунктов промежуточной обработки. При невыполнении любого из приведенных условий (5) значение t* увеличивается до значения следующего по возрастанию времени tijk и происходит возврат к проверке выполнения условий (5). Затем составляется исходный план перевозок одним из известных методов, например, методом северо-западного угла. При этом назначение величины перевозки в каждой клетке матрицы должно производится по правилу:
xijk=min(a’i, q’j, b’k, dijk), (6)
где a’i, q’j, b’k — ресурсы и потребности соответствующих пунктов с учетом уже назначенных перевозок.
Поскольку значение F при решении задачи транзитных перевозок не превышает величины F при решении задачи с накоплением при тех же исходных данных, то предлагается получать оптимальное решение задачи с накоплением используя результаты решения задачи транзитных перевозок и исключая из него после пересчета времен перевозки со временем, равным значению F.
Предложенный подход обеспечивает безусловное получение оптимального решения при неизменных значениях исходных данных. Однако как было показано в [2, с. 102] исходные данные для решения оптимизационных задач, а особенно временные данные, могут быть подвержены изменениям, что вероятней всего приведет к не оптимальности реализуемого плана. Причинами изменений значений данных могут быть дорожная ситуация, погодные условия и прочие форс-мажорные обстоятельства.
В этом случае целесообразным представляется использование данных актуальных в текущий момент времени, что естественно может обеспечить лишь наличие обратной связи с лицами, выполняющими план операции. Для реализации такого подхода необходимо уточнять план операции через определенные временные промежутки, в соответствии с текущим положением состоянием операции, при этом каждое из времен может измениться следующим образом:
(7)
где tреал.z — реальное время прибытия в р-й отсчетный момент времени;
где tрасч.z — расчетное время прибытия в р-й отсчетный момент времени;
Таким образом, в соответствии с предлагаемым подходом уточнение плана операции должно происходить в общем случае р раз, с откорректированными исходными данными. Как показали проведенные эксперименты, использование адаптированных значений исходных данных позволяет получить в среднем на 10-15% улучшенное решение.
Список литературы:
- Гольштейн Е.Г., Юдин Д.Б. Задачи линейного программирования транспортного типа. -М.: «Наука», ГРФМЛ, 1969. -384 с.
- Мартемьянов С.В., Ольшанский В.В., Богданов А.Е. Получение интервальных оценок в условиях дефицита исходных данных. Евразийский Союз Ученых. Технические науки. – 2014. – №7 . – с.101-103.[schema type=»book» name=»Применение адаптации исходных данных для многостадийных моделей» description=»Рассмотрена многоэтапная транспортная модель с промежуточной обработкой по критерию времени. Предложено применение венгерского метода для её решения, а также использование адаптации исходных данных в процессе реализации плана транспортировки.» author=»Мартемьянов Сергей Васильевич, Ольшанский Владимир Владимирович, Гавришов Владислав Андреевич» publisher=»Басаранович Екатерина» pubdate=»2016-12-07″ edition=»euroasia-science_30_22.09.2016″ ebook=»yes» ]