2.1.6. Выпуклое программирование

Под задачей выпуклого программирования понимают задачу вида

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

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

2.1.7. Геометрическое программирование

Под задачами геометрического программирования понимают задачи наиболее плотного расположения некоторых объектов в заданной двумерной или трехмерной области. Такие задачи встречаются в задачах раскроя материала для производства каких-то изделий и т.п. Это  еще недостаточно разработанная область математического программирования и имеющиеся здесь алгоритмы в основном ориентированы на сокращение перебора вариантов с поиском локальных минимумов.

2.1.8. Дискретное программирование

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

Найти при условиях:

-множество . Если множество является конечным или счетным, то условие — условие дискретности и данная задача является задачей дискретного программирования.

Чаще всего условие дискретности разделено по отдельным переменным следующим образом: , где конечное или счетное множество.

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

2.1.9. Динамическое программирование

Динамическое программирование — это вычислительный метод для решения задач определенной структуры. Возникло и сформировалось в 1950-1953 гг. благодаря работам Р. Беллмана над динамическими задачами управления запасами. В упрощенной формулировке динамическое программирование представляет собой направленный последовательный перебор вариантов, который обязательно приводит к глобальному максимуму.

Основные необходимые свойства задач, к которым возможно применить этот принцип:

1. Задача должна допускать интерпретацию как n-шаговый процесс принятия решений.

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

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

4. Выбор решения (управления) на k-м шаге не должен оказывать влияния на предыдущие решения, кроме необходимого пересчета переменных.

Задача о выборе траектории, задача последовательного принятия решения, задача об использовании рабочей силы, задача управления запасами — классические задачи динамического программирования.