Методы математического программирования. Задача оптимизации транспортной сети – это задача оптимизации при ограничениях

Задача оптимизации транспортной сети – это задача оптимизации при ограничениях. Следовательно, для ее решения должны быть применены методы условий оптимизации.

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

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

Если ряд переменных задачи являются целочисленными, например, уровень технической оснащенности дуги – 2, 4, 6 полос движения, то тогда получаем задачу целочисленного программирования.

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

Пусть имеется n=30 – это небольшая сеть, а m=2, т.е. два технических состояния дуги. Тогда получается уже 2³⁰, т.е. более миллиарда возможных комбинаций!

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

Рассмотрим его суть.