Транспортная задача.

Постановка задач:

Крупная торговая компания имеетК пунктов хранения одного и того же товара и Rпунктов потребления этого же товара. На каждом i-ом пункте хранения хранится αi-ой формы товара. Каждому j-ому пункту потребления необходимо _jединиц товара. Предполагается, что запасы и потребности являются сбалансированными, т.е. . Предполагается, что любой пункт хранения может взаимодействовать с любым пунктом потребления.Для каждого сочетания пункта хранения и пункта потребления известно стоимость перевозки единиц продукта (с_ij).

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

Решение:

х _ij– количество перевозимого товара из i-го пункта хранение в j-ый пункт хранения. Тогда суммарная мощность всех перевозок будет иметь вид: f(x) = ∑с_ijx_ijmax.

∑x_ij= _{j ,}

∑x_ij = _i,

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

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

1. Построение первоначального решения и оценка её оптимальности

2. Переход к новому решению в случае не оптимальности

Алгоритмы

1. Распределительный

2. Модифицированный распределительный (метод потенциалов)

Распределительный алгоритм решения транспортной задачи

1. Исходная задача записывается в виде распределительной таблицы (на этом шаге необходимо проверить сбалансированность задачи, а именно выполнение условия ∑α_i=Eβ_j). В случае невыполнения этого условия в задачу необходимо ввести либо дополнительного поставщика либо дополнительного потребителя. При этом запасы поставщика или потребности потребителя должны быть равны величине «не баланса» между запасами и потребностями.

Распределительная таблица транспортной задачи имеет следующий вид

Поставищики	ПОТРЕБИТЕЛЕЙ				Запасы
	В1	…	Вj	Вr
А1	c11		c1j	cir	a1
….
Аi	cj1		cij	cir	ai
….
Ак	ck1		ckj	Ckr	ak
Потребности	b1		bj	br

A=(45,20,35)

B=(40,10,50)

C=( )

∑α=∑β=100 – задача сбалансирована

ШАГ 1 составление распределительной таблицы

Поставщики	ПОТРЕБИТЕЛЕЙ			Запасы
	B1	B2	B3
A1	5	6	3	45
A2	3	8	2	20
A3	4	7	4	35
Потребности	40	10	50

ШАГ 2 – формирование первоначального базисного решения (ПБР).

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

Этапы метода

1. Среди всех клеток распределительной таблицы выбирается клетка имеющая наименьший тариф

   Поставщики	ПОТРЕБИТЕЛЕЙ			Запасы
   	B1	B2	B3
   A1	5	6	3	45
   A2	3	8	__2__	20
   A3	4	7	4	35
   Потребности	40	10	50

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

Поставщики	ПОТРЕБИТЕЛЕЙ			Запасы
	B1	B2	B3
A1	5	6	30 (столбец закрыт)	45
A2	3	8	20 (строка закрыта)	20
A3	4	7	4	35
Потребности	40	10	50

3. Если величина максимально возможной поставки ограничена величиной соответствующего запаса то «закрывается строка». Если максимальная строка ограничена величиной потребностей то «закрывается столбец». Закрытые строки и столбцы в дальнейшем поиске решения не участвуют.

Поставщики	ПОТРЕБИТЕЛЕЙ			Запасы
	B1	B2	B3
A1	5	6	3	45
A2	3	8	2	20
A3	4	7	4	35
Потребности	40	10	50

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

5. Шаги 3 и 4 повторяются до тех пор пока в распределительной таблице не будет заполнено k+r-1 клетка

Поставщики	ПОТРЕБИТЕЛЕЙ			Запасы
	B1	B2	B3
A1	155 (строка закрыта)	6	303 (столбец закрыт)	45
A2	3	8	202 (строка закрыта)	20
A3	254 (столбец закрыт)	107 (строка и столбец закрыты)	4	35
Потребности	40	10	50

Если количество загруженных клеток равно к+r-1, то транспортная задача на заданном этапе считается не вырожденной. Если количество загруженных клеток меньше чем к+r-1, то в этом случае задача является вырожденной и от вырожденности задачи избавляются следующим образом.

1. Если число закрытых клеток на ЕДИНИЦУ меньше чем к+r-1, то в любую свободную клетку ставят 0 и считают эту клетку загруженной

2. Если число закрытых клеток на 2 ЕДИНИЦЫ меньше чем к+r-1, то в любые две клетки ставят нули и считают эти клетки загруженными и т.д.

Записывается решение в виде матрицы и определяется значение целевой функции на рассматриваемом этапе

Х=

F(x)=375 (умножаем тарифы на цифры в клетках и складываем)

ШАГ 3 – оценка оптимальности полученного решения

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

ТЕОРЕМА – если транспортная задача является не вырожденной то для каждой свободной клетки может быть составлен единственный цикл в распределительной таблицы.

Рассмотрим клетку С12.

