Дискретно-непрерывная математика (стр. 47 )

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

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

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

Рис. 5.24

Рассмотрим поиск пути бродячего торговца на графе, приведенного на рис. 5.25.

Операция разветвления при построении порфириана в этом случае при переходе от σk=i1, i2,…,ik к σk+1 = (σk, j) требует строить вершины (k + 1)-го уровня (обозначая их j), если в графе рис. 5.25 имеется стрелка, которая соединяет ik с j.

Рис. 5.25.

В нашем примере мы тоже получим всего три возможных решения:

(1, 2, 7, 8, 3, 4, 5, 6),

(1, 2, 7, 8, 3, 5, 6, 4), (5.52)

(1, 2, 7, 8, 3, 6, 4, 5).

2. Расстановка оборудования вдоль кругового конвейера. Круговой конвейер движется в одном направлении. Вдоль конвейера требуется расставить п станков. Обработанные на станке i детали передаются на другой станок j в количестве аіj по конвейеру.

Требуется расставить станки в таком порядке, чтобы минимизировать общее время передачи деталей от станка к станку. Последнее означает, что если tij — время передачи детали от станка i к станку j, то требуется минимизировать

Будем считать, что время tij пропорционально расстоянию ρij между станками вдоль конвейера, а это расстояние полностью определяется тем, «как далеко» отстоят i и j в перестановке σп.

Пусть k (i) и k(j) - соответственно места, которые занимают i и j в перестановке σп. Конвейер движется вдоль станков в направлении от начала σп к концу. Это означает, что

(5.53)

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

(5.54)

где ρij (σп) определяется по формуле (5.53).

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

Зададимся вопросом: что произойдет, если мы в перестановке σп поменяем местами два каких-нибудь соседних станка i и j? Ясно, что все то, что направлялось к первому станку i (вдоль перестановки), будет теперь идти на единицу времени дольше, за исключением тех деталей, которые шли к i от второго станка j, для них время пути сократилось на п — 2 единиц. Все, что шло к второму станку j рассматриваемой пары, будет находиться в пути на единицу времени меньше, зато все, что шло от этого станка к другим, будет находиться в пути на единицу времени дольше. То, что шло к нему от соседнего станка i, будет находиться в пути на п — 2 единиц времени дольше (см. схему рис. 5.26).

Рис. 5.26

Окончательный эффект от этой перестановки будет таким:

(5.55)

Очевидно, что если φij<0, значит, выгодно поменять местами соседние станки i и j в перестановке σп — общее число «передач» при этом уменьшится, если φij ≥ 0, значит, этого не следует делать.

Рассмотрим пример, в котором исходные данные представлены табл. 5.6.

Таблица 5.6

Матрица аij

Для каждой пары станков проведем вычисление того, в каком порядке удобно в перестановке σп располагать станки i и j при условии, что они соседние.

Вычисления рекомендуем сделать с помощью специальной расчетной таблицы (РТ) (табл. 5.7).

Таблица 5.7

Расчетная таблица (РТ)

Запишем согласно формуле (5.55):

1) все элементы строки i матрицы аij из табл. 5.6 (за исключением стоящего в столбце j) в графу II РТ;

2) все элементы, которые стоят в столбце с номером i (за исключением стоящего в строке j), в графу I PT;

3) все элементы, которые стоят в строке j (за исключением i-гo столбца), в графу I;

4) все элементы, которые стоят в столбце j (за исключением i-й строки), в графу II;

5) (п — 2) аij в графу I;

6) (п — 2) аjі в графу II.

Суммируем все числа, выписанные в графе I, и полагаем х равным этой сумме; затем суммируем все числа, выписанные в графе II, и полагаем у равным этой сумме.

Если х > у (что соответствует φij> 0), в таблице Sij в клетке i-й строки, j-м столбце пишем +, в клетке j-й строки, i-го столбца пишем —.

Если х ≤ у (что соответствует φij ≤0), в таблице - Sij в клетке i-й строки, j-м столбце пишем —, в клетке j-й строки i-го столбца пишем +.

Знак + в таблице 5.9 означает, что переход от i к j при построении порфириана допустим. Знак -, что недопустим.

Описанные правила вычислений иллюстрирует табл. 5.8 для i = 1, j = 2.

Таблица. 5.8

Согласно описанному правилу в клетку i = 1, j = 2 таблицы заносим —, а в клетку j = 1, i = 2 заносим +

Окончательный результат вычислений представлен табл. 5.9.

Таблица 5.9

Рис. 5.27 определяет граф, соответствующий таблице 5.9. Этот граф задает допустимые пути поиска перестановки - как и в задаче бродячего торговца как бы «направляя» построение порфириана.

Рис. 5.27.

Нетрудно убедиться, что σп = (1, 4, 3, 2, 5) есть единственное решение нашей задачи (рис. 5.28).

Рис. 5.28

При построении порфириана, соответствующего графу рис. 5.27, поиск маршрута удобно начинать с пункта i1=1, в этом случае i2 = 4 — единственное i2 в порфириане.

3. Загадка маленькой мушки. Маленькая мушка - дрозофила - любимый объект экспериментирования генетиков: за одну неделю можно наблюдать несколько поколений мушки.

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

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

Перенумеруем наблюдаемые признаки и составим таблицу результатов проведенных опытов, где будем отмечать на пересечении i -й строки и j - го столбца

(5.56)

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

Математическая постановка задачи хорошо иллюстрируется примером, представленным на рис. 5.29, а, б.

Рис. 5.29

Рис. 5.29, а представляет результаты эксперимента — закрашенные в черный цвет клетки соответствуют δij = 1. Задача состоит в том, чтобы перестановкой i (т. е. одновременно строк и столбцов) привести таблицу к виду, соответствующему рис. 5.29,б, где закрашенные клетки некоторым образом «прилегают» к главной диагонали таблицы.

Это свойство «прилегания» к главной диагонали можно выразить и аналитически:

δij ≥δij+1 для всех j≥i. (5.57)

Изложим здесь метод решения нашей задачи диагонализации таблицы результатов эксперимента (матрицы δij) путем построения порфириана (отметим, что существует и более эффективный метод решения задачи, точнее, лучше «отбраковывающий» варианты в операции разветвления).

Исследуем для начала некоторые свойства искомого решения.

Назовем «хвостом» (не путайте с «перестановочним хвостом») i для σk все те j, которые не вошли в σk и для которых δij = 1.

Утверждение 4. Если σk и σk+1 = σk, j — фрагменты искомого решения, то j входит во все (непустые) «хвосты» σk.

Утверждение 5. Пусть для σk выбраны два каких-то «хвоста». Если каждый из выбранных «хвостов» содержит по одном j, не входящему в другой «хвост», то полученный σk не может быть фрагментом искомого решения.