Книги по разным темам Pages:     | 1 | 2 | 3 | 4 | 5 |

Если > 0, то второе решение является оптимальным, если < 0, то оптимальным является первое решение. Для обоснования предложенного алгоритма разобьем множество всех решений на два подмножества. В первом подмножестве предприятие, для которого 0 < ykT < 3 имеет номер больше, чем m, а во втором подмножестве номер такого предприятия меньше или равен m. Заметим теперь, что первое решение является оптимальным среди всех решений первого подмножества, а второе является оптимальным среди всех решений второго подмножества. Этот вывод следует из утверждений (2.1) и (2.2). Для первого подмножества это очевидно. Рассмотрим более детально обоснование алгоритма для второго подмножества.

Если - номер предприятия с нормативным уровнем 0 < y T < 3, и m, то в силу утверждения (2.2) первые (m+1) предприятий за исключением -го имеют в оптимальном решении максимальную величину нормативного уровня, то есть yiT = 3 для i =1, m + 1, i.

В этом случае m+Q2 = (Q - Q ).

Q -,3 s k,k=Очевидно, для того, чтобы Q2 была минимальной, следует выбрать, для которого разность (Q 3 - Q s) максимальна, что и дает второе решение.

Пример 2.3. Значение Qkj для шести предприятий приведены в таблице 2.5.

Таблица 2.5.

k 1 2 3 4 5 j 1 9 12 9 10 7 2 14 17 16 17 19 3 17 19 20 21 21 Возьмем RT = 11 = 33 + 2, то есть m = 3, s = 2.

Имеем для первого подмножества min Qi2 = min (17, 19, 19) 4i= 17 = Q42. Следовательно, Q1 = Q13 + Q23 + Q33 + Q42 = 73.

Для второго подмножества имеем max(Qi3 - Qi2)= max (3, 2, 1i4) = 4 = Q33 - Q32. Следовательно, Q2 = Q13 + Q23 + Q32 + Q43 = 77.

Так как Q2 > Q1, то оптимальное решение имеет вид:

y1T = 3, y2T = 3, y3T = 3, y4T = 2, y5T = y6T = 0.

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

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

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

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

Таблица 2.6.

k j 1 9 12 2 14 17 3 17 19 Применяя алгоритм, описанный в разделе 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) ~ QH ( R ) RT 1 2 3 4 5 6 7 8 Рис. 2.9.

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

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

Таблица 2.7.

k j 3 12 14 Вычисляем таблицу первых разностей (таблица 2.8).

~ Таблица первых разностей функции QH(R) для обобщенного предприятия Н имеет вид таблицы 2.9.

Таблица 2.8.

k j Таблица 2.9.

R 0 R 3 3 R 6 6 R 52/3 61/3 62/Применяя алгоритм для случая выпуклых функций, получаем следующее решение:

y1T = 3, y2T = 2, y3T = 3, yНT = 4.

~ Так как QH(4) < QH(4), то разбиваем множество всех решений на два подмножества. В первом подмножестве yНT 4, а во втором yНT 4.

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

Таблица 2.10.

R 0 R 3 3 R 52/3 Теперь оптимальное решение будет иметь следующий вид:

y1T = y2T = y3T = yНT = 3, а величина упущенной выгоды равна 12 + 14 + 13 + 17 = 56.

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

Таблица 2.11.

R 4 R 6 6 R 562/Оптимальное решение для этого подмножества решений имеет вид:

y1T = 2, y2T = 2, y3T = 2, yНT = 6.

а величина упущенной выгоды равна 6 + 7 + 6 + 36 = 55.

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

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

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

Сложность решения остальных 2n1 задач растет прямопропорционально n1. Поэтому сложность решения задачи первого этапа, оцениваемая числом элементарных операций (сложение, вычитание, сравнение) растет прямопропорционально n12.

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

Опишем алгоритм построения оценочной функции. Обозначим через m = min (RT, 3n1).

I шаг. Определяем величины QH(R) q1(R)= 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-ый шаг. Определяем величины QH(R)- QH(Rk-1) qk(R)= R - Rk-для всех 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 - положительные константы.

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

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

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

II шаг. Решаем оценочную задачу, как описано в разделе 2.3.

