Размещено на http://www.allbest.ru/

Лекция 1

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

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

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

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

1) для (здесь - множество, состоящее из един-ственного элемента );

2) если и , то .

В этих условиях можно организовать перебор элементов множества M с целью минимизации функции на этом множестве так:

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

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

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

Предположим, что ; тогда для любого элемента m множества M, принадлежащего множеству , будут верны неравенства

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

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

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

Имеется несколько городов, соединеных некоторым образом дорогами с известной длиной; требуется установить, имеется ли путь, двигаясь по кото-рому можно побывать в каждом городе только один раз и при этом вернуться в город, откуда путь был начат («обход коммивояжера»), и, если таковой путь имеется, установить кратчайший из таких путей.

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

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

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

пусть - полный ориентированный граф и -

весовая функция; найти простой остовный ориентированный цикл («цикл коммивояжера») минимального веса.

Пусть конкретный состав множества вершин и

- весовая матрица данного орграфа, т.е.

,

причем для любого .

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

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

Слова привести матрицу по строкам означают, что все строки матри-цы приводятся. Аналогичный смысл имеют слова привести матрицу по столбцам.

Наконец, слова привести матрицу означают, что матрица сначала приводится по строкам, а потом приводится по столбцам.

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

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

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

множеству всех обходов коммивояжера сопоставлено число () и матрица M₁.

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

Сопоставим множеству следующую матрицу M_1,1: в матрице M₁ заменим на число в клетке . Затем в полученной матрице вычеркнем строку номер i и столбец номер j, причем у оставшихся строк и столбцов сохраним их исходные номера. Наконец, приведем эту последнюю матрицу и запомним сумму констант приведения. Полученная приведенная матрица и будет матрицей M_1,1; только что запомненную сумму констант приведения прибавим к () и результат, обозначаемый в дальнейшем через (), сопоставим множеству .

Теперь множеству тоже сопоставим некую матрицу M_1,2. Для этого в матрице M₁ заменим на число в клетке и полученную в ре-зультате матрицу приведем. Сумму констант приведения запомним, а полученную матрицу обозначим через M_1,2. Прибавим запомненную сумму констант приведения к числу () и полученное число, обозначаемое в дальнейшем через (), сопоставим множеству .

