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

ТРАНСПОРТНАЯ ЗАДАЧА - задача линейного программирования, которой можно описать многие экономические и производственные ситуации, возникающие в конкретных условиях выполнения перевозок на ж.-д. транспорте. При постановке задачи принимается, что для m станций отправления и n станций назначения заданы размеры отправления и прибытия однородного или взаимозаменяемого груза (в тоннах, вагонах или других единицах); при этом известна стоимость перевозки единицы груза от каждой станции отправления до каждой станции назначения. Требуется составить такой план перевозок, в котором общие транспортные расходы были бы минимальными. Под стоимостью понимается как экономическое содержание этого понятие, так и условное (себестоимость, тариф, время, расстояние и т.п.). Если общие размеры запаса груза и общие размеры потребности в нем равны, то задача считается "закрытой", если эти условия не выполнены - "открытой". Математическая формулировка транспортной задачи в матричной форме имеет вид:

где xij - размер перевозки со станции i на станцию j; aij - стоимость соответствующей перевозки; ai - запас груза на i-й станции отправления; bj - запас груза на j-й станции назначения; F - целевая функция.

Требуется найти неотрицательное решение системы ограничений (i), минимизирующее целевую функцию.

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

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