Выбор метода решения задачи

Для выбора или разработки метода решения необходимо отнести поставленную задачу к одному из классов.

Пусть - заданное множество элементов x произвольной природы, – заданное отображение множества в множество Y чисел (натурального ряда, рациональных, действительных, неотрицательных,
и т. д.).

Тогда задача минимизации (максимизации) может быть сформулирована следующим образом: либо найти элемент , , который минимизирует функцию f(x), либо установить его отсутствие. Если существует такой элемент , то для всех .

Класс задачи оптимизации определяется:

· свойствами множества Х;

· видом ограничений;

· видом целевой функции.

Множества Х может быть:

· непрерывное (н), дискретное (д)- [ ], целочисленное (ц) - ;

· отрицательное (о), неотрицательное (н);

· бесконечное (б), конечное (к);

· бинарное (B) – [0,1], не бинарное (N).

Классы задач при учете свойств множества X представлены в табл. 3.2.:

Таблица 3.2

Непрерывность

н

н

н

н

д

д

д

д

ц

ц

ц

ц

ц

Отрицательность

о

о

н

н

О

о

н

н

о

о

н

н

н

Бесконечность

б

к

б

к

Б

к

б

к

б

к

б

к

к

Бинарность

N

N

N

N

N

N

N

N

N

N

N

N

B

Все ограничения относят к следующим видам:

· линейные - , или нелинейные , где нелинейная функция;

· логически связанные:

,

где - множество Н дизъюнктивных уравнений

Виды целевой функции может быть следующим:

· однокритериальные - , или многокритериальные - , где n - количество критериев.

· линейные или нелинейные.

Для определения класса задачи математического программирования необходимо воспользоваться источником: «Хохлюк В.И. Параллельные алгоритмы целочисленной оптимизации. -М.: Радио и связь, 1987.».

При установленном классе задачи можно воспользоваться методом решения задачи (см. Венцель Е.С. Исследование операций - М., «Советское радио», 1972).