Файл: Голенко Д.И. Статистические модели в управлении производством.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.04.2024
Просмотров: 170
Скачиваний: 0
гов вычисления обрываются и фиксируется последова тельность, на которой был достигнут наилучший резуль тат. Для матриц, у которых т < й < 3 т , вероятно, имеет смысл проводить анализ каждой последовательности ме тодом транспозиций и методом перемещения критиче ских столбцов одновременно. Такого рода вычислитель ная процедура увеличивает «глубину» анализа критиче ского пути, но объем вычислений при этом значительно возрастает. Вопросы целесообразности совместного ис пользования описанных алгоритмов и характер такого сочетания требуют дополнительного исследования. В опи санных выше алгоритмах каждая новая случайная пере становка из <п элементов формируется так, что ее вероят ность равна — . Естественно, что любой из эффективных
методов целенаправленного случайного выбора может повысить эффективность предлагаемых методов. Целесо образно, например, чтобы оператор Ф 2 реализовал цеп ной метод Монте-Карло либо использовал опробованные метрические подходы, изложенные в § 2.5 настоящей главы.
§ 2. 7. Вероятностные методы решения одномаршрутных задач очередности с матрицей, близкой к квадратной
В данном параграфе будет рассмотрен вероятностный подход к решению одномаршрутных задач очередности. При оптимизации некоторого функционала, построенного на исходных параметрах задачи, наибольшего эффекта достигают те методы, которые максимально используют конкретную информацию о данном объекте.
Рассмотренные в предыдущем параграфе статистиче ские методы решения одномаршрутных задач достаточно
эффективно |
использовали информацию, сосредоточенную |
||
в исходной |
матрице, однако их применение ограничилось |
||
задачами, для которых |
п^$>т. При n = m и п<т эффек |
||
тивность этих методов |
снижалась до величины 6 = 1 , |
т. е. |
|
была равна эффективности метода Монте-Карло. |
|
||
Вероятностные методы решения одномаршрутных |
за |
дач, описанные ниже, свободны от этого недостатка, од нако степень приближения к оптимуму для таких мето дов хуже, чем для методов, рассмотренных ранее. В связи
с этим возникает следующая схема применения вероят ностной модели решения одномаршрутных задач. Снача ла может быть получено некоторое хорошее решение ве роятностным методом, а затем данное решение уточня ется методом транспозиций либо методом перемещения критических столбцов [2. 14].
Класс вероятностных методов решения, к которому мы переходим, прямо и на первом шаге алгоритма ис пользует информацию, сосредоточенную в исходной мат рице, что отличает эти методы от рассмотренных выше алгоритмов статистического поиска, где исходная инфор мация использовалась косвенно и по частям, так что на каждом шаге рассматривалась информация о путях, число которых было равно выбранному количеству проб.
Сформулируем общий подход к решению задач оче
редности вероятностными методами. |
|
|
|
|
||
Рассмотрим |
некоторые |
числовые функции |
Х(и) |
и |
||
У {и), заданные |
на конечном множестве |
элементов |
U. |
|||
Элементами и множества |
U(u^U) |
могут |
быть |
всевоз |
можные подмножества некоторого фиксированного мно жества, в частности перестановки из п элементов либо другие комбинаторные объекты. Пусть между числовы
ми функциями |
Х(и) |
и |
Y(u) |
существует |
статистическая |
||||
связь, которая |
выражается в |
существовании некоторой |
|||||||
монотонно возрастающей (убывающей) функции f, |
такой, |
||||||||
что для некоторого случайного |
значения « є [ / |
при фик |
|||||||
сированных и достаточно малых |
6> 0 и е > 0 |
имеет |
место |
||||||
соотношение |
|
|
|
|
|
|
|
|
|
P{\Y(u)-f[X(u)]\<S}>l-E |
|
|
• |
|
|
(2.7.1) |
|||
Предположим, что известна величина иу*, |
доставляю |
||||||||
щая минимум (максимум) функции Y(u) (IK=U), |
|
и для |
|||||||
любого а существует |
эффективный метод |
выделения из |
|||||||
U такого подмножества |
UG, для которого |
|
|
|
|
||||
|
\Y(u)-Y(u;)\^a |
|
|
|
|
|
|
||
И |
|
U^Ua |
|
|
|
|
|
|
|
|
| Y(u) |
— У(и*) | > а • |
|
|
|
( 2 J - 2 ) |
|||
Из (2.7.1) |
и (2.7.2) |
следует, |
что элемент |
|
|
при |
|||
котором достигается |
экстремум |
функции |
Х(и), |
с |
веро- |
(S. д. и. Голенко
ятностью |
р > 1 — - в принадлежит множеству |
Uа, |
где |
а = |
|||||||
= 26. Для этого случая имеет место оценка |
|
|
|
|
|||||||
|
|
X(u')>f-*(Y(u*y)-8) |
|
|
.. |
|
|
(2.7.3) |
|||
Другими словами, |
элемент |
иу* |
является |
приближен |
|||||||
ным значением величины их*, |
а элемент их* |
находится в |
|||||||||
некоторой |
окрестности |
(имеется в |
виду, |
что топология |
|||||||
на U вводится с помощью множеств Ua) |
элемента |
иу*. |
|||||||||
Методика |
поиска их* |
в этих условиях |
заключается в |
||||||||
выделении |
и |
просмотре |
последовательности |
подмно |
|||||||
жеств Uai, |
Ua2\Uai,.. |
.,Ua:\ |
иак_г |
, |
где |
а і < а 2 < а з < |
|||||
< . . . < « * |
и, |
следовательно, |
Uai cz(7a 2 |
а ... |
aUaic. |
|
Воз |
можен и другой подход, при котором используется метод случайного поиска, осуществляемого в окрестности Un, где величина а определяется в зависимости от /, необхо димой точности и других факторов. Чтобы воспользовать ся описанным подходом к решению задач очередности, необходимо прежде всего найти функцию, обладающую свойствами, аналогичными Y(u).
Для выяснения этого вопроса рассмотрим прежде всего метод решения задачи о перестановке, минимизи рующей математическое ожидание длины критического пути.
Пусть задана технологическая матрица Л и предполо жим, что каждый конкретный путь / на матрице выби рается случайно, причем вероятность выбора каждого из возможных путей одинакова. Необходимо найти такую перестановку я*, чтобы
Mf(l, Л я , ) = т і п Mj(l,AJ |
• |
(2.7.4) |
Обозначим сумму длин всех путей произвольной мат рицы Л через ф (Л). Так как все матрицы Ал при я є П имеют одинаковое возможное количество различных пу тей, которое подсчитывается как число сочетаний из т + + я—2 элементов по т — 1 элементу, то в силу равнове роятности выбора каждого отдельного пути решение сформулированной задачи эквивалентно определению перестановки я*, для которой
ф ( Л я , ) = т і п < р ( Л я ) • |
(2.7.5) |
Чтобы определить ф(Л), можно вместо суммирования длин всех путей использовать сумму произведений каж дого элемента a-ij на величину Ьц — количество различ ных путей матрицы А, включающих элемент а^, тогда
тп
ф ( Л ) |
= 2 |
2 ciijbij |
• |
(2.7.6) |
|
г =1 |
j = l |
|
|
Если учесть, что любой путь из оц в at j может быть |
||||
независимо соединен с любым путем из ац в атп, |
образуя |
|||
путь из flu в атп, то получим |
|
|
|
|
|
г—1 |
т—г |
|
(2.7.7) |
bij = C{+j_2 • Сда+п—г—j • |
||||
В дальнейшем через S обозначим |
m X n — матрицу с |
|||
элементами Ьц, вычисленными по (2.7.7); через |
Ь)=(Ь^, |
|||
bzj, • • •, bmj) — вектор, |
координатами |
которого |
являются |
|
элементы /-го столбца |
матрицы В. Соотношения (2.7.6) |
и (2.7.7) дают возможность вычислить значение ср(Л). Обозначим через Л / матрицу, /-й столбец которой сов
падает с і-м столбцом исходной матрицы А, а все осталь
ные |
элементы |
являются |
нулями; через |
ац=(ан, |
а 2 г, ... , |
|
аПгі) |
— вектор, |
координатами которого являются |
элемен |
|||
ты і-го столбца |
матрицы А. Из (2.7.6) следует, что |
|||||
|
|
|
ф ( Л Ь = ( й г Д ) , |
|
_ J 2 - Z _ 8 ) |
|
где |
(йі, |
bj) — скалярное |
произведение векторов |
а.\ и by |
||
Так |
как |
из |
А=А{+А2 |
следует, что |
<р(Л) =<р(Лі) 4- |
+<р ( Л 2 |
) , и для произвольной последовательности столбцов |
||||||||
я = |
І2, • • •, |
in) имеет |
место равенство An — ^Aj |
*., сле- |
|||||
довательно, |
|
|
|
|
|
|
|
|
|
|
Ф ( Л Я ) = 2 |
Ф ( Л . - * ) = 2 |
(а ТІ) |
• |
(2.7.9) |
||||
|
|
|
h = i |
|
ft=i |
|
|
|
|
Рассмотрим |
матрицу |
Г = Л ' 5 |
( Л ' транспонирован |
||||||
ная матрица) |
|
размерности пХп, |
элементы іц |
которой |
|||||
|
|
— |
|
|
|||||
удовлетворяют |
равенству |
ta={au |
bj). |
|
ц>(Ал) |
|
|||
Из |
(2.7.9) |
следует, |
что для получения |
необхо |
димо просуммировать п элементов матрицы Т по одному |
|
из каждого столбца и каждой |
строки так, чтобы элемент |
Uj включался в сумму, если |
в перестановке я этот эле |
мент занимал /-е место. Для определения л* |
необходимо |
8: |
115 |
Минимизировать на множестве п\ возможных вариантоз сумму, составленную из элементов матрицы Т, взятых по одному из каждого столбца и каждой строки. Таким образом, задача о перестановке, минимизирующей мате матическое ожидание длины пути, сводится к задаче о назначениях [2.15], для решения которой разработаны достаточно эффективные алгоритмы, а математическое ожидание длины пути в данной задаче является анало гом функции Y(и).
Рассмотрим алгоритмы приближенного решения одномаршрутных задач очередности, основанные на опи санных выше методах, эвристическое обоснование кото рых заключается в следующем. В задаче очередности необходимо отыскать такую перестановку столбцов, при которой длина максимального пути достигла бы миниму ма. Поскольку каждому пути (в том числе и критическо му) на матрице соответствует определенное число «со седних» путей (т. е. путей, включающих элементы рас смотренного пути), то увеличение длины любого пути приведет к увеличению длин некоторого количества «со седних» путей и в результате к увеличению математи ческого ожидания длины пути. Другими слова-ми, между критическим путем матрицы F (А) и суммой длин всех путей ц>(А) должна существовать положительная корре ляционная связь. Поэтому естественно предположить, чго перестановка я*, обеспечивающая минимум величины ф ( Л я ) , дает достаточно хорошее приближение решения задачи очередности и, наоборот, точное решение задачи очередности необходимо искать среди приближенных ре шений задачи минимизации математического ожидания.
Проверка гипотезы о наличии статистической связи между указанными задачами осуществлялась с помощью специальной программы [2. 14], в соответствии с которой для каждой случайной перестановки рассчитывались ве личины критического пути и математического ожидания длины пути, после чего осуществлялся переход к новой перестановке столбцов. После просчета определенного количества вариантов подсчитывались дисперсии ука занных величин и коэффициент корреляции. Расположе ние 200 точек, последовательно рассчитанных для тесто вой задачи 20X20, показывает наличие корреляционной связи между функциями. Почти аналогичная картина была получена для тестовой задачи 10X50.
Рассмотрим Два способа решения задачи очередности вероятностными методами.
Алгоритм 1 реализует детерминированную процедуру решения задачи очередности и может быть использован в тех случаях, когда результаты необходимо получить как можно быстрее, в то время как существенная близость полученного решения к оптимальному из-за неизбежных погрешностей в исходных данных и воздействия случай
ных помех не имеет значения. Алгоритм |
1 может быть |
|
использован также в сочетании с методами |
транспозиций |
|
и замены критических столбцов. |
|
|
Вычислительная процедура |
алгоритма |
заключается |
в следующем. |
|
|
Этап 1. Определяются все элементы матрицы В в со |
||
ответствии с формулой (2.7.7), |
в которой |
значения m и |
п определяются по исходной матрице А. Если окажется,
что |
&п>106 , |
то необходимо |
подобрать такую константу |
|||
с ( 0 < с < 1 ) , чтобы с £ ц < 1 0 6 , и произвести |
пересчет |
осталь |
||||
ных элементов матрицы, применяя масштаб с. |
|
|
||||
пхп |
Этап 2. Вычисляется квадратная матрица Т—А'В |
из |
||||
элементов. |
|
|
|
|
||
|
Этап 3. Решается задача |
о назначениях [2. 15], т. |
е. |
|||
определяется |
последовательность n*=(i\, |
h,..., |
in) |
из |
||
элементов 1, |
2, ... , Л, минимизирующая |
величину |
2 ^ . ^ |
Этап 3 завершает вычисления, а перестановка я* прини мается в качестве приближенного решения задачи оче редности.
П р и м е р . Пусть задана |
матрица |
|
|
|
|||||
|
|
2 |
|
5 |
6 |
|
12 |
7 |
|
|
|
3 |
1 |
25 |
15 |
3 |
6 |
5 |
|
|
А = |
23 |
12 |
1 |
8 |
3 |
5 |
7 |
|
|
|
16 |
2 |
4 |
5 |
10 |
15 |
20 |
|
|
|
6 |
13 |
20 |
30 |
|
4 |
0 |
|
1. В |
соответствии с |
(2.7.7) |
определяем матрицу |
||||||
|
330 |
210 |
126 |
70 |
|
35 |
15 |
5 |
1 |
|
120 |
168 |
168 |
140 |
|
100 |
60 |
28 |
8 |
В |
36 |
84 |
126 |
150 |
|
150 |
126 |
84 |
36 |
|
8 |
28 |
60 |
100 |
140 |
168 |
168 |
120 |
|
|
1 |
5 |
15 |
35 |
70 |
126 |
210 |
330 |