Решение транспортной задачи

Состоит из 3-ёх этапов.

1 этап. Определение первоначального допустимого решения методом «Северо-Западного угла», это будет базисное решение или опорный план.

2 этап. Проверка опорного плана на оптимальность, используя метод потенциалов (тория потенциалов)

3 этап. Если решение оптимально, то задача решена, если нет, определяем новый план перевозки (этап 1), проверяем на оптимальность (этап) пока не получим оптимального решения.

Количество наборов m+n -1 неизвестных составленных из m×n неизвестных, есть число конечное мы определим и оптимальный набор неизвестных, но благодаря методу решения транспортной задачи мы перебираем не слепо, а каждый новый набор неизвестных лучше предыдущего, т.е. значение ƒ уменьшается.

	- 3 100			+ 1
	+ 1 200	- 4 200
		+ 3 300	1	2 200 -

ƒ₁= 100 ×3 + 200 + 200×4 + 200×3 + 100 + 200×2= 2700 у.е.

Правило: количество клеток, выделенных рамками равно m+n -1, они называются базисными неизвестными, остальные клетки без рамок это свободные неизвестные.

Сопоставим каждому складу Аί некоторую величину α_ί и каждому магазину β_ј .

Для дальнейшего уменьшения стоимости опорных планов и нахождения оптимального плана разработан метод потенциалов. α_ί и β_ј называются потенциалами соответственно пункта отправления (склад) и пункта назначения (магазин).

Для каждой базисной неизвестной х _ίј (базисной клетки) с α_ί и β_ј составим уравнение.

α_ί + с_ίј = β_ј где

с_ίј стоимость перевозки с α_ί до β_ј

α_ί + с_ίј = β_ј

α₁ + с₁₁ = β₁

α₁ + с₁₂ = β₂

α₁ + с₁₃ = β₃

α₁ + с₁₄ = β₄

α₂ + с₂₁ = β₁

Базисное решение транспортной задачи будет оптимальным, если для всех свободных клеток таблицы матрицы перевозок выполняется неравенство α_ί + с_ίј > или = β_ј – признак оптимальности нужного решения

Чтобы проверить план перевозок на оптимальность, необходимо сначала рассчитать метод потенциалов.

Определим величины α₁ α₂ α₃ и β₁ β₂ β₃ β₄ , одной из величин α можно предать произвольное значение, α₁ принято обозначать 0

α₁ = 0

0+3=3

α₂ + с₂₁ = β₁

2+1=3

Теперь проверим план перевозок на оптимальность, выполняется ли неравенство α_ί + с_ίј > или = β_ј (для свободных клеток)

Определение нового базисного решения в клетку а₁ в₄ поставим - знак поставки (> 0)

Правило перераспределения поставок.

Начиная со свободной клетки () и двигаясь по циклу пересчёта в вершинах цикла расставляем, чередуя знаки «+» и «-»

Просматриваем поставки, записанные в отрицательных вершинах, и среди них выбираем наименьшую. Это число прибавляем ко всем поставкам записанных в «+» вершинах и вычитаем из всех поставок с «-» вершинами.

Свободная клетка, для которой строится цикл пересчета объявляется базисной, а одна из базисных свободной, т.к. поставка в ней будет равна 0

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

				1
	1 200	- 4 4 100		+ 2
		+ 3 400	1	2 100 -

α₁ = 0

α₂ = -2

α₃ = -1

β₁ =-1 β₂ =2 β₃=0 β₄ =1

ƒ₂= 100+300+400+1200+100+200=2300 у.е.

				1
	1 300	4 0		2
		3	1

α₁ = 0

α₂ = -1

α₃ = 0

β₁ =0 β₂ =3 β₃ =1 β₄ =1

ƒ₃= 100+200+ 300+1500+100=2200 у.е.