Нетрудно доказать, что всегда существует решение оценочной задачи, в котором только не более чем для одного предприятия ~ имеет место Qk(ykT ) Qk(ykT) в оптимальном решении оценочной задачи. Из этого факта следует естественная процедура разбиения на подмножества. Если для предприятия k в оптимальном решении ~ y оценочной задачи имеет место Qk(y )< Qk(y ), то разбиваkT kT kT ем множество всех решений на два подмножества. В первом подмножестве ykT y, а во втором - ykT y.

kT kT III шаг. Оцениваем каждое подмножество, решая оценочные задачи согласно шагам I и II. Из двух подмножеств выбираем подмножество с минимальной оценкой. Если для этого подмножества в оптимальном решении оценочной задачи существует предприятие, ~ для которого Qk(y )< Qk(y ), то повторяем процедуру разбиения kT kT на подмножества, каждый раз оценивая новые подмножества и выбирая из всех полученных подмножеств то, оценка которого минимальна. Как только получено подмножество, для которого ~ нижняя оценка является точной (то есть, Qk(ykT) = Qk(ykT) для всех предприятий), задача решена.

Замечание. Если для какого либо подмножества получена задача с выпуклыми, вогнутыми или выпуклыми и вогнутыми зависимостями, то для ее решения применяются алгоритмы, описанные в разделах 2.3, 2.4, 2.5 соответственно.

Рассмотрим работу метода ветвей и границ на примере.

Пример 2.5. Рассмотрим четыре предприятия с функциями Qk(ykT), графики которых приведены на рис. 2.10 (а, б, в, г).

Пусть RT = 6.

I шаг. Строим оценочные функции (они показаны пунктиром на рис. 2.10).

II шаг. Решаем оценочную задачу. Для этого построим таблицу первых разностей (таблица 2.12).

Q1 Q8 6 y1T y2T 1 2 3 1 2 а) б) Q3 Qy3T y4T 1 2 3 1 2 а) б) Рис. 2.10.

Таблица 2.12.

k j 11 22/3 2 31/2 22/3 3 31/2 22/3 Составляем таблицу 2.13 максимальных уровней в зависимости от величины первой разности (см. таблицу 2.4).

Таблица 2.13.

k 1 2 3 4 R( ) 1 1 0 0 0 2 1 0 1 0 22/3 1 3 1 0 3 1 3 3 3 Оптимальный план (один из многих) имеет вид:

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 j 11 22/3 2 31/2 22/3 3 31/2 22/3 -Теперь оптимальное решение оценочной задачи будет другим:

y1T = 1, y2T = 3, y3T = 1, y4T = 1.

Оценка первого подмножества равна:

Q(y3T 2) = 1 + 8 + 2 + 3 = 14.

Оценка второго подмножества. Таблица первых разностей имеет вид:

Таблица 2.15.

k j 11 22/3 -2 31/2 22/3 -3 31/2 22/3 Оптимальное решение оценочной задачи:

y1T = 1, y2T = 2, y3T = 3, y4T = 0.

Оценка второго подмножества равна:

Q(y3T 2) = 1 + 51/3 + 9 = 151/3.

Выберем первое подмножество, имеющее меньшую оценку.

Так как в оптимальном решении оценочной задачи для первого под~ множества имеет место Q4(1) < Q4(1), то разбиваем его на два подмножества. В первом подмножестве y4T 1, а во втором - y4T 1.

Оценка подмножества y3T 2, y4T 1.

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

y1T = 1, y2T = 3, y3T = 1, y4T = 1.

Оценка подмножества равна Q(y3T 2, y4T 1) = 1 + 8 + 2 + 5 = 16.

Заметим, что эта оценка является точной нижней оценкой, так как ~ Qk = Qk для всех предприятий.

Оценка подмножества y3T 2, y4T 1.

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

y1T = 1, y2T = 2, y3T = 1, y4T = 2.

Оценка подмножества равна Q(y3T 2, y4T 1) = 1 + 51/3 + 2 + 6 = 141/3.

Выбираем подмножество y3T 2, y4T 1 с минимальной оценкой.

Так как в оптимальном решении оценочной задачи имеет ме~ сто Q2(2) < Q2(2), то разбиваем это подмножество на два. В одном из них y2T 2, а во втором - y2T 2.

Оценка подмножества {y2T 2, y3T 2, y4T 1}.

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

y1T = 1, y2T = 2, y3T = 1, y4T = 2.

