Выбор оптимального комплекта измерительных приборов

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

Контроль работоспособности системы производится путем проверки n параметров. Для проверки этих параметров могут быть использованы m измерительных приборов. Задана стоимость i -го измерительного прибора с_i (i= 1,..., m) и матрица ||x_ij|| (x_ij = 1, если возможен контроль j -го пара­метра i -м измерительным прибором, x_ij = 0 в противном случае). Для оцен­ки достоверности контроля j -го параметра i -м прибором используется величина q_ij = ( — вероятность ложного забракования, ошибка 1-го рода, — вероятность ложного пропуска, ошибка 2-го рода). Требуется определить комплект измерительных приборов, для которого стоимость измерительной аппаратуры минимальна и суммарная достоверность контроля не превосходит заданной величины Q.

Математически данная задача может быть сформулирована следующим образом. Требуется определить

(3.1)

при следующих ограничениях:

, j= 1, …, n, (3.2)

z_ij x_ijy_i, i= 1, …, m, j= 1, …, n, (3.3)

,

y_j { 0; 1 }, i= 1, …, m. (3.4)

Здесь

x_ij = (3.5)

y_i = (3.6)

z_i = (3.7)

Из условия (3.2) следует, что каждый параметр контролируется толь­ко одним прибором. Условие (3.3) означает, что j -й параметр может контролироваться i -м прибором только при условии, что прибор включен в комплект (у_i = 1) и возможен контроль этого параметра (х_ij = 1).

Рассмотрим алгоритм решения задачи (3.1)—(3.4), основанный
на идеях метода ветвей и границ. Предварительно введем следующие обо­значения: U — множество всех измерительных приборов; S -множество приборов, не включенных в комплект; E_s — множество приборов, вхо­дящих в комплект, исключение которых из комплекта приведет к наруше­нию условия (3.4); G_s = U\ (S U E_S) - множество приборов, входящих в комплект, для которых возможно исключение из комплекта. С учетом
введенных обозначений выражение (3.1) можно представить в следующем виде:

,

, i=1, …, m.

Из данного выражения следует, что при выполнении ограничений (3.2) — (3.4) чем больше стоимость приборов, вошедших в множество S (не включенных в комплект), тем меньше стоимость комплекта приборов. Следовательно, определив максимальную стоимость приборов, включенных в множество S, при выполнении ограничений (3.2) -(3.4) можно найти множество приборов U\ S, для которых выполняется условие (3.1). ^:

Рассматриваемый алгоритм позволяет найти множество приборов S, кото­рому соответствует максимальная стоимость и при котором обеспечивается выполнение ограничений (3.2)-(3.4). Обозначим

j =1, …, n,

, , , k= 1, …, m,

, .

Допустим, что множество S сформировано таким образом, что выполняет­ся условие Qs < Q. Определим верхнюю границу стоимости приборов, во­шедших в множество S:

, (3.8)

где

, (3.9)

при условии

, , k= 1, …, m. (3.10)

Задача (3.9), (3.10) является задачей целочисленного программирова­ния. Для ее решения могут быть использованы различные методы (например метод динамического программирования см. раздел 1.3).

Процесс формирования множества S начинается с S = , т.е. в исходный комплект включаются все возможные приборы. В множество Е_s вклю­чаются приборы, для которых выполняется неравенство > Q_S (к = 1,..., m). После формирования E_s, определяется G_S = U\ (S UE_S) и выбирается r -й прибор для включения в множество S с помощью условия

, h_k=c_k/ . (3.11)

Прибор r -й прибор вводится в множество S и перерассчитываются величины , к U\S, и Qs. Вновь сформировав множества Е_S и G_S, выбираем с по­мощью условия (3.11) прибор для включения в множество S. Аналогич­ным образом формируется множество S на всех последующих шагах.

Процесс формирования множества S заканчивается при условии Gs = , т.е. когда нет ни одного прибора, который можно было исключить из комп­лекта без нарушения ограничения (3.4). В этом случае значение C_S = С⁰_S принимается в качестве первого допустимого решения С⁰. Исключается из множества r-к прибор, включенный на последнем шаге (у_r = 0). При решении задачи (3.9), (3.10), рассчитывается верхняя граница целевой функции (6.149) и проверяется неравенство . (3.12)

