Введение На российских предприятиях и на предприятиях со смешанным капиталом морские перевозки чаще всего воспринимают утилитарно, как некий комплекс операций, привычных для любой компании (транспортировка, складирование, таможенная очистка и т. д.). Однако теория и практика транспортных операций доказывают, что для подобных операций всегда используется системный подход в управлении, необходимый для повышения рентабельности и показателей безопасности. Эффективная морская транспортная система конкретной судоходной компании - во многом уникальный комплекс операций, скопировать который конкурентам бывает очень сложно и, наверно, не нужно. Такая система одновременно является и самым главным преимуществом компании, и самым уязвимым её местом. С одной стороны, она позволяет компании сосредоточиться на главном: производстве материальных ценностей посредством сокращения затрат и высвобождения средств, которые могут быть направлены на развитие компании, с другой - её деятельность нацелена на сокращение затрат и запасов и осуществляется по принципу «в нужное время, в нужном месте». При малейшем сбое в порядке выполнения морских транспортных операций компании (производители продукции) могут столкнуться либо с проблемой производства, либо с проблемой отгрузки, что в свою очередь может привести к остановке производства в целом. Если же компания-производитель способна поставлять свою продукцию потребителям быстро и с более низкими издержками, то она будет получать определённые преимущества перед конкурентами в размере рыночной доли. Цель работы - предложение алгоритма сортировки партий груза на морском терминале, основанного на идеях метода ветвей и границ. Алгоритм представлен в описательном виде и может быть использован при обработке и сортировке партий грузов с различными приоритетами при ограничении на время. Материалы исследования Рассмотрим процедуру сортировки партий груза, поступающих на морской терминал по направлению «берег - море», основанную на идеях метода ветвей и границ, при этом для оценки верхней границы решения задачи сортировки будем использовать итерационно-градиентный метод [1]. При ограниченном времени сортировки партий груза, поступающих на обработку в морской терминал, обработать все партии груза одновременно практически невозможно [2]. Поэтому если партии груза xij, подлежащие сортировке, обладают различными приоритетами, то для реализации этой операции целесообразно выбирать лишь те партии, для которых выполняется условие при заданном ограничении (1) где λj - приоритет j-й партии груза, поступившей на морской терминал; Tд - допустимое время процедуры сортировки; S - множество переменных, определяющих качество решений, принимаемых персоналом терминала при сортировке партий грузов. Время контроля j-го приоритета партии груза tij (i, j = 0; n, i ≠ j) зависит от того, какой i-й приоритет партии груза проверяется непосредственно перед ним (i = 0 означает, что оператор, ответственный за сортировку партий груза, начинает просмотр элементов партии с исходного состояния). В то же время j = 0 означает, что оператор, ответственный за сортировку партий груза, после идентификации последнего приоритета возвращается к исходной партии груза [3]. Введём обозначения: U - множество приоритетов сортировки партий груза; ES - запрещённое множество приоритетов сортировки, введение которых на множество S приводит к повторной проверке параметров, образованию недопустимых циклов или не приводит к улучшению принимаемого для необходимого результата; GS - свободное множество приоритетов сортировки, из которого производится выбор очередной переменной для включения в множество S; hij = λj / tij - коэффициент эффективности сортировки партии груза по j-му приоритету, если ему предшествовал i-й приоритет. На первом шаге решения S = Ø, Еs= Ø, а множество GS включает партии груза, прибывшие на морской терминал xij (j = 1, 2, ..., n). С помощью выражения (2) определяется переменная x0k, которая включается на множество S. При этом величина λS(x0k) будет являться верхней границей целевой функции при включении на множество S переменной x0k. На втором шаге x0k Î S, x0k Î ES (i = l, 2, ..., n), xkj Î GS (j = 1, ... , n, j ≠ n). Поэтому определив величину можно ввести переменную (партию груза) xkl на множество S. На всех последующих шагах выбор очередной партии груза для включения на множество S производится с помощью выражения, аналогичного (2). Если в процессе решения окажется, что множество GS = Ø, то величину можно принимать уже в качестве первого приближенного решения по сортировке партий груза в зависимости от приоритетов. На следующем шаге из множества S исключается партия груза, вошедшая на последнем шаге (эта партия вводится на множество ES), и поиск продолжается для вариантов, которые удовлетворяют условию Выбор вариантов заканчивается, если для всех вершин дерева имеет место GS = Ø, то есть рассмотрены все перспективные комбинации, и одновременно выполняются два условия: Рассмотрим более подробно процесс определения верхней границы целевой функции. Допустим, что сортируемые партии груза (переменные) x0,1, x1,2, ..., xk - 1,k вошли во множество S(k < n). Тогда переменные хij (i = l, 2, ..., j = 1, 2, ..., k, i ≠ j), хij (i = 1, 2, ..., k - 1, j = k + 1, k + 2, ..., n), xi0 (i = 1, 2, ..., k - 1) образуют множество ES, т. к. их введение на множество S приведёт к повторному процессу сортировки и образованию недопустимых циклов. Кроме того, на множество ES заносятся сортируемые партии груза (переменные) xkj (j = k + 1, k + 2, ..., n), для которых выполняются неравенства (3) (4) Условие (3) означает, что введение переменной хkj на множество S не может привести к улучшению полученного на предыдущих шагах решения, а неравенство (4) следует из ограничения (1). Допустим, что требуется определить верхнюю границу целевой функции (5) при условии выполнение которого определяет принадлежность партии груза к множеству S. Определим и значения Тогда, приняв, что выполняется условие (6) можно найти (7) (8) Так как при то вместо (5) для определения верхней целевой функции может быть использована зависимость вида (9) Следовательно, для определения верхней целевой функции необходимо определить партии груза, для которых выполняются условия (6)-(8), и для этих партий вычислить величину, определяемую выражением (9). Упрощенное описание алгоритма сортировки партий груза по приоритетам на морском терминале при ограничении на время может быть представлено в виде следующей алгоритмической последовательности. Блок 1. Формируются множества S, ЕS, GS и принимается начальное значение λ = 0. Блок 2. С помощью условий (6)-(9) с учётом ЕS определяются значения λS(xij) (xij Î GS) и по формуле (2) выбирается переменная хkl, которая вводится в S. Блок 3. С учётом введения хkl в S пересчитываются GS и ES. Блок 4. Проверяется условие GS = Ø. Если условие не выполняется, то продолжается процесс формирования множества S. При выполнении условия процесс формирования множества S прекращается. Блок 5. Проверяется условие λ < λS. При выполнении неравенства величина λS является новым приближенным решением. Блок 6. Запоминается новое приближенное решение λ и соответствующее ему множество S. Блок 7. Для движения вверх по дереву возможных вариантов из множества S исключается последняя переменная xkl, которая для исключения повторного просмотра ветви вводится в множество ES. Блок 8. Находится множество GS и ES после исключения xkl из множества S. Блок 9. Проверяется условие GS = Ø. Если условие не выполняется, то строится новая ветвь дерева возможных вариантов. Блок 10. Проверяется условие S = Ø. Если условие не выполняется, то продолжается движение вверх по дереву возможных вариантов. Выполнение условия свидетельствует о том, что просмотрены все перспективные ветви и получено оптимальное значение λ и соответствующее ему множество S. Таким образом, эффективность рассмотренного алгоритма сортировки партий груза по приоритетам на морском терминале при ограничении на время определяется простотой способа определения верхней границы целевой функции [4]. Кроме того, если ветви дерева возможных вариантов сортировки партий груза по заданным приоритетам строятся последовательно, то алгоритм достаточно просто реализуется [5]. Заключение При ограниченном времени сортировки партий груза, поступающих на обработку в морской терминал, обработать все партии груза одновременно практически невозможно. Представлен алгоритм и упрощенное описание (в виде последовательности десяти блоков) сортировки партий груза по приоритетам на морском терминале при ограничении на время. Эффективность рассмотренного алгоритма сортировки партий груза по приоритетам на морском терминале при ограничении на время определяется простотой способа определения верхней границы целевой функции.