Оптимизация количества рюкзаков

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

В данной задаче постановка иная: вместимость каждого рюкзака одинакова, а список предметов — фиксирован. Необходимо определить минимальное количество рюкзаков, достаточное для размещения всех предметов.

Цель — сократить затраты, используя как можно меньше рюкзаков, при условии, что вес предметов в каждом рюкзаке не превышает установленный максимум.

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

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

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

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

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

Здесь мы воспользуемся линейной целочисленной моделью, так как:

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

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

Создадим объект модели, в котором будем описывать переменные, ограничения и целевую функцию.

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

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

Укажем следующие входные данные:

• МаксВесРюкзака — максимальная грузоподъёмность одного рюкзака;
• ВесаПредметов — массив весов всех предметов;
• МаксКоличествоРюкзаков — технически максимальное число рюкзаков (равное количеству предметов — случай, когда каждый предмет в отдельном рюкзаке).

// Ввод данных
МаксВесРюкзака			= 100;
ВесаПредметов			= О2.Утилиты().МассивЧиселИзСтроки(
    "48, 30, 19, 36, 36, 27, 42, 42, 36, 24, 30"
);
КоличествоПредметов		= ВесаПредметов.Количество();
МаксКоличествоРюкзаков 	= КоличествоПредметов;

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

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

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

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

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

Создадим отдельный массив булевых переменных со значениями:

• 1 — рюкзак используется,
• 0 — не используется.

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

5. Описание ограничений

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

Каждый предмет помещается ровно в один рюкзак

Сумма по всем рюкзакам для каждого предмета должна равняться 1.

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

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

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

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

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

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

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

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

// Устанваливаем целевую функцию. Минимизируем количество используемых рюкзаков
КоличествоРюкзаков = Модель.Выражения().Сумма(ИспользуемыеРюкзаки);
Модель.Минимизировать(КоличествоРюкзаков);

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

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

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

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

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

• Показываем количество использованных рюкзаков;
• Для каждого рюкзака выводим его заполнение и список предметов.

Если решения нет, выводим соответствующее сообщение.

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

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

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

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

// Ввод данных
МаксВесРюкзака          = 100;
ВесаПредметов           = О2.Утилиты().МассивЧиселИзСтроки(
    "48, 30, 19, 36, 36, 27, 42, 42, 36, 24, 30"
);
КоличествоПредметов     = ВесаПредметов.Количество();
МаксКоличествоРюкзаков  = КоличествоПредметов;

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

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

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

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

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

// Устанваливаем целевую функцию. Минимизируем количество используемых рюкзаков
КоличествоРюкзаков = Модель.Выражения().Сумма(ИспользуемыеРюкзаки);
Модель.Минимизировать(КоличествоРюкзаков);

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

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

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