Решение транспортной задачи методом потенциалов

Первоначальный план, выбранный по методу минимальной стоимости.

В нем число занятых клеток равно 7, а .

Следовательно, план вырожденный.

Для дальнейшего решения нужно сделать одну клетку фиктивно (условно) занятой.

Выбираем клетку и в нее записываем ноль.

(Целесообразно выбрать клетку с min стоимостью)

Таблица будет иметь другой вид:

Матрица перевозок	Потребители	Запасы
Поставщики
		-	-	-		-
			- 7 50	10 -	+ 6 -	11 -
		-	-	-	- 2 -	200 +
		-	150 +		-	50 -
Потребности

ед.

Расчет системы потенциалов

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

Выбираем строку с наибольшим количеством занятых клеток. Это строка А 4.

Пусть тогда

клетка А 4 В 2: следовательно

клетка А 4 В 3: следовательно

клетка А 4 В 5: следовательно

клетка А 3 В 5:

клетка А 3 В 4:

клетка А 1 В 4:

клетка А 2 В 2:

клетка А 2 В 1:

далее проверяем план на оптимальность по свободным клеткам (Теорема для свободных клеток)

клетка А 1 В 1: ДА

клетка А 1 В 2: ДА

клетка А 1 В 3: ДА

клетка А 1 В 5: ДА

клетка А 2 В 3: тогда рассчитываем разность потенциалов:

клетка А 2 В 4:

клетка А 2 В 5:

клетка А 3 В 1: ДА

клетка А 3 В 2: ДА

клетка А 3 В 3: ДА

клетка А 4 В 1: ДА

клетка А 4 В 4: ДА

Из трех цифр и выбираем самое большое .

С нее будем начинать цикл. Цикл строим по занятым клеткам. Затем выбираем количество груза, которое нужно перераспределить . Там где знак «+» прибавляем 0, там где «-» отнимаем.

Строим новую таблицу. И снова рассчитываем систему потенциалов.

Матрица перевозок	Потребители	Запасы
Поставщики
		-	-	-	- 1	+ 4 -
			- 7 50	10 -	+ 6 -	11 -
		-	-	-	-
		-	150 +		-	50 -
Потребности

Клетка А 2 В 4 была свободной, а стала занятой, следовательно, должно измениться либо либо .

Изменим так как его изменение приведет к меньшим пересчетам.

Пусть осталось равным -1 клетка А 2 В 4: , клетка А 1 В 4:

Проверим по занятым клеткам правильность расчетов системы потенциалов.

Клетка А 2 В 1: .

Все верно.

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

клетка А 1 В 1: ДА

клетка А 1 В 3:

клетка А 1 В 5:

клетка А 2 В 3:

самая большая величина. С этой клетки начинаем цикл .

Матрица перевозок	Потребители	Запасы
Поставщики
		-	-	+ 4 -	- 1
			- 7 0	-	+ 6	-
		-	-	3 -	-
		-	200 +	100 -	-	-
Потребности

Клетка А 1 В5 была свободной, а стала занятой, следовательно, должно измениться либо либо .

Изменим / так как его изменение приведет к изменению только .

Пусть осталось равным -6 клетка А1В5: , клетка А3В5:

Проверим по занятым клеткам правильность расчетов системы потенциалов.

Все верно.

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

Условие нарушено в трех клетках.

клетка А 1 В 3:

клетка А 2 В 3:

клетка А3В 3:

самая большая величина. С этой клетки начинаем цикл .

Матрица перевозок	Потребители	Запасы
Поставщики
		-	-
			-	-		-
		-	-	-	-
		-		100 -	-	-
Потребности

Клетка А 1 В3 была свободной, а стала занятой, следовательно, должно измениться либо либо .

Изменим , так как его изменение приведет к меньшим изменениям.

Пусть осталось равным -6 клетка А1В3: ,

клетка А4В3: ,

клетка А4В2: .

Проверим по занятым клеткам правильность расчетов системы потенциалов.

Все верно.

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

Условие выполняется во всех клетках. План оптимальный.

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

Z=0*4+50*1+50*4+200*2+50*6+200*2+200*8+100*12+4150