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

Вычислительные методы разработаны лишь для немногих типов задач нелинейного программирования, а именно для задач так называемого выпуклого программирования. Это задачи, в результате решения которых определяется минимум выпуклой (или максимум вогнутой) функции, заданной на выпуклом замкнутом множестве. В свою очередь, среди задач выпуклого программирования более подробно исследованы задачи квадратичного программирования. В результате решения таких задач требуется в общем случае найти максимум (или минимум) квадратичной функции = с₁x₁ + с₂x₂ + … + с_nx_n + +d₁₁x₁²+…+ d₁₂x₁x₂+… + d_1nx₁x_n +…+ d_nnx_n² при условии, что её переменные удовлетворяют либо некоторой системе линейных неравенств или линейных уравнений, либо некоторой системе, содержащей как линейные неравенства, так и линейные уравнения.

Отдельными классами задач математического программирования являются задачи целочисленного, параметрического и дробно-линейного программирования.

В задачах целочисленного программирования неизвестные могут принимать только целочисленные значения.

В задачах параметрического программирования целевая функция или функции, определяющие область возможных изменений переменных, либо то и другое, зависят от некоторых параметров.

В задачах дробно-линейного программирования целевая функция представляет собой отношение двух линейных функций, а функции, определяющие область возможных изменений переменных, также являются линейными.

Выделяют отдельные классы задач стохастического и динамического программирования. Если в целевой функции или в функциях, определяющих область возможных изменений переменных, содержатся случайные величины, то такая задача относится к задаче стохастического программирования. Задача, процесс нахождения решения которой является многоэтапным, относится к задаче динамического программирования. В каждом из классов задач оптимизации есть свой набор методов нахождения оптимального решения.

Контрольные вопросы

1. Вид оптимизационной задачи.

2. Математическая постановка задач оптимизации и ее интерпретация к проблемам выбора наилучших вариантов экономического поведения.

3. Условия сведения экономической задачи к задаче оптимизации.

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

Лекция № 5. Линейное программирование

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

5.2 Варианты решения задачи линейного программирования

5.3 Области применения линейного программирования

5.4 Пример решения станковой задачи

5.5 Математическая модель задачи использования сырья

5.6 Основные понятия и теоремы линейного программирования

5.7 Нахождение решения задачи линейного программирования на основе её геометрической интерпретации