Как проверить возможность выполнения заказа и распределить остатки по нескольким аналитикам?

В складском учете и логистике часто возникает задача резервирования и распределения остатков номенклатуры в разрезе нескольких аналитических измерений (например, Производитель, Завод-изготовитель, Склад, Серия). Сложность возникает в ситуации, когда строки заказа покупателя содержат требования разной степени строгости:

1. Строго заданы все аналитики (например: Производитель1 + Завод2 — 75 шт.).
2. Задана только часть аналитик (например: Производитель1, любой завод — 50 шт.).
3. Задана альтернативная аналитика (например: Завод1, любой производитель — 90 шт.).

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

Математическая природа задачи: максимальный поток в сети

Формально эта задача сводится к поиску максимального потока в транспортной сети (частный случай задачи линейного программирования). Построим двудольную сеть распределения:

1. Источники (первая доля графа): существующие комбинации фактических остатков на складе (например, вершины П1_З1, П1_З2, П2_З1, П2_З2). Пропускная способность дуг от фиктивного истока к этим вершинам равна доступному количеству товара в остатке.
2. Потребители (вторая доля графа): строки потребностей заказа (вершины З1, З2, З3...). Пропускная способность дуг от этих вершин к фиктивному стоку равна требуемому количеству по строке заказа.
3. Связующие дуги: проводятся от вершин остатков к вершинам потребностей только тогда, когда остаток удовлетворяет условию строки заказа. Пропускная способность таких дуг равна бесконечности.

Так как все значения пропускных способностей целочисленные, по теореме о целочисленности алгоритмы нахождения максимального потока гарантированно дают решение в целых числах без необходимости применения методов целочисленного линейного программирования (метода Гомори или ветвей и границ).

Если найденный максимальный поток равен суммарной потребности заказа, заказ гарантированно выполним. Если поток меньше, заказ выполнить нельзя. При этом минимальный разрез сети позволяет точно локализовать узкое место — группу ограничений, вызвавшую дефицит.

Алгоритм 1. Точный расчет методом нахождения максимального потока (Форд — Фалкерсон / Диниц)

Для гарантированного нахождения решения при произвольных пересечениях ограничений реализуем расчет остаточной сети. Рассмотрим по шагам логику построения графа во встроенном языке 1С:

1. Вычитаем из матрицы остатков строки с однозначным соответствием (где жестко зафиксированы и завод, и производитель).
2. Формируем список смежности графа с помощью коллекций Структура, Массив и Соответствие, обеспечивающих быстрый доступ к узлам по ключу ($O(1)$).
3. Запускаем поиск увеличивающих путей в остаточной сети (алгоритм Эдмондса — Карпа через поиск в ширину или алгоритм Диница).
4. Если суммарный найденный поток покрыл всю потребность, фиксируем распределение.

Посмотрим на пример структуры хранения графа и построения матрицы распределения:

// Подготовка структур данных графа
ГрафСети = Новый Соответствие;

// Заполнение ребер от истока к остаткам
Для Каждого СтрОстатка Из ТаблицаОстатков Цикл
    КлючИсточника = "SRC_" + СтрОстатка.Производитель + "_" + СтрОстатка.Завод;
    ГрафСети.Вставить(КлючИсточника, Новый Структура("Остаток, Ребра", СтрОстатка.Количество, Новый Массив));
КонецЦикла;

// Добавление допустимых связей к строкам заказа
Для Каждого СтрЗаказа Из ТаблицаЗаказа Цикл
    КлючПотребителя = "DST_" + СтрЗаказа.НомерСтроки;
    Для Каждого КлючИЗначение Из ГрафСети Цикл
        // Проверяем соответствие условиям строки заказа
        Если СоответствуетУсловию(КлючИЗначение.Ключ, СтрЗаказа) Тогда
            КлючИЗначение.Значение.Ребра.Добавить(КлючПотребителя);
        КонецЕсли;
    КонецЦикла;
КонецЦикла;

Алгоритм 2. Практическая многопроходная каскадная эвристика

В учетных задачах на 1С, где число измерений невелико (2–3 аналитики), часто применяется быстрый каскадный жадный алгоритм, выполняемый за линейное время:

1. Шаг 1. Жесткое сопоставление. Списываем строки, в которых однозначно задана конкретная пара (Производитель + Завод). Уменьшаем доступные остатки.
2. Шаг 2. Расчет дефицитности ресурсов. Для оставшихся строк подсчитываем свободный пул остатков по каждому производителю и каждому заводу. Сортируем потребности по возрастанию доступных альтернатив (обратная сортировка по коэффициенту покрытия).
3. Шаг 3. Списание ограниченных партий. Потребности с частичной неопределенностью («любой завод») покрываем в первую очередь из тех партий, которые наименее востребованы другими строками заказа (например, с заводов, не фигурирующих в других позициях заказа).
4. Шаг 4. Финальное списание. Оставшиеся свободные остатки распределяем на строки с полностью свободными условиями.

Разберем по шагам реализацию предварительного списания жестких условий и контроля остатков:

// Шаг 1: Прямое списание жестко заданных аналитик
Для Каждого СтрЗаказа Из ТаблицаЗаказовЖесткие Цикл
    ОтборОстатка = Новый Структура("Производитель, Завод", СтрЗаказа.Производитель, СтрЗаказа.Завод);
    НайденныеОстатки = ТаблицаОстатков.НайтиСтроки(ОтборОстатка);
    
    Если НайденныеОстатки.Количество() > 0 Тогда
        СтрокаОстатка = НайденныеОстатки[0];
        Если СтрокаОстатка.Количество >= СтрЗаказа.Количество Тогда
            СтрокаОстатка.Количество = СтрокаОстатка.Количество - СтрЗаказа.Количество;
            СтрЗаказа.Количество = 0;
        Иначе
            // Недостаточно точного остатка
            ВызватьИсключение "Недостаточно остатка по точной аналитике!";
        КонецЕсли;
    КонецЕсли;
КонецЦикла;

Рекомендации по оптимизации и архитектуре в 1С

1. Вынос логики на сервер: расчет распределения графа является вычислительно емким. Его необходимо реализовывать в серверных неконтекстных процедурах модулей менеджеров или общих модулей без использования клиентских коллекций.
2. Транзакционная безопасность: не выполняйте сложный подбор графа внутри транзакции проведения документа. Рассчитывайте распределение перед записью или используйте фоновые задания (объект ФоновыеЗадания), чтобы не вызывать длительных блокировок таблиц регистров остатков.
3. Критерии оптимизации (FEFO / минимизация паллет): если помимо факта выполнимости требуется подобрать партии по сроку годности или минимальному дроблению упаковок, задача расширяется до потока минимальной стоимости (Min-Cost Max-Flow), где ребрам графа присваиваются веса (стоимости), соответствующие датам серий или штрафам за дробление тарного места.