Диссертация (Разработка методов и алгоритмов решения многомерных минимаксных задач тропической оптимизации), страница 6

Осталосьвычислить(︃−1 ⊕ =(︀ (︀−−1 ⊕ )︀* )︀−=40 −1−1(︃(︁)︃01 −1(︀)︀*= −1 ⊕ ,)︁(︃0 −1−1)︃)︃−(︃=034)︃.Применяя формулу (1.13), находим решение в виде(︃=0 −1−10)︃(︃,−3)︃(︃≤≤−334)︃.В терминах обычных операций решение принимает вид1 = max(1 , 2 − 1),2 = max(1 − 1, 2 ),при условии, что−3 ≤ 1 ≤ 3,−3 ≤ 2 ≤ 4.Для рассматриваемого примера множество допустимых значений изображено на риc.

1.3 в форме полосы между прямыми, проведенными через концывекторов *1 и *2 (столбцов матрицы * ). В этом случае множество решенийзадачи без ограничений пересекается с допустимым множеством, а минимумыобеих задач равны.Пусть в рассматриваемой задаче матрица задана следующим образом:(︃=0 −55 −4)︃.Чтобы воспользоваться формулами из теоремы 4, вычислим(︃2 =0 −550)︃,Tr() = 0 = 1,37rurrr r r r r r r r r r r r r r rrrurCOCrCrCrCrCrCCrCrCrCrCrr0rrrrrr r r r r r r r r r r r r r r6rrrrrrrrrrr r rrurrrrrrrrrrРисунок 1.4: Пример множества решений задачи с ограничениями (множестване пересекаются).условие Tr() ≤ 1 выполняется.(︃ =1 03 4(︃ =)︃ (︃0 −50 −5)︃5 −4)︃ (︃5 −41 03 4(︃5 −4=9)︃(︃=)︃,01 0)︃.6 5Снова применим формулу (1.12) для нахождения минимума .

Заметим,1/3что в слагаемых 11 , 22 , а значит и в ( − 11 )матрица не присутствует,поэтому воспользуемся их значениями из предыдущего примера. Подсчитаемнедостающие слагаемые:01 = ⊕ = * ,(︀ − 01 )︀1/2 − 01 == 5/2,(︁12 =(︃1 −1)︁(︃)︃5 09 50 −55,0)︃ (︃1)︃1tr 12 = 5.= 5,38Отсюда получаем = 5, из чего следует, что минимум увеличился. Осталосьвычислить(︃−1 ⊕ =−4 −5)︃⊕−2 −1(︀−1 ⊕ (︃)︀*)︃0 −5=5 −4(︃=0 −55(︃0 −5)︃5 −1,)︃0,после чего находим нижнюю границу вектора как(︃−1 =−4)︃.−4Верхняя граница вычисляется следующим образом:( − (−1 ⊕ )* )− = 5(︃(︁1 −1)︁(︃0 −55)︃)︃−(︃=016)︃.Решение находится по формуле (1.13) в виде(︃=0 −550)︃(︃,−4)︃−4(︃≤≤16)︃.С использованием обычных операций полученное решение записывается вформе1 = max(1 , 2 − 5),2 = max(1 + 5, 2 ),где компоненты вектора ограничены неравенствами−4 ≤ 1 ≤ 1,−4 ≤ 2 ≤ 6.Множество решений задачи изображено на рис.

1.4 в виде отрезка прямой,проведенной под углом 45∘ к координатным осям. Этот пример иллюстрируетслучай, когда допустимая область решений не пересекается с множеством решений задачи без ограничений, вследствие чего минимум в задаче возрастает.39Все вычисления в примерах настоящей главы были выполнены с использованием программ, реализованных на языке R, исходный код которых приводитсяв приложении А.40Глава 2Практическое применение методов тропической оптимизации для планированиеработ по дезактивацииРазвитие современного общества трудно представить без новых технологий,которые позволяют преобразовывать окружающий мир, дают возможность использовать недоступные ранее территории и мощные источники энергии.

Однако вместе с новыми возможностями приходит и риск возникновения чрезвычайных ситуаций антропогенной природы, а также связанных с ними проблем.Например, к серьезным проблемам [83–86] может привести авария на радиационно опасном объекте с радиоактивным загрязнением местности.Разработка плана работ по ликвидации подобной аварии представляет собойзадачу сетевого планирования. Для решения таких задач применяются детерминированные методы, такие как метод критического пути (CPM) [87, 88] идиаграммы Ганта [89, 90], либо вероятностные, например, метод оценки и пересмотра планов (PERT) [91] и метод графической оценки и анализа (GERT) [92].Задачи сетевого планирования можно сформулировать в виде задач оптимизации. Для их решения используются различные методы линейного и нелинейного программирования [93–97].

