Метод Хичкока

Для ознакомления с методом Хичкока, проверим решение, полученное методом северо-западного угла (табл. 2.2), на оптимальность (см. табл.2.7). Дополнительный столбец и строка отведены для потенциалов.

Таблица 2.7
ГО	ГП	Итого по вывозу,т	Потен-циалы
В1	В2	В3	В4
А1										-16
А2										-12
А3										-8
Итого по вывозу,т
Потен-циалы		+10		+2

Условимся в дальнейшем называть клетки таблицы, в которых отмечено количество груза, перевозимого от ГО к данному ГП, загруженными. Количество загруженных клеток всегда должно равняться величине базиса, который будет равен п + т- 1 (п - число строк таблицы; т - число столбцов). Если количество загруженных клеток меньше, чем n + т - 1 (случай вырождения), то недостающее число клеток получается путем загрузки соответствующего количества свободных клеток нулями. Клетка, в которой будет проставлена загрузка, равная нулю, считается загруженной.

В данном примере это условие соблюдено: 3 + 4 - 1 =6.

Оценка оптимальности полученного решения:

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

Например, чтобы получить в загруженной клетке А₁В₁ нулевой потенциал, нужно ко всем расстояниям строки А₁ прибавить потенциал -16 (16 - 16 = 0).

В загруженной клетке А₁В₂ нулевой потенциал получится в том случае, если к ее расстоянию 6 и ранее прибавленному по строке А₁ потенциалу -16 прибавить по столбцу В₂ Потенциал +10 (6 - 16 + 10 = 0) и т.д.

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

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

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

Таблица 2.8
ГО	ГП	Итого по вывозу,т
В1	В2	В3	В4
А1			-			-6		-10
			+
А2		-4	+		-
А3		-6			+		-
Итого по ввозу,т

В первом варианте решения нашей задачи отрицательные потенциалы имеются в клетках А₁В₄, А₂В₁, А₁В₃, А₃В₁ (табл. 2.8) т.е. решение неоптимальное.

3. Определяют и загружают наиболее потенциальную клетку - клетку, имеющую наибольшее отрицательное значение потенциала.

В нашем примере это клетка А₁В₄.

Загрузка данной клетки осуществляется перераспределением загрузки клеток таблицы следующим образом:

1. Для наиболее потенциальной клетки строится контур.

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

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

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

3. Выявляют наименее загруженную клетку, занятую (-) углом контура. Количество груза, указанное в этой клетке, отнимается из всех клеток, занятых (-) углами контура, и прибавляется во все клетки, занятые (+) углами.

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

Таблица 2.9
ГО	ГП	Итого по вывозу, т	Потен-циалы
В1	В2	В3	В4
А1										-16
А2										-22
А3										-18
Итого по ввозу, т
Потен-циалы		+20	+10	+12

В табл. 2.8 из всех клеток, занятых (-) углами контура, наименьшую загрузку имеет клетка А1В2 - 200 т. Эти 200 т вычитаются из клеток, занятых (-) углами контура, и прибавляются в клетки, занятые (+) углами. В результате клетка А1В2 становится свободной, а наиболее потенциальная клетка А1В4 получает загрузку в 200 т.

Полученное закрепление ГП за ГО (табл. 2.9) является возможным решением задачи. Общая транспортная работа равна

200*16+200*4+400*2+200*12+600*8+400*6=14400 т*км.

Это на 2000т*км меньше, чем получено в первом варианте решения. Величину сокращения грузооборота можно определить и как произведение количества груза, которое получила наиболее потенциальная клетка, на ее потенциал [200*(-10)] = - 2000 т*км.

Таблица 2.10
ГО	ГП	Итого по вывозу, т
В1	В2	В3	В4
А1	-						+
А2		-14
А3	+	-16					-
Итого по ввозу, т

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

В данном примере второй вариант тоже неоптимальный (табл. 2.10), оптимальный же вариант получен в результате третьего шага решения (табл. 2.11).

Таблица 2.11
ГО	ГП	Итого по вывозу, т	Потен-циалы
В1	В2	В3	В4
А1
А2										-6
А3										-2
Итого по ввозу, т
Потен-циалы		+4	-6	-4

Таблица 2.12
ГО	ГП	Итого по вывозу, т
В1	В2	В3	В4
А1
А2
А3
Итого по ввозу, т

Оптимальность последнего решения подтверждается тем, что в свободных клетках таблицы этого варианта потенциалы являются положительными величинами (табл. 2.12). Объем грузовой работы равен 11200 т*км.