Электронная библиотека диссертаций и авторефератов России
dslib.net
Библиотека диссертаций
Навигация
Каталог диссертаций России
Англоязычные диссертации
Диссертации бесплатно
Предстоящие защиты
Рецензии на автореферат
Отчисления авторам
Мой кабинет
Заказы: забрать, оплатить
Мой личный счет
Мой профиль
Мой авторский профиль
Подписки на рассылки



расширенный поиск

Моделирование организации работ ремонтных бригад на скважинах в условиях неопределенности и риска Мамчистова, Елена Ивановна

Моделирование организации работ ремонтных бригад на скважинах в условиях неопределенности и риска
<
Моделирование организации работ ремонтных бригад на скважинах в условиях неопределенности и риска Моделирование организации работ ремонтных бригад на скважинах в условиях неопределенности и риска Моделирование организации работ ремонтных бригад на скважинах в условиях неопределенности и риска Моделирование организации работ ремонтных бригад на скважинах в условиях неопределенности и риска Моделирование организации работ ремонтных бригад на скважинах в условиях неопределенности и риска Моделирование организации работ ремонтных бригад на скважинах в условиях неопределенности и риска Моделирование организации работ ремонтных бригад на скважинах в условиях неопределенности и риска Моделирование организации работ ремонтных бригад на скважинах в условиях неопределенности и риска Моделирование организации работ ремонтных бригад на скважинах в условиях неопределенности и риска
>

Диссертация - 480 руб., доставка 10 минут, круглосуточно, без выходных и праздников

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Мамчистова, Елена Ивановна Моделирование организации работ ремонтных бригад на скважинах в условиях неопределенности и риска : диссертация ... кандидата технических наук : 05.13.01 Тюмень, 2006

Содержание к диссертации

Введение

РАЗДЕЛ 1. Краткий анализ работ в области организации ремонтных работ на скважинах 7

1.1. Анализ эффективности эксплуатации фонда нефтяных скважин в осложненных условиях 7

1.2. Анализ данных деятельности нефтяной компании «Сибнефть- Ноябрьскнефтегаз» 13

1.3. Анализ деятельности ОАО «Нижневартовскнефтегаз» 21

1.4. Анализ деятельности ОАО «Тюменьнефтегаз» 30

Цели и задачи исследований 33

РАЗДЕЛ 2. Моделирование затрат и потери от добычи нефти от простоев скважин в условиях неопределенности и риска 34

2.1. Использование методов теории массового обслуживания при принятии решений в условиях неопределенности и риска 34

2.2. Имитационное моделирование при организации ремонтных работ на скважинах 36

2.3. Динамическая модель управления техническим состоянием нефтепромыслового оборудования 41

2.4. Ситуационное управление производственно-технологическими процессами 45

2.5. Исследование затрат и потерь добычи от простоев скважин при организации ремонтных работ 56

Выводы по разделу 71

РАЗДЕЛ 3. Теоретические основы и алгоритмы решения задачи об организации ремонтных работ на скважинах 72

3.1. Прямо-двойственные алгоритмы для задач о максимальном потоке и кратчайшем пути 73

3.2. Прямо-двойственные алгоритмы для задачи о потоке минимальной стоимости 77

3.3. Численное моделирование и интерпретация полученных данных... 83

3.4. Методика организации аварийно-плановых ремонтов на скважинах 86

Выводы по разделу 111

РАЗДЕЛ 4. Алгоритмы решения задачи об организации ремонтных работ на скважинах с использованием задачи о парасочетании 113

4.1. Постановка задачи о паросочетании 118

4.2. Алгоритм для построения взвешенного паросочетания 119

4.3. Моделирование задачи организации ремонтных работ на скважинах методом взвешенного паросочетания 130

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

Выводы по разделу 148

Основные выводы и рекомендации 150

Список использованной литературы 151

Приложение

Введение к работе

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

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

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

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

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

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

Основные задачи исследований.

  1. Провести анализ эффективности работы добывающего фонда нефтяных скважин и работы ремонтных бригад на скважинах в осложненных условиях разработки нефтяных месторождений.

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

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

  4. Провести оптимизацию распределения заявок с помощью прямо-двойственного алгоритма Хичкока - АЛЬФАБЕТА.

  5. Провести анализ затрат и прибыли при организации ремонтных работ на скважинах, рассчитанных по методам принятия решений в условиях неопределенности и риска, взвешенного паросочетания и алгоритма Дейкстры, с применением системы аварийно-плановых ТОР, учетом количества ремонтных бригад и их простоев.

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

