Решение задачи раскроя арматуры

Из рабочей документации на фундамент извлекаем данные по длине отрезков арматуры (деталей) и их количестве

parts = ([8160]*42+[3960]*84+[3145]*165+[2855]*126)*2+([2965]*16+[2665]*20+[2005]*4+[1990]*12+[3530]*6)*7+ \
([2365]*28+[1990]*12+[1995]*4+[3530]*6)*11
parts.sort(reverse=True)  # Сортируем по уменьшению длины
len(parts)  # Количество деталей

1790

Создаём список длин деталей и сортируем его по убыванию

parts_uniq = list(set(parts))
parts_uniq.sort(reverse=True)  # Сортируем по уменьшению длины
parts_uniq

[8160, 3960, 3530, 3145, 2965, 2855, 2665, 2365, 2005, 1995, 1990]

Формируем спецификацию деталей (длина отрезка - количество отрезков)

from collections import Counter
counts = dict(Counter(parts))
counts

{8160: 84,
 3960: 168,
 3530: 108,
 3145: 330,
 2965: 112,
 2855: 252,
 2665: 140,
 2365: 308,
 2005: 28,
 1995: 44,
 1990: 216}

# Поставочная длина прута арматуры
rodLength = 11700  # мм

Алгоритм одномерной упаковки Best-Fit Decreasing с использованием классов

# Класс Прут
class Rod:
    def __init__(self, length):
        self.parts = []  # список отрезков, сделанных из данного прута
        self.residue = length  # остаток
    
    def add_part(self, part):  # отрезание от прута отрезка
        self.parts.append(part)
        self.residue -= part

rods = [Rod(rodLength)]
for part in parts:
    best_rod = None
    min_residue = rodLength + 1
    
    for rod in rods:
        if rod.residue >= part and rod.residue < min_residue:
            min_residue = rod.residue
            best_rod = rod
    
    if best_rod:
        best_rod.add_part(part)
    else:
        new_rod = Rod(rodLength)
        new_rod.add_part(part)
        rods.append(new_rod)

# Требуемое количество прутов арматуры 11,7 м 
len(rods)

486

# Класс схемы раскроя
class Scheme:
    def __init__(self, parts, residue, count):
        self.parts = parts  # список отрезков
        self.residue = residue  # остаток
        self.count = count  # сколько раз применить

# Набор схем раскроя
schemes = []
schemes.append(Scheme(rods[0].parts, rods[0].residue, 1))
for rod in rods[1:]:
    newScheme = True
    for scheme in schemes:
        if rod.parts == scheme.parts:
            scheme.count += 1
            newScheme = False
            break
    if newScheme:
        schemes.append(Scheme(rod.parts, rod.residue, 1))

# Сортируем схемы раскроя 1) по убыванию частоты применения, 2) по убыванию количества деталей в схеме
schemes.sort(key=lambda x: (-x.count, -len(x.parts)))
[(scheme.parts,  scheme.residue, scheme.count) for scheme in schemes]

[([3145, 3145, 3145, 1990], 275, 90),
 ([8160, 3530], 10, 84),
 ([2855, 2855, 2855, 2855], 280, 62),
 ([3960, 3960, 3145], 635, 60),
 ([2365, 2365, 2365, 2365, 1995], 245, 44),
 ([2965, 2965, 2965, 2665], 140, 37),
 ([2365, 2365, 2365, 2365, 2005], 235, 28),
 ([2665, 2665, 2665, 2665], 1040, 25),
 ([1990, 1990, 1990, 1990, 1990], 1750, 24),
 ([3960, 3960, 3530], 250, 24),
 ([2365, 2365, 2365, 2365, 1990], 250, 5),
 ([2965, 2855, 2855, 2855], 170, 1),
 ([2855, 2665, 2665, 2665], 850, 1),
 ([1990], 9710, 1)]

Формируем данные для csv файла для отображения набора схем раскроя в табличном виде.

