ВЫРОЖДЕННЫЕ ПЛАНЫ И ДЕКОМПОЗИЦИЯ ТРАНСПОРТНОЙ ЗАДАЧИ

Аннотация

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