Научная электронная библиотека
Монографии, изданные в издательстве Российской Академии Естествознания
4.2. Методы решения задачи целочисленного программирования
Как было отмечено выше существуют две группы методов решения задач целочисленного программирования. Суть методов отсечения, указанный впервые в работе Д. Данцига, Д. Фулкерсона, С. Джонсона [53], заключается в следующем. Если в результате решения задачи целочисленного программирования без учета целочисленности, получено не целочисленное решение, то к ограничениям исходной задачи добавляется новое линейное ограничение, обладающее свойствами:
1) полученное нецелочисленное решение ему не удовлетворяет;
2) любое целочисленное решение ему заведомо удовлетворяет.
Затем решается полученная расширенная задача, в случае необходимости добавляется еще одно ограничение и т.д. до получения целочисленного решения. Таким образом, решение целочисленной задачи сводится к решению некоторой последовательности обычных задач линейного программирования.
Геометрически добавление каждого такого ограничения отвечает проведению гиперплоскости, отсекающей от многогранника решений старую оптимальную точку с дробными координатами, но не затрагивающей ни одной из целочисленных точек этого многогранника. Поэтому они и называются «методами отсечения».
Наибольшую известность среди методов отсечения получил метод, предложенный Р. Гомори [59], которому удалось разработать универсальное правило формирования дополнительных ограничений и доказать конечность соответствующего процесса отсечения.
Вторая группа методов отличается от первой своим комбинаторным характером, т.е. используют идею перебора. Впервые метод такого рода был предложен в 1960 году в статье А. Лэнд и А. Дойг [67] и в настоящее время известен как метод ветвей и границ. Одним из достоинств этого метода является то, что он позволяет находить не только полностью, но и частично – целочисленные решения. Благодаря этому достоинству и относительной простоте реализации на компьютере он получил наибольшее применение при решении прикладных задач целочисленного программирования. Рассмотрим эти два метода.