Задача нескольких рюкзаков

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

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

Подобная задача встречается в самых разных бизнес-сценариях, где требуется оптимально распределить ограниченные ресурсы по нескольким вместилищам или каналам. Примеры:

• Логистика — распределение заказов по автомобилям с разной грузоподъёмностью;
• Складская деятельность — размещение товаров по складам с разными зонами хранения;
• Производство — распределение партий продукции по линиям с ограниченной загрузкой;
• Проектное управление — распределение задач или оборудования по командам с разным доступным временем или ресурсами.

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

Постановка задачи

Нужно разместить набор предметов в нескольких рюкзаках, при этом:

• каждый предмет имеет свой вес и ценность;
• у каждого рюкзака — своя вместимость;
• предмет можно положить не более чем в один рюкзак;
• допускается размещение не всех предметов;
• суммарный вес в каждом рюкзаке не должен превышать его вместимость;
• суммарная ценность размещенных в рюкзаках предметов должна быть максимальной.

Решение задачи

1. Выбор модели

Для решения задачи используем линейную целочисленную модель. Причины выбора:

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

2. Создание модели

Через менеджер моделей библиотеки О₂ создаём объект модели, в котором будут храниться переменные, ограничения и целевая функция.

// Создаем объект линейной модели
Модель = О2
    .Модели()
    .ЛинейнаяЦелочисленнаяМодель()
    .СоздатьМодель();

3. Ввод данных

В качестве входных данных задаём:

• массив весов предметов;
• массив ценностей предметов;
• массив вместимостей рюкзаков.

Данные преобразуем в числовой формат с помощью функции МассивЧиселИзСтроки.

// Вводим данные 
Веса 		= О2.Утилиты().МассивЧиселИзСтроки("48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36");
Ценности 	= О2.Утилиты().МассивЧиселИзСтроки("10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25");	
Вместимости = О2.Утилиты().МассивЧиселИзСтроки("100, 90, 65, 95, 75");

КоличествоПредметов = Веса.Количество();
КоличествоРюкзаков 	= Вместимости.Количество();

4. Регистрация переменных

Для каждой пары (предмет, рюкзак) зарегистрируем булеву переменную, значение которой отражает:

• 1 — предмет помещен в этот рюкзак;
• 0 — предмет в этот рюкзак не помещён.

Созданные переменные сохраним в двумерном массиве.

// Добавляем булевы переменные по одной на каждую комбинацию (Предмет, Рюкзак)
// Переменная будет принимать значение ИСТИНА, если предмет находится в указанном рюкзаке
ПредметыРюкзаков = Новый Массив(КоличествоПредметов, КоличествоРюкзаков);
Для Предмет = 0 По КоличествоПредметов - 1 Цикл
    Для Рюкзак = 0 По КоличествоРюкзаков - 1 Цикл 
        ПредметыРюкзаков[Предмет][Рюкзак] = Модель.БулеваПеременная();
    КонецЦикла;
КонецЦикла;

5. Установка ограничений

Установим следующие ограничения:

Один предмет — не более чем в одном рюкзаке

Суммируем все булевы переменные для предмета и требуем, чтобы сумма была ≤ 1.

// Устанавливаем ограничение: предмет может находить не более чем в одном рюкзаке
Для Предмет = 0 По КоличествоПредметов - 1 Цикл
    КоличествоРазмещений = Модель.Выражения().Сумма(ПредметыРюкзаков[Предмет]);
    Модель.Ограничения().ЗначениеМеньшеИлиРавно(КоличествоРазмещений, 1);
КонецЦикла;

Ограничение по вместимости каждого рюкзака

Суммируем веса предметов, помещённых в рюкзак, и сравниваем с его вместимостью.

// Устанавливаем ограничение: вес каждого рюкзака не превышает его вместимость
ВесаРюкзаков    = Новый Массив(КоличествоРюкзаков);
ВесРюкзака      = Модель.Выражения().СоздатьПостроительВыражений();

Для Рюкзак = 0 По КоличествоРюкзаков - 1 Цикл
    ВесРюкзака.Очистить();
    
    Для Предмет = 0 По КоличествоПредметов - 1 Цикл
        Вес 				= Веса[Предмет];
        ПризнакРазмещения 	= ПредметыРюкзаков[Предмет][Рюкзак];
        
        ВесРюкзака.ДобавитьТерм(ПризнакРазмещения, Вес);
    КонецЦикла;
    
    ВесаРюкзаков[Рюкзак] 	= ВесРюкзака.ПолучитьВыражение(); 
    Вместимость 			= Вместимости[Рюкзак]; 
    
    Модель.Ограничения().ЗначениеМеньшеИлиРавно(ВесаРюкзаков[Рюкзак], Вместимость);
КонецЦикла;

Здесь линейные выражения для веса каждого рюкзака сохраняются в отдельный массив. Эти выражения мы вычислим позднее при выводе результатов.

