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


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


66

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

знать количество особей на начало текущего года - . Другими словами, - состояние популяции на начало этапа /.

Определим функцию /ДЬ,) как максимальную чистую прибьшь, которую можно получить за период Г, Г + 1, Г, имея в начале этапа t состояние .

Рассмотрим теперь три аспекта, упомянутые применительно к данной конкретной задаче.

1.Каково множество допустимых решений на каждом этапе! В каждый год мы не можем вьшовить больше форели, чем есть в озере. Таким образом, для любого состояния / должно выполняться соотноше-ниеО<х, <й,.

2.Какова чистая прибыль, зарабатываемая в год tl Если вылавливается Xf форелей в год, в начале которого форелей было , то чистая прибьшь выражается как v{x)-с(Х/,b),

3.Каково будет состояние к началу t 1-го года! К концу года t в озере будет bf - Х( форелей. К началу следующего года количество форелей

увеличится на 20%, а следовательно, составит 1,2( Ь -х) или

=1,2(6,-X,).

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

fj.(bj) = ma x{r{Xj) - с(Ху., fey,)},

где о< Xf < . Далее на основании соотношения (7.1) получаем соотношение

f,(b,) = max{r(x,)-c{x„b,) + f,,,(l,2(b,-x,))},(7.2)

где 0<х,<Ь,.



Для того чтобы начать вычисления по приведенной схеме, вычислим ff(bf) для всех возможных значений (от О до 10 ООО • (1,2)"). Далее, используя рекурсивное соотношение (7.2), проводим вычисления, пока не получим / (10 ООО), которое будет достигаться при некотором

значении х*. Тогда в начале второго года в озере будет 1,2(10 ООО - х*) форелей. Это означает, что в качестве Х2 можно выбрать любое решение, на котором соотношение (2) достигает значения /2(1,2(10 000-х*)). Продолжая эту процедуру аналогичным образом, можно получить все остальные элементы оптимального решения, а именно Хз,Х4,...,х .

Приведенная модель имеет тот недостаток, что в ней не делается различия между прибылями различных годов. С точки зрения дисконтирования, доходы ранних лет имеют большую ценность, чем последующих. Предположим, что 1 доллар, полученный в начале года / + 1, эквивалентен величине /? < 1, полученной в начале года /. Мы можем учесть эффект дисконтирования, введя коэффициент J3 в рекуррентную формулу (7.2) следующим образом

/(fe,) = max{r(x,)-c(x„ft,) + ;ff/,i(l,2(fe,-x,))},(7.3)

где 0<х,<Ь,.

Пример. Известны прогнозные значения потребления электроэнергии на ближайшие Г лет, а именно г, - прогнозируемая мощность потребления электроэнергии в год /. Каждый год необходимо принимать решение, на сколько нужно увеличить (или уменьшить) мощность выработки электроэнергии. Пусть С/(х) - стоимость увеличения мощности на X кВт ч в году /. Так как мощность может сокращаться, х может быть отрицательной величиной. В течение года 10% ранее выработанной, но не использованной электрической мощности теряется (в первый год потери не происходят). Себестоимость выработки / единиц электрической мощности в год / составляет (/). В начале первого года

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



Решение.

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

1.Каково множество допустимых решений на каждом этапе! Для того, чтобы потребность в электроэнергии бьша бы удовлетворена, необходимо выполнение неравенства >а; , или х, >г, -i,. Это условие и определяет множество допустимых решений на каждом этапе.

2.Каковы затраты в год tl Если - объем наращивания (или сокращения) мощностей в год Г, а ц - мощность на начало года, то затраты выражаются соотношением c{x) + (/, + х,).

3.Каково будет состояние системы к началу t 1-го года! В начале t + 1-го года компания будет располагать 0,9 старых мощностей и х,

новыми, а следовательно, =0,9/,+х,. Теперь мы вновь можем

воспользоваться рекурсивным соотношением (7.1). Определим функцию /Д/) как минимальные затраты на удовлетворение спроса на электроэнергию за годы / + 1, Г при условии, что

мощности на начало года t, составляют fj{ij) = m i n{cJ{xJ) xт

mj{ij -Хр)}, Xj>rj-ij. ]Xnsit<TmAtQu f{d) = 0 для всех

у; (/, ) = min [с, (x,) + m, (/, + x,) + f,, (0, % + x,)},(7.4)

X, >r,

Можно предположить, что мощность не будет превышать max =\ значит, что мы можсм рассмотреть только состоя-

ния о, 1,2, г. Будем использовать соотношение (7.4) для расчетов в обратном направлении до тех пор пока не вычислим /j (100000). Далее мы найдем оптимальные изменения мощностей по годам * ♦ *

1 ,Х2,...,Х2г .

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