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

История развития, область исследований, цели науки

 

Одной из характерных особенностей современной науки является широкое проникновение результатов и методов математики в самые разнообразные области исследования.

Научные методы выработки количественно обоснованных рекомендаций по принятию оптимальных решений определили научное направление, получившее название теории исследования операций. Термин "исследования операций" возник в результате перевода с английского (" operations research ") условного наименования одного из подразделений британских ВВС, занимавшегося вопросами оптимального использования радиолокационных установок в системе обороны в конце 1930-х годов. Постепенно указанная теория с решения задач военного содержания расширилась для решения как чисто технических, так и экономических задач, задач управления на различных уровнях.

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

Операция – любое управляемое мероприятие, направленное на достижение цели.

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

Для применения количественных методов исследования требуется построить математическую модель операции. Следует отметить большой класс оптимизационных моделей. Такие задачи возникают при попытке оптимизировать планирование и управление экономическими системами. В общем виде они выглядят так: найти переменные x₁,x₂,...,x_n, удовлетворяющие системе неравенств (уравнений) j_i(x₁,x₂,...,x_n) £ b_i, 1£i£m;

и обращающие в максимум (минимум) целевую функцию Z=f(x₁,x₂,...,x_n). Точка X=(x₁,x₂,...,x_n), удовлетворяющая данным ограничениям, называется допустимой или допустимым решением. Среди допустимых точек отыскивается такая, в которой функция f(x₁,x₂,...,x_n) принимает наибольшее значение. Такая точка называется оптимальной или оптимальным решением.

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

Математическое программирование – составная часть математических дисциплин, изучающих теории и методы нахождения экстремумов (т.е. max и min) функций многих переменных при наличии дополнительных ограничений на эти переменные, которые представляются в виде равенств или не равенств.

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

 

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

 

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

1. Если f(x₁,x₂,...,x_n) и условия j_i (x₁,x₂,...,x_n) являются линейными функциями, и

X = Rⁿ₊ , то мы имеем задачу линейного программирования.

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

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

2. Нелинейное программирование - если целевая функция (и) или ограничения нелинейные функции.

Подклассы задач нелинейного программирования:

n Если указанные функции обладают свойствами выпуклости, то такой класс задач называется выпуклым программированием.

n Квадратичное программирование - целевая функция квадратичная, а ограничения являются линейными равенствами или неравенствами.

3. Если область допустимых решений состоит из конечного числа точек - такой класс задач называется дискретным программированием.

4. Если функции f(x₁,x₂,...,x_n), j_j(x₁,x₂,...,x_n) зависят от случайных факторов, то такой класс задач называется стохастическим программированием.

5. Исследованием задач, в которых принятие оптимального решения представлено в виде некоторого многошагового процесса, занимается динамическое программирование.

Существуют и другие методы выработки количественно обоснованных рекомендаций по принятию оптимальных решений, которые определили научное направление, получившее название теории исследования операций. Термин "исследования операций" возник в результате перевода с английского (" operations research ") условного наименования одного из подразделений британских ВВС, занимавшегося вопросами оптимального использования радиолокационных установок в системе обороны в конце 1930-х годов. Постепенно указанная теория с решения задач военного содержания расширилась для решения как чисто технических, так и экономических задач, задач управления на различных уровнях.

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

Операция – любое управляемое мероприятие, направленное на достижение цели.

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

К этим методам относятся:

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

- метод Монте-Карло (статистических испытаний),

- теория массового обслуживания,

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