Санкт-Петербургский гуманитарный университет профсоюзов

 

Утверждено

Учёным советом

экономического факультета

20 мая 1996 г., протокол № 8

Методические указания по выполнению задания

Сетевые методы планирования

для студентов 3-го курса дневного и заочного отделений экономического факультета

 

Санкт-Петербург

1996

 

Кафедра высшей математики

 

 

Автор

доцент кафедры высшей математики, кандидат физико-математических наук
А. М. Махов

 

 

Введение

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

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

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

I.                  Задания для самостоятельной работы студентов и порядок их выполнения

1.     План замены оборудования

Задание

Составить для вновь создаваемого на 8-летний период предприятия план замены оборудования, оптимальный по критерию минимума общих затрат на оборудование, в двух подходах: а) общие затраты исчисляются в национальной валюте, подверженной переменной инфляции; б) общие затраты исчисляются в сопоставимых ценах на момент начала функционирования предприятия. Сравнить полученные в обоих подходах результаты. Модель замены: оборудование приобретается в начале года и продается по остаточной (ликвидационной) стоимости в конце года. Период полного износа оборудования t = 4 года.

В общие затраты c_ij на оборудование, купленное в начале i-го, и проданное в конце j-го года, входят:

P_i - стоимость оборудования, купленного в начале i-го года. В сопоставимых ценах она не меняется: P_i = P_о = 100000 $. Курс национальной валюты на момент начала функционирования предприятия составляет 5000 руб. за 1 $.

m_ik - эксплуатационные расходы в k-ом году на оборудование, купленное в начале i-го года. В сопоставимых ценах m_ik = P_o (b + d * (k - i)); здесь b - коэффициент начальных эксплуатационных затрат (отношение эксплуатационных расходов в течение первого года эксплуатации к стоимости оборудования в сопоставимых ценах); d - коэффициент годового прироста эксплуатационных затрат (отношение разности эксплуатационных расходов в течение первых двух лет эксплуатации к стоимости оборудования в сопоставимых ценах).

d = 0,2 / t;  d = 1 / (6 t).

S_ij - ликвидационная стоимость оборудования, купленного в начале i-го и проданного в конце j-го года. В сопоставимых ценах определяется из выражения:

S_ij = max {0; P_o * (1 - (j - i) / t)}.

R_j - затраты на ликвидацию оборудования в конце j-го года. Составляют 10% от стоимости нового оборудования на момент ликвидации старого.

Таким образом:

c_ij = P_i + m_ik + 0.1 P_i - S_ij.

При вычислении суммы в подходе а) должна быть учтена ежегодная инфляция, коэффициент которой a_i, определяемый как отношение цен в начале i-го года и следующего за ним, является в данном задании функцией номера года i и фамилии и инициалов студента. Значения коэффициента годовой инфляции должны быть получены каждым студентом самостоятельно из порядковых номеров букв его фамилии и инициалов N_i по следующей формуле:

a_i = 1 + N_i/₁₀₀.

Если фамилия и инициалы содержат меньше 8-и букв, то последовательность букв повторяется до заполнения всех 8-и лет. Порядковые номера букв можно определить из следующей таблицы:

 

Пример получения значений коэффициентов годовой инфляции для Сидорова Ивана Петровича: Сидоров И.®

 ® 19, 10, 5, 16, 18, 16, 3,10® 1,19; 1,1; 1,05; 1,16 ;1,18; 1,16; 1,03; 1,1.

Порядок выполнения работы:

1) вычислить значения годового коэффициента инфляции в течение срока функционирования предприятия. Построить график a_i, дать общую характеристику инфляционных процессов на его основе;

2) составить граф всех возможных вариантов замены оборудования в течение всего срока функционирования предприятия. Узел графа с номером i должен соответствовать началу i-го года функционирования предприятия, а дуга [i, j] - процессу функционирования оборудования, купленного в начале i-го и проданного к началу j-го года, характеризуемому общими затратами c_{ij - 1;}

3) вычислить матрицу стоимостей для полученной сети C_8.8 в подходах а) и б);

4) в обоих подходах с использованием алгоритма Дейкстры и демонстрацией его прямого и обратного ходов найти кратчайшую цепь из первого в девятый узел и составить оптимальный план замены оборудования с указанием общих затрат за весь период и график расходов на оборудование. Сравнить полученные результаты;

5) согласно п. п. 1-4 составить отчет, снабдить его титульным листом и сдать в установленные преподавателем сроки.

2.     Маршрут перевозок

Задание

Составить для рекламного предприятия, состоящего из офиса с центром разработки и изготовления наружной рекламы и 4-х пунктов размещения с одинаковыми сроками смены рекламы, маршрут доставки, оптимальный по критерию минимума полного ежедневного пробега транспортного средства, стоянка которого находится в помещении офиса. Матрица пробегов между офисом (пункт № 1) и пунктами размещения (пункты № 2-5) должна быть получена каждым студентом самостоятельно из порядковых номеров букв его фамилии и инициалов. Полученными числами необходимо построчно заполнить матрицу (5´5), за исключением элементов главной диагонали, которые должны быть положены равными . Пример построения матрицы пробегов для Сидорова Ивана Петровича:

Для определенности можно считать числа в полученной матрице расстоянием в километрах.

Порядок выполнения работы:

1) с использованием алгоритма Литтла и демонстрацией его пошагового хода решения построить дерево маршрутов и получить оптимальный кольцевой маршрут ежедневной доставки товара в пункты реализации с товарного склада;

2) составить отчет согласно пункту 1, снабдить его титульным листом и сдать в установленные преподавателем сроки.

II. Введение в теорию графов

Перечень используемых в дальнейшем обозначений

x  B - элемент x принадлежит множеству B;

B Ì A - множество B является подмножеством множества A;

B É A - множество B включает множество A (A Ì B);

A\B - разность множеств (множество, содержащее все элементы A, не входящие в B);

A  В = A + B - множество, являющееся объединением (суммой) множеств A и B;

A  B = A * B - множество, являющееся пересечением (произведением) множеств A и B;

{...} - обозначение множества;

Æ - пустое множество;

A = {B, С} - множество A состоит из подмножеств B и C;

A = {a_i, i  N} - множество A состоит из элементов a_i, каждый из которых полностью характеризуется некоторым конкретным значением признака i, все значения которого составляют множество N;

A Û B - между всеми элементами множеств A и B установлено взаимно однозначное соответствие;

x_i- сумма значений величины x, характеризуемой признаком i, по всем возможным в промежутке [a, b] значениям этого признака;

x_i- сумма значений величины x, характеризуемой признаком i, по всем возможным значениям этого признака;

a = F (b) - величина a является функцией (зависит от) величины b;

 - любой;

: - такой, что;

 - бесконечность;

 - существует.

1. Определения

Сетью (графом) G может быть назван любой объект, который можно представить как совокупность множества узлов N и множества дуг A, соединяющих их. G = {N, A}. Каждый элемент множества A есть пара (i, j) элементов множества N. Примеры графического представления сетей и задающих их множеств см. рис. 1.

Узлы также называют вершинами или точками, а дуги - ребрами, звеньями, линиями или ветвями. Граф G конечен, если конечны оба задающие его множества N и A.

Сеть G₁, состоящую из узлов и дуг, входящих в сеть G, называют подграфом сети G; то есть G₁ = {N₁, A₁} - подграф G = {N, A}, если N₁  N и A₁  A. Наиболее простое представление сети получается, если использовать в качестве элементов {N}натуральные числа - номера узлов. Тогда каждая дуга характеризуется парой чисел - номерами узлов, которые она связывает.

Однако каждый узел и дуга сети характеризуются еще одной числовой величиной, смысл которой определяется в конкретных задачах. В общем случае такое поставленное в соответствие узлу число называют его интенсивностью d. Узлы называют источниками (если d > 0), стоками (если d < 0) и нейтральными узлами (если d = 0). Таким образом: N = {N₊} {N_-} {N_o}; N₊ = {n : d_n > 0}, N_- = {n : d_n < 0}, N_o = {n : d_n = 0}.

Аналогично, поставленное в соответствие дуге (i, j) число той же природы, что и интенсивность узла, называют пропускной способностью дуги r_ij.

Потоком F = {f_ij : (i, j)  A} в сети G называют совокупность величин f_ij - потоков в дугах, удовлетворяющих соотношениям:

f_ij - f_ji = d_i, i  N;        0 £ f_{ij £} r_ij.                                     (1)

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

 c_ij f_ij ® opt                                    (2)

при одновременном выполнении условий (1). В результате эта задача принимает вид стандартной задачи линейного (если c_ij = const), либо нелинейного (если c_ij = F (f_kl), (k, l)  A) программирования.

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

Метод - путь, способ получения решения; совокупность приемов, операций, направленных на достижение некоторой цели.

Алгоритм - последовательность четко определенных правил (команд) для получения решения за конечное число шагов.

Любой алгоритм - метод; но не любой метод является алгоритмом.

2. Ориентированные и неориентированные сети

Дугу (i, j) называют направленной от узла i к узлу j, если дополнительный поток из i в j, протекающий по этой дуге, увеличивает величину уже существующего в ней потока, а противоположный дополнительный поток уменьшает эту величину. Направленные дуги иногда обозначают следующим образом: [i, j]. Направленная дуга называется ориентированной и в графическом представлении сети обозначается линией со стрелкой (см. рис. 2а). Дуга, не имеющая направления, называется неориентированной и в графическом представлении сети обозначается линией (см. рис. 2б).

Сети также могут быть ориентированными (содержащими ориентированные дуги) и неориентированными (содержащими только неориентированные дуги).

Цепью [i, j, ..., k] из узла i в узел k называют подграф G₁ сети G, состоящий из последовательности дуг и узлов, в которой конечный узел каждой дуги (исключая узлы i и k) является начальным узлом следующей дуги. Цепь может включать неориентированные дуги.

Путем (i, j, ..., k) из узла i в узел k называют подграф G₂ сети G, состоящий из последовательности дуг и узлов, в которой каждый узел (исключая узлы i и k) является начальным или конечным узлом только двух дуг из G₂ и каждая дуга пути начинается и заканчивается в узлах из G₂.

