ЭКОНОМИКА И МАТЕМАТИЧЕСКИЕ МЕТОДЫ, 2009, том 45, № 2, с. 113-119
ЗАМЕТКИ ^^^^^^^^^^^^^^^^ И ПИСЬМА
ОПТИМИЗАЦИЯ ПОЛЯ ДЕЙСТВИЯ КОНЕЧНОГО ЧИСЛА ИСТОЧНИКОВ В НЕПРЕРЫВНОЙ СРЕДЕ
© 2009 г. Л. Я. Клеппер
(Москва)
На языке экономических моделей в работе рассматривается задача оптимального размещения объектов инфраструктуры, создающих в совокупности территориальное "поле обслуживания" для "клиентов", находящихся в данном ареале. К настоящему времени существует значительное число эвристических методов решения подобных задач, основанных на тех или иных представлениях о характере взаимодействия размещаемых объектов и клиентов; при этом описание взаимодействия часто дается по аналогии с физическими законами или их модификациями. Так, для приближенного описания транспортных потоков использовались гравитационные и энтропийные модели (Браиловский, 1979). При решении проблемы создания новых производственных комплексов в работах (Фаерман, 1971; Фаерман, Клеппер, Вейцман, 1979) был разработан метод общего геопотенциала, который позволяет оптимизировать районы размещения комплексов. Метод основан на аналогии с физическим взаимодействием электрических зарядов.
С содержательной точки зрения в экономических моделях размещаемые объекты представляют собой "пункты обслуживания", такие как склады, магазины, ремонтные мастерские и т.п., и задача оптимального размещения состоит в том, чтобы максимально приблизить эти пункты к клиентам. Для автора данной статьи такого рода задачи представляют интерес в связи с его работами в области оптимального планирования лучевой терапии злокачественных
опухолей1. В статье рассматриваемые задачи интерпретируются в указанном контексте: в качестве поля обслуживания выступает пораженная область, все точки которого являются "клиентами", а пунктами обслуживания выступают источники облучения, помещаемые внутри пораженной области и создающие терапевтическое радиационное поле, подавляющее очаги поражения. Проблема состоит в том, чтобы распределить заданное число источников облучения наилучшим (в определенном смысле) образом.
ПОСТАНОВКА ЗАДАЧИ В ОБЩЕЙ ФОРМЕ
Пусть G — ограниченная область обслуживания в k-мерном пространстве R, точки которой обозначаются y; X — конечное множество точечных источников х (реальные значения k = 1, 2, 3). Предполагается, что область G выпуклая и X является подмножеством в G, т.е. источники располагаются внутри обслуживаемой области. Для удобства будем называть множество X — "Источником".
Воздействие каждого источника на среду характеризуется функцией действия d (r), зависящей от расстояния r > 0 между источником х и точкой среды y е G. Относительно этой функции предполагается, что она обладает следующими свойствами.
Свойство l. Функция d(r) непрерывная и строго убывает по r (т.е. d'(r) < 0), причем d(+0) = +да, d(<x>) = 0.
Свойство 2. Функция d выпуклая, т.е. d"(r) > 0.
Свойство 3. Функция d однородная отрицательной степени; это означает, что при некотором 8 > 0 выполняется соотношение d(Xr) = X~ed(r), r > 0 УХ > 0.
1 В ЦЭМИ АН СССР в 1970-е годы зародилось новое научное направление в лучевой терапии злокачественных опухолей — разработка методов оптимального дозирования. Оно было развито в большом цикле работ с участием автора (около 30 публикаций). В монографии (Swan, 1981) цикл этих исследований получил высокую оценку.
Зна4ение п0ля Перечисленными свойствами, при допол-
нительном (не ограничивающем общности) условии нормировки d (1) = 1, обладает только степенная функция
d(r) = 1/ r9, е> 0; (1)
типичные случаи 6 = 2 и 0 = 1.
Совокупный эффект действия Источника X образует поле действия D(X). По определению,
значение поля в точке y е G задается выражением
D(X,y): = £d(x - y\), У * X, (2)
xgX
где |x - У — расстояние между точками x и y. В общем виде рассматриваемая задача формулируется следующим образом: для заданного числа источников n разместить множество X таким образом, чтобы максимизировать минимальный уровень поля D(X) (предполагается, что "слипание" источников недопустимо), т.е.
m(X): = minD(X,y) ^ max, (X с G,|X| = n); (3)
yeG X
максимальное значение критерия обозначим через M.
Примечание. Во внутритканевой лучевой терапии для достижения полного терапевтического эффекта (безрецидивного излечения опухолевого заболевания) необходимо так распределить источники радиоактивного излучения в опухоли, чтобы дозовое поле D(X) было как можно более однородным. Именно это требование однородности и заложено в критерии (3). Дело в том, что в области низких уровней облучения (в области локальных минимумов поля действия) возможен рецидив заболевания и, наоборот, в области высоких доз могут возникнуть трудноизлечимые лучевые некрозы.
Замечание. Из свойства 3 вытекает, что структура оптимального размещения зависит только от формы, а не от размера области G: при ее гомотетии (сжатии или расширении подобным образом), оптимальное размещение X подвергается той же гомотетии.
1600 1400 1200 1000 800 600 400 200 0
j_I_и_г - - -I----I
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0
[0.1]
Рис. 1. Поле действия, образованное тремя источниками с четырьмя точками минимума.
ОДНОМЕРНЫЙ СЛУЧАЙ: РАЗМЕЩЕНИЕ ИСТОЧНИКОВ НА ОТРЕЗКЕ
В случае, когда область обслуживания G является отрезком вещественной прямой R, задача имеет наиболее простое решение. Этот случай интересен и сам по себе, и как "мостик" для перехода к двумерному и трехмерному случаям.
1. Предварительный анализ. В одномерном случае ключевыми являются следующие соображения.
1. При оптимальном размещении источников ни один из них не будет находиться на конце отрезка G, так как в противном случае концевой источник можно слегка сместить внутрь отрезка и увеличить тем самым величину т (X). Размещения, удовлетворяющие указанному условию, назовем допустимыми. При общем числе источников п при всяком допустимом размещении отрезок G будет разбит на п + 1 интервалов разбиения, из которых п - 1 будут внутренними, а два — концевыми (рис. 1).
2. На любом интервале разбиения А поле действия В (X) является выпуклой функцией (так как
в силу свойства 2 она есть сумма выпуклых функций); следовательно, на А точка минимума существует и является единственной. Для концевых интервалов точка минимума будет концом отрезка G, для внутренних интервалов она будет находиться строго внутри интервала (так как на концах интервала значение поля равно С учетом соображения 1 всякое допустимое размещение имеет п + 1 локальный минимум.
3. Рассмотрим (при некотором размещении источников) какой-либо из интервалов разбиения А. Обозначим минимальный уровень поля действия на этом интервале через тсоб (собственный минимум), а вне А — через тчуж (чужой минимум).
Лемма 1. Если при размещении X имеем, что тсоб Ф тчуж, то это размещение можно улучшить — повысить глобальный минимум т (X).
Доказательство . Пусть тсоб > тчуж. Тогда глобальный минимум т (X) находится вне интервала А и равен тчуж. Возможны два случая — интервал А концевой или интервал А внутренний. Расширим интервал А на некоторую величину, причем в первом случае раздвинем только внутренний конец отрезка, а во втором случае — оба (внутренних) конца. Это позволит нам понизить уровень тсоб и одновременно повысить уровень тчуж (в этом легко убедиться), и тем самым повысим глобальный минимум.
Пусть теперь тсоб < тчуж; тогда глобальный минимум совпадает с тсоб. В этой ситуации будем сужать интервал А по правилу, указанному выше. Эффект будет такой же, как и в предыдущем случае — глобальный минимум повысится.
Из леммы 1 вытекают два важных следствия.
Предложение 1 (условие оптимальности размещения X). Для того чтобы допустимое размещение X было оптимальным, необходимо, чтобы каждый локальный минимум имел один и тот же уровень. В этом случае уровень будет глобальным и равен т (X).
Доказательство . Если не все локальные минимумы равны, то существует по крайней мере один интервал А, уровень которого тсоб отличается от т (X). Согласно лемме 1, такое размещение X не оптимально.
Лемма 1 дает конструктивный алгоритм построения размещения, все локальные минимумы которого одинаковы (такое размещение назовем сбалансированным или, коротко, сб-размещением); тем самым доказано существование сб-размещения.
Предложение 2. Если размещение построено согласно указанному в лемме 1 алгоритму, то существует сбалансированное размещение (сб-размещение).
Докажем теперь, что условие сбалансированности является не только необходимым, но и достаточным для оптимальности размещения. Для этого достаточно показать, что сб-размещение единственно.
2. Единственность сбалансированного размещения. Доказательство единственности сб-размещения требует рассмотрения общей задачи, которую назовем возмущенной. Она отличается от первоначальной задачи тем, что поле действия формируется не на "чистом листе", а на некотором заданном фоновом поле; т.е. вместо (2) рассматривается поле
X, у): = Г(у) + £ х - у|), у е О, у й X, (4)
xeX
где Ш — заданная непрерывная функция на О. Ниже в процессе доказательства область О и функция Ш могут меняться; поэтому для большей четкости рассуждений исходные данные обозначим через О0 и Е0.
Предложение 3. Для произвольного отрезка О0 и заданной на нем непрерывной функции Г0 сбалансированное размещение возмущенного поля (4) существует и единственно.
Доказательство . Проведем доказательство в два этапа.
1. К возмущенному полю применима лемма 1, так как наличие фона не препятствует ходу рассуждений, использованному при ее доказательстве, то оно полностью переносится на возмущенное поле. Как и раньше, из леммы 1 следует существование сб-размещения.
2. Единственность сб-размещения докажем методом математической индукции по числу источников. Пусть п = 1; тогда при любом допустимом размещении источника существуют два интервала разбиения. Проследим, как меняются их собственные минимальные уровни при перемещении источника от левого конца отрезка О0 к правому концу. Левый уровень тсоб строго убывает от +да до некоторого конечного значения (зависящего от функции В0); правый уровень тсоб строго возрастает от начального з
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.