Сущность методов дискретной оптимизации

В первом приближении методы целочисленной оптимизации можно разделить на две группы: точные и приближённые. К точным относятся методы отсечения и комбинаторные (метод ветвей и границ). Однако точные методы имеют слабую сходимость. Многие экспериментальные и прикладные задачи не удалось решить за десятки и тысячи итераций. Общая идея решения задачи дискретного программирования методами отсечения состоит в следующем: исходная задача решается сначала без учёта ограничения целочисленности. Если полученный оптимальный план удовлетворяет условиям целочисленности, то задача решена, в противном случае к ограничениям исходной задачи добавляются новые, обладающие следующими свойствами:

· Полученный нецелочисленный план нарушает это ограничение.

· Любой целочисленный допустимый план исходной задачи заведомо удовлетворяет и новому ограничению.

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

Для решения задачи дискретного программирования получили широкое распространение комбинаторные методы направленного частичного перебора допустимых планов. Из них наиболее универсален метод ветвей и границ. Для выявления сущности этого момента воспользуемся известной задачей об отыскании фальшивой монеты. Пусть в мешке с монетами одинакового достоинства имеется одна фальшивая, отличающаяся бόльшим весом, которую будем искать по средствам взвешивания на рычажных весах без гирь. Поступим так: Разделим содержимое мешка на 2 равные по количеству монет части. В случае, если число n монет – нечётное – разделим n-1 монет на 2 равные части. Положим на чашки весов равные по количеству монет части. Если чашки весов уравновесятся, то отложенная монета – фальшивая, в противном случае она находится в более тяжёлой части, с которой поступим аналогичным образом. Так до тех пор, пока не найдём фальшивую монету. Здесь деление мешка есть деление множества на подмножества, т.е. разбиение области допустимых решений на непересекающиеся подмножества. Взвешивание каждой части соответствует оценке целевой функции на подмножестве (оценке верхней или нижней границы). Если при этом удастся найти некоторый план, для которого верхняя (нижняя) оценка на множестве плана одного из подмножеств равна значению функции в этой точке и не меньше (не превосходит) оценок сверху (снизу) на всех подмножествах, то этот план оптимальный. Если такой план не обнаружен, то продолжается процесс разбиения, начиная его с подмножества, имеющего самую высокую (низкую) оценку и т.д. Поскольку множество всех планов задачи конечно, то в конце концов план будет оптимальный.