Теперь выберем между множествами и то, на котором ми-нимальна функция (т.е. то из множеств, которому соответствует меньшее из чисел () и ().

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

К выбранному множеству с сопоставленными ему матрицей и числом повторим все то же самое и так далее, пока это возможно.

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

После этого осуществляется улучшение рекорда вплоть до получения окончательного ответа.

Лекция 2

Решение задачи о коммивояжере методом ветвей и границ. Примеры.

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

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

	1	2	3	4	5
1		9	8	4	10
2	6		4	5	7
3	5	3		6	2
4	1	7	2		8
5	2	4	5	2

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

Подсчитаем () в нашем примере. Для этого выполним приведение матрицы весов; сначала - по строкам:



	1	2	3	4	5
1		9	8	4	10	4	min в строке 1
2	6		4	5	7	4	min в строке 2
3	5	3		6	2	2	min в строке 3
4	1	7	2		8	1	min в строке 4
5	2	4	5	2		2	min в строке 5

результат приведения по строкам:

	1	2	3	4	5
1		5	4	0	6
2	2		0	1	3
3	3	1		4	0
4	0	6	1		7
5	0	2	3	0

Определим константы приведения по столбцам:

	1	2	3	4	5
1		5	4	0	6
2	2		0	1	3
3	3	1		4	0
4	0	6	1		7
5	0	2	3	0
	0	1	0	0	0
	min в столбце 1	min в столбце 2	min в столбце 3	min в столбце 4	min в столбце 5

результат приведения матрицы:

	1	2	3	4	5
1		4	4	0	6
2	2		0	1	3
3	3	0		4	0
4	0	5	1		7
5	0	1	3	0

сумма констант приведения ()=4+4+2+1+2+1=14.

Обозначим эту матрицу через M₁; найдем в ней самый тяжелый нуль. Для этого запишем эту матрицу еще раз, указывая рядом с каждым нулем в скобках его вес:

	1	2	3	4	5
1		4	4	0(4)	6
2	2		0(2)	1	3
3	3	0(1)		4	0(3)
4	0(1)	5	1		7
5	0(0)	1	3	0(0)

Самым тяжелым оказывается нуль в клетке (1,4). Следовательно, множество разбивается на (все циклы, проходящие через ребро (1,4)) и (все циклы, не проходящие через ребро (1,4)).

Построим для множества соответствующую ему матрицу и зна-чение оценочной функции. Сейчас уместно отдельным абзацем напомнить ту самую «сложную» фразу из предыдущей лекции:

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

Учитывая это напоминание, элемент с номером (4,1) заменим на и вычеркнем строку номер 1 и столбец номер 4:

	1	2	3	5
2	2		0	3
3	3	0		0
4		5	1	7
5	0	1	3



Приведем теперь эту матрицу:

	1	2	3	5
2	2		0	3
3	3	0		0
4		4	0	6
5	0	1	3

Это - матрица M_1,1; сумма констант приведения здесь равна 1, поэтому 14+1= 15.

Для M_1,2 заменяем на элемент (1,4) в M₁:

	1	2	3	4	5
1		4	4		6
2	2		0	1	3
3	3	0		4	0
4	0	5	1		7
5	0	1	3	0

после этого приводим полученную матрицу:

	1	2	3	4	5
1		0	0		2
2	2		0	1	3
3	3	0		4	0
4	0	5	1		7
5	0	1	3	0

Это - матрица M_1,2; сумма констант последнего приведения равна 4, так что 14+4=18. Следовательно, дальнейшей разработке подвергается множество .

Вот веса нулей матрицы M_1,1 (они указаны в скобках):



	1	2	3	5
2	2		0(2)	3
3	3	0(1)		0(3)
4		4	0(4)	6
5	0(3)	1	3

самым тяжелым является нуль с номером (4,3), так что теперь следует рассматривать множества и .

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

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

Следовательно, клетки с номерами (4,2), (4,5) и (3,1) надо заполнить символом ; после этого строку номер 4 и столбец номер 3 следует вычерк-нуть; получим:

	1	2	5
2	2		3
3		0	0
5	0	1

Приведение этой матрицы:

	1	2	5
2	0		1
3		0	0
5	0	1

Для оценочной функции: =15+2=17.

Матрица для множества :

	1	2	3	5
2	2		0	3
3	3	0		0
4		4		6
5	0	1	3

Результат ее приведения:

	1	2	3	5
2	2		0	3
3	3	0		0
4		0		2
5	0	1	3

Оценочная функция: =15+4=19. Следовательно, дальнейшей разработке подлежит . «Взвешиваем» нули:

	1	2	5
2	0(1)		1
3		0(1)	0(1)
5	0(1)	1

Выбираем любую из соответствующих клеток; для определенности - клетку (2,1).

Теперь речь пойдет о множествах и .

Опять напомним фразу:

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

	2	5
3		0
5	1

Приведем эту матрицу:

	2	5
3		0
5	0

Получаем для оценочной функции: =17+1=18.

Для множества матрица такова:

	1	2	5
2			1
3		0	0
5	0	1

Приведение этой матрицы дает:

	1	2	5
2			0
3		0	0
5	0	1

Для оценочной функции: =17+1=18.

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

(1,4)(4,3)(2,1)(5,2)(3,5) или 143521.

Найденный рекорд на самом деле является искомым оптимумом,

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

При ином варианте выборов по ходу разбиений можно было получить другой оптимум: 143251.

Лекция 3

Постановка основной задачи теории расписаний. Случай одной машины.

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

Проиллюстрируем простым примером специфику этих задач.

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

станок\деталь	Д1	Д2	Д3
Т1	3	1	2
Т2	2	4	1



Если детали запустить на обработку в последовательности Д2, Д1, Д3 (т.е. сначала - Д2, потом - Д1, а потом - Д3), то весь производственный процесс закончится через 8 часов, а если эти же детали запустить на эти же станки в последовательности Д3, Д1, Д2, то весь производственный процесс закончится только через 11 часов.

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

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

Итак, имеется одна машина, на которой производятся работы в той или иной последовательности - работы из множества ; пусть - фактическая продолжительность выполнения i-ой работы, - начало и конец фактического выполнения работы (так что ), - директивное время выполения i-ой работы (т.е. время, в течение которого работы должна быть выполнена по плану), - стоимость ожидания в единицу времени i-ой работы.

Перерывы в выполнении работ не допускаются.

Пусть ; это - задержка i-ой работы по сравнению с директивным временем на производственном участке. Положим

;

это - суммарный штраф за простой при выполнении работ по тому или иному плану. Пусть, далее,

;



это - максимальный среди работ штраф за простой. Чем он меньше, тем равномернее издержки, доставляемые работами.

Наконец, пусть

;

это - сумма штрафов, связанных с ожиданием работ в системе.

Часто фиксируют величину

-

суммарное время выполнения всех работ.

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

Можно доказать следующее утверждение:

пусть работы занумерованы так, что

;

тогда, если их запустить на исполнение в порядке возрастания номеров, то критерий ₃ обратится в минимум.

Можно доказать также, что действия по нижеследующему алгоритму приводят к минимуму критерия ₂:

Шаг 0. Находим .

Шаг 1. Среди всех еще неупорядоченных работ находим такую работу l, что

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

Шаг 2. Работу l назначают последней к исполнению среди еще неупоря-доченных работ и исключают из рассмотрения. Если множество оставшихся работ пусто, то процесс упорядочения закончен. Если множество оставшихся работ непусто, заменим T на и переходим к Шагу 1.

Заметим, в заключение, что относительно критерия ₁ в общем случае неизвестен алгоритм, отличный от прямого перебора возможностей.

Лекция 4

Задача Джонсона в теории расписаний. Случаи двух и трех машин.

Сформулируем классическую задачу теории расписаний - задачу Джон-сона: граница коммивояжер машина джонсон

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

В этой постановке задачи предполагается, что

1) в любой момент времени на одной машине выполняется не более одной работы;

