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

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

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

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

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

Добавлен: 11.04.2024

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

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

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

Как будет показано ниже, при реализации алгорит­ ма поиска с использованием инверсной метрики при­ дется вычислять некоторые из чисел (г, q). В зависи­ мости от параметров задачи и возможностей вычисли­ тельной машины можно по-разному пользоваться соот­ ношениями (2.5.1), (2.5.2), (2.5.3). Можно, например, каждый раз непосредственно вычислять числа (г, q), или предварительно составить таблицу некоторых зна­ чений (г, q), или вычислять их приближенно, пользуясь формулой (7.5.3.) и асимптотической формулой Стер­ линга.

Используя полученные выше свойства метрики, по­ строим алгоритм, позволяющий выбрать с равной ве­

роятностью векторы

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

из

/^-окрестности

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

я = ( я ь

Я2,

. . . , я т ) .

Из опреде­

ления /^-окрестности вектора

следует,

что

случайный

вектор я* = (яг 'ь я{2, • • •, лЛп)

равномерно

распределен

в /^-окрестности вектора я тогда и только тогда, когда

каждая

компонента я*3- вектора

я* равномерно распре­

делена

в

/^-окрестности

Л) — соответствующей

компо­

ненты

вектора я. Поэтому достаточно

указать

алго­

ритм равновероятной выборки

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

из

R-OK-

рестности

произвольной

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

При

этом

мож­

но ограничиться /^-окрестностью нуля, так как любую

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

я = ( а ь

а2,...,ап)

с

некоторой

ее R-OK-

рестностью можно

топологически

отобразить

в нуль с

его /^-окрестностью,

установив

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

 

 

Otj

 

н ( £ =1, 2,...,

п).

R

/--окружно­

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

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

из

 

 

—

 

 

 

 

 

 

стей (0<r^ZR),

а

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

в

свою

очередь, со­

стоит из [г, п—1) перестановок; среди них содержит-

ся 2 (г, п—2) перестановок, индекс которых НаЧИНа-

г - І

ется с а г, в свою очередь, среди этих перестановок со-

R—а,—<х.2

(г, п—3) таких, индекс

которых имеет

на

держится 2

втором месте

«г, и т. д.; множество

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

ин­

дексы которых начинаются с чисел

щ, а 2 , . . . , а,,

со­

стоит из

 

 

 

Н- 2і а,- j = i

2 (r,n-i-\)

7*

99

перестановок. Следовательно, чтобы обеспечить равно­

мерную

 

выборку

 

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

 

из

^-окрестности

ЗТо,

можно

применить

следующий

поэтапный

алгоритм.

Этап

1.

 

Делим

отрезок

(0,1)

на

R

частей

в отно­

шении

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

H j - l

 

 

ПІ):

Я 4

- 2

 

 

 

2

 

 

 

 

1

 

 

 

2

 