Контур - конечная цепь с началом и концом в одном и том же узле.

Цикл - конечный путь с началом и концом в одном и том же узле.

Петля - цикл или контур из одной дуги и одного узла.

Не содержащие контуров сети называют бесконтурными, а не содержащие циклов - ациклическими.

Сеть связна, если для любых двух ее узлов существует соединяющий их путь.

Сеть сильно связна, если для любых двух ее узлов существует соединяющая их цепь.

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

Разрез C в графе - множество его дуг, исключение которых из сети G разделяет ее на два несвязных между собой подграфа G₁, G₂ исходной сети. То есть:

C = {(i, j) : (i, j)  A} :

G = G₁ G₂ C;  G₁ G₂ = , G₁ C = , G₂ C = ;  i, j G:  i G₁,  j G₂;  (i, j)  C.

Величина разреза C, его пропускная способность R_c (G₁  G₂) в направлении от G₁ к G₂ - это сумма пропускных способностей r_ij всех дуг [i, j] разреза C, начинающихся в G₁ и оканчивающихся в G₂ :

R_c (G₁ G₂) =  r_ij.

Таким образом, каждый разрез ориентированной сети характеризуется двумя пропускными способностями: R_c (G₁ G₂) и R_c (G₂ G₁). В приложениях теории графов для сетей с одним источником s и одним стоком r большое значение имеют разрезы, разделяющие сток и исток, причем важной оказывается только величина разреза в направлении от источника к стоку. Для таких разрезов s G₁, r G₂; а R_c (s  r) = R_c. В каждой конкретной сети разрезов этого типа может быть несколько. Тот из них, величина которого наименьшая, называется минимальным разрезом, а тот, величина которого наибольшая - максимальным разрезом.

3. Деревья и древовидности

Частным случаем связных сетей являются деревья.

 Дерево G₁ сети G, это связный подграф G, не содержащий циклов.

Подграф является деревом, если выполнены любые два из трех следующих условий:

1. Подграф связный.

2. Подграф ациклический.

3. Число дуг подграфа меньше числа его вершин на единицу.

Для любых двух узлов дерева существует единственный путь между ними. Остовным деревом (остовом) сети называют дерево, содержащее все узлы исходной сети. Таким образом, G_o = {N, A_o} - остовное дерево G = {N, A}, если A_o c A и G_o - дерево.

Весом дерева в сети, для дуг которой определена обобщенная стоимость  c_ij, называют сумму с_ij по всем дугам дерева.

Кратчайшим остовом называют остов с наименьшим для всех остовов данной сети весом.

Максимальным остовом называют остов с наибольшим для всех остовов данной сети весом.

Древовидностью называют дерево, состоящее только из ориентированных дуг и имеющее единственный корень - узел, из которого дуги только исходят.

Древовидное дерево - дерево, являющееся древовидностью.

Древовидный остов, являющийся древовидностью.

Примеры дерева, остова, древовидности, древовидного остова приведены на рис. 5.

4. Матричные представления сетей

Каждая сеть может быть однозначно задана в матричном представлении. Основными используемыми для этого матричными величинами являются матрицы обобщенных стоимостей C_n,n, смежности X_n,n и инциденции Z_n,k. Здесь индексы являются размерностью матриц, n - число узлов сети, k - число ее дуг.

Элементом c_ij матрицы стоимостей C_n,n является обобщенная стоимость дуги [i, j] A. Для неориентированной сети эта матрица симметрична. Значение элементов c_ij с i и j, для которых в графе G не существует дуг [i, j], определяется конкретной задачей и обычно полагается равным бесконечности ( ).

Элемент x_ij матрицы смежности X_n,n определяется следующим образом:

Свойства матрицы смежности для ориентированной сети:

1) каждый нулевой столбец соответствует источнику;

2) каждая нулевая строка соответствует стоку;

3) ненулевой элемент главной диагонали соответствует петле;

4) матрица не симметрична.

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

Матрица инциденции связана с альтернативным представлением сети, в котором каждой дуге ставится в соответствие ее номер, а не пара номеров связанных с ней узлов. Элементы z_ij  матрицы инциденции имеют вид:

 

 

Матрицы обобщенных стоимостей C_n,n, смежности X_n,n и инциденции Z_n,k  для сети (рис. 6) имеют следующий вид:

C = ; X = ; Z = ,

для Z: [1, 2] = 1;  (1, 3) = 2;  [2, 2] = 3; 

(2, 3) = 4;  (2, 4) = 5;  [3, 4] = 6.

Говорят, что сети G₁ = {N₁, A₁} и G₂ = {N₂, A₂} изоморфны, если между их дугами и узлами может быть установлено взаимно однозначное соответствие: N₁ <=> N₂: A₁ <=> A₂.

Верно следующее утверждение: любое уравнение, справедливое для данной сети, справедливо и для изоморфной ей сети. Это свойство изоморфных сетей может в ряде случаев существенно упрощать анализ сетей за счет выделения в них подграфов, изоморфных друг другу либо ранее исследованным сетям.

5. Теорема о максимальном потоке и минимальном разрезе

