автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Стратегии и алгоритмы оптимального резервирования

На правах рукописи

Губин Владимир Николаевич

СТРАТЕГИИ И АЛГОРИТМЫ ОПТИМАЛЬНОГО РЕЗЕРВИРОВАНИЯ

05.13.01 — Системный анализ, управление и обработка информации (в отраслях информатики, вычислительной техники и автоматизации)

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

9 СЕН 2015

Томск-2015

005562112

Работа выполнена в федеральном государственном автономном образовательном учреждении высшего образования «Национальный исследовательский Томский государственный университет», на кафедре математического анализа

Научный руководитель: доктор физико-математических наук, профессор,

Пестов Герман Гаврилович

Официальные оппоненты:

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

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

Ведущая Федеральное государственное бюджетное образовательное

организация: учреждение высшего профессионального образования

«Томский государственный университет систем управления и радиоэлектроники»

Защита состоится 30 сентября 2015 г. в 10:30 на заседании диссертационного совета Д 212.267.12, созданного на базе федерального государственного автономного образовательного учреждения высшего образования «Национальный исследовательский Томский государственный университет», по адресу: 634050, г. Томск, пр. Ленина, 36 (учебный корпус № 2, аудитория 212Б).

С диссертацией можно ознакомиться в Научной библиотеке и на официальном сайте федерального государственного автономного образовательного учреждения высшего образования «Национальный исследовательский Томский государственный университет» www.tsu.ru.

Материалы по защите диссертации размещены на официальном сайте ТГУ:

http://^vww.ams.tsu.ru/TSU/(^laliflcationDep/coseaгchers.шf}'newpublicationn/GllbinVNЗ

0092015.html

Автореферат разослан « 10 » августа 2015 г. Ученый секретарь

диссертационного совета, Тарасенко

кандидат физико- Петр Феликсович

математических наук, доцент

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. С развитием техники появляются всё более сложные системы, поэтому возникает необходимость повышения эффективности работы различных технических устройств. В частности, на производстве необходима безупречная работа различных устройств и их составных частей. Перебои в работе аппаратуры влекут за собой большие финансовые, а иногда и человеческие потери. В связи с этим все чаще появляются задачи увеличения показателей качества того или иного устройства, таких как надежность, долговечность, ремонтопригодность и т.п. Показатели надежности являются особо важным аспектом в тех сферах жизни человека, где оборудование является дорогостоящим, труднодоступным или не подлежит ремонту. В связи с этим возникают такие задачи, как:

1) повышение надежности устройства;

2) установление закономерностей возникновения отказов;

3) разработка методов проверки надежности.

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

1) резервирование элементов, входящих в состав системы;

2) уменьшение интенсивности отказов элементов системы;

3) сокращение времени непрерывной работы системы;

4) выбор подходящего периода для проверки исправности работы системы;

5) повышение надёжности элементов, входящих в состав системы;

6) проведение профилактических мероприятий элементов системы.

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

В связи с появлением такого метода как резервирование стали появляться различные постановки задач оптимизации некоторых критериев при ограничениях на затрачиваемые ресурсы. Чаще всего задачи оптимального резервирования с ограничениями формулируются в двух видах:

• Максимизировать выбранный показатель качества системы при заданных ограничениях на общие затраты, связанные с введением резервных элементов;

• Достичь требуемого уровня показателя качества системы при минимально возможных затратах на резервные элементы.

По способу подключения элементов в теории надежности выделяют также задачи динамического резервирования. При динамическом резервировании элементы могут подключаться двумя способами:

1) когда распределение резерва проводится в каждый момент проверки в зависимости от состояния системы в этот момент времени;

2) когда распределение резерва проводится в заранее определенные моменты времени и в дальнейшем не изменяется.

Задачи первого типа представлены в работах многих советских авторов. Первые работы в этом направлении принадлежат A.C. Манделю и A.JI. Райкину1, И.Б. Герцбаху.2

1 Мандель A.C., Райкин А.Л. Составление оптимального плана включений запасных элементов // Автоматика и телемеханика. 1967. № 5. С. 55-63.

2 Герцбах И.Б. Об оптимальном управлении включением резервных элементов // Изв. АН СССР.

Техническая кибернетика. 1966. № 5. С. 75-80.

4

