Документ: Интеллектуальные информационные системы. труды международной научно-практической конференции. И73, страницы 66-70

d := (d1,d2, ,dm ): R → ( + )m , R:= r ,r , ,r		, dsr ≥ 0	, s		.
	R			1,m
				1,m
1 2		i

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

Рассмотрим задачу транспортной логистики. Здесь разметки примут следующий вид:

m1(u) – запас однородного груза в вершине u ,

m2(u;v) – количество груза, назначенного для доставки из вершины u в

вершину v,
d1r	– стоимость перевозки единицы груза по ребру r ,
d2r	– пропускная способность ребра r ; m = 2.
Поставим задачу минимизации расходов на доставку всего груза с учётом
пропускной способности рёбер за цикл перевозки.
Статистические наблюдения позволяют определить матрицу взвешенной
смежности вершин A:=		d1r				V	; при этом отсутствующим рёбрам и петлям



		v v		j
			i	j	i, j=1
					i, j=1

присвоим штраф в виде бесконечной удельной стоимости перевозки d1rvivj = +∞. Алгоритмом, предложенным в публикациях [1,2], найдём матрицу минимальных расстояний на графе B:= bij iV, j=1; её элементы конечны из-за сильной

связности графа G . При этом получим матрицу списков cij := (e(k)ij )+∞k=0 соответ-

ствующих маршрутов C := cij iV, j=1, ранжированных удельной стоимостью пере-

d1e

:=

∑r e

d1r

=

→

. Очевидно cij

≠

; i, j

1,

.

возки: e(k)ij : vi

vj

(k)ij

V

(k)ij

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

2

1

)ij

1

)ij,

d

e

:= min

d

r:

d e(k

= d e(k

k

≤ k .

1

2

(k)ij

r e(k)ij

d

2e

≤ d2e

,

1

2

(k1)ij

(k2 )ij

Очевидно, маршрут e(0)ij будет оптимальным, хотя, быть может, не един-

ственным.

При необходимости по произвольному графу G(V,R,m1,m2,d) построим

орграф G1(V1,R1,m1,m2,d):

1. Вершине v V поставим в соответствие две различные вершины

vs,vf V1, при этом положим m1(vs )≡ m1(vf ):= m1(v). Очевидно, V1 = 2V .

2.Ориентированному ребру ruv R поставим в соответствие ориентиро-

ванное ребро ruv ru1svf R1 той же мультиразметки dru1svf := druv ; назначенную перевозку груза оставим прежней: m2(us;vf ):= m2(u;v).

65

3.

Неориентированное ребро

ruv R,

ruv ≡ rvu, заменим двумя ориентиро-

ванными антипараллельными рёбрами

r1 ,

r1

разных, в общем случае, разме-

uv

vu

ток

dr1

:= dr

, dr1 := dr , и согласно пункту 2

введём ориентированные рёбра

uv

vu

r1

,r1

R

разметок

dr1

:= dr ,

dr1

:= dr

и соответствующих заказов на

usvf

vsuf

1

usvf

uv

vsuf

vu

перемещение грузов: m2(us;vf ):= m2(u;v), m2(vs;uf ):= m2(v;u).

На полученном двудольном орграфе G1(V1 =Vs Vf ,R1,m1,m2,d)рассмотрим

транспортную задачу с долями в

роли источников Vs :={vs,i V1}

1 и стоков

V

i=

Vf := {vf ,i V1}iV=1. Её ограничения примут вид:

1. 0 ≤ xs,i; f , j ≤ d2e(0)s,i; f , j

; i, j 1,V – условие неотрицательности и ограни-

чения со стороны проводимости груза xs,i; f , j , отправленного из каждого пункта отправления vs,i Vs в каждый пункт назначения vf , j Vf по оптимальному маршруту e(0)s,i; f , j проводимости d2e(0)s,i; f , j .

2. ∑V (xs,i; f , j − xs, j; f ,i )≤ m1(vs,i ); i 1,V – условие неотрицательности запаса в

j=1

каждом пункте отправления vs,i для отправки во все заданные пункты назначения.

V

(vs,i )+

V

(vs,i,vf , j ); i

3.

∑

xs,i; f , j = m1

∑

m2

– условие доставки всего груза

1,

V

j=1

из каждого пункта отправления vs,i во все заданные пункты назначения vf , j .

V

(vf ,i )+

V

(vs, j,vf ,i ); i

4.

∑

xs, j; f ,i = m1

∑

m2

– условие доставки всего груза в

1,

V

j=1

каждый пункт назначения vf ,i из всех назначенных пунктов отправления vs, j .

V

5. ∑xs,i; f , jd1e(0)s,i; f , j i, j=1

→ min – критерий оптимальности в задаче минимиза-

ции транспортных расходов.

Транспортная задача 1-5 замкнута при необходимом условии

∑u,v V m2(u;v)= ∑u,v V m2(v;u)

и разрешима при достаточной проводимости рёбер графа G и достаточных запасах груза m1(u) во всех источниках u Vs . При исключении условия 2

транспортная задача решается стандартными приёмами. Укажем алгоритм учёта условия 2:

1) решим задачу при условиях 1,3,4,5 и проверим найденное решение на выполнение условия 2. Если оно выполнено, то исходная задача 1-5 решена. В противном случае переходим к следующему шагу;

66

				V

2) прибавим невязку	h:= max m1		(vs,i )−	∑	(xs,i; f , j − xs, j; f ,i ) ко всем значени-
	i, j 1,	V	j=1


