Оптимизация решений с использованием методов динамического программирования

программирование отсечение решение Основная идея динамического программирования заключается в замене одновременного выбора большого количества параметров поочередным их выбором. Многомерная задача оптимизации сводится к многошаговой задаче меньшей размерности. При этом одним из достоинств метода является общность подхода к решению самых различных задач оптимизации решений.

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

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

Целевая функция L в зависимости от содержания задачи может максимизироваться или минимизироваться, однако сущность метода при этом не меняется. Математически задача формулируется (при максимизации L) следующим образом.

Определить.

(14).

при ограничениях.

(15).

В этой задаче максимум функции L зависит от величины ресурса D и числа параметров управления N. Для того, чтобы эту задачу сделать определенной, вводят последовательность функций fn (Dn) для n = 1, 2,, N. При этом должно выполняться условие.

; (16).

Таким образом, мы перешли от решения задачи (14), (15) к решению более общей задачи (16), (17). Действительно, определив функцию fN (DN) при выполнении условия (17), мы находим целое семейство решений для различных значений fN (DN). По условиям же задачи (14), (15) нас интересует только одно решение.

Для удобства решения функционального уравнения (16) табличным способом перепишем его в следующем виде:

;

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

Рассмотрим пошаговый процесс динамического программирования на примере решения следующей задачи.

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

Данная задача соответствует математической постановке (14), (5) при D = 20, N = 4. Воспользуемся функциональным уравнением, для решения которого необходим следующий пошаговый процесс.

Шаг 1.;

.

Если D1 = 0, то d1x1D1 В том случае, когда x1 = 0 (так как d1 = 5 и 5×1при x1 = 0).

Поэтому.

Если D1 = 1, тоd1x1D1 в том случае, когда x1 = 0.

Поэтому.

Аналогично приD1 =2, 3, 4.

Если D1 = 5, тоd1x1D1 в том случае, когда x1 = 0 и x1 = 1.

Поэтому.

Результаты вычислений приведены в табл. 6. Замечаем, что значения f1(D1) при D1 = 1, 2, 3, 4, 6, 7,, 19, 20 не входят в оптимальную последовательность, так как аналогичные значения f1(D1) получаются при меньших затратах D1 = 0 и D1 = 5 соответственно. Поэтому для дальнейшего рассмотрения будет использоваться последовательность.

.

Таблица 6.

Шаг 2.;

.

Для решения данного функционального уравнения воспользуемся табличным способом. Определяем члены оптимальной последовательности клетки, соединенные стрелками в табл. 7.

Шаг 3.;

.

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

Следовательно, оптимальная последовательность такова, как показано в табл. 8.

Шаг 4.,.

.

В табл. 9 стрелками показаны члены оптимальной последовательности ={0, 0; 40, 5; 45, 9; 54, 12; 72, 13; 85, 14; 86, 20}, последний из которых определяет оптимальное значение целевой функции.

Четвертый шаг является заключительным шагом процедуры прямого хода, в результате выполнения которой найдено оптимальное значение целевой функции L = 86, т. е. величина максимального ущерба (в усл. ед.), который можно нанести противнику при оговоренных в задачах условиях. Однако задача еще не решена, так как план целераспределения не найден. Для того, чтобы определить, какие группы целей необходимо поражать, воспользуемся процедурой обратного хода, которая заключается в следующем.

Таблица 9.

Из табл. 9 по величине f4 (D4)=86 находим x4 = 1 (см. левый столбец), а по значению f3 (D3= 13)=72 (см. верхнюю строку) входим в табл. 8 и определяем x3 =1 (левый столбец). По величине f2 (D2= 5)=40 входим в табл. 7 и находим: по строке x2 = 0, по столбцу x1 = 1.

Таким образом, для нанесения двадцатью средствами максимального ущерба противнику необходимо планировать для поражения 1, 3 и 4-ю группы целей.

Для принятия более обоснованного решения целесообразно проанализировать оптимальную последовательность f4 (D4).

Показанная на рис. 3 зависимость оптимального значения целевой функции f4 (D4) от величины константы ограничения позволяет оценить чувствительность решения к изменению ограниченияD. Например, можно использовать не 20 средств поражения, а лишь 14, оставив 6 в резерве. При этом величина ущерба, наносимого противнику, снизится всего на единицу.

Рассмотренная задача весьма проста и использовалась лишь для пояснения метода.

