<< Предыдущая

стр. 5
(из 10 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

˜

два подмножества. В первом подмножестве yНT ? 4, а во втором -
yНT ? 4.
Оценка первого подмножества. Первые разности для функ-
ции Q H (R ) при R ? 4 приведены ниже:
˜

Таблица 2.10.
0?R?3 3?R?4
R
? 52/3 9


Теперь оптимальное решение будет иметь следующий вид:
y1T = y2T = y3T = yНT = 3,
а величина упущенной выгоды равна
12 + 14 + 13 + 17 = 56.
Оценка второго подмножества. Первые разности для функ-
ции Q H (R ) при 4 ? R ? 9 приведены ниже:
˜

Таблица 2.11.
4?R?6 6?R?9
R
? 62/3
5


Оптимальное решение для этого подмножества решений имеет вид:
y1T = 2, y2T = 2, y3T = 2, yНT = 6.
а величина упущенной выгоды равна
6 + 7 + 6 + 36 = 55.


32
Оценка второго подмножества меньше, поэтому выбираем
второе подмножества. Заметим теперь, что оценка 55 является
достижимой, поскольку Q H (6 ) = QH(6). Таким образом мы получи-
˜

ли оптимальное решение.
Дадим описание общей схемы предлагаемого алгоритма и
оценку его сложности.
1. Решение задачи для множества предприятий с вогнутыми
зависимостями Qk(ykT) для всех значений R. Если n1 – число пред-
приятий с вогнутыми зависимостями, то число решаемых задач не
более 3n1. Из них n1 задач решаются сразу (это задачи, для которых
R = 3m, где m – целое число) в соответствии с утверждением 2.
Сложность решения остальных 2n1 задач растет прямопропорцио-
нально n1. Поэтому сложность решения задачи первого этапа, оце-
ниваемая числом элементарных операций (сложение, вычитание,
сравнение) растет прямопропорционально n12.
2. Построение оценочной функции Q H (R ) .
˜

Опишем алгоритм построения оценочной функции. Обозна-
чим через m = min (RT, 3n1).
I шаг. Определяем величины
Q H (R )
q1 (R ) =
R
и находим минимальную из q(R), 1 ? R ? m. Пусть минимум дости-
гается в точке R1. Переходим к следующему шагу, если R1 < m – 1.
II шаг. Определяем величины
Q H (R ) ? Q H (R1 )
q 2 (R ) =
R ? R1



33
для всех R1 < R ? m, и находим минимальную из них. Пусть мини-
мум достигается в точке R2. Переходим к следующему шагу, если
R2 < m – 1.
k-ый шаг. Определяем величины
Q H (R ) ? Q H (R k ?1 )
q k (R ) =
R ? R k ?1
для всех Rk-1 < R ? m, и находим минимальную из них. Пусть мини-
мум достигается в точке Rk. Переходим к следующему шагу, если
Rk < m – 1.
За конечное число шагов k1 (не более m-1) процедура будет
закончена. Точки (Rs, QH(Rs)), s = 1, k1 , включая точки (0, 0) и (m,
QH(m)), дают искомую оценочную функцию.
Сложность алгоритма растет прямопропорционально m3.
3. Решение оценочной задачи. Оценочная задача является
задачей с выпуклыми функциями, метод решения которой описан в
разделе 2.3. При заданном RT сложность ее решения растет прямо-
пропорционально n22, где n2 – число предприятий с выпуклыми
функциями Qk(ykT).
4. Разбиение на подмножества и решение оценочных задач
для подмножеств. Выбор подмножества с минимальной оценкой.
5. Для выбранного подмножества повторяются шаги 2, 3, 4.
Очевидно, что число подмножеств не превышает m. Следовательно,
сложность решения всей задачи растет прямопропорционально
величине
an12 + [bm3 + c(n – n1)2]m,
где a, b, c – положительные константы.



34
В целом, при больших n сложность растет прямопропорцио-
нально n4 (в худшем случае). Эта оценка свидетельствует о доста-
точной эффективности предложенного алгоритма.


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

Рассмотрим общий случай, когда существуют предприятия,
функции Qk(ykT) которых не являются ни выпуклыми, ни вогнуты-
ми. Опишем применение метода ветвей и границ для этого случая.
I шаг. Строим оценочные функции Q k (y kT ) для всех невы-
˜

пуклых зависимостей Qk(ykT).
II шаг. Решаем оценочную задачу, как описано в разделе 2.3.
Нетрудно доказать, что всегда существует решение оценоч-
ной задачи, в котором только не более чем для одного предприятия
имеет место Q k (y kT ) ? Qk(ykT) в оптимальном решении оценочной
˜

задачи. Из этого факта следует естественная процедура разбиения
на подмножества. Если для предприятия k в оптимальном решении
() ()
˜
y? оценочной задачи имеет место Q k y? < Q k y? , то разбива-
kT kT kT
ем множество всех решений на два подмножества. В первом под-
множестве ykT ? y? , а во втором - ykT ? y? .
kT kT
III шаг. Оцениваем каждое подмножество, решая оценочные
задачи согласно шагам I и II. Из двух подмножеств выбираем под-
множество с минимальной оценкой. Если для этого подмножества в
оптимальном решении оценочной задачи существует предприятие,
() ()
˜
для которого Q k y? < Q k y? , то повторяем процедуру разбиения
kT kT
на подмножества, каждый раз оценивая новые подмножества и

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

предприятий), задача решена.
Замечание. Если для какого либо подмножества получена за-
дача с выпуклыми, вогнутыми или выпуклыми и вогнутыми зави-
симостями, то для ее решения применяются алгоритмы, описанные
в разделах 2.3, 2.4, 2.5 соответственно.
Рассмотрим работу метода ветвей и границ на примере.
Пример 2.5. Рассмотрим четыре предприятия с функциями
Qk(ykT), графики которых приведены на рис. 2.10 (а, б, в, г).
Пусть RT = 6.
I шаг. Строим оценочные функции (они показаны пунктиром
на рис. 2.10).
II шаг. Решаем оценочную задачу. Для этого построим табли-
цу первых разностей (таблица 2.12).
Q1 Q2
8 8

