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

ЛЕКЦИЯ-1. ПРИНЦИПЫ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ В СИСТЕМНОМ АНАЛИЗЕ СЛОЖНЫХ ОБЪЕКТОВ МОТИВАЦИЯ ДЛЯ СОЗДАНИЯ АЛГОРИТМОВ, СОКРАЩАЮЩИХ ПЕРЕБОР Справка. Класс P (polynomial time) (класс «быстро решаемых» задач за полиномиальное время): при обработке входных данных из n битов число шагов должно быть ограничено некоторой степенью числа n (полиномом). Класс полно-переборных задач называют NP (Non-deterministic Polynomial-Time Turing machines). Проблема: Сделать задачу с полиномиально проверяемым свойством. Большие задачи 1. Оптимальное решение задачи коммивояжёра. С ростом количества узлов время, затрачиваемое на полный перебор, растёт экспоненциально. Пример: на машине с 4-ядерным процессором 2,67 ГГц 10 узлов обсчитывается в среднем за 5 миллисекунд, 20 узлов – за 15 минут, а на расчёт оптимального пути для 60 узлов уйдёт более 6 триллионов лет… 2. Разложение многозначного целого числа на простые множители (алгоритмы криптографии). 25 3. C100  242519269720337121015504. Отбор 25-ти наиболее информативных признаков приемников сигналов из 100 каждые 10 минут. 4. Задача Гольбаха: любое четное число представить в сумме простых чисел. 5. Задача расписания. 6. Анализ генома. Геном –наследственная информация в четырех буквах А Т Г Ц. По анализу крови восстановить, какой геном крови (7 млрд букв) у каждого данного человека, а потом понять, что записано в нем (наши способности – к бегу, к математике, к музыке). Мы с вами живем 3 млрд секунд примерно. 2 7. .................................................................................................................................................................... ИДЕОЛОГИЯ ДП. ОСНОВНЫЕ ПЛОЖЕНИЯ Задачи выбора наилучшего (оптимального) варианта решения при наличии нескольких возможных вариантов. 25 - полный перебор вариантов; 1080  ?, C100  ? - много или мало? - решение задачи большей размерности при помощи решения подзадач меньшей размерности (метод динамического программирования). Условия для применения ДП 1) в исходной основной задаче можно выделить подзадачи аналогичной структуры меньшего размера; 2) среди выделенных подзадач есть подзадача, имеющая тривиальное решение; 3) вложенность задач: оптимальное решение подзадачи большего размера может быть построено из оптимальных решений подзадач; решения подзадач запоминаются в таблицы, имеющие разумные размеры. Два типа задач, решаемых на основе ДП 1. Подсчет количества вариантов решения. 2. Поиск самого оптимального решения (оптимизация целевой функции). В этом случае выбирают лучшее среди всех решений подзадач. Примеры прикладных задач, решаемых на основе ДП  ОПТИМАЛЬНОЕ РАСПРЕДЕЛЕНИЕ РЕСУРСОВ  ОПТИМАЛЬНАЯ ТРАЕКТОРИЯ (ЗАДАЧА КОММИВОЯЖЕРА)  КОЛИЧЕСТВО ВСЕВОЗМОЖНЫХ РАЗЛИЧНЫЙ КОМБИНАЦИЙ (РЕШЕНИЙ) ИЗ УКАЗАННОГО ПРАВИЛА ИХ ГЕНЕРАЦИИ 3 ОДНОМЕРНЫЕ ЗАДАЧИ ДП 1. Требуется подсчитать количество последовательностей длины N , состоящих из 0 и 1, в которых никакие две единицы не стоят рядом Из частных примеров: к каждой последовательности длиной (N-1) можно приписать 0 в любом случае (два способа) и 1 только в том случае, если она заканчивается на 0 (по условию задачи, один способ). Возникает динамическое правило: каждая последовательность длины (N-1) может быть продолжена либо одним, либо двумя способами. Пусть i - длина последовательности. F(i) – количество последовательностей длины i, удовлетворяющих условиям. Начальные значения (база динамики) динамики: F[1]=2; F[2]=3. Правило динамики F(i+1)=F(i)+F(i-1). Ответ к задаче - число F(N). Алгоритмическая сложность решения O(N). 4 ОДНОМЕРНЫЕ ЗАДАЧИ ДП 2. Требуется подсчитать длину наибольшей возрастающей подпоследовательности. Входные данные. В первой строке входных данных задано число N - длина последовательности (1 ≤ N ≤1000). Во второй строке задается сама последовательность - целые числа X, |X|10000. Выходные данные. 1) длина наибольшей строго возрастающей подпоследовательности; 2) сама наибольшая возрастающая подпоследовательность. 1) Определим i – номера элемента исходной последовательности наибольшую возрастающую подпоследовательность [a0,..,ai], заканчивающуюся элементом ai. 2) Определим массив d, где d[i] = количество элементов в [a0,..,ai] 3) База динамики: d[0]=1. 4) Правило динамики. Пусть {d[k], ki} - известны. Для определения d[i+1]: o выбрать из {d[k], ki} наибольший элемент d[k*(i)], для которого выполнится a[k*(i)] 1. Необходимо найти Fn по номеру n. Рекурсия без сохранения промежуточных результатов Решение задачи «с конца» уменьшение n, пока не дойдем до известных значений int F(int n) { if (n < 2) return 1; else return F(n - 1) + F(n - 2); } При n >= 40 работает долго; одни и те же промежуточные данные вычисляются по несколько раз - число операций нарастает экспоненциально Рекурсия с сохранением промежуточных результатов int F(int n) { if (A[n] != -1) return A[n]; if (n < 2) return 1; else { A[n] = F(n - 1) + F(n - 2); return A[n]; } } Повторное использование сохраненных результатов уменьшает число операций. По ряду Фибоначчи устроена шишка, ракушка, ананас, подсолнух, ураган, паутина, молекула ДНК, яйцо, стрекоза, ящерица… Алгоритм динамического программирования Решение «с начала». Сначала заполняем известные значения, затем все последующие. F[0] = 1; F[1] = 1; for (i = 2; i < n; i++) F[i] = F[i - 1] + F[i - 2]; Решили все подзадачи: Fi для i < n, затем, зная решения подзадач, нашли ответ: Fn = Fn – 1 + Fn – 2, где Fn – 1 , Fn – 2 уже найдены. 7 ПРИМЕР. ПОСЛЕДОВАТЕЛЬНОСТЬ ФИБОНАЧЧИ F1 = 1, F2 = 1, Fn = Fn – 1 + Fn – 2 при n > 1. Необходимо найти Fn по номеру n. Некоторые элементы последовательности вычисляются повторно несколько раз Цена вопроса. ДП предполагает сохранения результатов решения «мелких» подзадач («плата» памятью - мемоизация - ради экономии времени решения) 8 ЯЗЫК ДИНАМИЧЕСКИХ СИСТЕМ Нелинейная динамика (НД) – это наука, изучающая структуру и свойства эволюционных процессов в нелинейных динамических системах. Как научное направление, нелинейная динамика сформировалась сравнительно недавно, за последние примерно 30-35 лет. Динамическая система (ДС) - система любой природы (физическая, химическая, биологическая, социальная, экономическая и т. д.), состояние которой изменяется (дискретно или непрерывно) во времени. НД использует при изучении систем нелинейные математические модели, чаще всего дифференциальные уравнения и дискретные отображения ( (теории графов, теории марковских цепей,...). ,...). Непрерывное описание x j (t )  f j  x1 ,..., xn   u j , j  1, m, x j (t )  f j  x1 ,..., xn  , j  m  1, n. Дискретное описание x j (t  1)  f j  x1 (t ),..., xn (t )   u j (t ), j  1, m, x j (t  1)  f j  x1 (t ),..., xn (t )  , j  m  1, n, Базовая основа нелинейной динамики: 1) теория динамических систем, 2) теория устойчивости и бифуркаций, 3) механизмы формирования режимов детерминированного хаоса, 4) теория фракталов. 9 ЯЗЫК ДИНАМИЧЕСКИХ СИСТЕМ Оператор эволюции динамической системы определяет ее математическую модель; например, оператор задают в виде системы обыкновенных дифференциальных уравнений (ОДУ) или системы с дискретным временем (итерируемым отображением), или системы разностных уравнений. dx1  F1 ( x1 ,..., xN , ), dt dx2  F2 ( x1 ,..., xN , ), dt ... dxN  FN ( x1 ,..., xN , ). dt Величины x1, x2, …, xN переменные системы,  – вектор параметров, F1, F2, …, FN – некоторые функции (линейные или нелинейные). ЯЗЫК ДИНАМИЧЕСКИХ СИСТЕМ. ДИСКРЕТНАЯ МОДЕЛЬ В общем виде систему с дискретным временем можно записать следующим образом (в виде рекуррентного соотношения): xn 1  F( xn , ). x – вектор координат состояния; n – дискретное время; xn x1 x2 x3 F(x) – вектор-функция с компонентами fi, i=1,2,…, N, задает закон преобразования из предыдущей величины xn в последующую xn+1; x0  – вектор управляющих параметров системы. 1 2 3 n Для одномерного случая уравнение примет вид: xn 1  f ( xn ,  ). x0 – начальное состояние системы при n = 0. Последовательность точек xn (x0, x1, x2, …, xn) представляет дискретную фазовую траекторию отображения. Под размерностью дискретной системы N понимают количество независимых переменных состояния (размерность вектора состояния x). Как и для систем с непрерывным временем, оно соответствует числу уравнений. ЯЗЫК ДИНАМИЧЕСКИХ СИСТЕМ Если рассматривать величины x1, x2, …, xN как координаты точки x в Nмерном пространстве, то получается наглядное геометрическое представление состояния ДС в виде этой точки. Данная точка называется изображающей или фазовой точкой, величины x1, x2, …, xN - фазовыми координатами точки или фазовыми переменными системы, а пространство состояний – фазовым пространством (ФП) системы. Изменению состояния системы во времени отвечает движение фазовой точки вдоль некоторой линии, называемой фазовой траекторией (ФТ). Правые части уравнений F1, F2, …, FN определяют скорость движения изображающей точки в N-мерном фазовом пространстве. x1  - фазовая траектория x0 x2 x3 ЯЗЫК ДИНАМИЧЕСКИХ СИСТЕМ УПРАВЛЯЕМАЯ ДИНАМИЧЕСКАЯ СИСТЕМА С ДИСКРЕТНЫМ ВРЕМЕНЕМ. Динамическая система (ДС) - объект, состояния которого есть функции времени. Фазовое пространство - множество всех возможных состояний ДС (фаза -= состояние). ДС – дискретная, если смена состояний происходит в дискретные моменты времени. РАЗВИТИЕ УПРАВЛЯЕМОЙ ДИНАМИЧЕСКОЙ СИСТЕМЫ Фазовая траектория - набор состояний, через которые проходит ДС в развитии: Ek  k  Ek 1 , uk  , k  1, n. Начальное состояние E0 у всех траекторий одно и то же. В результате управлений uk k 1,n некоторая система переводится из начального состояния E0 в конечное состояние En  E * . В реальных системах с каждым управленческим шагом связан некоторый показатель его эффективности (доход на k-м шаге; затраты на управление) f k  f k  Ek 1 , uk  , k  1, n. Аддитивная целевая функция. n S   f k  Ek 1 , uk . k 1 Принцип оптимальности. Какого бы ни было состояния системы перед очередным шагом надо выбрать управление на этом шаге так, чтобы выигрыш на первом шаге + выигрыш на всех предыдущих шагах были 13 максимальными. ОБЩАЯ ЗАДАЧА ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ Постановка задачи ДП. Определить управляющий вектор u   u1 , u2 ,..., un  , обеспечивающий перевод системы из фиксированного начального состояния E0 в * некоторое целевое состояние En  E , при этом функция качества управления должна достигать своего экстремального значения. n S   f k  Ek 1 , uk   extr. k 1 Принцип оптимальности Беллмана. Каково бы ни было состояние системы перед очередным шагом, надо выбрать управление на этом шаге так, чтобы выигрыш на данном шаге и оптимальный выигрыш на всех последующих шагах был максимальным. Функциональные рекуррентные уравнения Беллмана. Исходя из принципа оптимальности Беллмана разумно первым рассмотреть последний n-й шаг, и управление un * должно выбираться из условия S n : f n  En 1 , un   extr  En 1. un * Управление un , на котором достигается S n  extr un называется условно-оптимальным управлением на n-ом шаге, поскольку присутствует зависимость от состояния En 1. * * Обозначим его через un : un  En 1  . Sk*  Ek 1  - максимальный суммарный доход, начиная с k-го шага и до конца т.е. на  k  1, n  . Согласно принципу оптимальности Беллмана для остальных шагов будем использовать рекурсивное уравнение: S k*  Ek 1   max  f k  Ek 1 , uk   S k*1  Ek 1  , k  n  1, n  2,...,1. 14 ПРИНЦИП ОПТИМАЛЬНОСТИ. ОСНОВНЫЕ ПЛОЖЕНИЯ 1. Оптимальное управление строится постепенно, шаг за шагом. 2. На каждом шаге оптимизируется управление только этого шага. 3. Управление на каждом шаге выбирается с учетом дальнейших последствий. Управление на каждом шаге должно быть оптимальным с точки зрения процесса в целом. Принцип оптимальности (Беллман): ЕСЛИ НЕКОТОРАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ РЕШЕНИЙ ОПТИМАЛЬНА, ТО НА ЛЮБОМ ШАГЕ ПОСЛЕДУЮЩИЕ РЕШЕНИЯ ОБРАЗУЮТ ОПТИМАЛЬНУЮ СТРАТЕГИЮ ПО ОТНОШЕНИЮ К РЕЗУЛЬТАТУ ПРЕДЫДУЩИХ РЕШЕНИЙ. Схема решения монгошаговой задачи на основе принципа оптимальности Беллмана: 1) Обратный ход: от последнего шага к первому получают множество возможных оптимальных («условно-оптимальных») управлений. 2) Прямой ход: от известного начального состояния к последнему из полученного множества «условно-оптимальных» управлений составляется искомое оптимальное управление для всего процесса в целом. Получение оптимальной стратегии управления. 1) найти оптимальную стратегию управления на n-м шаге; 2) затем на двух последних шагах; 3) затем на трех последних шагах и т.д., вплоть до первого шага. 15 ЗАДАЧА ОПТИМАЛЬНОГО РАСПРЕДЕЛЕНИЯ РЕСУРСОВ Постановка задачи оптимального распределения заданного объема капиталовложений в несколько предприятий. Примеры содержательной интерпретации задачи:  распределение средств на приобретение оборудования, закупку сырья и найм специалистов;  задачи о распределении товара по торговым предприятиям и складам;  задачи по определению последовательности пропорций между продукцией с/х производства, предназначенной для реализации и воспроизводства и т.д. Исходные данные. Фирма имеет 4 филиала. Следует определить оптимальное распределение капиталовложений (200 млн. руб) между филиалами, максимизирующее общий прирост прибыли фирмы Ожидаемый прирост прибыли филиалов при соответствующих капиталовложениях задан таблицей. Кап. Вложения Прирост прибыли по филиалам 1 2 3 4 50 25 30 36 28 100 60 70 64 56 150 100 90 95 110 200 140 122 130 142 Предположения 1. Ожидаемый прирост прибыли зависит как от финансируемого филиала, так и от объема этого финансирования. 2. Прирост прибыли в отдельно взятом филиале не зависит от вложенных средств в другие филиалы. 3. Общая прибыль фирмы равна сумме всех приростов по филиалам. 16 ЗАДАЧА ОПТИМАЛЬНОГО РАСПРЕДЕЛЕНИЯ РЕСУРСОВ Решение задачи. «Шаги» задачи - последовательное рассмотрение филиалов. Формирование функциональных уравнений Беллмана предполагает: N промежутков с определенным шагом . Здесь: N= 4, =200/4=50 млн. руб. Значения функций, входящих в уравнения Беллмана, будут определяться только в точках, кратных  (0, 50, 100, 150, 200). Обозначения. С =200 – общий объем распределяемых средств; xi - объем средств, выделяемых i-му филиалу; i=1,2,3,4; х= x1+x2+x3+x4 - объем средств, выделяемых всем филиалам (на каждом шаге), 0≤ х ≤C. Fi(xi) – ожидаемый прирост i-той фирмы при выделении ей хi средств. F = F1(x1) + F2(x2) + F3(x3) + F4(x4) → max целевая функция при ограничениях x1+x2+x3+x4=C, xi≥ 0, i=1,2,3,4. Вводится последовательность функций. z1(x) –максимальная прибыль фирмы, если x средств выделить одному 1-му филиалу; z2(x) – максимальная прибыль фирмы, если x средств распределить между 1-м и 2-м филиалами; z3(x) – максимальная прибыль фирмы, если x средств распределить между 3-м и двумя первыми филиалами; z4(x) – максимальная прибыль фирмы, при распределении x средств между всеми 4-мя филиалами. 17 Понятно, что z4(C) =max F=F*(искомое максимальное значение прибыли), zi(0) = 0. ЗАДАЧА ОПТИМАЛЬНОГО РАСПРЕДЕЛЕНИЯ РЕСУРСОВ Принцип ДП. Обратный ход. Функциональные уравнения Беллмана. Рассмотрим финансирование только 1-го филиала, тогда прибыль (1) z1  x   max Fi  x  . i 1,2,3,4 Пусть теперь средства в объеме x распределяются между 1-м и 2-м филиалами: 2-му в объеме x2, тогда х – х2= х1 выделяется 1-му. Общая прибыль двух филиалов (2) z2  x   max F2  x2   z1  x – x2  0 x2 C   Теперь включим в рассмотрение дополнительно 3-й филиал: из общей суммы х выделим 3му филиалу х3, тогда остальная часть х – х3 оптимальным образом распределяется между двумя первыми (3) z3  x   max F3  x3   z2  x – x3  . 0 x3 C   Наконец, по аналогии находим (4) z4  x   max F4  x4   z3  x – x4  . 0 x4 C   Принцип ДП. Прямой ход. 1) Рассчитать значения zi и Fi (i=1,2,3,4) для всех возможных х согласно (1)-(4). 2) В массиве { zi , Fi} найти z4(C) =F* (максимальное значение целевой функции). 3) найти x4: F4(x4*) =F4*.(максимальное значение целевой функции) 4) Зная x4*, находим С–х4* - объем финансирования остальных трех филиалов, а следовательно, и F3* и х3*. 5) Аналогично находим F2* и х2*. 6) Аналогично находим F1* и х1*. 18 7) Находим F1* =F1(x1*). ВЫВОДЫ ПО АЛГОРИТМУ ДП ДП - есть задача, оптимальное решение которой непонятно, а полный прямой перебор – за пределами реального времени. Для такой задачи предусматривают двухпроходную процедуру:: 1) пробуют разбить на вложенные подзадачи с меньшей размерностью (эффект матрешки); 2) каждая подзадача решается отдельно один раз; оптимальные значения решений всех подзадач запоминаются; сначала решают самую простую с минимальной размерностью; 3) для исходной задачи строится возвратное соотношение, связывающее между собой оптимальные значения подзадач, то есть формируют правило использования решения нижнего уровня для первого верхнего (по вложению). N-шаговый процесс Переход между состояниями 19 ЗАДАЧА КАЛЕНДАРНОГО ПЛАНИРОВАНИЯ ТРУДОВЫХ РЕСУРСОВ Предпринимателю необходимо составить план регулирования численности рабочих на последующие пять месяцев – январь, февраль, март, апрель и май. Пусть b– вектор потребностей в рабочей силе: b=(b1; b2; b3; b4; b5) = (5; 7; 8; 4; 6) (в январе потребуется не меньше 5 человек, в феврале не меньше 7... .). Политика управления: принимать новых людей на работу и увольнять (без выходного пособия). Пусть yj – количество рабочих, работающих в j-м месяце, yj ≥ bj. ПЗ. составить оптимальный план численности рабочих на 5 месяцев, при условии, что в конце декабря работало 5 человек. Известны законы: Убытки при наличии лишних рабочих Расходы, связанные с наймом новых рабочих Ограничения на yj, j=1,2,3,4,5. Достаточно рассмотреть значения Рекуррентные соотношения. 20 ЗАДАЧА КАЛЕНДАРНОГО ПЛАНИРОВАНИЯ ТРУДОВЫХ РЕСУРСОВ (b1; b2; b3; b4; b5) = (5; 7; 8; 4; 6) Шаг 5. Май Шаг 4. Апрель. Май Шаг 3. Март. Апрель. Май 21 ЗАДАЧА КАЛЕНДАРНОГО ПЛАНИРОВАНИЯ ТРУДОВЫХ РЕСУРСОВ Шаг 2. Февраль. Март. Апрель. Май Шаг 1. Январь. Февраль. Март. Апрель. Май Иллюстрация исходных данных и ответа в задаче b= (5; 7; 8; 4; 6) ОТВЕТ 22 ЛИТЕРАТУРА 1. Беллман Р. Динамическое программирование. – М.: Иностранная литература, 1960. 2. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. – М.: Наука, 1965. 3. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. – М.: Высшая школа, 1980. 4. Калихман И.Л., Войтенко М.А. Динамическое программирование в примерах и задачах. – М.: Высшая школа, 1979. 5. Деньдобренко Б.Н., Малика А.С. Автоматизация конструирования РЭА – М.: Высшая школа, 1980. 6. Ройтенберг Я.Н. Автоматическое управление. – М.: Наука, 1978. 7. Вентцель Е.С. Теория вероятностей. – М.: Наука, 1964. 8. Исследование операций в экономике / Под ред. профессора Н.Ш. Кремера. – М.: Банки и биржи, ЮНИТИ, 1997. 9. Фомин Г.П. Математические методы и модели в коммерческой деятельности. – М.: Финансы и статистика, 2005. 10. Лекции И.А. Шуйковой. 11. https://mipt-cs.github.io/python3-2017-2018/labs/lab11.html 12. https://server.179.ru/tasks/python/2022a/pgm14.6__Dynamic_programming.html#prob_R 13. Беров В., Лапунов А., Матюхин В., Пономарев А. Особенности национальных задач по информатике. Изд.Триада, 2000. 23