Техника решения транспортной задачи вручную

(МЕТОД ПОТЕНЦИАЛОВ)

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

Сумма потенциалов строки и столбца должна быть равна показателю оптимальности c_ij, т.е.

где - потенциал строки;

- потенциал столбца;

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

Рассмотрим технику транспортной задачи вручную на конкретном примере, заданном таблицей.

 

	D1	D2	D3	D4	D5	Мощность
S1
S2
S3
S4
Спрос

 

Решение:

1.Составляем первый опорный план методом Северо-Западного угла.

 

	D1	D2	D3	D4	D5	Мощность
S1
S2
S3
S4
Спрос

 

Целевая функция для этого плана F=1880.

2. Определяем потенциалы из первого опорного плана для заполненных клеток.

 

u v	4=5-1	1=7-6	3=9-6	1=4-3	9=12-3
6=10-4
3=6-3
-5=4-

 

Значения в выделенных клетках переносятся из условий задачи и равны c_ij.

3. Заполняем свободные клетки таблицы потенциалов.

Рассмотрим более подробно фрагмент:

 

u v
		2 -6

 

 

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

Если Е<0 для всех свободных переменных, то исходный план определяет оптимальное решение.

Если Е>0, то можно путем перераспределения поставок улучшить значение функции цели (F). Для этого следует отметить, что перераспределение поставок цепи к этой клетке уменьшает функционал (в расчете на единицу перераспределяемой продукции) на величину характеристики (Е).

Вся таблица имеет вид

		D1	D2	D3	D4	D5
	u v
S1			2 8	4 3	2 10	10 4
-6		-8
S2					7 6	15 5
S3		7 7	4 3
S4	-5	-1 6	-4 3	-2 11	-4 5
-7	-7	-13	-9

 

 

4. Находим max значение характеристики свободных переменных (E=max). В нашем примере она находится в клетке S₂ - D₅, и равна 10.

5. Вводим свободную переменную +Q в клетку S₂ - D₅ (см. первый опорный план).

Запомните:

Абсолютная величина поставки Q должна быть в точности равна величине возможных ликвидируемых поставок (в нашем случае +Q=20).

Баланс по столбцам и строкам не должен нарушаться (в нашем примере из-за введения свободной переменной +Q=20 нарушен баланс по строке S₂).

Чтобы сохранить баланс в строке S₂, вводим в клетку S₂ - D₃ свободную переменную -Q=20. Этим самым баланс по строке S₂ восстановлен, но нарушен баланс по столбцу D₃. Восстанавливая его, в клетку S₃ - D₃ введем переменную +Q=20 и в клетку S₃ – D₅ – переменную -Q=20. Эта процедура носит название построение цепей. Очевидно, что цепи должны быть замкнуты.

6. Составляем следующий план перевозок:

7.

	D1	D2	D3	D4	D5	Мощность
S1
S2
S3
S4

Для этого плана целевая функция F=1680 (сравн. с первым планом). Приращение функции цели всегда равно .

Вновь составляем таблицу потенциалов и далее – новый план. Всего для решения рассматриваемой задачи составляется 8 планов перевозок. В итоге 8-й итерации получаем следующее оптимальное решение, для которого целевая функция F=1450→min:

 

	D1	D2	D3	D4	D5	Мощность
S1
S2
S3
S4

 

Проверьте себя.

Решите транспортную задачу вручную (методом потенциалов).

Исходные данные - в следующей таблице:

Вариант 13

	D1	D2	D3	D4	Мощность
S1
S2
S3
S4
Спрос

Примечание

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

Доказательство:

Формула для расчета величины функции цели имеет вид

.

Так как в пустых клетках величина х_ij = 0, то формулу можно записать иначе:

.

но . Отсюда

.

Вспомнив, что и , получим

.

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