Определение начального решения

Метод северо-западного угла

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

Шаг 1 Переменной х₁₁ присваивается максимальное значение, допускаемое ограничениями на спрос и предложение.

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

Шаг 3 Если не вычеркнута только одна строка или только один столбец, процесс останавливается. В противном случае переходим к ячейке справа, если вычеркнут столбец, или к нижележащей ячейке, если вычеркнута строка. Затем возвращаемся к первому шагу.

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

Таблица 6.2

мельницы		1		2		3		4		предло-
элеваторы										жение
	1		10		2		20		11
		5		10						15
	2		12		7		9		20
				5		15		5		25
	3		4		14		16		18
								10		10
Спрос		5		15		15		15		50

Остальные х _ij =0. Суммарная стоимость перевозок равна

f=5*10+10*2+5*7+15*9+5*20+10*18=520.

Метод минимального элемента

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

Применим метод к нашему примеру 6.1.

1 Ячейка (1,2) имеет наименьшую стоимость (=2). Наибольшее значение, которое можно присвоить переменной х₁₂, равно 15. В этом случае удовлетворяются ограничения, соответствующие первой строке и второму столбцу. Вычеркиваем второй столбец, предложение первой строки и спрос второго столбца принимают нулевые значения.

2 Следующей ячейкой с наименьшей стоимостью в незачеркнутой части таблицы будет ячейка (3,1). Присвоим переменной х₃₁ значение 5 и вычеркнем первый столбец. Ограничение по предложению, соответствующей третьей строке, станет равным 10-5=5.

3 Продолжим процедуру, последовательно присваиваем переменной х₂₃ значение 15, переменной х₁₄ – значение 0; далее находим х₃₄=5 и х₂₄=10.

Процесс поиска начального решения представлен в таблице 6.3. Стрелками показана последовательность присвоения переменным значения.

Таблица 6.3

мельницы		1		2		3		4		предло-
элеваторы										жение
	1		10		2		20		11
				15				0		15
	2		12		7		9		20
						15		10		25
	3		4		14		16		18
		5						5		10
Спрос		5		15		15		15		50

Соответствующее значение целевой функции равно

f=15*2+5*4+15*9+0*11+5*18+10*2 0=475.

Начальное решение, полученное методом минимального элемента, меньше, чем методом северо-западного угла.

Метод потенциалов

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

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

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

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

Решим транспортную задачу из примера 6.1, используя начальное решение, полученное методом северо-западного угла (таблица 6.2).

В методе потенциалов каждой i -й строке и каждому j -му столбцу транспортной таблицы ставятся в соответствие числа (потенциалы или двойственные переменные) u_i и v _j. Для каждой базисной переменной x_ij потенциалы u_i и v _j удовлетворяют уравнению u_i + v_j =c_ij.

В рассматриваемом примере имеем 7 переменных (потенциалов) и 6 уравнений, соответствующих шести базисным переменным. Чтобы найти значения потенциалов из этой системы уравнений, нужно присвоить одному из них произвольное значение (обычно полагают u₁ =0) и затем последовательно вычислять значения остальных потенциалов.

Поскольку для базисных клеток верны равенства u₁+ v ₁ =с₁₁=10 и u₁+ v ₂ =с₁₂=2, то находим, что v₁=10 и v ₂ =2. Далее последовательно находим значения для u₂ из равенства u₂+ v ₂ =с₂₂=7. Оно будет равно u₂=5. Далее легко находим потенциалы v ₃, v ₄ из равенств u₂+ v ₃ =с₂₃=9 и u₂+ v ₄ =с₂₄=20. То есть v ₃ =4 и v₄=15. И последний потенциал u ₃ находим из условия, что u₃+ v ₄ =с₂₄=18. Он равен u ₃ =3.

Теперь вычислим выражения u_i + v_j - c_ij для всех небазисных переменных.

Небазисные переменные	Значения u_i + v_j - c_ij
х₁₃	u₁+v₃-c₁₃=0+4-20=-16
х₁₄	u₁+v₄-c₁₄=0+15-11=4
x ₂₁	u₂+v₁-c₂₁=5+10-12=3
x₃₁	u₃+v₁-c₃₁=3+10-4=9
x₃₂	u₃+v₂-c₃₂=3+2-14=-9
x₃₃	u₃+v₃-c₃₃=3+4-16=-9

Вычисленные значения совместно с нулевыми значениями для базисных переменных (поскольку u_i + v_j - c_ij =0 для любой базисной переменной х _ij) фактически являются коэффициентами z-строки симплекс-таблицы.

базис	x₁₁	x₁₂	x₁₃	x₁₄	x₂₁	x₂₂	x₂₃	x₂₄	x₃₁	x₃₂	x₃₃	x₃₄
z	0	0	-16	4	3	0	0	0	9	-9	-9	0

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

