Типовые процедуры решения задач дискретной оптимизации

Если число решений  очень велико, то можно построить  относительные оценки состояний  так, чтобы оценки, отвечающие каждой паре последовательных решений, отличались друг от друга на постоянную величину, представляющую собой средний «доход»  на решение. Также можно выполнять  дисконтирование доходов от будущих  решений. Необходимость в этом иногда появляется в том случае, когда  решение принимаются редко, скажем раз в году. Тогда уже не нужно  рассматривать последовательно 1,2,3…решения, чтобы достичь решения с большим  номером. Вместо этого можно непосредственно  оперировать функциональным уравнением, что, как правило, дает существенную выгоду с точки зрения сокращения объема вычислений.

 

 

 

2. Метод ветвей и границ в решении задач дискретной оптимизации

Понятие о методе ветвей и границ

 

Метод ветвей и  границ — один из комбинаторных  методов. В основе метода ветвей и  границ лежит идея последовательного  разбиения множества допустимых решений на подмножества. На каждом шаге метода элементы разбиения подвергаются проверке для выяснения, содержит данное подмножество оптимальное решение  или нет. Проверка осуществляется посредством  вычисления оценки снизу для целевой  функции на данном подмножестве. Если оценка снизу не меньше рекорда — наилучшего из найденных решений, то подмножество может быть отброшено. Проверяемое подмножество может быть отброшено еще и в том случае, когда в нем удается найти наилучшее решение. Если значение целевой функции на найденном решении меньше рекорда, то происходит смена рекорда. По окончанию работы алгоритма рекорд является результатом его работы.

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

Вычисление  нижней границы является важнейшим  элементом данной схемы.

 

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

 

Общая схема метода ветвей и границ

 

Пусть стоит задача:

                     (2.1)

где D — конечное множество.

Алгоритм является итеративным, и на каждой итерации происходит работа с некоторым подмножеством множества D. Назовем это подмножество текущим и будем обозначать его как D^(q) , где q — индекс итерации. Перед началом первой итерации в качестве текущего множества выбирается все множество D (D⁽¹⁾ =D), и для него некоторым способом вычисляется значение верхней оценки для целевой функции . Стандартная итерация алгоритма состоит из следующих этапов:

1.Если   можно   указать   план   ,   для   которого , то — решение задачи (2.1).

2. Если такой план не  найден, то область определения D^(q) некоторым образом разбивается на подмножества , удовлетворяющие условиям:

    (2.2)

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

2.1. Если существует такой  план  , что

  то этот план оптимальный.

2.2. Если такой план  не найден, то выбирается одно  из множеств (как правило, имеющее наибольшую оценку):

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

 

 

 

 

 

 

 

 

 

Рис. 1

 

Схема дробления множества D представлена на рис. 1 в виде графа. Существуют и более сложные системы индексации подмножеств, при которых не требуется их переобозначение на каждом шаге.

Конкретные реализации метода ветвей и границ связаны с правилами  разбиения на подмножества (правилами  ветвления) и построения оценок значений целевых функций на данных подмножествах (границ).

 

 

3. Решение задачи о ранце методом динамического программирования

Классическая задача о ранце (КЗР). Имеются ранец и предметы П_1, П₂,…, П_n; каждый предмет П_i характеризуется двумя целыми положительными показателями: с_i –

 

стоимость предмета; v_i – вес предмета, i = . Предметы недробимы, т.е. каждый из них можно поместить в ранец только целиком. Требуется найти совокупность предметов, которые следует поместить в ранец с тем, чтобы суммарная стоимость предметов в ранце оказалась максимальной при условии, что суммарный вес предметов в ранце не может превысить заданной натуральной константы W (предполагается, что суммарный вес всех имеющихся предметов больше W).

 

КЗР формулируется как следующая задача булева линейного программирования (БЛП):

 

 

n

        max    (3.1) i=1

 

при условиях

 

n

≤ W;    (3.2) i=1

 

 

х_i {0,1}, i=.         (3.3) Задачу (3.1)- (3.3) далее будем именовать задачей Z.

По начальным данным задачи Z формулируем совокупность частных задач о ранце Z(k, p), где k{1, 2,…, n}; р{1, 2,…, W}. Задача Z(k, p) записывается следующим образом:

 

k

        max 

i=1

 

при условиях

 

k

≤ p; (3.2) i=1

 

 

 

х_i {0,1}, i=.

 

(в частной задаче Z(k, p) имеющимися в наличии считаются только первые k предметов из совокупности {П₁, П₂,…, П_n}, суммарный вес предметов в ранце не может превышать константы р).

 

Оптимальное значение критерия в частной задаче Z(k, p) обозначим В*(k, p). Как очевидно, задача Z(n,W) совпадает с исходной задачей Z; поэтому В*(n,W) – оптимальное значение критерия в задаче Z .