В приложениях теории графов при анализе потоков в сетях с одним источником  s и одним стоком r и ограниченной пропускной способностью основной задачей является поиск максимального потока в сети с постоянными пропускными способностями дуг и изменяемыми интенсивностями источника и стока (то есть потока максимальной величины, втекающего в сток, а не потока максимальной обобщенной стоимости в смысле выражения (2)). Алгоритм поиска максимального потока строится на базе того простейшего факта, что поток через разрез не может быть больше его пропускной способности, что, в свою очередь, приводит к теореме Форда и Фалкерсона (о максимальном потоке и минимальном разрезе):

в любой сети с одним источником и одним стоком величина максимального потока от источника к стоку равна величине минимального разреза.

Так, для сети (рис. 4) минимальный разрез C_min = {[1,2]; (1, 3)}; а его величина R_c = 3 + 2 = 5 равна величине максимально возможного потока из узла 1 в узел 4 (см. рис. 7).

III. Задача о кратчайшей цепи

1. Постановка задачи

В приложениях теории графов для сетей с одним источником s и одним стоком r большое значение имеет группа задач о кратчайшей (или максимальной) цепи из истока в сток, причем пропускные способности всех дуг сети в таком случае могут быть положены равными бесконечности.

Формулировка задачи имеет следующий вид:

задана сеть - G = {N, A}; для всех дуг из A определена обобщенная стоимость c_ij прохождения единицы потока по дуге, которая в реальных задачах в зависимости от выбранного критерия оптимальности может быть либо временем выполнения каких-либо процессов в моделируемом объекте, либо расстоянием, либо величиной, имеющей денежное выражение и связанной со стоимостью. Для фиктивных дуг, задающих только последовательность узлов, c_ij = 0, для пары узлов i и j, не соединенных дугой, c_ij = .

Интенсивности истока и стока: d_s = 1, d_r = -1; для остальных узлов сети

d = 0.

Требуется найти цепь [s, ..., r] с оптимальной (минимальной или максимальной) суммарной обобщенной стоимостью c_sr всех входящих в нее дуг.

Эта задача может быть представлена, как задача дискретного программирования:

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

2. Алгоритм решения (алгоритм Дейкстры)

Алгоритм Дейкстры применим для неотрицательных элементов матрицы с и состоит из двух частей: прямого и обратного ходов. Прямой ход содержит начальное заполнение и итеративную процедуру. В процессе работы каждому узлу i приписывается, а затем изменяется некоторое число, называемое пометкой, которая может быть двух видов - постоянная L_i или временная I_i . Изменяться при этом могут только временные пометки. Присвоенные узлам постоянные пометки в дальнейшем изменяться не могут.

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

Величина постоянной пометки стока равна обобщенной стоимости неизвестной пока еще оптимальной цепи. Сама цепь определяется во второй части алгоритма Дейкстры и состоит из дуг, для каждой из которых разность между значениями постоянных пометок ее концевых узлов, равна длине (обобщенной стоимости) этой дуги. Иными словами, условие, при выполнении которого узлы i и j принадлежат кратчайшей цепи [s, ..., i, j, ..., r] может быть записано следующим образом:

                     L_j - L_i - c_ij = 0.                                            (5)

Это соотношение можно использовать рекурсивно, двигаясь от узла r к узлу s.

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

Итеративная процедура состоит не более чем из n-1 итерации и продолжается до тех пор, пока источник не попадет в оптимальную цепь. Каждая итерация выполняется по одному и тому же алгоритму и состоит из двух шагов.

Совершенно аналогичным методом может быть решена задача о цепи максимальной длины, однако при этом в прямом ходе алгоритма Дейкстры в выражениях (3) и (4) необходимо min {...} заменить на max {...} (от тех же выражений) и в начальном заполнении прямого хода алгоритма Дейкстры вместо  необходимо ввести - .

При решении конкретных задач возможны два способа реализации алгоритма Дейкстры: графический (удобен для задач с малым числом узлов) и табличный (удобен для задач с большим числом узлов либо при решении задачи с использованием компьютерных электронных таблиц).

3. Пример решения

Рассмотрим работу алгоритма Дейкстры на примере сети, изображенной на рис. 8. Узел s=1 здесь является источником, r=4 - стоком, а числа c_ij, приписанные дугам, соответствуют их длине или обобщенной стоимости. Матрица обобщенной стоимости этой сети имеет вид:

C = ;

Работа алгоритма (см. рис. 9) начинается с того, что источнику приписывается постоянная пометка I₁ = 0, а узлам j = 2,3,4  присваиваются временные пометки I_j = . Таким образом производится начальное заполнение. В дальнейшем производится итеративная процедура. Первая итерация: на первом шаге вычисляются новые временные пометки всех узлов (2, 3, 4), не имеющих постоянных пометок:

I₂’= min {I₂, L₁ + c₁₂} = min { , 0 + 3} = 3,

I₃’= min {I₃, L₁ + c₁₃} = min { , 0 +2} = 2,

I₄’= min {I₄, L₁ + c₁₄} = min { , 0 + } = .

На втором шаге узлу 3, временная пометка которого наименьшая из полученных, присваивается постоянная пометка L₃ = I₃’ = 2.

Вторая итерация: на первом шаге вычисляются новые временные пометки узлов 2, 4, не имеющих постоянных пометок:

I₂’= min {I₂, L₃ +  c₃₂} = min {3,2 + } = 3,

I₄’= min {I₄, L₃ + c₃₄} = min { , 2 + 7} = 9.

На втором шаге узлу 2, временная пометка которого наименьшая из полученных, присваивается постоянная пометка L₂ =I₂’ = 3.

Третья итерация: на первом шаге вычисляется новая временная пометка узла 4, не имеющего постоянной пометки:

I₄’= min {I₄, L₂ + с₂₄} = min {9,3 + 4} = 7.

На втором шаге узлу 4, временная пометка которого наименьшая (и единственная) из полученных, присваивается постоянная пометка L₄ = I₄’ = 7. Так как помеченным оказался сток 4 = r, прямой ход алгоритма Дейкстры закончен.

Графическая демонстрация этого решения приведена на рис. 9; табличное решение - в табл. 1.

Таблица 1: Прямой ход алгоритма Дейкстры

Узел i:	s=1	2	3	r=4
Итерация:	Значения пометок
0	0
1		3	2
2		3		9
3				7

В обратном ходе алгоритма Дейкстры (см. рис. 10) участвуют все 4 узла. После исходного заполнения оптимальная цепь имеет вид [?, 4]. Первая итерация: на первом шаге вычисляются величины:

1 = L₄ - L₁ - c₁₄  = 7 - 0 - = - ,

2 = L₄ - L₂ - c₂₄  = 7 - 3 - 4 = 0,

3 = L₄ - L₃ - c₃₄  = 7 - 2 - 7 = - 2.

На втором шаге узел 2, для которого ₂ = 0, включается в оптимальную цепь [?, 2, 4].

Вторая итерация: на первом шаге вычисляются величины:

1 = L₂ - L₁ - c₁₂ = 3 - 0 - 3 = 0, ₃ = L₂ - L₃ - c₃₂ = 3 - 2 - = - .

На втором шаге узел 2, для которого ₁ = 0 включается в оптимальную цепь [1, 2, 4]. Так как это источник (1 = s), обратный ход алгоритма Дейкстры закончен.

Графическая демонстрация этого решения приведена на рис. 10; табличное решение - в табл. 2.

Таблица 2: Обратный ход алгоритма Дейкстры

 

Таким образом, с использованием алгоритма Дейкстры решена задача поиска кратчайшей цепи (цепи наименьшей обобщенной стоимости) для сети G (см. рис. 8). Оптимальная цепь: [1, 2, 4], ее длина 7. Оптимальный поток F_min в сети G: F_min  = {f₁₂ = 1; f₁₃ = 0; f₂₃ = 0; f₂₄ = 1; f₃₄ = 0}.

4.     Примеры экономических задач, сводимых к задаче о кратчайшей цепи

 

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

При планировании работ по осуществлению проекта в методе критического пути узлами являются события - решения о начале выполнения некоторой (или некоторых) работы; дугами - сами работы. В зависимости от характееристик работы могут быть трех видов: реальные с ненулевыми стоимостью выполнения и временем выполнения; пассивные с нулевыми стоимостью выполнения и ненулевым временем выполнения; фиктивные с нулевыми стоимостью выполнения и временем выполнения, вводимые для выполнения условий упорядоченности совершения событий. В такой постановке продолжительность всего проекта определяется в задаче о максимальной по продолжительности цепи.

5.     Тестовые вопросы.

На тестовые вопросы можно ответить с оценкой ответа ЗДЕСЬ,

либо без оценки ЗДЕСЬ.

 

IV. Задача о минимальном остовном контуре

1. Постановка задачи

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

Формулировка задачи имеет следующий вид:

задана сеть - G = {N, A}; для всех дуг из A определена обобщенная стоимость c_ij прохождения  единицы потока по дуге, которая в реальных задачах в зависимости от выбранного критерия оптимальности может быть либо расстоянием, либо величиной, имеющей денежное выражение и связанной со стоимостью. Для фиктивных дуг, задающих только последовательность узлов, c_ij  = 0, для пары узлов i и j, не соединенных дугой, c_ij = . В сети нет истока и стока; интенсивность всех узлов сети d = 0.

Требуется найти остовный контур G₁ = {[1, ..., i, ..., 1]; i N} с оптимальной (минимальной или максимальной) суммарной обобщенной стоимостью C_G1 всех входящих в него дуг.

Эта задача может быть представлена, как задача дискретного программирования:

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

2. Алгоритм решения (алгоритм Литтла)

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

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

Алгоритм Литтла состоит из следующих блоков:

1.     Редуцирование ацикличных и однонаправленных участков сети G (обязательный блок).

2.     Вычисление верхней границы длин маршрутов (необязательный блок).

3.     Итеративная процедура построения дерева маршрутов:

3.1. Редукция матрицы длин дуг по строкам и столбцам.

3.2. Вычисление нижней границы длины маршрута.

3.3. Вычисление штрафов.

3.4. Ветвление дерева маршрутов.

3.5. Анализ дерева маршрутов на возврат, подциклы и полный маршрут.

3.6. Получение новой матрицы длин дуг с учетом 3.4 и 3.5.