Затем в 70-х годах по этой тематике выходят работы В.В. Конева и А.В. Овчинникова3, Г.Г. Пестова и Л.В. Ушаковой4,5, Е.М. Никанорова и А.Л. Райкина6, В.А. Томиленко7, В.В. Конева8, И.Б. Герцбаха9, Л.В. Ушаковой10 и др.

Задачи второго типа рассмотрены в работе В.В. Конева", в книге А.Л. Райкина.12

Решение задач динамического резервирования остается актуальным, поскольку на практике используются два основных вида резервирования: нагруженное резервирование, когда все резервные элементы включены в работу, и ненагруженное резервирование, когда некоторое количество элементов находится в рабочем состоянии, остальные - в резерве; после выхода из строя одного из рабочих элементов, на его место вставляют элемент из резерва. Ясно, что второй вид резервирования с позиции использования резерва более рационален, чем первый.

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

3 Конев ВВ., Овчинников А.В. Оптимальное резервирование группы однотипных элементов // Изв. АН СССР. Техническая кибернетика. 1976. № 4. С. 75-84.

4Пестов Г.Г., Ушакова Л.В. Исследование оптимальных стратегий в задаче динамического резервирования // Изв. АН СССР. Техническая кибернетика. 1973. Л'» 5. С.76-82.

Пестов Г.Г., Ушакова Л.В. Оптимальные стратегии в задаче динамического резервирования // Изв. АН СССР. Техническая кибернетика. 1971. № 5. С. 69-72.

6 Никаноров Е.М., Райкин А.Л. Динамическое резервирование для поддержания готовности хранимых изделий // Автоматика и телемеханика. 1973. № 8. С. 138-145.

7 Томиленко В.А. Об одной задаче динамического резервирования // Изв. АН СССР. Техническая кибернетика. 1975. № 4. С. 93-100.

8 Конев В.В. Об оптимальном программном включении резервных элементов // Изв. АН СССР. Техническая кибернетика. 1975. № 3. С. 109-117.

9 Герцбах И.Б. Динамическое резервирование. Оптимальное управление включением резервных элементов // Автоматика и вычислительная техника. 1970. № 1. С. 28-34.

10 Ушакова Л.В. Об одной задаче управляемого резервирования при неодинаковых интервалах контроля // Надежность и контроль качества. 1979. .Ча 8. С. 3-12.

11 Конев В.В. Об оптимальном включении резервных элементов // Изв. АН СССР. Техническая кибернетика. 1974. К» 4. С. 75-83.

12 Райкин А.Л. Элементы теории надёжности технических систем. -М.: Советское радио, 1978.

5

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

Классическая постановка задачи динамического резервирования выглядит следующим образом. Имеется система, состоящая из одного основного элемента, параллельно которому может быть включено некоторое конечное число элементов того же типа. К моменту начала работы системы имеется г исправных элементов, среди которых один основной. Система функционирует на интервале времени (0,7). Через некоторый промежуток времени фиксированный длины А в моменты времени Н = к А, где к = 0, 1,2, ... , проводится проверка исправности включенных в работу элементов. Время на проверку и на включение новых элементов из резерва считается пренебрежимо малым и в дальнейшем не учитывается. Часть элементов, которые не включены в работу, находится в холодном резерве. Отказ элемента, включенного в работу, не влияет на исправность других элементов. Обозначим через q вероятность отказа одного элемента на интервале длиной Д, черезр = 1 -ц -вероятность безотказной работы одного элемента на этом же интервале длиной Д. Стратегия управления резервом заключается в задании целочисленной функции 1 < К (г. я) < г, которая показывает, какое количество исправных элементов необходимо включить в работу при наличии г исправных, где- вектор параметров системы. Требуется найти стратегию включения исправных элементов в моменты проверок, которая максимизирует вероятность безотказной работы системы на заданном промежутке времени (0, 7).

Для отыскания оптимальной стратегии в такой постановке задачи в работе И.Б. Герцбаха13 используется метод динамического программирования. В этой же

13 Герцбах И.Б. Об оптимальном управлении включением резервных элементов // Изв. АН СССР. Техническая кибернетика. 1966. № 5. с. 75-80.

6

