АЛГОРИТМ КОНКУРИРУЮЩИХ ТОЧЕК ДЛЯ ЗАДАЧИ УПАКОВКИ

ALGORITHM OF COMPETITIVE POINTS FOR THE PACKING PROBLEM

Alexander Dvoryankin

Doctor of science., Professor of the Department of POAS,  Volgograd State Technical University,

Russia, Volgograd

Ismail Adams Ibrahim

student of POAS department, Volgograd State Technical University(VSTU),

Russia, Volgograd

Jean Max Habib Tape

student of POAS department, Volgograd State Technical University(VSTU),

Russia, Volgograd

АННОТАЦИЯ

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

ABSTRACT

The purpose of the work is meant to find the optimal resolution of segments from the center of gravity. The article presents an algorithm of competing points for solving the packing problem. In such a scenario, the competing point algorithm proves to be an effective tool for providing practically optimal solutions in a short time.

Ключевые слова: одномерная упаковка, приложенная сила, нагруженные отрезки, алгоритм, упаковка.

Keywords: one-dimensional packing, applied force, loaded segments, algorithm, packing.

ВВЕДЕНИЕ

Проблема упаковки бункера - одна из самых важных проблем оптимизации. В последние годы благодаря NP-жесткий характер, представлено несколько алгоритмов аппроксимации. Доказано, что лучший алгоритм для задачи упаковки бункера имеет коэффициент аппроксимации 3/2 и временной порядок O (n), если P = NP.

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

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

МОДЕЛИ

A(отрезок нагрузки) - это горизонтальный отрезок, к которому силу, приложенная вертикально вниз..:, где a - расстояние от левого края отрезка до точки приложения силы , b - расстояние от точки приложения силы до правого края отрезка. Силу  это вес отрезки с заданным положением центра тяжести и . Для обозначения различных отрезков будем использовать нижние индексы в виде букв или цифр: или  Компоненты отрезка , будем также обозначать как .

ПОСТАНОВКА ЗАДАЧИ

Пусть заданы  отрезков  и некоторое число . Для любой перестановки  поставим соединение сегментов: . Функция   - функцией перестановки w.

Для заданного множества  отрезков и числа  определим функцию δ:

                                           (1)

Задача: найти перестановку, на которой достигается минимум функции:

АЛГОРИТМ

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

1 шаг. Генерация случайной перестановки , здесь _, Перестановку можно найти с помощью алгоритма Фишера-Йетса.

2 шаг. Вычисление центр тяжести для перестановки  .

3 шаг. Перестановке , присвоить номер k=0 и обозначить как w₀. На итерации к алгоритму для перестановки  вычислить значения . Перестановка  строится путём применением к перестановке   расположение элементов с номеров . На итерации k обозначить  и вычислить  Решение – соответствующая перестановка , с минимальной

Используя следующий пример исходных данных при  = 7 и  = 35 приведён в таблице 1.

Таблица 1.

Исходные данные

Показан работы алгоритмов в таблице 2. При  найдено ближайшее оптимальное решение: . Отклонение от глобального минимума не превышает значения δ.

Применение алгоритма полного перебора даёт глобальный минимум на перестановке .

Далее в таблице 3 представлены результаты работы программы.

Таблица 2.

Отчёт работы программы

ЗАКЛЮЧЕНИЕ

Дана постановка задачи размещения отрезков, нагруженных сосредоточенной силой. Критерием оптимального размещения является минимальное отклонение центра тяжести получившегося отрезка от заданного значения. Алгоритм даёт приблизительное решение, а иногда и точное. Однако время работы по сравнению с алгоритмом перебора уменьшилось в 4-10 раз и временная сложность алгоритма .

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

1. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования Пер. с англ. - М.: Наука, 1965. — 460 с.
2. Романовский И. В. Алгоритмы решения экстремальных задач. - М: Наука, 1977.-352 с.
3. Залюбовский В. В. О представлении перестановками допустимых решений одномерной задачи упаковки в контейнеры. // Труды XIII Байкальской международной школы-семинара «Методы оптимизации». Том 1: Иркутск, ИСЭМ СО АН РАН.- 2005. с.461- 467.
4. Месягутов М. А, Мухачева Э. А., Г. Н. Белов, Шайтхауэр Г. Упаковка одномерных контейнеров с продолженным выбором идентичных предметов: точный метод поиска оптимального решения, Автомат. и телемех., 2011, № 1, 154–173
5. Мейер Б., Бодуэн К. Методы программирования: в 2-х томах. Т.2. Пер. с франц. Ю.А. Первина. Под ред. А.П. Ершова.-М.: Мир, 1982.-368 с.