10. Необходимые условия экстремума функций при отсутствии ограничений и при ограничениях. 11. Экономическая интерпретация множителей Лагранжа.

Множители Лагранжа рассматривались выше как параметры, значения которых выбираются таким образом, чтобы выполнялись ограничения задачи. С экономической точки зрения множители Лагранжа интерпретируются как неявные (теневые) цены ресурсов, определяемых ограничениями; оптимальные значения множителей Лагранжа играют важную роль в анализе чувствительности решений. Для того, чтобы пояснить эту интерпретационную схему, рассмотрим следующую оптимизационную задачу с двумя переменными и одним ограничением в виде равенства:

Минимизировать 

При ограничении 

Где постоянная величина B1 характеризует наличие некоторого ресурса.

Предположим, что стационарная точка функции L соответствует глобальному минимуму.

Пусть   - оптимальное значения множителя Лагранжа, а   - оптимальное решение задачи. Далее, пусть минимум функции L(X; V1) при   достигается в точке  , причем   и  . Очевидно, что оптимальные значения   связаны функциональной зависимостью с величиной B1, задающей границу наличия дефицитного ресурса.

Изменения F0 (оптимального значения F), обусловлены изменениями B1, описываются частной производной  . По правилу дифференцирования сложной функции имеем

.   (14)

Дифференцируя обе части ограничений  , получаем

.  (15)

Умножим обе части равенства (15)  на   и вычтем из (14):

.  (16)

Так как Х0 и   удовлетворяют уравнениям (12) и (13), равенство (16) приводится  к виду

.  (17)

Таким образом, из формулы (17) следует, что скорость изменения оптимального значения F, вызываемого изменением B1, определяется оптимальным значением множителя Лагранжа  . Другими словами, величина изменения оптимального значения целевой функции,

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

12. Динамическое программирование (дп). Основная идея и метод дп.

Оптимальная подструктура в динамическом программировании означает, что оптимальное решение подзадач меньшего размера может быть использовано для решения исходной задачи. К примеру, кратчайший путь в графе из одной вершины (обозначим s) в другую (обозначим t) может быть найден так: сначала считаем кратчайший путь из всех вершин, смежных с s, до t, а затем, учитывая веса ребер, которыми s соединена со смежными вершинами, выбираем лучший путь до t (через какую вершину лучше всего пойти). В общем случае мы можем решить задачу, в которой присутствует оптимальная подструктура, проделывая следующие три шага.

Разбиение задачи на подзадачи меньшего размера.

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

Использование полученного решения подзадач для конструирования решения исходной задачи.

Подзадачи решаются делением их на подзадачи ещё меньшего размера и т. д., пока не приходят к тривиальному случаю задачи, решаемой за константное время (ответ можно сказать сразу). К примеру, если нам нужно найти n!, то тривиальной задачей будет 1! = 1 (или 0! = 1).

Перекрывающиеся подзадачи в динамическом программировании означают подзадачи, которые используются для решения некоторого количества задач (не одной) большего размера (то есть мы несколько раз проделываем одно и то же). Ярким примером является вычисление последовательности Фибоначчи,   и   — даже в таком тривиальном случае вычисления всего двух чисел Фибоначчи мы уже посчитали   дважды. Если продолжать дальше и посчитать  , то   посчитается ещё два раза, так как для вычисления   будут нужны опять   и  . Получается следующее: простой рекурсивный подход будет расходовать время на вычисление решения для задач, которые он уже решал.

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

Подводя итоги вышесказанного можно сказать, что динамическое программирование пользуется следующими свойствами задачи:

перекрывающиеся подзадачи;

оптимальная подструктура;

возможность запоминания решения часто встречающихся подзадач.

Динамическое программирование обычно придерживается двух подходов к решению задач:

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

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

Языки программирования могут запоминать результат вызова функции с определенным набором аргументов (мемоизация), чтобы ускорить «вычисление по имени». В некоторых языках такая возможность встроена (например, Scheme, Common Lisp, Perl), а в некоторых требует дополнительных расширений (C++).

Известны сериальное динамическое программирование, включённое во все учебники по исследованию операций, и несериальное динамическое программирование (НСДП), которое в настоящее время слабо известно, хотя было открыто в 1960-х годах.

Обычное динамическое программирование является частным случаем несериального динамического программирования, когда граф взаимосвязей переменных — просто путь. НСДП, являясь естественным и общим методом для учета структуры задачи оптимизации, рассматривает множество ограничений и/или целевую функцию как рекурсивно вычислимую функцию. Это позволяет находить решение поэтапно, на каждом из этапов используя информацию, полученную на предыдущих этапах, причём эффективность этого алгоритма прямо зависит от структуры графа взаимосвязей переменных. Если этот граф достаточно разрежен, то объём вычислений на каждом этапе может сохраняться в разумных пределах.

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