Раздел 6. Задачи скалярной оптимизации, линейные, нелинейные, дискретные
6.1 Математическое программирование
В математическом программировании можно выделить два направления.
К первому, уже вполне сложившемуся направлению – собственно математическому программированию – относятся детерминированные задачи , предполагающие, что вся исходная информация является полностью определенной.
Ко второму направлению – так называемому стохастическому программированию – относятся задачи, в которых исходная информация содержит элементы неопределенности, либо когда некоторые параметры задачи носят случайный характер с известными вероятностными характеристиками. Так, планирование производственной деятельности зачастую производится в условиях неполной информации о реальной ситуации, в которой будет выполняться план. Или, скажем, когда экстремальная задача моделирует работу автоматических устройств, которая сопровождается случайными помехами. Заметим, что одна из главных трудностей стохастического программирования состоит в самой постановке задач, главным образом из-за сложности анализа исходной информации.
Традиционно в математическом программировании выделяют следующие основные разделы.
Линейное программирование – целевая функция линейна, а множество, на котором ищется экстремум целевой функции, задается системой линейных равенств и неравенств. В свою очередь в линейном программировании существуют классы задач, структура которых позволяет создать специальные методы их решения, выгодно отличающиеся от методов решения задач общего характера. Так, в линейном программировании появился раздел транспортных задач.
Нелинейное программирование – целевая функция и ограничения нелинейны. Нелинейное программирование принято подразделять следующим образом:
Выпуклое программирование – целевая функция выпукла (если рассматривается задача ее минимизации) и выпукло множество, на котором решается экстремальная задача.,
Квадратичное программирование – целевая функция квадратична, а ограничениями являются линейные равенства и неравенства.
Многоэкстремальные задачи. Здесь обычно выделяют специализированные классы задач, часто встречающихся в приложениях, например, задачи о минимизации на выпуклом множестве вогнутых функций.
Важным разделом математического программирования является целочисленное программирование, когда на переменные накладываются условия целочисленности.
Целью математического программирования является создание, где это возможно, аналитических методов определения решения, а при отсутствии таких методов – создание эффективных вычислительных способов получения приближенного решения.
Наконец, заметим, что наименование предмета – “математическое программирование” – связано с тем, что целью решения задач является выбор программы действий. Рассмотрим более подробно задачу линейного программирования.