Нелинейное и динамическое программирование

7. Таха Х.А. Введение в исследование операций [Текст], 7-е издание.: Пер. с англ. – М., 2005.-912 с.
8. [Электронный ресурс] http://emirs.miet.ru/oroks-miet/upload/normal1/003pdt3q3qw3dv/REVYAKIN3_3.pdf
9. [Электронный ресурс] http://sdamzavas.net/1-32634.html
10. [Электронный ресурс] https://math.semestr.ru/math/nonlinear_graphic.php
11. [Электронный ресурс] https://studfiles.
…

1.1. Понятие нелинейного программирования
Нелинейное программирование — это раздел математического программирования, объединяющий теорию и методы решения задач отыскания экстремальных значений, в которых целевая функция или система ограничений (или та и другая) содержат выражения, нелинейные относительно искомых величин [1].
Нелинейное программирование объединяет методы решения задач, которые описываются нелинейными соотношениями. К задачам нелинейного программирования относятся задачи оптимизации производства для большинства предприятий, поскольку в настоящее время они действуют на неоднородном рынке в условиях монополистической конкуренции и спрос на их продукцию зависит от цены [2].
К задачам нелинейного программирования относятся такие задачи, в которых или целевая функция, или система ограничений, или и целевая функция и система ограничений содержат выражения, нелинейные относительно переменных.
…

1.2. Формулировка и особенности задач нелинейного программирования
В общем виде задача нелинейного программирования (ЗНП) формулируется следующим образом:
f  х1,х2,х3,….хn →maxmin (1)
g (x1, x2, …,xn) ≤ bi, i= 1,m1
g (x1, x2, …,xn) ≥ bi, i= m1+1,m2 (2)
g (x1, x2, …,xn) = bi, i= m2+1,m
Найти значения переменные xj ( j=1, n ), при которых при ограничениях gi(x1, x2, …,xn) ≤ (≥, =) bi, i= 1,m (2) выполнятся условие (1), где f и g – заданные функции от n переменных.
Для задач нелинейного программирования, в отличие от задач линейного программирования, нет универсального метода решения.
Рассмотрим некоторые свойства задач линейного программирования.
– Множество допустимых решений выпукло. Это выпуклое множество имеет конечное число вершин, которые обычно называют крайними или угловыми точками.
– Целевая функция, принимая определенное значение, представляет собой гиперповерхность уровня.
…

1.3. Примеры решения задач нелинейного программирования
Рассмотрим пример решения задачи, в которой целевая функция является нелинейной.
Пример 1.Решить задачу графическим методом:

,
Решение.
Определим область допустимых решений задачи, которая задается системой неравенств (1)-(3).

Строим прямую по двум точкам:
х =х1
0
3
у = х2
2
0

Строим прямую по двум точкам:
х =х1
0
6
у = х2
9
0

Строим прямую по двум точкам:
х =х1
0
-4
у = х2
2
0

С учетом неотрицательности переменных искомая область представлена на рисунке 1.

Рис. 1.
Линии уровня целевой функции  задаются следующим образом:

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

2.1. Понятие и формулировка задачи динамического программирования
Задачи оптимального планирования (управления) обычно состоят в следующем. Рассматривается система, состояние которой со временем меняется. Процесс изменения состояний управляем. Оптимальность управления означает выбор наилучшего решения для достижения поставленной цели. Динамическое программирование – это метод для решения задач определённой структуры.
Такие задачи имеют ряд особенностей [11].
Во- первых, рассматривается процесс поведения системы во времени.
Во-вторых, состояние системы в каждый момент времени определяется численными значениями некоторого набора параметров.
В-третьих, поведение системы определяется в дальнейшем настоящим состоянием и выбором управления.
Специфика метода состоит в том, что процесс разделяется на этапы и задача оптимизации управления решается на каждом этапе. Управление на каждом шаге надо выбирать с учётом будущего.
…

2.2. Принцип оптимальности Беллмана
Метод динамического программирования позволяет одну задачу со многими переменными заменить рядом последовательно решаемых задач с меньшим числом переменных. Процесс решения задачи разбивается на шаги. При этом нумерация шагов, как правило, осуществляется от конца к началу.
Основным принципом, на котором базируются оптимизация многошагового процесса, а также особенности вычислительного метода, динамического программирования, является принцип оптимальности Р. Беллмана.
Оптимальное поведение обладает тем свойством, что каковы бы ни были начальное состояние и начальное решение, последующие решения должны быть оптимальными относительно состояния, полученного в результате первоначального решения.
Принцип оптимальности имеет конструктивный характер и непосредственно указывает процедуру нахождения оптимального решения.
…