ГЛАВА 9

ЦЕЛОЧИСЛЕННОЕ ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

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

В настоящей главе рассматриваются сначала примеры задач целочисленного программирования, а затем методы их решения.

9.1. ПРИМЕРЫ ЗАДАЧ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ

Рассмотрим сначала простые практические задачи, которые сводятся к задачам ЦЛП, затем обратимся к более сложным. Для удобства задачи, в которых все переменные должны быть целочисленными, называются полностью целочисленными, а задачи, в которых лишь некоторые переменные должны принимать целочисленные значения, - частично-целочисленными.

Пример 9.1.1. Распределение капиталовложений

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

Доступный капитал 25 25 25

(млн. долл.)

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

Задача сводится к решению типа да-нет относительно каждого проекта. Определим двоичные переменные хг.

Г1, если проект j утвержден, Xj =<

(О, если проект j не утвержден. Задача ЦЛП будет записана следующим образом.

Максимизировать г = 20л:, + 40х2 + 20х3 + 15х4 + 30х5 при ограничениях

5*, + 4х2 + Зх3 + 7xt + 8х5 < 25,

хх + 7х2 + 9х3 + 4xt + 6xs < 25,

8х, + 10*2 + 2х3 + xt + 10хй < 25,

хх, х2, х3, xt, х5 = 0 или 1.

Оптимальным целочисленным решением (полученным с помощью программы TORA1) является хх = х2 = х3 = xt = 1, xs = 0 с z = 95 млн. долл. Это решение означает, что необходимо выбрать для финансирования все проекты, кроме пятого.

Интересно сравнить решение данной задачи ЦЛП с решением обычной задачи ЛП с теми же ограничениями, но без условия целочисленности переменных. Задача линейного программирования получается в результате замены условия х = О или 1 на ограничение 0<х;< 1 для всех у. Эта задача имеет решение *, = 0,5789, х2= х3= х( = 1, х5 = 0,7368 и 2 =108,68 млн. долл. Такое решение с точки зрения целочисленной задачи лишено смысла, так как две переменные принимают дробное значение. Можно было бы попытаться округлить полученный результат, что привело бы к хх = xs = 1. Полученное при этом решение является недопустимым, так как нарушаются ограничения задачи. Более существенным в этой ситуации является то, что округление применять нельзя, так как х} представляет решение типа да-нет , для которого дробные значения лишены смысла.

УПРАЖНЕНИЯ 9.1.12

1. В модели распределения капиталовложений из примера 9.1.1 предположим, что проект 5 должен быть обязательно выбран, если выбирается либо проект 1, либо 3. Измените математическую модель, включив в нее новое ограничение, и решите полученную задачу с помощью программы TORA.

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

1 Для решения задач ЦЛП в программе TORA из основного меню выберите команду Integer Programming (Целочисленное программирование). После ввода исходных данных (файл Ch9ToraCapitalBudgetEx9-l-l.txt) перейдите в выходное окно и для получения оптимального решения выберите Automated В&В (Автоматические вычисления методом ветвей и границ).

2 Задачи 3-6 в адаптированном виде заимствованы из книги Malba Tahan. El Hombre Que Calculaba, Editorial Limusa, Mexico City, 1994, pp. 39-182.

Груз / Вес единицы груза, Объем единицы груза, Стоимость единицы груза,

iv, (тонны) V/(куб. ярд) Г/ (100 долл.)

15 1 4

2 8 8 7

3 3 6 6

4 2 5 5

5 7 4 4

Максимальная грузоподъемность и объем самолета равны 112 тонн и 109 куб. ярдов соответственно. Сформулируйте в виде модели ЦЛП задачу определения набора грузов, обеспечивающего максимальную стоимость груза, и найдите решение с помощью программы TORA.

3. Пусть есть 7 полных бутылок вина, 7 бутылок, заполненных наполовину, и 7 пустых бутылок. Необходимо распределить 21 бутылку между тремя персонами так, чтобы каждый получил 7 бутылок. В то же время каждый должен получить одинаковое количество вина. Сформулируйте эту задачу в виде задачи ЦЛП с ограничениями в виде равенств и найдите решение, используя программу TORA. (Совет. Используйте фиктивную целевую функцию, все коэффициенты которой равны нулю.)

4. Эксцентричный шейх оставил завещание относительно распределения стада верблюдов между тремя детьми: Тарик получает не менее половины стада, Шариф - не менее одной трети, а Маиса - по меньшей мере одну девятую часть. Остаток завещался благотворительной организации. В завещании не упоминался размер стада, говорилось лишь, что количество верблюдов - число нечетное и благотворительная организация получает в точности одного верблюда. Сколько верблюдов оставил шейх и сколько получил каждый из его детей?

5. Супружеская пара фермеров посылает трех своих сыновей на базар продать 90 яблок, чтобы обучить их числам и обращению с деньгами. Самый старший Джим получил для продажи 50 яблок, Билл (средний) - 30 и самый младший Джон- лишь 10. Родители поставили пять условий. 1. Цена яблок должна быть равна либо 1 долл. за 7 яблок, либо 3 долл. за 1 яблоко. 2. Каждый ребенок может использовать один или оба варианта цен. 3. Все дети должны вернуться с одинаковой суммой денег. 4. Каждый ребенок приносит домой сумму, которая является четным числом (без центов). 5. Сумма денег, полученная каждым из детей, должна быть максимальной при сформулированных условиях. Считается, что дети могут продать все яблоки, которые они имеют. Как дети могут выполнить требования своих родителей?

6. Капитан торгового судна, который хотел наградить трех членов команды за их героические усилия по спасению груза корабля во время неожиданного шторма, взял некоторую сумму денег у казначея и отдал приказ старшему помощнику распределить их поровну между тремя матросами после того, как корабль достигнет берега. Однажды ночью один из матросов решил взять свою (справедливую) третью часть заранее. После деления денег на три равные части осталась одна монета, которую матрос решил оставить себе (в дополнение к третьей части денег). На следующую ночь второй мат-