Содержание к диссертации
Введение
Глава 1 Математические модели задачи размещения и их свойства 15
1.1 Постановка задачи размещения 15
1.2 Модель п-центров, свойства модели 18
1.3 Модель n-медиан, свойства модели 21
1.4 Метод решения задачи размещения с использованием одного из критериев 24
1.5 Нахождение субоптимальных решений 30
1.6 Многокритериальный подход к решению задачи оптимизации расположений 34
Выводы 39
Глава 2 Метод подбора метрики для оценки расстояний 40
2.1 Теоретические аспекты определения функции расстояний 40
2.2 Метод определения числа необходимых точек 42
2.3 О снятии с карты расстояний между точками 44
2.4 Алгоритм расчета метрики 45
Выводы 48
Глава 3 Бисекторы и области Вороного 49
3.1 Бисекторы и области Вороного 50
3.1.1 Центросимметричные многоугольники 50
3.1.2 Бисекторы 54
3.1.3 Области Вороного и их свойства 59
3.2 Бисекторы и области Вороного двух пар точек 61
3.2.1 Эллипсы в/р-метрике 62
3.2.2 Бисекторы и области Вороного двух пар точек 64
3.2.3 Бисекторы двух пар точек в Ц 65
3.2.4 Бисекторы пар точек в 1Р, 1<р<со. 76
3.2.5 Бисекторы для 1Р, 0<р<1 78
3.2.6 Бисекторы пар точек в 1„ 78
3.2.7 Бисекторы специальных пар точек 81
3.2.8 Свойства областей Вороного 81
Выводы 84
Глава 4 Алгоритмическое и программное обеспечение решения задачи 86
4.1 Обобщенный алгоритм решения задачи 86
4.2 Программное обеспечение решения задачи 87
4.3 Пример решения задач 89
4.3.1 Пример расчета метрик 89
4.3.2 Решение задачи для района Азино г.Казани 93
4.3.3 Решение задачи для Ново-Савиновского вместе с Московским и частью Кировского районов г. Казани 97
Выводы 101
Основные результаты, полученные в диссертации 102
Библиографический список 103
- Метод решения задачи размещения с использованием одного из критериев
- Многокритериальный подход к решению задачи оптимизации расположений
- Метод определения числа необходимых точек
- Бисекторы и области Вороного двух пар точек
Введение к работе
Задачи оптимального расположения станций обслуживания, в частности, станций скорой помощи, граничат с социальными и экономическими проблемами в сферах здравоохранения, транспортного обеспечения, в работе коммунальных служб, органов социальной защиты населения, МЧС, при размещении предприятий обработки «вредных» объектов (утилизации отходов), и др. Решение этих задач является необходимым условием для эффективной деятельности организаций. Поэтому проблемы данной области являются важными и актуальными.
Очевидно, что расположение станций скорой помощи должно обеспечивать быстрое прибытие машин скорой помощи в точки вызовов. Кроме того, необходимо учитывать и другие факторы, в частности, экономические: уменьшение расхода бензина, уменьшение среднего пробега машин, уменьшение числа станций скорой помощи для обслуживания заданных областей обслуживания и т.п.
В некоторых случаях необходимо учитывать путь как до точки вызова, так и путь доставки пациента до больницы. Таким образом будем получать различные ограничения задачи, реализующие различные условия обслуживания.
В настоящее время существуют различные направления исследования расположения станций обслуживания распределенных потребителей.
Оптимальное решение зависит от принятых критериев и ограничений. В различных случаях критерии и ограничения формулируются различным образом.
Задачи оптимизации расположения станций обслуживания можно разделить на следующие классы: оптимизация расположений станций для обслуживания конечного числа заданных потребителей при условии, что станции могут располагаться в некоторых точках заданного конечного множества. В результате эту задачу можно рассматривать как оптимизационную задачу на графе.
При такой постановке получаем так называемую дискретную модель;
оптимизация расположения станций для обслуживания конечного числа заданных потребителей при условии, что станции могут располагаться в произвольных точках некоторой заданной области. При такой постановке получаем смешанную модель;
оптимизация расположений станций для обслуживания потребителей, расположенных в произвольных точках некоторой области при условии, что станции могут располагаться в произвольных точках некоторой заданной области. При такой постановке получаем непрерывную модель. Для первого класса задач станции обслуживания могут быть расположены в вершинах графа, а расстояния измеряются по длинам дуг графа.
Для второго класса задач станция обслуживания может быть расположена в любой точке области, а потребитель располагается в заданных точках. В этом случае расстояние измеряется по вводимой метрике, например, по евклидовой или иной метрике. Для третьего класса задач как станции обслуживания, так и потребители могут быть расположены в произвольных точках заданной области. Расстояние измеряется по вводимой метрике. Первая работа по задаче расположения была исследована в 1909 году Альфредом Вебером [87], который исследовал расположение склада для обслуживания потребителей с известными координатами и потребностями в материале, хранящемся на складе. Далее Купер рассмотрел обобщение этой задачи [55]. В настоящее время существует множество работ, посвященных задаче расположения станций обслуживания. Имеются различные модели их исследования, такие как: модели л-центров {minimax модели); модели л-медиан (minisum модели); вероятностные модели; модели теории массового обслуживания; и другие.
Каждая из рассматриваемых в работе постановок задач порождает задачи нелинейной оптимизации, в частности, минимаксные и минимаксиминные. Задачи такого типа исследованы многими авторами: Демьянов В.Ф., Васильев Л.В. [14], Васильев Ф.П. [1], Федоров В.В. [43], Кларк Ф. [28], Михалевич B.C., Гупал A.M., Норкин В.И. [34, 35], Поляк Р.А. [78], Заботин Я.И. [24, 25], Коннов И.В. [30-32] и другими.
В обзоре Брандо М.Л. и Чина С.С. [50] указано более 50 различных моделей, используемых для решения задач выбора расположения станций обслуживания.
Принципиальные результаты о моделях и методах их решения представлены в работах Дрезнера 3. [57], Лов Р.Ф., Морриса Дж.Г. [72], Михалевича B.C., Трубина В.А., Шора Н.З. [35], в статьях [64, 58, 47, 54, 56, 60, 79, 62, 68, 69], см. также указанный выше обзор [50] и библиографии в [57, 35, 72]. Имеются специальные выпуски журналов, такие, как «Location Science» [64] и другие, целиком посвященные этим задачам.
Для решения дискретных задач предложены различные подходы, среди них можно отметить: метод ветвей и границ, методы динамического программирования, методы целочисленного программирования, вероятностные методы, различные эвристические методы и т.п. [1, 26]. Одни из этих методов хороши для одних моделей, но не подходят для других. Для каждой из моделей целесообразно подобрать свой алгоритм, дающий решение за наиболее короткое время.
Для непрерывных моделей, как правило, нельзя использовать методы, разработанные для дискретного случая. Здесь разработаны свои методы, например, методы недифференцируемой оптимизации [1, 36, 17, 42].
Для решения задачи оптимизации расположения станций обслуживания важно уметь находить глобальный экстремум целевых функций. Существуют различные методы нахождения глобального экстремума, см., например, работы Жиглявского А.А., Жилинскаса А.Г. [22, 23], Хорста Р., Пардалоса Р., Туи Г. [65, 66] и др. Среди различных методов глобальной оптимизации одними из важных являются методы, использующие липшицевость функции.
При введении критериев оптимизации в той или иной мере используется расстояние между обслуживающей станцией и потребителем. Вводимые расстояния зависят от многих факторов. Например, в городе из точки А до точки В не всегда можно проехать по соединяющей их прямой. Следовательно, евклидово расстояние не всегда приемлемо. Различные расстояния можно определить с помощью различных норм. Как известно, норма х элемента х из действительного Л/-мерного пространства RN удовлетворяет следующим трем условиям: х 0 для VxeRN, Х = 0 тогда и только тогда, когда х = 0; \\С • Х = \С\ \\Х\\ ДЛЯ VXeRN И CG(-CO,OO)\ х + у\\ = х + у для Vx,yGRw- неравенство треугольника. Пусть V— единичный «шар» в Ff: \/={хєЯЛ/:х 1}1 По свойствам этого «шара» выделяют круговые и блок нормы. Норма ПИ считается круговой тогда и только тогда, когда: \\яz1 + ( -я)z2\\ , (D для V zr, z2 є frV, І ФІ2\Л VA є (0,1), здесь frV- граница множества V. Блок нормы вводятся как нормы, единичный «шар» V для которых является выпуклым многогранником в RN (в R2 выпуклым многоугольником). Для блок норм в (1) нужно заменить неравенство « » на « ». В работе [86] показано, что блок нормы в R2 можно определить как: IM= Z (y/,z), (2) ./=1 где { у;, j = 1,2 т} - множество векторов, z = (х,у), у/- транспонированный вектор у;, (у/, z) - скалярное произведение. В данной работе запись (2) заменяется на эквивалентную форму: т lz= I bjd2(z,Rj), (3) ./=1 где bj - положительные числа, Rj - различные прямые, проходящие через начало координат, a d2(z, Rj) - евклидово расстояние от точки z до прямой Rj.
Известно [83], что блок нормы плотны в множестве всех норм в R . Использование блок норм во многих случаях позволяет свести задачу оптимизации расположения станций обслуживания к задаче линейного программирования. Исходя из указанного, блок нормы играют большую роль при решении задачи расположения. Поэтому в данной работе рассматриваются блок нормы, исследуются порождаемые ими бисекторы и области Вороного при заданных блок нормах.
Если в (3) допустить, что коэффициенты bj могут быть и отрицательными, то получим, что множество V, определяемое функцией Z , уже не будет выпуклым. Для подобного случая получены необходимые и достаточные условия того, что эта функция будет гипер-прямоугольной нормой, для которой выполняются первые два свойства нормы, но не выполняется неравенство треугольника. Введенные с помощью таких норм «расстояния» позволяют рассматривать задачи, в которых обходной путь лучше кратчайшего пути. Такие случаи возникают, если учитывается загруженность дорог, количество пробок на кратчайших путях.
Отметим, что в настоящее время существует ряд работ, посвященных вопросу оценки пропускной способности улично-дорожной сети. В работе [33] дан обзор методов оценки загруженности дорог и отмечено, что разными авторами предлагаются различные критерии. До настоящего времени нет общепринятой концепции определения пропускной способности дорог. Выделено несколько направлений исследований в решении задачи оценки загруженности дорог; например, использование дискретной модели, позволяющей использовать теорию графов и теорию оптимизации. В данной работе загруженность дорог не учитывается.
Как известно, /р-норма вектора х с N координатами х„ 1 i N, вводится
следующим образом:
(N \1/р
р 1. Отметим, что вместо 1р(х) часто используется запись х \\р.
Щ При р=1 эта норма называется прямоугольной (или манхэттенской), для р=2 получаем евклидову норму, а при р=х получаем чебышевскую норму: Цх) = max (х,, \х2\ xw).
Расстояния (метрики), вводимые по этим нормам, считаются соответственно прямоугольными (манхэттенскими), евклидовыми и чебышевскими. В общем случае метрика, соответствующая /р-норме,
т, считается /р-метрикой.
В литературе по оптимизации расположений метрика, вводимая по 1Р норме, обозначается как /р-метрика, см., например, работы [59, 74, 83, 86], и
как Lp-метрика - см., например, работы [70, 71, 81]. Учитывая, что обозначение «Lp-пространство» в функциональном анализе используется в ином смысле (как множество абсолютно интегрируемых функций), в данной работе будем использовать обозначение «/р-метрика».
При исследовании задач расположения станций обслуживания в
городах часто используется прямоугольная метрика. Для более точного решения этих задач Ward и Wendell [86] ввели в R2 норму, представимую в виде:
а, х , + а24ї X \U сс О, а2 0, а, + а2 0, то есть представимую как некоторую линейную комбинацию прямоугольной и чебышевской нормы. В дальнейшем было выяснено, что эта норма является частным случаем блок нормы. Таким образом была еще раз подтверждена важность блок норм. Важную роль в исследовании задач расположений играют взвешенные
/р-нормы, введенные Лов Р.Ф. и Моррисом Дж.Г. в работах [73, 74]. Указанные
нормы получаются умножением /р-норм на весовой коэффициент г, г 0.
Нормы можно также классифицировать на дифференцируемые и недифференцируемые. Установлено (см., например, [57]), что /р-нормы при р со являются дифференцируемыми почти всюду. Блок нормы не являются дифференцируемыми.
В [76] Лов Р.Ф. и Уолкер Дж.Х. показали, что взвешенные /р-нормы
более предпочтительны, чем блок нормы, так как дают более точные результаты. Таким образом, блок нормы позволяют иногда проще решать задачу, а взвешенные /р-нормы дают лучшее решение. Исходя их этого в
данной работе используются как блок нормы, так и взвешенные /р-нормы.
При исследовании задач размещения станций обслуживания большую роль играют так называемые диаграммы Вороного.
Положим, задана совокупность точек {сь с2, ..., сп] в FP и введено некоторое расстояние d(a,b) между точками а и Ь. Многогранником (многоугольником в R2) Вороного называется множество:
Vj = {хєРР: d(x,Cj) min d(x,cj)% 1 y п.
\ i n
Эти множества для евклидового расстояния ввел Г.Ф. Вороной при изучении свойств полиэдров, а также при построении квадратичных форм. Иногда эти множества называют многоугольниками (ячейками) Дирихле, многоугольниками Тиссена, ячейками Вигнера-Зейтца, а также многоугольниками близости. Совокупность многогранников (многоугольников) Вороного называется диаграммой Вороного. Для евклидовой метрики многогранник (многоугольник) Вороного образуется пересечением полуплоскостей и может быть ограниченным многогранником (многоугольником для R2) или бесконечной областью, ограниченной гиперплоскостями. При использовании прямоугольной метрики области V, также представляют собой ограниченные многогранники или бесконечные области, ограниченные гиперплоскостями. Если метрика отлична от прямоугольной и евклидовой, то V/, как правило, ограничены не плоскостями (прямыми в R2), а достаточно сложными поверхностями. Поэтому можно говорить об областях Вороного.
Построение областей Вороного является нетривиальной задачей. Имеется много работ по построению диаграмм Вороного. Так, например, в
работе [80] разработан алгоритм построения этих диаграмм для точек на плоскости (при евклидовой метрике) со сложностью 0(п\одп).
Диаграммы Вороного в R2 для метрик Ц и 1„ исследованы в работах [70,
71]. В работе [71] рассмотрены некоторые проблемы построения диаграмм Вороного для метрик 1р, р 1.
Вопрос построения диаграмм Вороного для блок норм в общем случае является неисследованным. Поэтому в данной работе исследуются бисекторы и области Вороного для произвольных блок норм.
В некоторых задачах необходимо учитывать доставку пациента в больницу, в этом случае возникает задача определения бисекторов пар точек. Эта область также является практически не исследованной. В данной работе рассматриваются бисекторы и области Вороного для множества пар точек при различных /р-метриках.
Отметим, что в работе не затрагиваются вопросы оценок сложности построения диаграмм Вороного.
В задачах расположений, как правило, оказывается, что целевые функции являются многоэкстремальными и для них необходимо отыскать глобальные экстремумы. Нахождение глобального экстремума можно обеспечить, как уже отмечено, например, для функций, удовлетворяющих условиям липшицевости. В данной работе устанавливается липшицевость целевых функций, что и позволяет решать задачу.
Как уже говорилось, в задачах расположений вводятся различные критерии. В данной работе рассматриваются модели л-центров, л-медиан и их варианты. Для одновременного учета выбранных критериев строится множество эффективных решений (эффективных по Парето).
Строится как множество Парето, так и множество эффективных решений. Кроме того, строятся окрестности эффективных решений, позволяющие выбирать решения с учетом значений обоих критериев. Построение окрестностей эффективных решений осуществляется с использованием липшицевости целевых функций. первой главе введены критерии оптимизации и рассмотрены модели л-центров и л-медиан. Выведены следующие свойства моделей: доказана липшицевость целевых функций моделей л-центров (с учетом и без учета доставки пациента в больницу) и л-медиан (без учета доставки пациента в больницу) по вектору переменных, а также по каждой из координат этого вектора при фиксированных остальных; найдены постоянные Липшица целевых функций моделей л-центров и л-медиан как по всему вектору переменных, так и по каждой их координат при фиксированных остальных. Предложены следующие методы. Нахождения глобального минимума липшицевых функций для решения задач по одному из критериев с использованием -метрики. Построения областей субоптимальных решений. Нахождения решений задач с учетом многокритериальности. Во второй главе рассмотрена постановка задачи нахождения функции, вычисляющей расстояние между двумя произвольными точками области с учетом транспортных коммуникаций. Предложена методика определения функции расстояния, состоящая из следующих двух этапов. 1). Нахождение числа расчетных точек т. 2). Определение степени адекватности полученной метрики реальным расстояниям области G. Также в главе изложен разработанный метод автоматизации процесса снятия расстояний с карты. Третья глава посвящена исследованию бисекторов и областей Вороного. Введены и указаны некоторые свойства эллипса в /р-метрике. Введены бисекторы для двух пар точек, рассмотрены бисекторы для различных расположений пар точек и различных значений р, 0 р оо. Выявлены следующие свойства бисекторов и областей Вороного. 1. Для двух пар точек в 1-і показано, как строится бисектор при различных положениях двух пар точек, приведены условия существования и 13 вид двумерных областей, найдено их количество, условия совпадения бисектора со всей плоскостью, связь между бисекторами двух точек и двух пар точек. 2. Выявлено, что в 1Р, 1 р оо бисектор состоит не из ломаных линий, как в случае 1-і, а из кривых, повторяющих в некоторой степени поведение ломаных при Ц. Если 0 р 1, то бисектор состоит из кривых, совпадающих с кривыми бисектора при 1 р оо, и кривых, близких по виду к границам двумерных бесконечных частей бисектора при р=1. В 1„ построение и виды бисекторов пар точек аналогичны случаю для Ц с разницей в том, что в этом случае используются не прямые, параллельные осям координат, как при р=1, а биссектрисы первого и второго координатных углов. Доказаны некоторые свойства областей Вороного для пар точек. 1. Объединение областей Вороного представляет собой всю рассматриваемую область обслуживания. При рИ и р оо множество VfT\ V, имеет нулевую площадь, если / / и пары точек таковы, что среди всех четырех точек имеется по крайней мере три различных точки. При р=1 и р-оо границами областей V/ являются отрезки прямых, параллельных осям координат, либо образующие угол 45° с осью абсцисс. Знание бисекторов для р 1 позволяет в некоторой степени дополнять бисекторы для р 1 и описать границы двумерных частей бисекторов для р=1. В четвертой главе приведено методическое и алгоритмическое обеспечение решения задачи оптимизации расположения станций скорой помощи. Описан программный комплекс «Решение задачи расположения», программная реализация его модулей. Кроме того, в этой главе приведены оптимальные расположения станций скорой помощи для некоторых районов г.Казани, получены значения параметров метрик для отдельных частей 14 г.Казани и всего г.Казани, а также для ряда городов Республики Татарстан: Набережные Челны, Альметьевск, Нижнекамск. Основные результаты работы опубликованы в [6-9, 11, 12, 19-21, 40, 41, 53].
Метод решения задачи размещения с использованием одного из критериев
Каждую из задач (1.1)-(1.6) можно представить как минимизацию соответствующей функции F,(f), 1 / 6, при условии: Построим минимальный прямоугольник D, содержащий множество G, и пусть стороны D параллельны осям декартовой системы координат. Можно показать, что условие (1.13) можно заменить на условие eDn, что эквивалентно условию: С/ є D, 1 / п. В разделах 1.2 и 1.3 была показана липшицевость целевых функций Fi(), F2(f), F3(f). Таким образом, рассмотренные задачи (1.1)-(1.4) являются задачами минимизации липшицевых функций на параллелепипеде. Установленное свойство позволяет использовать методы поиска глобального экстремума липшицевых функций для решения задач (1.1)-(1.4). Задачи (1.1)- (1.3) являются задачами негладкой оптимизации и для них можно использовать известные методы недифференцируемой оптимизации. Задача (1.1) при евклидовой метрике сводится к задаче покрытия области G п кругами наименьшего возможного радиуса.
В случае прямоугольной метрики задача (1.1) сводится к задаче покрытия области G л квадратами наименьшего возможного радиуса. Указанные квадраты являются «кругами» в прямоугольной метрике. В случае произвольной /р-метрики (1 р оо) получим, что задача (1.1) сводится к покрытию G п «кругами» наименьшего возможного диаметра. Существует ряд работ, посвященных задаче покрытия, см., например, [3, 10, 84, 85, 82, 63]. Для решения задачи (1.1) можно использовать алгоритм А1 из работы Галиева Ш.И. [5]: Алгоритм А1. 1. Выбираем начальное расположение станций обслуживания с„ 1 d i, т.е. вектор f. 2. На G строим области Вороного V,, 1 d i. 3. Для каждой Vj, 1d n, находим центр с/ минимального «круга», покрывающего область V,-. Точки с/ определяют вектор f . 4. Если вектор f отличается от f меньше, чем на заданную величину (в выбранной метрике), то f - решение (приближенное решение), иначе идем к п.5. 5. Полагаем с, = с/, 1 d i, и идем к п.2. Заметим, что алгоритм А1 следует из чисто геометрических рассуждений как процедура, которая на каждой итерации как минимум не увеличивает размер покрывающих фигур. Отметим также, что этот алгоритм не гарантирует нахождения глобального экстремума. Он может дать точку локального экстремума, точку перегиба и т.п. Рис. 1 иллюстрирует идею алгоритма на примере 3-х точек: сь с2, с3. При р=2 реализация шага 3 предложенного алгоритма не представляет сложности. При р=1 для реализации шага 3 необходимо ввести новые переменные и с помощью преобразований свести задачу отыскания наименьшего покрывающего квадрата к задаче линейного программирования (см. работу [12], а также [46, 49]). Задача (1.2) в случае, когда F2{f) определена по (1.3), сводится к задаче покрытия G п эллипсами (в /р-метрике) наименьшего возможного размера. В одном из фокусов эллипса будет находиться станция скорой помощи, а в другом - больница, в которую доставляется пациент. В общем случае задача (1.2) сводится к покрытию G фигурами, являющимися пересечением нескольких эллипсов указанного вида. При решении задачи (1.2), когда F2(f) определена по (1.3), можно использовать следующий алгоритм: Алгоритм А2. Выбираем начальное расположение станций обслуживания с„ 1 5SD, т.е. вектор f. Для заданных пар точек с,, Ь„ 1 7, строим области Вороного V,, 1 . Для каждой V-, находим фокус с, наименьшего эллипса, покрывающего Vj. Точки с, определяют вектор f. 4. Если вектор f отличается от f меньше, чем на заданную величину (в выбранной метрике), то f - решение (приближенное решение), иначе идем к п.5. 5.
Полагаем с, = с, , 1 L-g\, и идем к п.2. Для реализации шага 3 приведенного алгоритма необходимо решить задачу: В случае р=1 указанная задача вновь сводится к задаче линейного программирования. В общем случае ее можно решить методом ломаных, поскольку имеем дело с липшицевыми функциями с известными постоянными Липшица. Алгоритм А2 не гарантирует нахождение глобального экстремума. Отметим, что задача (1.2) для частного случая л=1 рассмотрена в [81]. Задача (1.4) при 1 р ао может быть решена градиентным методом в точках, где градиент существует. Отметим, что область G - ограниченная. Аналогично работе Дрезнера 3. [59] приближенное решение задачи (1.4) при р=1 и р=оо можно найти, заменив р=1 на р = р +є, где є- малая величина, а вместо р=оо выбрав достаточно большое значение р так, чтобы линии уровней dp (s,c) и dp{s,c) мало отличались для любых s,ce G. Отметим, что поведение линий уровней исследовано в работе Лов Р.Ф. и Морриса Дж.Г. [73]. Указанные выше подходы к решению задач (1.1)-(1.4) не гарантируют нахождения глобального экстремума. Глобальный экстремум для задач (1.1) (1.4) можно найти, используя липшицевость функций Ftifi, F2(f) и F3(f) . Для /1=1 или л=2 можно реализовать вложенные методы ломаных, т. е. решить следующую задачу
Многокритериальный подход к решению задачи оптимизации расположений
Решение задачи определения параметров метрики во многом зависит от выбранного количества расчетных точек т. Отметим, что при числе точек т число возможных расстояний между парами этих точек будет равно величине М=Ст=— -. Очевидно, что при увеличении т величина М будет резко возрастать. В связи с этим повышается трудоемкость снятия с карты реальных расстояний между произвольными точками. Поэтому необходимо знать, какое минимальное число точек т достаточно для расчета метрики. Предлагаемая в данной работе методика определения метрики состоит из двух этапов и позволяет: 1) найти число расчетных точек т; 2) определить, насколько правдоподобно полученная метрика будет оценивать реальные расстояния области G. Поскольку координаты точек выбираются случайно, то даже при фиксированном т при каждом новом случайном наборе точек из области G будем иметь различные значения параметров функции расстояний.
Поэтому необходимо априорно зафиксировать значение т и для к случайных наборов т точек определить значения параметров (а, г, р/"), (а2т, т2т, р2т), .... (акт, ткт, Рк")- В работе [2] указано, что на практике достаточно взять значение к в пределах от 10 до 20. На первом этапе необходимо с выбранной доверительной вероятностью Р-1 найти интервал Г, накрывающий найденные значения параметра (р/77, р2т, ..., Рк"), и его математическое ожидание рсрт. Зная рсрт, можно найти значения остальных параметров функции расстояний. В работе [57] приведен график зависимости средней величины параметра г от р. На основании этих данных можно вычислить искомое среднее значение параметра тсрт. Для вычисления параметра асрт в данной работе предлагается аппроксимировать зависимость а? от рГ, 1 / /с. Зная рсрт, можно вычислить значение параметра асрт. В результате получим «среднюю» метрику, соответствующую найденным параметрам (асрт, тсрт, рсрт), а также длину доверительного интервала Г.
На этом первый этап завершен. На втором этапе необходимо определить, насколько правдоподобно «средняя» метрика будет оценивать реальные расстояния области G. С этой целью для каждого из к случайных наборов т точек необходимо оценить, насколько существенно отличается метрика (а?, г?, рГ), 1 / /f, рассчитанная по / -му набору точек, от «средней» метрики (acpm, тсрт, рсрт). Для этого формируются и проверяются к гипотез о существенности различий /-ой метрики со «средней» метрикой: Н, s (Различие отклонений реальных расстояний Bjt от расстояний, рассчитанных по метрикам (а?, т?, рГ) и {асрт, тсрт, рсрт), несущественно), 1 / /с, где; и ґ- номера точек.
Для проверки гипотез Hj, 1 / /(, в данной работе используется критерий согласия Смирнова, его использование см., например, в работе [29]. Задав доверительную вероятность р2, после проверки всех к гипотез НІ обозначим через с количество принятых гипотез. Таким образом, будем иметь с метрик (а, тГ, рГ), несущественно отличающихся от «средней» метрики (асрт, тсрт, Рсрт) с доверительной вероятностью /?2. Далее необходимо вычислить долю г метрик, несущественно отличающихся от «средней»: Если длина у полученного на первом этапе доверительного интервала Г удовлетворяет заданной точности %рит и доля г не меньше заданной величины Гкрит, то можно считать, что с выбранной доверительной вероятностью р2 «средняя» метрика с параметрами (а, г, р) = (асрт, тсрт, рсрт) может быть использована как истинная для области G. Функция расстояний примет вид (2.1), где (ха,Уа) и (xb,yb) - координаты произвольных точек а и Ь области G в системе координат, повернутой на угол а. В противном случае можно сделать вывод, что топология рассматриваемой области G неоднородна, и данное количество расчетных точек /?7 не может дать метрики, правдоподобно описывающей реальные расстояния. Необходимо увеличить число расчетных точек т и повторить вычисления.
Метод определения числа необходимых точек
Очевидно, что расположение станций скорой помощи должно обеспечивать быстрое прибытие машин скорой помощи в точки вызовов. Кроме того, необходимо учитывать и другие факторы, в частности, экономические: уменьшение расхода бензина, уменьшение среднего пробега машин, уменьшение числа станций скорой помощи для обслуживания заданных областей обслуживания и т.п. В некоторых случаях необходимо учитывать путь как до точки вызова, так и путь доставки пациента до больницы. Таким образом будем получать различные ограничения задачи, реализующие различные условия обслуживания. В настоящее время существуют различные направления исследования расположения станций обслуживания распределенных потребителей. Оптимальное решение зависит от принятых критериев и ограничений. В различных случаях критерии и ограничения формулируются различным образом. Задачи оптимизации расположения станций обслуживания можно разделить на следующие классы: оптимизация расположений станций для обслуживания конечного числа заданных потребителей при условии, что станции могут располагаться в некоторых точках заданного конечного множества.
В результате эту задачу можно рассматривать как оптимизационную задачу на графе. При такой постановке получаем так называемую дискретную модель; оптимизация расположения станций для обслуживания конечного числа заданных потребителей при условии, что станции могут располагаться в произвольных точках некоторой заданной области. При такой постановке получаем смешанную модель; оптимизация расположений станций для обслуживания потребителей, расположенных в произвольных точках некоторой области при условии, что станции могут располагаться в произвольных точках некоторой заданной области. При такой постановке получаем непрерывную модель. Для первого класса задач станции обслуживания могут быть расположены в вершинах графа, а расстояния измеряются по длинам дуг графа. Для второго класса задач станция обслуживания может быть расположена в любой точке области, а потребитель располагается в заданных точках. В этом случае расстояние измеряется по вводимой метрике, например, по евклидовой или иной метрике. Для третьего класса задач как станции обслуживания, так и потребители могут быть расположены в произвольных точках заданной области. Расстояние измеряется по вводимой метрике. Первая работа по задаче расположения была исследована в 1909 году Альфредом Вебером [87], который исследовал расположение склада для обслуживания потребителей с известными координатами и потребностями в материале, хранящемся на складе. Далее Купер рассмотрел обобщение этой задачи [55]. В настоящее время существует множество работ, посвященных задаче расположения станций обслуживания. Имеются различные модели их исследования, такие как: модели л-центров {minimax модели); модели л-медиан (minisum модели); вероятностные модели; модели теории массового обслуживания; и другие. Каждая из рассматриваемых в работе постановок задач порождает задачи нелинейной оптимизации, в частности, минимаксные и минимаксиминные. Задачи такого типа исследованы многими авторами: Демьянов В.Ф., Васильев Л.В. [14], Васильев Ф.П. [1], Федоров В.В. [43], Кларк Ф. [28], Михалевич B.C., Гупал A.M., Норкин В.И. [34, 35], Поляк Р.А. [78], Заботин Я.И. [24, 25], Коннов И.В. [30-32] и другими. В обзоре Брандо М.Л. и Чина С.С. [50] указано более 50 различных моделей, используемых для решения задач выбора расположения станций обслуживания. Принципиальные результаты о моделях и методах их решения представлены в работах Дрезнера 3. [57], Лов Р.Ф., Морриса Дж.Г. [72], Михалевича B.C., Трубина В.А., Шора Н.З. [35], в статьях [64, 58, 47, 54, 56, 60, 79, 62, 68, 69], см. также указанный выше обзор [50] и библиографии в [57, 35, 72]. Имеются специальные выпуски журналов, такие, как «Location Science» [64] и другие, целиком посвященные этим задачам. Для решения дискретных задач предложены различные подходы, среди них можно отметить: метод ветвей и границ, методы динамического программирования, методы целочисленного программирования, вероятностные методы, различные эвристические методы и т.п. [1, 26]. Одни из этих методов хороши для одних моделей, но не подходят для других. Для каждой из моделей целесообразно подобрать свой алгоритм, дающий решение за наиболее короткое время. Для непрерывных моделей, как правило, нельзя использовать методы, разработанные для дискретного случая. Здесь разработаны свои методы, например, методы недифференцируемой оптимизации [1, 36, 17, 42]. Для решения задачи оптимизации расположения станций обслуживания важно уметь находить глобальный экстремум целевых функций. Существуют различные методы нахождения глобального экстремума, см., например, работы Жиглявского А.А., Жилинскаса А.Г. [22, 23], Хорста Р., Пардалоса Р., Туи Г. [65, 66] и др. Среди различных методов глобальной оптимизации одними из важных являются методы, использующие липшицевость функции.
Бисекторы и области Вороного двух пар точек
Как уже указано, бисектором Вр двух точек а \л b плоскости Р считается геометрическое место точек s, seP, равноудаленных от а и b в метрике 1Р, Бисектором Вр двух пар точек {(flb fi2), \ 2) называется геометрическое место точек s плоскости Р, сумма расстояний от которых до точек fu и f12 равна сумме расстояний от s до f21 и до f22, т.е.: Вр = {sєР: dp (s, fu) + dp (s, f12) = dp (s, f21) + dp (s, f22)}. (3.10) Пусть задано множество пар точек {(fi1t fi2), \ п]. Областью Вороного V, пары точек (fa, fi2) называется геометрическое место точек s плоскости Р, сумма расстояний от которых до fu и до f,2 не превосходит любой суммы расстояний до fy и до fj2, 1 п,/ /, т.е.: Отметим, что бисектор является границей двух соседних областей V-, и Vk, разделяет их (если они разделяются). Область Вороного V, состоит из тех точек s эллипса с фокусами ft1 и fi2, которые расположены не дальше (по сумме расстояний до фокусов) к своим фокусам, чем к фокусам соседних эллипсов. Для случая р=2 (евклидовой метрики) известны результаты по введенным бисекторам Вр пар точек и областям Вороного, см., например, [61]. Для р=1 некоторые результаты получены в [13, 3] и носят несистематический характер. Рассмотрим бисекторы и области Вороного для пар точек более подробно и при различных значениях р. Ясно, что, если выяснить, как построить бисектор, то тем самым можно построить и области Вороного. Поэтому уделим достаточное внимание именно бисекторам. Отметим, что в данной работе не рассматриваются вопросы сложности алгоритмов построения областей Вороного. Рассмотрим случай р=1.
Положим, что заданы пары точек {fu, f12) и (f21, f22). Бисекторы для некоторых возможных положений этих пар точек приведены в [3]. При этом бисектор может быть ломаной или состоять из ломаных и двумерных областей [3]. Пусть даны пары точек (fu, f12) и (f2i, І22), и пусть В? - бисектор этих пар. Всюду в дальнейшем считаем, что указанные пары таковы, что среди точек fu, fi2, hi и h2 хотя бы три точки различные. Рассмотрим возможные положения точек f11t f12, hu h2 и получающиеся при этом бисекторы пар точек (f11t fi2) и (hi, Ы Если все точки f11t f12, hi и f22 лежат на одной прямой L, параллельной оси ох либо оси оу, то: 1) когда отрезки [f11t f12] и [hi, h2] не вложены один в другой, то при условии, что длины их различны, либо одинаковы, но отрезки не пересекаются, бисектором В-І является прямая I, перпендикулярная L; если же длины их равны и отрезки пересекаются, то бисектором будет бесконечная полоса, ограниченная теми концами отрезков, что принадлежат пересечению; 2) пусть отрезки [f11t f12] и [f2i, h2] вложены один в другой, например, [hi, /] содержится в [f11t f12], и положим, что L параллельна ох, а хи х12.
Если середины указанных отрезков расположены в одной точке (совпадают), то бисектор В-1 состоит из двух двумерных бесконечных областей Z-i и Z2, Zi={(x y): x2Xii}, z2={(x,y): x X12}. Если расположения середин указанных отрезков не совпадают, то бисектор В1 является прямой I, перпендикулярной к L; 3) случай, когда L параллельна оси оу, будет аналогичен. Далее рассмотрим случай, когда точки f11t f12, hi и f22 не лежат на одной прямой, параллельной оси ох либо оси оу. Построим минимальный прямоугольник R-I2, содержащий все точки f11t f12, hi и f22, стороны которого параллельны осям ох и оу. Также построим минимальные прямоугольники R1t содержащий точки f« и f12, и R2, содержащий точки hi и f22, стороны этих прямоугольников также пусть будут параллельны осям ох и оу. Обозначим через Р, периметр прямоугольника Rit /=1,2. Если прямоугольник R вырождается в отрезок [а,Ь], то периметр R полагаем равным удвоенной длине отрезка [а,Ь].