Оценка подмножества равна Q(y2T 2, y3T 2, y4T 1) = 1 + 6 + 2 + 6 = 15, и является точной нижней оценкой.

Оценка подмножества {y2T 2, y3T 2, y4T 1}.

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

y1T = 1, y2T = 3, y3T = 0, y4T = 2.

Оценка подмножества равна Q(y2T 2, y3T 2, y4T 1) = 1 + 8 + 0 + 6 = 15, и также является точной нижней оценкой.

Окончательно получаем два оптимальных решения:

y1T = 1, y2T = 2, y3T = 1, y4T = 2, и y1T = 1, y2T = 3, y3T = 0, y4T = с величиной упущенной выгоды равной 15.

Дерево ветвлений, в вершинах которого указаны оценки снизу соответствующих подмножеств, приведено на рис. 2.11. Толстыми дугами выделены подмножества решений, в которых определены оптимальные решения.

y3T 2 y3T 14 151/y4T 1 y4T 16 141/y2T 2 y2T 15 Рис. 2.11.

2.7. Метод динамического программирования Метод динамического программирования в ряде случаев является более эффективным по сравнению с методом ветвей и границ, особенно, в случае малых n и RT.

Идея метода в том, что последовательно определяется минимальная величина упущенной выгоды для возможных значений 0 R RT, если региональный уровень R обеспечивается за счет первых двух предприятий, затем первых трех, и т.д. Обозначим через Фm(R) - минимальную величину упущенной выгоды в случае, если уровень R обеспечивается только за счет первых m предприятий. Величины Фm+1(R) определяются на основе уравнения Беллмана:

(2.7.1) Фm+1(R)= min [Фm(R - i)+ Qm+1(i)].

0i Сложность алгоритма прямопропорциональна RTn или, учитывая, что RT 3n, прямопропорциональна n2. Заметим, однако, что в методе ветвей и границ оценка n4 достигается в самом худшем случае. Средняя оценка, как показали многочисленные примеры, также имеет порядок n2. В то же время, во многих случаях метод ветвей и границ имел сложность порядка n. Рассмотрим применение метода на примере 2.5.

Значения Ф1(R), 0 R 3, приведены ниже.

Таблица 2.16.

R Ф1(R) Вычислим Ф2(R), 0 R 6. Имеем:

Ф2(0) = 0, Ф2(1) = min(Ф1(0) + Q21; Ф1(1) + Q20) = 1, Ф2(2) = min(Ф1(0) + Q22; Ф1(1) + Q21; Ф1(2) + Q20) = min(6; 6; 6) = 6, Ф2(3) = min(Ф1(0) + Q23; Ф1(1) + Q22; Ф1(2) + Q21; Ф1(3) + Q20) = = min(8; 7; 11; 8) = 7, Ф2(4) = min(Ф1(1) + Q23; Ф1(2) + Q22; Ф1(3) + Q21) = min(9; 12; 13) = 9, Ф2(5) = min(Ф1(2) + Q23; Ф1(3) + Q22) = 14, Ф2(6) = Ф1(3) + Q23 = 16.

Вычислим Ф3(R). Заметим, что так как RT = 6, то первые три предприятия должны обеспечить по крайней мере уровень не менее R = 3. Имеем:

Ф3(3) = min(Ф2(0) + Q33; Ф2(1) + Q32; Ф2(2) + Q31; Ф2(3) + Q30) = = min(9; 9; 8; 7) = 7, Ф3(4) = min(Ф2(1) + Q33; Ф2(2) + Q32; Ф2(3) + Q31; Ф2(4) + Q30) = = min(10; 14; 9; 9) = 9, Ф3(5) = min(Ф2(2) + Q33; Ф2(3) + Q32; Ф2(4) + Q31; Ф2(5) + Q30) = = min(14; 15; 11; 14) = 11, Ф3(6) = min(Ф2(3) + Q33; Ф2(4) + Q32; Ф2(5) + Q31; Ф2(6) + Q30) = = min(16; 17; 16; 16) = 16.

Наконец, вычислим Ф4(RT).

Ф4(6) = min(Ф3(3) + Q43; Ф3(4) + Q42; Ф3(5) + Q41; Ф3(6) + Q40) = = min(16; 15; 16; 16) = 15.

Естественно, мы получили те же самые оптимальные решения.

Pages:     | 1 | 2 | 3 | 4 | 5 |    Книги по разным темам