работе получено достаточное условие оптимальности нулевой стратегии, согласно которой все исправные элементы включаются в работу. Этой же задачей занимались в своих работах A.C. Мандель и A.JI. Райкин14'15 Однако, в перечисленных работах большинство свойств оптимальных стратегий были получены лишь экспериментально, но не доказаны. В работах Г.Г. Пестова и JI.B. Ушаковой 1617 был расширен перечень основных свойств оптимальных стратегий на конечном промежутке, и все полученные свойства были строго доказаны. Вскоре после этого В.А. Томиленко18 получил обобщение некоторых результатов для модели резервирования с дробной кратностью.

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

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

1) выделить класс задач динамического резервирования, для которых эффективно работает сигма-оператор;

2) сформулировать и доказать общие свойства оптимальных стратегий для трех моделей динамического резервирования;

3) найти то количество резервных элементов, при котором оптимальной стратегией в системе Sm является включение в работу (от + 1) исправных элементов;

4) построить алгоритм поиска оптимальной стратегии для трех рассматриваемых моделей резервирования на основе доказанных свойств оптимальных стратегий.

14 Мандель A.C., Райкин АЛ. Составление оптимального плана включений запасных элементов // Автоматика и телемеханика. 1967. № 5. С. 55-63.

15 Райкин А.Л. Маневрирование аппаратурной избыточностью в реальных системах // Труды Ш Всесоюзного совещания по автоматическому управлению, Одесса, 1965, М., 1967. Т. 5 : Технические средства автоматики. С. 94.

16 Пестов Г.Г., Ушакова Л.В. Исследование оптимальных стратегий в задаче динамического резервирования // Изв. АН СССР. Техническая кибернетика. 1973. № 5. С.76-82.

11 Пестов Г.Г., Ушакова Л .В. Оптимальные стратегии в задаче динамического резервирования // Изв. АН СССР. Техническая кибернетика. 1971. № 5. С. 69-72.

18 Томиленко В.А. Об одной задаче динамического резервирования // Изв. АН СССР. Техническая кибернетика. 1975. № 4. С. 93-100.

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

1) Для модели резервирования с дробной кратностью, где в качестве критерия оптимизации выступает среднее время безотказной работы системы на бесконечном промежутке, в общем случае найдена область выпуклости по к функции Т(к, г) при фиксированном г,

2) Для модели резервирования на бесконечном промежутке доказано, что с увеличением резерва на единицу оптимальное количество включаемых в работу элементов может только возрасти, но не более, чем на единицу;

3) Доказано существование предела функции К „{г) при г->°о, где К „(г) -оптимальное количество элементов, которое необходимо включить в работу при наличии г исправных элементов в резерве;

4) Найдены границы интервала, как функции параметра р, на котором оптимальной стратегией является включение в работу двух исправных элементов. Решена аналогичная задача для случая резервирования с дробной кратностью;

5) Доказано, что существует такое г0, что при г >г0

а) на входе в очередной промежуток К0 - постоянства функция (о - I)2 Т(г + 2) становится положительной;

б) внутри промежутка К0- постоянства и на выходе из него функция (а - I)2 Т(г + 2) отрицательна;

6) Разработаны быстрые алгоритмы вычисления оптимальной стратегии как для конечного промежутка работы системы, так и для бесконечного.

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

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

Полученные результаты можно использовать при чтении спецкурсов по теории надежности.

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

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

Основные результаты диссертации обсуждались на научном семинаре кафедры математического анализа, а также на семинаре в ТУ СУР и докладывались на следующих конференциях:

1) XVI Международная конференция студентов, аспирантов и молодых ученых «Наука и образование», Томск, 23 — 27 апреля 2012.

2) 51 Международная научная студенческая конференция «Студент и научно-технический прогресс», Новосибирск, 12 — 18 апреля 2013.

3) XVII Международная конференция студентов, аспирантов и молодых ученых «Наука и образование», Томск, 22 - 26 апреля 2013.

4) Всероссийская конференция по математике и механике, Томск, 02 - 04 октября 2013.

5) 52 Международная научная студенческая конференция «Студент и научно-технический прогресс», Новосибирск, 11 — 18 апреля 2014.

6) XVIII Международная конференция студентов, аспирантов и молодых ученых «Наука и образование», Томск, 21-25 апреля 2014.

9

Публикации. Основные результаты, полученные в диссертации, опубликованы в 8 печатных работах, в том числе 3 статьи в журналах из перечня ВАК [1 - 3].

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

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списка литературы и четырех приложений. Общий объем диссертации составляет 105 страниц, включая 15 рисунков и 11 таблиц. Список литературы включает в себя 52 наименования.

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе приведен обзор постановок задач оптимального резервирования, сформулирована постановка задачи для трех моделей динамического резервирования.