Описанные вычисления обычно выполняются непосредственно в транспортной таблице, как показано в таблице 6.4. Для потенциалов в таблицу добавляем еще один столбец справа и строку снизу. В этом случае нет необходимости в явном виде выписывать уравнения потенциалов. Вычисления в транспортной таблице начинаются с присвоения потенциалу u₁=0. Затем находим v -потенциалы в первой строке. Потом, используя v ₂, находим u ₂ и так далее находим все потенциалы. После этого вычисляем для всех небазисных переменных величины u_i + v_j - c_ij и записываем их в правом нижнем углу соответствующей ячейки транспортной таблицы.

Определив вводимую в базис переменную x₃₁, далее следует определить исключаемую переменную. Для этого строим цикл (маршрут перевозок, начинающийся и заканчивающийся во вводимой переменной). Цикл состоит из последовательности горизонтальных и вертикальных отрезков (но не диагональных), соединяющих ячейки, соответствующие текущим базисным переменным, и ячейку, соответствующую вводимой переменной. При этом все ячейки, в которых делается поворот, меняют значения. В нечетных вершинах цикла увеличиваем на q перевозки, а в нечетных уменьшаем на q. Значение q выбирается так, чтобы одна базисная переменная стала равной нулю там, где отнимается q и в ячейке, вводимой в базис, значение увеличится на q, т.е. она станет базисной.

Таблица 6.4

мельницы		1		2		3		4		предло-
элеваторы										жение
	1	-	10	+	2		20		11		u₁=0
		5		10			-16		4	15
	2		12	-	7		9	+	20		u₁=5
			3	5		15		5		25
	3	+	4		14		16	-	18		u₁=3
			9		-9		-9	10		10
Спрос		5		15		15		15		50
		v₁=10		v₂=2		v₃=4		v₄=15

Понятно, что q надо выбрать как минимум всех стоимостей перевозок с _ij, находящихся на четных вершинах цикла. Тогда выполнятся два условия цикла (маршрута перевозок):

1 Должны выполняться ограничения на спрос и предложение.

2 Ни по какому отрезку маршрута не должны выполняться перевозки с отрицательными объемами грузов.

Подобный цикл представлен в таблице 6.4. Он начинается из ячейки (3,1) и там же заканчивается и перевозит по всем отрезкам цикла 5 единиц груза.

Таблица 6.5

мельницы		1		2		3		4		предло-
элеваторы										жение
	1		10	-	2		20	+	11		u₁=0
			-9	15			-16		4	15
	2		12	+	7		9	-	20		u₁=5
			-6	0		15		10		25
	3		4		14		16		18		u₁=3
		5			-9		-9	5		10
Спрос		5		15		15		15		50
		v₁=1		v₂=2		v₃=4		v₄=15

Цикл проходит через ячейки х₃₁, х₃₄, х₂₄, х₂₂, х₁₂, х₁₁и х₃₁. В каждой ячейке цикла изменяем значения на q =min(x₃₄, х₂₂, х₁₁)=5. В нечетных прибавляем 5 единиц, а в четных ячейках уменьшаем на 5единиц. Получится таблица 6.5.

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

f=15*2+5*4+0*7+15*9+5*18+10*20=475.

В новой транспортной таблице 6.5, используя новые базисные переменные, находим новые потенциалы. Они все будут принимать прежние значения, кроме v₁=1. Находим также в небазисных переменных разности u_i + v_j - c_ij и записываем в правом нижнем углу. Максимальное положительное значение находится в ячейке (1,4) (оно равно +4), следовательно, вводить будем переменную х₁₄. Строим также цикл через ячейки х₁₄, х₁₂, х₂₂ и х₁₄, по которому перебросим 10 единиц груза. В результате получим транспортную таблицу 6.6.

Таблица 6.6

мельницы		1		2		3		4		предло-
элеваторы										жение
	1		10		2		20		11		u₁=0
			-13	5			-16	10		15
	2		12		7		9		20		u₁=5
			-10	10		15			-4	25
	3		4		14		16		18		u₁= 7
		5			-5		-5	5		10
Спрос		5		15		15		15		50
		v₁= -3		v₂=2		v₃=4		v₄=1 1

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

f=5*2+5*4+10*7+15*9+10*11+5*18=435.

Найдем для нового базисного решения потенциалы u _i и v_j. Теперь новые значения величин u_i + v_j - c_ij для всех небазисных переменных х _ij отрицательные. Поэтому решение, представленное в таблице 6.6, оптимально.

На этом вычисления заканчиваются, и выписывается решение транспортной задачи:

От элеватора	До мельницы	Количество зерновозов
1	2	5
1	4	10
2	2	10
2	3	15
3	1	5
3	4	5

Минимальная стоимость перевозок равна 435 тысяч рублей.