Метод динамического программирования дает значительный эффект по сравнению с методом простого перебора вариантов при достаточно большой размерности задачи (например, при значительных величинах N). Однако следует учитывать, что по мере увеличения размерности задач трудоемкость их решения возрастает. При этом растет количество таблиц и их размеры, а при использовании ЭВМ возникают трудности, связанные с ограниченным объемом оперативной памяти.

Рис. 3 — Зависимость оптимального значения целевой функции от величины ограничения

От этих недостатков в значительной мере свободен модифицированный метод динамического программирования.

Сущность метода состоит в исключении полного перебора вариантов на каждом шаге оптимизации. Фактически этот метод предусматривает применение принципа неполного (частичного) инвариантного погружения.

Алгоритмы решения задач модифицированным методом динамического программирования во многом зависят от характера решаемых задач. Рассмотрим классификацию этих задач (рис. 4).

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

Рис. 4 — Классификация решаемых задач

Для задач первого типа количество вариантов для каждого элемента в исходных данных может быть различным. Задачи второго типа характеризуются для каждого элемента двухвариантными исходными данными. Если в исходных данных строго соблюдается соответствие увеличения затрат увеличению полезности, то такие исходные данные будем называть строго упорядочиваемыми. В задачах первого типа исходные данные для каждого варианта всегда строго упорядочиваемые.

Сущность модифицированного метода динамического программирования рассмотрим вначале для задач первого типа. Математически задача формулируется (при максимизацииL) следующим образом.

Определить.

(18).

при ограничениях.

(19).

где xjномер варианта реализации j-го элемента.

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

(20).

В зависимости от содержания задачи значения могут быть больше нуля или равны нулю.

Функциональные уравнения при решении задач первого типа аналогичны уравнениям (16), (17):

(21).

(22).

Для ускорения выявления вариантов, не удовлетворяющих условию DnD, целесообразно нумерацию элементов исходного множества осуществлять в соответствии с условиями.

(23).

2 kN.

Если в соответствии с этими условиями можно пронумеровать не все элементы, а лишь k.

Поясним теперь сущность алгоритма решения задачи на примере оптимизации плана огневого поражения четырех групп целей (N=4) двадцатью средствами поражения (D=20).

Известны варианты xjвозможного использования этих средств по каждой группе целей, характеризующиеся соответствующим ущербами cj, наносимыми противнику средствами поражения dj (табл. 10). Нумерация групп целей (элементов) выполнена согласно условиям (23), а нумерация вариантов для каждой группы целей в соответствии с (20). Необходимо составить план поражения, при котором противнику будет нанесен максимальный ущерб.

Основные положения алгоритма заключаются в следующем.

Таблица 10.

1. Значения c1, d1заносятся в верхнюю строку первой таблицы, а c2, d2 в левый столбец этой же таблицы. Заполнение строки и столбца осуществляется последовательно, по мере вычислений в клетках таблицы.

2. После вычисления в первой таблице первого члена последовательности его значения заносятся в верхнюю строку второй таблицы; В левый столбец этой таблицы заносятся (последовательно) значения c3, d3. По этим данным вычисляется первый член последовательности .

3. Процессы повторяются до тех пор, пока в последней таблице (а число таблиц равно N1) не будет найдено максимальное значение.

.

4. Таким образом, на каждом шаге выполняется ограниченный перебор вариантов. Это оказывается возможным ввиду записи исходных данных в соответствии с условиями (20). Благодаря выполнению этих условий каждый очередной член последовательности находится среди элементов диагонали таблицы при движении слева направо.

В соответствии с изложенным и исходными данными табл. 10 заготавливаем формы трех таблиц (табл. 11, 12, 13). В верхнюю строку табл. 11 заносим значения с1 = 45, d1 = 9 для варианта x1 = 1, а в левый столбец с2 = 40, d2 = 5 для x2 = 1. Суммируя с1 и с2, d1и d2, получаем первый член последовательности. Значения f2 = 85, D2 = 14 заносим в верхнюю строку табл. 12, а в ее левый столбец с3 =32, d3 = 8 для x3 = 1. Суммируя f2 и с3, D2и d3, находим f3 = 117 и D3 = 22. Так как D3 = 22 >D = 20, то найденные значения f3 и D3 в дальнейшем не используем (клетку в табл. 12 зачеркиваем) и определяем следующий член последовательности. Он должен находиться в одной из клеток табл. 12 ниже или правее первой клетки (т.е. на диагонали). Для определения значения f3, D3 В этих клетках заносим в левый столбец табл. 12 значения с3 =25, d3 = 6 для x3 = 2.