6. Установка целевой функции

Цель — максимизировать суммарную ценность всех размещённых предметов.

Формируем в цикле линейное выражение для целевой функции: для каждой пары (предмет, рюкзак) добавляем слагаемое Ценность × ПризнакРазмещения.

// Установка целевой функции (максимизация ценности размещенных предметов)
СуммарнаяЦенность = Модель.Выражения().СоздатьПостроительВыражений();

Для Предмет = 0 По КоличествоПредметов - 1 Цикл
    Для Рюкзак = 0 По КоличествоРюкзаков - 1 Цикл
        Ценность            = Ценности[Предмет];
        ПризнакРазмещения   = ПредметыРюкзаков[Предмет][Рюкзак];
        
        СуммарнаяЦенность.ДобавитьТерм(ПризнакРазмещения, Ценность);
    КонецЦикла;
КонецЦикла;

Модель.Максимизировать(СуммарнаяЦенность.ПолучитьВыражение());

7. Решение модели

Выполняем поиск оптимального решения.

// Решаем модель
Решение = Модель.Решить();

8. Вывод результатов

Если решение найдено:

• выводим статус;
• по каждому рюкзаку — список предметов, их вес и ценность;
• показываем суммарный вес и суммарную ценность.

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

Полный код решения задачи

Ниже представлен полный код решения. Вы также можете скачать пример в виде готовой обработки.

// Создаем объект линейной модели
Модель = О2
    .Модели()
    .ЛинейнаяЦелочисленнаяМодель()
    .СоздатьМодель();  

// Вводим данные   
Веса 		= О2.Утилиты().МассивЧиселИзСтроки("48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36");
Ценности 	= О2.Утилиты().МассивЧиселИзСтроки("10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25");	
Вместимости = О2.Утилиты().МассивЧиселИзСтроки("100, 90, 65, 95, 75");

КоличествоПредметов = Веса.Количество();
КоличествоРюкзаков 	= Вместимости.Количество();  

// Добавляем булевы переменные по одной на каждую комбинацию (Предмет, Рюкзак)
// Переменная будет принимать значение ИСТИНА, если предмет находится в указанном рюкзаке
ПредметыРюкзаков = Новый Массив(КоличествоПредметов, КоличествоРюкзаков);
Для Предмет = 0 По КоличествоПредметов - 1 Цикл
    Для Рюкзак = 0 По КоличествоРюкзаков - 1 Цикл 
        ПредметыРюкзаков[Предмет][Рюкзак] = Модель.БулеваПеременная();
    КонецЦикла;
КонецЦикла; 

// Устанавливаем ограничение: предмет может находить не более чем в одном рюкзаке
Для Предмет = 0 По КоличествоПредметов - 1 Цикл
    КоличествоРазмещений = Модель.Выражения().Сумма(ПредметыРюкзаков[Предмет]);
    Модель.Ограничения().ЗначениеМеньшеИлиРавно(КоличествоРазмещений, 1);
КонецЦикла;

// Устанавливаем ограничение: вес каждого рюкзака не превышает его вместимость
ВесаРюкзаков    = Новый Массив(КоличествоРюкзаков);
ВесРюкзака      = Модель.Выражения().СоздатьПостроительВыражений();

Для Рюкзак = 0 По КоличествоРюкзаков - 1 Цикл
    ВесРюкзака.Очистить();
    
    Для Предмет = 0 По КоличествоПредметов - 1 Цикл
        Вес 			= Веса[Предмет];
        ПредметПомещен 	= ПредметыРюкзаков[Предмет][Рюкзак];
        
        ВесРюкзака.ДобавитьТерм(ПредметПомещен, Вес);
    КонецЦикла;
    
    ВесаРюкзаков[Рюкзак] 	= ВесРюкзака.ПолучитьВыражение(); 
    Вместимость 			= Вместимости[Рюкзак]; 
    
    Модель.Ограничения().ЗначениеМеньшеИлиРавно(ВесаРюкзаков[Рюкзак], Вместимость);
КонецЦикла;


// Установка целевой функции (максимизация ценности размещенных предметов)
СуммарнаяЦенность = Модель.Выражения().СоздатьПостроительВыражений();

Для Предмет = 0 По КоличествоПредметов - 1 Цикл
    Для Рюкзак = 0 По КоличествоРюкзаков - 1 Цикл
        Ценность 		= Ценности[Предмет];
        ПредметПомещен 	= ПредметыРюкзаков[Предмет][Рюкзак];
        
        СуммарнаяЦенность.ДобавитьТерм(ПредметПомещен, Ценность);
    КонецЦикла;
КонецЦикла;

Модель.Максимизировать(СуммарнаяЦенность.ПолучитьВыражение());

// Запускаем поиск решения
Решение = Модель.Решить(); 

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

  Скачать пример