22 Сен

Применение адаптации исходных данных для многостадийных моделей




Номер части:
Оглавление
Содержание
Журнал
Выходные данные


Науки и перечень статей вошедших в журнал:

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

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

В рассматриваемой задаче возможны три основных правила вывоза обработанного продукта из пунктов промежуточной обработки:

1) по окончании обработки полуфабриката на всех  промежуточных пунктах рассматриваемой стадии;

2) по готовности очередной партии продукта, доставленной ранее из какого-либо пункта отправления (транзитные  перевозки);

3) по окончании обработки продукта, назначенного в рассматриваемый пункт промежуточной обработки (перевозки с накоплением).

Решение в соответствии с первым правилом интереса не представляет, т.к. в этом случае оптимальное решение может быть найдено последовательным решением независимых одностадийных задач известными методами [1, с.117]. Наиболее интересен второй вариант вывоза обработанного продукта, так как в этом случае возможно получения решения лучшего по сравнению с первым вариантом, о чем говорилось ранее, а кроме того это решение служит основой для выработки оптимального плана по третьему варианту.

Для простоты изложения рассмотрим двустадийную модель, поскольку, ее обобщение для случая многостадийной обработки не вносит существенных изменений в алгоритм. Пусть xijk — количество продукта, доставляемое из пункта  Ai в Bk через пункт обработки Qj. Для ясности изложения будем полагать, что время обработки полуфабриката на всех промежуточных пунктах не зависит от объема поступившей партии и входит во время доставки этой партии из i-й базы в j-й пункт промежуточной обработки. Требуется определить план перевозок ||xijk||, при котором достигается минимум целевой функции

bezymyannyj               (1)

где      tijk=t’ij+t’’jk — время доставки из i-го пункта в k-й пункт назначения, через j-й пункт промежуточной обработки;

tijk(xijk)— функция, определяемая следующим образом:

bezymyannyj1

при транзитных перевозках;

bezymyannyj2

при перевозках с накоплением.

При этом должны быть выполнены условия

  bezymyannyj3                                      (2)

Необходимое и достаточное условие решения задачи

  bezymyannyj4                                                 (3)

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

bezymyannyj6

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

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

 bezymyannyj8                                            (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] исходные данные для решения оптимизационных задач, а особенно временные данные, могут быть подвержены изменениям, что вероятней всего  приведет к не оптимальности реализуемого плана. Причинами изменений значений данных могут быть дорожная ситуация, погодные условия и прочие форс-мажорные обстоятельства.

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

bezymyannyj9                            (7)

где  tреал.z — реальное время прибытия в р-й отсчетный момент времени;

где tрасч.z — расчетное время прибытия в р-й отсчетный момент времени;

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

Список литературы:

  1. Гольштейн Е.Г., Юдин Д.Б. Задачи линейного  программирования транспортного типа. -М.: «Наука», ГРФМЛ, 1969. -384 с.
  2. Мартемьянов С.В., Ольшанский В.В., Богданов А.Е. Получение интервальных оценок в условиях дефицита исходных данных. Евразийский Союз Ученых. Технические науки. – 2014. – №7 . – с.101-103.
    Применение адаптации исходных данных для многостадийных моделей
    Рассмотрена многоэтапная транспортная модель с промежуточной обработкой по критерию времени. Предложено применение венгерского метода для её решения, а также использование адаптации исходных данных в процессе реализации плана транспортировки.
    Written by: Мартемьянов Сергей Васильевич, Ольшанский Владимир Владимирович, Гавришов Владислав Андреевич
    Published by: Басаранович Екатерина
    Date Published: 12/07/2016
    Edition: euroasia-science_30_22.09.2016
    Available in: Ebook