По этим значениям вычисляем для нижней клетки f3 = 110 и D3 = 20. Для определения f3, D3 в правой клетке необходимо найти очередной член последовательности f2 (D2) в табл. 11. В связи с этим заносим в верхнюю строку табл. 11с1 =30, d1 = 6 для x1 = 2 и в левый столбец с2 =20, d2 = 3 для x2 = 2. Тогда в клетках диагонали табл. 11 получим очередные значения f2, D2: f2 = 70, D2 = 11; f2 = 65, D2 = 12. Так как в правой клетке значения f2, D2 лучше, чем в нижней (в нижней затраты больше, а эффект меньше), то очередной член оптимальной последовательности f2 (D2) составляют значения f2 = 70, D2 = 11. Заносим эти значения в верхнюю строку табл. 12 и вычисляем f3 = 102, D3 = 19. В качестве первого члена оптимальной последовательности f3 (D3) берем значения f3, D3, записанные в нижней клетке табл. 12 (в соответствии с убыванием значений f и D), и заносим их в верхнюю строку табл. 13. В левый столбец этой таблицы заносим значения с4 =14, d4 = 7 для x4 = 1. Суммируя эти значения с f3 = 110, D3 = 20, получаем f4 = 124, D4 = 27 >D = 20. Поэтому полученные значения из дальнейшего рассмотрения исключаем и для нахождения первого члена оптимальной последовательности f4 (D4), удовлетворяющего условию D4D, заносим в левый столбец очередные значения c и d: с4 = 0, d4 = 0 для x4 =2. Получаем в нижней клетке табл. 13f4 = 110, D4 = 20. Но для нахождения решения надо найти значения f4, D4 в правой клетке (относительно первой клетки). Для этого из табл. 12 берем очередной член последовательности f3 (D3): f3 =102,D3 = 19. Заносим его в верхнюю строку табл. 13. Тогда получаем f4 = 116, D4 = 26 >D = 20 и исключаем их из рассмотрения. Следовательно, необходимо вычислить значения f4, D4 для клетки, находящейся правее исключенной. Для этого следует определить очередной член оптимальной последовательности f3 (D3), находящийся на следующей (второй) диагонали табл. 12. В свою очередь, для этого надо в левый столбец этой таблицы занести с3=0, d3=0 для x3=3 и определить очередной член оптимальной последовательности f2 (D2), находящийся на второй диагонали табл. 12. Поэтому в левый столбец этой таблицы надо занести очередные значения с2 = 10, d2 = 10 для x2 =3 и в верхнюю строку с1 = 15, d1 = 3 для x1 =3. Последовательно выполняем эти операции и вычисляя соответствующие значения f и D, определяем f2 = 55, D2 = 8 и f3 = 95, D3 = 17. Заносим последние значения в верхнюю строку табл. 13 и получаем f4 =109,D4 = 24 >D = 20. Этот член последовательно исключается из последовательности, но в дальнейших вычислениях необходимости нет, так как полученные значения f4 и D4 хуже найденных ранее f4 =110,D4 = 20 = D. Поэтому величина максимального ущерба, наносимого противнику двадцатью средствами поражения, составляет L = f4 = 110 (усл. ед.). Для определения плана поражения последовательно анализируем табл. 13, 12, 11.

Из табл. 13 по значениям f4 =110,D4 = 20 находим соответствующие значения с4 = 0, d4 = 0, т. е. x4 =2, и f3 =110,D3 = 20. По f3 =110,D3 = 20 в табл. 12 определяем с3 = 25, d3 = 6, т. е. x3 =2, и f3 = 85, D2 = 14. По f2 = 85, D2 = 14 в табл. 11 находим с2 = 40, d2 = 5, т. е. x2 =1, и с1 = 45, d1 = 9, т. е. x1 =1. Таким образом, обращаясь теперь к исходным данным в табл. 10, формулируем полученное решение: для нанесения максимального ущерба противнику следует для поражения первой группы целей назначить 9 средств поражения, для поражения второй группы целей 5 средств поражения, для поражения третьей группы целей 6 средств поражения, для поражения четвертой группы целей средства поражения не назначать.

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

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