Легко видеть, что

 

0 при р{0,1,2,…, v₁- 1};

 

В*(1, p) =   (3.4) с₁ при р{v₁, v₁+1,…, W}.

Пусть для некоторого k, принадлежащего множеству {1, 2,…, n-1} и всех р{1, 2,…, W} значения функции В*(k, p) уже вычислены. При р{0,1,2,…, v_k+1- 1} ситуация, возникающая при нахождении В*(k+1, p), фактически не отличается от ситуации, имевшей место при подсчете В*(k, p), ибо дополнительно появляющийся при переходе от задачи Z(k, p) к задаче Z(k+1, p) предмет П_k+1 в ранец поместить невозможно. В случае, когда р{v_k+1, v_k+1+1,…,W}, при переходе от задачи Z(k, p) к задаче Z(k+1, p) мы получаем дополнительную возможность поместить в ранец предмет П_k+1. Этой возможностью можно: а) не воспользоваться; б) воспользоваться. Очевидно, что в случае а) мы получим уже вычисленную величину В*(k, p). В случае б) в ранец кладется предмет П_k+1 стоимостью с_k+1 и так как вес этого предмета равен v_k+1, то далее мы оказываемся в условиях задачи Z(k, p - v_k+1). В итоге получаем:

 

В*(k, p), если р{0,1,2,…, v_k+1- 1};

 

В*(k+1,p)=         (3.5)

 

max { В*(k, p), с_k+1 + В*(k, p - v_k+1) } при р{v_k+1, v_k+1+1,…, W};

здесь k= 2, 3,…, n-1.

 

Равенства (3.4) - (3.5) – рекуррентные соотношения динамического программирования для решения задачи о ранце. Пользуясь ими, мы находим сначала величины В*(1, p), р{1, 2,…, W}, затем величины В*(2, p), р{1, 2,…, W}, и т.д., вплоть до отыскания В*(n, W) – оптимального значения критерия в исходной задаче Z .

 

Процедуру вычисления значений функции В*(k, p) целесообразно реализовывать как процесс последовательного заполнения строк таблицы стоимостей. В этой таблице строки соответствуют значениям параметра k (по возрастанию), а столбцы – значениям параметра р (также по возрастанию). В каждую клетку, расположенную в пересечении произвольной строки k и произвольного столбца р, вносится значение В*(k, p). Первая строка заполняется согласно формуле (3.4). Далее заполнение каждой (k+1)-ой строки, k= 1,2,…, n-1, осуществляется в соответствии с формулой (3.5). Одновременно целесообразно фиксировать множества предметов М(k, p), которые обеспечивают значения В*(k, p) критериев рассматриваемых частных задач. Как очевидно, М(1, p) =, если р < v₁; М(1, p) ={1} в противном случае. Далее можно считать

 

М(k, p), если В*(k+1, p) = В*(k, p); М(k+1, p) =

М(k+1, p) = М(k, p - v_k+1) { k+1} в противном случае.

 

В заполненной таблице  стоимостей содержимое клетки (n, W) – оптимальное значение критерия в задаче Z. Для обеспечения этого значения в ранец следует поместить предметы совокупности М(n, W).

 

Изложенный алгоритм решения КЗР далее будем называть алгоритмом.

 

ПРИМЕР: Решить КЗР:

В машину грузоподъемностью 35 т. загрузить предметы с наибольшей суммарной ценой (полезностью). Характеристика предметов дана в таблице:

Номер предмета	1	2	3	4	5	6
Вес                                  (т.)	4	7	11	12	16	20
Цена                           (тыс. руб.)	7	10	15	20	27	34

 т.

Формализуем условие задачи:

7x₁+10x₂+15x₃+20x₄+27x₅+34x₆               max

4x₁+7x₂+11x₃+12x₄+16x₅+20x_635;

x_i {0,1}, i=.

Таблица стоимостей 1:

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35
1	0	0	0	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7
2	0	0	0	7	7	7	10	10	10	10	17	17	17	17	17	17	17	17	17	17	17	17	17	17	17	17	17	17	17	17	17	17	17	17	17
3	0	0	0	7	7	7	10	10	10	10	17	17	17	17	22	22	22	25	25	25	25	32	32	32	32	32	32	32	32	32	32	32	32	32	32
4	0	0	0	7	7	7	10	10	10	10	17	20	20	20	22	27	27	27	30	30	30	32	37	37	37	37	42	42	42	45	45	45	45	52	52
5	0	0	0	7	7	7	10	10	10	10	17	20	20	20	22	27	27	27	30	34	34	34	37	37	37	37	44	47	47	47	49	54	54	54	57
6	0	0	0	7	7	7	10	10	10	10	17	20	20	20	22	27	27	27	30	34	34	34	37	41	41	41	44	47	47	47	51	54	54	54	57