При этом зачастую подобное решение являетсяалгоритмическим и не предоставляет полного решения задачи.Одним из способов решения некоторых задач планирования производстваи сетевого планирования является применение методов тропической математики [6, 40, 50, 98]. Идемпотентная (тропическая) математика представляет собой41область математики, которая занимается изучением полуколец и полуполей сидемпотентным сложением [7,22,46]. По сравнению с методами математического программирования, которые зачастую предоставляют лишь алгоритмическое решение, для некоторых классов задач сетевого планирования применениеметодов тропической оптимизации дает возможность получить в явном видеполное решение.В настоящей главе рассматривается решение задачи планирования операциипо ликвидации последствий радиационной аварии с помощью методов идемпотентной алгебры.

Это решение получено путем применения теоремы, приведенной в предыдущей главе, которая была доказана в работе [63].Глава устроена следующим образом: сначала формулируется задача ликвидатора, которая заключается в составлении плана работ по ликвидации последствий аварии. Затем строится математическая модель, которая может бытьиспользована для решения задачи различными способами, например, методамилинейного программирования.

После этого задача формулируется в терминахидемпотентной математики, что позволяет применить для ее решения методытропической оптимизации и получить решение в явном виде. Для иллюстрацииприводится наглядный численный пример.2.1Задача ликвидатораРассмотрим следующую чрезвычайную ситуацию: предположим, что нанекоторой территории произошла авария с радиоактивным загрязнением местности. Необходимо провести обследование местности, выработать план первоочередных работ и осуществить его.Для этого в район заражения будут отправлены три группы: исследователи,проектировщики/руководители и исполнители работ. Перед началом работыкаждой группы осуществляется ее доставка к месту аварии, а после завершения работы – ее эвакуация с места аварии.

В силу некоторых обстоятельств(таких как погодные условия, наличие подходящего транспорта, опасность переоблучения населения и пр.) имеются ограничения на наиболее позднюю датувысадки, а также на наиболее раннюю возможную дату эвакуации групп послезавершения задания (для разных групп ограничения могут отличаться). При42этом высадка каждой группы может осуществляться в любой момент до установленной конечной (наиболее поздней возможной) даты высадки, а эвакуация– в любой момент после установленной начальной (наиболее ранней возможной)даты эвакуации.Для каждой группы известна продолжительность работ, которые она должна выполнить, а также зависимости между сроками выполнения этих работи сроками выполнения других работ (для начала проектирования необходимо первичное исследование; для начала работ требуется проект и уточненныеданные исследований; кроме того, у исследователей и проектировщиков естьдополнительные задачи).Изменение мощности дозы во времени не учитывается так как время работы групп в зоне значительно меньше периода полураспада, чтобы можно былоговорить о каком-либо снижении мощности дозы во времени.

В общем случае максимальное время пребывания групп в зоне радиоактивного загрязненияопределяется нормативными документами [99, 100].Необходимо запланировать операцию таким образом, чтобы минимизировать максимальное время пребывания (промежуток между высадкой и эвакуацией) всех групп в опасной зоне для минимизации полученной дозы радиациис учетом всех ограничений.Построение математической моделиПредставим задачу планирования работ по ликвидации чрезвычайной ситуации в виде некоторой задачи планирования взаимосвязанных операций с учетом необходимости переброски исполнителей до места выполнения операций иих эвакуации обратно.

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

Пусть — минимально возможная задержка между43началом операции = 1, . . . , и окончанием операции . В случае, если длякакого-то задержка не указана, положим = −∞. Для любой операции время окончания работы не может быть меньше, чем + для всех = 1, . . . , . Таким образом, время окончания каждой из работ вычисляетсякак = max(1 + 1 , . .

. , + ), = 1, . . . ,.(2.1)Ограничения «старт-старт» определяют минимальный интервал между началом выполнения двух операций. Обозначим через наименьший допустимый интервал времени между началом операции = 1, . . . , и началом операции . Тогда эта зависимость обуславливает неравенства ≥ max(1 + 1 , .

. . , + ), = 1, . . . ,.(2.2)Введем обозначения и для конечной даты высадки и начальной датыэвакуации -й группы. Обозначим через время (дату) переброски, а через – эвакуации соответствующей группы. Их можно представить в следующейформе: = min( , ) = − max(− , − ), = max( , ), = 1, . . . ,.(2.3)Тогда максимальное время пребывания в опасной зоне вычисляется какmax(1 − 1 , . . . , − ).(2.4)Запишем задачу планирования в виде задачи нахождения времени начала и времени завершения операций для каждой из групп, которые минимизируют максимальное время нахождения групп в районе заражения:minmax ( − ),1≤≤ = − max(− , − ),(︁)︁ = max max ( + ), ,1≤≤ ≥ max ( + ),1≤≤ = 1, . .