Экономика и менеджмент \ Управление предприятием

Задачи сетевого планирования и управления. Свободный резерв времени, страница 9

2. На матрицу Х = [x_ij] неизвестных должны быть наложены ограничения

(1)

. (2)

Система ограничений (1) обеспечивает построение маршрута, при котором коммивояжер въезжает в каждый город только один раз, а система ограничений (2) – маршрута, когда он выезжает из каждого города один раз.

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

Поэтому следует ввести n дополнительно переменных V_i (i = 1, 2,…, n), принимающих только целые неотрицательные значения, и записать для них специальные ограничения:

V_i – V_j + nx_ij ≤ n-1; (i = 1, 2,…, n; j = 1, 2,…, n).

3.Длина маршрута для выбранного плана переездов запишется в виде

. (3)

В результате приходим к следующей модели частично целочисленной задачи:

при условии

		i=1, 2, … , n; j=1, 2, … , n;
	или 1, или 2

		i=1, 2, … , n.
	или 1, или 2, . . .

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

Имеется 4 пункта с заданным расстояниями С_ij между i-м и j-м пунктами (см. рис.18). (Задача решается с применением Excel).Требуется:

I. Cоставить оптимальный маршрут из условия минимизации суммарного пробега для машины, выходящей из «нулевого» пункта, которая должна побывать в каждом пункте по одному и только одному разу и вернуться в «нулевой» пункт.

II. Найти кратчайшее оставное дерево графа, представленного на рисунке 18.

Решение

I. 1.Каждому ребру построенного графа сопоставляем свою булеву (альтернативную) переменную x_i, i=1..6, значение которой равно 1, если ребро входит в кратчайший путь, и равно 0 в противном случае.

2. Для каждой вершины сумма значений переменных, соответствующих ребрам, выходящим из нее, должна быть равна 2, так как по условию задачи коммивояжер в каждый пункт должен въехать, а значит, и выехать из него, причем по другому пути, иначе он попадает в пункт, в котором уже был. Таким образом, данная задача сводится к задаче линейного программирования с булевыми переменными. Найти

(1)