|
Соответствующая очередность обработки деталей (2,3,1) с продолжительностью обработки Т = 20. Это решение оптимально, поскольку оценка остальных подмножеств больше 20 (рис. 1.4.6). На Рисунке число в скобках у дуг (например (1)) показывает, какая деталь делается, а число с чертой показывает, какая деталь не делается (последней, предпоследней и т.д.). 39 Рис. 1.4.6 В основе метода лежит сведение задачи оптимизации к задаче определения экстремальной траектории (минимальной или максимальной длины) в некоторой специальным образом построенном семействе возможных траекторий. Принцип оптимальности Веллмана гласит: любой участок оптимальной траектории оптимален [17, 25, 26]. В случае дискретных задач метод динамического программирования сводится к определению пути максимальной или минимальной длины в специальным образом построенной сети. Дадим иллюстрацию метода на примере классической задачи о ранце. Имеются п предметов. Каждый предмет имеет ценность щи вес с\. Требуется выбрать подмножество 0 предметов так, чтобы их суммарная ценность А((£) = была максимальной при огранило чении на суммарный вес ^ И ¡еч Способ построения сети рассмотрим на примере. Имеются четыре предмета, данные о ценностях и весах которых приведены втабл. 1.4.1. |
Заметим, что функция приоритета, основанная на степени критичности работ фронта в эвристических алгоритмах распределения ресурсов, является оценкой снизу продолжительности проекта (насколько хороша эта оценка —отдельный вопрос). Дадим иллюстрацию метода на примере задачи обработки деталей (Рис. 1.3). Возьмем деталь 1 с минимальным bj и разобьем множество всех ^ решений на два подмножества. В первом подмножестве деталь 1 делается последней, а во втором не делается последней. Очевидно, что оценка снизу продолжительности обработки для первого подмножества равна П Til ~ ^ c ti + minbi =13+7=20 i=i 1 а для второго П Ц2 ~ S a ' + minbi =13+9=22 w w Выбираем подмножество с минимальной оценкой, то есть деталь 1 обрабатывается последней. Это подмножество разбивается на два. В первом деталь 3 (имеющая минимальную величину bi из оставшихся деталей) обрабатывается предпоследней, а во втором нет (то есть обрабатывается первой). Оценка пер•' вого подмножества V = (Q n) = max (19, 20) = 20 а оценка второго V = (Q12) = max (22,20) = 22 Выбираем первое подмножество. Соответствующая очередность обработки деталей (2,3,1) с продолжительностью обработки Т = 20. Это решение оптимально, поскольку оценка остальных подмножеств больше 20 (Рис. 1.6). На Рисунке число в скобках у дуг (например (1)) показывает, какая деталь делается, а число с чертой показывает, какая деталь не делается (последней, предпоследней и т.д.). Рис. 1.6. 83 Метод динамического программирования В основе метода лежит сведение задачи оптимизации к задаче определения экстремальной траектории (минимальной или максимальной длины) в некоторой специальным образом построенном семействе возможных траекторий. Принцип оптимальности Беллмана гласит: любой участок оптимальной траектории оптимален [17,22, 26]. В случае дискретных задач метод динамического программирования сводится к определению пути максимальной или минимальной длины в специальным образом построенной сети. Дадим иллюстрацию метода на примере классической задачи о ранце. Имеются п предметов. Каждый предмет имеет ценность ci{ и вес с,. Требуется выбрать подмножество Q предметов так, чтобы их суммарная ценность A(Q) = £сц isQ была максимальной при ограничении на суммарный вес Z c i S R ieq Способ построения сети рассмотрим на примере. Имеются четыре предмета, данные о ценностях и весах которых приведены в таблице I. Таблица 1. i 1 2 3 4 а* 3 2 4 5 Ci 2 1 3 4 Пусть R = 6. Строим на плоскости систему координат, одна ось которой соответствует предметам, а вторая их весу. По оси предметов отмечаем номера предметов 1,2,3,4 (Рис. 1.7). Из начала координат проводим две дуги —одна горизонтальная в точку (1,0), а другая наклонная в точку (1,2), где 2 вес первого предмета. Первая дуга соответствует случаю, когда первый предмет не берется, а вторая когда он берется. Из каждой полученной точки (1, 00) и (1,2) проводим также по две дуги для второго предмета. Получаем четыре точки (2,0), (2,1), (2,2) и (2,3), соответствующие четырем возможным вариантам для двух предметов. Продолжая таким образом, получим сеть, приведенную на Рис. 1.7. Очевидно, что любой путь в сети, из начальной вершины 0 в одну из конечных вершин соответствует некоторому набору предметов. И наоборот, любому набору предметов, суммарным весом не более 6 однозначно соответствует 84 |