Xj 0, xj – целые числа, j 1:n. (3.3)
Таким образом, математическая модель задачи о раскрое состоит в определении чисел xj, j 1:n, удовлетворяющих ограничениям (3.2) и (3.3), для которых функция (3.3) достигает наименьшего значения. Она относится к линейному целочисленному программированию, поскольку на все неизвестные наложены условия целочисленности. Если за критерий оптимальности принять минимум суммарной величины отходов при раскрое, то целевая функция заменится на
(3.4)
где сj
= L –
–
отходы от одной заготовки при способе
раскроя j.
Пример
Заготовки длиной L = 2 м необходимо раскроить на детали двух типов: длиной l1 = 0,6м в количестве 25 штук и длиной l2 = 0,9 м в количестве 19 шт. таким образом, чтобы было затрачено наименьшее число заготовок.
В табл. 3.1 укажем возможные способы раскроя заготовок, количество деталей 2-х типов, полученных от каждого реального способа раскроя, и потребности в этих деталях.
Таблица 3.1
Детали |
Способы раскроя |
Потребности |
||
длиной |
1 |
2 |
3 |
в деталях |
l1=0,6 l2=0,9 |
3 0 |
1 1 |
0 2 |
25 19 |
Обозначим через х1, х2, х3 – число заготовок, которое надо раскроить первым, вторым и третьим способами соответственно. Тогда общее число раскроенных заготовок равно
z = x1 + x2 + x3 min. (3.5)
Ограничения составляются из условий требуемого количества деталей каждого типа:
, (3.6)
x1, x2, x3 0, 1, 2, 3, ... (3.7)
Математическая модель (3.5)-(3.7) раскройной задачи относится к линейному целочисленному программированию. Оптимальное целочисленное решение: x1 = 8, x2 = 1, x3 = 9. Оптимальный план состоит в раскрое 8 заготовок первым способом, 1 заготовки вторым способом и 9 заготовок третьим способом; при этом будет затрачено минимальное число заготовок zmin = 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, что означает x1 = 8, x2 = 1, x3 = 9. Целевая функция в ячейке D1 примет значение 18, что соответствует 18 заготовкам.