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


[Старт] [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] [148] [149] [ 150 ] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [248] [249] [250] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [267] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293]


150

Этап 1.

/i(vi,vvi)= 0max + У2(v, - 2jCj,w,)} = max {2jc, +5min(v,-2xvw,)}.

Оптимизация на первом этапе требует решения минимаксной задачи, что в общем случае является достаточно сложным делом. Для рассматриваемой задачи имеем у, = 430 и wt = 230, что дает 0 < 2х, < 430. Так как min(430 - 2xv 230) представляет собой нижнюю огибающую двух пересекающихся прямых (проверьте!), то

„„ „ [230, 0<х<100,

min(430-2x„230)= \ 1

1 [430 - 2*,, 100<л-, <215

(2х. +1150, 0<х<100, /,(430,230)= тах{

J1K * \-8дг, +2150, 100<л-,<215.

Графически можно легко проверить, что функция/,(430, 230) достигает максималь-

ного значения при х,

= 100. Итак, получаем следующее.

Оптимальное решение

Состояние

(430, 230)

1350

Для определения оптимального значения х2 заметим, что

v2 = и, - 2х, = 430 - 200 = 230, w2 = w1 - 0 = 230.

Следовательно,

х2 = min{v2, w2) = 230. Итак, оптимальное решение имеет вид: х, = 100 единиц, х2 = 230 единиц, г = 1350 долл.

УПРАЖНЕНИЯ 10.4

1. Решите следующие задачи линейного программирования методами динамического программирования.

a) Максимизировать г = 4х, + Ых2 при ограничениях

2х, + 7х2<21, 7х1 + 2х2<21, x„*2>0.

b) Максимизировать z = 8х, + 1х2 при ограничениях

2х, + х2 < 8, 5х, + 2х2<15, jc,, х2 > 0 и целые.



с) Максимизировать г = 7 х\ + 6х, + 5 х; при ограничениях

х, + 2х2 < 10, х,-3х2<9, х„ х2>0.

2. Пусть в задаче из примера 10.3.1 о загрузке предметов п наименований ограничения самолета по весу и объему представлены величинами W и V соответственно. Величины wh Vj и г, представляют соответственно вес, объем и прибыль, отнесенные к одному предмету наименования г. Необходимо записать рекуррентное уравнение обратной прогонки для алгоритма динамического программирования решения сформулированной задачи.

ЛИТЕРАТУРА

1. Bertsekas D. Dynamic Programming: Deterministic and Stochastic Models, Prentice Hall, Upper Saddle River, N.J., 1987.

2. Denardo E. Dynamic Programming Theory and Application, Prentice Hall, Upper Saddle River, N.J., 1982.

3. Dreyfus S., Law A. The Art and Theory of Dynamic Programming, Academic Press, New York, 1977.

4. Sniedovich M. Dynamic Programming, Marcel Dekker, New York, 1991.

Литература, добавленная при переводе

1. Беллман Р. Динамическое программирование. - М.: ИЛ, 1960.

2. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. - М.: Наука, 1965.

3. Вентцель Е. С. Исследование операций. - М.: Сов. радио, 1972.

4. Романовский И. В. Алгоритмы решения экстремальных задач. - М.: Наука, 1977.

КОМПЛЕКСНАЯ ЗАДАЧА

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



Комплексная задача

Стоимость содержания (долл.) Стоимость продажи (долл.) для Год Стоимость для данного возраста (лет) данного возраста (лет)

покупки

покупки (долл.)

10 000

9 000

7 000

5 000

12 000

11 000

9 500

8 000

13 000

12 000

11 000

10 000

13 500

12 000

11 500

11 000

13 800

12 000

11 800

11 200

14 200

12 500

12 000

11 200

14 800

13 500

12 900

11 900

15 200

14 000

13 200

12 000

15 500

15 500

14 500

13 800

16 000

15 800

15 000

14 500

[Старт] [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] [148] [149] [ 150 ] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [248] [249] [250] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [267] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293]