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

наруживается лучший вариант, то далее второй

блок

сравнивается последовательно с каждым

из следующих

за ним блоков и т. д., пока не произойдет

сравнение

пред­

когда обнаружена лучшая перестановка,

которая затем

в таком же порядке анализируется, либо

после оконча­

Фигурирующие в описании специальные ячейки памя­

ти

имеют следующие условные обозначения:

М-—массив, содержащий элементы исходной матри­

цы

lloijll;

у0 — ячейка,

в которой хранится величина F— про­

межуточное значение критического пути;

у\ — рабочее

поле перестановки, с помощью которой

была получена величина F;

У2 — ячейка,

содержащая

значение

Fy —наимень­

шую из достигнутых величин критического пути;

уз —• поле, сохраняющее перестановку, на которой

по­

лучено значение Fy ^;

Y4 — ячейка,

отведенная для счета количества проана­

лизированных вариантов (случайных

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

Y5 — ячейка, в которую заносится

величина К — коли­

чество блоков в перестановке из у и

уе — ячейка,

сохраняющая

величину

і — номер

пер­

вого сравниваемого блока;

У7 — ячейка,

сохраняющая

величину

/ — номер

вто­

рого сравниваемого блока;

Y8 — ячейка,

сохраняющая

номера

переставляемых

столбцов.

Действия операторов заключаются в следующем:

Л[ — записывает

в М исходную матрицу \\а^\\,

в ячей­

ку

у2 заносит число,

которое

заведомо

больше

любого

Ф2 — формирует случайную перестановку п=

t2 ,

...,

i7l),

которая и засылается

с признаком

нуль в

уи

М

Л 3

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

я

из

YI и

исходной

матрице

из

определяет

критический

путь F(n)

(прямой ход алго­

ритма Форда). Величина F посылается в YO;

РА — проверяет условие

F<.F^

(т. е. F

сравнивается

с содержимым

ячейки у2).

Если F<F-i2,

то

управление

передается оператору As,

при

F^F^—оператору

Ре;

А5

— величину F засылает

в ячейку

Y2, а

последова­

тельность я — в рабочее .поле уз;

Лз

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

из Yi с

едини­

цей. Если признак равен единице (это означает, что за­

писанная—

в yi перестановка получена транспозицией), то

передает

управление Ра, если же признак

равен нулю

(т. е. перестановка является случайной), то —

Pf,

Р 7 — проверяет условие F — Fy.2>6,

где

б — наперед

за; при

6 = 0 алгоритм практически мало

отличается

от

слепого

поиска; при F — Fy2^.6

управление передается

Рі2, в противном случае Ф2 ;

Р 8 — проверяет условие F<Fyo.

Если

F<Fy0

( F 7

q —

элементов, указанных

в ув",

ет

—

1) определяет

критическую последовательность

Аи

блоки; 2) в ячейку ys записывает величину

К — коли­

чество

блоков; 3)

в ячейку

Y6 и Y7 записывает

единицы;

Pi2

— проверяет условие j<K,

где величина / — содер­

жимое

ячейки у7,

а К — ячейки

у5. Е С Л И

j<.K,

то управ­

ление

передается

на А ] 4 ,

в

противном

случае — на Pi 3 ;

Л з

проверят

условие

i<cK

1, где

і — содержимое

ячейки—ув, а К — ячейки ys-

Если условие выполнено, то

—

управление передается на Ai5,

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

управления передается на К19,

Л и — увеличивает величину /

(из у7 )

на

единицу;

Л 1 5

1)

в ячейку Y7 засылает

величину

j — i + 2,

где

содержимое Ye! 2) увеличивает і на единицу;

і —Л 1 6

—— выделяет и сравнивает блоки, порядковые

номе­

ра которых і и / указаны в ячейках

у& и у7. Для

этого:

1) по і и / определяются соответствующие

(см. Аи)

зна­

чения

а,і и ау,

2) последовательно для

каждого элемента

tj из блока

ш

вычисляется

Л я

'

{U)=aat-

II

—azt-

и

on-

(Xj

-

рєделяется

элемент t*, для

которого AaJ

достигает

мак­

ется величина AaJ

(tj) =аа-.(.

—aa.t.

и находится

эле-

Й£

J J

і

J

мент

t* , для которого эта величина

наибольшая

(если

таких

элементов несколько, то можно взять

любой из

них);

вычисляется

A(i\, t))=A^

{ft)+A%

{t*).

Pn

— проверят

условия

A(t*,

t*

) > 0 .

Если

Л ^ О ,

то путем транспозиций любых элементов,

содержащихся

в блоках т и а,,

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

невозмож­

но и управление

передается

на Р\2,

если

Л > 0 ,

то — на

Л 1 8

— производит транспозицию

элементов

t'l

и

t'*} а

ница» и заносит в у8 элементы t*

и

t*;

/Сіз •— увеличивает значение

п — количества

проана­

лизированных вариантов на единицу;

Р2о—проверяет

условия n<N,

где п из Y4> а

N — за­

данное количество анализируемых

вариантов;

Монте-Карло с

использованием данного

алгоритма,—

резко возрастает

с ростом

отношения— . Для

m

=S~o,

r

r

r

m

n.<10

и

A/ = 20

получена

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

этого

отноше-

—

дач

очередности, как правило, —

выражается двузнач-

т

ным

числом,

то преимущество

метода

транспозиций в

этих

случаях

становится

очевидным. Вопросы

выбора

величин

JV И б в общем

случае

зависят

от размерности

задачи,

располагаемого для ее решения

времени

и целе­

сообразности

улучшения

достигнутого

результата.

В заключение параграфа следует отметить, что метод

транспозиций

является

достаточно

эффективным для

матриц, у которых количество столбцов

в несколько раз

превышает количество строк. Если

т соизмеримо

с п, то

ческих столбцов. Дл я отсеивания

неперспективных

вари­

антов в этом случае можно использовать результаты

сле­

дующей теоремы.

Теорема

4. Пусть

элемент

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

л —

= (іь к , - - - ,

i n )

разделяет

блоки

(ih-j,

... , ik-l)

и

{ik+u • •.,

ik+t)®1,

тогда

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

Яі =

— (Ч. • • • . ih-U

ih+U

• . . , tft+r,

ih,

ih+r+\,

. . . , in),

Г Д Є О ^ Г ^ t,

И Я 2 = ( г ь . . . ,

ih-j+r-l,

ih, ik-j+r,...,

ih-1, 4 + 1 , . . . ,

i n ) ,

где

0 ^ > < / , имеют место соотношения:

^(.n,)<f.(n)=>

2 + Г

( f l a , i j

- a a l i j ) > 0 ;

(2.6.8)

F(n2)<F(n)

= >

S 1

( a a i i j

- a a 2 i j ) > 0 .

(2.6.9)

j—h—i+r

Вычислительная процедура метода перемещения кри­

тических столбцов,

как и

метода

транспозиций,

заклю­

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

правой

части

(2.6.8) (соответственно ( 2 . 6 . 9 ) ) ,

а затем

осуществляется

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

л к я г

(соответственно,

яг) и

определение критического

пути

для яі

(либо Яг). Этот .

блоки. В первом случае

по описанной схеме

анализиру­

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

(т. е. Яі либо яг), а во втором —

генерируется случайная

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

элементов