Материал: Основы математического моделирования. курс лекций. Перова А.В

Тогда математическая модель задачи будет иметь следующий вид:

n n

pijxij max;

i1j 1 n

xij 1,i 1,n;

j 1

n

xij 1,j 1,n;

i1

xij {0,1}.

Квадратичная задача о назначениях.

Имеется m пунктов, в которых необходимо разместить n объектов. В каждом пункте может быть размещен только один объект. Даны расстояния между i-м и j-м пунктами dij, а

также csk – показатели, характеризующие взаимосвязи между s-м и k-м объектами (стоимость перевозок, число коммукникаций и т.д.). Необходимо определить такое назначение объектов в выделенные пункты, чтобы минимизировать соответствующие затраты.

Математическая модель задачи имеет следующий вид:

n 1 n m m

xsi xkjcsk dij min; s 1 k s 1 i 1 j 1

m

xsk 1,s 1,n;

k1 n

xsk 1,k 1,m;

s 1

xsk {0,1}.

В данном случае целевая функция зависит не от всевозможных назначений, а от всевозможных пар назначений (s-й

110

элемент размещается в i-й пункт, а k-й – в j-й пункт). Целевая функция при этом не является линейной.

Квадратичная задача о назначениях имеет широкий круг практических приложений. Она может быть использована для решения задач размещения (оборудования, предприятий, деталей, и т.д.). Особенно часто эта модель используется в задачах конструкторско-топологического проектирования.

Пример 3. Необходимо таким образом разместить n компонентов печатной платы на m позициях монтажного пространства, чтобы суммарная длина электрических соединений между компонентами была бы минимальной.

Предположим, что n=m. Пусть lks - расстояние между

k-й и s-й позициями, mij - число связей между i-м и j-м ком-

понентами. Введем бинарные переменные

1,еслиi -йкомпонентназначается

xik на k -юпозицию .0 в противном случае

n 1 n m m

xik xjSlkSmij min; i 1 j 1 i k 1 S 1

m

xik 1;i 1,n;

k1 n

xik 1;k 1,m;

i 1

xik {0,1}.

Задача коммивояжера

Имеются n пунктов или городов с заданными расстояниями dij между i-м и j-м пунктами. Необходимо составить

оптимальный маршрут из условия минимизации суммарного расстояния для коммивояжера, выходящего из пункта с номе-

111

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

Введем альтернативные бинарные переменные:

Условия минимизации общего расстояния , а также прибытия в каждый пункт и выезда из него ровно по одному разу могут быть выражены следующим образом:

n n

dij x ij min;

i1 j 1 n

x ij 1,i 1, n;

j 1

n

x ij 1,j 1, n;

i 1

xij {0,1}.

Однако необходимо обеспечить непрерывность маршрута, чтобы набор звеньев, входящих в маршрут, образовывал единую цепочку (например, при n=8 цепочка (1,2) - (2,6) - (6,4) - (4,8) - (8,5) - (5,3) - (3,7) - (7,1)), а не состоял бы из отдельных не связанных цепочек (например, (1,2) - (2,6) - (6,1) и (3,8) - (8,7) - (7,5) - (5,4) - (4,3)). Для устранения замкнутых циклов (подобходов), включающих количество вершин меньшее n, в

модель вводятся n дополнительные переменных ui 0 (i 1,n) и n2 дополнительных ограничений:

Ui Uj (n 1)xij n 2,i 2,n,j 2,n.

112

Действительно, пусть маршрут включает несколько цепочек. Тогда существует цепочка, начинающаяся и заканчивающаяся в начальном пункте, но включающая n1 звеньев, где n1<n. Просуммировав эти неравенства вдоль такой цепочки (т.е. при xik=1), получим бессмысленное неравенство n1(n- 1) n1(n-2) (все ui и uj при суммировании взаимно уничтожаются). Покажем теперь, что для маршрута, исключающего подобходы, это неравенство выполняется, т.е., можно найти значения ui, удовлетворяющие дополнительным ограничениям. Положим ui=p, если город i посещается коммивояжером на p-м

шаге, p=2,n . Отсюда следует, что ui uj n 2 i, j 2,n.

Таким образом, ограничения выполняются для всех xij 0.

При xij 1 эти ограничения превращаются в равенства

Ui U j (n 1)xij p (p 1) n 1 n 2.

Задача коммивояжера имеет широкий круг практических приложений. К ней сводятся задачи оптимальной маршрутизации (выбор маршрутов перевозки грузов, маршрутов движения транспорта, минимизация расстояния, проходимого исполнительным механизмом станка с ЧПУ и т.д.), задачи проектирования электрических и вычислительных сетей, задачи определения последовательности обработки деталей на станках с условием минимизации времени переналадок и т.д.

Пример 4. Пусть необходимо проложить коммуникации между n различными ЭВМ таким образом, чтобы каждая ЭВМ была связана с двумя соседними, вся сеть была бы подключена к центральной ЭВМ, а суммарная длина коммуникаций была бы минимальна. Заданы расстояния dij между i-й и j-й ЭВМ.

Данная задача формализуется в виде задачи коммивояжера следующим образом:

113

n n

dij xij min; i 1 j 1

n

xij 1,i 1,n;

j1 n

xij 1,j 1,n;

i 1

U i U j (n 1) x ij n 2 ,i 2 , n , j 2 , n ; x ij {0,1}, u i 0 .

При этом xij=1, если i-я и j-я ЭВМ соединяются.

Задача о покрытии

Пусть имеется n предметов, каждый из которых обладает некоторым числом признаков из заданного множества m признаков, а в совокупности эти n предметов обладают всеми m признаками. Необходимо выбрать минимальное число предметов, которые в совокупности обладали бы m признаками. Условия задачи задаются матрицей A с элементами

Тогда математическая модель задачи имеет следующий

вид:

114