logo
Шепеленко О

2.6. Транспортная задача. Метод потенциалов

Транспортная задача принадлежит к специальному классу распределительных ЗЛП. Пусть нужно перевезти однородный груз из m пунктов отправления Аi в n пунктов назначения Bj. Известно количество груза ai (запасы), находящееся у i-го поставщика (постоянно), а также объемы потребностей в нем bj (заявки) j-го потребителя. Известны также затраты на перевозку единицы груза от i-го поставщика к j-му потребителю – тариф – сij. Тарифы записывают в верхнем левом углу каждой клетки таблицы. Необходимо распределить груз таким образом, чтобы затраты на его перевозку были минимальными.

Из условий задачи получим следующую модель линейного программирования:

(2.6.1)

(2.6.2)

(2.6.3)

(2.6.4)

Система ограничений (2.6.1) говорит о том, что груз из каждого пункта отправления должен быть вывезен. Система ограничений (2.6.2) говорит о том, что потребность в грузе в каждом пункте назначения должна быть удовлетворена. Система ограничений (2.6.3) говорит о том, что по любому маршруту либо перевозится некоторое количество груза, либо нет. Целевая функция (2.6.4) минимизирует совокупные транспортные затраты на перевозку всех партий грузов из всех пунктов отправления во все пункты назначения.

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

.

В случае отсутствия баланса между спросом и предложением транспортная задача называется открытой.

Решение задач с открытой моделью сводится к решению задач с закрытой моделью.

Опорным планом транспортной задачи называется неотрицательное решение системы ограничений (2.5.1)-(2.5.3), который записывают в виде матрицы .

Оптимальным планом транспортной задачи называется опорный план транспортной задачи, при котором целевая функция (2.5.4) достигает минимального значения.

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

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