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

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

ОГЛАВЛЕНИЕ

Следующая >>

алгоритм ее решения. Предварительно докажем ряд утверждений.




24
Утверждение 2.1. Существует оптимальное решение задачи
(2.2.6), (2.2.7), в котором имеется не более одного предприятия со
значением 0 < yT < 3.
Доказательство. Поведем доказательство методом от про-
тивного. Пусть имеются два предприятия k и q, такие что 0 < ykT <3,
0 < yqT <3.
Пусть ykT = i, yqT = j. Обозначим
ai = Qk,i – Qk, i-1, bi = Qk,i+1 – Qk,i,
aj = Qk,j – Qk, j-1, bj = Qk,j+1 – Qk,j.
Положим ykT = i – 1, yqT = j +1. Из условия оптимальности исходно-
го решения следует, что должны выполняться условия
-ai + bj ? 0.
(2.4.1)
Положим теперь ykT = i + 1, yqT = j -1. Аналогично предыдущему
случаю из условия оптимальности исходного решения получаем
-aj + bi ? 0.
(2.4.2)
Из условия вогнутости функций Qk(ykT) и Qq(yqT) имеем
bi ? ai , bj ? aj .
(2.4.3)
Объединяя условия (2.4.1) – (2.4.3), получаем
bj ? ai ? bi ? aj ? bj,
(2.4.4)
что возможно только в одном случае, когда bj = ai = bi = aj. Однако,
в этом случае решение ykT = i-1, yqT = j+1, а также решение ykT = i+1,
yqT = j-1 являются оптимальными. Берем любое из этих решений,
например, первое, и повторяем процедуру. Через конечное число шагов
(не более двух) мы придем к решению, в котором либо ykT = 0, либо
yqT = 3. Таким образом, число предприятий, для которых 0 < ykT < 3
уменьшилось на единицу. Повторяя эту операцию с другой парой
предприятий, имеющих промежуточное значение ykT, мы за конеч-


25
ное число таких повторений получим оптимальное решение, со-
держащее не более одного предприятия со значением 0 < ykT < 3.
Пусть предприятия пронумерованы в порядке возрастания
Qk,3, то есть Q13 ? Q23 ? ... ?Qn3.
Утверждение 2.2. Если RT = 3m, где m – целое положитель-
ное число, то оптимальное решение задачи (2.2.6), (2.2.7) имеет вид
ykT = 3, k = 1, m , ykT = 0, k > m.
Доказательство. Построим для функций Qk(ykT) оценочные
функции:
Q
Q k (y kT ) = y kT ? k 3 .
˜
(2.4.5)
3
Эти функции дают оценку снизу для функций Qk(ykT) и совпадают с
ними в двух точках: ykT = 0 и ykT = 3. Рассмотрим задачу минимиза-
ции суммы оценочных функций при ограничениях
n
? y kT = R T , 0 ? y kT ? 3, k = 1, n .
k =1
Это задача линейного программирования, решение которой оче-
видно. Нужно взять первые m предприятий с минимальными значе-
ниями Qk3. Заметим, однако, что это решение является допустимым
решением для исходной задачи, поэтому оно также является опти-
мальным.
Таким образом, если n = 3m + s, где 0 < s < 3, то существует
оптимальное решение, в котором одно, и только одно предприятие
имеет значение ykT = s. Для определения этого предприятия постро-
им 2 решения. В первом решении первые m предприятий получают
максимальные нормативные уровни ykT = 3, k = 1, m . Среди остальных
(n – m) предприятий выбирается предприятие p с минимальной вели-

26
чиной Q ps = min Q i,s . Для этого предприятия ypT = s, для остальных
m <i? n
ykT = 0. Величина упущенной выгоды для этого решения составит
m
? Q k ,3 + Q p,s .
Q1 =
(2.4.6)
k =1

Во втором решении определяется предприятие l, такое что величи-
на
Q l,3 ? Q l,s = max (Q k ,3 ? Q k ,s ) .
1? k ?m

Все предприятия 1 ? k ? m+1, за исключением предприятия l полу-
чают нормативные уровни ykT = 3, для предприятия l нормативный
уровень ylT = s, для остальных предприятий ykT = 0. Величина упу-
щенной выгоды для второго решения составляет
m +1
? Q k ,3 + Q l,s
Q2 = .
k =1, k ? l

Разность величин Q1 – Q2 равна
? = Ql,3 + Qp,s - Ql,s – Qm+1,3.
(2.4.7)
Если ? > 0, то второе решение является оптимальным, если ? < 0,
то оптимальным является первое решение. Для обоснования пред-
ложенного алгоритма разобьем множество всех решений на два
подмножества. В первом подмножестве предприятие, для которого
0 < ykT < 3 имеет номер больше, чем m, а во втором подмножестве
номер такого предприятия меньше или равен m. Заметим теперь,
что первое решение является оптимальным среди всех решений
первого подмножества, а второе является оптимальным среди всех
решений второго подмножества. Этот вывод следует из утвержде-
ний (2.1) и (2.2). Для первого подмножества это очевидно. Рассмот-


