Научная электронная библиотека
Монографии, изданные в издательстве Российской Академии Естествознания

4.2. Методы решения задачи целочисленного программирования

Как было отмечено выше существуют две группы методов решения задач целочисленного программирования. Суть методов отсечения, указанный впервые в работе Д. Данцига, Д. Фулкерсона, С. Джонсона [53], заключается в следующем. Если в результате решения задачи целочисленного программирования без учета целочисленности, получено не целочисленное решение, то к ограничениям исходной задачи добавляется новое линейное ограничение, обладающее свойствами:

1) полученное нецелочисленное решение ему не удовлетворяет;

2) любое целочисленное решение ему заведомо удовлетворяет.

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

Геометрически добавление каждого такого ограничения отвечает проведению гиперплоскости, отсекающей от многогранника решений старую оптимальную точку с дробными координатами, но не затрагивающей ни одной из целочисленных точек этого многогранника. Поэтому они и называются «методами отсечения».

Наибольшую известность среди методов отсечения получил метод, предложенный Р. Гомори [59], которому удалось разработать универсальное правило формирования дополнительных ограничений и доказать конечность соответствующего процесса отсечения.

Вторая группа методов отличается от первой своим комбинаторным характером, т.е. используют идею перебора. Впервые метод такого рода был предложен в 1960 году в статье А. Лэнд и А. Дойг [67] и в настоящее время известен как метод ветвей и границ. Одним из достоинств этого метода является то, что он позволяет находить не только полностью, но и частично – целочисленные решения. Благодаря этому достоинству и относительной простоте реализации на компьютере он получил наибольшее применение при решении прикладных задач целочисленного программирования. Рассмотрим эти два метода.

 


Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074