назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [ 74 ] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]


74

Возникает вопрос, при каком способе соединения центров затраты будут наименьшими? Мы пришли к задаче указанного вида.

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

На нулевом (вспомогательном) шаге выбирается произвольная вершина, например вершина 1 и полагается V\ = {l}, R\ - ®.

К началу к-го шага (к = 1,1) даны множества VjaV и

Rl czR, образующие связный граф = (F, i?). Выберем такое ребро {ikJk) У которого начало лежит в множестве Vj, конец - в его дополнении F \ и которое имеет наименьшую длину среди всех таких дуг, т.е.

iik,Jk)eR, ikeVf, дК и су = = min [cij: (i,J)eR, ieVf,, j€Vj,]

После этого полагаем Vj = Vj,, Rj,x = h {(JkJk)] •

Ясно, что ri = (A;+bA;+l) Tb СВЯЗНЫЙ граф, так как новая вершина 7 связана с любой вершиной из множества Vj через вершину .

Поскольку на каждом шаге к множеству Vj добавляется ровно одна вершина, то на шаге к = п-\ мы получим, что Vy = V. При этом, согласно сказанному, Г„ =(F,i?„) есть связный граф, т.е. по определению R является остовом исходного графа, Г =(y,R ).

Теорема. Множество R есть остов минимальной длины. Перед тем

как доказать эту теорему, продемонстрируем работу алгоритма на примере графа, указанного на рис 8.6.

Решение. ШагО. Полагаем = {l}, i?i = ®.

Шаг 1. Минимальным среди чисел q2=4, 3=6, q4=5 является Поэтому полагаем V2 = {1,2}, R2= {(1,2)}.

Шаг 2. Минимальным среди чисел Сз =6, С4 =5, С23 =1, С25 =7 является С23. Поэтому полагаем F3 = {1,2,3}, i?3 = {(1,2),(2,3)}.

ШагЗ. Минимальным среди чисел q4 = 5, С25 = 7, С34 = 2, 35=5, сз5=4 является С34. Поэтому полагаем F4 ={1,2,3,4}, i?4={a2),(2,3),(3,4)}.



Шаг 4. Минимальным среди чисел С35 = 5, С25 = 7, С36 = 4, С45 = 5 является с35.

Поэтому полагаем

F5 ={1,2,3,4,6}, ={(1,2),(2,3),(3,4),(3,6)}.

Шаг 5. Минимальным среди чисел С35 = 5, С25 = 7, 05 = 1 является . Поэтому полагаем

Кб ={1,2,3,4,6,5}, i?6 ={(1,2),(2,3),(3,4),(3,6),(6,5)}.

Таким образом, минимальные затраты на прокладку кабеля достигаются при соединении пар центров из вершины и равны y(i?5)=4 + 1 + 2 + 44- 1 = 12. Минимальный остов изображен на рис. 8.7.

Рис. 8.7

Теперь докажем приведенную теорему, для простоты ограничившись случаем, когда все числа су ((iJ) е R) различны.

Доказательство. Пусть R* - остов наименьшей длины и R R* . Ясно, что не может лежать целиком в R*, так как иначе f{Rn)< /(R*) и, значит, R* не есть решение задачи. Тогда найдется такая дуга (ij) € , что ((/,У) R*. Согласно построению множества R существует такой индекс к е {1, «}, что {iJ) = {ikJk) Поскольку Г* = (К,Л*) - связный граф, то вершины и jj могут быть соединены

некоторым маршрутом, все дуги которого лежат в it. Начало этого маршрута лежит в , а конец д не лежит. Следовательно, найдется та-230



кая дуга (г, s) этого маршрута, что г eVj и s V/, Тогда по определению дуги QkJk) (и с учетом различности чисел с/) имеем

\jk rs(8-4)

Введем множество ребер R = R и {{iJk) \ {()}}» образованное из

R* путем замены ребра (г, s) на ребро Qk,Jk)- Граф Г =являет-

ся связным, поскольку вершины г и s соединены маршрутом, проходящим через дугу (ik,Jic)- В то же время из (8.4) имеем f(R) < f(R*), но это противоречит тому, что R* - остов наименьшей длины. Таким образом, R= R*.

8.5. Задачи распределения ресурсов на сетевых графиках

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

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

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [ 74 ] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]