Научная новизна работы.

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

  2. Алгоритм Дейкстры дополнен критериями (дебит, коэффициент технической готовности) при планировании транспортных путей для работы ремонтных бригад на скважинах.

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

Основные защищаемые положения.

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

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

Практическая ценность работы.

  1. Пакет прикладных программ для решения задач об организации ремонтных работ на скважинах, написанных на языке «Object Pascal» в системе программирования «Delphi 7.0».

  2. Методика выбора стратегии организации ремонтных работ с учетом критериев (дебит, коэффициент технической готовности, кратчайшее расстояние).

  3. Учет простоев бригад и скважин, выявлены зависимости прибыли и затрат от количества ремонтных бригад, времени межремонтного периода.

Апробация работы. Основные результаты диссертационной работы докладывались: на научно-практической конференции «Наука и производство: параметры взаимодействия» (17 -18 апреля 2003 г., г. Сургут, ХМАО), международной научно-технической конференции «Нефть и газ Западной Сибири», г. Тюмень, 25 - 27 октября 2005г., научно-методических семинарах кафедры «Моделирование и управление процессами нефтегазодобычи» ТюмГНГУ, г. Тюмень, 2003-2005гг.

Публикации. По теме диссертации опубликовано 8 научных статей.

Структура и объем работы. Диссертационная работа состоит из введения, четырех разделов, основных выводов и рекомендаций, 1 приложения, списка использованной литературы, включающего 92 наименования. Работа изложена на 158 страницах машинописного текста, включая 101 рисунок, 44 таблицы.

Автор выражает благодарность научному руководителю д.т.н., профессору Р.Я. Кучумову и научному консультанту к.т.н., профессору P.P. Кучумову за научную и методическую помощь, оказанную при выполнении диссертационной работы.

Анализ эффективности эксплуатации фонда нефтяных скважин в осложненных условиях

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

В табл. 1.1 и 1.2 приведен фонд нефтяных скважин по 3 крупным нефтяным компаниям. Из табл. 1.1 видно, что в 1996 г. простаивающий фонд скважин колебался от 27,5% до 42,4% от эксплуатационного фонда скважин. Наибольшее количество простаивающих скважин имеет Тюменская нефтяная компания - 42,4% от всего эксплуатационного фонда. Наиболее благополучной компанией из рассматриваемых является ЛУКОЙЛ, у которой этот показатель не превышает 20% [30, 77].

Анализ табл. 1.2 показывает, что в 1997 г. наиболее благополучными остались нефтяные компании ЛУКОЙЛ - 18,7 и Роснефть - 24,1% простаивающего фонда.

В табл. 1.3 приведены сводные данные о скважинах, простаивающих в ожидании комплексного ремонта к 1996 г. Из таблицы следует, что количество скважин, простаивающих по причине отсутствия электроснабжения, колеблется от 6,6% (Тюменская НК) до 29%.

Годовые потери по причине отсутствия энергоснабжения на одну скважину составляют: Тюменская нефтяная компания - 32,9 тонн, ЛУКОЙЛ -44,1 тонн, Сибнефть - 35 тонн, Роснефть - 20,5 тонн.

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

В последние годы в нефтедобывающих предприятиях России эксплуатировалось 52 228 скважин, оборудованных установками ЭЦН, в том числе: погружными центробежными насосами - 49 030 (табл. 1.4), диафрагменными насосами - 532, винтовыми насосами - 780, импортными УЭЦН - 1886. С помощью УЭЦН было добыто 208,123 млн. т нефти 1291,708 млн. м3 жидкости.

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

Анализ данных деятельности нефтяной компании «Сибнефть- Ноябрьскнефтегаз»

Анализ и разработка мероприятий по повышению эффективности работы бригад подземного ремонта скважин в осложненных условиях. На современном этапе развития нефтяной отрасли большинство крупных месторождений Западной Сибири находятся на поздней стадии разработки и требуют повышения эффективности использования фонда скважин, а также введения большого объема геолого-технических мероприятий с целью интенсификации добычи нефти. Эти мероприятия проводятся при эксплуатации добывающих скважин в условиях, осложненных процессами отложения солей, кустования наклонно-направленных скважин, повышенной депрессии на пласт. При эксплуатации скважин усиливаются коррозионные процессы в связи с появлением в продукции сероводорода и увеличением ее обводнённости. Кроме того, очень высоким остается фонд бездействующих и простаивающих скважин, достигая в некоторых нефтяных компаниях до 40-60%. Все это диктует принятие неотложных мер по повышению эффективности использования фонда добывающих скважин.

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

