Синтез оптимальных систем методом динамического проектирования. Лабораторная работа №4 (1253750), страница 3
Текст из файла (страница 3)
Из всехвыигрышей последнего столбца выбирается максимальный (в табл.А.3 он равен3,6, а соответствующее управление x(7)=2).7 _________________________________________________________________________________Деменков Н.П. Синтез оптимальных систем методом динамического программированияМосковский государственный технический университет им.Н.Э.БауманаКафедра “Системы автоматического управления”__________________________________________________________________________________Приложение Б. Задача о загрузке или задача о рюкзаке (ранце)Задачаорюкзаке (Knapsackproblem)однаизполных задач комбинаторнойоптимизации.Названиесвоёполучилаот максимизационной задачи укладки солдатом или туристом как можнобольшего числа ценных вещей в рюкзак (ранец) при условии, что общий объём(или вес) всех предметов, способных поместиться в рюкзак, ограничен. Задачио загрузке и её модификации часто возникают в экономике, прикладнойматематике, криптографии, генетике и логистике для нахожденияоптимальной загрузки транспорта (космического аппарата, самолёта,автомашины, поезда, трюма корабля и т.п.) или склада, которые имеетограничения по объему или грузоподъемности.
Каждый размещенный грузприносит определенную прибыль. Задача состоит в определении загрузкитакими грузами, которые приносят наибольшую суммарную прибыль.В общем виде задачу можно сформулировать так: из заданногомножества предметов со свойствами «стоимость» и «вес», требуетсяотобрать некое число предметов таким образом, чтобы получитьмаксимальную суммарную стоимость при одновременном соблюденииограничения на суммарный вес.Рекуррентное уравнение процедуры обратной прогонки выводится дляобщей задачи загрузки некоторого объема грузоподъемностью W предметов(грузов) n наименований.
Пусть ki -количество предметов i-го наименования,подлежащих загрузке, сi - прибыль, которую приносит один загруженныйпредмет i-го наименования, wi - вес одного предмета i-го наименования. Общаязадачаимеетвидследующейцелочисленнойзадачилинейногопрограммирования.Максимизировать J = c1k1 + c2k2 + ... + cnkn при выполнении условий:w1k1 + w2k2 + ... + wnkn = W, k1, k2, ..., kn > 0 и целые.Три элемента модели динамического программирования определяетсяследующим образом.1.Шаг i ставится в соответствие предмету i-го наименования, i =1,2,..., n.2.Варианты решения на шаге i описываются количеством ki,предметов i-го наименования, подлежащих загрузке.
Соответствующаяприбыль равна ciki. Значение ki заключено в пределах от 0 до [W/wi], где [W/wi] —целая часть числа W/wi.3.Состояние xi, на шаге i выражает суммарный вес предметов,решения о погрузке которых приняты на шагах i, i + 1,..., n. Это определениеотражает тот факт, что ограничение по весу является единственным,которое связывает n шагов вместе.Пусть Ji(xi) - максимальная суммарная прибыль от шагов i, i + 1,...,n при заданном состоянии xi. Проще всего рекуррентное уравнениеопределяется с помощью следующей процедуры:1) Выразим Ji(xi) как функцию Ji+1(xi+1) в виде{ci ki J i 1 ( xi 1 )} , i=1,2,…,nJ i( xi ) = maxk i 0 ,1,...,[W / wi ]ci 0 ,1,...,W2) Выразим xi+1 как функцию xi для гарантии того, что левая частьпоследнего уравнения является функцией лишь xi. По определению xixi+1 представляет собой вес, загруженный на шаге i, т.е.
xi - xi+1 = wiki или xi-1=xi - wiki. Следовательно, рекуррентное уравнение приобретает следующий вид:8 _________________________________________________________________________________Деменков Н.П. Синтез оптимальных систем методом динамического программированияМосковский государственный технический университет им.Н.Э.БауманаКафедра “Системы автоматического управления”__________________________________________________________________________________J i( xi ) =maxki 0 ,1,...,[W / wi ]ci 0 ,1,...,W{ci ki J i 1 ( xi wi ki )} , i=1,2,…,nПример.
В 4-тонный КА загружаются предметы трех наименований.Табл. Б.1 содержит данные о массе одного предмета wi (в тоннах) иприбыли сi (в тысячах условных единиц), получаемой от одного загруженногопредмета. Как необходимо загрузить КА, чтобы получить максимальнуюприбыль?Таблица Б.1Предмет iwi (масса)сi (прибыль)123123473114Так как масса одного предмета wi для всех наименований имаксимальнаямасса W принимаютцелочисленныезначения,состояние xi может принимать лишь целочисленные значения.Точная масса, которая может быть загружена на шаге 3 (предметнаименования 3), заранее неизвестна, но она должна принимать одно иззначений 0, 1, ..., 4 (так как W = 4 тонны).
Состояния x3 = 0 и x3 = 4представляют собой крайние случаи, когда предметы третьего наименованиясовсем не загружаются или загружают КА полностью. Остальные значения x3,равные 1, 2 или 3, предполагают частичную загрузку КА предметами третьегонаименования. Действительно при этих значениях x3 все оставшиеся емкостисамолета могут быть заполнены предметами третьего наименования.Шаг 3. Так как масса w3 одного предмета последнего третьего типаравна 1 тонне, то максимальное количество единиц этого типа, котороеможет быть загружено, равно [4/1] = 4. Это означает, что возможнымизначениями x3 будут 0, 1, 2, 3 и 4.
Решение k3 является допустимым лишь приусловии, что w3k3 < x3. Следовательно, все недопустимые альтернативы (т.е.для которых w3k3 > x3) исключены. Основой для сравнения альтернатив натретьем шаге является уравнение:4J 3 ( x3 ) = max{14k3} , max{k3}= =4.1k3В табл.Б.2 сравниваются допустимые решения для каждого значения x3Таблица Б.2x3k3 = 0k3 = 1k3 = 2k3 = 3k3 = 4J3(x3)k300----001014---141201428--28230142842-4234014284256564Шаг 2.
Основой для сравнения альтернатив на втором шаге являетсяуравнение:9 _________________________________________________________________________________Деменков Н.П. Синтез оптимальных систем методом динамического программированияМосковский государственный технический университет им.Н.Э.БауманаКафедра “Системы автоматического управления”__________________________________________________________________________________4J 2 ( x2 ) = max{47k2 J 3 ( x2 3k2 )} , max{k2}= 3 =1. k2В табл.Б.3 сравниваются допустимые решения для каждого значения x2Таблица Б.3x2k2 = 0k2 = 1J2(x2)k200+0=0-0010 + 14 = 14-14020 + 28 = 28-28030 + 42 = 4247 + 0 = 4747140 + 56 = 5647 + 14 = 61611Шаг 1.
Основой для сравнения альтернатив на первом шаге являетсяуравнение:4J1 ( x1 ) = max{31k1 J 2 ( x1 2k1 )} , max{k1}= =2.2k1В табл.Б.4 сравниваются допустимые решения для каждого значения x1Таблица Б.4x1k1 = 0k1 = 1k1 = 2J1(x1)k100+0=0--0010 + 14 = 14--14020 + 28 = 2831 + 0 = 31-31130 + 47 = 4731 + 14 = 45-47040 + 61 = 6131 + 28 = 5962 + 0 = 62622Оптимальное решение определяется теперь следующим образом.
Изусловия W=4 следует, что первый шаг решения задачи при x =4 даетоптимальное решение k1=2, которое означает, что два предмета первогонаименования будут загружены в КА. Эта загрузка cоставляет x2 = x1-2k1 =42*2 = 0. Решение на втором шаге при x2 = 0 приводит к оптимальномурешению k2 = 0, которое, в свою очередь, дает x3 = x2 – 3k3 = 0–3*0 = 0.
Далеешаг 3 при x3 = 0 приводит к k3 = 0.Следовательно, оптимальным решением задачи является k1 = 2, k2 = 0и k3 = 0. Соответствующая прибыль равна 62 000 условных единиц.10_________________________________________________________________________________Деменков Н.П. Синтез оптимальных систем методом динамического программирования.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
