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


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


68

ЛСО) = 2(0) + /з(0) = о + о = о, xliO) = о, Л(1) = тах{2(0) + /з(1),20) + /з(0)} = гпах{2,1} = 2,

Л (2) = max (0) + f, (2), (1) + /з (1), 2(2) + /з (0)} = max {4,3,3} = 4,

х;(2) = 0,

Л (3) = max (0) + /з (3), <Р2 (1) + /з (2), (2) + /з (1), <Р2 (3) + /з (1)} = = max{5,5,5,6} - 6,

х;(3) = 3,

/2 (4) = max

2(0) + /з(4),2(1) + /з(3),2(2) + [+/з (2), <р, (3) + /з (1),(4) + /з (0) J

х;(4) = 3,

= max{6,6,7,8,7} = 8,

/2(5) = max <

2 (0) +/3 (5), 2 0) +/3 (4), 2 (2) + +/з(3),2(3) + /з(2),«2(4) + /з(1),«2(5) + /з(0) J = max{8,7,8,10,9,8} = 10,

x;{5) = 3.

Далее вычислим значения функции /(й?) и соответствующие значения x*(u?) исходя из соотношения

f(d) = max{<p(x,) + f(d-x,)}. 0<x, <d

/,(0) = ,(0) = 0, х;(0) = 0,

/,(1) = тах{,(0) + M\),<PiO) + /2(0)} = max{2,3} = 3, хЛ\) = 1



yj(4) = max

= max{8,9,8,7,7} = 9.

/,(2) = max{,(0) + Л(2),,(1) + Л(1),«?,(2) + Л(0)} = max{3,5,4} = 4,

xl(2) = \,

f, (3) = max (0) + Л (3), (p, (1) + (2), «о, (2) + Л (1), , (3) + Л (0)} = = max{6,7,6,5} = 7,

,*(3) = 1,

>,(0) + Л(4),«»,(1) + Л(3),,(2) + +/2(2),«,,(3) + Л(1),,(4) + /2(0)

x;(4) = l,

>,(0) + /2(5),,(1) + Л(4),,(2) + Л(3),,(3) + Л(2),,(4) + Л(1),,(5) + /(0)] = max{lO,l 1,10,9,9,8} = 11, х\{5) = \.

Результаты приведенных вычислений собраны в табл. 7.2.

Таблица 7.2

/(5) = max

х\{х)

x2(x)

Как отмечалось, максимальная эффективность может быть вычислена из соотношения

max = max {0,3,5,7,9,11} = 11. 0<х<5

Далее воспользуемся общими соотношениями (7.3) для нахождения оптимального распределения

х[=х\{5) = \.



xl =Хз(5-х* -Х2) = ХзЧ5-1-3) = Хз(1) = 1.

Ответ, Оптимальным распределением кредитных денег между предприятиями является распределение: 1-е предприятие 1 млн. руб.; 2-е предприятие 3 млн. руб.; 3-е предприятие 1 млн. руб. Ожидаемая при этом прибыль составит 11 млн. руб.

К задачам рассматриваемого типа относится и такая классическая задача линейного программирования, как задача о рюкзаке, которая в переменных О и 1 имеет следующий вид:

max z = qx, -i- С2Х2 +... + с„х„ aiXi+a2X2+... + a„x„<fe, x,g{0; 1}, / = 1, 2,...,«.

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

либо нет (х, = 0). Выбор /-й позиции требует затрат ресурса в количестве . Общее количество имеющегося в распоряжении ресурса равно Ь. Эффект от выбора i-и позиции есть q . Следует осуществить выбор среди позиций, допустимый в смысле затрат ресурсов и имеющий максимальный суммарный эффект.

7.3. Метод динамического программирования в недетерминированном случае

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

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

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