2) в любой момент времени одна работа выполняется не более, чем на

одной машине.

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

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

Шаг 0. Записывается матрица времен выполнения данных работ.

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

Шаг 2. Исключают из дальнейшего рассмотрения время выполнения упорядоченной работы (т.е. вычеркивают из матрицы строку). Если после этого от матрицы ничего не остается, то задача решена; в противном случае переходим к Шагу 1.

Напомним, что описанный алгоритм минимизирует суммарное время простоя обеих машин.

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

пусть по-прежнему - множество работ, которые выполня-

ются на двух машинах (№1 и №2), пусть по-прежнему - - время выполнения i-ой работы на j-ой машине, но:

N₁ - подмножество работ, которые выполняются только на первой маши-не;

N₂ - подмножество работ, которые выполняются только на второй маши-не;

N_1,2 - подмножество работ, которые выполняются сначала на первой, а потом на второй машине;

N_2,1 - подмножество работ, которые выполняются сначала на второй, а потом - на первой машине.

Таким образом, .

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

1) в соответствии с алгоритмом Джонсона для последовательного

варианта задачи для двух машин упорядочим работы из множеств N_1,2 и N_2,1;

2) на первую машину запускаются сначала работы из N_1,2, затем - из N₁, а затем - из N_2,1;

3) на вторую машину запускаются сначала работы из N_2,1, затем - из N₂, а затем - из N_1,2.

Рассмотренный общий случай задачи Джонсона для двух машин часто называют смешанным вариантом задачи Джонсона.

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