Если неравенство не выполняется, то из множества S вводится очередной прибор, включаем его в множество Е_S и вновь проверяется условие (3.12). Если неравенство (3.12) выполняется, то с помощью условия (3.11) выбирается новый прибор для включения в множество S, вводится в это мно­жество, рассчитывается верхняя граница целевой функции (3.8) и вновь проверяется неравенство (6.153). Если, в Процессе решения окажется, что неравенство (3.12) выполняется и G_S = , то полученное значение С_S принимается в качестве нового значения допустимого решения С⁰. Анало­гичным образом вычислительный процесс продолжается до тех пор, пока не будет выполняться неравенство (3.12) при S = . В этом случае послед­нее приближенное решение С⁰ и соответствующее ему множество S⁰ обеспечивают оптимальное решение задачи.

Рассмотрим более подробно основные шаги вычислительного алгоритма.

1. Рассчитать , q_k, Q_S, и h_k (первоначально S= ).

2.Сформировать множества E_S и G_S.

3.Рассчитать значение С_S.

4.Проверить условие С_S > С⁰ (первоначально С⁰ = 0).

Если условие выполняется, перейти к п. 5, если не выполняется — к п. 9.

5.Проверить условие G_S= . Если условие выполняется, перейти к п. 6, если не выполняется — к п. 8.

6.Запомнить С⁰ = С_S и соответствующее множество S°.

7.Вывести из множества S последний элемент и ввести его в множество Е_S; перейти к п. 1.

8.Определить , включить его последним элементом в множество S; перейти к п. 1.,

9.Проверить условие S= . Если условие не выполняется, перейти к п. 7, если выполняется, закончить вычислительный процесс.

Рассмотрим применение данного алгоритма на численном примере. Исходные данные приведены в таблице 3.1, это

Матрица вероятностей ошибок по параметрам и приборам, значения стоимостей приборов . Величина q_ij = ¥ означает, что контроль j – го параметра i – м прибором невозможен.

Таблица 3.1

Параметры j Приборы i									Ci
		∞		∞	∞		∞
	∞		∞		∞		∞	∞
		∞	∞	∞		∞		∞
	∞		∞		∞		∞
		∞		∞		∞
	∞		∞		∞	∞	∞

Первая итерация: На первом шаге вычислительного процесса множество S = Æ, т. е. для контроля могут использоваться все шесть приборов. В каждом столбце находятся минимальные значения q_kj (выделены в таблице 3.2) и вычисляется q_k (последний столбец таблицы 3.2). Вычислив D q_kj , находим D q_k и h_k (см. таблица 3.3).

Таблица 3.2

Параметры Приборы									qk
		∞		∞	∞		∞
	∞		∞		∞		∞	∞
		∞	∞	∞		∞		∞
	∞		∞		∞		∞
		∞		∞		∞
	∞		∞		∞	∞	∞

Поскольку множество , то Т.к. все , то , и тогда . Среди них ищем набор строк, удовлетворяющий условиям 3.9 и 3.10.

Таблица 3.3

Параметры Приборы									Δqk	hk
										1,3
										∞
										2,5
										∞

Для расчета воспользуемся методом динамического программирования, при этом должны выполняться условия 3.9 и 3.10. Из первоначального набора уберем те строки, где Δq_k=0, т.к. они в любом случае не влияют на ограничение 3.10, сумма стоимостей этих строк (2 и 6) равна 2+5=7.

Исходный набор

Таблица 3.4

i
Δqk
Ci

, при этом фиксируется индекс 5.

, в этом случае , остается индекс 5.

в этом случае , остается индекс 5.

при этом фиксируется индекс 3, получаем 3,5.

при этом фиксируется индекс 4, получаем 4,5.

Итак, максимальная сумма получается для набора строк 2,4,5,6 и .

В таком случае, .

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

Вторая итерация:

Таблица 3.5

Параметры Приборы									qk
		∞		∞	∞		∞
		∞	∞	∞		∞		∞
	∞		∞		∞		∞
		∞		∞		∞
	∞		∞		∞	∞	∞

