Нахождение опорного решения методом северо-западного угла.

Исходные данные занесем в упрощенную таблицу

 

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

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

Северо-западный угол таблицы – это её левый верхний угол, т.е. клетка в 1-й строке и 1-м столбце – клетка (1, 1). Поэтому рассмотрим 1-го поставщика и 1-го потребителя. У поставщика А1 есть 30 единиц груза, а потребителю В1 нужно 70 единиц. Находим минимум из этих двух чисел: min (30, 70) = 30. Клетка (1, 1) перечеркивается по диагонали сплошной чертой ( ), по центру пишется найденный минимум 30. Это означает, что А1 должен поставить потребителю В1 30 единиц груза. Такие клетки в дальнейшем будем называть отмеченными.

Так как поставщик А1 израсходовал все свои 30 единиц груза, то мы исключаем его из рассмотрения. Поэтому все остальные клетки 1-й строки перечеркиваем по диагонали. Такие клетки в дальнейшем будем называть пустыми.

После первого шага наша таблица имеет следующий вид:

	304

 

Первая строка в дальнейшем не рассматривается.

Северо-западный угол этой таблицы – это клетка (2, 1). Поэтому рассмотрим 2-го поставщика и 1-го потребителя. Мощность поставщика А2 равна 190 единиц. Спрос потребителя В1 – 70 единиц груза. Но 30 единиц груза он получил от поставщика А1 (об этом говорит отмеченная клетка (1, 1)). Поэтому непокрытый спрос потребителя В1 равен 70–30=40. Находим минимум min (190, 70-30)=40. Клетка (2, 1) становится отмеченной. Мы запишем там этот минимум 40.

Поставщик А1(30 единиц) и А2 (40 единиц) полностью покрывают спрос потребителя В1 (70 единиц). Поэтому остальные клетки 1-го столбца объявим пустыми и в дальнейшем исключим из рассмотрения.

После второго шага таблица имеет следующий вид:

 

	304
	403	1

 

Северо-западный угол этой таблицы – это клетка (2, 2). min (190-40, 120)=120.

Получаем следующую таблицу:

	304
	403	1201

 

Северо-западный угол этой таблицы – это клетка (2, 3). min (190-40-120, 150)=30. Получаем следующую таблицу:

	304
	403	1201	302

 

Северо-западный угол этой таблицы – это клетка (3, 3). min (250, 150-30)=120. Получаем следующую таблицу:

	304
	403	1201	302
			1203

 

Осталась одна незаполненная клетка – это клетка (3, 4). min (250-120, 130)=130. Получаем следующую таблицу:

 

	304
	403	1201	302
			1203	1307

После выполнения очередного шага мы исключали из рассмотрения либо строку, либо столбец. Только на последнем шаге отпали и строка, и столбец. Поэтому для полностью заполненной таблицы должно соблюдаться следующее отношение: число отмеченных клеток = число строк +число столбцов – 1. В нашем случае это так: 6=3 + 4 – 1.

Посчитаем суммарные затраты. Для этого нужно в каждой отмеченной клетке перемножить ее числа и результаты сложить: 4*30+3*40+1*120+2*30+3*120+7*130=1690.

Нахождение опорного решения методом минимального тарифа (минимальной стоимости)

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

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

Рассмотрим нахождение исходного опорного решения транспортной задачи на конкретном примере.

 

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

Шаг 1. Среди всех незаполненных клеток у клетки (2, 2) наименьшая стоимость перевозки груза – 1. Поэтому делаем поставку в эту клетку min (190, 120)=120. Исключаем 2-й столбец как полностью «удовлетворенный».

		1201

 

Шаг 2. Среди всех незаполненных клеток у клеток (1, 3) и (2, 3) наименьшая стоимость перевозки единицы груза – 2. Для клетки (1, 3) min (30, 150)=30. Для клетки (2, 3) min(190-120, 150)=70. Выбираем ту клетку, куда можно сделать наибольшую поставку. Так как 70> > 30, то это клетка (2, 3). Исключаем 2-ю строку как полностью «использованную»:

		1201	702

 

Среди всех незаполненных клеток у клетки (1, 3) наименьшая стоимость перевозки единицы груза – 2. min (30, 150 – 70)=30. Исключаем 1-ю строку как полностью «использованную»:

			302
		1201	702

