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


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


67

7.2. Задача оптимального распределения ресурсов

Допустим, что в нашем распоряжении имеется некоторое количество единиц какого-либо однородного ресурса. В качестве ресурса могут выступать деньги, человеческие технические ресурсы (например, материалы, оборудование) и т.д. в количестве w. Имеется Т объектов его распределения. Это могут быть объекты строительства, инвестиционные проекты, регионы и т. д. Пусть x - количество ресурса, выделяемое на

объект /. Известны функции эффективности при выделении ресурса в количестве X, на объект /-Дх,). Эффективность конкретного способа

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

Xj +Х2 + ... + Х7 = W,

X, 6 {О, 1,2,...}.

Согласно методу динамического программирования нам необходимо определить функции fd) как максимальную эффективность, которую можно получить, распределяя d единиц ресурса по объектам /, / + 1, Г. Как мы уже отмечали, fj{d) =0 для Bcex(i, 0<d<w. Последующие функции {t <Т) допускают задание через следующие рекуррентные соотношения

у; id) = max (X,) + {d - X,)}.(7.5)

Пусть x]{d) - значение х, на котором достигается значение максимума в соотношение (7.5). Сначала с помощью соотношения (7.5) находятся значения функции fj{x) и xj.(x) для всевозможньос значений аргумента (0<х< w). Далее аналогичным способом из соотношения (7.5) строятся функции /7 i(x) и X7 i(x)h так далее, заканчивая функциями /, (х) и Xi*(x). Значение max /Лх) и есть максимальная эффективность,

которая достигается при оптимальном способе распределения ресурсов между объектами. Само же оптимальное распределение X* =s(x*,xj,...,x*) получается как



b,-x,

(7.6)

Пример. Банк намерен предоставить 5 млн. руб. в качестве кредита для модернизации трех предприятий. Расчеты показывают, что вьщеле-

ние /-му предприятию (/ = 1, 2, 3) млн. руб. принесет /(/ млн. руб. прибыли (см. табл. 7.1). Как следует распределить всю сумму кредита по предприятиям, чтобы получить максимальную суммарную прибыль, если средства выделяются в размерах, кратных 1 млн. руб.?

Таблица 7.1

<Piix )

<Р2(х )

(Рз(х )

Решение.

Исходя из общего вида задачи (7.2) и учитывая, что w = 5, а Г = 3, данную задачу можно записать в виде:

max((Pi (xi) + <г?2 (Х2) + (р (х))

Xj + Х2 + Хз = 5, .

х,е{о, 1,2,3,4,5}, / = 1,2,3.

Вычислим функции /з(), f{d), fid). Как бьшо отмечено, f(cl) = О для всех значений ((i = О, 1, 2, 3, 4, 5).

**/**\



Вычислим значения функции f{d) и соответствующие значения xlid) исходя из соотношения

/з() = тах{(Хз) + /Дй?-х,)}

О < Хз < й?

или так как /4 (с?) = О, имеем

/з() = тахз(хз) Q<x<d

/з(0) = з(0) = 0, хз*(0) = 0,

/з(1) = тах{з(0),з(1)} = тах{0,2} = 2,

/з(2) = тах{«?з(0),«?з(1),«?з(2)} = тах{0,2,4} = 4, ХзЧ2) = 2,

/з(3) = тах{«?з(0),з(1),з(2),з(3)} = тах{0,2,4,5} = 5, з(3) = 3,

/з(4) = тах{«?з(0),з(1),з(2),з(3),«?з(4)} = тах{0,2,4,5,б} = 6,

Хз*(4) = 4,

/з(5) = тах{з(0),з(1),з(2),з(3),з(4),з(5)} = max (0,2,4,5,6,8} = 8,

Хз(5) = 5.

Далее вычислим значения функции /зС) и соответствующие значения XjCflf) исходя из соотношения

/2 {d) = max (2) + /3 - 2)} •

0<X2 <d

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