Приводящей константой

В методе ветвей и границ издержки цикла t вычисляются по формуле Z(t)=Z'(t)+h, где h – это ….

(Z(t) – издержки цикла t для исходной матрицы расстояний, Z'(t) – издержки цикла t после приведения)

Сумма минимальных элементов строк исходной матрицы

Пара городов (i, j) для ветвления в задаче о коммивояжере выбирается среди тех пар, которым в приведенной матрице расстояний соответствуют … элементы.

Нулевые

В методе ветвей и границ на вершине дерева ветвей располагается ….

Подмножество, содержащее две пары городов, завершающих маршрут

Расставьте в правильном порядке пункты алгоритма метода ветвей и границ:

3) Выбрать претендентов для ветвления, т.е. те пары (i, j) i=l,2,..., j = l, 2,..., i ≠ j, для которых S_ij(k)=0.

2) Вычислить сумму приводящих констант h(k) - это оценка для исходного множества маршрутов G₀.

4) Выбрать для ветвления ту пару (i,j) из претендентов на ветвление, для которой θ_ij получится максимальным.

1) Произвести приведение матрицы расстояний S по строкам и столбцам, получим приведенную матрицу S′.

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

Завершают

Графическим решением задачи о коммивояжере является маршрут ….

Дана матрица расстояний

Претендент на ветвление в приведенной матрице находится на пересечении ….

Строки 1 столбца 4

В задачах о размещениях затраты на производство продукции будут равны ….

(x_i –объем продукции в единицах, который необходимо производить в пункте «i», x_ij – количество единиц продукции, поставляемой из пункта «i» в пункт «j», c_ij – затраты на транспортировку единицы продукции из производящего пункта «i» в потребляющий пункт «j», m – количество производящих пунктов, n – количество потребляющих пунктов)

В задаче о размещениях суммарные затраты по производству и транспортировке должны быть ….

Минимальными

При использовании метода Гомори полученное решение задачи линейного программирования проверяется на ….

Целочисленность

Если хотя бы одна координата решения задачи линейного программирования не удовлетворяет условию целочисленности при использовании метода Гомори, то ….