Тогда первый алгоритм Гомори требует конечного числа больших итераций

 

 

20)

Целочисленное программирование – один из наиболее молодых, перспективных и быстро развивающихся разделов математического программирования. Можно перечислить большое количество разнообразных задач планирования экономики, организации производства, исследования конфликтных ситуаций, синтеза схем автоматического регулирования, которые формально сводятся к выбору лучших, в некотором смысле, значений параметров из определенной дискретной совокупности заданных величин. К ним можно отнести и экстремальные комбинаторные задачи, возникающие в различных разделах дискретной математики.

Задачи и методы, относящиеся к перечисленному кругу вопросов, в литературе именуются по-разному. Наибольшее распространение получил термин «целочисленное программирование», однако встречаются и такие как «дискретное программирование», реже «комбинаторное (или диофантово) программирование».

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

Целочисленные задачи математического программирования могут возникать различными путями.

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

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

3. Другим важным толчком к построению теории целочисленного программирования стал новый подход к некоторым экстремальным комбинаторным задачам. В них требуется найти экстремум целочисленной линейной функции, заданной на конечном множестве элементов. Такие задачи принято называть задачами с альтернативными переменными. В качестве примеров можно назвать задачи коммивояжера (бродячего торговца), об оптимальном назначении, теории расписания, или календарного планирования, и задачи с дополнительными логическими условиями (например, типа «или – или», «если – то» и т. п.).

Исторически первой задачей целочисленного типа является опубликованная в 1932 г. венгерским математиком Е. Эгервари задача о назначении персонала. В 1955 г. на Втором симпозиуме по линейному программированию была рассмотрена задача о бомбардировщике, известная как задача о ранце.

Приведем примеры целочисленных задач линейного программирования.

Пример. Задача о ранце. Имеется m-вектор ограниченных ресурсов , которые можно использовать для перевозки различных по своим характеристикам грузов. Каждый j-й груз обладает следующими свойствами: 1) неделимостью; 2) полезностью ; 3) расходом i-го ресурса для перевозки единицы j-го груза . Выбрать такой номер груза для перевозки, при котором максимизируется общая полезность рейса (суммарная стоимость перевезенных за рейс грузов).

Составим математическую модель задачи. Обозначим через количество выбранных для траспортировки предметов. Требованию неделимости соответствует условие

целые, (13.1)

Сопоставление расходов ресурсов каждого типа для транспортировки единицы груза и их наличия приводит к ограничению

(13.2)

Общая полезность рейса определяется значением функции

. (13.3)

Частным случаем задачи (13.1) – (13.2) является задача о ранце, в которой любой из заданного набора предметов может быть выбран или нет. Тогда математическая модель примет следующий вид:

Максимизировать

при условиях

Пример. В области

найти максимум функции .

Решим задачу геометрически (рис. 13.1). Область поиска экстремума – многоугольник OABCD. Так как линия уровня целевой функции параллельна стороне BC многоугольника, экстремум достигается в вершинах и , а также в любой точке отрезка BC и равен 7. Нас интересуют лишь точки с целочисленными координатами, поэтому ни B, ни C не являются допустимым решением задачи. Округлив значение координат точек B и C, получим точку (4; 3), не принадлежащую области поиска. Легко показать, что целочисленный оптимум достигается в точках M(2; 3) и N(3; 2) и равен 5. Обе точки находятся внутри области поиска.

Рисунок 13.1

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

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