1Решаем задачу линейного программирования.

2Полученное оптимальное решение задачи, если оно существует, проверяем на целочисленность.

Набор из «n» упорядоченных пар городов, образующих маршрут, который проходит через каждый город только один раз, называется … .

циклом

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

о размещениях

Задача о размещениях формулируется следующим образом: найти такие значения … .

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

х_i и x_ij, при которых , при условиях, что производимая продукция полностью потребляется, каждый потребитель получает продукцию в объеме, не менее заданного значения, х_i и x_ij – принимает целочисленные значения

В задачах о размещениях условие означает следующее … .

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

производимая продукция полностью потребляется

Задача о назначениях формулируется следующим образом: найти такие значения … .

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

Xij, при которых при условиях, что на каждое предприятие поставляется по одному виду оборудования и каждая единица оборудования распределяется на одно предприятие

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

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

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

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

При решении задач целочисленного программирования методом Гомори "k-ое" дополнительное ограничение имеет вид … .

([x_i0], [x_ij] – целая часть соответствующей величины; x_i0 – нецелая координата оптимального плана задачи целочисленного программирования с наименьшим индексом; x_ij – координаты разложения векторов A_j, не попавших в базис; N_k – множество векторов, не попавших в базис)

В задачах целочисленного программирования, множество всех допустимых решений представляет собой … .

комбинации (перестановки) одного и того же набора чисел

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

подмножество с меньшей оценкой

В методе ветвей и границ длина замкнутого маршрута, образованного циклом t (набор из «n» упорядоченных пар городов, образующих маршрут, который проходит через каждый город только один раз) называется … .

издержками

В методе ветвей и границ условие S_ii = ∞, i=1,…,n говорит о том, что … .

(S_ij – элемент матрицы расстояний, который определяет расстояние при переходе из пункта «i» в пункт «j»)

переезд из пункта «i» в пункт «i» запрещен

Сумма минимальных элементов, вычисляемых в процессе приведения матрицы расстояний в методе ветвей и границ, называется … .

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

В методе ветвей и границ издержки цикла 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.