Задачи целочисленного булева программирования

КРАТКИЙ КОНСПЕКТ ЛЕКЦИЙ

Под задачей математического программирования понимается задача (1):

extr f (x), (1)

x D

где D = {х (x) 0, j=1,2,...,n, x Q, Q }.

Здесь (x), j=1,2,...,n, и f(x) - произвольные функции, а extr - max или min. Функция f(x) называется целевой функцией, функционалом или критерием задачи (1), а D - множеством или областью допустимых решений задачи (1).

Среди задач типа (1) выделяют задачи, которые называют регулярными.

Для них:

- для каждого допустимого вектора x, x D, может быть определена непустая окрестность;

-можно указать достаточно эффективно проверяемые необходимые и достаточные условия локальной оптимальности, т.е. локальный оптимум может быть найден на множестве D при помощи конечного процесса (или бесконечного сходящегося);

-локальный оптимум целевой функции совпадает с глобальным.

Примерами регулярных задач являются задачи выпуклого программирования (функция f(x) - вогнута, а функции g_j(x) -выпуклые). Если функции f(x) и g_j (x) - линейные, то задача называется задачей линейного программирования.

Если область Q не является связной, то задача (1) называется дискретной задачей математического программирования или задачей дискретного программирования. Если функции f(x) и g_j (x) при этом являются линейными, то такая задача называется задачей целочисленного линейного программирования. Если компоненты вектора x могут принимать лишь значения 0 или 1, то такая задача называется задачей целочисленного булева программирования.

Дата добавления: 2017-02-01; Просмотров: 75; Нарушение авторских прав?; Мы поможем в написании вашей работы!