WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     | 1 |   ...   | 54 | 55 || 57 | 58 |   ...   | 82 |

Теорема 8. (Критерий пассивности). Для того, чтобы ограничение aruT cr было пассивным для (5), необходимо и достаточно существование базисной матрицы Aб, относительно которой разложение rk 0 для всех k.

Введем в рассмотрение (0), Пr = u / aruT cr Пr = u / aruT = cr (+) { } { } (-) Пr = u / aruT cr { } образованные с использованием гиперплоскости aruT = cr.

Теорема 9. ( Критерий неразрешимости за несовместностью ). Для несовместности множества (5) (U =, Ur, U = U П(-) ) необходимо и достаточно существование А и u0 таких, что r r ‡ ri 0, i = 1, m и = a uT - с > 0.

r r 0 r Доказательство теорем 8, 9 приведено в [Войналович, 1987].

242 Mathematical Foundations of AI Построим с использованием ограничения aruT cr следующие модели линейного программирования max{aruT / u U }, p (11) min{aruT / u U }, p (12) -1 -где crH ( p), crB( p), urH ( p), urB( p), ArH ( p), ArB( p) значение целевых функций, оптимальных решений, оптимальные базисные матрицы (13), (14), а (H )rk 0, k = 1, m, (H )rk 0, k = 1, m - коэффициенты разложения нормалей целевых функций по строкам соответствующих базисных матриц для (11) и (12), U, p = 1,k множество, соответствующее ограничениям на переменные (2).

p Следует отметить, что условия пассивности и неразрешимости за несовместностью существенно упрощаются для множества (2) - гиперпараллелепипеда переменных, поскольку решения задач (11) и (12) формируются непосредственно - без решения оптимизационной задачи.

m m u - u uj(B) - uj(H ) j(B) j(H ) Пусть = min ( 2 )2 -минимальный радиус сферы, вписанной в П, R = ( 2 )2 - jJ j =1 j=u1(B) + u1(H ) u2(B) + u2(H ) um(B) + um(H ) радиус сферы, описанной вокруг П с центром в точке u0(sr ) = (,,... ), 22 T aru0(sr) -cr расстояние от заданной точки u0(sr ) к r-ой гиперплоскости d =.

r ar Следствие 4. Достаточным условием существования единственного решения (1), (2) есть выполнение ( ( u0i) - u0(sr ) <, lki) 0, i = 1, m, на итерациях замещения строк (2) строками (1) Следствие 5. Необходимым и достаточным условием неразрешимости (1), (2) есть выполнение 0 cr, cr(B) хотя бы для одного r I.

cr (H ) Следствие 6. Достаточным условием существования единственного решения (1), (2) есть выполнение ( ( u0i) - u0(sr ) <, lki) 0, i = 1, m, на итерациях замещения строк (2) строками (1) Следствие 7. Необходимым и достаточным условием неразрешимости (1), (2) есть выполнение 0 cr, cr (B) хотя бы для одного r I.

cr (H ) Следствие 8. Необходимым и достаточным условием неразрешимости (1), (2) есть выполнения Rr < dr хотя бы для одного r I.

Следствие 9. Необходимым условием разрешимости (1), (2) есть выполнение cr (H ) < cr < cr(B) r I.

Следствие 10. Необходимым условием разрешимости (1), (2) есть выполнения Rr > dr r I.

Справедливость теоремы 10 и следствий 4-10 вытекает из критериев пассивности и неразрешимости (теоремы 8, 9).

Выводы Применение симплексной идеологии на основе МБМ даёт возможность:

• исследовать свойства решений СЛАР и СЛАН (1), (2) при изменениях в векторах ограничений;

• проводить анализ свойств системы при изменении значений отдельных элементов и ее компонент;

• использовать решение начальной системы при анализе возмущенной системы • контролировать или направлено изменять величину ранга системы;

XII-th International Conference "Knowledge - Dialogue - Solution" • разрабатывать механизм постадийного преобразования вырожденной матрицы ограничений в невырожденную направленной коррекцией элементов;

• находить решение квадратной системы неравенств за фиксированное количество шагов • строить начальные решения задач на основе тривиальных базисных матриц, которые исключает трудоёмкие начальные вычисления;

• применять схему анализа для задач, которые предусматривают многошаговость или многократность расчетов на моделях при изменениях в компонентах модели;.

• анализировать корректность построения модели - на наличие пассивных и порождающих неразрешимость за несовместностью компонент на стадии анализа так и на стадии решения при уточнении функции принадлежности или интервалов принадлежности параметров.

Литература [Леонтьев, 1972 ] Леонтьев В.В., Форд Д. Межотраслевой анализ воздействия структуры экономики на окружающую среду// Экономика и математические методы.- 1972.-Т.VIII,-Вып.3.-с.370-[Гасс, 1961] Гасс С. Линейное программирование. Физматгиз,-[Волошин, 1987] Волошин А.Ф. Метод локализации облаcти оптимума в задачах математичеcкого программирования // Докл. АН CCCР. - 1987. -293, N 3.- C. 549-553.

