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

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

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

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

(3.1)

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

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

zij xijyi, i=1, …, m, j= 1, …, n, (3.3)

,

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

Здесь

xij= (3.5)

yi = (3.6)

zi = (3.7)

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

Рассмотрим алгоритм решения задачи (3.1)—(3.4), основанный
на идеях метода ветвей и границ. Предварительно введем следующие обо­значения: U — множество всех измерительных приборов; S-множество приборов, не включенных в комплект; Es — множество приборов, вхо­дящих в комплект, исключение которых из комплекта приведет к наруше­нию условия (3.4); Gs = U\ (S U ES) — множество приборов, входящих в комплект, для которых возможно исключение из комплекта. С учетом
введенных обозначений выражение (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вклю­чаются приборы, для которых выполняется неравенство > QS (к = 1, ..., m). После формирования Es, определяется GS = U\ (S UES) и выбирается r-й прибор для включения в множество S с помощью условия

, hk=ck/ . (3.11)

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

Процесс формирования множества S заканчивается при условии Gs = , т.е. когда нет ни одного прибора, который можно было исключить из комп­лекта без нарушения ограничения (3.4). В этом случае значение CS = С0S принимается в качестве первого допустимого решения С0. Исключается из множества 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) выполняется и GS = , то полученное значение СS принимается в качестве нового значения допустимого решения С0. Анало­гичным образом вычислительный процесс продолжается до тех пор, пока не будет выполняться неравенство (3.12) при S = . В этом случае послед­нее приближенное решение С0 и соответствующее ему множество S0обеспечивают оптимальное решение задачи.

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

1. Рассчитать , qk, QS, и hk (первоначально S= ).

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

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

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

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

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

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

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

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

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

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

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

Таблица 3.1

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

Таблица 3.2

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

Таблица 3.3

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

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

Таблица 3.4

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

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

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

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

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

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

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

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

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

Таблица 3.5

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

Таблица 3.6

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

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

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

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

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

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

Таблица 3.7

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

Таблица 3.8

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

Таблица 3.9

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

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

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

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

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

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

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

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

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

Таблица 3.10

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

Таблица 3.11

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

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

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

Таблица 3.12

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

Таблица 3.13

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

Таблица 3.14

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

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

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

Таблица 3.15

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

Таблица 3.16

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

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

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

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

Таблица 3.17

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

Таблица 3.18

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

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

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

Таблица 3.19

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

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

Таблица 3.20

Таблица 3.21

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

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

Таблица 3.22

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

Таблица 3.23

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

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

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

Таблица 3.24

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

Таблица 3.25

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

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

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

Таблица 3.26

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

Таблица 3.27

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

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

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

Таблица 3.28

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

Таблица 3.29

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

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

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

Таблица 3.30

Рис 3.1. Дерево формирования решения