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


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


143

а\хи x2) + f2(x2)

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

х2 = 2

х2 = 3 х2 = Л

M*l) х.

7 + 21 = 28

8 + 15 = 23 5 + 16 = 21

21 4

УПРАЖНЕНИЯ 10.2

1. Для задачи из упражнения 10.1.1 получите рекуррентное соотношение обратной прогонки и используйте его для получения оптимального решения.

2. Для задачи из упражнения 10.1.2 получите рекуррентное соотношение обратной прогонки и используйте его для получения оптимального решения.

3. Определите кратчайший маршрут между городами 1 и 7 на сети дорог, представленной на рис. 10.3. Определите этапы и состояния системы с помощью алгоритма обратной прогонки, а затем решите задачу.

Рис. 10.3. Сеть для упражнения 3

10.3. ПРИЛОЖЕНИЯ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

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

1. Определение этапов.

2. Определение на каждом этапе вариантов решения (альтернатив).

3. Определение состояний на каждом этапе.

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

1. Какие соотношения связывают этапы вместе?

2. Какая информация необходима для того, чтобы получить допустимые решения на текущем этапе без повторной проверки решений, принятых на предыдущих этапах?



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

10.3.1. Задача о загрузке

Задача о загрузке - это задача о рациональной загрузке судна (самолета, автомашины и т.п.), которое имеет ограничения по объему или грузоподъемности. Каждый помещенный на судно груз приносит определенную прибыль. Задача состоит в определении загрузки судна такими грузами, которые приносят наибольшую суммарную прибыль.

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

Рекуррентное уравнение процедуры обратной прогонки выводится для общей задачи загрузки судна грузоподъемностью W предметов (грузов) п наименований. Пусть т, - количество предметов i-го наименования, подлежащих загрузке, г,- прибыль, которую приносит один загруженный предмет /-го наименования, w,- вес одного предмета 1-го наименования. Общая задача имеет вид следующей целочисленной задачи линейного программирования.

Максимизировать z = гхтх + г2т2+ ... + гпт„

при условии,что

иуи,+ w2m2 + ... + w„m„< W, ть т2,т„>0 и целые.

Три элемента модели динамического программирования определяется следующим образом.

1. Этап i ставится в соответствие предмету /-го наименования, i = 1,2,п.

2. Варианты решения на этапе i описываются количеством т, предметов /-го наименования, подлежащих загрузке. Соответствующая прибыль равна гр\,. Значение т,- заключено в пределах от 0 до [W/wt], где [W/wJ - целая часть числа W/w,.

3. Состояние х, на этапе i выражает суммарный вес предметов, решения о погрузке которых приняты на этапах /, i + 1,п. Это определение отражает тот факт, что ограничение по весу является единственным, которое связывает п этапов вместе.

Пусть f,(x)- максимальная суммарная прибыль от этапов /, /+ 1, я при заданном состоянии Xj. Проще всего рекуррентное уравнение определяется с помощью следующей двухшаговой процедуры.



Пример 10.3.1

В 4-тонный самолет загружаются предметы трех наименований. Приведенная ниже таблица содержит данные о весе одного предмета w, (в тоннах) и прибыли г, (в тысячах долларов), получаемой от одного загруженного предмета. Как необходимо загрузить самолет, чтобы получить максимальную прибыль?

Предмет /

Так как вес одного предмета w, для всех наименований и максимальный вес W принимают целочисленные значения, состояние х, может принимать лишь целочисленные значения.

Этап 3. Точный вес, который может быть загружен на этапе 3 (предмет наименования 3), заранее неизвестен, но он должен принимать одно из значений 0, 1, 4 (так как W = 4 тонны). Состояния х3= 0 и х3= 4 представляют собой крайние случаи, когда предметы третьего наименования совсем не загружаются или загружают самолет полностью. Остальные значения х3 (= 1, 2 или 3) предполагают частичную загрузку самолета предметами третьего наименования. Действительно при этих значениях х3 все оставшиеся емкости самолета могут быть заполнены предметами третьего наименования.

Так как вес w3 одного предмета третьего типа равен 1 тонне, максимальное количество единиц этого типа, которое может быть загружено, равно [4/1] = 4. Это означает, что возможными значениями х3 будут 0, 1, 2, 3 и 4. Решение т3 является допустимым лишь при условии, что w3m3<x3. Следовательно, все недопустимые альтернативы (те, для которых w3m3> х3) исключены. Следующее уравнение является основой для сравнения альтернатив на этапе 3.

/3(х3) = max{l4m3}, max{m3} =

Шаг1. Шаг 2.

Выразим/;(*,) как функциюв виде

/(*,) = max .{nm,+fM{xM)}, / = 1,2,...,и,

m,=0.1.....МЧ1

г, =0.1.....w

где/U,,) = 0.

Выразим jcjj как функцию дг,- для гарантии того, что левая часть последнего уравнения является функцией лишь xt. По определению Xj - xUl представляет собой вес, загруженный на этапе /, т.е. хг = WjiTij или xUi - Xj- Wjirii. Следовательно, рекуррентное уравнение приобретает следующий вид.

/;(*,.)= max {rifn.+fM(xi-wimi)}, / = 1,2,..., п.

wi,=0.1.....

г, =0.1.....w

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