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