N		N1,2				N2,1		N1		N2
М\Р	р1	р2	р3	р4	р5	р6	р7	р8	р9	р10	р11
М1	3	1	2	4	1	3	2	5	2	0	0
М2	4	3	1	2	5	2	1	0	0	2	1

здесь р_j - имя работы, М_i - имя машины.

По алгоритму Джонсона:

оптимумы для N_1,2 и N_2,1, соответственно: (р₂,р₁,р₄,р₃) и (р₇,р₆,р₅);

оптимальные режимы работ.

Машина №1: (р₂,р₁,р₄,р₃,(р₈,р₉), р₇,р₆,р₅);

Машина №2: (р₇,р₆,р₅,(р₁₀,р₁₁), р₂,р₁,р₄,р₃).

Записи (р₈,р₉) и (р₁₀,р₁₁) означают, что порядок выполнения

этих работ - произвольный.

Перейдем к случаю трех машин.

Ограничимся здесь далеко не общей ситуацией; итак,

m=3 - число машин;

- множество работ;

- время выполнения i-ой работы на j-ой машине;

предполагается, что у все работ одна и та же последователь-

ность прохождения по машинам.

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

Утверждение №1. Пусть работы можно пронумеровать так, что окажутся выполненными одновременно следующие неравенства:

Тогда суммарный простой машин будет минимальным при следующем порядке запуска работ на исполнение: 12...n.

Утверждение №2. Пусть для матрицы выполнено хотя бы одно из двух следующих условий:



Построим новую матрицу , в которой i=1,2,...,n, j=1,2 и , и будем считать ее матрицей времен задачи Джонсона для двух машин в последовательном варианте и множества тех же работ . Тогда суммарное время простоя исходных трех ма-шин при выполнении исходных работ будет минимальным, если эти работы направлять на исполнение в том порядке, который является оптимальным в задаче с матрицей .

Более общие случаи задачи Джонсона рассматриваются в следующей лекции.

Лекция 5

Общее решение задачи Джонсона методом ветвей и границ.

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

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

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

Для большей ясности мы будем далее предполагать, что .

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

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

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

Итак, пусть

Таким образом, - время окончания исполнения работы на k-ой машине. Далее определим функции рекуррентно:

,

,

.



Теперь можно построить сразу три оценочных функции для множеств , которые будем обозначать так: ₁, ₂ и ₃. Вот их определение (мы будем обозначать для удобства записи через x и через те работы из множества , которых нет среди работ ):

;

;

.

Тот факт, что эти функции - оценочные, можно доказать; аналогично, можно доказать то же самое в отношении функции

;

она - оценочная.

Лекция 6

Системы массового обслуживания (СМО): определение, классификация, построение графа состояний. Введение основных характеристик.

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

Схематически эту ситуацию можно изобразить так:

Это - ситуация системы массового обслуживания (СМО).

Особенность обсуждаемой ситуации: заявки приходят на обслуживание хаотично, в случайные моменты времени. И вторая особенность: время, в течение которого заявка находится в СМО (в очереди и в узле обслуживания) - тоже величина случайная. Приняты две классификации СМО - по типу очереди и по типу узла обслуживания.

Будем говорить, что некая СМО находится в состоянии Е_k в момент времени t₀, если в этот момент в ней находится ровно k заявок. С каждой СМО принято связывать специальный граф - граф состояний, - который строится следующим образом: его множеством вершин является множество всех возможных состояний Е_k (k=0,1,2,...), а ребро (E_i, E_j) включается тогда и только тогда, когда СМО в процессе своей работы может перейти из состояния E_i в состояние E_j непосредственно, т.е. минуя все остальные состояния.

Как было сказано выше, важнейшая особенность СМО как объекта изучения состоит в том, что заявки приходят в СМО на обслуживание в случайные моменты времени. Следовательно, переход СМО из одного состояния в другое есть событие случайное. Пусть - вероятность того, что СМО переходит из состояния E_i в состояние E_j за период времени , причем здесь и всюду в дальнейшем, если только не будет оговорено иное, предполагается именно такая пара состояний (E_i, E_j), которая составляет ребро в графе состояний. Введенные вероятности называются переходными вероятностями СМО.

