1.3. Вопросы классификации и специфики

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

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

Традиционно в математическом программировании выделяют следующие основные разделы.

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

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

Выпуклое программирование - когда выпукла целевая функция (если рассматривается задача ее минимизации) и выпукло

множество, на котором решается экстремальная задача.

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

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

Целочисленное программирование - когда на переменные накладываются условия целочисленности.

В чем специфика задач математического программирования?

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

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

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

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