Сущность методов отсечения. Оптимизация решений с использованием метода ветвей и границ. Правила построения дерева вариантов. Способ оценки верхней границы решения. Особенности оптимизации решений с использованием методов динамического программирования.
Аннотация к работе
Таким образом, целочисленный, дискретный характер решения определяется физическим смыслом этих задач. В соответствии с таким характером решения рассматриваемые в задачах зависимости являются дискретными и нелинейными, задачи имеют большую размерность, во многих случаях аналитические зависимости отсутствуют. Таким образом, для решения целочисленных задач необходимо использовать методы оптимизации, учитывающие особенности этих задач и позволяющие исключить перебор всех возможных вариантов. Рассмотрим алгоритм решения задачи (2) - (4) методом ветвей и границ с простым и эффектным способом оценки верхней границы целевой функции. Согласно (2) - (4) математическая постановка данной задачи имеет вид при ограничениях где n=4, b1=20, причем переменная xj = 1, если j-я изделие производится, и xj=0 в противном случае.
Введение
Большой класс задач оптимизации сводится к задачам целочисленного программирования. Общей особенностью всех этих задач является обязательность целочисленного решения. Например, физически невозможно подготовить к эксплуатации 0,3 изделия, заменить при ремонте 1,5 агрегата. Таким образом, целочисленный, дискретный характер решения определяется физическим смыслом этих задач. В соответствии с таким характером решения рассматриваемые в задачах зависимости являются дискретными и нелинейными, задачи имеют большую размерность, во многих случаях аналитические зависимости отсутствуют.
Задачи целочисленного программирования можно представлять в виде задач линейного программирования. Например, в таком виде: (0) при ограничении
. (1)
Особенность задачи (0), (1) заключается в том, что xj принимает только два значения - 0 или 1. К задаче такого типа могут быть сведены различные задачи оптимального распределения дискретных ресурсов. Очевидно, что с помощью методов линейного программирования можно решить задачу (0), (1), округлив полученные нецелочисленные значения xj до ближайших целых чисел. Однако такой подход может привести к решению, значительно отличающемуся от оптимального.
Другая особенность задач целочисленного программирования - отсутствие способа проверки допустимого плана на оптимальность. Ввиду большой размерности многих задач этого класса найти оптимальное решение путем простого перебора вариантов не представляется возможным.
Таким образом, для решения целочисленных задач необходимо использовать методы оптимизации, учитывающие особенности этих задач и позволяющие исключить перебор всех возможных вариантов.
Для решения задач целочисленного программирования разработаны две группы методов: методы отсечения и комбинированные методы.
Сущность методов отсечения состоит в следующем.
1. Задачу целочисленного программирования решают как задачу линейного программирования без учета условия целочисленности решения. Если полученное решение является целочисленным, то вычислительный процесс прекращают. В противном случае переходят к п.2.
2. Вводят дополнительное ограничение, исключающее (отсекающее) нецелочисленное решение, и возвращаются к п.1.
Опыт использования этого метода показал, что эффективность алгоритмов отсечения невысока. Более эффективными в общем случае являются комбинаторные методы, основанные на упорядоченном переборе наиболее перспективных вариантов.
Комбинаторные методы решения задач целочисленного программирования можно разделить на две группы: методы ветвей и границ и методы динамического программирования.
1. Оптимизация решений с использованием метода ветвей и границ
Метод ветвей и границ использует последовательно-параллельную схему построения дерева возможных вариантов. Первоначально ищут приближенное решение, и для каждого варианта определяют верхнюю границу целевой функции. Ветви дерева возможных вариантов, для которых верхняя граница ниже приближенного решения, из дальнейшего рассмотрения исключают.
Поясним сущность этого метода и алгоритм на примере типовой задачи целочисленного программирования.
Требуется максимизировать выражение
(2) при ограничениях
; (3)
. (4)
Рассмотрим алгоритм решения задачи (2) - (4) методом ветвей и границ с простым и эффектным способом оценки верхней границы целевой функции.
Обозначим: U- множество переменных xj; S - множество фиксированных переменных, вошедших в допустимое решение; Es- множество зависимых переменных, которые не могут быть включены в множество S, так как для них выполняется неравенство
;
Gs-множество свободных переменных, из которых производится выбор для включения в S очередной переменной.
Рассмотрим первоначально одномерную задачу, т.е. m= 1 и задача (2) - (4) имеет только одно ограничение (3).
Обозначим и допустим, что и выполняются условия
; (5)
; (6)
. (7)
Условия (6), (7) означают, что в множество Sбез нарушения неравенства (3) можно дополнительно ввести элементы xk 1, xk 2, ?xl-1. При введении в множество S элементов xk 1, xk 2, ?xlнеравенство (2) не выполняется.
Для определения верхней границы решения может быть использовано выражение
, (8), где ; (9)
(10)
Из условий (5) - (7) следует, что при ограничении
, .
Выбор очередной переменной для включения в множество S производится с помощью условия
. (11)
Для выбранной переменной xr определяются величины , т.е. в S включается или .
Если в процессе решения окажется, что в множестве нет элементов, которые могут быть введены в множество Sбез нарушения ограничения (3), то полученное решение принимается в качестве первого приближенного значения L0.
Все ветви дерева возможных вариантов, для которых выполняются условия , из дальнейшего рассмотрения исключаются. Из оставшихся ветвей выбирается ветвь с максимальным значением Hs, и процесс поиска оптимального варианта продолжается. Если в процесс решения будет найдено
, то полученное решение принимается в качестве нового приближенного результата. Вычислительная процедура заканчивается, если для всех оставшихся ветвей выполняется условие
.
Рассмотрим алгоритм решения задачи (2)-(4).
Одномерные задачи. Пусть для производства каждого из четырех типов изделий, имеющих потенциалы , необходимо соответственно 4 типа бригад. Требуется назначить бригадытаким образом, чтобы получить максимальную выгоду двадцатью выделенными бригадами.
Согласно (2) - (4) математическая постановка данной задачи имеет вид при ограничениях где n=4, b1=20, причем переменная xj = 1, если j-я изделие производится, и xj=0 в противном случае.
С учетом исходных данных необходимо определить при ограничениях
7x1 9x2 8x3 5x4?20;
x1, x2,x3,x4=0 или 1.
Введем обозначения: - множество всех переменных ;
S -множество переменных , включенных в ветвь дерева вариантов, соединяющую данную вершину с начальной (корневой) вершиной, причем , если =0 и , если =1;
- множество запрещенных переменных, которые нельзя ввести в множество S;
- множество свободных переменных, из которых производится выбор очередной переменной для включения в множество S (т.е. для продолжения построения соответствующей ветви дерева вариантов);
- накопленное значение ограничения и целевой функции соответственно;
- оценка верхней границы решения в вершине , принадлежащей ветви S;
Со - рекорд (значение целевой функции, соответствующее лучшему из полученных допустимых решений).
Определяем: 1. Правила построения дерева вариантов. Выбираем одностороннюю схему построения дерева вариантов, в которой используются правило «последний вошел - первый выходит», и дихотомический способ разветвления выбранной переменной. Выбор очередной переменной для включения в множество S будем производить с помощью условия
, где .
На основании исходных данных рассчитаем значения h (табл. 1)
Таблица 1 х1 х2 х3 х4
14453240
7985
2548
Упорядочим исходные данные задачи в порядке убывания величины (табл. 2).
Таблица 2 х1 х2 х3 х4
40453214
5987
8542
2. Способ оценки верхней границы решения. Верхнюю границу решения будем оценивать с помощью выражения
.
Величина находится в результате решения задачи при ограничениях
.
3. Правило окончания вычислительного процесса. Когда в процессе вычислений окажется, что =?, то полученное значение целевой функции принимаем в качестве первою приближенного решения задачи. Эту величину (рекорд) обозначаем через Со.
Все концевые вершины дерева вариантов, для которых выполняется условие , исключаются из дальнейшею рассмотрения. Среди оставшихся концевых вершин выбирается вершина с максимальным значением , которая и подвергается разветвлению. Если в процессе решения будет найдено новое значение Cs>Со, то величина Cs принимается в качестве новою значения Со (происходит уточнение рекорда).
Решение задачи прекращается, когда для всех концевых вершин дерева вариантов.
С учетом сделанных пояснений на первом шаге вычислительного процесса
S= ?, Es = ?, , =0, =0.
Так как =0, решаем задачу по определению до выполнения ограничения в виде равенства: D - = 20 - 0 = 20; D1 = d4*1 = 5 < 20; D2 = D1 d2*1 = 5 9 = 14 < 20;
D3 = D2 d3*1 = 14 8 = 22 > 20;
Dd3 = d3x3 = 8*6/8 = 6; D3 = D2 Dd3 = 14 6 = 20;
= c4 c2 h3Dd3 = 40 45 4*6 = 109.
Значение верхней границы решения для начальной вершины
HS=?= = 0 109 = 109.
Из условия (11) выбираем и рассчитываем
= 109; = 0 (45 32) 2*3 = 83;
(так как для имеем l = 4, Db1 = 20 - (9 8) = 3, h14 = 2).
На втором шаге, следовательно x4IS, Es = ?, XJIGS(j = 1,2,3), Hs = Hs(x4) = 109.
Выбираем и рассчитываем
= 109; = 40 32 14 = 86.
Поэтому на третьем шаге имеем {x4,x2}IS, {x3,, x1}IES,Gs= ?.
Следовательно, значение = 40 45 = 85 может быть принято в качестве первого приближенного решения Lo.
Осталась неисследованной ветвь для , где = 86 >Lo =85. Поэтому на четвертом шаге имеем: ,Es = ?, XJIGS(j = 3,1), = 86Выбираем и рассчитываем =40 32 14=86 и = 40 14= 54.
На пятом шаге имеем ,Es = ?, x1IGS..Выбираем и рассчитываем = 40 32 14 = 86; =40 32= 72. Полученное значение рекорда, равное 86 единицам, является наибольшим, а Gs = ?. Поэтому ветвь соответствует оптимальному решению задачи.
Таким образом, необходимо из четырех изделий производить только 4, 3, 1-еизделие. При этом будет максимальная выгода от работы двадцати бригад.
Процесс решения задачи представим в виде таблицы (табл. 3), производя одновременно построение дерева возможных вариантов (рис. 1).
Рис. 1 - Дерево возможных вариантов одномерной задачи
Многомерная задача. При решении многомерных задач, т.е. задач с несколькими ограничениями (т>1), верхняя граница определяется по каждому из ограничений отдельно. При этом используются выражения, аналогичные (8) - (10).
Верхняя граница определяется из условия
(12) где определяется с помощью выражения, аналогичного выражению (9).
Выбор очередной переменной для включения ВS производится с помощью условия
, (13) где
.
Несмотря на увеличение трудоемкости (но сравнению с одномерными задачами), решение многомерных задач методом ветвей и границ является достаточно актуальным. Например, к таким задачам можно отнести часто возникающие задачи планирования производства: имеющимся количеством бригад, при ограничениях на расход сырья, произвести максимальное количество продукции.
Производственному объединению из состава восемнадцати бригад поставлена задача производства группы изделий. На выполнение задачи отпущено 13 тыс. ед.сырья. Необходимо так спланировать объем производства, чтобы имеющимся количеством бригад, при ограничениях на расход сырья (табл.4), произвести максимальный объем продукции.
Таблица 4
Параметр Параметр
1 2 3 4 5 6 7 8
Важность изделий 610210620820
Количество бригад 852564210
Количество сырья , тыс. ед.сырья.852564210
Рассчитав величины
=||0,75 2 1 2 1 5 4 2||; =||4 5 4 20 6 5 16 4||;
производим решение задачи с учетом ограничений на число бригад и на количество сырья. Процесс решения показан в табл. 5. Решение сопровождается построением дерева возможных вариантов (рис. 2).
Рис. 2 - Дерево возможных вариантов многомерной задачи
Результаты решения показывают, что для максимального производства необходимо производить изделия № 6, 7, 2, 4, 3. При этом будет израсходовано 7,5 тыс. ед. сырья из 13 тыс. ощущенных.
Таким образом, рассмотренный алгоритм может быть использован для решения как одномерных, так и многомерных задач целочисленного программирования. Алгоритм сравнительно прост, позволяет учитывать на каждом шаге оптимизации жесткость каждого из ограничений и обеспечивает высокую точность оценки верхней границы целевой функции. Алгоритмы, основанные на методе ветвей и границ, легко программируются для ЭВМ. Эффективность метода ветвей и границ часто удается повысить, используя специфические особенности конкретной задачи.
Основной недостаток метода ветвей и границ - отсутствие общих способов оценки верхней (нижней) границы решения. При этом чем точнее способ оценки границы решения, тем эффективнее отсекаются бесперспективные варианты.
2. Оптимизация решений с использованием методов динамического программирования программирование отсечение решение
Основная идея динамического программирования заключается в замене одновременного выбора большого количества параметров поочередным их выбором. Многомерная задача оптимизации сводится к многошаговой задаче меньшей размерности. При этом одним из достоинств метода является общность подхода к решению самых различных задач оптимизации решений.
В основу метода положен принцип оптимальности, заключающийся в том, что при пошаговом процессе каждое последующее решение должно быть оптимальным относительно предыдущего решения.
Принцип оптимальности является частным случаем более общего и физически понятного принципа инвариантного (независимого) погружения. Сущность принципа погружения заключается в том, что исходная задача заменяется более общей, частным случаем которой является исходная задача. Результаты решения более общей задачи позволяют определить решение исходной задачи. Таким образом, исходная задача как бы «погружается» в более общую задачу.
Целевая функция L в зависимости от содержания задачи может максимизироваться или минимизироваться, однако сущность метода при этом не меняется. Математически задача формулируется (при максимизации L) следующим образом.
Определить
(14) при ограничениях
(15)
В этой задаче максимум функции L зависит от величины ресурса D и числа параметров управления N. Для того, чтобы эту задачу сделать определенной, вводят последовательность функций fn(Dn) для n = 1, 2, ?,N. При этом должно выполняться условие
; (16)
(17)
Таким образом, мы перешли от решения задачи (14), (15) к решению более общей задачи (16), (17). Действительно, определив функцию FN(DN) при выполнении условия (17), мы находим целое семейство решений для различных значений FN(DN). По условиям же задачи (14), (15) нас интересует только одно решение.
Для удобства решения функционального уравнения (16) табличным способом перепишем его в следующем виде: ;
На каждом шаге итерационной схемы решения необходимо найти решение всех задач для заданного числа переменных n и всех Все шаги, кроме первого, являются однотипными.
Рассмотрим пошаговый процесс динамического программирования на примере решения следующей задачи.
Для поражения четырех групп целей, боевые потенциалы которых , имеется двадцать средств поражения. Известно количество средств , необходимых для их поражения с заданной степенью. Определить план поражения, при котором противнику будет нанесен максимальный ущерб.
Данная задача соответствует математической постановке (14), (5) при D = 20, N = 4. Воспользуемся функциональным уравнением, для решения которого необходим следующий пошаговый процесс.
Шаг 1. ;
,
Если D1 = 0, то d1x1?D1в том случае, когда x1 = 0 (так как d1 = 5 и 5x1?0при x1 = 0).
Поэтому
Если D1 = 1,tod1x1?D1 в том случае, когда x1 = 0.
Поэтому
Аналогично ПРИD1 =2, 3, 4.
Если D1 = 5,tod1x1?D1 в том случае, когда 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)
Для ускорения выявления вариантов, не удовлетворяющих условию Dn?D, целесообразно нумерацию элементов исходного множества осуществлять в соответствии с условиями
(23)
2 ?k?N.
Если в соответствии с этими условиями можно пронумеровать не все элементы, а лишь k<N элементов, то оставшиеся (N-k) элементов нумеруют как отдельное подмножество в соответствии с условиями (6.33), присваивая первому элементу этого подмножества номер k 1, второму элементу -k 2 и т.д.
Поясним теперь сущность алгоритма решения задачи на примере оптимизации плана огневого поражения четырех групп целей (N=4) двадцатью средствами поражения (D=20).
Известны варианты xjвозможного использования этих средств по каждой группе целей, характеризующиеся соответствующим ущербами cj, наносимыми противнику средствами поражения dj (табл. 10). Нумерация групп целей (элементов) выполнена согласно условиям (23), а нумерация вариантов для каждой группы целей в соответствии с (20). Необходимо составить план поражения, при котором противнику будет нанесен максимальный ущерб.
Основные положения алгоритма заключаются в следующем.
1. Значения c1,d1заносятся в верхнюю строку первой таблицы, а c2,d2- в левый столбец этой же таблицы. Заполнение строки и столбца осуществляется последовательно, по мере вычислений в клетках таблицы.
2. После вычисления в первой таблице первого члена последовательности его значения заносятся в верхнюю строку второй таблицы; В левый столбец этой таблицы заносятся (последовательно) значения c3, d3. По этим данным вычисляется первый член последовательности .
3. Процессы повторяются до тех пор, пока в последней таблице (а число таблиц равно N-1) не будет найдено максимальное значение
.
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), удовлетворяющего условию D4?D, заносим в левый столбец очередные значения 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не обязательно соответствует и большие значения cj. Упорядочение исходных данных для решения этой задачи должно начинаться с расположения элементов в ряд, удовлетворяющий условию
(24)
Это условие означает, что из исходного множества элементов формируется ряд, в котором номера соответствуют принципу невозрастания значений полезности cj и затрат dj. Такая ранжировка элементов наилучшим образом соответствует идее модифицированного метода динамического программирования.
В зависимости от характера исходных данных при решении задач второго типа, после получения ряда согласно условию (24), могут быть следующие случаи упорядочения исходного множества элементов.
1. Если k =N, то оптимальное множество элементов выбирают из всего упорядоченного множества (случай А).
2. Если k<N, то вычисляют значения для упорядоченного подмножества и для оставшегося подмножества значения , где номера устанавливают в соответствии с убыванием величин hl.
Затем сравнивают hj иhl; при этом возможны следующие случаи: а) для всех ; тогда сформированное упорядоченное подмножество считается окончательным, элементы подмножества остаются пронумерованными в соответствии с убыванием hl;
б)для некоторых элементов первоначально сформированного упорядоченного подмножества выполняется неравенство ; тогда эти элементы переводят из подмножества в подмножество , и полученное новое упорядоченное подмножество является окончательным, а элементы подмножества нумеруют в соответствии с убыванием значений hl.
Оптимальное подмножество элементов выбирают только из подмножества , если и в процессе оптимизации будет получено значение (случай Б). Подмножество является достаточным для набора из него подмножества , поскольку любой из элементов подмножества хуже любого из элементов подмножества по показателю h.
Если (случай В), то оптимальное подмножество элементов выбирают из и из , .
В частном случае (случай Б0) может быть , и тогда оптимальным является упорядоченное подмножество , т.е. решение задачи фактически заканчивается формированием этого подмножества.
Поясним изложенное на ряде примеров.
Пусть требуется составить оптимальный план огневого поражения восьми целей, если известны (табл. 14) боевые потенциалы cj (в усл. ед.) каждой из них и необходимые количества боеприпасов dj (в усл. ед) для поражения каждой из них с заданной степенью. Известно имеющееся количество боеприпасов D = 15 (усл. ед.).
Таблица 14 cj 1 8 15 6 9 4 2 10 dj 1 2 5 2 3 1 1 5
Данная задача относится к задачам второго типа, и в соответствии с условием (24) выполним упорядочение исходных данных (табл. 15).
Здесь k=N=8, что соответствует случаю А; следовательно, оптимальный выбор элементов (целей) необходимо осуществлять из всего упорядоченного множества. Для этого используем табличный способ, аналогично уже рассмотренному примеру решения задачи первого типа (табл. 16- 22).
Из табл. 22 следует, что максимальный ущерб, наносимый противнику, составит f8 =L= 45 (усл. ед.), а также необходимость включения в план поражения восьмой цели (т.е. x8 = 1). По значениям f7 = 44 и D7 = 14 (из табл. 22) после вхождения в табл. 21 находим x7 = 1 и f6 = 42, D6 = 13.
Поступая аналогичным образом, с помощью табл. 20-16 определяем: x7 =1, x6 = 1, x5 = 1, x4 = 1, x3 = 1, x2 = 0, x1 = 1. Таким образом, в план поражения следует не включать лишь цель с номером 2.
Упорядочение исходных данных в случаях Б и В рассмотрим на аналогичном примере, характеризуемом исходными данными в табл. 23 для N = 10 при двух вариантах ограничений: а) D = 12, б) D = 20.
Таким образом, окончательно имеем: Теперь определяем подмножество (или подмножества), из которого следует выбрать оптимальное подмножество элементов. Для этого вычисляем
Отсюда следует, что а) при D = 12получаем и, следовательно, оптимальный выбор осуществляем лишь из подмножества (случай Б);
б) при D = 20 получаем и следовательно, оптимальный выбор осуществляем из подмножества и из подмножества (случай В).
Дальнейшее решение задач выполняется так, как уже было показано.