Алгоритм метода потенциалов

1. построение исходного опорного плана;

2. отыскание потенциалов поставщиков и потребителей;

3. проверка полученного плана на оптимальность;

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

Возьмем предыдущую задачу с опорным планом, полученным методом северо-западного угла, добавив строку и столбец дополнительно.

План :

Таблица 5.

поставщики	потребители	запасы
			—
				+,,2-
			+,,2-	—
потребности

План : .

1. Построим систему потенциалов для исходного опорного плана для занятых клеток:

; пусть , тогда: ;

; ;

; ;

; ;

; ;

; .

2. Для незанятых клеток проверим условие оптимальности :

; ;

; ;

; ;

загрузить , т.к. .

3. Для нахождения строим цикл перерасчета – сдвиг цикла на .

(Показано в таблице 5).

План :

Таблица 6.

поставщики	потребители	запасы
потребности

4. .

.

5. Найдем для плана потенциалы для занятых клеток:

; пусть , тогда: ;

; ;

; ;

; ;

; ;

; .

6. Для проверки плана на оптимальность найдем для незанятых клеток: .

;

;

;

;

;

.

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

– необходимо перераспределить.

7. Построим план , введем .

План :

Таблица 7.

поставщики	потребители	запасы
потребности

8. Транспортные издержки:

.

.

9. Запишем систему уравнений для определения потенциалов для занятых клеток:

; пусть , тогда: ;

; ;

; ;

; ;

; ;

; .

10. Проверяем план на оптимальность: найдем для незанятых клеток: .

;

;

;

;

;

.

План оптимален.

Из таблицы 7 выпишем план :

.

11. Так как

,

то план не единственный.

12. Введем перевозку , определим

.

13. Составим еще один оптимальный план .

План :

Таблица 8.

поставщики	потребители	запасы
		—	+
		+	—
потребности

14. Транспортные издержки:

.

Ответ.

Пример 4. Найти оптимальный план этой же транспортной задачи, взяв в качестве первоначального опорного плана, план, полученный методом минимального элемента.

1. План :

Таблица 4.

поставщики	потребители	запасы
		—	+
		+		—
			—	+
потребности

2. Составим систему потенциалов для занятых клеток:

; пусть , тогда: ;

; ;

; ;

; ;

; ;

; .

3. Запишем условие оптимальности для незанятых клеток: .

;

;

;

;

;

.

Т.к. и , то план неоптимален.

4. Введем в опорное решение перевозку , т.к. .

ед. перераспределим по циклу (показано в таблице 4).

5. Составим план :

Таблица 5.

поставщики	потребители	запасы
потребности

6. Составим систему потенциалов для занятых клеток:

; пусть , тогда: ;

; ;

; ;

; ;

; ;

; .

7. Проверим план на оптимальность: найдем для незанятых клеток: .

;

;

;

;

;

.

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

Ответ.

.