Задача 3. Задача об оптимальном линейном раскрое

Задача об оптимальном линейном раскрое

Теория

Предположим, что имеется большое (практически неограниченное) число одномерных заготовок одинаковой длины L. Это могут быть доски, бревна, трубы и т.п. Заготовки следует разрезать на детали m типов; длина детали типа i равна l_i, i Î 1: m. По данным числам L и l_i можно составить матрицу всевозможных способов раскроя A =(a_ij), где каждое a_ij указывает количество деталей типа i, получающееся из одной заготовки при раскрое ее по способу j, j Î 1: n. Таким образом, каждый способ раскроя j изображается столбцом матрицы А; он характеризуется набором целых чисел a_ij, подчиненных лишь условию которое означает, что суммарная длина выкраиваемых из заготовки деталей не превосходит длины заготовки. Пусть, кроме того, заданы потребности b_i, i Î 1: m, в деталях типа i. Требуется выполнить это плановое задание, раскроив минимальное число заготовок.

Составление математической модели начинается с выбора неизвестных величин. Пусть x_j – количество заготовок, подлежащее раскрою по способу j, j Î 1: n, z – общее число раскроенных заготовок. Тогда задача сводится к минимизации целевой функции

(3.1)

при условиях

(3.2)

x_j ³ 0, x_j – целые числа, j Î 1: n. (3.3)

Таким образом, математическая модель задачи о раскрое состоит в определении чисел x_j, j Î 1: n, удовлетворяющих ограничениям (3.2) и (3.3), для которых функция (3.3) достигает наименьшего значения. Она относится к линейному целочисленному программированию, поскольку на все неизвестные наложены условия целочисленности. Если за критерий оптимальности принять минимум суммарной величины отходов при раскрое, то целевая функция заменится на

(3.4)

где с_j = L – – отходы от одной заготовки при способе раскроя j.

Пример

Заготовки длиной L = 2 м необходимо раскроить на детали двух типов: длиной l ₁ = 0, 6м в количестве 25 штук и длиной l ₂ = 0, 9 м в количестве 19 шт. таким образом, чтобы было затрачено наименьшее число заготовок.

В табл. 3.1 укажем возможные способы раскроя заготовок, количество деталей 2-х типов, полученных от каждого реального способа раскроя, и потребности в этих деталях.

Таблица 3.1

Обозначим через х ₁, х ₂, х ₃ – число заготовок, которое надо раскроить первым, вторым и третьим способами соответственно. Тогда общее число раскроенных заготовок равно

z = x ₁ + x ₂ + x ₃ ® min. (3.5)

Ограничения составляются из условий требуемого количества деталей каждого типа:

, (3.6)

x ₁, x ₂, x ₃ ³ 0, 1, 2, 3,... (3.7)

Математическая модель (3.5)-(3.7) раскройной задачи относится к линейному целочисленному программированию. Оптимальное целочисленное решение: x ₁ = 8, x ₂ = 1, x ₃ = 9. Оптимальный план состоит в раскрое 8 заготовок первым способом, 1 заготовки вторым способом и 9 заготовок третьим способом; при этом будет затрачено минимальное число заготовок z _min = 18.

Решение задачи

Решим эту задачу на компьютере, воспользовавшись средством поиска решений Excel. Исходная таблица изображена на рис. 3.1.

Рис. 3.1

В ячейках таблицы А1: С1 записаны коэффициенты целевой функции (3.5), они все равны единице.

В ячейках А3: С4 записаны коэффициенты матрицы ограничений (3.6), в ячейках С3: С4 — правые части ограничений (3.6).

Вектор искомых неизвестных будет находится в ячейках А6: С6, в начальный момент они считаются равными нулю.

В ячейку D1 запишем формулу вычисления целевой функции =СУММПРОИЗВ(A1: C1; $A$6: $C$6).

В ячейки D6: D7 запишем формулы вычисления значения левой части системы ограничений:

=СУММПРОИЗВ(A3: C3; $A$6: $C$6)

=СУММПРОИЗВ(A4: C4; $A$6: $C$6)

Исходные данные введены, можно приступать к поиску решения. Выберем команду меню Сервис, Поиск решения. Откроется окно, в которое мы занесем условия задачи (рис. 3.2). Полезно нажать кнопку Параметры и поставить птичку у флажка Линейная модель.

Рис. 3.2

После ввода данных нажмем кнопку Выполнить, в ячейках А6: С6 появится решение: 8, 1, 9, что означает x₁ = 8, x₂ = 1, x₃ = 9. Целевая функция в ячейке D1 примет значение 18, что соответствует 18 заготовкам.

Варианты контрольных заданий

В таблице 3.2 приведены задания для 3 возможных деталей. Необходимо вручную на бумаге составить таблицу всех возможных способов раскроя заготовки на детали трех типов. При любом способе длина оставшегося куска должна быть меньше, чем длина любой детали (из него уже ничего вырезать нельзя). Потом заполнить таблицу Excel, подобную изображенной на рис. 3.1, и решить задачу.

Таблица 3.2.