Задача об оптимальном раскрое материалов (о минимизации отходов)

В строительном деле достаточно часто приходится решать проблему раскроя полуфабрикатов или минимизации отходов производства.

Постановка задачи. Из имеющихся заготовок в виде досок длиной D каждая требуется получить bi частей длиной Li (i =1, 2, …, m). Имеется несколько вариантов раскроя Vj (j =1, 2, …, n) каждой доски L (план раскроя). При каждом j- м варианте раскроя получается aij частей длиной lj. (При этом . Это условие, наложенное на коэффициенты, содержится в определении «вариант раскроя» и не является условием оптимизации). Требуется так распилить доски, чтобы было как можно меньше отходов, или требуемое количество частей должно быть получено из минимального количества заготовок.

В качестве независимых параметров выбираем x_j – количество досок (заготовок), распиленное по j -му варианту.

Оптимизацию будем проводить исходя из минималь-ного количества распиленных заготовок.

Математической модели задачи имеет вид: минимизировать целевую функцию

при ограничениях:

Задачи об оптимальном раскрое довольно разнообразны и в качестве примера рассмотрим еще один вариант такой задачи.

n Пример 6.7. При серийном производстве некоторого изделия из полос проката длиной 5000мм необходимо вырезать 3 вида заготовок. Номер, длина и количество заготовок:

№1 длина 1655мм, 1шт.

№2 длина 1050мм, 5шт.

№3 длина 210мм, 1шт.

Требуется составить оптимальный план раскроя, чтобы получить комплект заготовок для 12 изделий и израсходовать при этом минимальное количество полос.

Решение

Оптимизацию будем производить, исходя из минимальных отходов полос проката при их раскрое.

1. Составим таблицу - карту раскроя:

Таким образом, получилось четыре способа раскроя полос.

2. В качестве проектных параметров возьмем: x_i – количество прокатных полос, раскроенных i -способом.

3. Определим длину отходов при каждом способе раскроя.

4. В качестве функции цели примем суммарную длину отходов, которая должна быть минимальной:

Z_min = 35x₁ + 430x₂ + 195x₃ + 590x_4.

5. Запишем ограничения. Для 12 изделий необходимо заготовок:

№1 – 12 шт. №2 – 12 × 5 шт.; №3 – 12 шт.

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

Задача о планировании смен на предприятии

Полученная ММ задачи об оптимальном раскрое материалов (6.23) – (6.25) может быть использована также при решении задач о планировании смен на предприятии.

Только в этом случае содержательный смысл параметров будет другой, а именно:

V_j (j =1, 2, …, n) – возможные в течение дня смены;

L_i (i =1, 2, …, m) – определенное время дня;

а_ij = 1, если V_j предусматривает работу во время L_i, в противном случае а_ij = 0;

b_i – число работников, требующихся в момент времени L_i;

x_j – количество работников смены V_j.