result = "; ".join([str(x) for x in parts_uniq]) + '; Остаток' + '; Количество'
print('N; ' + result)
for i, scheme in enumerate(schemes):
    print(i+1, end='')
    for part in parts_uniq:
        print(';', scheme.parts.count(part), end='')
    print(';', scheme.residue, ';', scheme.count)

N; 8160; 3960; 3530; 3145; 2965; 2855; 2665; 2365; 2005; 1995; 1990; Остаток; Количество
1; 0; 0; 0; 3; 0; 0; 0; 0; 0; 0; 1; 275 ; 90
2; 1; 0; 1; 0; 0; 0; 0; 0; 0; 0; 0; 10 ; 84
3; 0; 0; 0; 0; 0; 4; 0; 0; 0; 0; 0; 280 ; 62
4; 0; 2; 0; 1; 0; 0; 0; 0; 0; 0; 0; 635 ; 60
5; 0; 0; 0; 0; 0; 0; 0; 4; 0; 1; 0; 245 ; 44
6; 0; 0; 0; 0; 3; 0; 1; 0; 0; 0; 0; 140 ; 37
7; 0; 0; 0; 0; 0; 0; 0; 4; 1; 0; 0; 235 ; 28
8; 0; 0; 0; 0; 0; 0; 4; 0; 0; 0; 0; 1040 ; 25
9; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 5; 1750 ; 24
10; 0; 2; 1; 0; 0; 0; 0; 0; 0; 0; 0; 250 ; 24
11; 0; 0; 0; 0; 0; 0; 0; 4; 0; 0; 1; 250 ; 5
12; 0; 0; 0; 0; 1; 3; 0; 0; 0; 0; 0; 170 ; 1
13; 0; 0; 0; 0; 0; 1; 3; 0; 0; 0; 0; 850 ; 1
14; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 1; 9710 ; 1

Программа для решения задачи раскроя

from ortools.linear_solver import pywraplp
import math

