ПРИКАСПИЙСКИЙ ЖУРНАЛ

УПРАВЛЕНИЕ И ВЫСОКИЕ ТЕХНОЛОГИИ

Решение задачи размещения нагруженных отрезков на массиве перестановок «пузырек»

Читать Дворянкин А. М. Решение задачи размещения нагруженных отрезков на массиве перестановок «пузырек» // Прикаспийский журнал:  управление и высокие технологии. — 2018. — №4. — Стр. 39-45.

Дворянкин А. М. - доктор технических наук, профессор, Волгоградский государственный технический университет, 400005, Российская Федерация, г. Волгоград, пр. им. Ленина, 28, dvam1@mail.ru

Приведено описание основных используемых понятий: нагруженный отрезок, соединение отрезков, определение порядка на множестве отрезков, формула для вычисления центра тяжести соединения отрезков. Сформулирована задача размещения множества отрезков, нагруженных сосредоточенной силой. Предложено использование в качестве критерия точности решения показателя «отклонение центра тяжести от целевого положения». Задача является NP полной. Алгоритм полного перебора для ее решения имеет временную сложность O ( n !), где n - число размещаемых отрезков. При большом числе отрезков получение оптимального решения путем сплошного перебора вариантов требует очень высоких вычислительных затрат. Поэтому поиск эффективных, приближенных алгоритмов является актуальной задачей. Приводится определение массива перестановок «пузырек». Предложен алгоритм формирования транспозиций, с помощью которых можно формировать перестановки этого массива. Доказаны следующие теоремы: о неубывании положения центра тяжести соединения отрезков на этих перестановках; о вычислении приращения положения центра тяжести на соседних перестановках. На основе этих теорем построен алгоритм приближенного решения задачи размещения отрезков, временная сложность которого O ( n ). Дана формула, определяющая для заданных отрезков максмально возможное отклонение. Приведены примеры с результатами работы алгоритма. Результаты работы могут быть использованы для планирования оптимального размещения груза на транспорном средстве.

Ключевые слова: нагруженный отрезок, соединение отрезков, размещение отрезков, центр тяжести, перестановка, транспозиция, массив «пузырек», loaded segment, connection of segments, placement of segments, center of gravity, permutation, transposition, “bubble” array