Пусть система состоит из конечного числа параллельно включенных в смысле надежности элементов. Время в системе дискретно и может принимать значения, равные Д, 2Д, ЗД,... . В каждый из этих моментов времени производится проверка исправности всех включённых в работу элементов, и принимается решение о том, какое количество исправных элементов следует включить в работу на следующий период времени. Элементы, не включенные в работу, находятся в холодном резерве, то есть вероятность отказа элемента равна 0. Вероятность отказа включенного в работу элемента за один шаг равна у, вероятность безотказной работы - р. Отказавшие элементы не восстанавливаются. Пусть состояние системы в данный

10

момент времени полностью характеризуется набором параметров (г, s), где г -общее количество исправных элементов в данный момент времени, как включённых, так и не включённых в работу, s — некоторый конечный вектор параметров системы, задаваемый в начале работы системы. В дальнейшем исследуются системы, у которых в процессе работы вектор параметров s не изменяется. Функцию К(>\ а), принимающую целые значения и такую, что для каждого натурального г выполнено неравенство: 1 < K(r, s) < г , назовём стратегией резервирования системы. Поскольку вектор параметров s не изменяется в процессе работы системы, то в перечне аргументов различных функций будем его опускать. Например, вместо K(r, s) всюду пишем К(г). Система рассматривается на этапе нормальной работы, когда элементы не стареют.

Модель Mi. Система S,„ задана на конечном промежутке [1, и], где п — натуральное число. Система S,„ работает исправно тогда и только тогда, когда количество включённых в работу исправных элементов не меньше, чем т. Обозначим через К(г) следующую стратегию: на первом шаге в работу включено к исправных элементов, а на последующих шагах используется стратегия, оптимальная по среднему времени безотказной работы системы. В качестве критерия оценки стратегии используется среднее время исправной работы системы. Обозначим через Т(г, п) математическое ожидание времени работы системы при стратегии, оптимальной по критерию среднего времени безотказной работы системы, если в начальный момент имеется ровно г исправных элементов. Через T(k, г, и) обозначим математическое ожидание времени работы системы при стратегии К. По формуле полного математического ожидания имеем

Т{к, г, п) = X (1)

1=0

Модель М2. Система функционирует на промежутке [1, =о). Как и в модели М! вводим характеристики системы: Т(к, г) - математическое ожидание времени исправной работы системы, если в начальный момент включено в работу к элементов, а после первой проверки используется стратегия, оптимальная по среднему времени безотказной работы системы; Т(г) — математическое ожидание времени работы системы при стратегии, оптимальной по времени безотказной

11

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

к-т

Цк, г) = X С'кРк~'ч'Т(г - 0 +1. (2)

1=0

Модель М3. Пусть система функционирует на промежутке [1, и], где п -натуральное число. Обозначим Т(К, г, н) вероятность того, что система не откажет на [1, и] при стратегии К, если в начальный момент имеется г исправных элементов. Как и раньше, будем считать известной функцию F(k, Г) — вероятность такого события: в работу включено к исправных элементов, из них за один шаг отказало ровно /. Обозначим через Т(г, п) математическое ожидание времени исправной работы системы при стратегии, оптимальной по среднему времени работы системы, если в начальный момент имеется г исправных элементов. По формуле полной вероятности имеем

к-т

T(k,r,n)= X q/-y7"(r-/>-l). (3) 1=0

Требуется:

1) для каждой из трех моделей найти стратегию управления резервом, которая доставляет максимум выбранному критерию на заданном промежутке;

2) исследовать свойства оптимальных стратегий для трех введенных моделей;

3) на основе полученных свойств оптимальных стратегий построить алгоритм нахождения оптимальной стратегии для перечисленных моделей;

Очевидно, что для всех трех моделей выполнена следующая лемма. Лемма 1. Т(г) > 0 и монотонно возрастает с ростом г. Из леммы 1 и выражений (1), (2), (3) следует

Лемма 2. При фиксированном к < г функция Т(к, г) возрастает по г.

В разделе 1.3 изложен метод динамического программирования Беллмана для

задач динамического резервирования.

В разделе 1.4 рассмотрен частный случай описанной выше задачи, когда в

систему можно включить не более (к + 1) элементов, и система работает исправно,