Если все переходные вероятности не зависят от аргумента , т.е. для всех ребер графа состояний = , то СМО называется стационарной. Всюду в дальнейшем именно такие и только такие СМО будут рассматриваться. Именно для стационарных СМО слова «граф состояний» обозначают не только тот граф состояний, который был введен выше, но еще и совокупность функций ; таким образом, граф состояний (стационарной) СМО - это взвешенный граф, в котором роль графа играет прежний граф состояний, а весовой функцией является функция, сопоставляющая каждому ребру функцию .

Функции называются функциями переходных вероятностей или просто переходными вероятностями; бывает удобным в рассмотрениях следующий объект: матрица переходных вероятностей:

.

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

СМО называется системой без последействия, если функции не зависят от того, как именно СМО попала в состояние E_i. Именно такие СМО рассматриваются в дальнейшем. Таким образом, мы будем обсуждать только стационарные СМО без последействия.

Лекция 7

Основные характеристики СМО. Пуассоновский поток заявок, экспоненциальное время обслуживания.

Рассмотрим теперь величину при . Если эта величина стремится к нулю при для всех i,j таких, что или , то СМО называется ординарной. По смыслу это означает, что в ординарную СМО за короткий промежуток времени не может поступить более одной заявки и из ординарной СМО за короткий промежуток времени не может выйти более одной заявки.

Мы будем в дальнейшем рассматривать только стационарные ординарные СМО без последействия.

Заметим следующее обстоятельство. Пусть - вероятность того, что СМО попадает в течение времени t в состояние E_j и - вероятность того, что в некоторый начальный момент времени СМО была в состоянии E_j. Если обозначить и , то, согласно формуле полной вероятности и правилу умножения матриц, окажется выполненным равенство:

.

Промежуток времени между последовательно поступающими заявками в СМО есть величина случайная. Если функция распределения этой случайной величины имеет вид

при некотором , то поток заявок называется пуассоновским.

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

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

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

Положим и введем матрицу . Число называется интенсивностью перехода СМО из состояния в состояние . Когда , число () называют интенсивностью выхода СМО из состояния . Полезно заметить, учитывая, что при , а при , справедливы неравенства:

при , а при .

Матрица называется матрицей интенсивностей СМО.

Можно доказать, что вероятности , введенные в этой лекции, удовлетворяют системе линейных дифференциальных уравнений

(7.1)

при начальных условиях (здесь ).

Из ординарности СМО следует, что в ее матрице интенсивностей отличными от нуля могут быть элементы только на главной диагонали и на двух ближайших к ней и параллельных ей линиях:

.

Это обстоятельство делает систему уравнений (7.1) более конкретной. В частном случае, например, при пуассоновском потоке входных заявок (можно проверить, что в этом случае СМО будет стационарной, ординарной и без последействия) и полном отсутствии обслуживания (это значит, что заявки только поступают в СМО, но не покидают СМО) матрица A принимает вид

,

после чего система (7.1) решается рекуррентно стандартными средствами. В результате получается ответ:

.

Это означает, что в СМО с пуассоновским потоком заявок и любым режимом обслуживания вероятность поступления k заявок

за время t равна .

Лекция 8

Особенности пуассоновского потока заявок и экспоненциального времени об-служивания. СМО типа (m,n).

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

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

-

функция распределения времени обслуживания (при неотрицательных значениях t, а при отрицательных - она равна нулю), то математическое ожидание времени обслуживания есть число

.



Стандартное интегрирование по частям дает ответ - число . Следовательно, среднее время обслуживания одной заявки равно (при экспоненциальном обслуживании); поэтому в единицу времени (при экспоненциальном обслуживании) в среднем обслуживается заявок.

