Файл: Голенко Д.И. Статистические модели в управлении производством.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 11.04.2024

Просмотров: 159

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

ствует!), соответствующий точке X, и в итоге найдем зна­ чение целевой функции.

Целевая функция К, заданная на множестве распи­ саний, определяет некоторую функцию F на ограничен­ ном множестве целочисленных точек m-мерного прост­ ранства

K(A)=F(X)

•

At=D

Х(=Н

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

так как помимо окрестности

любого

фиксированного

плана

здесь имеет смысл говорить о направлении движе­

ния в

пространстве

планов; при этом поиск ведется в Н

с целевой функцией

F. Схема

такого

направленного по­

иска представляется следующим образом. Из некоторой

случайно выбранной точки Х0^Н

делается

а

случайных

проб, т. е. определяются

значения

F(X0 + zli)

целевой

функции в

а (і = 1, 2,...,

а) точках

Xi = X0

+ zlil,

где | j —

случайный

m-мерный вектор

с равномерно

 

распреде­

ленными на

[—1,1] компонентами;

 

z — некоторая

посто­

янная,

заранее выбранная

величина. Затем

отбирается

точка

Xj, которой соответствует

минимальное

F;

точки

Хо и Xj определяют вектор W] — ось m-мерного

гипер­

конуса Tj с углом раскрытия W и вершиной

в точке X;.

Дальнейшие

а проб делаются

в пределах

построенного

гиперконуса из точки Ху, снова отбирается «лучшая» точ­ ка и вершина конуса переносится в отобранную точку, а вектор W{ меняет соответствующим образом свое на­ правление. Если для трех последующих точек на траек­

тории движения Xj-2, Xj-\ и Xj

выполняется условие

F(Xj-2)>F(Xi-i)

\

FiXj^KFiXj)

J

то точка Xj-i отмечается как «подозрительная» на мини­ мум, т. е. в ней достигается локальный минимум или близкое к нему значение.

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

F(Xj-2)<F(Xj^) 1

F(Xi^)>F(Xj) )

угол раскрытия восстанавливается. Движение прекра­ щается только после попадания очередной точки за уста­ новленные пределы.

 

Для вычисления F(X)

необходимо от X=(Xh

Х2,...,

Хт)

ПереЙТИ

С П О М О Щ Ь Ю

алгоритма

ВЫЧИСЛеНИЯ Я{ =

= N~l(Xi) к вектор-перестановке я = ( я ь

яг, ... ,

я т ) и за­

тем

построить

сетевую модель. Расчет

сетевой

модели

выполняется с помощью таблиц длительности всех опера­ ций и последовательности их выполнения. Таблица после­ довательности состоит из двух частей — постоянной и пе­ ременной, при этом постоянная часть включает техноло­ гические последовательности выполнения операций по всем деталям, а также связи операции условного начала О н нулевой "длительности со всеми первыми операциями деталей и связи всех последних операций обработки де­ талей с операцией О к условного конца; переменная часть таблицы определяется найденной в соответствии со слу­ чайной точкой X вектор-перестановкой я. Для расчета сетевой модели используется алгоритм Форда для сети без событий, который дополнен алгоритмом для обнару­

жения

циклов.

Если целевой функцией плана является

минимальное

время выполнения всех работ, то

 

 

 

K(A)=F(X)=TKP

 

 

 

 

 

вычисляется одновременно с Л.

(т. е. точке X не соот­

При обнаружении циклов в сети

ветствует

план, совместимый

с технологической

матри­

цей), точка X

отбрасывается

и целевая функция

опреде­

ляется для следующей точки.

 

 

 

 

 

 

Инверсная

метрика [2.8]. Пусть

яі=|(і'ь іг, • • ., in), яг

=

= {І и

І2, • • •> in) — Две

произвольные

перестановки

11

объектов;

ik, к

(k>l)

•—произвольные элементы

переста­

новки п\.

Если в перестановке яг найдется пара элементов

j p , j q , такая, что ik=jp,

ii = j q и p<q,

то будем говорить, что

пара j p ,

j

q образует

инверсию относительно

перестановки

щ. Число

всех

инверсий

перестановки

яг

относительно

яі определим как расстояние между этими перестановка­ ми р ( я ь яг).

Покажем, что введенное расстояние удовлетворяет аксиомам метрики 1—3:

1) р(яі, я 2 ) = 0 тогда и только тогда, когда любые два элемента расположены в обеих перестановках в одина­ ковом порядке, т. е. когда яі = яг;

 

2)

