Диссертация (1137155), страница 15
Текст из файла (страница 15)
Выход из рекурсии обеспечивается либо принахождении допустимого решения, либо при нахождении тупиковойвершины. Функция Test(h, k) проверяет истинность ограничений(2.32), (2.33) и условияприсвоенызначениядля пары переменныхTr[h],Tr[k], которымсоответственно.Еслисоответствующие ограничения не существуют, возвращается значение«истина».Приведенный алгоритм можно улучшить, используя характерограничений задачи.
Напомним, что ограничения (2.32) определяют108для некоторых пар практикусловие непосредственногоследования в траектории. Это означает, что при проходе по деревурешений после присвоения переменнойшаге переменнойзначенияна следующемдолжно быть присвоено значение . Такимобразом, данное условие можно использовать не для проверкиполученного частичного решения в функции Test(), а для построениячастичногорешениянаследующемуровне,минуяперебор, тодолжнооставшихся значений в домене D.Ограничение (2.33) означает, что если (появиться в траектории раньше, чем). Это позволяет нам прикаждом присвоении использовать для проверки не только самочастичное решение, но и значения, оставшиеся еще неприсвоенными.Если среди последних обнаруживаются, когда, тогда данноечастичное решение объявляется некорректным.Дополним алгоритм хронологического поиска c возвратами всоовтетствии с описанной логикой.109Алгоритм 2.
Модифицированный поиск c возвратамиПроцедура Поиск_с_возвратами_2(k)1: для j := 1 до n+m циклесли ExchBT(Tr[k-1]) = 02:3:Tr[k] := D[j]4:если k ≠ n+m и ExchBT(Tr[k]) ≠ 05:Tr[k+1] := ExchBT(Tr[k])6:Поиск_с_возвратами_2(k+1)иначе7:8:Consistent := Истина9:для h := 1 до k-1 пока Consistent циклConsistent := Tr[k] ≠ Tr[h] и (Tr[k], Tr[h])10:11:кцикл12:для h := j+1 до n+m пока Consistent цикл13:Consistent := (Tr[h], Tr[k])14:кцикл15:если Consistent16:если k = n+m17:Вывод TrSиначе18:Поиск_с_возвратами_2(k+1)19:кесли20:21:Sкесли22:кциклКонец процедурыФункция ExchBT(b) для заданной исключаемой практикивозвращает заменяющую ее внедряемую практику, если110. Если заданы значенияили, тофункция возвращает 0.Предложенная модификация алгоритма поиска с возвратамипозволяет эффективно использовать ограничения (2.32), (2.33) инаходить все допустимые решения3.4..Вычислительный экспериментПроведем вычислительный эксперимент, в котором сначалаопределим, а затем оценим значения целевых функций длятраекторий.Для проведения вычислительного эксперимента на основеалгоритма 2 в среде MS Access была разработана программа, котораястроит допустимые траектории и вычисляет для них значения целевыхфункций (2.30), (2.31).
В качестве источника тестовых данныхвыбрана матрица изменений 5х6 из статьи [66] (рис. 19). Сведения оявных заменах практик и порядке практик взяты из текста даннойстатьи.++6. Гибкоеоборудование7. Большаяответственность8. Фиксированнаяоплата9. Низкие запасы ипоставки точно в срок10.
Мало уровнейуправления (3-4)11. Оптимизация налинии++++++ +1. Специализированноеоборудование2. Узкие должностныеобязанности3. Большие запасы незаверш.и готовой продукции----+---4. Сдельная оплата-5. Несколько уровнейуправления (6)+2++2-2-1-+1+2+1Рисунок 19. Тестовая матрица изменений+1111Тестовые данные:1. Множествапрактик:,,.2. Явные замены практик:.3. Порядок практик:4. Функция(2.1).заданаввидемассиваv[1..11]={0,-2,-1,1,0,2,2,0,2,1,1}, функция (2.2) – в виде двумерного массиваr[1..11,1..11], который заполнен значениями взаимосвязей междусоответствующими практиками.Таким образом, заданы все необходимые данные для построениямодели (2.9).ЭкспериментвыполнялсянаПЭВМDellOptiplex980(процессор Intel(R) Core™ i5 3.33ГГц, оперативная память 4 ГБ,операционная система MS Windows 7).Время работ программы – 0,1 секунды.В результате вычислительного эксперимента построено 180допустимых траекторий, которые были выведены в виде электроннойтаблицы MS Excel (приложение 1).Оценим сначала характер целевых функций (рис.
20, на врезкевыведены первые 10 значений функций в большем масштабе погоризонтали). Хотя функции и являются дискретными, далее длянаглядности будем использовать их непрерывные графики, в которыхдве соседние точки соединены отрезком прямой.112Рисунок 20. Графики целевых функцийПо графикам функций, представленным на рис. 20 можносделать выводо том, что обе целевые функции являютсямногоэкстремальными,причеммонотоннонеубывающиеилиневозрастающие участки имеются только в небольших промежутках.Подобный характер целевых функций делает неприменимыми методылокального поиска (например, градиентный спуск) и говорит онеобходимости использования методов глобальной оптимизации(например, генетические алгоритмы, имитация отжига).Для оценки применимости методов, основанных на отсечениимножеств решений при помощи оценочных функций, были построеныграфики изменения целевых функций (2.30), (2.31) для участковтраекторий, содержащих от 2 до 6 элементарных преобразований(рис.
21). Построенные графики не являются монотонными.113Рисунок 21. Целевые функции частичных решенийЗначение суммарной легкости для всех 180 траекторийодинаково () и равно вычисленному по формуле (2.15)), что подтверждает(справедливость теоремы о суммарной легкости преобразований.После сортировки траекторий по значению функции(2.21) построены графики функции легкости (рис. 22) парныхпреобразованийзначений функциидля лучшего, худшего и промежуточного, которая является первой целевойфункцией (2.30) поставленной оптимизационной задачи.114Рисунок 22.
Графики легкости для лучшего, худшего и промежуточного значенийфункцииИз графика видно, что траектория, соответствующая лучшему(минимальному) значению функцииграфик функции легкости, имеет более гладкийпо сравнению с остальнымитраекториями. В самом начале преобразований эта траектория«проигрывает» худшей траектории по легкости изменений (-2 против+2). Однако далее (на шаге 4) создается ситуация, когда у худшейтраектории легкость изменений падает до -4. Это говорит о том, чтокомпаниястолкнетсясозначительнымисложностямипривыполнении изменений по данному сценарию, поскольку в текущей(для шага 4) системе практик будет много практик, конкурентных поотношению к внедряемым практикам и/или комплементарных поотношению к исключаемым.
В то же время легкость лучшейтраектории постепенно (без скачков) увеличивается от -2 до +1. Такоеповедениефункциилегкостисоответствуетсодержательнойпостановке задачи, описанной в параграфе 2.2.Возможнаситуация,когдаруководствуорганизациинеобходимо обеспечить определенную легкость изменений в началепреобразований, чтобы обеспечить уверенность участников в успехевсегопроекта(такназываемаястратегия«быстрыхпобед»).115Смоделируем эту стратегию, установив для траекторий условие(рис. 23).Рисунок 23. Графики легкости для лучшего, худшего и промежуточного значенийфункцииприВ случае применения стратегии «быстрых побед» минимумфункциитакже позволяет нам выбрать траекторию сминимальными скачками легкости.
Однако при таком сценариипреобразованиянашагахбудутпроисходитьсозначительными трудностями.График,приведенныйнарис. 23,такжеиллюстрируетбесперспективность применения «жадного» алгоритма, посколькупреимущества, полученные на первыхшагах преобразований,повлияют на легкость преобразований на последних шагах в сторонуее уменьшения. Это объясняется постоянством значений суммарнойлегкости изменений для любой траектории (2.15) (теорема осуммарной легкости преобразований).Перейдем теперь к оценке значений второй целевой функции(2.26).116Упорядоченноемножествозначенийчистойдобавленнойценности, отсортированных по убыванию (2.25),.Это множество представляет «предпочтительный» график изменения,когда более ценные изменения выполняются раньше.На рис.
24 изображены графики чистой добавленной ценности(2.23), которые имеют наибольшее (лучшая траектория) инаименьшее (худшая траектория) значения ковариации с.Рисунок 24. График чистой добавленной ценности лучшей и худшей траекторийПо графикам (рис. 24) видно, что максимальное значениецелевой функции(2.26) обеспечивает наилучшееприближение графика изменения чистой добавленной ценности к«предпочтительному».Следует отметить, что данный подход к выстраиваниюизменений в зависимости от приоритетов бизнеса, является гибким,поскольку при помощи целевой функции(2.26)можно оценивать также и любой другой заданный наперед порядокчистой добавленной ценности.
Например, если принято решение, чтонаиболее ценные изменения должны быть выполнены в серединепроекта, то достаточно лишь соответствующим образом перестроитьмножество.117Для результатов вычислительного эксперимента графическимспособомпостроеномножествоПарето(рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
