Исследование операций / ИСО Учебник

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

′	′	′	> c1 j1	+c2 j2	+... +cnjn ,
c1 j1	+c2 j2	+... +cnjn

а это противоречит тому, что для задачи с матрицей С выбор

(1, j1), (2, j2), …, (n, jn) — оптимальный.

Так как свойство эквивалентности матриц взаимное, то так же доказывается, что любой оптимальный выбор задачи с матрицей D является и оптимальным выбором задачи с матрицей С. Теорема доказана. ■

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

Нам будет удобно предварительно перейти от данной задачи выбора на максимум к задаче выбора с теми же условиями, но на минимум, т. е. от матрицы С = (сij) перейти к матрице С = (–cij) и искать выбор, дающий минимальную сумму элементов.

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

121

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

С = (сij ) (1)→C1 = (cij′ ) = (max cij −cij ) (2)→D = (dij ) = (cij′ −min cij′ ) .

Назовем эти преобразования предварительными. Если в каждой строке матрицы С1 = (сij′ ), полученной после первого преобразования матрицы С,

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

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

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

1.Отмечаем (например, звездочкой) какой-нибудь нуль в первом столбце матрицы D, (0*); отмечаем звездочкой какой-нибудь нуль во втором столбце, не лежащий в той строке, в которой находится 0* из первого столбца (если такой нуль во втором столбце найдется); отмечаем звездочкой один из нулей третьего столбца, лежащий в строке, где нет еще нулей со звездочкой (если такой нуль в третьем столбце найдется); и так далее, пока не пройдем все столбцы матрицы. Если число отмеченных звездочкой нулей равно n, то процесс окончен: места, занимаемые нулями со звездочкой, соответствуют n переменным xij , равным 1, в оптимальном решении исходной задачи. Если нулей со звездочкой меньше n, то поступаем следующим образом:

122

2.Помечаем (например, знаком «+» сверху) столбцы матрицы, в которых есть 0*, и считаем эти столбцы занятыми. В ходе процесса будут появляться и занятые строки. Элементы, стоящие на пересечении незанятого столбца и незанятой строки, будут считаться незанятыми, остальные элементы – занятыми. Если в матрице нет незанятых нулей, то переходим к п. 5. Если незанятые нули есть, то выбираем первый из них (просматривая поочередно строки матрицы слева направо). Отмечаем его каким-нибудь промежуточным значком (например, штрихом — 0′). Если в его строке нет нуля со звездочкой, то переходим к п. 4; если в его строке 0* есть, то делаем следующее:

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

4.Начиная с только что отмеченного 0′, строим цепочку из нулей: от этого 0′, по столбцу к 0*, от него по строке к 0′ и т. д., пока это возможно. Цепочка оборвется (может быть, на первом же 0′) на некотором 0′. Снимаем звездочки у нулей из цепочки и заменяем звездочками штрихи у нулей из цепочки. Новый набор нулей со звездочками содержит на один больше чем предыдущий и является также правильным. Снимаем все пометки, кроме звездочек, и возвращаемся ко второй части п. 1.

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

123

Пример. Найти оптимальный вариант назначений, если матрица эффективностей такова:

	2	3	3	5	4
	4	2	4	6	2
С=	2	2	2	4	3
	4	3	4	3	5
	0	1	0	2	0

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

Процесс окончен, так как получилось n = 5 нулей со звездочкой. Оптимальный вариант назначений: x15=x24=x31=х43=x52=1, остальные хij=0, т. е. первый механизм назначается на пятую работу, второй — на четвертую, третий — на первую, четвертый — на третью, пятый — на вторую.

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

	2	3		3	5		4					2 0 1 1 1
	4	2		4	6		2						0		1 0 0			3
	2	2		2	4		3	(1)					2		1	2 2		2		(2)
								→												→
	4	3		4	3		5						0		0 0 3			0
	0	1		0	2		0						4		2 4 4			5
	2 0* 1					1			1			1 0* 0΄							0	0
	0* 1			0		0΄ 3								0* 2			0 0΄			3
	1 0			1		1			1		→			0΄		0	0 0			0		→
	0΄		0	0* 3					0					0΄		1	0* 3			0
	2 0			2		2			3					1 0			1 1			2

124

	1	0* 0		0	0				1	0	0	0	0*
	0	2	0	0* 3					0	2	0	0* 3
							→
→	0*	0΄	0	0	0				0*	0	0	0	0
							результат
	0΄	1	0* 3		0				0	1	0* 3		0
	1	0΄	1	1	2				1	0* 1		1	2

Общая модель целочисленной задачи и метод Гомори для её решения

Задача о назначениях относится к частному случаю задачи целочисленного программирования.

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

n

∑ aij x j = bi , i =1, m , найти решение х=(х1,х2,..., xn), при котором максимизи-

j =1

руется значение функции

n

F(x) = ∑cj xj и при этом хj — целое (j=1, n ).

j=1

Метод Гомори

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

n

∑ f (aij* ) xj ≥ f (bi* )

j=1

инаходят решение задачи, сформулированной выше. В данном неравенстве aij* и bi* — преобразованные исходные величины aij и bi , значения которых

125

взяты из последней симплекс-таблицы, а f (aij* ) и f (bi* ) — дробные части

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

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

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

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

3.Используя метод искусственного базиса, находят решение задачи, получающейся в результате присоединения дополнительного ограничения.

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

126

Условие неразрешимости линейной задачи в целых числах

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

127

Лекция 2.2.4. Теория массового обслуживания: основные понятия, определения, теоремы

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

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

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

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

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

128

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

одноканальные и многоканальные (рис. 2.6).

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

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

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

Результирующие показатели или интересующие характеристики СМО — показатели эффективности, которые описывают, способна ли данная система справляться с потоком заявок. В качестве них используются: среднее число заявок, обслуживаемых в единицу времени; среднее число заявок в очереди; среднее время ожидания обслуживания; вероятность отказа в обслуживании без ожидания; вероятность того, что число заявок в очереди превысит определенное значение, и т. п.

129

Рис. 2.6. Классификация систем массового обслуживания

130