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

Классификация задач скалярной оптимизации

Процедуры оптимизации решений на основе отбора альтернатив.

а) Применение бинарных отношений

Наилучшим (недоминирующим) решением считается такое решение, которое не имеет ни одного доминирующего (превосходящего) решения при их попарном сравнении.

При оптимизации данным способом необходимо учитывать следующие предпосылки:

· Для каждой пары (х, у) устанавливается отношения равнодействия или предпочтения;

· Каждая пара рассматривается независимо от других пар.

Алгоритм:

1) Перечислить все пары (х,у) ∈ R;

2) Задать таблицу предпосылок

x>y, y>x, y≈x.


-
	-	≈
	≈	-

3) Разработка графа предпочтений

1 6

2 4

б) Применение функции выбора.

F(x): С_х∈Х

Х * С_х

Функция F(x) часто называется типичный выбор, стандартный выбор, критериальный выбор.

в) Применение методов группового выбора

R=Ф(R₁, … R_n)

Возможные варианты:

1) Правило большинства

2) Правило 2-х ступенчатого голосования

Типовые задачи оптимизации

1 Детализированные задачи

2 Стохастические задачи

1.1 Задача вариационного исчисления	1.2 Задача линейного прогр-я	1.3 Задача нелинейного прогр-я	1.4 Задача дискретного прогр-я	2.1 Задача оптимизации в условиях риска	2.2 Задача оптимизации в условиях неопределенности

Зад. Больца	Стандартная ЗдЛП	Задачи выпуклого прогр-я	Дискретные задачи вариационного исчисления	Оптимизация по среднему риску	Минимаксимальные задачи оптимизации
Зад. Лагранжа	Транспортная ЗдЛП	Задачи геометрического прогр-я	Многошаговые задачи дискретной оптимизации	Многошаговые задачи оптимизации	Задачи с равновероятными расстояниями и т.д.
Зад. Майера	Зад. блочного прогр-я	Зад. о потоках в сетях	Задачи теории расписаний	Стохастические задачи фильтрации и прогнозирования
Зад. Портнягина	Зад. с переменными огранич-ями коэф-тов		Частично целочисленные задачи
Зад. На быстродействие	Задача точного программирования		Задачи с булевыми переменными
Зад. Динамического прогр-я	Задача с интервальными коэффициентами

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

Дано:

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

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

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

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

Требуется:

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

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

Найти

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

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

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

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

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

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

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

Найти такие, что

при выполнении ограничений:

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

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

Найти такие, что

при выполнении ограничений:

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

Найти