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

Шаг 1. Привести открытую модель транспортной задачи к закрытой.

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

Правило северо-западного угла.

Заполнение транспортной таблицы начинается с левой верхней клетки («северо-западного угла») и состоит из однотипных шагов, на каждом из которых из рассмотрения исключается один поставщик или один потребитель:

1) если остаток продукта у i-го поставщика после предыдущих шагов меньше, чем неудовлетворенный запрос j-го потребителя, то исключается из рассмотрения i-й поставщик, и в клетку (i, j) заносится поставка x_ij, равная остатку продукта у i-го поставщика после предыдущих шагов;

2) если остаток продукта у i-го поставщика после предыдущих шагов больше, чем неудовлетворенный запрос j-го потребителя, то исключается из рассмотрения j-й потребитель, и в клетку (i, j) заносится поставка x_ij, равная неудовлетворенному запросу j-го потребителя;

3) если остаток продукта у i-го поставщика после предыдущих шагов равен неудовлетворенному запросу j-го потребителя, то исключается из рассмотрения или i-й поставщик, или j-й потребитель, и в клетку (i, j) заносится поставка x_ij, равная остатку продукта у i-го поставщика после предыдущих шагов. В случае исключения i-го поставщика в клетку (i+1, j) заносится поставка x_i_{+1, j}= 0 равная неудовлетворенному запросу j-го потребителя. В случае исключения j-го потребителяв клетку (i, j+1) заносится поставка x_{i, j}₊₁= 0 равная остатку продукта у i-го поставщика после предыдущих шагов.

Шаг 3. Вычислить потенциалы.

1. Каждому поставщику ставится в соответствие потенциал p_i.

2. Каждому потребителю — потенциал q_j.

При этом каждой клетке соответствует некоторая оценка

, (5.6)

где ;

Один из потенциалов можно выбирать произвольно, т.к. в системе (5.3) и (5.4) одно уравнение линейно зависит от остальных. Обычно полагают p₁=0. Остальные потенциалы вычисляются из того условия, что для базисных клеток Δ _ij=0.

Шаг 4. Вычислить оценки всех свободных клеток по формуле (5.6).

Шаг 5. Проверить транспортнцю таблицу на оптимальность:

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

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

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

, ; .

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

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

Шаг 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.

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

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

	*	®			®

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

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

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

, , ,

, .

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

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

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

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

, , ,

, ,

Все .

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

Ответ.

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

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

⇐ Предыдущая 1 2 3 4 5 678 Следующая ⇒