2.4. Вогнутый случай
Утверждение 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. Из условия оптимальности исходного решения следует, что должны выполняться условия (2.4.1)
-ai + bj > 0.
Положим теперь ykT = i + 1, yqT = j -1. Аналогично предыдущему случаю из условия оптимальности исходного решения получаем (2.4.2)
-a, + bi > 0.
Из условия вогнутости функций Qk(ykT) и Qq(yqT) имеем (2.4.3)
bi < ai , bj < aj . Объединяя условия (2.4.1) - (2.4.3), получаем (2.4.4)
bj > ai > bi > aj > bj,
что возможно только в одном случае, когда bj = ai = bi = aj. Однако, в этом случае решение ykT = i-1, yqT = j+1, а также решение ykT = i+1, yqT = j-1 являются оптимальными. Берем любое из этих решений, например, первое, и повторяем процедуру. Через конечное число шагов (не более двух) мы придем к решению, в котором либо ykT = 0, либо yqT = 3. Таким образом, число предприятий, для которых 0 < ykT < 3 уменьшилось на единицу. Повторяя эту операцию с другой парой предприятий, имеющих промежуточное значение ykT, мы за конеч- ное число таких повторений получим оптимальное решение, содержащее не более одного предприятия со значением 0 < ykT < 3.
Пусть предприятия пронумерованы в порядке возрастания Qk,3, то есть Q13 < Q23 < ...
ykT = 3, k = 1,m , ykT = 0, k > m.
Доказательство. Построим для функций Qk(ykT) оценочные функции:
Эти функции дают оценку снизу для функций Qk(ykT) и совпадают с ними в двух точках: ykT = 0 и ykT = 3. Рассмотрим задачу минимизации суммы оценочных функций при ограничениях
n
ZykT = 0 Это задача линейного программирования, решение которой очевидно. Нужно взять первые m предприятий с минимальными значениями Qk3. Заметим, однако, что это решение является допустимым решением для исходной задачи, поэтому оно также является оптимальным.
Таким образом, если n = 3m + s, где 0 < s < 3, то существует оптимальное решение, в котором одно, и только одно предприятие имеет значение ykT = s. Для определения этого предприятия построим 2 решения. В первом решении первые m предприятий получают максимальные нормативные уровни ykT = 3, k = 1,m . Среди остальных (n - m) предприятий выбирается предприятие p с минимальной вели-
чиной Q„s = min Qi s. Для этого предприятия ypT = s, для остальных
m m
(2.4.6) Q1 = IQk,3 + Qp,s .
k=1
Во втором решении определяется предприятие 1, такое что величина
Q 1,3 - Q 1,s = max (Qk,3 - Qk,s ). 1 m+1
Q2 = I Qk,3 + Qi,s. k=1,k
Разность величин Qj - Q2 равна
(2.4.7) 5 = Qi,3 + Qp,s - Qi,s - Qm+1,3.
Если 5 > 0, то второе решение является оптимальным, если 5 < 0, то оптимальным является первое решение. Для обоснования предложенного алгоритма разобьем множество всех решений на два подмножества. В первом подмножестве предприятие, для которого 0 < ykT < 3 имеет номер больше, чем m, а во втором подмножестве номер такого предприятия меньше или равен m. Если 1 - номер предприятия с нормативным уровнем 0 < ylT < 3, и 1 < m, то в силу утверждения (2.2) первые (m+1) предприятий за исключением 1-го имеют в оптимальном решении максимальную величину нормативного уровня, то есть yiT = 3 для i = 1,m +1, i Ф 1. В этом случае
Q2 = ZQk,3 -(Q 1,3 - Q 1s ). k=1
Очевидно, для того, чтобы Q2 была минимальной, следует выбрать 1, для которого разность (Ql3 - Q1s) максимальна, что и дает второе решение.
Пример 2.3. Значение Qkj для шести предприятий приведены в таблице 2.5.
Таблица 2.5.
\k i \
1
2
3
4
5
6
1
9
12
9
10
7
9
2
14
17
16
17
19
19
3
17
19
20
21
21
22
Возьмем RT = 11 = 3-3 + 2, то есть m = 3, s = 2.
Имеем для первого подмножества min Qi2 = min (17, 19, 19)
4 Для второго подмножества имеем max(Qj3 - Qj2) = max (3, 2,
1 y1T = 3, y2T = 3, y3T = 3, y4T = 2, y5T = y6T = 0.
Еще по теме 2.4. Вогнутый случай:
- 2.5. Выпукло-вогнутый случай
- 3.5. Дискретные функции затрат. Вогнутый случай
- 17.1 Вогнутые и квазивогнутые функции
- В случае ликвидации эти задолженности удовлетворяются в первую очередь, в случае реорганизации (главы 11 и 13) они удовлетворяются в полном объёме.
- § 3. Страхование от несчастных случаев 3.1. Общие положения добровольного страхования от несчастных случаев
- Особенности страхования от несчастных случаев и болезней 5.2.1. Обязательное страхование от рисков, связанных с несчастными случаями и болезнями
- 2.6. Общий случай
- Страхование от несчастных случаев
- Случаи выплаты пособия
- 7.2. Страхование от несчастных случаев
- 14.4. Страхование от несчастных случаев