[Орловский, 1981] Орловский С.А Принятие решения при нечёткой исходной информации.- М:, Наука,-1981,- 206с.

[Волошин,1993] Волошин А.Ф. Войналович В.М., Кудин В.И. Предоптимизационые и оптимизационные схемы сокращения размерности задачи линейного програмирования // Автоматика,N4, 1993.

[Войналович, 1987] Волкович В.Л., Войналович В.М., Кудин В.И. Релакcационная cхема cтрочного cимплекc метод // Автоматика. - 1987. -N4.-C. 79-86.

[Войналович, 1988] Волкович В.Л., Войналович В.М., Кудин В.И. Релакcационная схема двойственного строчного симплекс метода // Автоматика.-1988. -N 1,c.39-46.

[Кудин, 2002] Кудин В.И. Применение метода базисных матриц при исследовании свойств линейной системы // Вестник Киевского университета. Cерия физ.-мат. науки. - 2002.-2., C. 56-61.

Информация об авторах Владимир И. Кудин – Киев, Киевский национальный университет имени Тараса Шевченко, факультет кибернетики, Украина, к.т. н., с. н.с., e-mail: V_I_Kudin@mail.ru Григорий И. Кудин – Киев, Киевский национальный университет имени Тараса Шевченко, факультет кибернетики, Украина, к.ф. -г.н., доц., e-mail: kuding@mail.univ.kiev.ua ЭВОЛЮЦИОННЫЙ МЕТОД ОПРЕДЕЛЕНИЯ КРАТЧАЙШЕГО ПУТИ ПРОЕЗДА ПОЖАРНОГО РАСЧЕТА К МЕСТУ ПОЖАРА С ОПТИМИЗИРОВАННЫМ ПРОСТРАНСТВОМ ПОИСКА Виталий Снитюк, Александр Джулай Аннотация: В статье предложен метод определения кратчайшего пути проезда пожарного автомобиля к месту пожара по критерию минимизации времени с использованием эволюционного моделирования. Исследован алгоритм его реализации на базе полного и оптимизированного пространства поиска возможных решений. Рассмотрены аспекты формирования моделей целевой функции и программной реализации метода. Выполнена экспериментальная верификация и приведены результаты сравнительного анализа с экспертными заключениями.

Ключевые слова: Неопределенность, эволюционное моделирование 244 Mathematical Foundations of AI Введение Поиск кратчайшего пути является задачей дискретной оптимизации. При этом определение оптимального пути проезда пожарного автомобиля к месту пожара имеет аспекты, которые выделяют его из общего ряда таких задач. Так, практически, это единственная задача, которая решается в критических условиях, от правильности ее решения зависят человеческие жизни. Верно выбранный маршрут - необходимое условие предотвращения техногенных и экологических катастроф. В условиях дефицита материальных и кадровых ресурсов минимизация времени проезда пожарного расчета является решающим фактором предотвращения негативных последствий пожара. Значительное количество научных исследований посвящено решению этой задачи.

Традиционно предлагают обоснования маршрута выезда пожарного автомобиля, исходя из критерия минимизации времени прибытия личного состава и пожарно-технического вооружения на место пожара. В статье [Пряничников, 1988] выполнен анализ факторов, влияющих на аварийную безопасность дорог:

ширины проезжей части, обочины, количества полос движения, радиуса кривизны, видимости, интенсивности транспортных потоков. Предложено определять коэффициент дорожных условий по формуле:

n m D = ( )Li /L, (1) k ij i=1 j= где n - количество участков маршрута, m - число факторов, определяющих дорожные условия, kij - коэффициент важности j -го фактора дорожных условий на i -м участке маршрута, Li - длина i -го участка, L - общая длина маршрута следования. Выезд пожарного расчета предполагается по маршруту, имеющему наибольшее значение D.

Во многих научных публикациях рассматриваются аналогичные подходы. Их недостатком является необходимость рассмотрения фиксированного, желательного полного набора возможных маршрутов, что практически трудно реализуемо. Не предусмотрена возможность варьирования значений важности факторов дорожных условий, что в условиях изменения дорожной обстановки, ремонта дорожного полотна, погодных условий приводит к искажению предполагаемого времени проезда. Необходима разработка адекватной модели времени проезда, как зависимости от значимых факторов, с возможностью ее уточнения и адаптации к изменяющимся внешним условиям.

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

Постановка задачи определения оптимального пути проезда пожарного автомобиля Без ограничения общности будем считать, что структура дорог является прямоугольной (рис. 1).

Пронумеруем каждый перекресток в соответствие с центрально-радиальной схемой. Местонахождение пожарного подразделения имеет нулевой номер, наиболее отдаленному “северо-восточному” перекрестку отвечает наибольший номер. Количество перекрестков - N. Рассмотренной структуре дорог отвечает матрица расстояний между перекрестками S = (sij)N-1, где sij - расстояние от i -го к j -у перекрестку. Зная i,j=среднюю скорость движения пожарного расчета, матрице расстояний можно поставить в соответствие матрицу времени проезда между перекрестками T = (tij)N-1.

