Второй способ (метод Креко )

Прием нахождения потенциалов для свободных клеток методом Креко отличается от рассмотренного выше.

На основании исходных данных задачи так же, как и при первом способе решения, составляется таблица и указывается по диагонали первое распределение груза (табл. 7). Определение оптимального решения начинается с построения контуров для всех свободных клеток. Расстояниям, указанным в клетках положительных углов контура, придается знак плюс, а расстояниям отрицательных углов - знак минус. Алгебраическая сумма расстояний, стоящих в клетках всех углов контура, будет потенциалом свободной клетки. Так, у контура свободной клетки А₂В₁; отрицательные углы будут расположены в клетках А₁B₁, А₂В₂, положительные - в клетках А₂В₁, A₁B₂. Ее потенциал будет -16-2+8+6 = -4.

У контура клетки А₃В₁, отрицательные углы будут находиться в клетках A₁B₁, A₂B₂, A₃B₃, положительные - в клетках А₃В₁, А₂В₃, А₁В₂. Потенциалом этой клетки будет сумма: -16-2-8+2+12+6 = -6 и т.д.

Найденные таким путем потенциалы записывают в левых верхних углах свободных клеток. При решении задачи на минимум оптимальный вариант будет в том случае, когда потенциалы всех свободных клеток станут положительными величинами. Если же есть отрицательные значения потенциалов, то выявляется наиболее потенциальная клетка (в нашем примере такой клеткой будет клетка А₁В₄) и по ее контуру (см. табл. 7), соблюдая указанные ранее правила, делают перераспределение груза.

Таблица 7

Грузообразующие точки	Грузопоглощающие точки									Итого по вывозу, т
	B1		B2	B3					B4
A1	16 200		- 6 200	6 10					10 + 4	400
A2	4 8		+ 2 200	- 12 400					14	600
A3	6 2		18	+ 8 400					6600-	1000
Итого по ввозу, т	200		400	800					600	2000

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

Таблица 8

Грузообразующие точки	Грузопоглощающие точки									Итого по вывозу, т
	B1		B2		B3				B4
A1	16 200 -		10 6		10				4200+	400
A2	14 8		2 400		12 200				14	600
A3	16 2 +		0 18		8 600				6400-	1000
Итого по ввозу, т	200		400		800				600	2000

Таблица 9

Грузообразующие точки	Грузопоглощающие точки					Итого по вывозу, т
	B1		B2	B3	B4
A1	6 16		0 6	10	4400	400
A2	1 8		2 400	12200	414	600
A3	2 200		0 18	8600	6200	1000
Итого по ввозу, т	200		400	800	600	2000

4. третий способ (модифицированный распределительный метод -МОДИ, или метод потенциалов)

Условие задачи записано в табл. 10. Первое распределение груза производится по диагональному методу. Для оценки оптимальности решения подбираются по т енциалы следующим образом.

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

L_ij = N_i + M_j ,

где N_i - потенциал строки; М_j- потенциал столбца.

Так, если для первой строки таблицы взят потенциал, равный нулю, то потенциал столбца В₁ будет равен 16, так как разность между расстоянием загруженной клетки А₁В₁ и потенциалом первой строки равна 16 (16 - 0 = 16). Потенциал второго столбца В₂ будет равен 6 (6 - 0 = 6), так как расстояние загруженной клетки А₁В₂ равно 6. Тогда потенциал строки А₂ будет определен по расстоянию загруженной клетки А₂В₂ и найденному потенциалу столбца В₂ (2 - 6 = -4). Потенциал столбца В₃ определяется через расстояние загруженной клетки А₂В₃ и найденный потенциал второй строки А₂: 12 - (-4) =16. Таким же образом находятся потенциалы строки А₃ и столбца В₄.

Таблица 10

Грузообразующие точки	Потенциал	Грузопоглощающие точки							Итого по вывозу, т
		B1		B2		B3	B4
		16		6		16	14
A1	0	16 200		- 6 200		10	+ 4		400
A2	-4	8		+ 2 200		- 12400	14		600
A3	-8	2		18		+ 8400	- 6 600		1000
Итого по ввозу, т	200	400		800		600	2000

Если число загруженных клеток будет меньше, чем m + n - 1, то потенциалы для некоторых строк и столбцов невозможно определить. Чтобы устранить это препятствие, недостающее количество клеток, как и в предыдущих способах, загружают нулями. Загружать нулями следует те клетки, которые лежат на пересечении строк или столбцов, не имеющих потенциалов, со столбцами или строками, для которых они уже определены. При этом наиболее целесообразно выбрать из этих клеток такие, в которых имеются наименьшие расстояния. Клетки, загруженные пулями, рассматриваются как обычные загруженные клетки. После того как будут найдены потенциалы, определяют их сумму для каждой свободной клетки.

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

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

Клеткой, обладающей наибольшим потенциалом при решении задачи на минимум, является клетка, у которой имеется наибольшая разность между суммой потенциалов и расстоянием, проставленным в клетке. В нашем примере такой клеткой является клетка А₁В₄ (см. табл. 10). Ее потенциал равен 10 (14 - 4 = 10). Перераспределение загрузок по ее контуру дает новый вариант решения задачи (табл. 11), который не является еще оптимальным. В этом варианте наиболее потенциальной будет клетка А₃В₁. Ее потенциал равен 16(18-2= 16). Перераспределение загрузки по контуру клетки А₃В₁ позволяет найти оптимальное решение задачи (табл. 12).

Таблица 11

Грузообразующие точки	Потенциал		Грузопоглощающие точки						Итого по вывозу, т
			B1	B2		B3	B4
			16	-4		6	4
A1	0		- 16200	6		10	+ 4 200		400
A2	6		8	2 400		12200	14		600
A3	2		+ 2	18		8600	6 400-		1000
Итого по ввозу, т	200		400	800		600	2000

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