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

В задаче коммивояжера для формирования оптимального маршрута объезда п городов с посещением каждого города не более одного раза необходимо выбрать один лучший из (n-1)! вариантов по критерию времени, стоимости или длине маршрута. Эта задача связана с определением гамильтонова цикла минимальной длины. Будем считать, что в общем случае расстояние от города до города зависит от направления движения, а матрица расстояний задана. Если прямого маршрута между городами i,j нет, а также для всех i = j полагаем, что расстояние равно ∞.

Множество всех возможных решений можно представить в виде дерева - связного графа, не содержащего циклов и петель.

Корень этого дерева объединяет все множество вариантов, а вершины дерева - это подмножества частично упорядоченных вариантов решений. Вершина (i,j) соответствует

подмножеству всех маршрутов, содержащих дугу (i,j), а вершина (i,j) - подмножеству всех маршрутов, где эта дуга отсутствует. Процесс разбиения на эти подмножества можно рассматривать как ветвление дерева. Поэтому метод называется методом поиска по дереву решений, или методом ветвей и границ.

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

1)Оценка не должна быть больше (при минимизации) или меньше (при максимизации) минимального (максимального) значения функции для рассматриваемого множества.

2)Оценка подмножества нижнего уровня не должна быть меньше (при минимизации) или больше (при максимизации) значения оценки подмножества боле высокого уровня.

3)Оценка единственного варианта решения на последнем уровне точно совпадает со значением критерия целевой функции решения.

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

27. Классическая задача управления запасами

Под задачей управления товарными запасами понимается такая оптимизационная задача, в которой задана информация: о поставках товаров; о спросе на товар; об издержках и условиях хранения товарных запасов; критерий оптимизации.

Рассмотрим данную задачу в так называемой классической постановке. Выберем за единичный интервал времени один день. Пусть к концу дня t-1 на складе находится запас товара в объеме х_t-1 ≥ 0. Склад делает заказ на пополнение запаса в объеме h. Это пополнение поступает к началу следующего дня t, так что запас товара в начале следующего дня составляет х_t-1 + h_t. Пусть s_t - объем товара, запрашиваемый потребителями в день t (объем заявки). Если s < х_t-1 + h_t, то склад удовлетворяет заявку потребителей полностью, а остатки товара х₁ = х_t-1 + h_t -s_t переносятся на следующий день t +1, причем издержки хранения этого запаса пропорциональны его объему и равны сх_t = с(х_t-1 +h_t - s_t). Если объем заявки s_t > х_t-1 + h_t, то склад полностью отдает свой запас, а за недопоставленный товар несет потери (штрафуется), пропорциональные объему дефицита и равные - k(х_t-1 +h_t -s_t). Таким образом, полные издержки φ(х_t-1 ,h_t, s_t) склада можно записать в виде: φ(х_t-1,h_t,s_t)= mах{с(х_t-1 +h_t –s_t);-k(x_t-1+h_t-s_t)}, ( 1 )

при этом остаток товара х, = mах{0;х_t-1 +h_t-s_t}. Из (1) следует, что: если х_t >0, то φ(х_t) = сх₁; если х_t < 0, то φ(х_t) = -kх_t; если х_t = 0 , то φ(х_t) = 0.

Предполагается, что величина спроса s_t неизвестна, однако известно, что она является случайной величиной, имеющей заданный закон распределения F(х) с плотностью распределения f(х), Тогда средние, полные издержки Ф(x_t-1 + h_t) равны:

Ф(x_t-1+ ht) = M(φ(x_t-1,h_t ,s_t)) = (x_t-1,h_t ,s_t)dF(s_t)

Сама задача управления ставится следующим образом: определить объем заказа на пополнение h_t, минимизирующий полные средние издержки. В статической постановке,

считая величины х,h,s не зависящими от времени t и обозначая у = х_t-1+ h_t, получим:

Ф(y) = c min

Вычислим первые две производные функции Ф(>0:

Ф'(у) = сF(у) - k{ 1 – F(у))=(c+к)F(у) - k; Ф"(у)=(c + к)F'(у) = (с + k)f(у) ≥0 . Так как вторая производная неотрицательна, то в точке экстремума функции Ф(у) имеет место минимум. Поэтому, приравнивая Ф'(>0 к нулю, находим уравнение для

минимизирующего запаса:

F(у*)= ( 3 )

Решение (3) задачи (2) определяет стратегию оптимального пополнения запасов. Величина пополнения запасов к*,, минимизирующая средние полные издержки, задается следующим правилом:

0, x_t-1 ≥ y*

h*_t =

y*- x_t-1, x_t-1 ≥ y*

Конкретные числовые характеристики системы управления запасами зависят от вида функции плотности f(х) распределения случайной величины спроса.