<< prev | ^up^ | next >>

3.2. Задача ВПС:

Постановка задачи: Задана структура сети в виде ориентированного графа:

, распределение потоков в КС,

, набор пропускных способностей КС-Д={d₁,..., d_k} и удельных стоимостей каналов в зависимости от типа C={C₁, C₂,..., C_k} на единицу длины.

Требуется найти такие пропускные способности каналов  всех КС, для которых

    (3.5)

и средняя задержка не будет превышать заданной величины Т_зад:

                                              (3.6)

и

, "(r,s)ÎE

Решение. В случае если  - непрерывные переменные, то можно применить метод множителей Лагранжа и составить функцию Лагранжа и решить строго аналитически.

 

  ;

                                        (3.7)

Решим систему (3.7) относительно неизвестных _rs.

Можно найти численное решение из системы (3.3)

Если стоимости являются линейными:

,     (3.8)

то получаем следующее решение для оптимальных пропускных способностей:

       (3.9)

Недостаток: такой подход применим, если пропускные способности являются непрерывными и ф-ии ст-ти-линейные.

В случае, если - дискретные, . Клейнрок предлагает округлить (3.9) до ближайшего члена из этого ряда. Имеем задачу нелинейного дискретного программирования.

Д={2400, 4800, 9600, 14400, 19200,... }