Рассмотрим теперь следующую модель СМО. Предположим, что ее узел обслуживания имеет n одинаковых устройств и очередная приходящая заявка попадает на любое из этих устройств для обслуживания. Если оказывается, что все устройства заняты, то заявка становится в очередь и ожидает, когда какое-либо устройство освободится. Предположим, что число мест в очереди равно m. Наконец, будем предполагать, что входной по-

ток заявок - пуассоновский с параметром , а время обслуживания - экспоненциальное с параметром . Такие СМО называются СМО типа (m, n).

Граф состояний такой СМО выглядит очень просто:

,

причем около ребер-стрелок в данном случае указаны лишь интенсивности перехода из состояния в состояние.

Лекция 9

Характеристики СМО типа (m,n).

Основной характеристикой СМО типа (m, n) являются вероятности того, что в момент времени t СМО находится в состоянии . Для функций можно построить систему дифференциальных уравнений, допускающую явное решение. В основе соответствующих построений лежат два обстоятельства, на которые мы укажем, но сами построения оставим за пределами данного курса лекций.

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

,

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

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

Если теперь перейти в этих соотношениях к пределу при , то получатся дифференциальные уравнения относительно искомых функций ; вот вид соответствующей системы уравнений:

(9.1)

где A - матрица из констант.

Сформулируем теперь знаменитую теорему о финальных вероятностях, на которой основаны дальнейшие сведения о СМО типа (m, n):

Все функции имеют предел при . Все производные при .

Положим ; числа называются финальными или стационарными вероятностями.

Если в (9.1) перейти к пределу при , то, с учетом теоремы о финальных вероятностях, получим систему линейных алгебраических уравнений относительно финальных вероятностей:

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

Приведем теперь основные характеристики рассматриваемых СМО.

Вероятность того, что в СМО занято обслуживанием ровно k устройств равна , .

Вероятность отказа заявке есть число .

Число занятых устройств в СМО есть, очевидно, величина случайная. Ее математическое ожидание - это среднее число занятых устройств. Оно может быть вычислено и вот результат:

Если - среднее число простаивающих устройств, то, очевидно,

Часто используются коэффициенты простоя и занятости (эти формулы и представляют собой определения):

.

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

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

Среднее число заявок, ожидающих в очереди - величина- может быть вычислено как соответствующее математическое ожидание; вот результат:

Среднее число заявок, поступающих в СМО, - это число

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

И, наконец, последняя характеристика: среднее время пребывания заявки в СМО - число V:



Лекция 10

Эрланговские СМО и СМО с неограниченной очередью, их основные характеристики.

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

Легко заметить, что эрланговские СМО - это СМО типа (m,n) при . Поэтому все рассуждения о СМО типа (m,n) можно адаптировать к этому частному случаю. В этом числе, формулы Эрланга - формулы, выражающие вероятности - можно

получить из формул для финальных вероятностей СМО типа (m,n) при . Вот результат (по-прежнему ):

В частности, вероятность отказа равна , среднее число занятых устройств равно , относительная пропускная способность , абсолютная пропускная способность .

Рассмотрим второй «крайний» случай СМО типа (m,n), когда . Это означает, что очередь может быть как угодно большой. Вероятности имеют здесь смысл при любом целом неотрицательном k. Выражение для можно получить предельным переходом при из выражения для в случае (m,n). Если , то все требования находятся на обслуживании, а очередь пуста; соответствующая вероятность:

при на обслуживании находятся n заявок и k-n находятся в очереди; соответствующая вероятность:

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

;

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

.

Это неравенство называется условием стационарности СМО с ожиданием (не путать с общим понятием стационарности СМО!). Если , то это означает, что СМО не справляется с обслуживанием и очередь всё возрастает.

Если же условие стационарности выполнено, то

.

По смыслу легко заметить, что в рассматриваемых СМО вероятность отказа равна 0, относительная пропускная способность равна 1, абсолютная пропускная способность равна .

Среднее число занятых устройств:

Среднее число простаивающих устройств:

