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

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

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

Граф может быть неориентированным,

15(4) 15(3) если связь по всем ветвям двухсторонняя,

или ориентированным, если имеют место

односторонние (т.е. в одном направлении)

15(9) связи между отдельными узлами,

15(2) 10(6) 20(8) например 1®2 на рис.7.1.

В общем случае некоторые характе-

ристики ветвей могут не совпадать по раз-

10(8) 10(7) ным направлениям, например стоимость

передачи единицы информации в одном

Рис. 7.1 направлении будет отличаться от стоимо-

сти в обратном направлении.

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

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

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

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

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

это будет означать, что требуется передать потоки с объемами информации j_2-5 = 16 и j_1-3 = 15.

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

Рис.7.2

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

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

Ф	Пути	x_i	Пропускные способности ветвей и стоимости	Стоимость пути С
b₁₂	b₁₅=b₅₁	b₂₃=b₃₂	b₂₄=b₄₂	b₃₄	b₄₃	b₃₅=b₅₃	b₄₅=b₅₄
j_2-5	2-3-5 2-4-5 2-4-3-5 2-3-4-5	x₁ x₂ x₃ x₄
j_1-3	1-2-3 1-5-3 1-2-4-3 1-5-4-3	x₅ x₆ x₇ x₈

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

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

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

(7.11)

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

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

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

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

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

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

х₅ + х₇ £ 15,

х₆ + х₈ £ 15,

х₁ + х₄ + х₅ £ 20,

х₂ + х₃ + х₇ £ 10,

х₄ £ 10, (7.13)

х₃ + х₇ + х₈ £ 10,

х₁ + х₃ + х₆ £ 15,

х₂ + х₄ + х₈ £ 15.

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

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