Работы по ремонту скважин выполняет цех подземного ремонта скважин. В табл. 1.6 представлен анализ работы бригад текущего ремонта скважин ОАО «Сибнефть-Ноябрьскнефтегаз».

Как видно из табл. 1.6, число бригад в 1998 году уменьшилось на 4 бригады. При этом среднедействующее количество бригад увеличилось на 2% за счет увеличения сменности бригад. Коэффициент сменности увеличился с 2,79 до 2,85, то есть на 2,15%. Поэтому в целях дальнейшего совершенствования организации ремонта скважин следует установить для большинства бригад непрерывный круглосуточный график работы.

Выработка на одну бригаду в 1998 г. уменьшилась на 6,3% по сравнению с 1997 г. Это возникло за счет низкой производительности труда в НГДУ "Холмогорнефть" ("ХН"), "Заполярнефть" ("ЗН") и "Суторминскнефть" ("СИ"). Например, выработка на одну бригаду в НГДУ "ХН" уменьшилась на 13,5%, а в НГДУ "ЗН" - на 25,2%. При этом по «Сибнефть-Ноябрьскнефтегаз» стоимость одного бригадо-часа увеличилась на 7,5% за счет показателей НГДУ "ЗН" и "СН". Наилучшие результаты достигли бригады ПРС НГДУ "Муравленковскнефть" ("МН"), где наблюдается уменьшение стоимости бригадо-часа на 24,6% в 1998 г.

В табл. 1.7 представлен объем работ по текущим ремонтам скважин, выполненный в «Сибнефть-Ноябрьскнефтегаз» за 1997-98 гг.

Из табл. 1.7 видно, что наблюдается уменьшение на 331 ремонтов в 1998 г. Увеличение ремонтов отмечено по фонтанным скважинам на 20,5%. На 8,3% уменьшилось количество ремонтов в скважинах, оборудованных ЭЦН. Очевидно, уменьшение объема ремонтных работ в 1995 г. связано с уменьшением производительности труда бригад ПРС, а именно с уменьшением выработки на бригаду и увеличением непроизводительного времени до 11,8%.

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

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

Как известно, недостаток ремонтных бригад или их несвоевременное обслуживание может привести к простою скважин и убыткам. Ремонт скважин бригадами рассматривается как многоканальная система массового обслуживания (рис. 2.1), в которой потоком требований на обслуживание является поток заявок на ремонт. Процедура обслуживания состоит в выделении ремонтной бригады по заявке. Заявка считается обслуженной по окончании работы данной бригады на объекте. Дисциплиной очереди является удовлетворение заявок в порядке их поступления. Заявка, заставшая все бригады занятыми, остается в системе до момента ее удовлетворения [58, 73].

При решении задачи предполагается, что в системе имеются N ремонтных бригад (абсолютно надежные каналы обслуживания). Спрос на ремонтные