И т.д. Окончательный вариант:

			302
		1201	702
	705		503	307

 

Число отмеченных клеток = число строк + число столбцов – 1: 6=3+4–1.

Стоимость перевозки равна: 2*30+1*120+2*70+5*70+3*50+7*130=1730.

Нахождение опорного плана методом Фогеля.

Метод Фогеля предусматривает введение штрафов строк (d_i) и штрафов столбцов (d_j). Каждый штраф определяется как разность между минимальным элементом рассматриваемой строки (столбца) и следующим по величине. Вычеркнутые строки и столбцы в рассмотрение не принимают. Перевозку осуществляют в клетку, лежащую на строке (в столбце) с максимальным штрафом и имеющую минимальную стоимость перевозки. Далее при необходимости реализуют вычёркивание строк и столбцов, и все штрафы пересчитываются заново. Алгоритм заканчивается, когда все перевозки реализованы.

Шаги алгоритма представлены ниже.

Шаг 1. Рассчитываем штрафы строк и столбцов:

 

Потреб.   Поставки	В1	В2	В3	В4
				di
А1		4	7	2	3	3-2=1
А2		3	1	2	4	2-1=1
А3		5	6	3	7	5-3=2
	dj	4-3=1	6-1=5	3-2=1	4-3=1

 

Максимальный штраф в столбце 2. Минимальный элемент этого столбца – 1. Загружаем его максимально возможным количеством груза – 120.

Получаем следующую таблицу:

 

Потреб. Поставки	В1	В2	В3	В4
А1		4	7	2	3
А2		3	120 1	2	4
А3		5	6	3	7

 

Шаг 2. Убираем столбец 2, одновременно уменьшаем количество груза у второго поставщика (строка 2) на 120 единиц и пересчитываем штрафы.

 

Потреб. Поставки	В1	В3	В4
			di
А1		4	2	3	3-2=1
А2		3	2	4	3-2=1
А3		5	3	7	5-3=2
	dj	4-3=1	3-2=1	4-3=1

 

Загружаем клетку с тарифом 3 в строке 3 максимально возможным количеством груза – 150, получаем таблицу:

 

 

Потреб. Поставки	В1	В3	В4
А1		4	2	3
А2		3	2	4
А3		5	150 3	7

Шаг 3. Убираем отмеченный столбец, одновременно уменьшаем количество груза у третьего поставщика на 150 и пересчитываем штрафы.

 

Потреб. Поставки	В1	В4
		di
А1		4	3	4-3=1
А2		3	4	4-3=1
А3		5	7	7-5=2
	dj	4-3=1	4-3=1

 

Загружаем клетку А₃В₁ 70 единицами груза, получаем:

 

Потреб. Поставки	В1	В4
А1		4	3
А2		3	4
А3		705	7

 

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

 

 

Потреб.   Поставки	В4
А1		30 3
А2		70 4
А3		307

 

В итоге получаем опорный план:

Потреб. Поставки	В1	В2	В3	В4
А1		4	7	2	303
А2		3	120 1	2	70 4
А3		70 5	6	150 3	307

Стоимость перевозки – 1500.

Кроме вышерассмотренных методов существуют и другие приёмы составления опорного плана:

· метод двойного предпочтения;

· метод минимальной стоимости по столбцу или строке и др.

· метод дфференциальных рент и др.

Вырожденность в транспортных задачах.

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

Рассмотрим вырожденность транспортной задачи на примере.

Воспользуемся методом северо-западного угла.

Шаг 1. Клетка (1, 1). min (50, 30)=30. Исключаем 1-й столбец:

 

	30 1

 

Шаг 2. Северо-западной клеткой является клетка (1, 2). min (50-30, 20)=20. Мы видим, что выпадают 1-я строка, и 2-й столбец. Это приводит к невыполнению соответствия: число отмеченных клеток = число строк + число столбцов -1. Поэтому помимо клетки (1, 2) мы объявляем отмеченной еще одну клетку в 1-й строке или 2-м столбце. Делаем туда так называемую нулевую поставку, т.е. 0. Пусть это будет клетка (2, 2).

 

 

	301	203
		03

 

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

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

⇐ Предыдущая78910111213141516Следующая ⇒

Поделиться: