Контрольная работа № 3 по предмету «Логика» на тему: «Методы упорядоченного ограниченного перебора на дереве вариантов решений» Вариант 17

Задача
Необходимо осуществить производство N = с химических продуктов, используя единственный тип аппаратуры. После выпуска продукта рi аппарат (реактор) должен быть «перенастроен» на выпуск продукта рj Время, требуемое на «перенастройку»,. зависит от последовательности выпуска продуктов (рi, рj) и равно аij, причем аij=aji. Продукты производятся в непрерывном цикле, таким образом после производства последнего из продуктов возобновляется в том же фиксированном цикле производство первого продукта.
Требуется:
1) построить полный взвешенный по ребрам граф, отображающий разнообразные последовательности циклического выпуска N продуктов;
2) с использованием дерева вариантов решений (ДВР) найти такую последовательность производства продуктов, чтобы суммарное время, затраченное на «перенастройку» ...

-

-

9).11538625, 5, 1153, 3, 381, 1, 012,2,1002934,4,1296435,5,16436,5,2087911538625, 5, 1153, 3, 381, 1, 012,2,1002934,4,1296435,5,16436,5,20879Рис. 9. Под-ДВР на очередном шагеР8=208+a51=208+115=323.Берём вершину (19, 5, 105) – 100 есть наименьшим НГ среди НГ оставшихся «листьев» (висячих вершин). Для простоты изображения начертим соответствующее под-ДВР отдельно (рис. 10).1151259295, 5, 1154, 4, 122, 2, 591, 1, 06, 2, 416419,5,10537,3,159541151259295, 5, 1154, 4, 122, 2, 591, 1, 06, 2, 416419,5,10537,3,15954Рис. 10. Под-ДВР на очередном шагеР9=159+a31=159+38=197.Берём вершину (15, 2, 108) – 108 есть наименьшим НГ среди НГ оставшихся «листьев» (висячих вершин). Для простоты изображения начертим соответствующее под-ДВР отдельно (рис. 11).11538546285, 5, 1153, 3, 381, 1, 014, 5, 9212,2,1006215,2,1085416,5,10038,5,1726413, 4, 4611538546285, 5, 1153, 3, 381, 1, 014, 5, 9212,2,1006215,2,1085416,5,10038,5,1726413, 4, 46Рис. 11. Под-ДВР на очередном шагеР10=172+a51=172+115=287.Берём вершину (5, 5, 115) – 115 есть наименьшим НГ среди НГ оставшихся «листьев» (висячих вершин). Для простоты изображения начертим соответствующее под-ДВР отдельно (рис. 12).1155464795, 5, 11540,3,1691, 1, 039,2,1792942,2,223843,3,20244,2,2646241,4,1941155464795, 5, 11540,3,1691, 1, 039,2,1792942,2,223843,3,20244,2,2646241,4,194Рис. 12. Под-ДВР на очередном шагеР11=264+a21=264+59=323.Берём вершину (21, 3, 121) – 121 есть наименьшим НГ среди НГ оставшихся «листьев» (висячих вершин). Для простоты изображения начертим соответствующее под-ДВР отдельно (рис. 13).5964622, 2, 591, 1, 023,5,12321,3,12185446,5,17546,5,2087945,4,1295964622, 2, 591, 1, 023,5,12321,3,12185446,5,17546,5,2087945,4,129Рис. 13. Под-ДВР на очередном шагеР12=208+a51=208+115=323.Берём вершину (23, 5, 123) – 123 есть наименьшим НГ среди НГ оставшихся «листьев» (висячих вершин). Для простоты изображения начертим соответствующее под-ДВР отдельно (рис. 14).59642, 2, 591, 1, 023,5,12347,3,177547949,4,185848,4,20259642, 2, 591, 1, 023,5,12347,3,177547949,4,185848,4,202Рис. 14. Под-ДВР на очередном шагеР13=185+a41=185+12=197.Берём вершину (28, 2, 155) – 155 есть наименьшим НГ среди НГ оставшихся «листьев» (висячих вершин). Для простоты изображения начертим соответствующее под-ДВР отдельно (рис. 15).12794, 4, 121, 1, 08, 5, 916428,2,15550,2,2176212794, 4, 121, 1, 08, 5, 916428,2,15550,2,21762Рис. 15. Под-ДВР на очередном шагеР14=217+a21=217+59=276.Берём вершину (25, 5, 167) – 167 есть наименьшим НГ среди НГ оставшихся «листьев» (висячих вершин). Для простоты изображения начертим соответствующее под-ДВР отдельно (рис. 16).592, 2, 591, 1, 07925,5,16751,3,2115422, 4, 8829592, 2, 591, 1, 07925,5,16751,3,2115422, 4, 8829Рис. 16. Под-ДВР на очередном шагеР15=211+a31=211+38=249.Берём вершину (40, 3, 169) – 169 есть наименьшим НГ среди НГ оставшихся «листьев» (висячих вершин). Для простоты изображения начертим соответствующее под-ДВР отдельно (рис. 17).11554645, 5, 11540,3,1691, 1, 039,2,1796252,2,231853,4,17754,2,2062911554645, 5, 11540,3,1691, 1, 039,2,1796252,2,231853,4,17754,2,20629Рис. 17. Под-ДВР на очередном шагеР16=206+a21=206+59=265.Берём вершину (40, 3, 175) – 175 есть наименьшим НГ среди НГ оставшихся «листьев» (висячих вершин). Для простоты изображения начертим соответствующее под-ДВР отдельно (рис. 18).59622, 2, 591, 1, 021,3,1215446,5,17555,4,2547959622, 2, 591, 1, 021,3,1215446,5,17555,4,25479Рис. 18. Под-ДВР на очередном шагеР17=254+a41=254+12=266.Берём вершину (39, 2, 179) – 179 есть наименьшим НГ среди НГ оставшихся «листьев» (висячих вершин). Для простоты изображения начертим соответствующее под-ДВР отдельно (рис. 19).115645, 5, 1151, 1, 039,2,1796256,3,24158,3,21657,4,208298115645, 5, 1151, 1, 039,2,1796256,3,24158,3,21657,4,208298Рис. 19. Под-ДВР на очередном шагеР17=216+a31=216+38=254.Лучший результат был получен ещё на первом проходе – 198. Порядок вершин: 1, 4, 3, 5, 2.б) стратегию «лучевого ветвления».Одна из наиболее часто применяемых стратегий ветвления – лучевое ветвление. Сущность ее заключается в том, что в качестве активной вершины ДВР выбирают одну из висячих вершин последнего образовавшегося при декомпозиции исходной задачи слоя вершин ДВР. После завершения цепи ДВР до некоторого альтернативного варианта решения или просмотра всех висячих вершин некоторого слоя вершин ДВР выбор активной вершины происходит на предыдущем слое. При этом просмотр вершин каждого слоя проводится в строго установленном порядке: «слева – направо», «справа – налево» или в порядке возрастания.Начальное дерево вариантов решений будет аналогичным предыдущему (рис. 20).115123859792985, 5, 1154, 4, 123, 3, 382, 2, 591, 1, 08, 5, 916, 2, 417, 3, 20629, 2, 825410, 5, 7411,2,13864115123859792985, 5, 1154, 4, 123, 3, 382, 2, 591, 1, 08, 5, 916, 2, 417, 3, 20629, 2, 825410, 5, 7411,2,13864Рис. 20. Начальное дерево вариантов решенийР1=138+a21=138+59=197.Берём вершину (9, 2, 82) – 82 есть наименьшим НГ среди НГ оставшихся «листьев» (висячих вершин) на текущем или том из предыдущих слоёв, где ещё есть «листья» (в порядке «снизу –вверх»). Для простоты изображения начертим соответствующее под-ДВР отдельно (рис. 21).115123859792985, 5, 1154, 4, 123, 3, 382, 2, 591, 1, 08, 5, 916, 2, 417, 3, 20629, 2, 8212,5,14664115123859792985, 5, 1154, 4, 123, 3, 382, 2, 591, 1, 08, 5, 916, 2, 417, 3, 20629, 2, 8212,5,14664Рис. 21. Под-ДВР на очередном шагеР2=146+a51=146+115=261.Берём вершину (6, 2, 41) – 41 есть наименьшим НГ среди НГ оставшихся «листьев» (висячих вершин) на текущем или том из предыдущих слоёв, где ещё есть «листья» (в порядке «снизу –вверх»). Для простоты изображения начертим соответствующее под-ДВР отдельно (рис. 22).115123859295, 5, 1154, 4, 123, 3, 382, 2, 591, 1, 06, 2, 4113,3,103626414,5,10515,5,15754115123859295, 5, 1154, 4, 123, 3, 382, 2, 591, 1, 06, 2, 4113,3,103626414,5,10515,5,15754Рис. 22. Под-ДВР на очередном шагеР3=157+a51=157+115=272.Берём вершину (14, 5, 105) – 105 есть наименьшим НГ среди НГ оставшихся «листьев» (висячих вершин) на текущем или том из предыдущих слоёв, где ещё есть «листья» (в порядке «снизу –вверх»). Для простоты изображения начертим соответствующее под-ДВР отдельно (рис. 23).115123859295, 5, 1154, 4, 123, 3, 382, 2, 591, 1, 06, 2, 416414,5,10516,3,15954115123859295, 5, 1154, 4, 123, 3, 382, 2, 591, 1, 06, 2, 416414,5,10516,3,15954Рис. 23. Под-ДВР на очередном шагеР4=159+a31=159+38=197.Берём вершину (8, 5, 91) – 91 есть наименьшим НГ среди НГ оставшихся «листьев» (висячих вершин) на текущем или том из предыдущих слоёв, где ещё есть «листья» (в порядке «снизу –вверх»). Для простоты изображения начертим соответствующее под-ДВР отдельно (рис. 24).11512385979545, 5, 1154, 4, 123, 3, 382, 2, 591, 1, 08, 5, 9118,3,1456417, 2, 8219,5,1466411512385979545, 5, 1154, 4, 123, 3, 382, 2, 591, 1, 08, 5, 9118,3,1456417, 2, 8219,5,14664Рис. 24. Под-ДВР на очередном шагеР5=146+a51=146+115=261.Берём вершину (18, 3, 145) – 145 есть наименьшим НГ среди НГ оставшихся «листьев» (висячих вершин) на текущем или том из предыдущих слоёв, где ещё есть «листья» (в порядке «снизу –вверх»). Для простоты изображения начертим соответствующее под-ДВР отдельно (рис. 25).11512385979545, 5, 1154, 4, 123, 3, 382, 2, 591, 1, 08, 5, 9118,3,14520, 2, 826211512385979545, 5, 1154, 4, 123, 3, 382, 2, 591, 1, 08, 5, 9118,3,14520, 2, 8262Рис. 25. Под-ДВР на очередном шагеР6=207+a21=207+59=266.Берём вершину (3, 3, 38) – 38 есть наименьшим НГ среди НГ оставшихся «листьев» (висячих вершин) на текущем или том из предыдущих слоёв, где ещё есть «листья» (в порядке «снизу –вверх»). Для простоты изображения начертим соответствующее под-ДВР отдельно (рис. 26).1153859546285, 5, 1153, 3, 382, 2, 591, 1, 023, 5, 9221,2,10022, 4, 462924, 2, 7526,5,1396425,5,125791153859546285, 5, 1153, 3, 382, 2, 591, 1, 023, 5, 9221,2,10022, 4, 462924, 2, 7526,5,1396425,5,12579Рис. 26. Под-ДВР на очередном шагеР7=139+a51=139+115=254.Берём вершину (25, 5, 125) – 125 есть наименьшим НГ среди НГ оставшихся «листьев» (висячих вершин) на текущем или том из предыдущих слоёв, где ещё есть «листья» (в порядке «снизу –вверх»). Для простоты изображения начертим соответствующее под-ДВР отдельно (рис. 27).1153859546285, 5, 1153, 3, 382, 2, 591, 1, 023, 5, 9221,2,10022, 4, 4627,2,24011525,5,125791153859546285, 5, 1153, 3, 382, 2, 591, 1, 023, 5, 9221,2,10022, 4, 4627,2,24011525,5,12579Рис. 27. Под-ДВР на очередном шагеР8=240+a21=240+59=299.Берём вершину (23, 5, 92) – 92 есть наименьшим НГ среди НГ оставшихся «листьев» (висячих вершин) на текущем или том из предыдущих слоёв, где ещё есть «листья» (в порядке «снизу –вверх»). Для простоты изображения начертим соответствующее под-ДВР отдельно (рис. 28).115385954625, 5, 1153, 3, 382, 2, 591, 1, 023, 5, 9221,2,10029,4,1716428,2,15630,4,1852979115385954625, 5, 1153, 3, 382, 2, 591, 1, 023, 5, 9221,2,10029,4,1716428,2,15630,4,1852979Рис. 28. Под-ДВР на очередном шагеР9=185+a41=185+12=197.Берём вершину (29, 4, 181) – 181 есть наименьшим НГ среди НГ оставшихся «листьев» (висячих вершин) на текущем или том из предыдущих слоёв, где ещё есть «листья» (в порядке «снизу –вверх»). Для простоты изображения начертим соответствующее под-ДВР отдельно (рис. 29).115385954625, 5, 1153, 3, 382, 2, 591, 1, 023, 5, 9221,2,10029,4,17131,2,2002979115385954625, 5, 1153, 3, 382, 2, 591, 1, 023, 5, 9221,2,10029,4,17131,2,2002979Рис. 29. Под-ДВР на очередном шагеР10=200+a21=200+59=295.