6 6
5



y1T y2T
1
1 2 3 1 2 3

а) б)




36
Q3 Q4
9
9
8

6
5


2
y3T y4T
1 2 3 1 2 3

а) б)
Рис. 2.10.



Таблица 2.12.
k
1 2 3 4
j
22/3
1 2 3
1
31/2 22/3 3 3
2
31/2 22/3 3 3
3
Составляем таблицу 2.13 максимальных уровней в зависимо-
сти от величины первой разности ? (см. таблицу 2.4).
Таблица 2.13.
k
1 2 3 4 R(?)
?
1 0 0 0 1
1
1 0 1 0 2
2
22/3 1 3 1 0 5
1 3 3 3 10
3


Оптимальный план (один из многих) имеет вид:
37
y1T = 1, y2T = 3, y3T = 2, y4T = 0.
Оценка Q(6 ) = 1 + 8 + 5 = 14.
˜

Так как Q3 (2 ) < Q3(2), то разбиваем множество всех решений
˜

на два подмножества. В первом подмножестве y3T ? 2, а во втором -
y3T ? 2.
Оценка первого подмножества. Таблица первых разностей
принимает уже другой вид:
Таблица 2.14.
k
1 2 3 4
j
22/3
1 2 3
1
31/2 22/3 6 3
2
31/2 22/3 - 3
3


Теперь оптимальное решение оценочной задачи будет другим:
y1T = 1, y2T = 3, y3T = 1, y4T = 1.
Оценка первого подмножества равна:
Q(y3T ? 2) = 1 + 8 + 2 + 3 = 14.
Оценка второго подмножества. Таблица первых разностей
имеет вид:
Таблица 2.15.
k
1 2 3 4
j
22/3
1 - 3
1
31/2 22/3 - 3
2
31/2 22/3 1 3
3


Оптимальное решение оценочной задачи:

<< Предыдущая

стр. 5
(из 10 стр.)

ОГЛАВЛЕНИЕ

Следующая >>