Решение сетевых задач методом линейного программирования

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

Модель сети связи, используемая для передачи информации, можно рассматривать как совокупность ветвей и узлов и представить в виде графа, вершины которого поставлены в соответствие узлам, а ребра — ветвям, как показано на рис. 5 для примера с 5 пунктами передачи и ретрансляции.

Рис. 5.

Граф может быть неориентированным, если связь по всем ветвям двухсторонняя, или ориентированным, если имеют место односторонние (т.е. в одном направлении) связи между отдельными узлами, например 12 на рис. 5.

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

Каждая ветвь характеризуется двумя параметрами. Один параметр — это емкость или пропускная способность _ij, которая ограничивает возможности передачи определенного объема информации между пунктами i и j. На рис. 5, например, пропускная способность односторонней ветви ₁₂ = 15, а двухсторонних, совпадающая в обоих направлениях, — ₁₅ = ₅₁ = 15, ₃₄ = ₄₃ = 10, ₂₃ = ₂₃ = 20 и т. д.

Второй параметр каждой ветви зависит от выбранного критерия оптимизации. Это может быть и длина ветви l_ij, и стоимость передачи единицы информации c_ij по данной ветви, и другие параметры. Как отмечено выше, для двухсторонних ветвей эти параметры могут не совпадать, например на рис. 5. Стоимость, указанная в скобках, для ветви с₄₃=8, а с₃₄=7.

Для полной характеристики сети используются матрица пропускных способностей (емкостей) В и, например, матрица стоимостей С, соответствующие приведенной на рис. 5 сети связи.

Для передачи заданных потоков информации между парами узлов образуются пути, которые включают последовательности узлов и ветвей и при этом ни один из узлов не встречается дважды. Так, если требования на потоки информации Ф задать в матричном виде.

это будет означать, что требуется передать потоки с объемами информации ₂₋₅ = 16 и ₁₋₃ = 15.

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

В качестве переменных х_i целесообразно выбрать величины потоков информации, передаваемой по i-му пути. Число переменных будет определяться количеством путей входящих в построенные деревья путей.

Для составления математической модели задачи удобно использовать таблицу путей где каждому потоку Ф соответствует набор путей с количеством передаваемой информации х_i.

Рис. 6.

Таблица 13.

Стоимость пути складывается из стоимости передачи единицы информации по каждому из составляющих ветвей. Так стоимость первого пути с1 = с23 + + с35 = 14.

Как видно, в таблице объединены двухсторонние ветви, имеющие в обоих направлениях одинаковые характеристики, и только выделены отдельно ветви ₃₄ и ₄₃, имеющие разную стоимость.

Математическая модель задачи имеет целевую функцию, соответствующую оптимизации-минимизации стоимости передачи информации:

(11).

В частности, из таблицы путей следует F = 14x₁ + 8x₂ + 23x₃ + 14x₄ + 8x₅ + + 13x₆ + 8x₅ + 13x₆ + 17x₇ + 14x₈ min.

В качестве ограничений выступают следующие требования:

1. Суммарный поток информации между заданной парой узлов, представленный в виде суммы потоков по каждому из путей, должен быть равен требуемому потоку информации между этой парой узлов, т. е.

х₁ + х₂ + х₃ + х₄ = ₂₅ = 16,.

х₅ + х₆ + х₇ + х₈ = ₁₃ = 15. (12).

2. Для любой ветви сети суммарный поток информации, образованный путями, проходящими через ветвь, не может превышать пропускной способности этой ветви, поэтому из таблицы путей следует х₅ + х₇ 15,.

х₆ + х₈ 15,.

х₁ + х₄ + х₅ 20,.

х₂ + х₃ + х₇ 10,.

х₄ 10, (7.13).

х₃ + х₇ + х₈ 10,.

х₁ + х₃ + х₆ 15,.

х₂ + х₄ + х₈ 15.

3. Потоки информации не могут принимать отрицательных значений, т. е. хi 0.

Целевая функция (11) и система ограничений (12) и (13) позволяют решать и исследовать задачу оптимизации сети связи методом линейного программирования.