Поставщики	ПОТРЕБИТЕЛЕЙ			Запасы
	B1	B2	B3
A1	1 55 (строка закрыта)	6	303 (столбец закрыт)	45
A2	3	8	202 (строка закрыта)	20
A3	2 54 (столбец закрыт)	107 (строка и столбец закрыты)	4	35
Потребности	40	10	50

Клетка С22

Поставщики	ПОТРЕБИТЕЛЕЙ			Запасы
	B1	B2	B3
A1	1 55 (строка закрыта)	6	3 03 (столбец закрыт)	45
A2	3	8	202 (строка закрыта)	20
A3	2 54 (столбец закрыт)	107 (строка и столбец закрыты)	4	35
Потребности	40	10	50

Для всех свободных клеток выявляются и строятся циклы.

Алгоритм распределительного метода предполагает переход к новому решению путем реализации операции передвижения по циклу некоторой поставки величиной θ.

Рассмотрим некоторый произвольный цикл, включающий клетки с номерами jk, jk, lj и lk.

Считаем ij – свободной, все остальные загруженные.

С ij	X ik Сik (-θ)
XljClj(-θ)	XlkСlk(+θ)

Рассмотрим приращение целевой функции при реализации процедуры передвижения по циклу величины θ

∆ f= θ(c_ij-C_ik+C_lk-C_lj)

∆_ij= (c_ij-C_ik+C_lk-C_lj) - принято называть оценкой свободной клетки

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

ШАГ 4 – переход новому базисному решению.

Для этого определяется величина поставки θ, которая может быть загружена в клетку с отрицательной оценкой наиболее просто определить эту величину

Величина θ = mn _{(четные)} {x_ij}

ШАГ 5 – распределительная таблица переписывается, записывается решение полученное в результате перемещения по циклу и определяется значение целевой функции при этом решении.

ШАГ 6 – переход к ШАГУ 3

ПРИМЕЧАНИЕ:

1. за конечное число шагов решение транспортной задачи будет найдено

2. если среди всех не отрицательных оценок имеется нулевая то это означает что оптимальное решение не единственно.

ШАГ3.1

∆12=С12-С32+С31+С11 = 6-7+4-5 = -2

∆21=С21-С11+С13-С32 = 3-5+3-2 = -1

∆22=С22-С31+С31-С11+С13-С23= 8-7+4-5+3-2 = 1

∆33 = С33-С31+С11-С13 = 4-4+5-3 = 2

Если при решении имеется несколько отрицательных оценок, то выбирается наибольшая по модулю отрицательная оценка.

θ = min {x_ij}

θ = min {10,15} = 10

Поставщики	ПОТРЕБИТЕЛЕЙ			Запасы
	B1	B2	B3
A1	55	106	303	45
A2	3	8	202	20
A3	354	7	4	35
Потребности	40	10	50

X

f(x)=355

Решение не вырождено

ШАГ 3.2

∆21=C21-C11+C13-C23 = 3-5+3-2= -1

∆22 = 8-6+3-2 = 3

∆31=C31-C31+C11-C12=7-4+5-6 = 2

∆33=C33-C31+C11-C13 = 2

Поставщики	ПОТРЕБИТЕЛЕЙ			Запасы
	B1	B2	B3
A1	5	106	353	45
A2	53	8	152	20
A3	354	7	4	35
Потребности	40	10	50

X

f(x)=60+105+15+30+140=350

Решение не вырождено

ШАГ 3.3

∆11=5-3+2-3 = 1

∆22= 3

∆32=7-4+3-2+3-6 = 1

∆33 =4-4+3-2=1

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

X

f(x)=350 – минимальные затраты на перевозку

Модифицированный распределительный метод (метод потенциалов)

На этапе оценки оптимальности решения для каждой строки и каждого столбца вводятся величины u_i и v_j, которые называются потенциалами i-ой строки и j-го столбца

Поставщики	ПОТРЕБИТЕЛЕЙ			Запасы
	B1	B2	B3
A1	5	106	353	45	U1
A2	53	8	52	20	U2
A3	354	7	4	35	U3
Потребности	40	10	50
	V1	V2	V3

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

U_i+V_j=C_ij

C _ij – тарифы загруженных клеток

U₁+V₂=6

U₁+V₃=3

U₂+V₁=3

U₂+V₃=2

U₃+V₁=4

Для решения данной системы уравнений один из потенциалов (любой) полагается равным некоторому числу (любому, например 0)

Например U1=0

V2=6, V3=3, U2=-1, V1=4, U3=0, U1=0

По полученным значениям потенциалов вычисляются оценки свободных клеток

∆_ij=C_ij-(U_i+V_j)

C_ij – тариф свободной клетки

∆11=5-(U1+V1)=5-4=1

∆22=С22-(U2+V2)=8-5=3

∆32=С32-(U3+V2)=7-3 = 4

∆33=C33-(U3+V3)=4-3 = 1