ям запасов в вершинах графа m1(vi ):= m1(vi )+hV						и повторим стандартное реше-

ние задачи 1,3,4,5, удовлетворяющее дополнительному условию 2.

Если весь груз перевезён, поставленная задача решена с использованием лишь оптимальных маршрутов. Если же пропускной способности d2e(0)s,i; f , j не хватило хотя бы одного оптимального маршрута e(0)s,i; f , j , то преобразуем граф

G(V,R,m1,m2,d):

1. Удалим рёбра, насыщенные найденным потоком грузов xs,i; f , j :

d2rv1ivj − xij = 0.

2.Удалим при необходимости возникшие изолированные вершины.

3.Пересчитаем остаток грузов в каждой вершине m1(vi ):= m1(vi )+ ∑V (xij − xji )

j=1

и по каждому ребру m2(vi;vj ):= m2(vi;vj )− xij ≥ 0.

4. Найдём проводимость оставшихся рёбер d2rv1ivj := d2rv1ivj − xij > 0.

Пересчитаем матрицу A смежности вершин, матрицу B оптимальных расстояний и матрицу C упорядоченных по уровню оптимальности списков маршрутов удалением маршрутов, содержавших удалённые в пунктах 1 и 2 рёбра и вершины [2]. При этом меняется хотя бы одна верхняя оценка

d2e(0)s,i; f , j условия 1 транспортной задачи 1-5.

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

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

Литература

1.Котенко А.П. Матричный алгоритм Беллмана–Мура / А.П. Котенко // Управление организационно-экономическими системами: моделирование взаимодействий, принятие решений. – Самара: Самарский национальный исследовательский университет, 2013. – т.10. – С.33–37.

2.Докучаев А.В. Свойства графов задач сетевого планирования и управления / А.В. Докучаев, А.П. Котенко // Вестник СамГТУ. Серия: Физикоматематические науки. – Самара: Самарский государственный технический университет, 2010. – №5(21). – С.204–211.

Самарский государственный технический университет

67

УДК 004.023

Е. А. Кумагина, А. Н. Марков, Д. Е. Тюрин

ПРИМЕНЕНИЕ АЛГОРИТМА РОЕВОЙ ЛОГИКИ К РЕШЕНИЮ ЗАДАЧИ УПОРЯДОЧЕНИЯ РАБОТ НА ОДНОМ ПРИБОРЕ

