2.5. Выпукло-вогнутый случай

На втором этапе решается задача для предприятий с выпуклыми зависимостями Qk(ykT) и одним обобщенным предприятием Н, имеющим зависимость QH(R). Для решения этой задачи эффективным методом является метод ветвей и границ. В этом методе зависимость QH(R) заменяется выпуклой оценочной функцией Qh(R)< Qh(R), максимально близкой к QH(R). Эффективность метода определяется в данном случае тем, что невыпуклой является только одна функция QH(R), и поэтому ветвление будет проводиться только в случае, если Qh(RQh(R) . Рассмотрим применение метода на примере.

Пример 2.4. Возьмем три первых предприятия из примера 2.2 и три первых предприятия из примера 2.3.

I этап. Решаем задачу для трех предприятий с вогнутыми функциями Qk(ykT), данные о которых приведены ниже.

Таблица 2.6.

1 9 12 9 2 14 17 16 3 17 19 20 Применяя алгоритм, описанный в разделе 2.4, получаем последова- тельно: 1. R = 1. QB(1) = 9; 2. R = 2. 0Н(2) = 14; 3. R = 3. QH(3) = 17; 4. R = 4. QH(4) = min (17 + 9; 19 + 9) = 26; 5. R = 5. QH(5) = min (17 + 16; 19 + 14) = 33; 6. R = 6. QH(6) = 36; 7. R = 7. QH(7) = min (36 + 9; 39 + 9) = 45; 8. R = 8. QH(8) = min (36 + 16; 39 + 14) = 52; 9. R = 9. QH(9) = 56; График зависимости QH(R) приведен на рис. 2.9.

Рис. 2.9.

Пунктиром показана функция Qh (R), являющаяся оценкой снизу для функции QH(R).

II этап. Пусть RT = 12. Данные о трех предприятиях с выпуклыми функциями Qk(ykT) приведены ниже (начальные величины Qk0 вычтены из всех Qkj).

Таблица 2.7. 1 2 3 1 2 2 2 2 6 7 6 3 12 14 13 Вычисляем таблицу первых разностей (таблица 2.8).

Таблица 2.8. 1 2 3 1 2 2 2 2 4 5 4 3 6 7 7 Таблица 2.9. R 0 < R < 3 3 < R < 6 6 < R < 9 D 52/з 61/з 62/3

Применяя алгоритм для случая выпуклых функций, получаем следующее решение:

y1T = 3, y2T = 2, y3T = 3, УШ- = 4. Так как Qh (4) < QH(4), то разбиваем множество всех решений на два подмножества. В первом подмножестве уНт < 4, а во втором - Уш- ^ 4.

Оценка первого подмножества. Первые разности для функции Qh (R) при R < 4 приведены ниже:

Таблица 2.10. R 0 < R < 3 3 < R < 4 D 52/3 9 Теперь оптимальное решение будет иметь следующий вид: y1T = y2T = y3T = yHT = 3, а величина упущенной выгоды равна

12 + 14 + 13 + 17 = 56. Оценка второго подмножества. Первые разности для функции Qh (R) при 4 < R < 9 приведены ниже:

Таблица 2.11. R 4 < R < 6 6 < R < 9 D 5 62/3 Оптимальное решение для этого подмножества решений имеет вид:

y1T = 2, y2T = 2, y3T = 2, yHT = 6. а величина упущенной выгоды равна

6 + 7 + 6 + 36 = 55.

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

Дадим описание общей схемы предлагаемого алгоритма и оценку его сложности. 1.

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

Построение оценочной функции Qh (R).

Опишем алгоритм построения оценочной функции.

шаг. Определяем величины

41(R )=^

и находим минимальную из q(R), 1 < R < m. Пусть минимум достигается в точке R1. Переходим к следующему шагу, если R1 < m - 1. II

шаг. Определяем величины

Qh (R)-Qh (R1)

q2 (R )=

R-R

для всех R1 < R < m, и находим минимальную из них. Пусть минимум достигается в точке R2. Переходим к следующему шагу, если R2 < m - 1.

k-ый шаг. Определяем величины

qk (R ) = QH (R)-QH (Rk-1)

kW R - Rk-1

для всех Rk-1 < R < m, и находим минимальную из них. Пусть минимум достигается в точке Rk. Переходим к следующему шагу, если Rk < m - 1.

За конечное число шагов ki (не более m-1) процедура будет закончена. Точки (R, 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 - положительные константы.

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