если включено не менее к исправных элементов. Обозначим такую систему S^i.

Резерв в начальный момент также состоит из г элементов. Остальные условия

12

задачи неизменны. Пусть Т{к+\,г) - математическое ожидание времени безотказной работы системы при стратегии: на первом шаге включается в работу (к + 1) исправных элементов, а на следующем шаге переходим к стратегии, оптимальной по критерию среднего времени безотказной работы; 1\к, г) -математическое ожидание времени безотказной работы системы при стратегии: на первом шаге в работу включается к элементов, а после первой проверки используется стратегия, оптимальная по критерию среднего времени безотказной работы. Тогда имеет место следующая теорема.

Теорема 1.1. Для всех к и г, таких что к+\<г, в системе выполнено Т(к + 1,г)>Т(к,г).

Следовательно, оптимальная стратегия для модели такова: если имеется не меньше, чем (к + 1) исправных элементов, то в работу включается (к +1) элементов. Если в данный момент имеется только к исправных элементов, то все они включаются в работу.

Для системы З^н получено среднее время исправной работы системы при оптимальной стратегии в явном виде:

( (k + l)pkq] г-к Г Ьярк } 1

V 1 -Р ' (l— pk)(l — (kq + \)рк)

Показано, что при неограниченном увеличении резерва значение Т(г), монотонно возрастая, стремится к конечной величине, равной ((1- )(1 — (Aqr +1)/?* ))"'. Затем вычислено среднее время работы системы, имеющей некоторое конечное количество гнезд, и показано, что даже при сколько угодно большом резерве, величина среднего времени такой системы остается конечной величиной.

В разделе 1.5 первой главы вводится линейный оператор а на множестве функций {Т(г)}. Для каждого г > О полагаем по определению сгТ(г + \) = Г(г). С помощью а- оператора можно переписать выражение для Т(к, г) при m = 1 в виде сигма-многочлена:

T(k,r) = ^Clp^q'nr - 0 +1 = [(р + qo)k - (qo)k]T{r) + 1.

;=О

С помощью а- оператора получены некоторые вспомогательные сигма-неравенства. В конце первой главы изложены известные результаты по теме диссертации.

Во второй главе исследуются свойства оптимальных стратегий. Первый раздел посвящен исследованию поведения функции Т(к, г) относительно переменной к при фиксированном г. Следующая теорема описывает область выпуклости и промежутки возрастания и убывания функции Т(к, г).

Теорема 2.1. При р> "1 + 1 функция Т(к, г) для системы имеет не более двух т + 3

максимумов при фиксированном г, причем она выпукла вверх по к в области т<к<К"(г) + \ и не возрастает при К" (г)<к<г.

Из данной теоремы получается несколько полезных следствий. Следствие 1. Функция Т{к, г) при фиксированном г возрастает по к в области т< к < К0(г).

Следствие 2.Для любого г > 0 если Цк, г) > Т(к-1, г), ток< К0(г); если же Т(к, г) < Т(к-1, г), то к> К0(г).

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

Рисунок 1: График функции Т(к, г) прир = 0.7, т = 1 ,г= 170

Следствие 3. При т= 1 имеет место оценка

T(k +1, г) - Т(к, /•) < plq{2T{r -1) - Т(г)).

В разделе 2.2 изучаются свойства функций К0(г) и Т(г). Используя убывание

отношения критериев при оптимальной стратегии с ростом резерва в виде

Г(г + 1) Т(г)

-- <---, доказана

T(r) Т(г -1)

Теорема 2.2. К0(г) не убывает с ростом резерва.

Аналогичный результат можно получить более просто, если функция Т(г)

обладает свойством выпуклости. Из теоремы 2.2 получена следующая оценка.

Следствие 4. Существует г0, такое что при г>г0 выполнено pT\r) < Т(г — 1).

Следующая теорема говорит о том, что с ростом резерва на единицу,

оптимальная стратегия если и возрастет, то не более, чем на единицу.

Теорема 2.3. При любом г > 1 выполнено K0(r +1) < K0(r) +1.

Следовательно, из теорем 2.2 и 2.3 вытекает очевидный результат: для любого

г > 0 оптимальные стратегии удовлетворяют неравенству

Ка(г)<К0(?- + \) <К0(г) + \.

Этот результат подтверждается и по результатам численных экспериментов,

приведенных на рис. 2 в частном случае прир = 0.8 и m = 1.

