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

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

ОГЛАВЛЕНИЕ

Следующая >>

3 5 6
(2) (1)
Рис. 2.2.


T=1 T=2 T=3
(6) (5)
15 15 y2=2
16
(8) (7)

(4) (3)
7 9 10 y2=1
(14) (13)
(5)
(6)
y2=0
3 5 6
(2) (1)
Рис. 2.3.

t
Числа в скобках равны упущенной выгоде s kij . Так, напри-

мер, число 6 у дуги, соединяющей вторую (снизу) вершину первого
вертикального слоя (на рис. 2.2) с третьей (снизу) вершиной второ-
го вертикального слоя равно упущенной выгоде от отвлечения
средств на развитие СУПБ от уровня 1 в конце периода 1 до уровня


17
2 к концу периода 2. Числа в остальных вершинах равны мини-
мальной
T=1 T=2 T=3
(4) (3)
18 18 y3=2
12
(12) (7)

(2) (2)
14 14 7 y3=1
(17) (10)
(5)
(13)
y3=0
1 2 3
(1) (1)
Рис. 2.4.


упущенной выгоде от отвлечения средств на развитие СУПБ до
соответствующего уровня к концу соответствующего периода. Для
их определения применяется известный алгоритм определения
кратчайшего пути.
Зависимости Qk(ykT) приведены на рис. 2.5, 2.6, 2.7 соответст-
венно.




18
Q1(y1T)
18
14


6

y1T
1 2
Рис. 2.5.

Q2(y2T)

16

10
6

y2T
1 2
Рис. 2.6.




19
Q3(y3T)



12

7
3
y3T
1 2
Рис. 2.7.


Пусть требуемое значение регионального уровня ПБ равно 5.
В данном случае задачу легко решить простым перебором. Очевид-
но, что если y1T = 1, то y2T = y3T = 2 и величина упущенной выгоды
составит 14 + 16 + 12 = 42.
Если y1T = 2, то оптимальный вариант взять y2T = 1, y3T = 2,
что дает упущенную выгоду равную 18 + 10 + 12 = 40.
Выбирая минимальное из этих двух чисел, получаем опти-
мальное решение: y1T = 2, y2T = 1, y3T = 2, которому соответствуют
стратегии развития СУПБ предприятий, выделенные на рис. 2.2,
2.3, 2.4 толстыми дугами. Так, уровень y1T = 2 для первого предпри-
ятия достигается к концу третьего периода при следующей страте-
гии: в первом периоде поддерживается существующий (0-ой)
уровень СУПБ, к концу второго периода обеспечивается уровень
СУПБ равный 1, а к концу третьего – уровень 2.
Рассмотрим задачу обеспечения регионального уровня ПБ за
меньшее число периодов. Данные для ее решения можно получить
непосредственно из рис. 2.2, 2.3 и 2.4. Так, зависимостям Qk(yk2)

20
соответствуют числа второго вертикального слоя. Сведем эти дан-
ные в таблицу.
Таблица 2.1.
yk2
0 1 2
k
5 13 18
1
5 9 15
2
2 14 18
3

Простым перебором определяется оптимальное решение для
этого случая: y12 = 2, y22 = 1, y32 = 2 с величиной упущенной
выгоды Q(y2) = 45. В более сложных случаях для решения задачи
(2.2.6), (2.2.7) требуются специальные методы, описание которых
дается ниже для различного вида зависимостей Qk(ykT).


2.3. Выпуклый случай

Поскольку Q(y) заданы в дискретных точках y = 0, 1, 2, 3, то
обычное определение выпуклости к ним не применимо. Однако,
если соседние значения Q(y) соединить отрезками прямой, то полу-
чим непрерывную кусочно-линейную функцию Q(y ) . Будем счи-
˜

тать Q(y) выпуклой, если Q(y ) - выпуклая функция (см. рис. 2.6,
˜

2.7). Для случая выпуклых зависимостей задача (2.2.6), (2.2.7) решает-
ся достаточно просто. Метод решения рассмотрим на примере.
Пример 2.2. Значение функций Qk(ykT) = Qkj, j = 0, 3 , для шес-
ти предприятий приведены в таблице 2.2.
Таблица 2.2.


21
k
1 2 3 4 5 6
y
3 2 1 2 2 1
0
5 3 3 3 5 3
1
7 6 7 8 8 6
2
10 9 12 13 14 10
3


Составляем таблицу 2.3 первых разностей ?kj = Qkj – Qk,j-1,
j = 1, 3, k = 1, 6 .
Таблица 2.3.
k
1 2 3 4 5 6
j
2 1 2 1 3 2
1
2 3 4 5 3 3
2
3 3 5 5 6 4
3
Первые разности, как следует из таблицы 2.3., принимают
значения от 1 до 6. Составляем таблицу 2.4, в которой для каждого
значения ? от 1 до 6 и каждого предприятия высчитываем макси-
мальный уровень j, для которого ?kj ? ?. Так, например, при ? = 4
для первого и второго предприятий максимальный уровень j, как
следует из таблицы 2.3, равен 3, для третьего – 2, для четвертого –
1, для пятого – 2 и, наконец, для шестого – 3. Максимальные уров-
ни будем обозначать j(k, ?). В последнем столбце таблицы 2.4
вписываем сумму уровней всех предприятий, соответствующих
6
данному значению ?, то есть R (? ) = ? j(k, ? ) .
k =1
Таблица 2.4.


22
k
1 2 3 4 5 6 R(?)
?
0 1 0 1 0 0 2
1
2 1 1 1 0 1 6
2
3 3 1 1 2 2 12
3
3 3 2 1 2 3 14
4
3 3 3 3 2 3 17
5
3 3 3 3 3 3 18
6


Итоговая таблица 2.4. дает возможность определить для каждого RT
нормативные уровни ykT для каждого предприятия, минимизирую-
щие суммарную величину упущенной выгоды. Для этого при за-
данном RT определяем величину ? такую, что R(?) ? RT < R(?+1).
Определяем величины ykTиз условий
? y kT = R T
(2.3.1)
k
j(k, ?) ? ykT ? j(k, ?+1).
(2.3.2)
Полученные значения {ykT} минимизируют суммарную величину
упущенной выгоды. Доказательство этого факта легко следует из
условий выпуклости функций, и мы не будем его приводить. Дей-
ствительно, увеличивая RT, мы каждый раз увеличиваем норматив-
ные уровни у тех предприятий, для которых это увеличение дает
минимальное приращение упущенной выгоды. Так, при RT ? 2
каждое увеличение RT на 1 увеличивает упущенную выгоду так же
на ? = 1. При 2 ? RT ? 6 увеличение RT на 1 увеличивает упущенную
выгоду уже на ? = 2, при 6 ? RT ? 12 – на 3, и т.д.




23
График зависимости величины минимальной упущенной вы-
годы от регионального уровня ПБ приведен на рис. 2.8. Заметим,
что Q(RT) также является выпуклой функцией RT.


Q(RT)
70
68
62

47
39

21
13
11
RT
2 6 10 12 14 18 20

Рис. 2.8.


2.4. Вогнутый случай

Рассмотрим случай вогнутых зависимостей Qk(ykТ), предпола-
гая, что Qk0 = 0 (это всегда можно сделать, вычитая Qk0 из всех
значений Qkj). Известно, что задача (2.2.6), (2.2.7) в случае вогнутых
зависимостей Qk(ykТ) является многоэкстремальной. Тем не менее,
учитывая специфику задачи, связанную с тем, что ykТ принимает цело-
численные значения от 0 до 3, можно предложить эффективный

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

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

ОГЛАВЛЕНИЕ

Следующая >>