Задача о назначениях

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

Возможные применения задачи о назначениях можно видеть в таблице 6.7.

Таблица 6.7

Ресурсы	Объекты	Критерии эффективности
Рабочие	Рабочие места	Время
Грузовые автомобили	Маршруты	Затраты
Станки	Участки	Объем переработанной продукции
Экипажи	Рейсы	Время простоя
Коммивояжер	Города	Товарооборот

Матрица стоимостей имеет вид

где c_ij – затраты, связанные с назначением i -го ресурса на j -й объект, i, j =1,…,n,; n – число объектов или ресурсов.

Обозначим

Таким образом, решение задачи можно записать в виде матрицы

Допустимое решение называется назначением. Оно строится путем выбора ровно одного элемента в каждой строке матрицы Х и ровно одного элемента в каждом столбце этой матрицы.

Математическая постановка задачи:

Задача о назначениях является частным случаем транспортной задачи, в которой а _i =b_j =1 (i =1, …,n; j =1, …,n), поэтому ее можно решить с помощью метода потенциалов. Однако более эффективным является метод, учитывающий специфику математической модели и называемый венгерским методом. Рассмотрим его алгоритм:

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

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

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

Шаг 4 Если после проведения третьего шага решения не будет найдено, то процедуру проведения прямых следует повторять до тех пор, пока не будет получено допустимое решение.

При применении рассмотренного алгоритма нужно иметь в виду следующее:

· если исходная матрица С не является квадратной, то нужно ввести фиктивные ресурсы или фиктивные объекты так, чтобы матрица стала квадратной;

· если какой либо ресурс не может быть назначен на какой-то объект, то соответствующая ему стоимость должна быть выбрана равной достаточно большому значению;

· если исходная задача является задачей максимизации, то все элементы матрицы С следует умножить на (-1) и сложить их с достаточно большим числом так, чтобы матрица не содержала отрицательных элементов. Затем можно решить задачу минимизации;

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

Контрольные вопросы

1 Как открытую транспортную задачу свести к закрытой?

2 Какими методами можно найти начальное допустимое решение для транспортной задачи?

3 Каким образом при решении транспортной задачи методом потенциалов в текущей итерации находят вводимую в базис переменную?

4 Каким образом в транспортной задаче в текущей итерации находят исключаемую из базиса переменную?

5 Можно ли решить задачу о назначениях методом потенциалов?

6 Если при решении задачи о назначениях венгерским методом при вычеркивании нулей окажется, что вычеркнуты все строки и столбцы, что это означает?

Тема 7 Основы сетевого планирования

Основные понятия теории графов

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

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

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

Теория графов оперирует понятием пути, объединяющим последовательность взаимосвязанных ребер. Контур означает такой путь, у которого начальная вершина совпадает с конечной. Сетевой график – это ориентированный граф без контуров. В сетевом моделировании имеются два основных понятия – работа и событие.

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

Фиктивная работа – это связь между результатами работ (событиями), не требующая затрат времени и ресурсов.

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

Путь – это любая непрерывная последовательность (цепь) работ и событий.

Критический путь – это путь, имеющий наибольшую продолжительность по времени; он включает самые напряженные работы комплекса.

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

При построении сетевых моделей необходимо соблюдать следующие правила:

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

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

Рисунок 7.1 Изображение на сетевом графике параллельных работ

3 В сети не должно быть тупиков, т.е. промежуточных событий, из которых не выходит ни одна работа (рисунок 7.2)

Рисунок 7.2 В сетевом графике нет промежуточных событий без продолжения

4 В сети не должно быть промежуточных событий, которым не предшествует хотя бы одна работа (рисунок 7.3).

Рисунок 7.3 В графике нет висячих событий

5 В сети не должно быть замкнутых контуров, состоящих из взаимосвязанных работ, создающих замкнутую сеть (рисунок 7.4).

Рисунок 7.4Не должно быть путей типа k ® j ® s ® k

6 Для правильной нумерации событий поступают следующим образом: нумерация событий начинается с исходного события (в него не входит ни одна работа, таких бывает только одно событие), которому дается номер 1 (рисунок 7.5 а). Из исходного события 1 вычеркиваются все исходящие из него работы; на оставшейся сети вновь находят событие, в которое не входит ни одна работа. Этому событию дается номер 2 (рисунок 7.5 б). Затем вычеркивают работы, выходящие из работы 2, и вновь находят на оставшейся части сети событие, в которое не входит ни одна работа – ему присваивается номер 3 (рисунок 7.5 в), и так продолжается до завершающего события (рисунок 7.5 г).

Рисунок 7.5 а) Рисунок 7.5 б)

Рисунок 7.5 г) Рисунок 7.5 д)

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

После составления списка работ приступают к процедуре построения сетевого графа. Рассмотрим пример составления сетевого графика.