если ift = /p,

ii = j q ,

то элементы

ik,

U образуют

ин­

версию

относительно

яг тогда

и только тогда, когда

/ р и

j q

образуют

инверсию

относительно

я ь

следовательно,

р ( я ь

яг) =р(яг, Яі);

і2,...,іп),

 

 

 

 

 

j2,...,jn),

 

 

 

3)

пусть

Я і = : ( І Ь

 

Я 2 = ( / ь

 

я 3 =

=

(&ь &г, • • .,kn)

и ik = jp, h = jq. Если

пара

Й, іг образует

инверсию относительно

яз, то она

либо

образует инвер­

сию относительно Яг, либо пара /

р

,

j

q образует

инверсию

 

 

 

Ї

 

 

относительно

я 3 . Значит

каждой

 

инверсии

перестановки

яі

относительно перестановки

яз соответствует

инверсия

тех же элементов

в Я [ относительно яг или же в яг отно­

сительно яз, откуда следует

 

 

 

 

 

 

 

 

 

 

 

 

 

р(яі,

я 3 ) ^ р ( я і ,

я 2 ) + р ( я 2 , Яз)

«

 

 

 

Легко видеть, что р(яі, яг)

может принимать

все цело­

численные значения от 0 до

п ^п ——.Перестановку

я 0 =

=

(1, 2, ... , п)

будем

впредь называть нулем пространст­

ва

перестановок,

^-окрестностью

 

 

вектор-перестановки

я = ( я і ,

Яг, • •., Jtm )

будем называть

множество

всех

век­

торов

я * = ( я / ,

Л2,...,п1т),

 

для

 

которых

р(я,-,

nlj)^R

при / = 1 , 2 , . . . ,

т.

 

 

 

 

 

 

 

 

 

 

 

 

 

Согласно

инверсной

метрике,

 

близость

перестановок

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

ства имеет больший набор ^-окрестностей, чем

в цеп­

ной, так

как

максимальное

удаление между

точками

пространства

П

'

 

п

(п— 1)

 

как в

 

составляет — ^ —- 'в то время

цепной метрике

 

оно

равно

п

1.

Инверсная

метрика

свободна

также

 

от

основного

недостатка лексикогра­

фической метрики: расстояние—между двумя

переста­

новками

не зависит

от нумерации

деталей.

 

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

вектор-перестановки

из

заданной ^-окрестности; все

дальнейшие выкладки проводятся в этих целях.

Пусть я'о — произвольная

перестановка;

назовем

окружностью радиуса

г,

или

r-окружностью

с центром

я'о, множество всех перестановок я, обладающих свой­

ством Q (Яо Я) =Г.

Чтобы выяснить, как распределяются перестановки по окружностям различных радиусов, установим взаим­ но-однозначное соответствие между всеми перестанов­

ками п

символов

я=

(й\, а,2, ..., ап) и

целочисленными

векторами вида

(щ,

аг, ...,

а п - і ) , где

0 ^

сч^п—і

(і —

= 1, 2,..., п—1).

Соответствие строится

таким образом,

чтобы а, было равно количеству инверсий,

образуемых

членом

а, с последующими

членами

перестановки

я.

Указанный целочисленный вектор назовем индексом

перестановки я. Например, перестановке

я = (8,3,1,5,4,

2,6,7) соответствует индекс (7,2,0,2,1,0,0).

Если задан

индекс перестановки, то соответствующая ему переста­

новка

восстанавливается

следующим

алгоритмом:

Шаг

1. Яі = аі + 1;

в

ряду

чисел

1,2, ...,п зачеркива­

ем число «ь

полученную

последовательность

1,2,...,

«і—1, «1 + 1,...,я обозначим

Аі,

 

 

 

Шаг 2. Находим

а2

как

(аг+1) - е

по счету

(по по­

рядку)

число

последовательности

Л ь

затем

вычерки­

ваем число а2

из Лі

и получаем Л г;

 

 

Шаг і. Находим а* как (<ХгтИ)-е по счету число последовательности Л^ _ ь затем вычеркиваем а* из А^ и получаем Ас

Шаг п. ап =

Ап-\-

Пусть

индекс

искомой пере­

Рассмотрим

пример.

становки

равен

(3,6,0,2,0,2,0).

 

 

 

 

 

Тогда

в соответствии

с алгоритмом

имеем:

1)

а1 =

3 + 1 = 4

Л1 = 1,

2,

3,

5,

6,

7, 8

2)

« 2 = 8

 

Л 2 = 1 ,

2,

з,

5,

6,

7

3)

