Лекция: Задачи компоновки и алгоритмы их решения

Это построение сложного объекта из элементов более низкого уровня.

Дано: набор элементов (количество и размеры), критерии сравнения компоновочных решений.

А) Площадь (объем), занимаемый скомпонованной схемой. (мин)

Б) Суммарная длина всех связей между элементами (мин)

В) Экономические затраты (мин)

Ограничения:

1) Элементы не могут располагаться в одном месте пространства;

2) Связи не могут пересекаться;

3) Удобство обслуживания(около каждого элемента должна быть зона, свободная от других элементов);

4) Иногда необходимо предусмотреть минимально расстояние между связывающими линиями;

5) Элементы или связь не могут располагаться в некоторых, заранее определённых местах;

6) Заданная площадь (объём), на которой требуется скомпоновать схему.

Постановка задачи компоновки:

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

Алгоритмы решения задач компоновки:

1) Метод полного перебора;

2) Последовательный алгоритм: размещение элемента осуществляется с учётом размещения предыдущих, на первом этапе – ранжирование элементов по важности, на втором осуществляется размещение одного наиболее важного и т. д.

Достоинство – быстрота.

Недостатки – не всегда оптимально решение.

3) Параллельно последовательный алгоритм:

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

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

5) Эвристический алгоритм.