Итак, задача (14), (15) характеризуется тем, что в общем случае большим значениям djне обязательно соответствует и большие значения сj. Упорядочение исходных данных для решения этой задачи должно начинаться с расположения элементов в ряд, удовлетворяющий условию.

(24).

Это условие означает, что из исходного множества элементов формируется ряд, в котором номера соответствуют принципу невозрастания значений полезности сj и затрат dj. Такая ранжировка элементов наилучшим образом соответствует идее модифицированного метода динамического программирования.

В зависимости от характера исходных данных при решении задач второго типа, после получения ряда согласно условию (24), могут быть следующие случаи упорядочения исходного множества элементов.

1. Если k =N, то оптимальное множество элементов выбирают из всего упорядоченного множества (случай А).

2. Если k.

Затем сравнивают hj иhl; при этом возможны следующие случаи:

а) для всех; тогда сформированное упорядоченное подмножество считается окончательным, элементы подмножества остаются пронумерованными в соответствии с убыванием hl;

б)для некоторых элементов первоначально сформированного упорядоченного подмножества выполняется неравенство; тогда эти элементы переводят из подмножества в подмножество, и полученное новое упорядоченное подмножество является окончательным, а элементы подмножества нумеруют в соответствии с убыванием значений hl.

Оптимальное подмножество элементов выбирают только из подмножества, если и в процессе оптимизации будет получено значение (случай Б). Подмножество является достаточным для набора из него подмножества, поскольку любой из элементов подмножества хуже любого из элементов подмножества по показателю h.

Если (случай В), то оптимальное подмножество элементов выбирают из и из, .

В частном случае (случай Б0) может быть, и тогда оптимальным является упорядоченное подмножество, т. е. решение задачи фактически заканчивается формированием этого подмножества.

Поясним изложенное на ряде примеров.

Пусть требуется составить оптимальный план огневого поражения восьми целей, если известны (табл. 14) боевые потенциалы cj (в усл. ед.) каждой из них и необходимые количества боеприпасов dj (в усл. ед) для поражения каждой из них с заданной степенью. Известно имеющееся количество боеприпасов D = 15 (усл. ед.).

Таблица 14.

Данная задача относится к задачам второго типа, и в соответствии с условием (24) выполним упорядочение исходных данных (табл. 15).

Таблица 15.

Здесь k=N=8, что соответствует случаю А; следовательно, оптимальный выбор элементов (целей) необходимо осуществлять из всего упорядоченного множества. Для этого используем табличный способ, аналогично уже рассмотренному примеру решения задачи первого типа (табл. 16 22).

Из табл. 22 следует, что максимальный ущерб, наносимый противнику, составит f8 =L= 45 (усл. ед.), а также необходимость включения в план поражения восьмой цели (т.е. x8 = 1). По значениям f7 = 44 и D7 = 14 (из табл. 22) после вхождения в табл. 21 находим x7 = 1 и f6 = 42, D6 = 13.

Поступая аналогичным образом, с помощью табл. 2016 определяем: x7 =1, x6 = 1, x5 = 1, x4 = 1, x3 = 1, x2 = 0, x1 = 1. Таким образом, в план поражения следует не включать лишь цель с номером 2.

Упорядочение исходных данных в случаях Б и В рассмотрим на аналогичном примере, характеризуемом исходными данными в табл. 23 для N = 10 при двух вариантах ограничений: а) D = 12, б) D = 20.

Таблица 23.

В соответствии с (24) составляем табл.24, где получилось k = 6, т. е. k.

Таблица 24.

Таблица 25.

j.
cj.
dj.
hj.	2,25.	2,67.		2,5.			1,4.	1,14.		0,25.

Сравним значения hjи hl:

поэтому x6 переводим в подмножество и изменяем нумерацию элементов (табл. 26).

Таблица 26.

Таким образом, окончательно имеем: Теперь определяем подмножество (или подмножества), из которого следует выбрать оптимальное подмножество элементов. Для этого вычисляем.

Отсюда следует, что.

а) при D = 12получаем и, следовательно, оптимальный выбор осуществляем лишь из подмножества (случай Б);

б) при D = 20 получаем и следовательно, оптимальный выбор осуществляем из подмножества и из подмножества (случай В).

Дальнейшее решение задач выполняется так, как уже было показано.