Поскольку множество , то Т.к. все , то , и тогда . Среди них ищем набор строк, удовлетворяющий условиям 3.9 и 3.10

Таблица 3.6

Параметры Приборы									Δqk	hk
										1,3
										2,5
										∞

Из первоначального набора уберем те строки, где Δq_k=0, т.к. они в любом случае не влияют на ограничение 3.10, сумма стоимостей этих строк (строка 6) равна 5.

Итак, поскольку текущий набор такой же как и в предыдущей итерации, то

максимальная сумма получается для набора строк 4,5,6 и .

В таком случае, .

, где , тогда, т.к. , ищем r из условия , откуда получаем .

Третья итерация:

Таблица 3.7

Параметры Приборы									qk
		∞		∞	∞		∞
		∞	∞	∞		∞		∞
	∞		∞		∞		∞
		∞		∞		∞

Поскольку множество , то Т.к. условию не удовлетворяет строка 4, то , и тогда . Среди них ищем набор строк, удовлетворяющий условиям 3.9 и 3.10.

Таблица 3.8

Параметры Приборы									Δqk	hk
4	0	∞	0	∞	0	0	0	0	∞	0

Итак, исходный набор

Таблица 3.9

I
Δqk
Ci

, при этом фиксируется индекс 5.

, в этом случае , остается индекс 5.

в этом случае , остается индекс 5.

при этом фиксируется индекс 3, получаем 3,5.

в этом случае , остаются индексы 3,5.

Итак, максимальная сумма получается для набора строк 3,5 и .

В таком случае, .

, где , тогда, т.к. , ищем r из условия , откуда получаем .

Четвертая итерация:

Таблица 3.10

Параметры Приборы									qk
		∞		∞	∞		∞
		∞	∞	∞		∞		∞

Поскольку множество , то Т.к. условию не удовлетворяют строки 1,3, то , и тогда .

Таблица 3.11

Параметры Приборы									Δqk	hk
1	0	0	∞	0	0	1	0	3	∞	0
3	2	0	0	0	∞	0	∞	0	∞	0

, следовательно . В таком случае, .

, где , тогда, т.к. , . Выносим из S последний элемент 5 и вносим его в E_S.

Пятая итерация:

Таблица 3.12

Параметры Приборы									qk
		∞		∞	∞		∞
		∞	∞	∞		∞		∞
	∞		∞		∞		∞
		∞		∞		∞

Поскольку множество , то Т.к. условию не удовлетворяет строка 4, то , и тогда . Среди них ищем набор строк, удовлетворяющий условиям 1.11 и 1.12.

Таблица 3.13

Параметры Приборы									Δqk	hk
4	0	∞	0	∞	0	0	0	0	∞	0

Итак, исходный набор

Таблица 3.14

I
Δqk
Ci

так, максимальная стоимость получается для строки 3 и .

В таком случае, . , где , тогда, т.к. , выносим из S последний элемент 6 и вносим его в E_S.

Шестая итерация:

Таблица 3.15

Параметры Приборы									qk
		∞		∞	∞		∞
		∞	∞	∞		∞		∞
	∞		∞		∞		∞
		∞		∞		∞
	∞		∞		∞	∞	∞

Поскольку множество , то Т.к. все , то остается , и тогда . Среди них ищем набор строк, удовлетворяющий условиям 3.9 и 3.10.

Таблица 3.16

Параметры Приборы									Δqk	hk
										1,3
										2,5

Итак, поскольку текущий набор такой же, как и в первой итерации, то

максимальная сумма получается для набора строк 4,5 и .

В таком случае, . , где , тогда, т.к. , ищем r из условия , откуда получаем .

Седьмая итерация:

Таблица 3.17

Параметры Приборы									qk
		∞		∞	∞		∞
		∞	∞	∞		∞		∞
	∞		∞		∞		∞
	∞		∞		∞	∞	∞

Поскольку множество , то Т.к. условию не удовлетворяют строки 1,3, то , и тогда .

Таблица 3.18

Параметры Приборы									Δqk	hk
1	0	0	∞	0	0	1	0	2	∞	0
3	2	0	0	0	∞	0	∞	0	∞	0