а 3

= 1

 

Л 3

= 2,

3,

5,

6,

7

 

4)

а 4

= 5

 

Л 4

= 2,

3,

6,

7

 

 

5)

« 5 = 2

 

л 5 = з , 6, 7

 

 

 

6)

а6 = 7

 

л 6 = з , 6

 

 

 

 

7)

« 7

= 3

 

 

 

 

 

 

 

 

8) а 8 = Л 7 = 6 Итак, я = (4,8,1,5,2,7,3,6).

Если перестановке я соответствует индекс (си, а2 ,. • •, (Хп-і), то это значит, что количество инверсий, обра-

7. Д . И . Голенко

97

зуемых

перестановкой я

относительно

перестановки

я0 ,

равно 2

сц .

 

 

 

 

 

Так

;

і

инверсий в перестановке

определяет

 

как

число

ее

расстояние до

нулевой

перестановки

и в

то же вре­

мя из любой окрестности перестановки яо соответствую­ щей перенумерацией объектов можно получить окрест­

ность любой

перестановки

я,

то справедливо

следую­

щее

утверждение:

 

 

 

 

 

 

Каждая г-окружность содержит столько перестано­

вок,

сколько существует

различных

представлений

чи-

ела г в виде суммы г=

і2-Л

т,

(О^щ^п—і)

с учетом

порядка

слагаемых.

Действительно, каждой

перестановке из г-окружно-

сти

взаимно-однозначно

соответствует индекс

(<хь

аг,

 

 

 

 

я - 1

щ = г, а

 

 

 

. . . , a n - i ) ,

для

которого

2

каждый такой

ин-

деке есть разложение числа г в сумму г= 2 a, ( 0 ^ i=i

^ a 2 - ^ n — t ) .

Будем обозначать через (г, q) количество разложе-

ний числа г

 

 

ч

а,

с учетом

порядка

слагаемых.

в сумму 2

 

 

 

 

i=\

 

 

 

 

 

Используя

стандартные

методы

комбинаторного

ана­

лиза, нетрудно доказать следующую теорему:

 

величину

(г, q)

можно

определить из рекуррентных

соотношений

 

 

 

 

 

 

 

 

(г,

q) = (r,

7 - І ) +

( г - 1 ,

q-l)

+ ...

+ (r-q,

q -

l ) -

или

 

 

 

 

 

 

 

 

 

(2.5.1)

(г,

g) = (r-l,

q) + {r, q-l)-(r-q-l,

 

q-l)-

 

(2.5.2)

с граничными

условиями

 

 

 

 

 

 

 

 

(0,7)

= 1,

 

(-r,q)=0

 

 

 

или

вычислить

по формуле

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(2.5.3)

 

 

 

а \

 

а{а-\)-(а-Ь+\)

 

 

Ь' ьГ~-

Смотрите также файлы