стр 269
Целочи́сленное программи́рование — раздел математического программирования, в котором на все или некоторые переменные дополнительно накладывается ограничение целочисленности[1].
Простейший метод решения задачи целочисленного программирования — сведение её к задаче линейного программирования с проверкой результата на целочисленность.
Целочисленные задачи математического программирования могут возникать различными путями.
1. Существуют задачи линейного программирования, которые формально к целочисленным не относятся, но при соответствующих исходных данных всегда обладают целочисленным планом. Примеры таких задач – транспортная задача и ее модификации (задачи о назначениях, о потоках в сетях).
2. Толчком к изучению целочисленных задач в собственном смысле слова явилось рассмотрение задач линейного программирования, в которых переменные представляли физически неделимые величины. Они были названы задачами с неделимостью. Таковы, например, задачи об оптимизации комплекса средств доставки грузов, о нахождении минимального порожнего пробега автомобилей при выполнении заданного плана перевозок, об определении оптимального машинного парка и его оптимального распределения по указанным работам при условии минимизации суммарной стоимости (машинного парка и производимых работ), о нахождении минимального количества судов для осуществления данного графика перевозок и т. п.
3. Другим важным толчком к построению теории целочисленного программирования стал новый подход к некоторым экстремальным комбинаторным задачам. В них требуется найти экстремум целочисленной линейной функции, заданной на конечном множестве элементов. Такие задачи принято называть задачами с альтернативными переменными. В качестве примеров можно назвать задачи коммивояжера (бродячего торговца), об оптимальном назначении, теории расписания, или календарного планирования, и задачи с дополнительными логическими условиями (например, типа «или – или», «если – то» и т. п.).
Целочисленным (иногда его называют также дискретным) программированием называется раздел математического программирования, изучающий экстремальные задачи, в которых на искомые переменные накладывается условие целочисленности, а область допустимых решений конечна. Изучение этого раздела в курсе «Экономико-математические методы и прикладные модели» вызывается тем, что огромное количество экономических задач носит дискретный, чаще всего целочисленный характер, что связано, как правило, с физической неделимостью многих элементов расчета: на пример, нельзя построить два с половиной завода, купить полтора автомобиля и т.д. В ряде случаев такие задачи реша ются обычными методами, например, симплексным методом, с последующим округлением до целых чисел. Однако такой подход оправдан, когда отдельная единица составляет очень малую часть всего объема (например, товарных запасов); в противном случае он может внести значительные искажения в действительно оптимальное решение. Поэтому разработаны специальные методы решения целочисленных задач, среди
которых можно выделить два направления: методы отсече ния (отсекающих плоскостей) и комбинаторные методы. Метод отсекающих плоскостей состоит в построении дополнительных ограничений и применении двойственного симплексного метода. Представление о комбинаторных методах дает широко используемый на практике метод ветвей и границ. Рассмотрим более подробно один из методов отсекающих плоскостей, известный как метод Гомори. Метод Гомори для линейных задач целочисленного программирования основан на понятии конгруэнтности действительных чисел. Любое действительное число можно представить в виде суммы его целой и дробной частей: х = [х] +, где квадратные скобки означают целую часть, а фигурные — дробную. Например, 7,5 = [7,5] +
= 7 + 0,5. Неотрицательные числа (для про стоты мы будем рассматривать только их) называются конгру энтными, если равны их дробные части. Если обозначать кон груэнтность чисел символом =, то, например, 7,5 = 0,5; 6,3 = 2,3; в частности, все целые числа конгруэнтны нулю, поэтому условие целочисленности переменной Xi можно записать: xi = 0. По методу Гомори первый этап решения целочисленных задач не отличается от обычного расчета по симплексному алгоритму. Если среди значений переменных в оптимальном плане есть дробные, то составляется дополнительное ограни чение, отсекающее дробную часть решения, но оставляющее в силе все прочие условия, которым должен удовлетворять оптимальный план. Это дополнительное ограничение при соединяется к исходным ограничениям задачи, и вновь при меняется процедура симплексного метода. Алгоритм Гомори позволяет прийти к оптимальному целочисленному решению за конечное число шагов.
Методы целочисленной оптимизации можно разделить на три основные группы: а) метод отсечения; б) комбинированные методы; в) приближенные методы. Рассмотрим один из методов отсечения – метод Гомори. Алгоритм Гомори: 1) решаем задачу без учета условий целочисленности; 2) полученное оптимальное решение (если оно существует) проверяется на целочисленность. Если условие целочисленности выполняется по всем переменным, то оптимальное решение найдено. Если это условие не выполняется, то переходим к следующему этапу или делаем вывод, что задача оказалась неразрешимой (случай: базисная переменная дробная, а все коэффициенты в строке целые числа); 92 3) строится дополнительное ограничение, отсекающее часть области, в которой содержится оптимальное решение задачи (1)-(2) и не содержится ни одного допустимого решения задачи (1)-(3); 4) последний этап предусматривает возвращение к задаче линейного программирования с отброшенным условием целочисленности, но с расширенной системой ограничений, в которую включено дополнительное ограничение, полученное на 3-ем шаге. К расширенной системе ограничений вновь применяется симплексная процедура. Если найденное таким образом решение будет опять нецелочисленным, то формируется новое дополнительное ограничение и процесс вычислений повторяется. Алгоритм Гомори позволяет за конечное число шагов прийти к оптимальному целочисленному решению, если оно существует.
Впервые метод ветвей и границ был предложен в 1960 г. А. Лэндом и А. Дойгом применительно к задаче целочисленного линейного программирования. Фактически «второе рождение» этого метода связано с работой Дж. Литтла, К. Мурти, Д. Суини и С. Кэрела. В ней же было предложено и принятое теперь название метода: «метод ветвей и границ». Он применим как к полностью, так и частично целочисленным задачам.
Алгоритм метода ветвей и границ
- Находится решение задачи линейного программирования без учета целочисленности
- Составляется дополнительные ограничения на дробную компоненту плана.
- Находится решение двух задач с ограничениями на компоненту.
- Строятся в случае необходимости дополнительные ограничения, согласно возможным четырем случаям. Определяется оптимальный целочисленный план, либо устанавливается неразрешимость задачи.
Главный недостаток алгоритма метода ветвей и границ заключается в необходимости полностью решать задачи линейного программирования, ассоциированные с каждой из вершин многогранника допустимых решений. Для задач большой размерности это требует значительных и, в известной степени, неоправданных с практической точки зрения затрат времени.
Таким образом, несмотря на отмеченные недостатки данного метода, можно утверждать, что в настоящее время алгоритмы метода являются наиболее надежным средством решения целочисленных задач, встречающихся в практических исследованиях. Это не означает, однако, что любая целочисленная задача может быть решена с помощью рассматриваемого метода. Тем не менее проблема выбора между методом отсечений и методом ветвей и границ в подавляющем большинстве случаев обоснованно разрешается в пользу последнего.
Рассмотрим далее ряд специальных оптимизационных за дач, сводящихся к задачам линейного целочисленного про граммирования. Одной из таких задач является задача о назначениях, с помощью которой можно получить ответ на вопросы типа: как распределить рабочих по станкам, чтобы общая выработка была наибольшей или затраты на заработ ную плату наименьшими; как наилучшим образом распре делить экипажи самолетов; как назначить людей на различ ные должности (отсюда и название задачи) и т.д. Математически такие задачи относятся к тому же типу распределительных задач, что и рассмотренная в § 3.2 транс портная задача, с той особенностью, что в них объемы на личных и требующихся ресурсов для выполнения каждой работы равны единице (at = bj = 1), а все переменные хц либо равны единице, если i-й работник назначен на у-ю работу, либо равны нулю в других случаях. Исходные данные задачи о назначениях группируются в таблице, которая называется матрицей оценок, а результаты — в матрице назначений. Задача о назначениях в общем виде может быть сформу лирована следующим образом. Имеется п работников, кото рые могут выполнять п работ, причем использование i-ro работника на ;-й работе, например, приносит доход Су. Тре буется поручить каждому из работников выполнение одной вполне определенной работы, чтобы максимизировать в дан ном случае суммарный доход.
Другой задачей подобного рода является задача о ком мивояжере, которая может быть сформулирована следую щим образом. Имеется п городов, пронумерованных числами от 1 до п. Коммивояжер, выезжая из города 1, должен побывать в каждом городе ровно один раз и вернуться в исходный пункт. Пусть известны расстояния Сц между городами (i, у = 1, п; i * у). Требуется найти самый короткий маршрут.
К задачам целочисленного программирования приводят также многие оптимальные задачи теории расписаний, в которой рассматриваются методы оптимизации оперативно- календарного планирования. В качестве примера таких задач можно привести задачу определения оптимальной очередности обработки изделий на различных станках или других рабочих местах, задачу составления программы «диспетчер» для управ ления работой ЭВМ в мультипрограммном режиме и др.
Значительная часть задач коммерческой деятельности требует целочисленного решения. К ним относятся задачи, у которых переменные величины означают количество единиц неделимой продукции, например, распределения товаров между предприятиями, раскрой материалов, число станков при загрузке оборудования, распределение транспортных средств по рейсам, продажа автомобилей, распределение самолетов по авиалиниям, количество персональных компьютеров в управляющем комплексе и т.д. Линейные задачи, решения которых должно быть получено в целых числах, называют задачами целочисленного программирования.
Графический метод решения задач. При наличии в задаче линейного программирования двух переменных, а в системе ограничений – неравенств, она может быть решена графическим методом. 90 В системе координат X1OX 2 находят область допустимых решений, строят вектор C и линию уровня. Перемещая линию уровня по направлению C для задач на максимум, находим наиболее удаленную от начала координат точку и ее координаты. В том случае, когда координаты этой точки целочисленные, в области допустимых решений строят целочисленную решетку и находят на ней такие целые числа, которые удовлетворяют системе ограничений и при которых значение целевой функции наиболее близко к экстремальному нецелочисленному решению. Координаты такой вершины и являются целочисленным решением. Аналогично решается задача на минимум
