5. 2.3 Определение начального плана транспортировок. Методы "северо-западного" угла, минимального элемента, Фогеля

Рассмотрим три метода нахождения начального решения транспортной задачи: метод "северо-западного" угла, метод минимального элемента и метод Фогеля.

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

Шаг 1. Составляют транспортную таблицу.

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

Пример 2.3.1

Определить начальное решение по методу "северо-западного" угла для транспортной задачи из примера 2.1.1. Транспортная таблица имеет следующий вид (табл. 2.3.1):

Таблица 2.3.1

№	1	2	3	4	Предложение
1	7 120	8 40	1	2	160
2	4	5 10	9 130	8	140
3	9	2	3 60	6 110	170
Спрос	120	50	190	110

В первую клетку помещают . Спрос первого потребителя полностью удовлетворен, первый столбец вычеркивают. Остаток сырья в первом пункте составляет: усл. ед. Двигаемся по первой строке вправо . Предложение поставщика исчерпано, первая строка вычеркивается. Второму потребителю не хватает 50-40=10 усл. ед. Двигаемся по второму столбцу вниз ; Второй столбец вычеркивается. Двигаемся по второй строке вправо . Вторая строка вычеркивается. Двигаемся по третьему столбцу вниз . Спрос третьего потребителя удовлетворен. Двигаемся по третьей строке вправо . Таблица заполнена. Число ненулевых значений , равно 6. Число базисных переменных задачи 3+4-1=6. Остальные переменных являются свободными, их значения равны нулю.

Начальный план перевозок имеет вид:

Стоимость перевозок по этому плану составляет .

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

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

Шаг 1. Составляют транспортную таблицу.

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

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

Если все клетки заполнены или вычеркнуты, то план перевозок построен. В противном случае переходят к шагу 2 без учета заполненных и вычеркнутых клеток.

Пример 2.3.2

Определить начальное решение по методу минимального элемента для транспортной задачи из примера 2.1.1.

Таблица 2.3.2

№	1	2	3	4	Предложение
1	7	8	1 160	2	160
2	4 120	5	9	8 20	140
3	9	2 50	3 30	6 90	170
Спрос	120	50	190	110

Минимальный тариф . Первую строку вычеркивают. Минимальный тариф для оставшихся клеток . Второй столбец вычеркивают.

Для оставшихся клеток минимальный тариф . Третий столбец вычеркивают.

Для оставшихся клеток минимальный тариф . Первый столбец вычеркивают.

Для оставшихся клеток минимальный тариф . Для одной оставшейся клетки .

План перевозок, полученный по методу минимального элемента, имеет вид:

Стоимость перевозок по этому плану составляет .

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

Метод Фогеля.

Шаг 1. Составляют транспортную таблицу.

Шаг 2. Для каждой строки и каждого столбца транспортной таблицы определяют разность между наименьшим тарифом и ближайшим к нему значением. Переход к шагу 3.

Шаг 3. В строке или в столбце, которым соответствует наибольшая разность, выбирают клетку с наименьшим тарифом. Переход к шагу 4.

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

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

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

Пример 2.3.3

Определим начальное решение по методу Фогеля для транспортной задачи из примера 2.1.1.

Таблица 2.3.3

№	1	2	3	4	Предложение	Разность по строкам
1	7	8	1 160	2	160	1	6	—	—
2	4 120	5	9	8 20	140	1	1	1	1
3	9	2 50	3 30	6 90	170	1	1	1	7
Спрос	120	50	190	110
Разность по столбцам	3	3	2	4
	3	3	2	—
	5	3	6	—
	5	3	—	—

Разности по строкам будем записывать в правой части таблицы 2.3.3, разности по столбцам — внизу таблицы 2.3.3. Наименьший тариф в первой строке равен 1. Ближайший к нему равен 2. Разность равна 1. Наименьший тариф во второй строке 4. Ближайшее к нему значение 5. В третьей строке 2 и 3 соответственно. Разности по всем строкам равны 1.

В первом столбце наименьший тариф . Ближайшее значение . Во втором столбце наименьшее значение . Ближайшее значение .

Третий столбец: .

Четвертый столбец: .

Максимальная из всех разностей 4 находится в четвертом столбце. В этом столбце клетка с наименьшим тарифом находится в первой строке. В эту клетку помещаем максимально возможное значение: . Четвертый потребитель полностью удовлетворил свой спрос, и четвертый столбец вычеркиваем.

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

Первая строка: минимальный тариф . Ближайшее значение .

Вторая строка: минимальный тариф . Ближайшее значение .

Третья строка: .

Первый столбец: минимальный тариф . Ближайшее значение .

Второй столбец: минимальный тариф . Ближайшее значение .

Третий столбец: минимальный тариф . Ближайшее значение .

Максимальная разность равна 6 и стоит в первой строке. Минимальный тариф в первой строке . В эту клетку помещаем . Вычеркиваем первую строку. Повторяем все действия без учета первой строки и четвертого столбца.

Вторая строка: .

Третья строка: .

Первый столбец: .

Второй столбец: .

Третий столбец: .

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

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

Вторая строка: .

Третья строка: .

Первый столбец: .

Второй столбец: .

Максимальная разность стоит в третьей строке. Минимальный тариф в этой строке .

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

Полученный по методу Фогеля план перевозок имеет вид:

.

Затраты на перевозку по этому плану составляют:

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