i,j=Факторы, влияющие на время проезда, по форме представления их значений можно разделить на три группы: детерминированные, вероятностно-статистические и субъективные.

Минимальное количество перекрестков K на пути прохождения – детерминированный фактор, его возможные значения – натуральные числа, равные номеру квазиконцентрической окружности (см. рис. 1) и увеличивающиеся в меру отдаления перекрестка назначения от местоположения пожарного подраздела.

XII-th International Conference "Knowledge - Dialogue - Solution" Загруженность дорог U - вероятностно 27 14 5 24 статистический фактор, который характеризуется статистическим рядом распределения (табл. 1), где в верхней части таблицы находятся временные 15 6 1 12 интервалы, в нижней - относительные частоты количества автомобилей на дороге в этих 7 2 0 4 временных интервалах. Качество дорожного покрытия V является субъективным фактором и определяется функцией принадлежности, которая 17 8 3 10 может быть как непрерывной, так и дискретной. Ее построение осуществляется одним из двух 31 18 9 20 35 способов, первый из которых базируется на парных сравнениях, выполненных одним Рис. 1. Центрально-радиальная нумерация экспертом [Ротштейн, 2002], второй – на перекрестков статистической обработке мнений группы экспертов [Zadeh, 1965].

Таблица Статистический ряд Интервалы...

[t0,t1] [t1,t2] [tn-1,tn] Относительные частоты...

f1 f2 fn Предположим, что место пожара H находится между двумя перекрестками n1 и n2. Тогда необходимо определить оптимальный маршрут, что отвечает решению задачи [Снитюк, 2004]:

min{Lon + Ln H; Lon + Ln H} (2) 1 1 2 t где Lij - маршрут от i -го пункта к j -у. Исходными данными для решения задачи (2) являются значения N элементов матриц S; T; K = (kij)i=1, j=1, где ki1 - номер перекрестка назначения, ki2 - минимальное 24 количество перекрестков, которое необходимо проехать при прохождении к ki1 ; G = (gij)i=1, j=1, где gi1- номер временного интервала (сутки разбиты на 24 промежутка: с 0 часов до 1-го часа (1), с 1-го до 2-го часа (2),...), gi2 - относительные частоты количества автомобилей в gi1-м временном 24 интервале, = 1; = 1; Q = (qij)i,N, где qij (0,1) - коэффициенты, которые определяют g g j=i2 ii=1 i=качество дорожного покрытия на участке от i -го перекрестка к j -у. Заметим, что матрица G может иметь не статистическую, а субъективную природу. Если движение в одно и то же время на разных участках дороги является неравномерным, то матрица будет трехмерной, одно из измерений которой будет отвечать номеру участка дороги. В зависимости от особенностей конкретного города или ситуации, количество матриц значений факторов, влияющих на скорость движения пожарного расчета, может быть увеличено. Отметим, что содержательно сущность учета других факторов не будет отличаться от уже рассмотренных.

Предпосылки решения задачи определения оптимального пути с помощью эволюционного моделирования Особенности социально-экономического развития стран являются непосредственной причиной роста количества пожаров и, как следствие, гибели людей и нанесения имущественных убытков. Кадровый и материальный дефицит есть, с одной стороны, причиной неэффективного тушения пожаров, а с другой - стимулом к внедрению новых информационно-аналитических технологий, что позволяет повысить эффективность работы пожарных подразделений.

246 Mathematical Foundations of AI Одной из задач, требующих применения интеллектуальных моделей и методов, является минимизация времени проезда пожарного расчета к месту пожара.

Определим исходные предпосылки ее решения. Заметим, что такая задача имеет некоторые общие аспекты с известной задачей коммивояжера. Известно, что точного метода решения данной задачи любой размерности, кроме полного перебора всех вариантов, не существует. Удовлетворительные результаты дают метод ветвей и границ [Luger, 2002; Зайченко, 2000], метод последовательного анализа вариантов [Волкович, 1993], поиск оптимального пути с использованием нейронной сети Хопфилда [Уоссермен, 1992]. Однако посредством последнего метода точный результат получают, примерно, в 50% вычислений, точность первых методов зависит от размерности задачи, высоковероятным также является попадание в локальные оптимумы.

Особенностью задачи поиска оптимального пути пожарного расчета заключаются в том, что наилучшее решение ищется по критерию минимума времени. При этом необходимо учитывать количество перекрестков по пути следования, загруженность дорог (среднее количество автомобилей на дороге в единицу времени), их качество. Учет других факторов также является возможным при их особой значимости и необходимости. Отметим, что технология определения оптимального пути проезда пожарного расчета к месту пожара реализуется с учетом субъективных и статистических факторов.

Pages:     | 1 |   ...   | 54 | 55 || 57 | 58 |   ...   | 82 |



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.