Допустимые планы в транспортной задаче

В работе даются оценки числа допустимых решений транспортных задач широкого класса. Эти оценки делаются на основе структурных свойств транспортных задач независимо от вида целевой функции и конкретных значений запасов, потребностей и тарифов. Рассматриваются базисные планы, удовлетворяющие только классическим технологическим ограничениям и условию отсутствия циклов в закрытой задаче. Анализируются двудольные графы и соответствующие им деревья. В работе используются методы комбинаторики и теории графов. Полученные количественные и качественные характеристики множества допустимых планов транспортных задач могут быть полезны как для оценки сверху числа планов конкретной транспортной задачи, так и при решении различных модификаций транспортных задач. Приведены формулы для оценки роста числа планов с ростом размеров транспортной задачи и примеры подсчета для определенных размерностей задачи.