В работе рассматривается алгоритм решения задачи упорядочения работ, основанный на методе «муравьиные колонии» (ACO, Ant Colony Optimization) [1,2]. Идея алгоритма заключается в последовательном приближении к оптимальному решению. Это конечный итерационный процесс, на каждом шаге которого происходит формирование допустимого решения.

Задача минимизации суммарного взвешенного запаздывания
Пусть					–
						множество работ, которые выполняются одним
прибором.	Каждая работа			,			, характеризуется	длительностью обслужива-
		= {1, 2, … ,		}
ния, директивным сроком						и коэффициентом		, определяюшим величину
штрафа за нарушение			директивного срока на единицу времени. Все работы дос-

тупны для выполнения сразу. В каждый момент времени прибор выполняет не более одной работы. Порядок обслуживания работ произвольный. Прерывания

в выполнении работ не допускаются. Требуется найти такой порядок выполне-

момент окончания

(

) = ∑

∙max (0,

) →

ния работ

)

, при котором минимизируется суммарное взве-

шенное

запаздывание

, здесь

–

= (

, , … ,

выполнения работы

,

.

Задача относится к классу NP-

трудных, известна как задача ТР5 [3], по-

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

Для задач комбинаторной оптимизации предложено множество итерационных алгоритмов, основанных на локальном поиске [4-6]. В данной работе предлагается применить алгоритм ACO к задаче минимизации суммарного взвешенного запаздывания.

Общая схема алгоритма ACO

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

Любой алгоритм ACO, может быть представлен в следующем виде [1,2]:

1.Инициализация переменных pheromone, оценивающих путь к пище;

2.Пока не выполнится критерий остановки повторять шаги 3-5:

3.Сформировать новый путь (получить решение задачи);

4.Уменьшить значение переменных pheromone на некоторый процент

(испарение);

68

5. Для переменных pheromon, соответствующих хорошему решению, увеличить значение на некоторую величину (усиление).

Параметры алгоритма

1.	– количество итераций алгоритма (групп муравьев).
2.	и – параметры, при помощи которых контролируется соотноше-

ние случайного выбора очередной работы и выбора, основанного на предыдущих состояниях системы.

3.	– параметр, определяющий способ постановки в расписание оче-
редной работы.
4.	– коэффициент усиления объема феромона.
5.	– коэффициент коррекции дополнительного объема феромона для
лучших расписаний итерации.
6.	– коэффициент испарения феромона.
Состояние следа		×
Начальное состояние следа моделируется матрицей			. Эле-
мент	работы		j-ой по
мент	этой матрицы характеризует выгоду от постановки =

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

Cостояние пути к пище (наличие феромона на следе) на каждой итерации

моделируется матрицей

. Элементы

– это накопленная

преимуществе выбора позиции для работы . В

статистическая информация( )о=

( )

×

(0) = 0, ,

( )

качестве начального состояния возьмем

= 1, .

Распределение вероятностей P(t)

ность

На каждой итерации t предложенного алгоритма вычисляется квадратная

( )

=

( )

×

. Элемент

( )

этой матрицы определяет вероят-

матрица

назначения работы

на j-ое место на итерации

и вычисляется по фор-

( ) =

∑

( )( ) , = 1, n, Ω,

муле:

Ω

0,

= 1, n,

Ω.

Здесь – множество работ, еще не включенных в расписание на итерации

,

, αΩ– коэффициент, определяющий важность стохастической состав-

ляющей, β – коэффициент, определяющий важность решений, построенных к

шагу .
Формирование пути
Первая работа выбирается случайно. Каждая следующая работа ,			,
ставится на позицию ,	= 2, , в зависимости от случайного значения	ру-
	= 2, , в зависимости от случайного значения	q (	Ω

69

Материал: Интеллектуальные информационные системы. труды международной научно-практической конференции. И73

Смотрите также: