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


[Старт] [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]


76

0."Ч-Д) =5 = 1,.

xeX; (Ps{x)>0,

Если мы хотим выбрать такое распределение ресурсов, чтобы время выполнения работ было минимальным по всем распределениям ресурсов, то нам надо решить задачу minmin(;7 -l) при ограничениях задачи

X t

(8.7). Объединяя два последовательных минимума в один, окончательно получаем

in(;7-l),(8.8)

Решение задачи (8.8) всегда существует.

Особо отметим случай, когда распределяется один вид ресурса, например деньги. В этом случае задача (8.8) будет иметь вид

min(;7-l),(8.9)

x = (xi,...,x,„), >0; х<А, 5 = 1,.

где А - заранее заданное количество ресурса, которое распределяется по всем работам. Такой вид распределения ресурсов называется сепара-бельным. Задача (8.9) является сепарабельной задачей нелинейного программирования.

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



min/(x),

(8.10)

xeX, s = \,...,m.

Аналогично задаче (8.9) приведем отдельно постановку задачи (8.10) для случая сепарабельного распределения ресурсов. В этом случае имеется только один ресурс и естественно экономить именно его. Тогда задача (8.10) принимает вид

min Z ,

(8.11)

Xj s=\

>0, s = l,...,m.

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

8.5.3. Оптимальное распределение ресурсов на сетевых графиках при наличии неопределенных факторов.

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

Итак, дан сетевой график с событиями zi,.„,Zjj и работами

/у ,7 = 1,..., т. Каждой работе поставлена в соответствие некоторая непрерывная функция (pj{x,k) ,j = 1,..., т, хеХ, k = 1, г. Эта функция 236



есть время выполнения работы Ij, если выбрано распределение ресурсов

х е X, а неопределенный фактор принял значение L

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

со = min max min -

xeX\<k<r V/

(8.12)

8.6. Задачи распределения ресурсов на транспортных сетях

Мы уже рассматривали задачу о максимальном потоке. Приведем более формальную ее постановку.

Пусть задан ориентированный граф с вершинами zi,...,z и дугами

lj,j =Для каждой вершины Zy определим множество дуг С(у),

выходящих из этой вершины, и множество дуг D(y), входящих в данную вершину. Будем предполагать, что С(1) и 0(т])- пустые множества. Вершину Zj будем называть источником, а вершину Zjj - стоком. Будем считать, что каждой дуге Ij поставлено в соответствие число dj>0,j= 1,..., т, которое мы будем называть пропускной способностью дуги. Ориентированный граф с такими характеристиками будем называть сетью. Тогда задача о максимальном потоке в сети может быть записана как

maxL»(8.13)

[Старт] [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]