Выделение в сети G подграфа G₁, не содержащего узлов, каждый из которых связан с каким-то одним узлом оставшейся сети, и только с ним, называется редуцированием ацикличных и однонаправленных участков. Здесь необходимо также удалить те узлы, в которые входят только направленные дуги, и не выходит ни одной дуги, и наоборот, только направленные дуги выходят, и не входит ни одной дуги. При этом количество узлов полученного G₁ оказывается равным N₁.

Длина L (T) маршрута T равна сумме элементов матрицы длин дуг, входящих в маршрут T. Для любого допустимого маршрута каждая строка и каждый столбец матрицы C содержат ровно по одному элементу, соответствующему этому маршруту. Величина L (T) определена для любого допустимого маршрута и длина оптимального маршрута не может превосходить значение L(T) для такого T. Следовательно, значение L(T) всякого допустимого маршрута является верхней границей длины оптимального маршрута.

Если из каждого элемента некоторой строки матрицы расстояний вычесть постоянную величину C, то длина любого маршрута, определяемая новой матрицей, меньше длины того же маршрута, определяемой старой матрицей, на величину С (верно, так как каждому маршруту соответствует ровно один элемент данной строки). Однако относительные длины всех маршрутов останутся неизменными. Таким образом, при переходе от исходной матрицы расстояний к новой останутся неизменными и все оптимальные маршруты. Такое же утверждение справедливо и для элементов столбцов матрицы расстояний. Процедуры вычитания из каждого элемента строки наименьшего элемента этой же строки и из каждого элемента столбца наименьшего элемента этого же столбца называются редукцией строк и редукцией столбцов, соответственно. Матрица с неотрицательными элементами, в каждой строке и каждом столбце которой содержится по крайней мере один нулевой элемент, называется редуцированной матрицей. Она может быть получена в результате последовательной редукции ее строк и столбцов.

Если L (T) - длина маршрута T , определяемая матрицей расстояний до выполнения редукции, L’ (T) - длина того же маршрута, определяемая редуцированной матрицей, а H - сумма всех констант, используемых при вычислении редуцированной матрицы, то L (T) = H + L’ (T). Поскольку редуцированная матрица содержит только неотрицательные элементы, то H является нижней границей длины маршрута T для нередуцированной матрицы расстояний.

Штрафом Ф_ij за неиспользование в полном маршруте дуги [i, j], для которой на данной итерации в редуцированной матрице c_ij = 0, называют увеличение стоимости полного маршрута при невключении в него этой дуги. Для вычисления штрафов используется следующее выражение:

Ф_ij = {c_kj} + {c_ik}.

Ветвление - процесс разбиения множества всех маршрутов на непересекающиеся подмножества. Может быть представлен в виде построения дерева, корень которого имеет пометку <все маршруты>, а остальные узлы могут быть двух видов: а) с пометкой о включении в рассматриваемые маршруты дуги [i, j] и б) с пометкой о невключении в рассматриваемые маршруты этой дуги. У каждого узла дерева должна быть проставлена величина нижней границы подмножества тех маршрутов, которое выделено цепью от корня дерева до данного узла. Из каждого узла типа а) выходит две дуги - в узлы типа а) и б) (кроме узлов предпоследнего (одна дуга) и последнего (нет дуг) уровней, причем уровнем узла считается количество разделяющих его и корень в цепи узлов; всего уровней N₁). Из каждого узла типа б) дуг не выходит. В полном дереве маршрутов самая длинная цепь, выходящая из корня, состоит из всех узлов, входящих в минимальный остовный контур, причем величина нижней границы у последнего узла этой цепи равна стоимости оптимального маршрута. На каждом уровне в дерево маршрутов включается та дуга [i, j], для которой величина штрафа максимальна. При этом после анализа на возврат и подциклы при получении матрицы следующей итерации из нее удаляются i-я строка и j-й столбец. При получении матрицы 2 х 2, в которой обязательно должны содержаться два бесконечных и два конечных элемента, расположенных по диагоналям (иначе в процессе вычислений была допущена ошибка, итерации заканчиваются в случае невозникновения возврата, так как в такой матрице обязательно должны быть выбраны обе дуги, соответствующие конечным элементам.

Если в процессе построения дерева маршрутов величина нижних границ узлов типа а) и б) превысила на данном уровне величину нижней границы какого-либо узла типа б) для дуги [i, j] на предыдущих уровнях, производится процедура возврата к этому узлу, и все вычисления повторяются с момента, предшествующего выбору этой дуги, причем величина c_ij временно полагается равной . Величина нижней границы для узла типа б) есть сумма нижней границы предыдущей итерации и штрафа за невыбор выбранной на этой итерации дуги. Величина нижней границы для узла типа а) есть сумма нижней границы предыдущей итерации и всех констант, которые вычитались из строк и столбцов матрицы в процедуре редукции на данной итерации.

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

3. Пример решения

Рассмотрим работу алгоритма Литтла на примере сети, изображенной на рис. 11. Числа c_ij, приписанные дугам, соответствуют их длине или обобщенной стоимости. Матрица обобщенной стоимости этой сети имеет вид:

C =

Работа алгоритма начинается с редуцирования ацикличных и однонаправленных участков сети. Результат приведен на рис. 12. Из матрицы C при этом вычеркиваются строки и столбцы с одинаковыми номерами, в которых не на главной диагонали имеется не более одного конечного элемента, то есть в нашем случае №№ 4, 5. Матрица редуцированного циклического подграфа G₁ имеет вид:

C₁ =

Для вычисления верхней границы используем цепь [1, 2, 3, 4, 1]:

H_max = H [1, 2, 3, 4, 1] = 17 + 7 + 11 + 3  =  38.

Процедура итераций:

Итерация № 1.

 

Нижняя граница стоимости всех маршрутов, которая получается на этой итерации, есть сумма всех величин, на которые редуцировалась матрица (они выписаны справа от исходной и снизу от редуцированной по строкам матриц): H₁ = 22 + 0 = 22.

В последней таблице справа и снизу выписаны наименьшие (кроме нуля) элементы в строках и столбцах, соответственно. Сумма тех из них, которые расположены в тех же столбце и строке, что и какой-нибудь ноль, есть штраф за невыбор этого нуля. Для каждого нуля вычисляем штрафы:

i, j	1,4	2,3	3,2	4,1
Фij	10	9	7	8

Так как максимален Ф₁₄, то все маршруты делятся на две группы: содержащие дугу [1, 4], и ее не содержащие (в дереве маршрутов метка [1, 4], рис. 13). Нижняя граница стоимости всех маршрутов, не содержащих дугу [1, 4], вычисляется как сумма H₁ и Ф₁₄: Н₁₄ = 22 + 10 = 32. Элемент с₄₁ полагается равным . Поверок на возврат и подциклы на итерации №1 не производится, нижняя граница второй вершины рис. 13 вычисляется на следующей итерации №2, в которой рассматривается матрица без первой строки и четвертого столбца.

Итерация № 2.

 

Нижняя граница узла [1, 4], которая получается на этой итерации, есть сумма всех величин, на которые редуцировалась матрица, и предыдущей нижней границы H₁: H₁₄ = 22 + 5 + 3 = 30.

Для каждого нуля вычисляем штрафы:

i, j	2,3	3,1	3,2	4,2
Фij	10	7	0	3

Так как максимален Ф₂₃, то маршруты, содержащие дугу [1, 4], делятся на две группы: содержащие дугу [2, 3] и ее не содержащие (в дереве маршрутов метка [2, 3], рис. 14). Причем нижняя граница стоимости всех маршрутов, не содержащих дугу [2, 3], вычисляется как сумма H₁₄ и Ф₂₃: Н₂₃ = 30 + 10 = 40. Элемент с₃₂ полагается равным . Проверка на возврат и подциклы на итерации № 2 результата не дает, так как H₁₄ < min {H_max, H₁₄} и из дуг [1, 4] и [2, 3] нельзя образовать подцикл добавлением любой третьей, нижняя граница второй вершины (рис. 14) вычисляется на следующей итерации № 3, в которой рассматривается матрица без второй строки и третьего столбца.

 

Итерация № 3.

 

Нижняя граница узла [2, 3]: H₂₃ = H₁₄+ 0 + 0 = 30.

Для каждого нуля вычисляем штрафы:

i, j	3,1	4,2
Фij

Бесконечные штрафы означают, что мы обязаны выбрать обе дуги, которым соответствуют конечные элементы матрицы, прием при выборе их получается полный маршрут. В такой ситуации нижние границы H₃₁ и Н₄₂ равны между собой и равны H₂₃ (нижней границе данной итерации). Так как H₂₃ < min {H_max, H₁₄, H₂₃}, то возврата нет; так как замкнут полный маршрут, то подцикл не образован. Вообще говоря, наличие на какой-либо итерации матрицы 2 х 2, аналогичной полученной здесь, свидетельствует о правильности произведенных вычислений и об окончании итераций и без вычисления штрафов. Результирующее дерево маршрутов приведено на рис. 16.

В результате итеративного процесса получен минимальный остовный контур [1, 4, 2, 3, 1] графа G₁ (рис. 12) с обобщенной стоимостью 30. Для получения минимального остовного контура исходной сети G (рис. 11) необходимо в него добавить контуры от редуцированных на первом этапе алгоритма участков: [1, 4, 6, 4, 2, 3, 1, 5, 1], а к стоимости добавить с₁₅ + с₅₁  + с₄₆  + с₆₄, что даст окончательную величину обобщенной стоимости найденного минимального остовного контура:

С _{[1, 4, 6, 4, 2, 3, 1, 5, 1]} = 30  + 2  + 4  + 5  + 5 = 46.

Решение задачи получено. Необходимо, однако, отметить, что в данном случае не встретилась ситуация возврата и ситуация устранения возможного подцикла, и сели последняя встретится ниже в примере выполнения домашнего задания, то ситуацию возврата иллюстрирует дерево маршрутов (рис. 17) для задачи с нижеприведенной матрицей обобщенной стоимости, причем из-за наличия только нулевых штрафов на первой итерации (ситуация большого количества близких по стоимости маршрутов) при выборе на первой итерации дуги [1, 5] уже на третьей возникает возврат, так как на этой итерации H₃₄ оказывается больше H₁₅ (см. рис. 17).

