Как решить задачу оптимизации загрузки фуры по весу и максимальной стоимости в 1С?

← На главную

Рассмотрим популярную оптимизационную задачу: имеется транспортное средство (фура) с фиксированной грузоподъемностью (например, 50 000 кг) и набор неделимых партий товаров, каждая из которых обладает определенным весом и общей стоимостью. Требуется выбрать такой набор партий, чтобы суммарный вес не превысил лимит грузоподъемности, а суммарная стоимость перевезенного груза была максимальной.

Часто разработчики пытаются решить эту задачу исключительно средствами языка запросов 1С с использованием техники «распределения интервалов» (нарастающих итогов). Выясним причину, почему такой подход приводит к ошибкам, и разберем корректные способы реализации задачи.

Анализ проблемы: почему метод «распределения в запросе» не дает нужного результата

Метод нарастающих итогов и соединение интервалов в запросе 1С отлично подходят для задач непрерывного списания (например, списание партий по ФИФО/ЛИФО или распределение суммы взаиморасчетов по документам). Однако в нашем случае мы сталкиваемся с фундаментальным различием:

Неделимость груза (дискретная задача о ранце 0-1): Партию нельзя загрузить частично. Метод распределения интервалами в запросе берет партии по порядку и «срезает» последнюю партию на величину оставшегося места в фуре, что нарушает условие целостности партий.
Некорректный критерий жадного алгоритма: Сортировка по абсолютной стоимости партии (Стоимость) ошибочна, так как дорогая партия может занимать почти всю грузоподъемность фуры, не оставляя места для более выгодных комбинаций. Даже сортировка по удельной стоимости (Стоимость / Вес) дает лишь приближенное (эвристическое) решение и не гарантирует точного максимума.
Ограничения языка запросов 1С: Язык запросов 1С не поддерживает рекурсивные выражения (CTE) и динамическое построение матриц решений, а перебор всех $2^N$ сочетаний через декартово произведение таблиц приводит к критическому падению производительности при росте числа партий.

Способ 1. Реализация алгоритма динамического программирования на встроенном языке

Классическим и наиболее эффективным методом решения задачи о ранце 0-1 является динамическое программирование. Алгоритм находит абсолютно точное оптимальное сочетание партий за полиномиальное время.

Разберем реализацию по шагам:

Нормализация исходных данных: Если грузоподъемность и веса партий кратны определенному числу (например, 1 000 кг), уменьшим размерность задачи, разделив все значения на общий делитель. Фура на 50 000 кг превращается в лимит 50 единиц.
Инициализация одномерного массива максимальных стоимостей: Создадим массив размером ЛимитВеса + 1, где индекс соответствует доступной вместимости.
Итеративный пересчет: В цикле по всем партиям обходим массив вместимостей в обратном порядке (сверху вниз до веса текущей партии), чтобы гарантировать учет каждой партии не более одного раза.
Восстановление оптимального состава: По завершении циклов восстанавливаем перечень партий, обеспечивших максимальную стоимость.

Посмотрим на пример программного кода:


// Входные данные по партиям
ТаблицаПартий = Новый ТаблицаЗначений;
ТаблицаПартий.Колонки.Добавить("Код", Новый ОписаниеТипов("Строка"));
ТаблицаПартий.Колонки.Добавить("Вес", Новый ОписаниеТипов("Число"));
ТаблицаПартий.Колонки.Добавить("Стоимость", Новый ОписаниеТипов("Число"));

