Некоторые типовые задачи скалярного математического программирования

а) Задача линейного программирования

Дано:

- множество искомых переменных (вещественные числа) ;

- критерий оптимальности ;

- ограничения:

- граничные условия

Требуется:

Найти такие {x_j}, которые удовлетворяют ограничениям, граничным условиям и соответствующему максимуму критерия Q.

Данная задача в матричной векторной форме записывается в следующей форме:

Найти

Данный тип задачи оптимизации имеет определенные предпосылки (ограничения), при выполнении которых гарантируется отыскание верного решения.

Условия, предпосылки:

1. Коэффициенты задачи aj Cj bj должны быть известны точно

2. Ограничения задач должны быть совместны

3. Количество искомых переменных n должно быть больше чем количество ограничений m (m<n);

4. {Хj} должны относится к положительным вещественным числам, которые определяются точно в процессе проектирования.

б) Задача с нелинейным критерием и линейными ограничениями

Найти такие, что при выполнении ограничений:

в) Задачи с сепарабельным критерием оптимальности

г) Задача геометрического программирования

Найти такие, что при выполнении ограничений:

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

Найти

Раздел 3. Некоторые алгоритмы решения задач оптимизации

3.1 Поисковые (прямые) алгоритмы оптимизации

Поисковые алгоритмы классифицируются следующим образом:

Поисковые алгоритмы:
Вероятностные (опираются на случайные числа, выбираемы в соответствии с заданным законом распределения вероятностей)	Детерминированные
Случайный перебор	Алгоритмы полного перебора	Алгоритмы направленного поиска

Рассмотрим конкретные примеры поисковых алгоритмов.

1. Алгоритм полного перебора (алгоритм сеток)

Рассмотрим задачу.

Дано:

1) Исходное пространство R_x

2) Вектор искомых переменных

3) Критерий оптимальности

4) Ограничения:

Требуется:

Найти удовлетворяющие критериям.

Пример:

В итоге получаем множество точек и будим искать среди них оптимальное значение (например, перебором).

Алгоритм:

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

Недостаток: быстро растущие затраты времени на поиск оптимума с ростом числа вариантов решения.

3.1.2 Алгоритм покоординатного поиска

Поочередный подбор решений конкретных координат пространства искомых переменных

Данный метод гарантирует нахождение оптимума только в 1 случае, когда критерий оптимальности сепарабельный.

Формула сепарабельного критерия:

Для отыскания приближенного решения этот метод также можно применять.

Достоинства по отношения к предыдущему алгоритму: можно достигнуть оптимума без полного перебора