27
рим более детально обоснование алгоритма для второго подмноже-
ства.
Если l - номер предприятия с нормативным уровнем 0 < ylT < 3, и
l ? m, то в силу утверждения (2.2) первые (m+1) предприятий за
исключением l-го имеют в оптимальном решении максимальную
величину нормативного уровня, то есть yiT = 3 для i = 1, m + 1 , i ? l.
В этом случае
m +1
? Q k ,3 ? (Q l,3 ? Q ls ) .
Q2 =
k =1
Очевидно, для того, чтобы Q2 была минимальной, следует
выбрать l, для которого разность (Ql3 – Qls) максимальна, что и дает
второе решение.
Пример 2.3. Значение Qkj для шести предприятий приведены
в таблице 2.5.
Таблица 2.5.
k
1 2 3 4 5 6
j
9 12 9 10 7 9
1
14 17 16 17 19 19
2
17 19 20 21 21 22
3
Возьмем RT = 11 = 3?3 + 2, то есть m = 3, s = 2.
Имеем для первого подмножества min Qi 2 = min (17, 19, 19)
4 ?i ? 6
= 17 = Q42. Следовательно, Q1 = Q13 + Q23 + Q33 + Q42 = 73.
Для второго подмножества имеем max (Qi3 ? Qi 2 ) = max (3, 2,
1? i ?3
4) = 4 = Q33 - Q32. Следовательно, Q2 = Q13 + Q23 + Q32 + Q43 = 77.
Так как Q2 > Q1, то оптимальное решение имеет вид:
y1T = 3, y2T = 3, y3T = 3, y4T = 2, y5T = y6T = 0.

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

Пусть часть функций Qk(ykT) являются выпуклыми, а часть –
вогнутыми. В этом случае задача решается в два этапа. На первом
этапе решается задача только для множества предприятий с вогну-
тыми функциями Qk(ykT) при различных значениях R = 1, R T . Пусть
Н – множество предприятий с вогнутыми зависимостями. Обозна-
чим QН(R) – зависимость минимальной величины суммарного
ущерба от уровня R. Заметим, что эта функция не является, как
правило, ни выпуклой, ни вогнутой.
На втором этапе решается задача для предприятий с выпук-
лыми зависимостями Qk(ykT) и одним обобщенным предприятием
Н, имеющим зависимость QН(R). Для решения этой задачи эффек-
тивным методом является метод ветвей и границ. В этом методе
зависимость QН(R) заменяется выпуклой оценочной функцией
Q H (R ) ? Q H (R ) , максимально близкой к QН(R). Эффективность
˜

метода определяется в данном случае тем, что невыпуклой является
только одна функция QН(R), и поэтому ветвление будет проводить-
ся только в случае, если Q H (R ) ? Q H (R ) . Рассмотрим применение
˜

метода на примере.
Пример 2.4. Возьмем три первых предприятия из примера 2.2
и три первых предприятия из примера 2.3.
I этап. Решаем задачу для трех предприятий с вогнутыми
функциями Qk(ykT), данные о которых приведены ниже.
Таблица 2.6.
k
1 2 3
j

29
9 12 9
1
14 17 16
2
17 19 20
3


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

Qн(R)
56
52
45
36
33
˜
QH ( R )
26
17
14
9
RT
1 23 4 567 8 9

Рис. 2.9.

30
Пунктиром показана функция Q H (R ) , являющаяся оценкой снизу
˜

для функции QH(R).
II этап. Пусть RT = 12. Данные о трех предприятиях с выпук-
лыми функциями Qk(ykT) приведены ниже (начальные величины Qk0
вычтены из всех Qkj).
Таблица 2.7.
k
1 2 3
j
2 2 2
1
6 7 6
2
12 14 13
3

Вычисляем таблицу первых разностей (таблица 2.8).
Таблица первых разностей функции Q H (R ) для обобщенного
˜

предприятия Н имеет вид таблицы 2.9.
Таблица 2.8.
k
1 2 3
j
2 2 2
1
4 5 4
2
6 7 7
3


Таблица 2.9.
0?R?3 3?R?6 6?R?9
R
? 52/3 61/3 62/3




31
Применяя алгоритм для случая выпуклых функций, получаем
следующее решение:
y1T = 3, y2T = 2, y3T = 3, yНT = 4.
Так как Q H (4) < QH(4), то разбиваем множество всех решений на

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

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

ОГЛАВЛЕНИЕ

Следующая >>