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

АЛГОРИТМ ПОИСКА СУБОПТИМАЛЬНЫХ РЕШЕНИЙ В ДИСКРЕТНЫХ ЗАДАЧАХ ЛИНЕЙНОГО РАСКРОЯ

Гуськов М.Е.

Гуськов Михаил Евгеньевич - магистрант, кафедра автоматизированных систем управления, Новосибирский государственный технический университет, г. Новосибирск

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

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

УДК 519.8

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

В данной работе рассматривается производственная задача линейного раскроя. Задачи линейного раскроя в условиях массового производства относятся к классу задач линейного программировании, с неявно заданными способами раскроя [2]. При решении таких задач методами линейного программирования возникает необходимость в генерировании раскроев на каждом шаге процесса и рассмотрении всех вариантов раскроя.

Поиск и перебор субоптимальных решений представляется одной из важнейших задач дискретной оптимизации. Интерес к методам такого перебора повышается из-за необходимости анализа нескольких вариантов решения одной и той же задачи в условиях, когда математическая модель была изначально упрощена. Задачи дискретной оптимизации более требовательны, трудоемкость их решения резко меняется при малейших изменениях задачи [3]. Поэтому, при решении практических задач некоторыми существенными ограничениями могут пренебрегать, и это приведет к тому, что полученное решение окажется нереализуемым из-за внемодельных факторов, то есть тех условий, которые не стали включать в математическую модель. Соответственно, кажется естественным: перебирать допустимые решения с постепенным ухудшением целевой функции до тех пор, пока не встретится решение, приемлемое с точки зрения истинных ограничений.

В рамках текущей задачи необходимо произвести процесс перебора решений. Процесс определять пару (Б, Т), где Б —множество. Во множестве состояний выделен элемент d1 Е Б — начальное состояние. Т: Б ^ Б - отображение, называемое правилом перехода из

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

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

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

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

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

1. Канторович Л.В. Рациональный раскрой промышленных материалов. Изд. 3-е. СПб.: Невский диалект, 2012.

2. Романовский И.В. Перебор субоптимальных решений в задачах дискретной оптимизации. // Компьютерные инструменты в образовании. ЛЭТИ С.-Петербург, 2012. № 6. С. 25-34.

3. Беллман Р. Прикладные задачи динамического программирования. М.: Наука, 1965.

ПОВЫШЕНИЕ БЕЗОПАСНОСТИ ДОРОЖНОГО ДВИЖЕНИЯ НА ПЕШЕХОДНОМ ПЕРЕХОДЕ Шведова А.А.

Шведова Анастасия Анатольевна - магистрант, кафедра организации дорожного движения, Белорусский государственный университет транспорта, г. Гомель, Республика Беларусь

Аннотация: были проведены детальные обследования пешеходных переходов в наиболее оживленных участках улично-дорожной сети города Гомеля. На основании собранной информации, а также в результате анализа официальной статистики дорожно-транспортных происшествий на пешеходных переходах, были выявлены основные причины высокого уровня аварийности на обследуемых участках. Было предложено техническое решение, направленное на улучшение информативности пешеходных переходов, как основного критерия отвечающего за безопасность. Ключевые слова: пешеходный переход, безопасность дорожного движения, освещение.

УДК 331.225.3

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