МАТЕМАТИКА/5. Математическое моделирование

К.т.н. Бруслова О.В.

Тюменский государственный нефтегазовый университет, Россия

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

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

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

                (1)

и поставим вопрос о нахождении оптимального параметра , равного . Иными словами, рассмотрим такое назначение :i(i) (i=1,2,…,m), при котором самое «тесное» место его будет наибольшим среди всех возможных назначений.

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

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

.

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

Пусть  - произвольная подстановка, тогда сопоставим матрице А=((аij))тхт матрицу  порядка тхт, состоящую из нулей и единиц так, что

.                   (2)                       

Теорема 2. Если в матрице  существует т независимых единичных элементов, то подстановку  можно «улучшить» так, что

>                  (3)                       

Подстановка ` будет отвечать одному из возможных максимальных паросочетаний П (d(П) = m) в графе , структура множества дуг в котором определяется условиями (2).

Если максимальное число независимых единичных элементов меньше, чем m, m = |Х|, то подстановка  оптимальна.

Доказательство. Первое утверждение вытекает из определения независимости элементов бинарной матрицы и равенства (2). Для доказательства второго рассмотрим сначала частный случай, когда в матрице  существует строка i0, не содержащая ни одной единицы. Значит, по построению , что для данной строки все элементы

                                      (4)              

и, в частности, на этой строке =.

Тогда для любой другой подстановки ' выполнение условия (3) приведёт к неравенству >, которое заведомо не выполняется в силу (4).

Для доказательства второго утверждения заметим, что любая другая подстановка ', для которой хотя бы один элемент = 0 не может увеличиться, как это видно из (2) и определения , величины . Подстановки ', отличной от  и использующей только единичные элементы матрицы , не существует в силу условия теоремы. Из доказательства теоремы непосредственно видно, что алгоритм решения задачи в существенной своей части сводится к проверке условий теоремы 3 и нахождению максимального паросочетания.

Теорема 3. Паросочетание, отображающее X в Y , существует тогда и только тогда, когда для любого множества АХ выполняется соотношение

|А|<|ГА|.                                                   (5)

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

Как нетрудно увидеть, задача о максимальном потоке для сети, состоящей из двудольного графа G = (X, Y, Г), дополненного входом и выходом, сводится к построению максимального множества независимых единичных элементов в матрице АG порядка от mхп, где m=|X|, n=|Y|.

Рассмотрим таблицу Т, в которой клетки с номерами (ij) (i(1,2,...,m), j(1,2,,...,n)),  такими, что  аij=1,   называются допустимыми.

Клетки таблицы Т, не лежащие на одной строке или в одном столбце, называются независимыми. Допустимые клетки таблицы Т, образующие независимое множество, соответствуют множеству независимых единичных элементов матрицы АG.

Для построения наибольшего паросочетания в двудольном графе в случае матричного представления транспортной сети  используем алгоритм Форда — Фалкерсона. Его словесное представление имеет вид:

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

2. Просмотреть все помеченные строки, отыскать все допустимые клетки, не содержащие единицы, и пометить индексом соответствующей строки непомеченные столбцы, содержащие такие клетки. Если будет помечен столбец, не содержащий единиц, перейти к 4°. В противном случае — к 3°. 3°. Просмотреть помеченные столбцы и найти в них клетку с единицей. Строки, содержащие такие клетки и еще не помеченные, пометить номером соответствующего столбца. Если новых меток строкам присвоить нельзя, перейти к 5°. В противном случае — к 2°.

4. Увеличить множество независимых клеток на единицу с помощью следующей операции, называемой «прорывом». В столбце, не содержащем единицы и только что помеченном, поставить единицу в клетке с меткой этого столбца. Затем в строке, в которую поставлена единица и не помеченной меткой (X), убрать единицу из клетки, соответствующей метке данной строки. Теперь в столбце, содержащем клетку, из которой убрана единица, поставить единицу в клетку, соответствующую метке данного столбца. Перейти к 2°.

5. Закончить работу. Имеющееся размещение независимых клеток с единицами определяет в матрице АG максимальное множество независимых элементов.

Рис..1. Исходная таблица планирования 1

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

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

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

Теперь можно устроить «прорыв», перемещая 1 из клетки 1(1, 2) указанным выше способом; на рис. 3 изображено получившееся размещение независимых единиц в клетках (1,5), (2,1), (3,3) (4,4), (5,2) и (7,6). Просматривая вновь помеченные строки, находим столбец 7, не содержащий единиц и поэтому допускающий прорыв (рис. 4). Полученное размещение единиц в клетках (1,5), (2,1), (3,7), (4,4), (5,2), (6,3), (7,6) максимально.

 

 Рис. 2. Транспортная сетка 1

 

Рис. 3.Транспортная сетка 2

Рис. 4. Транспортная сетка 3

 

С учётом вышеизложенного представим  алгоритм решения задачи об оптимальном назначении:

1. По исходной матрице А и произвольной подстановке  составить матрицу , состоящую из нулей и единиц, причем так, что.

2. Найти в матрице  максимально возможное количество независимых единичных элементов.  Если число таких элементов меньше, чем , то перейти к 4, если нет, то к 3.

3. По n независимым единичным элементам определить подстановку `(i)=j(i=1,2,…,n), j- номер столбца, содержащего единичный элемент строки i и перейти к 1.

4. Закончить работу.

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

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

Таблица 1

Исходная матрица

2

6

4

5

9

2

3

5

3

1

8

8

1

4

7

0

5

2

6

6

9

5

6

1

7

4

7

8

0

8

2

4

3

4

1

1

9

6

5

2

5

3

6

9

1

0

4

6

7

Числа, стоящие на пересечении строки и столбцов соответственно с номерами i, (i) (i=1,2,...,7), подчеркнуты.

Для исходной матрицы А =3, поэтому матрица  принимает вид, представленный таблицей на рис. 5.5, где незаштрихованные клетки соответствуют единичным элементам матрицы , а заштрихованные — нулевым элементам.

В матрице  отыскиваем максимально возможное количество независимых клеток. При этом, по возможности, как можно больше клеток подстановки . На рис. 5 такое назначение указано единицами. Поскольку матрица  совпадает с матрицей АG, представленной таблицей на рис. 3, то, применяя описанный алгоритм Форда — Фалкерсона, можно указать максимальное множество из 7 клеток (см. рис. 4) и тем самым определить новую подстановку

 такую, что .

Рис. 5. Таблица планирования 2

Рис. 6. Таблица планирования 3

 

Подстановка ' определяет матрицу . (рис. 6), для которой нетрудно определить, что максимальное независимое множество содержит 5 < 7 клеток, и поэтому подстановка  оптимальна.

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

1.     Матрицей расстояний между кустами.

2.     Матрицей расстояний от базы, на которой находятся бригады, до кустов скважин.

3.     Количество свободных бригад.

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

Литература:

1.     Карнаухов М.Л., Шевченко В.Н., Павлов М.В. Критерии эффективности капитального ремонта скважин - М.: Нефтяное хозяйство, №12, 1997 г. - с.53 - 57.

2.     Кучумов Р.Я., Кучумов Р.Р. Математические методы обработки статистической информации на ЭВМ. - Тюмень: ТюмГНГУ, 1995.

3.     Мирзаджанзаде А.Х., Степанова Г.С., Математическая теория эксперимента в добыче нефти и газа. -М.: Недра, 1969.