Ао(г)

2 С 20 132 г

Рисунок 2: График функции Ко(г)

Определение. Назовем максимальный промежуток [/'ь г2], на котором функция К0(г) постоянна, промежутком Ко - постоянства.

Далее исследовано поведение оптимальной стратегии, когда в резерве имеется неограниченное число элементов.

Имеет место

Лемма 4. Существует lim^0(r), причем, если система допускает включение в

работу неограниченного числа элементов, то этот предел равен бесконечности.

С помощью леммы 4 доказана следующая теорема. Теорема 23. Если система допускает включение в работу сколь угодно большого количества элементов из резерва, то при г —> оо отношение T(r + 1) / Т(г) —> ].

Из теоремы 2.3 легко получаются два следствия. Следствие 5. Отношение T(r) i T(r + 1) —> 1 при г-*ж. Следствие 6. Дм любого r> k отношение T(r) / T(r -к)—> 1 при г =о.

В первом разделе третьей главы изучается знак выражения (<т — I)2 T{r +1). Так как промежуток [1, г] разбивается на непересекающиеся промежутки Ка -постоянства, возможны три случая:

1)K0(r-l)=k-l,K0(r) = k,K0(r-h 1 ) = k.

2) Ko(r- l) = k— 1, Ko(r)= k- 1, Ko(r+ 1) = k.

3) KQ(r - 1) = k, Ko(r) = k, Ko(r + 1 )=k.

Удалось показать, что начиная с некоторого г = г0, в первом и третьем случае

(o-l)2J(r + l)<0, а во втором - (сг-1)2Г(г + 1)>0. Это означает, что внутри промежутка и на выходе из него (ст-1):Г(г+1) отрицательна; при входе в очередной промежуток Àb-постоянства функция (а - l)2T(r +1) = T(r +1) - 2T(r) + Т(г -1) становится положительной.

Замечание. Из экспериментальных данных, приведенных в главе 4, можно сделать вывод о том, что внутри промежутков ^-постоянства функция Т(г) выпукла.

Лемма 5. Если функция Т(г) выпукла, то отношение убывает с ростом г.

Во втором разделе третьей главы рассматривается задача об оптимальности

включения в работу двух исправных элементов следующего вида.

Пусть имеется система Si при наличии резерва из г элементов. Через каждый

промежуток времени фиксированный длины проводятся проверки исправности

включенных в работу элементов. Требуется определить для модели условия, при

которых оптимальной стратегией является включение в работу двух элементов.

16

Иными словами, сколько должно остаться элементов в резерве для того, чтобы оптимальной стратегией до конца работы системы (если г > 1) было включение в работу двух исправных элементов.

Для данной задачи было получено ограничение на резерв в виде промежутка

2,3 +

lng(/>) In/00.

где g{p) = (1-р-р )

1+-

(/>+!);

Отсюда получаем два очевидных следствия. Следствие 7. Если г >2, то К0(г)>2.

1п g{p)

; Др) =

Ell 2 р '

Следствие 8. Если г > 3 +

in ЯР).

,то К0(г)>3.

