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

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

В каждой матрице из данной потенциальной клетки можно провести только один контур.

Потребитель	Вспомога- тельные	Поставщик
Строка   Столбец	А1	А2	А3	Потребность в грузе, т
Б1
434 +		_ (22)
Б2	-11					_
		+ 434
Б3	-4	_
0		(9)		+ 210
Б4	-13
Наличие груза, т

Рисунок 6.-Матрица №6 с нанесённым контуром.

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

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

имелось. Затем из следующей клетки со знаком плюс отнимаем это число и переносим далее по линии контура в клетку со знаком минус и так далее до потенциальной клетки.

Перенесем число 210 из клетки А3Б3 (+) в клетку А3Б2 (-) и добавим ее к той величине, которая в ней имелась. Тогда цифра загрузки в клетке А3Б3 будет равна нулю, а в клетке А3Б3 - 210 единицам. Из клетки А2Б2 (+) отнимаем число 210 и переносим ее в клетку А2Б1 (-), тогда в ней окажется загрузка, равная 210, а в А2Б2 останется 224. Из клетки А1Б1 (+) переносим число 210 в клетку А1Б3 (-).

Новый план закрепления получателей за поставщиками показан на матрице №7 (рисунок 7).

Рисунок 7.-Матрица №7-улучшенный план закрепления получателей за поставщиками.

В результате проведенных действий произошло следующее; при переносе 210 единиц из клетки А3Б3 в клетку А3Б2 расстояние перевозки уменьшилось на 7 км (12-5=7); при переносе числа 210 из клетки А2Б2 в клетку А2Б1 расстояние перевозки уменьшилось на 11 км (17-6 = 11). Из клетки А1Б1 в А1Б3 уменьшилось на 4км (12-8=4).Таким образом, общее уменьшение расстояния перевозки 210 единиц груза составило 7+11+4=22

км, т.е. оно численно равно величине потенциала потенциальной клетки, из которой контур взял свое начало.

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

Продолжаем исследование матрицы №7. Проверяем ее на число загруженных клеток. Оно равно 6, т.е. соответствует правилу, при котором число загруженных клеток должно быть равно 4+3-1=6.

Пользуясь предыдущими правилами, отыскиваем вспомогательные коэффициенты строки и столбца и подставляем их в матрицу. Такими коэффициентами будут :для Б1- 0; Б2-11; БЗ- (-4); Б4-9; А1-12; А2-6; А3-(-6).

Проверяем матрицу на потенциальность и устанавливаем, что в ней имеется две потенциальные клетки: А1Б2; А1Б4; (матрица №8, рисунок 8). Строим контур, который выйдет из клетки А1Б2, т.к. это клетка с наибольшим потенциалом, пойдет в клетки А2Б2, А2Б1, А1Б1 и замкнется в клетке А2Б2. На вершинах контура проставляем знаки минус и плюс, причем первый минус ставится в потенциальной.

Потребитель	Вспомога- Тельные	Поставщик
Строка Столбец	А1	А2	А3	Потребность в грузе, т
		-6
Б1				_
224+
Б2	-11
(10) _		+ 224
Б3	-4
Б4
(9)
Наличие груза, т

Рисунок 8.-Матрица №8- с нанесенным контуром

В результате проведенных действий произошло следующее; при переносе 224 единиц из клетки А2Б2 в клетку А2Б1 расстояние перевозки уменьшилось на 11 км (17-6=11); при переносе числа 224 из клетки А1Б1 в клетку А1Б2 расстояние перевозки увеличилось на 1 км (12-13=-1). Таким образом, общее уменьшение расстояния перевозки 224 единиц груза составило 11-1=10 км, т.е. оно численно равно величине потенциала потенциальной клетки, из которой контур взял свое начало.

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

Продолжаем исследование матрицы №8. Проверяем ее на число загруженных клеток. Оно равно 5, т.е. не соответствует правилу, при котором число загруженных клеток должно быть равно 4+3-1=6. Вводим нулевую загрузку в А1Б4.

Пользуясь предыдущими правилами, отыскиваем вспомогательные коэффициенты строки и столбца и подставляем их в матрицу. Такими коэффициентами будут для Б1- 0; Б2-10; БЗ-5; Б4-9; А1-3; А2-6; А3-(-5).

Новый план закрепления получателей за поставщиками показан на матрице №9 (рисунок 9).

Рисунок 9.-Матрица №9-оптимальный план закрепления получателей за поставщиками.

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

1. Поставщик А1 будет поставлять продукцию потребителю Б3 в количестве 210 единиц на расстояние 8 км и потребителю Б2 в количестве 224 единицы на расстояние13 км;

2. Поставщик А2 будет поставлять продукцию потребителю Б1 в количестве 434 единицы на расстояние 6 км и потребителю Б4 в количестве 196 единицы на расстояние15 км;

3. Поставщик А3 будет поставлять продукцию потребителю Б2 в количестве 210 единиц на расстояние 5 км

Расшифрованный оптимальный план перевозок передают в диспетчерскую для определения дневных заданий шоферам и выписки путевых листов.

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

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

, (9)

где Q – количество перевозимого груза, указанного в клетке рассматриваемой матрицы, т;

- расстояние между поставщиком и получателем, соответствующие грузу Q, км.

Уменьшение среднего расстояния перевозки в процентах определяется:

, (10)

где и - среднее расстояние перевозки, соответственно, при первичном и улучшенном плане закрепления получателем за поставщиками, км

При первичном плане закрепления получателей за поставщиками среднее расстояние перевозки

;

при вторичном плане

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

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

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

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

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