def generate_patterns(stock_length, part_lengths):
    """Генерирует допустимые шаблоны раскроя с помощью динамического программирования"""
    patterns = []
    max_counts = [stock_length // length for length in part_lengths]
    
    # Рекурсивная генерация шаблонов
    def generate_recursive(idx, current_pattern, current_length):
        if idx == len(part_lengths):
            patterns.append(current_pattern[:])
            return
        
        max_count = min(max_counts[idx], (stock_length - current_length) // part_lengths[idx])
        for count in range(max_count + 1):
            new_length = current_length + count * part_lengths[idx]
            if new_length <= stock_length:
                current_pattern[idx] = count
                generate_recursive(idx + 1, current_pattern, new_length)
            current_pattern[idx] = 0  # Reset
    
    generate_recursive(0, [0] * len(part_lengths), 0)
    return patterns

def solve_cutting_stock(stock_length, part_types):
    # Преобразуем данные в списки
    part_lengths = list(part_types.keys())
    demands = [part_types[length] for length in part_lengths]
    n_types = len(part_lengths)
    
    # 1. Генерируем все возможные шаблоны раскроя
    patterns = generate_patterns(stock_length, part_lengths)
    print(f"Сгенерировано шаблонов раскроя: {len(patterns)}")
    
    # 2. Создаем решатель
    solver = pywraplp.Solver.CreateSolver('SCIP')
    
    # 3. Создаем переменные: сколько раз использовать каждый шаблон
    x = [solver.IntVar(0, sum(demands), f'x_{i}') for i in range(len(patterns))]
    
    # 4. Ограничения: удовлетворить спрос по всем типам деталей
    constraints = []
    for j in range(n_types):
        constraint = solver.RowConstraint(demands[j], demands[j], f'demand_{j}')
        for i, pattern in enumerate(patterns):
            constraint.SetCoefficient(x[i], pattern[j])
    
    # 5. Цель: минимизировать количество использованных прутьев
    objective = solver.Objective()
    for i in range(len(patterns)):
        objective.SetCoefficient(x[i], 1)
    objective.SetMinimization()
    
    # 6. Решаем задачу
    status = solver.Solve()
    
    # 7. Обработка результатов
    if status == pywraplp.Solver.OPTIMAL:
        solution = []
        total_stocks = 0
        
        # Собираем решение
        for i, var in enumerate(x):
            count = int(var.solution_value() + 0.5)  # Округление для целочисленных значений
            if count > 0:
                total_stocks += count
                pattern_info = []
                for j, length in enumerate(part_lengths):
                    if patterns[i][j] > 0:
                        pattern_info.append(f"{patterns[i][j]}x{length}мм")
                solution.append({
                    'pattern': pattern_info,
                    'count': count,
                    'waste': stock_length - sum(patterns[i][j] * part_lengths[j] for j in range(n_types))
                })
        
        # Рассчитываем эффективность
        total_waste = sum(item['waste'] * item['count'] for item in solution)
        total_length = sum(length * count for length, count in part_types.items())
        efficiency = (1 - total_waste / (total_stocks * stock_length)) * 100
        
        return {
            'status': 'OPTIMAL',
            'total_stocks': total_stocks,
            'total_waste': total_waste,
            'efficiency': efficiency,
            'solution': solution
        }
    else:
        return {'status': 'NOT_SOLVED', 'message': 'Оптимальное решение не найдено'}

# Ваши данные
rod_length = 11700  # мм
part_types = {
    8160: 42*2,
    3960: 84*2,
    3145: 165*2,
    2855: 126*2,
    2965: 16*7,
    2665: 20*7,
    2005: 4*7,
    1990: 12*7 + 12*11,
    3530: 6*7 + 6*11,
    2365: 28*11,
    1995: 4*11
}

# Решаем задачу
result = solve_cutting_stock(rod_length, part_types)

# Выводим результаты
print("\nРезультаты раскроя:")
print(f"Статус решения: {result['status']}")
if result['status'] == 'OPTIMAL':
    print(f"Минимальное количество прутьев: {result['total_stocks']}")
    print(f"Общие отходы: {result['total_waste']} мм")
    print(f"Эффективность раскроя: {result['efficiency']:.2f}%")
    
    print("\nОптимальные шаблоны раскроя:")
    for i, item in enumerate(result['solution']):
        print(f"Шаблон {i+1}:")
        print(f"  - Используется {item['count']} раз")
        print(f"  - Детали: {', '.join(item['pattern'])}")
        print(f"  - Отходы на прут: {item['waste']} мм")
        print(f"  - Общие отходы: {item['waste'] * item['count']} мм")
        print()
    
    # Проверяем покрытие спроса
    demand_fulfilled = {length: 0 for length in part_types}
    for item in result['solution']:
        for part_str in item['pattern']:
            count, length = part_str.split('x')
            length = int(length.replace('мм', ''))
            demand_fulfilled[length] += int(count) * item['count']
    
    print("\nПроверка покрытия спроса:")
    for length, demand in part_types.items():
        fulfilled = demand_fulfilled[length]
        status = "OK" if fulfilled == demand else "ОШИБКА"
        print(f"Детали {length}мм: {fulfilled}/{demand} ({status})")

Сгенерировано шаблонов раскроя: 1015

Результаты раскроя:
Статус решения: OPTIMAL
Минимальное количество прутьев: 474
Общие отходы: 49170 мм
Эффективность раскроя: 99.11%

Оптимальные шаблоны раскроя:
Шаблон 1:
  - Используется 64 раз
  - Детали: 2x2665мм, 2x1990мм, 1x2365мм
  - Отходы на прут: 25 мм
  - Общие отходы: 1600 мм

Шаблон 2:
  - Используется 1 раз
  - Детали: 1x2855мм
  - Отходы на прут: 8845 мм
  - Общие отходы: 8845 мм

Шаблон 3:
  - Используется 2 раз
  - Детали: 1x2855мм, 2x2005мм, 2x2365мм
  - Отходы на прут: 105 мм
  - Общие отходы: 210 мм

Шаблон 4:
  - Используется 1 раз
  - Детали: 1x2855мм, 1x2965мм, 1x3530мм
  - Отходы на прут: 2350 мм
  - Общие отходы: 2350 мм

Шаблон 5:
  - Используется 23 раз
  - Детали: 1x3145мм, 1x2965мм, 1x2005мм, 1x3530мм
  - Отходы на прут: 55 мм
  - Общие отходы: 1265 мм

Шаблон 6:
  - Используется 15 раз
  - Детали: 2x3145мм, 1x2965мм, 1x2365мм
  - Отходы на прут: 80 мм
  - Общие отходы: 1200 мм

Шаблон 7:
  - Используется 72 раз
  - Детали: 2x3145мм, 1x2855мм, 1x2365мм
  - Отходы на прут: 190 мм
  - Общие отходы: 13680 мм

Шаблон 8:
  - Используется 44 раз
  - Детали: 3x3145мм, 1x1995мм
  - Отходы на прут: 270 мм
  - Общие отходы: 11880 мм

Шаблон 9:
  - Используется 6 раз
  - Детали: 1x3960мм, 2x2665мм, 1x2365мм
  - Отходы на прут: 45 мм
  - Общие отходы: 270 мм

Шаблон 10:
  - Используется 73 раз
  - Детали: 1x3960мм, 1x2965мм, 2x2365мм
  - Отходы на прут: 45 мм
  - Общие отходы: 3285 мм

Шаблон 11:
  - Используется 88 раз
  - Детали: 1x3960мм, 2x2855мм, 1x1990мм
  - Отходы на прут: 40 мм
  - Общие отходы: 3520 мм

Шаблон 12:
  - Используется 1 раз
  - Детали: 1x3960мм, 1x3145мм, 1x2005мм, 1x2365мм
  - Отходы на прут: 225 мм
  - Общие отходы: 225 мм

Шаблон 13:
  - Используется 84 раз
  - Детали: 1x8160мм, 1x3530мм
  - Отходы на прут: 10 мм
  - Общие отходы: 840 мм


Проверка покрытия спроса:
Детали 8160мм: 84/84 (OK)
Детали 3960мм: 168/168 (OK)
Детали 3145мм: 330/330 (OK)
Детали 2855мм: 252/252 (OK)
Детали 2965мм: 112/112 (OK)
Детали 2665мм: 140/140 (OK)
Детали 2005мм: 28/28 (OK)
Детали 1990мм: 216/216 (OK)
Детали 3530мм: 108/108 (OK)
Детали 2365мм: 308/308 (OK)
Детали 1995мм: 44/44 (OK)

# Результат работы программы
result['solution']

[{'pattern': ['2x2665мм', '2x1990мм', '1x2365мм'], 'count': 64, 'waste': 25},
 {'pattern': ['1x2855мм'], 'count': 1, 'waste': 8845},
 {'pattern': ['1x2855мм', '2x2005мм', '2x2365мм'], 'count': 2, 'waste': 105},
 {'pattern': ['1x2855мм', '1x2965мм', '1x3530мм'], 'count': 1, 'waste': 2350},
 {'pattern': ['1x3145мм', '1x2965мм', '1x2005мм', '1x3530мм'],
  'count': 23,
  'waste': 55},
 {'pattern': ['2x3145мм', '1x2965мм', '1x2365мм'], 'count': 15, 'waste': 80},
 {'pattern': ['2x3145мм', '1x2855мм', '1x2365мм'], 'count': 72, 'waste': 190},
 {'pattern': ['3x3145мм', '1x1995мм'], 'count': 44, 'waste': 270},
 {'pattern': ['1x3960мм', '2x2665мм', '1x2365мм'], 'count': 6, 'waste': 45},
 {'pattern': ['1x3960мм', '1x2965мм', '2x2365мм'], 'count': 73, 'waste': 45},
 {'pattern': ['1x3960мм', '2x2855мм', '1x1990мм'], 'count': 88, 'waste': 40},
 {'pattern': ['1x3960мм', '1x3145мм', '1x2005мм', '1x2365мм'],
  'count': 1,
  'waste': 225},
 {'pattern': ['1x8160мм', '1x3530мм'], 'count': 84, 'waste': 10}]

Переведём возвращаемый результат в список схем раскроя

schemes =[]
for elem in result['solution']:
    original_list = elem['pattern']
    numbers_list = []
    for item in original_list:
        count, rest = item.split('x')  # Разделяем по 'x'
        num = int(rest.replace('мм', ''))  # Удаляем 'мм' и преобразуем в число
        numbers_list.extend([num] * int(count))  # Добавляем число `count` раз
    schemes.append(Scheme(numbers_list, elem['waste'], elem['count']))

[scheme.parts for scheme in schemes]

[[2665, 2665, 1990, 1990, 2365],
 [2855],
 [2855, 2005, 2005, 2365, 2365],
 [2855, 2965, 3530],
 [3145, 2965, 2005, 3530],
 [3145, 3145, 2965, 2365],
 [3145, 3145, 2855, 2365],
 [3145, 3145, 3145, 1995],
 [3960, 2665, 2665, 2365],
 [3960, 2965, 2365, 2365],
 [3960, 2855, 2855, 1990],
 [3960, 3145, 2005, 2365],
 [8160, 3530]]

Отсортируем схемы по частоте применения

schemes.sort(key=lambda x: (-x.count, -len(x.parts)))
[(scheme.parts,  scheme.residue, scheme.count) for scheme in schemes]

[([3960, 2855, 2855, 1990], 40, 88),
 ([8160, 3530], 10, 84),
 ([3960, 2965, 2365, 2365], 45, 73),
 ([3145, 3145, 2855, 2365], 190, 72),
 ([2665, 2665, 1990, 1990, 2365], 25, 64),
 ([3145, 3145, 3145, 1995], 270, 44),
 ([3145, 2965, 2005, 3530], 55, 23),
 ([3145, 3145, 2965, 2365], 80, 15),
 ([3960, 2665, 2665, 2365], 45, 6),
 ([2855, 2005, 2005, 2365, 2365], 105, 2),
 ([3960, 3145, 2005, 2365], 225, 1),
 ([2855, 2965, 3530], 2350, 1),
 ([2855], 8845, 1)]

Формируем данные для csv файла для отображения набора схем раскроя в табличном виде.

result = "; ".join([str(x) for x in parts_uniq]) + '; Остаток' + '; Количество'
print('N; ' + result)
for i, scheme in enumerate(schemes):
    print(i+1, end='')
    for part in parts_uniq:
        print(';', scheme.parts.count(part), end='')
    print(';', scheme.residue, ';', scheme.count)

N; 8160; 3960; 3530; 3145; 2965; 2855; 2665; 2365; 2005; 1995; 1990; Остаток; Количество
1; 0; 1; 0; 0; 0; 2; 0; 0; 0; 0; 1; 40 ; 88
2; 1; 0; 1; 0; 0; 0; 0; 0; 0; 0; 0; 10 ; 84
3; 0; 1; 0; 0; 1; 0; 0; 2; 0; 0; 0; 45 ; 73
4; 0; 0; 0; 2; 0; 1; 0; 1; 0; 0; 0; 190 ; 72
5; 0; 0; 0; 0; 0; 0; 2; 1; 0; 0; 2; 25 ; 64
6; 0; 0; 0; 3; 0; 0; 0; 0; 0; 1; 0; 270 ; 44
7; 0; 0; 1; 1; 1; 0; 0; 0; 1; 0; 0; 55 ; 23
8; 0; 0; 0; 2; 1; 0; 0; 1; 0; 0; 0; 80 ; 15
9; 0; 1; 0; 0; 0; 0; 2; 1; 0; 0; 0; 45 ; 6
10; 0; 0; 0; 0; 0; 1; 0; 2; 2; 0; 0; 105 ; 2
11; 0; 1; 0; 1; 0; 0; 0; 1; 1; 0; 0; 225 ; 1
12; 0; 0; 1; 0; 1; 1; 0; 0; 0; 0; 0; 2350 ; 1
13; 0; 0; 0; 0; 0; 1; 0; 0; 0; 0; 0; 8845 ; 1

Инженерные расчёты на Python, С.В. Медведев, 2020-2025
Использование Python и Jupyter Notebook для инженерных расчётов, С.В. Медведев, 2020-2025