2. Математическая постановка задачи

N - число городов.

Ci j , i, j=1..N - матрица затрат, где Ci j - затраты на переход из i-го города в j-й.

Xi j - матрица переходов с компонентами:

Критерий:

Ограничения:

Ui - Uj + N × Xi j £ N-1, i, j = 1..N, i ¹ j. (4)

 

Условие (2) означает, что коммивояжер из каждого города выезжает только 1 раз;

Условие (3) о том , что в каждый город въезжает только 1 раз;

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

2. Обзор существующих решений

Задачи «коммивояжера» решаются несколькими способами:

1.Прямым алгоритмом

Имеется N городов, которые должен обойти коммивояжер с минимальными затратами. При этом на его маршрут накладывается два ограничения:

- маршрут должен быть замкнутым, то есть коммивояжер должен вернуться в тот город, из которого он начал движение;

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

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

2. Метод ветвей и границ

Общая идея метода может быть описана на примере поиска минимума и максимума функции f(x) на множестве допустимых значений x. Функция f и x могут быть произвольной природы. Для метода ветвей и границ необходимы две процедуры: ветвление и нахождение оценок (границ).

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

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

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

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

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

2. Технологическая часть

2.1 Нелинейное программирование. Общий вид задач нелинейного программирования Модели нелинейного программирования. Методы решения задач нелинейного программирования.

Нелинейное программирование  — случай математического программирования, в котором целевой функцией или ограничением является нелинейная функция.

Задача нелинейного программирования ставится как задача нахождения оптимума определенной целевой функции   при выполнении условий

где   — параметры,  

s — ограничения, n — количество параметров, s — количество ограничений.

В отличие от задачи линейного программирования, в задаче программирования нелинейного оптимум не обязательно лежит на границе области, определенной ограничениями.

Как правило, в практических задачах необходимо определить наибольшее и наименьшее значения функции (глобальный экстремум) в некоторой области. Говорят, что функция z = f (X) имеет в точке X⁰ заданной области D глобальный максимум (наибольшее значение) или глобальный минимум (наименьшее значение), если неравенство f(X) ≤ f(X⁰) или соответственно выполняется для любой точки X € D. 

Если область D замкнута и ограничена, то дифференцируемая функция z = f (X) достигает в этой области своих наибольшего и наименьшего значений или в стационарной точке, или в граничной точке области (теорема Вейерштрасса).

Граница области D аналитически может быть задана системой уравнений (условий) относительно переменных x₁, x₂, ..., x_n. Поэтому, исследуя экстремальные свойства функции на границе, необходимо решить задачу определения условного экстремума.

Условный экстремум. Пусть необходимо найти экстремум функции z = f (x₁, x₂, ..., x_n ) при условии, что переменные x₁, x₂, ..., x_n удовлетворяют, уравнениям

φi (x1, x2, ..., xn ) = 0, i = 1, 2, ..., m,m < n

(1)

Предполагается, что функции f и φ_i , имеют непрерывные частные производные по всем переменным. Уравнения (1) называют уравнениями связи. Говорят, что в точке удовлетворяющей уравнениям связи(1), функция z = f (X) имеет условный максимум (минимум), если неравенство f(X⁰) ≥  f(X) (f(X⁰) ≤  f(X)) имеет место для всех точек X, координаты которых удовлетворяют уравнениям связи. 

Легко заметить, что задача определения условного экстремума совпадает с задачей нелинейного программирования.

Один из способов определения условного экстремума применяется в том случае, если из уравнений связи (1) m переменных, например x₁, x₂, ..., x_n, можно явно выразить через оставшиеся n – m переменных:

xi = ψi (xm + 1 , ..., xn ), i = 1, 2, ..., m,

(2)

Подставив полученные выражения для x_f в функцию z, получи мz_i = f(ψ_i (x_{m + 1} , ..., x_n ), ..., ψ_m (x_{m + 1} , ..., x_n ), x_{m + 1} , ..., x_n )

или

z = F(xm + 1 , ..., xn )

(3)

Задача сведена к нахождению локального (глобального) экстремума для функции (3) от n - m переменных. Если в точке функция (3) имеет экстремум, то в точке функция z = f (x₁, ..., x_n ) имеет условный экстремум.