2.6. Общий случай

шаг.

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

имеет место Qk (ykT) ^ Qk(ykT) в оптимальном решении оценочной задачи. Из этого факта следует естественная процедура разбиения на подмножества. Если для предприятия k в оптимальном решении

ykT оценочной задачи имеет место Qk (ykT )< Qk (ykT), то разбиваем множество всех решений на два подмножества. В первом подмножестве ykT < ykx, а во втором - ykT > ykx . III

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

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

нижняя оценка является точной (то есть, Qk (ykT ) = Qk(yki) для всех предприятий), задача решена.

Замечание. Если для какого либо подмножества получена задача с выпуклыми, вогнутыми или выпуклыми и вогнутыми зависимостями, то для ее решения применяются алгоритмы, описанные в разделах 2.3, 2.4, 2.5 соответственно.

Рассмотрим работу метода ветвей и границ на примере.

Пример 2.5. Рассмотрим четыре предприятия с функциями Qk(ykT), графики которых приведены на рис. 2.10 (а, б, в, г).

Пусть RT = 6. I

шаг. Строим оценочные функции (они показаны пунктиром на рис.

б)

1

2

3

8 /7 // м v //! Л ! // ' / ! я 1

^^ 1 1 У1Т — 1

2

3

а) II

шаг. Решаем оценочную задачу. Для этого построим таблицу первых разностей (таблица 2.12).

а) б)

Рис. 2.10.

Таблица 2.12. 1 2 3 4 1 1 22/3 2 3 2 31/2 22/3 3 3 3 31/2 22/3 3 3 Составляем таблицу 2.

3 максимальных уровней в зависимо

сти от величины первой разности А (см. таблицу 2.4).

Таблица 2.13. Ч\ к А\ 1 2 3 4 R(A) 1 1 0 0 0 1 2 1 0 1 0 2 22/з 1 3 1 0 5 3 1 3 3 3 10 Оптимальный план (один из многих) имеет вид: У1Т = 1, У2Т = 3, У3Т = 2, У4Т = 0. Оценка Q (б) = 1 + 8 + 5 = 14.

Так как Q3 (2) < Q3(2), то разбиваем множество всех решений на два подмножества. В первом подмножестве y3T < 2, а во втором -

У3Т ^ 2.

Оценка первого подмножества. Таблица первых разностей принимает уже другой вид:

Таблица 2.14. j 1 2 3 4 1 1 22/3 2 3 2 372 22/3 б 3 3 372 22/3 - 3 Теперь оптимальное решение оценочной задачи будет другим:

У1Т = 1, У2Т = 3, У3Т = 1, У4Т = 1. Оценка первого подмножества равна:

Q^ < 2) = 1 + 8 + 2 + 3 = 14. Оценка второго подмножества. Таблица первых разностей имеет вид:

Таблица 2.15. j 1 2 3 4 1 1 22/3 - 3 2 372 22/3 - 3 3 372 22/3 1 3 Оптимальное решение оценочной задачи: 38

У1Т = 1, У2Т = 2, У3Т = 3, У4Т = 0. Оценка второго подмножества равна:

Q(y3T > 2) = 1 + 51/3 + 9 = 151/3. Выберем первое подмножество, имеющее меньшую оценку. Так как в оптимальном решении оценочной задачи для первого подмножества имеет место Q4 (1) < Q4(1), то разбиваем его на два подмножества. В первом подмножестве y4T < 1, а во втором - y4T > 1. Оценка подмножества y3T ? 2, y4T ? 1. Оптимальное решение оценочной задачи имеет вид:

У1Т = 1, У2Т = 3, У3Т = 1, У4Т = 1.

Оценка подмножества равна

QG^ < 2, У4Т < 1) = 1 + 8 + 2 + 5 = 16. Заметим, что эта оценка является точной нижней оценкой, так как

Qk = Qk для всех предприятий.

Оценка подмножества y3T ? 2, y4T > 1.

QG^r < 2, У4Т > 1) = 1 + 51/3 + 2 + 6 = 141/3. Выбираем подмножество У3Т < 2, У4Т > 1 с минимальной оценкой.

Так как в оптимальном решении оценочной задачи имеет место Q2 (2) < Q2(2), то разбиваем это подмножество на два. В одном из них У2Т < 2, а во втором - У2Т > 2.

Оценка подмножества {y2T ? 2, y3T ? 2, y4T > 1}. Оптимальное решение оценочной задачи имеет вид: У1Т = 1, У2Т = 2, У3Т = 1, У4Т = 2. Оценка подмножества равна Q^ < 2, У3Т < 2, У4Т > 1) = 1 + б + 2 + б = 15, и является точной нижней оценкой.

Оценка подмножества {y2T > 2, y3T ? 2, y4T > 1}.

Оптимальное решение оценочной задачи имеет вид: У1Т = 1, У2Т = 3, У3Т = 0, У4Т = 2. Оценка подмножества равна

Q^ > 2, У3Т < 2, У4Т > 1) = 1 + 8 + 0 + б = 15, и также является точной нижней оценкой.

Окончательно получаем два оптимальных решения: У1Т = 1, У2Т = 2, У3Т = 1, У4Т = 2, и У1Т = 1, У2Т = 3, У3Т = 0, У4Т = 2 с величиной упущенной выгоды равной 15.

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

Рис. 2.11.

2.7. Метод динамического программирования

Метод динамического программирования в ряде случаев является более эффективным по сравнению с методом ветвей и границ, особенно, в случае малых n и RT.

Идея метода в том, что последовательно определяется минимальная величина упущенной выгоды для возможных значений 0 < R < RT, если региональный уровень R обеспечивается за счет первых двух предприятий, затем первых трех, и т.д. Обозначим через Фщ^) - минимальную величину упущенной выгоды в случае, если уровень R обеспечивается только за счет первых m предприятий. Величины Фт+1^) определяются на основе уравнения Белл- мана:

(2.7.1) Фщ+i(R)= min [Фт (R - i) + Qm+1 (i)].

0 < i < 3

Сложность алгоритма прямопропорциональна RTn или, учитывая, что RT < 3n, прямопропорциональна n2.

4

в методе ветвей и границ оценка n достигается в самом худшем случае. Средняя оценка, как показали многочисленные примеры, также имеет порядок n2. В то же время, во многих случаях метод ветвей и границ имел сложность порядка n. Рассмотрим применение метода на примере 2.5.

Значения Ф1^), 0 < R < 3, приведены ниже.

Таблица 2.16. R 0 1 2 3 Фх^) 0 1 6 8 Вычислим Ф2^), 0 < R < 6. Имеем:

Ф2(0) = 0,

Ф2(1) = Ш1И(Ф1(0) + Q21; Фх(1) + Q20) = 1,

Ф2(2) = ш1п(Ф1(0) + Q22; Фх(1) + Q21; Ф:(2) + Q20) = ш1п(б; б; б) = б, Ф2(3) = ш1И(ФХ(0) + Q23; Фх(1) + Q22; Фх(2) + Q21; Фх(3) + Q20) =

= Ш1П(8; 7; 11; 8) = 7, Ф2(4) = ш1п(Ф1(1) + Q23; Ф1(2) + Q22; Ф1(3) + Q21) = ш1п(9; 12; 13) =

9,

Ф2(5) = Ш1П(Ф1(2) + Q23; Ф1(3) + Q22) = 14, Ф2(б) = Ф1(3) + Q23 = 1б.

Вычислим Ф3(Я). Заметим, что так как R^ — б, то первые три предприятия должны обеспечить по крайней мере уровень не менее R = 3. Имеем:

Ф3(3) = Ш1П(Ф2(0) + Q33; Ф2(1) + Q32; Ф2(2) + Q31; Ф2(3) + Q30) =

= Ш1П(9; 9; 8; 7) = 7, Ф3(4) = Ш1П(Ф2(1) + Q33; Ф2(2) + Q32; Ф2(3) + Q31; Ф2(4) + Q30) =

= Ш1П(10; 14; 9; 9) = 9, Ф3(5) = Ш1П(Ф2(2) + Q33; Ф2(3) + Q32; Ф2(4) + Q31; Ф2(5) + Q30) =

= Ш1П(14; 15; 11; 14) = 11, Ф3(б) = Ш1П(Ф2(3) + Q33; Ф2(4) + Q32; Ф2(5) + Q31; Ф2(б) + Q30) = = ш1п(1б; 17; 1б; 1б) = 1б. Наконец, вычислим Ф4(RT). Ф4(б) = ш1п(Ф3(3) + Q43; Ф3(4) + Q42; Ф3(5) + Q41; Ф3(б) + Q40) = = ш1п(1б; 15; 1б; 1б) = 15.

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