.

Параметр называется уровнем загрузки СМО.

Среднее число требований, ожидающих в очереди в обсуждаемых СМО:



Среднее число заявок, находящихся в СМО:

Среднее время ожидания заявки в очереди:

И, наконец, среднее время пребывания заявки в СМО:

.

Лекция 11

Полипоточные Системы Массового Обслуживания.

Предположим теперь, что в СМО с неограниченной очередью, о которой шла речь в Лекции 10, имеется не один, а несколько входных потоков (все они пуассоновские и каждый имеет свой параметр , так что всего потоков - N) и все потоки имеют экспоненциальное обслуживание, причем коэффициент для го потока есть число . Попадая в СМО, заявки становятся в очередь на обслуживание.

Можно доказать, что в такой ситуации суммарный входной поток в СМО тоже будет пуассоновским с параметром

Можно также доказать, что функция распределения времени обслуживания равна:

.

В теории массового обслуживания имеется следующий фундаментальный результат, называемой формулой Поллачека-Хинчина (в введенных обозначениях):

Среднее время ожидания в очереди в СМО описанного только что типа есть число

где , причем предполагается, что выполнено условие: .

Неравенство называется условием стационарности. Непосредственное интегрирование (по частям) показывает, что

;

полагают , так что и . Кроме того,

.

Полагают , так что формула Поллачека-Хинчина приобретает следующий краткий вид:

.

Легко заметить отсюда, что среднее число заявок i-го потока, ожидающих в очереди, есть величина

;

суммарное число заявок из всех потоков, ожидающих в очереди, равно, следовательно,

.

Лекция 12

Дисциплины очереди в СМО и построение характеристик СМО при различных дисциплинах очереди. Заключительные замечания по теме.

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

Дисциплина очереди «БЕСПРИОРИТЕТНАЯ». Это - самая простая дисциплина. На бытовом языке это - «живая очередь»: заявка, попав в СМО, становится последней в имеющуюся очередь; сама очередь продвигается в естественном порядке - как только узел обслуживания освобождается, первая по очереди заявка поступает на обслуживание, а все остальные заявки в очереди продвигаются на одно место вперед.

Именно для «бесприоритетных» СМО получена формула Поллачека-Хинчина; среднее время ожидания в очереди для заявки в «бесприоритетных» СМО есть число

.

Дисциплина очереди «ОТНОСИТЕЛЬНЫЕ ПРИОРИТЕТЫ». Мы по-прежнему рассматриваем полипоточную СМО с N пуассоновскими потоками; все предыдущие обозначения сохраняют смысл.

Занумеруем имеющиеся потоки числами 1,2,..., N; фиксируем произвольную подстановку

;

число будем называть приоритетом потока номер k; если у одного потока приоритет как число меньше приоритета другого потока, то говорят, что приоритет первого потока выше, чем приоритет другого потока.

Теперь введем следующий порядок установки заявки в очередь. Каждая поступающая в СМО заявка имеет свой приоритет - приоритет своего потока; попав в СМО, она начинает продвигаться по очереди вперед до тех пор, пока не встретит заявку своего же приоритета или заявку более высокого приоритета; столкнувшись с такой заявкой, она становится в очередь непосредственно за ней; если поступившей заявке удалось сразу подойти к узлу обслуживания и он занят, то она дожидается, когда узел освободится и поступает на обслуживание.

Такой порядок организации очереди называется «относительными приоритетами».

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

Будем считать, что потоки занумерованы своими приоритетами. Для каждого k положим ; это число называется загрузкой СМО первыми k потоками; число называется общей загрузкой СМО.

Можно доказать, что при <1 СМО обладает установившимся режимом, т.е. все характеристики СМО обладают ассимтотикой во времени. В частности, среднее время ожидания в очереди заявки приоритета есть число

,

при этом для удобства принимается, что .

Отсюда следует, что среднее время пребывания в СМО заявки приоритета k есть число

.

Среднее число заявок приоритета k, находящихся в очереди, есть

.



Среднее число заявок приоритета k, находящихся в СМО, есть

.

Наконец, общее число заявок, находящихся в СМО, есть

.

И, наконец,

Дисциплина очереди «АБСОЛЮТНЫЕ ПРИОРИТЕТЫ». Эту дисциплину очень легко описать после того, как уже описана дисциплина «относительные приоритеты». А именно, предположим, что входным потокам присвоены приоритеты, т.е. задана подстановка

;

таким образом, потоку номер k сопоставлено число , называемое далее его приоритетом и чем это число меньше, тем приоритет выше. Имеет смысл, следовательно, говорить о заявках более высокого приоритета и о заявках менее высокого приоритета.

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

При такой дисциплине основная характеристика СМО - среднее время ожидания в очереди заявки приоритета k имеет иной вид, чем в случае относительных приоритетов. А именно:

,

где все символы справа имеют тот же смысл, что и при обсуждении относительных приоритетов.

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

Датчик случайных чисел - это компьютерная программа с выходным продуктом в виде сколь угодно большого набора чисел, которые можно интерпретировать как значения случайной величины с конкретным законом распределения. В любом языке программирования имеется макрокоманда, каждый вызов которой дает число из интервала (0,1), но чем больше совокупность таких чисел, тем равномернее расположены они в интервале (0,1); последнее означает, что если (0,1) разбить на любое число равных частей, то количества чисел, поставляемых упомянутой макрокомандой и попадающих в ячейки разбиения, будут все меньше и меньше отличаться друг от друга. В языке БЭЙСИК, например, эта макрокоманда выглядит так: ; и после каждого очередного написания этой команды будет возникать новое число , и совокупность этих чисел будет все равномернее располагаться в интервале (0,1). Этот датчик - имитатор равномерно распределенной в интервале (0,1) случайной величины. Будем в ближайшем тексте условно обозначать символом RND число только что описанной природы.

В теории вероятностей доказывается следующая теорема: если - случайная величина с функцией распределения и - равномерно распределенная случайная величина в интервале (0,1), то случайная величина , получаемая при решении уравнения , в качестве своей функции распределения имеет ту же . Это позволяет создавать на компьютере потоки не только равномерно распределенных в интервале (0,1) чисел, но и произвольным образом распределенных чисел. Простейший пример доставляет экспоненциальное распределение: числа , получаемые из решения уравнения , то есть числа распределены экспоненциально.

Компьютерный имитатор СМО - это компьютерная программа, в которой построено несколько датчиков случайных чисел, значениям которых удается приписать смысл элементов СМО и с помощью которых удается вычислить те или иные характеристики СМО. Вот простейший пример: как найти относительную пропускную способность СМО с единственным входным пуассоновским потоком заявок (с параметром ), с экспоненциальным обслуживанием (с параметром ) и при отсутствии мест для очереди? Обозначим через и через - случайные экспоненциально распределенные числа с коэффициентами и соответственно, обозначим через - период имитации СМО, через - количество обратившихся в СМО заявок на текущий момент времени и через - количество обслуженных заявок на текущий момент времени. В этих обозначениях искомое число есть дробь , причем и должны быть взяты на момент времени =. Обозначим через

момент поступления заявки и через момент выхода заявки после обслуживания. Таким образом, если в исходный момент времени положить =0, то момент поступления каждой очередной заявки есть (здесь и далее = это знак компьютерной операции присвоения), а в случае ее поступления на обслуживание моментом завершения этого обслуживания будет число . Отсюда - следующий алгоритм поведения: вводим в компьютер ; полагаем ; вычисляем и полагаем ; проверяем условие ; если оно выполнено, то полагаем и : если же условие не выполнено (случай потери заявки, так как СМО занята), то переходим снова к подсчету . После вычисления надо проверить условие ; если оно выполнено, то надо перейти к очередному подсчету , а если условие не выполнено, то надо получить искомый результат: .