Задача о раскрое. Постановка, модель, пример

53. Задача о раскрое. Постановка, модель, пример.

1.  Постановка

На раскрой поступает L видов материалов, причем известно, что каждого вида материала a_j (), каждую единицу можно раскроить p способами и можно произвести k – видов изделий, которые производятся комплектами, причем известны коэффициенты комплектности b_i, которые показывают сколько изделий этого вида входит в комплект.  - сколько единиц i-го вида изделия можно раскроить k-ым способом из одной единицы j-го вида материала. Определить план раскроя поступающих материалов, при котором выпускается максимальное количество продукции.

i = 1,k – вид изделия

{}_p´l – число единиц j-го вида материала, раскроенного m-тым способом

у – число комплектов

2.  Модель

(l+k)´(p×l+1) – размерность

Пример: На распил поступают бревна 4-х метровой длины. Из этих бревен нужно распилить брусья длиной 0.6, 1.5, 2.5. В один комплект входят бревна длины 2 = b₁, 1=b₂, 3=b₃.Определить оптимальный план распила.

l=1, , a_j=a=100%, i=1, k=3 – видов кусков