Алгоритм пересчета транспортной таблицы

Шаг 1. Выбрать свободную клетку (r, s), соответствующую наибольшей положительной оценке

.

Шаг 2. Для выбранной свободной клетки (r, s) построить цикл пересчета – это замкнутая ломаная, одна из вершин которой находится в данной свободной клетке, а все остальные – в занятых клетках, соседние звенья взаимно перпендикулярны, сами звенья параллельны строкам и столбцам таблицы. Цикл пересчета всегда состоит из четного числа вершин.

Шаг 3. Клетку (r, s) пометить знаком «плюс», далее соседние вершины цикла пересчета пометить по очереди знаками «минус», «плюс».

Шаг 4. Из поставок, отмеченных знаком «минус», выбрать минимальную – ρ.

Шаг 5. Перейти к новому базисному допустимому решению:

1) к поставкам, отмеченным знаком «плюс», добавляется ρ,

2) из поставок отмеченных знаком «минус», вычитается ρ.

Пример решения классической транспортной задачи

Пример №5.1.

Однородный продукт, находящийся в трех пунктах производства (m=3), необходимо доставить в четыре пункта потребления (n=4). При этом матрица транспортных затрат на перевозку единицы продукта из любого пункта отправления в любой пункт назначения, вектор объемов запасов продукта в пунктах производства и вектор объемов продукта, необходимых пунктам потребления, имеют вид:

Решение.

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

Для того, чтобы превратить открытую модель транспортной задачи в закрытую, необходимо ввести фиктивный пункт потребления с объемом потребления

единиц.

При этом тарифы на перевозку продукта в этот пункт потребления будут равны нулю, т.к. фактического перемещения продукта не происходит.

Шаг 2. По правилу «северо-западного угла» определяется первое допустимое решение:

Шаг 3.Оценки базисных клеток транспортной таблицы равны нулю.

Приняв , потенциалы вычисляются следующим образом:

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

Шаг 4. По формуле (5.6) вычисляются оценки всех свободных клеток:

, , ,

, , ,

, .

Шаг 5. Т.к. есть хотя бы одна из оценок свободных клеток строго положительная, то базисное допустимое решение, содержащееся в данной транспортной таблице, не является оптимальным.

Шаг 6. В соответствии с алгоритмом пересчета транспортной таблицы выбираетсясвободная клетка (r, s), соответствующая наибольшей положительной оценке

Для выбранной свободной клетки (14) строится цикл пересчета: 14-13-23-24.

50				*

Клетка (14) помечается знаком «плюс», далее соседние вершины цикла пересчета помечаются по очереди знаками «минус», «плюс». Выбирается минимальная из поставок, отмеченных знаком «минус» , и к поставкам, отмеченным знаком «плюс», добавляется ρ_max, а из поставок отмеченных знаком «минус», вычитается .

Производится перераспределение поставок вдоль цикла пресчета:

	*	®			®

Получается второе базисное допустимое решение. Далее необходимо вычислить новые потенциалы, полагая :

Вторая транспортная таблица и потенциалы имеют вид:

50
		*

Оценки всех свободных клеток таблицы равны:

, , ,

, , ,

, .

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

Далее решая задачу по алгоритму получается третье, четвертое, пятое и шестое базисные решения.

Шестая транспортная таблица и потенциалы имеют вид:

Оценки всех свободных клеток таблицы равны:

, , ,

, ,

, ,

.

Все .

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

Ответ.

Оптимальный план перевозки имеет вид:

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