Главная Бухгалтерия в кармане Учет расходов Экономия на кадровиках Налог на прибыль Как увеличить активы Основные средства
Главная ->  Гамильтоновы циклы 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 [ 19 ] 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141

МЫ как раз и получим нижнюю границу для оптимальной стоимо-ети в подзадаче (о покрытии) - границей является найденное значение v. Здесь мы предполагали, что множества, соответствующие элементам матрицы D, расположенным в разных строках, не пересекаются; такая ситуация, очевидно, является наилучшей из возможных. Последняя строка 9 просто гарантирует, что если

di,.<M-\El

то оставшиеся элементы покрываются наилучшим образом, т. е. с минимальной стоимостью покрытия для каждого дополнительно покрываемого элемента.

Наименьшее значение для

е е

2 is- при ограничении 2 /М - \Е' \

1=1 г=1

легко может быть получено с помощью следующего алгоритма динамического программирования.

Пусть gp {v) - наибольшее число элементов, которые могут быть покрыты только с помощью первых р строк матрицы D (т. е. с использованием только р блоков задачи), причем общая стоимость покрытия не превышает v. Тогда gp {v) может быть найдено итерационным методом, так как

{v) = max [dp, + gp i {v-dp,)], (3.17)

где go W) придается начальное значение, равное О для всех v.

Следовательно, наименьшее из значений величины v, для которых выполняется неравенство g% iy) Tlf - I £ , как раз будет требуемой нижней границей h; оно может быть легко получено из таблицы решения задачи динамического программирования, составленной с использованием приведенного выше итерационного уравнения. Следует отметить, что необходимо рассмотреть только такие значения величины у, для которых О f <:z - z, поскольку если h Z - z (т. е. gQ{v) <СМ - \ Е' \ для v z - z), то можно сразу же сделать шаг возвращения.

4.5. Вычислительная характеристика алгоритма решения ЗНП

Вычислительные возможности алгоритма, описанного в разд. 4.4 и предназначенного для решения ЗНП, представлены в табл. 3.2. Во второй и третьей графах таблицы даны числа строк и столбцов, полученные после применения упрощающих



правил. Данные во всех задачах задавались случайным образом, а стоимости брались равными единице, т. е. Cj = 1, для каждого столбца

Таблица 3.2

Время вычисления при решении ЗНП

Число строк

Число столбцов

Плотность

Время Вытсления

Умы в дереве поиска

0,22

0,05

0,02

0,25

0,04

0,01

0,30

0,06

0,02

0,18

0,25

0,07

0,11

0,02

0,23

0,35

0,05

0,17

0,60

0,06

0,19

1,30

0,16

0,22

1,50

0,11

0,12

1,00

0,20

0,15

10,50

1,60

0,17

6,00

0,52

0,21

9,20

0,20 0,23

11,00

0,09

22,00

0,40

0,23

105,50

3,02

0,25

32,50

0,12

0,26

57,20

0,18

1000

0,27

72,80

0,19

0,09

18,50

2,18

0,13

28,00

2,03

0,16

75,50

2,95

0,18

129,50

3,96

0,19

141,20

5,03

1075

0,20

110,00

0,55

1) СДС-6600, в секундах.

2) Число узлов в дереве поиска (в тысячах)

Лемке, Салкин и Шпильберг [41] предложили такие методы решения ЗНП, в которых используются дерево поиска (иного типа), а также линейные программы. Решение соответствующей задачи линейного программирования берется в качестве нижней границы в процессе поиска и, кроме того, определяет характер последующего ветвления в текущем узле дерева поиска. Подходы, базирующиеся на рассмотрении отсекающих плоскостей и подобные, в принципе, тем, которые применяются в общем О-1-программи-ровании [32], представлены в работах Хауза, Нелсона и Радо [35] и Белмора и Рэтлифа [9]. Сравнение этих методов и исследование их вычислительных характеристик дается в статье Кристо-фидеса и Кормана [19].



А

Е

Французский

Немецкий

Греческий

Итальянский

Испанский

Русский Китайский

5.2. ИнформационныЁ поиск [21)

Предположим, что некоторое количество единиц информации хранится в 7V массивах длины Cj, / = 1, 2, . . ., TV, причем на каждую единицу информации отводится по меньшей мере один массив. В некоторый момент делается запрос о М единицах информации. Они могут быть получены различными способами при помощи поиска в массиве. Для того чтобы получить все М единиц информации и при этом произвести просмотр массивов наименьшей длины, надо решить ЗНП, в которой элемент матрицы Т равен 1, если информация i находится в массиве, и О в противном случае.

5. Приложения задачи о покрытии 5.1. Выбор переводчиков

Предположим, что организации нужно нанять переводчиков е французского, немецкого, греческого, итальянского, испанского, русского и китайского языков на английский и что имеется пять кандидатур А, В, С, D п Е. Каждая кандидатура владеет только некоторым собственным подмножеством из указанного выше множества языков и требует вполне определенную зарплату. Необходимо решить, каких переводчиков (с указанных выше языков на английский) надо нанять, чтобы затраты на зарплату были наименьшими. Очевидно, что это - задача о наименьшем покрытии.

Если, например, требования на оплату труда у всех претендентов одинаковые и группы языков, на которых они говорят, указаны ниже в матрице Т, то решение задачи будет таким: нужно нанять переводчиков В, С м D.

Переводчик



1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 [ 19 ] 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141

© 2024 Constanta-Kazan.ru
Тел: 8(843)265-47-53, 8(843)265-47-52, Факс: 8(843)211-02-95