Эта задача была обобщена на случай резервирования с дробной кратностью. Показано, что для системы Sm оптимальной стратегией является включение в работу (т + 1) исправных элементов, если г е[т + \,т + 2 + d\ где

InC (rn + X)pmq

а — целая часть выражения-; а =-г^-;

Ina 1 — р

С = -

-; Ь = -

1

q(a-a2 +С2т+1ртЧ)((а-1)Тт(т)+ЬУ " 1 -pm+l ' Соответственно, отсюда получаем

InC

Следствие 9. Если г > т + 2 +

Ina

то К0(г) > т +1.

В первом и втором разделах четвертой главы построены алгоритмы поиска оптимальной стратегии на конечном промежутке и на бесконечном промежутке.

Для моделей резервирования на конечном промежутке (М1 и М3) алгоритм строится на основе метода динамического программирования с использованием свойств оптимальных стратегий. Знание такого свойства оптимальных стратегий, как К0(г,п)<К0(г + \,п)< К0(г,п) + 1 существенно сужает область поиска оптимальной стратегии.

Алгоритм для вычисления оптимальной стратегии включения резервных элементов на бесконечном промежутке (модель М2) строится иначе, а именно, индукцией по г. На первом шаге если г = т, то Кп(т) = т. Вычисляем значение

17

Г(/и) =

l-p'

-. Далее воспользуемся соотношением (2). Выделим в правой части

равенства (2) слагаемое при / = 0. Получим уравнение

к-т

Т(к,г) = ркТ(г) + X С'крк-*с/Т(г-0+1 •

1=1

Подставим в (4) значение к = К0(г) = ко. Тогда

(4)

Г(г) =

1

fkQ-m

х с^-удг-о+1 1=1

Если в (4) подставить к = кх* К0(г), то получим неравенство

T(r) > Т(ки г) =

1

1 -р*

(ki~m

X Ск1рк^Т(г-0 + 1

ч ¿=1

Таким образом, T(r) = max

1 -р'

V i=l

, где максимум берётся по

всем натуральным к, таким, что m<k<r. Обозначим

1

( к-п,

1 -р*

\ i=l

Пусть уже вычислены АГ0(/и), K0(m + 1),..., Ko(r- 1), Т(т), Т(т + 1),..., T(r- 1). Вычислим К0(г) и Т(г). Для этого вычисляем J[Ka(r- 1), г) иД£0(г- 1) + 1, г). Если_/(£о(> -1), г) >flKo(r- 1) + 1, г), то полагаем Ka(r) = Ка(г - 1) и, соответственно, T(r) =J{Ka(r - 1), г). Если же J{Ko(r - 1) + 1, г) >fiKo(r - 1), г), то полагаем К0(г) = К0(г- 1) + 1 и Т(г) =№о(г- 1) + 1, г).

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

В заключении формулируются основные теоретические и практические результаты диссертации, полученные автором.

Благодарность. Автор выражает благодарность научному руководителю профессору кафедры математического анализа Герману Гавриловичу Пестову и участникам семинара при кафедре математического анализа за обсуждение результатов и ценные советы в процессе работы над диссертацией.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

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

1.Губин В.Н., Травкина В.В. Две задачи динамического резервирования // Вестник Томского государственного университета. Математика и механика. - 2013.

- № 5(25). - С. 5-12. - 0.42 / 0.21 пл.

2. Губин В.Н., Пестов Г.Г. Об одном классе резервируемых устройств // Вестник Томского государственного университета. Математика и механика. - 2014.

- № 4(29). - С. 14-23. - 0.6 / 0.3 пл.

3. Губин В.Н. Об оптимальном резервировании на бесконечном промежутке [Электронный ресурс] // Современные проблемы науки и образования.

- 2014. — № 4. - URL: http://www.science-education.ru/118-14484 (дата обращения: 05.09.2014).-0.37 пл.

Публикации в других научных изданиях:

4. Губин В.Н., Травкина В.В. Модели систем с управляемых резервом // XVI Международная конференция студентов, аспирантов и молодых ученых «Наука и образование» (Томск, 23-27 апреля 2012 г.): в 5 т. - Т. I: Естественные и точные науки. - Томск: Издательство ТГПУ, 2012. - С. 75-84. - 0.6 / 0.3 п.л.

5. Губин В.Н. Некоторые модели резервирования // Материалы 51-й Международной научной студенческой конференции «Студент и НТП» (Новосибирск, 12-18 апреля 2013 г.): Математика. - Новосибирск, 2013. - С. 250. -0.06 пл.

6. Губин В.Н., Пестов Г.Г. Некоторые модели резервированных устройств // XVII Международная конференция студентов, аспирантов и молодых ученых «Наука и образование» (Томск, 22-26 апреля 2013 г.): в 5 т. - Т. I: Естественные и точные науки. - Томск: Издательство ТГПУ, 2013. - С. 66-71. - 0.38 / 0.19 п.л.

7. Губин В.Н. Некоторые модификации модели Райкина-Герцбаха // Всероссийская конференция по математике и механике (Томск, 02-04 октября 2013 г.).-Томск: Иван Федоров, 2013.-С. 181-182. -0.12 п.л.

8. Губин В.Н. Некоторые теоремы о резервировании // Материалы 52-й Международной научной студенческой конференции «Студент и НТП» (Новосибирск, 11-18 апреля 2014 г.): Математика. - Новосибирск, 2014. - С. 233. -0.06 пл.

Тираж 100 экз. Заказ 562. Томский государственный университет систем управления и радиоэлектроники. 634050, г. Томск, пр. Ленина, 40. Тел. (3822) 533018.