Введение. Дискретное программирование

Дискретное программирование

Рассмотрим общую задачу математического программирования:

(1)

где D – множество точек n -мерного действительного евклидова пространства Rⁿ.

Определение. Задача (1) называется задачей дискретного программирования (ДП), если множество D является конечным или счетным.

Определение. Задача (1) называется задачей целочисленного программирования (ЦП), если множество D таково, что условие означает, что - целые числа.

Таким образом, задача ЦП является частным случаем задачи ДП. Однако задачу ДП обычно путем введения новых переменных удается сформулировать как задачу ЦП.

Для решения задачи ДП нельзя применить известные методы нелинейного программирования. Это связано с тем, что допустимая область в задаче (1) является невыпуклой и несвязной. Для решения задач ДП разработаны специальные методы: методы отсечения, методы ветвей и границ, эвристические методы, методы случайного поиска и др. Мы рассмотрим варианты первых двух групп методов.

Дата добавления: 2014-01-06