// Заполняем таблицу исходными значениями (веса нормализованы / 1000)
Строка = ТаблицаПартий.Добавить(); Строка.Код = "101"; Строка.Вес = 10; Строка.Стоимость = 700000;
Строка = ТаблицаПартий.Добавить(); Строка.Код = "201"; Строка.Вес = 12; Строка.Стоимость = 540000;
Строка = ТаблицаПартий.Добавить(); Строка.Код = "301"; Строка.Вес = 14; Строка.Стоимость = 840000;
Строка = ТаблицаПартий.Добавить(); Строка.Код = "302"; Строка.Вес = 4;  Строка.Стоимость = 240000;
Строка = ТаблицаПартий.Добавить(); Строка.Код = "401"; Строка.Вес = 8;  Строка.Стоимость = 640000;
Строка = ТаблицаПартий.Добавить(); Строка.Код = "501"; Строка.Вес = 16; Строка.Стоимость = 880000;
Строка = ТаблицаПартий.Добавить(); Строка.Код = "601"; Строка.Вес = 24; Строка.Стоимость = 2160000;
Строка = ТаблицаПартий.Добавить(); Строка.Код = "602"; Строка.Вес = 11; Строка.Стоимость = 990000;
Строка = ТаблицаПартий.Добавить(); Строка.Код = "701"; Строка.Вес = 10; Строка.Стоимость = 400000;
Строка = ТаблицаПартий.Добавить(); Строка.Код = "801"; Строка.Вес = 18; Строка.Стоимость = 630000;

Грузоподъемность = 50; // 50 000 / 1000

// Инициализируем массив максимальных стоимостей и массив наборов
ТаблицаСтоимостей = Новый Массив;
ИсторияВыбора = Новый Массив;

Для Индекс = 0 По Грузоподъемность Цикл
    ТаблицаСтоимостей.Добавить(0);
    ИсторияВыбора.Добавить(Новый Массив);
КонецЦикла;

// Выполняем расчет
Для Каждого СтрПартия Из ТаблицаПартий Цикл
    ВесПартии = СтрПартия.Вес;
    СтоимостьПартии = СтрПартия.Стоимость;
    
    // Идем сверху вниз, чтобы использовать партию только 1 раз
    Для w = Грузоподъемность По ВесПартии Шаг -1 Цикл
        ПредыдущаяВместимость = w - ВесПартии;
        НоваяСтоимость = ТаблицаСтоимостей[ПредыдущаяВместимость] + СтоимостьПартии;
        
        Если НоваяСтоимость > ТаблицаСтоимостей[w] Тогда
            ТаблицаСтоимостей[w] = НоваяСтоимость;
            
            // Копируем историю формирования для новой вместимости
            НовыйНабор = Новый Массив;
            Для Каждого Элемент Из ИсторияВыбора[ПредыдущаяВместимость] Цикл
                НовыйНабор.Добавить(Элемент);
            КонецЦикла;
            НовыйНабор.Добавить(СтрПартия);
            
            ИсторияВыбора[w] = НовыйНабор;
        КонецЕсли;
    КонецЦикла;
КонецЦикла;

// Результат оптимизации
ОптимальныйНабор = ИсторияВыбора[Грузоподъемность];
ИтоговаяСтоимость = ТаблицаСтоимостей[Грузоподъемность];

В результате работы алгоритма мы получаем строго оптимальный набор партий: 101, 302, 601, 602 с суммарным весом 49 000 кг и максимальной стоимостью 4 090 000.

Способ 2. Рекурсивный перебор с отсечением ветвей (метод ветвей и границ)

Если веса партий не кратны и имеют высокую точность (например, дробные числа с плавающей точкой), размерность массива для динамического программирования может стать избыточной. В таких случаях эффективен рекурсивный алгоритм с отсечениями:

Предварительно упорядочиваем партии по убыванию удельной стоимости Стоимость / Вес.
Рекурсивно рассматриваем два варианта для каждой партии: включать ее в фуру или пропустить.
Вычисляем верхнюю теоретическую оценку оставшейся стоимости. Если даже при полной дозагрузке остатка самым дорогим удельным весом итоговая сумма не превысит уже найденный оптимум — немедленно прерываем обход данной ветви (отсечение).

Итоги

Попытка решить задачу дискретной оптимизации (рюкзака) одним запросом 1С концептуально некорректна из-за природы неделимости партий. Для получения гарантированно правильного результата следует извлекать исходные данные запросом, а сам расчет производить на встроенном языке с использованием динамического программирования.