|
Выбираем первое подмножество. Соответствующая очередность обработки деталей (2,3,1) с продолжительностью обработки Т = 20. Это решение оптимально, поскол ьку оценка остальны х подмножеств больше 20 (Рис. 1.6). Н а Р исунке число в скобках у д у г (например ( 1)) показывает, какая деталь делается, а число с чертой показывает, какая деталь не делается (последней, предпоследней и т.д.). 57 Рис. 1.6. Оптимальное решение М е т о д д и н а м и ч е с к о г о п р о г р а м м и р о в а н и я . В основе метода л еж ит сведение задачи оптимизации к задаче определения экстремальной траектории (минимальной или максимальной длины ) в некоторой специальным образом построенном семействе возм ож ны х траекторий. П ринцип оптимальности Бсллмана гласит: лю бой участок оптимальной траектории оптимален [17, 2 2 ,2 6 ]. В случае дискретны х задач метод динамического программирования сводится к определению п ути максимальной или м инимальной длины в специальным образом построенной сети. Дадим иллю страцию метода на примере классической задачи о ранце. И мею тся п предметов. К аж д ы й предмет имеет ценность ас и вес Cj. Требуется выбрать подмножество Q предметов так, чтобы их суммарная ценность A(Q) = Z a , isQ была максимальной п р и ограничении на сум м арны й вес Z c , < R isq |
эта оценка —отдельный вопрос). Дадим иллюстрацию метода на примере задачи обработки деталей (Рис. 1.3). Возьмем деталь 1 с минимальным Ь, и разобьем множество всех решений на два подмножества. В первом подмножестве деталь 1 делается последней, а во втором не делается последней. Очевидно, что оценка снизу продолжительности обработки для первого подмножества равна П rj = ^ a i + minbi =13+7=20 i=l a для второго II Лг “ + minbi =13+9=22 i=i Выбираем подмножество с минимальной оценкой, то есть деталь 1 обрабатывается последней. Это подмножество разбивается на два. В первом деталь 3 (имеющая минимальную величину bj из оставшихся деталей) обрабатывается предпоследней, а во втором —нет (то есть обрабатывается первой). Оценка первого подмножества Tl = (Q ii) = max(19, 20) = 20 а оценка второго Ti = (Q,2) = max (22, 20) = 22 Выбираем первое подмножество. Соответствующая очередность обработки деталей (2,3,1) с продолжительностью обработки Т = 20. Это решение оптимально, поскольку оценка остальных подмножеств больше 20 (Рис. 1.6). На Рисунке число в скобках у дуг (например (1)) показывает, какая деталь делается, а число с чертой показывает, какая деталь не делается (последней, предпоследней и т.д.). 49 Метод динамического программирования. В основе метода лежит сведение задачи оптимизации к задаче определения экстремальной траектории (минимальной или максимальной длины) в некоторой специальным образом построенном семействе возможных траекторий. Принцип оптимальности Беллмана гласит: любой участок оптимальной траектории оптимален [17, 22, 26]. В случае дискретных задач метод динамического программирования сводится к определению пути максимальной или минимальной длины в специальным образом построенной сети. Дадим иллюстрацию метода на примере классической задачи о ранце. Имеются п предметов. Каждый предмет имеет ценность сц и вес Cj. Требуется выбрать подмножество Q предметов так, чтобы их суммарная ценность A(Q ) = 2 а , i€Q была максимальной при ограничении на суммарный вес 2 c iiR leq Способ построения сети рассмотрим на примере. Имеются четьфе предмета, данные о ценностях и весах которых приведены в таблице 1. Таблица 1.1. i 1 2 3 4 ai 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), соответствую50 |