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

нения

различных

методов

поиска и выбора одного

из

них для решения

каждой

конкретной

задачи

очеред­

ности

необходимо

строить

зависимость

в = /(7п,

п),

ко­

торая

является полной характеристикой эффективно­

сти метода.

В

предыдущих

параграфах данной

главы

описан

рода

«гибридизации»

детерминированных

и

статисти­

ческих методов.

Ниже строятся алгоритмы последовательного улуч­

шения

плана

(порядка

обработки

деталей),

сочетаю­

щие случайный выбор

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

с

анализом

вариантов ее

«исправления».

Рассмотрим формальную постановку задачи очеред­

ности

на матричной математической модели. Для

этого

введем

определения:

Путем на произвольной

матрице

\\йм\\ (І=

1, 2, ... , m,

k = \,

2 , . . . , n)

называется

сумма (m + n

1)

слагаемых,

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

слагаемое

равно

ап, последнее

атп

и любые

два

—рядом

втоящих

зует сумма

элементов

матрицы,

расположенных

по

«лестнице»,

ведущей из

ап

в

атп.

Критическим

путем

F(\\aik\\)

на

матрице ||а,-ь|| назы­

вается путь, который

не

меньше

любого другого

пути

на

данной

матрице, а

слагаемые

этого

пути

называют­

ся

критическими

элементами.

Рассмотрим множество Q, состоящее из п! матриц,

образованных

из исходной

матрицы

||аг -й || путем

про­

извольной

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

столбцов.

Каждый

элемент

этого множества Цая || может быть

однозначно охарак­

теризован

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

n—{iu-k,

•••,*«)>.

указываю-

щей порядок

следования

столбцов исходной матрицы,

т. е.

O l t j >

ali2

>•••> aUn

^ 2 І ! ,

# 2 t 2

>•••> а 2 і „

а"

=

щего

некоторой

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

а-элементов на

||ая || запись fa{n).

Вместо ^(Ца1 1 !!)

для простоты будем

использовать символ F(jt) либо

(если

не

возникнет

двусмысленности)

просто F.

Чтобы продемонстрировать удобство введенных по­

нятий,

покажем

оптимальность алгоритма

Джонсона

для задач очередности с матрицей

2Хп.

Оптимальность

алгоритма Джонсона.

Не

уменьшая

общности, можно

считать столбцы матрицы

2 Х п пе­

ренумерованными

так, что последовательность

1,2, . . . , , п

ственно

из алгоритма

следует, что всегда

найдется та­

кое

k(l^k^.n—

последний

невычеркнутый столбец),

что

і аіа^а^;

а1а^а2а'<

« і р ^ й з р ,

если

a<fi<k

(2.6.1)

I а 2 а ^ а 2 р ; a2a^ala;

а 2 р ^ а Ц } ,

е с л и

a > P > f e -

Пусть

критическим

путем

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

1, 2 , . . . ,

п является

F = S аи+

2

a2i

(2.6.2)

1=1

l=z

Чтобы доказать оптимальность исходной последо­

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

достаточно

показать,

что

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

последовательность столбцов i\, i2,...,

t n

содержит

путь

}~^F.

С этой

целью

рассмотрим

отдельно

случаи

z = k

z>k,

z<k.

При

z = k

определяем

для

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

г'ь к,...,in

такую

величину

у,

что

iy = k, и,

используя

(2.6.1)

и

(2.6.2),

немедленно

получаем

fy=

V

п

ац

>F.

2 а«

+

2

(2.6.3)

При

j=l

j = Y

1,2,

выделяем

из

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

множество

Q=(t,

t + l,

t+2,...,t

+ m),

где

,

( k,

если

a2k^aik

( « + 1 ,

если

a2ft>aift

iy

Далее

определяем

величину

у

так,

чтобы

явля­

лось последним

элементом

из

множества

Q в

ряду

h, Ї2,--.,іп.

Из (2.6.1) и (2.6.2) следует, что для опре­

деленной таким образом у неравенство (2.6.3)

всегда

выполняется.

При

z<k

множество

Q

определяем

так,

что

t = z

и t + m =

k,

если

aih<a2k

k—l,

если

aik>a2k,

а у является индексом

первого

в

ряду i\, i2,...,

i n

эле­

мента из Q. Нетрудно определить,

что и в этом

случае

(2.6.3)

также имеет

место.

Из

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

этих

случаев

делаем

заключение,

что

алгоритм

Джонсона

определяет

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

столбцов

для матриц

2 Х « .

т,

п ~>2,

Для

задаче

матрицами

Ца^-Цтп, имеющими

в настоящее время неизвестен практически

реализуе­

мый метод

нахождения

оптимальной

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

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

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

я =

i2,...,

in) и

соответ­

ствующая

ей

матрица

||ал |].

Используя

алгоритм

Фор­

да

[2.26],

определим F(n)

и

выпишем

критическую

по­

следовательность элементов

(если

критических

после­

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

несколько,

то выбираем

любую

из

них). В указанной последовательности

отметим номе­

ра

столбцов,

которые

встречаются

более

одного

раза

(т.

е. столбцы,

содержащие

более чем

один

элемент

из

критической

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

Я* — (t'l, І2,'">Ік-х-1, 'ft' ik-x+i,"',

ih-U ih-x, 6t+l>"' ' г 'п) •

Тогда

для любой

матрицы,

у которой п^ат,

име­

ет место

неравенство

P{F{n*)<F(n)}<

***

•

(2.6.6)

Например,

для

матрицы

10x100

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

двух

случайно

выбранных

рядом

стоящих столбцов

может улучшить исходный результат в

среднем

менее

чем один

раз на пять испытаний.

Из

описания

процедуры

разбиения

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

ности

на

блоки

ясно,

что любому пути

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

Теорема

3.

Пусть критическому

пути

на

матрице

||ая || соответствует такая

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

блоков,

что элементы iu

и iv принадлежат блокам, определяемым

аи

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

Яі получена

из я транспози­

цией элементов l ' u и iv, то

F(ni)<F(n)

= > a a t i U - a a

u i v

+ао

-аа

.

> 0

а,,г„

(2.6.7)

(А=>В

обозначает, что из

А

следует

В).

Из

(2.6.5) и

(2.6.7)

следует,

что

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

Яі

может

оказаться лучше,

чем я, только

в том случае,

если элементы

\ и и і„ расположены

в разных блоках и

..

—а„ .

+ а

.

а

. > 0 .

а аиги

au\v

а « Ь

— «V»