C = .

Более того, при проведении процедуры возврата к первой итерации (при этом c₁₅ = ) на итерации 2’ снова возникает возврат (см. рис. 17) за счет отмеченной выше особенности матрицы примера.

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

Среди задач, решаемых с помощью алгоритма Литтла, особое место занимает задача коммивояжера.

Задача коммивояжера может быть сформулирована следующим образом. Коммивояжер должен выехать из заданного города, побывать в каждом из остальных n-1 городов ровно один раз и вернуться в исходный город. Задача заключается в определении последовательности объезда городов, при которой коммивояжеру требуется проехать наименьшее суммарное расстояние. При этом предполагается, что расстояние для каждой пары городов известно. Вместо длины пути можно рассматривать любые другие критерии эффективности, такие, как стоимость, время и т. д.

Нетрудно заметить, что всего существует (n-1)! возможных маршрутов, среди которых один или несколько - оптимальные. Однако если некоторые города для коммивояжера недоступны, то минимальное значение целевой функции должно быть бесконечным. В большинстве случаев можно считать, что расстояние между городами i и j является симметричным, то есть расстояние от города i до города j равно расстоянию от города j до города i. Однако для алгоритма, который был приведен выше, данное предположение можно опустить.

5. Заключительные замечания

Следует отметить, что задача коммивояжера является комбинаторной задачей, поскольку число возможных маршрутов экспоненциально зависит от числа городов. Данная задача принадлежит к классу так называемых NP-полных задач. Было показано, что многочисленный класс комбинаторных задач является классом эквивалентных задач, где эквивалентность понимается в том смысле, что либо все они могут быть решены с помощью алгоритмов, имеющих полиномиальную сложность вычислений, либо ни одна из них не может быть решена с помощью таких алгоритмов. Данная группа задач образует класс NP-полных задач. И. наконец, задача коммивояжера не может быть непосредственно сформулирована и решена как задача линейного программирования. Она относится к классу потоковых задач в силу исторически сложившейся связи между методами их решения и в силу ее графического представления как задачи об оптимальном маршруте.

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

6.     Тестовые вопросы.

На тестовые вопросы можно ответить с оценкой ответа ЗДЕСЬ,

либо без оценки ЗДЕСЬ.

 

Дополнительная литература

1. Ю. М. Ермолаев и др. Математические методы исследования операций. Киев: “Вища школа”, 1979 г.

2. Д. Филлипс, А. Гарсиа-Диас. Методы анализа сетей. М.:Мир, 1984 г.

3. Н. М. Губин и др. Экономико-математические методы и модели в планировании и управлении в отрасли связи. М.: Радио и связь, 1993 г.

Выполнение заданий с использованием компьютера

Оба задания для самостоятельной работы студентов могут быть выполнены как с использованием вычислительных средств, так и вручную. Однако с точки зрения общего образовательного уровня рекомендуется выполнение этих заданий на ПК, при этом необходимо иметь в виду достаточный для этого уровень обеспечения студентов СПбГУП временем доступа к компьютерным классам и высокий уровень программного обеспечения в этих классах. При выполнении заданий на компьютере возможны три различных варианта в зависимости от уровня подготовки конкретного студента:

1. Разработка программной реализации вышеизложенных алгоритмов в каком-либо доступном студенту языке программирования (C, Basic, FORTRAN). Данный подход приемлем лишь для студентов с высоким уровнем подготовки в области информатики. Обсуждение вариантов выполнения работ такими студентами может быть проведено ими в индивидуальном порядке с преподавателем, ведущим практические занятия.

2. Использование в расчетах широко распространенных математических пакетов общего назначения (таких, как MathCad, MathLab, Eureca). Этот подход может быть реализован на условиях предыдущего варианта.

3. Использование в расчетах крупноформатных электронных таблиц (таких, как Excel 97, ЭТ пакета Works 2.0). Этот вариант доступен студентам любого уровня подготовки, так как в компьютерных классах установлены файлы примеров выполнения данных заданий (каталог NetPl на сетевом сервере, файлы ShortPath и Hamilton – здесь гиперссылки на них - с расширениями xls для Excel 97).

При использовании этих файлов необходимо помнить, что задания в них выполнены для конкретных исходных данных и при их изменении (Коэффициенты годовой инфляции в задании файла ShortPath и исходная матрица в Hamilton) автоматически пересчитывается не весь рабочий лист, так как в целях понимания студентом работы самого алгоритма прямой и обратный ход алгоритма Дейкстры в задании ShortPath и процедуры алгоритма Литтла в задании Hamilton реализованы с ручным выбором постоянных пометок и оптимального пути в первом случае, и с ручной реализацией всех частей алгоритма Литтла, кроме процедуры редукции матрицы. Более конкретную информацию о правилах работы с этими файлами можно получить на семинарских занятиях у преподавателя.

 

Редактор В. А. Меньшенина

Технический редактор О. Ю. Козырева

Корректор Н. А. Бобкова

 

 

© А.М.Махов, 1996

© Оформление, СПбГУП, 1996

© Гипермедийная версия: Ó 2001, Махов А.М.