§ 2. Задачи с неделимостями

2.1. Изучение дискретных моделей математического программирования началось с анализа целочисленных задач линейного программирования, т. е. задач линейного программирования, в которых на все переменные или на их часть наложено дополнительное требование целочисленности.

Говоря формально, целочисленная задача линейного программирования заключается в максимизации

при условиях

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

Модель (2.1) — (2.4) естественно интерпретировать, например, в следующих терминах. Пусть через обозначены производственные факторы, через виды конечной продукции. Обозначим далее: количество фактора необходимое для производства единицы продукта наличные ресурсы фактора прибыль, получаемая от единицы продукта Пусть продукты для являются неделимыми, т. е. физический смысл имеют лишь целые неотрицательные количества их («штуки»). Предположим, что целью является составление производственной программы, обеспечивающей максимум суммарной прибыли и не выводящей за пределы данных ресурсов. Обозначая через искомые объемы выпуска продукции, мы сводим эту задачу к модели

Дадим теперь другую интерпретацию для полностью целочисленной модели (2.1) — (2.4). Пусть теперь через обозначены типы работ, подлежащих выполнению, а через типы оборудования. Пусть себестоимость использования единицы оборудования типа на работе ограничения по суммарной себестоимости для работы

эффект от использования единицы оборудования

Пусть все типы оборудования являются неделимыми, т. е. могут быть использованы лишь в целых неотрицательных количествах. Целью является составление программы использования оборудования, удовлетворяющей ограничениям по себестоимости и дающей максимальный суммарный эффект. Обозначим через искомые количества единиц оборудования типа Тогда задача сведется к модели (2.1) — (2.4).

Отметим еще, что в последней интерпретации могут присутствовать также и ограничения сверху на количества единиц оборудования каждого типа. Иными словами, могут быть заданы также целые неотрицательные числа в этом случае к условиям (2.1) — (2.4) следует добавить еще ограничения

Указанные две интерпретации задач с неделимостями (планирование выпуска неделимых видов продукции и планирование использования неделимых производственных факторов) являются в определенном смысле универсальными.

2.2. Опишем теперь одну конкретную целочисленную модель, явившуюся первой опубликованной моделью целочисленной задачи линейного программирования [63]. Речь идет об оптимальной загрузке бомбардировщиков различных типов бомбовым запасом с целью максимизации суммарного эффекта данной системы боевых операций. Обозначим через типы бомб, через типы бомбардировщиков, через боевые операции. Введем также следующие величины:

имеющийся запас бомб типа

— эффективность бомбы типа на операции планируемое число боевых вылетов бомбардировщика

— «вес», приписываемый командованием операции

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

Задача, таким образом, сводится к максимизации суммарного эффекта

при ограничениях

Разумеется, к ограничениям (2.7) могут быть присоединены и другие реально возникающие ограничения.

Не вдаваясь в критику этой весьма упрощенной модели, отметим, что во время ее опубликования (1955 г.) основным препятствием для ее решения и использования было именно требование целочисленности всех переменных.

2.3. Приведем теперь один важный и наиболее простой вариант линейной модели с неделимостями, широко известный под названием задачи о ранце. Имеется предметов; заданы величины: вес предмета ценность предмета

Требуется загрузить ранец, «грузоподъемность» которого равна набором предметов с максимальной суммарной ценностью. Если ввести переменные имеющие следующий смысл:

то задача о ранце сведется к максимизации

при условиях

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