бригады характеризуется потоком заявок от отдельных скважин, требующих выполнение j-ro вида работ. Интенсивность потока заявок на ремонтную бригаду от і-ой скважины, требующей выполнение j-ro вида работ (среднее количество заявок в единицу времени), составляет величину Х[у Продолжительность работ бригады на і-й скважине, требующей j-й вид работ, составляет Ц дней. Предполагается, что ty - случайная величина, имеющая тот или иной закон распределения. Введем также величину // = — - интенсивность обслуживания и заявок, где Ту - средняя продолжительность использования бригады на объекте.

Условием существования стационарного режима работы системы массового обслуживания (когда очередь заявок на обслуживание стабилизируется) является

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

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

Имитационное моделирование - это вычислительная процедура, которая не требует приводить модель к конкретному виду. Оно позволяет моделировать работу систем с разными законами распределения, режимами.

Такой подход обладает значительной гибкостью, и отработанную в результате имитационного эксперимента модель можно привести в хорошее соответствие с исследуемой системой [7-10, 18].

Основными причинами популярности метода имитационного моделирования систем массового обслуживания являются [58]: более высокая адекватность между физической сущностью описываемого процесса и его математической моделью; моделирование значительно более широкого класса систем по сравнению с аналитическими методами; моделирование работы систем при самых различных законах распределения многочисленных случайных величин; моделирование функционирования систем не только в установившихся, но и в переходных режимах; получение в результате моделирования более содержательной информации, в том числе многочисленных характеристик законов распределения случайных величин, характеризующих работу системы. Процесс имитации включает огромное число операций, связанных с формированием, преобразованием и использованием реализаций случайных событий, случайных величин и случайных процессов, обеспечивающих случайные скачки состояний системы. Поэтому траектории движения сложной системы в пространстве состояний, получаемые путем имитации, являются случайными функциями времени [7]. Случайный характер также носят любые результаты моделирования, если они получены при воспроизведении на ЭВМ единственной реализации моделируемого процесса. Такие результаты не могут объективно характеризовать моделируемый процесс; они отражают лишь случайные сочетания действующих факторов, складывающиеся в процессе моделирования. Искомые величины при исследовании сложных систем методом имитационного моделирования обычно определяют как средние значения по данным некоторого числа реализаций процесса. Совокупность реализаций выступает в роли "статистического материала" при машинном эксперименте, а оценка параметров исследуемой системы по результатам моделирования - в роли обработки "экспериментальных данных".

Исходным "материалом" для построения любых случайных объектов в ЭВМ служат так называемые случайные числа, вырабатываемые специальной программой - датчиком случайных чисел [8, 79]. Случайные числа можно рассматривать как возможные значения Xj случайной величины %, приближенно подчиняющейся равномерному закону распределения в интервале (0;1). Способы конструирования из случайных чисел различных более сложных случайных объектов достаточно развиты в настоящее время и носят название преобразования случайных чисел [7, 8].

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

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

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

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

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

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

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

В свою очередь, необходимо заметить, что высокий уровень эксплуатационной надежности нефтепромысловых систем обеспечивается выбором необходимых условий и режимов работы глубинных насосов. В процессе эксплуатации нефтепромысловое оборудование переходит из работоспособного состояния в неработоспособное. Этот процесс носит вероятностный характер и описывается случайными закономерностями. Поэтому расчеты будем производить с использованием теории вероятности, теории надежности и теории массового обслуживания [3, 4, 11, 12].

Теорема о максимальном потоке и минимальном разрезе.[74]. Рассмотрим потоковую сеть N=(s, t, V, Е, Ъ) с п-\Ч\ вершинами и т-\Е\ дугами и обозначим поток на дуге (х, у) через f(x, у). Тогда задача о максимальном потоке представляется следующей задачей ЛП, которую мы будем рассматривать как двойственную задачу [74]:

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

Рис. 3.1 иллюстрирует понятия разреза; при этом пропускная способность разреза равна сумме пропускных способностей «прямых» дуг, то есть тех дуг, которые идут из вершин множества W в вершины множества W.

Сопоставим первым п ограничениям, которые соответствуют закону сохранения потока, переменные л(х), а следующим т ограничениям пропускных способностей — переменные у(х,у). Так как первые п ограничений являются равенствами, то ж (х) 0, и поскольку следующие т ограничений являются неравенствами, то у(х, у) 0. Вид задачи ЛП в точности соответствует двойственной задаче в определении 1, поэтому из симметрии прямая задача в этом определении есть та двойственная задача, которую мы ищем: (Теорема о максимальном потоке и минимальном разрезе). Величина потока из s в t не превосходит пропускной способности C{W,W) любого s-разреза. Более того, величина максимального потока равна пропускной способности минимального разреза, и поток f, и разрез (W,W) одновременно оптимальны в том и только в том случае, если f(x,y) = 0 для дуг (х, у) Е, таких, что х Є w и у Є W, f(x,y) = b(x, у) для дуг (х, у) Є Е, таких, что х Є W и у Є W. (3.6) Доказательство теорем 3.1 и 3.2 приведены X. Пападимитриу, Н. Стайглиц [74]. Алгоритм Дейкстры. Рассмотрим эффективную реализацию прямо-двойственного алгоритма для задачи о кратчайшем пути - алгоритма Дейкстры. Учтем, что веса Су всех дуг в задаче о кратчайшем пути предполагаются неотрицательными. В дальнейшем будет видно, что это важное ограничение.

Вместо распространения неизменяющихся пометок назад от вершины t будем двигаться вперед из вершины s. На каждом шаге у нас будет множество вершин Wu пометки р(х) для всех х Є V, обладающие свойством р(х) = (кратчайшая длина пути из s в х, в котором все промежуточные вершины принадлежат W)

Похожие диссертации на Моделирование организации работ ремонтных бригад на скважинах в условиях неопределенности и риска