(г,

2

(г, п і ) : - :

2

 

{г,п{)-

 

2

(г,пх),

 

Г=1

 

 

 

Г=1

 

 

 

Г=1

 

 

 

Г=г1

 

 

 

 

 

 

где

ПІ = П—

1

и

Ri = R.

 

 

 

 

 

Этап

2.

 

После

того

как

отрезок

 

(0,1)

разделен

на

R частей,

генерируем

go — случайную

 

величину,

равно­

мерно

распределенную

на

(0,1).

Если

| 0

попадает

на

1-й интервал отрезка

(0,1),

то

полагаем

aj = г—1.

 

Этап

3.

Полагая на

этапе

1 Rj+i

= Rj—ctj, п^\

= п^—-1

( 1 < / < п — 1 )

и повторив этапы

1 и

2,

получим ctj+i.

 

Этап

4.

Построив

полностью

индекс

(аь аг,...,

an-i),

находим

по

нему

соответствующую

 

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

 

Проведенные

на

ЭВМ

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

показали,

что

эффективность поиска существенно зависит от свойств

метрики

и, в частности, от возможностей ее для

более

глубокой

детализации структуры

исследуемого

про­

странства.

 

 

 

 

 

 

 

Так,

например,

при

организации

статистического

поиска с

помощью

цепной

и

лексикографической

мет­

рик для

задачи

календарного

планирования

mXnXl

(I — количество

операций

каждой

детали) количество

недействительных

планов

на

один

действительный

оказалось в цепной ме.трике в 5—б раз больше, чем в

лексикографической

метрике, при одних

и

тех

же

^-окрестностях (расчеты проводились для

R = 3).

Это

указывает на

то, что эффективность поиска

с приме­

нением лексикографической метрики в 5—6

раз

боль­

ше, чем при

цепной

метрике. Перечисленные

ранее

преимущества инверсной метрики по сравнению с цеп­

ной

и

лексикографической

позволяют ожидать боль­

шую

эффективность последней.

 

Поиск

с пересчетом

вероятностных

характеристик.

Метод

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

случайного поиска,

связанный с

пересчетом

вероятностных

характеристик

случайного

расписания, может быть предложен для решения сле­

дующей задачи

календарного планирования. Имеется

m одинаковых

станков, на которых нужно обработать

два типа деталей, причем число деталей каждого типа

равно

tij

(/=1,2). Каждая деталь должна

пройти об­

работку

на одном станке и только один раз. Требует­

ся найти

оптимальное расписание. Эта

задача

матема­

тически

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

 

 

 

В

п=

(п, + я2 )-мерном

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

задано

множе­

ство

точек

с булевыми

переменными,

т.

е.

D = { X } ,

где Х={х\...хп),

ХІ = 0 или 1 означает,

что

на

освобо­

дившийся станок запускается деталь 1-го или, соответ­ ственно, 2-го типа. Тогда вектор X однозначно опреде­

ляет

некоторое

расписание

запуска

деталей.

 

 

 

На множестве

D

задана

некоторая

функция

К(Х)—

значение цикла. Тогда алгоритм решения

задачи

мож­

но

представить

в

следующем

виде.

 

 

 

 

 

 

 

1.

Задаем

некоторое

чисто

^о-

 

 

 

 

 

 

 

2. Выбираем

за

v-e

расписание

Xv=

(xvu

xv2,...,

xvn)

 

такое, что

 

К(Х»)>і0.

 

 

 

 

 

 

 

 

 

где

3.

Вычислим

pv

= X

Я ( Г ) - ; „

 

д ^ о ,

 

 

 

К выбирается

из

условий

улучшения

сходимости.

 

 

 

 

 

 

 

 

 

 

 

—

 

 

 

 

 

 

4.

Моделируем

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

| v

+ ! =(

 

 

),

для

которого

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

+1_

|

х{*

с

вероятностью

1 —pv

•

 

 

 

 

 

t

\

l—Xiv

с

-вероятностью

p v

 

 

 

 

 

Реализацию

£ v + 1

обозначим

через

Xv+1

 

 

 

 

5. Вычислим K(Xv+])

и сравним с до­

 

 

 

 

вели K(Xv+l)>f0,

 

то

переходим

к

п.

2.

 

 

 

 

 

.6. Запоминаем

Xv+X; уменьшаем

t0

так,

чтобы

io^K(lv+l)

и переходим

к

п. 4

 

 

 

 

 

 

 

 

Признаком

окончания

процедуры

является

v>N,

где

N задано,

и за оптимальное

принимаем

расписание

Xv+l.

 

Процесс

моделирования

 

Xv,v=l,...,N

 

 

можно

представить

как

случайное

блуждание

в

области

D,

отвечающее

некоторой

марковской

цепи.

Состояния

X,

для которых

K(X)^t0,

 

являются

поглощающими.

Известно, что

вероятность

попадания

из

любого

со­

стояния конечной неприводимой марковской цепи в поглощающее состояние равна единице,

Рассмотренный метод применялся для решения за­

дачи

со

следующими

исходными данными [2,9].

 

т = 7,

« 1

= 115,

я 2 = 20, % = 3.

 

исследовалось

На

ЭВМ

«БЭСМ-ЗМ» за минуту

около

60

расписаний.

Цикл,

соответствующий

наилуч­

шему

расписанию,

составил

/( = 720

час. Ранее

за ме­

сяц

(К —717

час.)

на

т = 7 выполнялось

число

деталей

П ! = 93

и

п2

= 20.

 

 

 

 

 

 

 

 

 

§ 2. 6. Вероятностные методы решения

 

 

 

 

одномаршрутных задач очередности

 

 

 

 

 

с прямоугольной матрицей

 

 

Выше, в

§ 2.2

настоящей

главы,

мы

уже отмечали,

что под задачей очередности в теории расписаний по­ нимается следующая проблема. Имеются т различных станков, на которых необходимо обработать п различ­

ных деталей.

Деталь

di(i=

1,2,..., п) характеризуется

ВеКТОрОМ di—

(til, ti2,

. . . ,tim)

, ГДЄ t{j — ВреМЯ обработ-

ки ї'-й детали на /-м станке. Необходимо найти такой порядок обработки деталей, при котором время завер­

шения

обработки последней

детали

достигает

миниму­

ма при условии, что последовательность

обработки де­

талей

на всех станках одна

и та же

и

каждая

опера­

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

Для задач очередности определенного объема пре­

имущество

некоторого

метода

оптимизации проявляет­

ся в том,

что либо этот

метод

за фиксированное время

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

Эффективность

статистических

методов

оптимизации,

как правило, сравнивают

с чисто случайным поиском

(метод Монте-Карло), который

в

этом

случае

стал

эталоном.

 

 

 

 

 

 

Можно распространить эту методику на все пред­

лагаемые методы

решения

задачи

очередности.

Если

эффективность метода Монте-Карло принять за

едини­

цу, то эффективность какого-нибудь

другого

метода

можно считать равной 9

единицам;

эквивалентные

решения той же ЭВМ могут быть получены во втором случае за время (в среднем) в в раз меньшее, чем в

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