Итак, максимальная сумма стоимости получается для строки 4 и .

В таком случае, . , где , тогда, т.к. , ищем r из условия , откуда получаем .

Восьмая итерация:

Таблица 3.19

Параметры Приборы									qk
		∞		∞	∞		∞
		∞	∞	∞		∞		∞
	∞		∞		∞	∞	∞

Поскольку множество , то , , тогда и , а в таком случае, . , где , тогда, т.к. , . Выносим из S последний элемент 4 и вносим его в E_S.

Девятая итерация:

Таблица 3.20

Параметры Приборы									qk
		∞		∞	∞		∞
		∞	∞	∞		∞		∞
	∞		∞		∞		∞
	∞		∞		∞	∞	∞

Таблица 3.21

Параметры Приборы									Δqk	hk
1	0	0	∞	0	0	1	0	2	∞	1
3	2	0	0	0	∞	0	∞	0	∞	2

Поскольку множество , то Т.к. условию не удовлетворяют строки 1 и 3, то , и тогда . Максимальная стоимость получается для строки 6 и . В таком случае, . , где , тогда, т.к. , выносим из S последний элемент 5 и вносим его в E_S.

Десятая итерация:

Таблица 3.22

Параметры Приборы									qk
		∞		∞	∞		∞
		∞	∞	∞		∞		∞
	∞		∞		∞		∞
		∞		∞		∞
	∞		∞		∞	∞	∞

Поскольку множество , то Т.к. все , то остается , и тогда . Среди них ищем набор строк, удовлетворяющий условиям 3.9 и 3.10.

Таблица 3.23

Параметры Приборы									Δqk	hk
										1,3
										2,5
										∞

Итак, максимальная сумма получается для набора строк 4,6 и .

В таком случае, . , где , тогда, т.к. , выносим из S последний элемент 2 и вносим его в E_S.

Одиннадцатая итерация:

Таблица 3.24

Параметры Приборы									qk
		∞		∞	∞		∞
	∞		∞		∞		∞	∞
		∞	∞	∞		∞		∞
	∞		∞		∞		∞
		∞		∞		∞
	∞		∞		∞	∞	∞

Поскольку множество , то Т.к. все , то остаётся , и тогда . Среди них ищем набор строк, удовлетворяющий условиям 3.9 и 3.10.

Таблица 3.25

Параметры Приборы									Δqk	hk
										1,3
										2,5
										∞

Итак, максимальная сумма стоимости получается для набора строк 4,5,6 и .

В таком случае, . , где , тогда, т.к. , ищем r из условия , откуда получаем .

Двенадцатая итерация:

Таблица 3.26

Параметры Приборы									qk
		∞		∞	∞		∞
	∞		∞		∞		∞	∞
		∞	∞	∞		∞		∞
	∞		∞		∞		∞
		∞		∞		∞

Поскольку множество , то Т.к. строка 4 не удовлетворяет , то , и тогда . Среди них ищем набор строк, удовлетворяющий условиям 3.9 и 3.10.

Таблица 3.27

Параметры Приборы									Δqk	hk
4	0	2	0	4	0	0	0	0	6	1,6

Итак, максимальная сумма получается для набора строк 3,5 и .

В таком случае, . , где , тогда, т.к. , выносим из S последний элемент 6 и вносим его в E_S.

Тринадцатая итерация:

Таблица 3.28

Параметры Приборы									qk
		∞		∞	∞		∞
	∞		∞		∞		∞	∞
		∞	∞	∞		∞		∞
	∞		∞		∞		∞
		∞		∞		∞
	∞		∞		∞	∞	∞

Поскольку множество , то Т.к. все , то остаётся , и тогда . Среди них ищем набор строк, удовлетворяющий условиям 3.9 и 3.10.

Таблица 3.29

Параметры Приборы									Δqk	hk
										1,3
										∞
										2,5

Итак, максимальная сумма стоимости получается для набора строк 4,2,5 и .

В таком случае, . , где , тогда, т.к. , расчёт заканчивается.

Процесс формирования набора представлен в Таблице 3.30, ему соответствует граф (рис 3.1 – Дерево формирования решения)

Таблица 3.30