Решение задач целочисленного программирования в excel

Когда модель решателя включает в себя целочисленные, двоичные или все различные ограничения. Она называется задачей целочисленного программирования. Целочисленные ограничения делают модель невыпуклой, и поиск оптимального решения задачи целочисленного программирования эквивалентен решению задачи глобальной оптимизации. Такие задачи могут потребовать гораздо больше вычислительного времени. Чем та же задача без целочисленных ограничений. Когда используются симплексные методы нелинейного решения LP или GRG. Решатель использует метод ветвления и привязки для целочисленных ограничений. Эволюционный метод решения таких задач использует свои собственные методы.

Метод Ветвления и Привязки

Метод ветвей и границ начинается с поиска оптимального решения “релаксации” задачи. Игнорируя целочисленные ограничения. Если случится так. Что в этом решении переменные решения с целочисленными ограничениями уже имеют целочисленные значения. То дальнейшая работа не требуется. Если одна или несколько целочисленных переменных имеют нецелые решения. Метод Ветвления и привязки выбирает одну такую переменную и “ветвится”. Создавая две новые подзадачи. Где значение этой переменной более жестко ограничено. Эти подзадачи решаются. И процесс повторяется. “ветвясь” по мере необходимости на каждой из целочисленных переменных решения. Пока не будет найдено решение. В котором все целочисленные переменные имеют целочисленные значения (с небольшим допуском).

Таким образом. Метод Branch & Bound может решить множество подзадач. Каждая из которых является “обычной” проблемой решателя. Количество подзадач может расти экспоненциально. “Ограничивающая” часть метода Branch & Bound предназначена для устранения множества подзадач. Которые не нужно исследовать. Потому что полученные решения не могут быть лучше. Чем уже полученные решения.

Многие другие методы, такие как предварительная обработка и зондирование. Генерация разрезов. Выбор переменных узлов и ветвей. Локальный поиск и эвристика. Могут быть применены к задачам целочисленного программирования для смягчения экспоненциального роста числа подзадач. Но все эти методы обычно работают в рамках структуры Ветвей и границ.