Физическая постановка задачи

В проектируемой информационной сети имеется 2 сервера с информационными ресурсами и 3 рабочих станции (пользователи информационных ресурсов). Объемы информации серверов составляют А1 = 100 и А2 = 60 е.о., а объемы информации требуемой для пользователей В3 = 70, В4 = 40 и В5 = 50 е.о. Удельные затраты на передачу информации по линиям между серверами и рабочими станциями составляют z12 = 10, z13 = 5, z14 = 2, z15 = 4, z23 = 3, z24 = 2, z25 = 4, z34 = 5, z35 = 6 и z45 = 2 у.е.

Требуется найти оптимальную схему информационной сети.

Построение частной модели и ее решение

Примем следующую сквозную нумерацию узлов: А1, А2, В3, В4 и В5.

Составим транспортную матрицу размерностью 5×5.

Исходное допустимое решение найдем методом наименьшей удельной стоимости. Перемещаясь по транспортной матрицы сверху вниз выбираем клетку 14 с наименьшей удельной стоимостью z14 = 2. В эту клетку вписываем наименьшее из двух значений А1=100 и В4=40. По линии 14 будет передаваться объем, равный 40 е.о. Потребность в мощности узла 4 будет полностью покрыта, поэтому в остальные клетки столбца 4 вписываются нули. математический мощность транспортный В клетку 23 вписываем наименьшее из двух значений А2=60 и В3=70. по линии 23 будет передаваться объем, равный 60 е.о. Объем источника А2=60 будет полностью израсходован, поэтому в остальные клетки строки 2 вписываем нули.

Из оставшихся не заполненных клеток выбираем клетку 13 с наименьшей удельной стоимостью z13 = 5. В эту клетку впишем оставшуюся потребность объема В3=70 — 60 = 10 е.о. По линии 13 будет передаваться объем, равный 10 е.о. Потребность в объеме узла 3 (В3=70) полностью покрыта, в остальные клетки столбца вписываем нули.

В клетку 15 вписываем оставшийся объем источника 1.

(А1 = 100 — 40 — 10 = 50).

Объем источника 1 полностью израсходован, поэтому в остальные клетки вписываем нули.

Балансы во всех узлах выполняются:

узел 1 10+40+50 = 100 узел 2 60 = 60.

узел 3 10+60 = 70 узел 4 40 = 40.

узел 5 50 = 50.

В полученном допустимом решении:

свободные переменные х12 = х21 = х24 = х25 = х31 = х32 = х34 = х35 = х41 = х42 = х43 = х45 = х51 = х52 = х53 = х54 = 0;

базисные переменные х11 = х22 = х33 = х44 = х55 = 0, х13 = 10, х14=40, х15 = 50, х23=60 е.о.

значение целевой функции.

Z = z13×13+z14×14+z15×15+z23×23 = 5*10+2*40+4*50+3*60 = 510 у.е.

Попробуем улучшить полученное решение. Воспользуемся методом потенциалов и присвоим каждой строке потенциал Vi, а каждому столбцу — потенциал Uj. В соответствии с алгоритмом метода дл всех базисных переменных сумма потенциалов равна удельной стоимости.

Vi + Uj = zij.

Зададим произвольно значение одного из потенциалов (U1 = 1).

По выражению Vi + Uj = zij вычислим значение остальных потенциалов Поскольку для базисных транзитных переменных удельные стоимости zii = 0, потенциалы с одинаковыми индексами равны по величине и противоположны по знаку Vi = - Ui.

U3 = - V1 + z13 = 1+5 = 6 V3 = -6.

U4 = - V1 + z14 = 1+2 = 3 V4 = -3.

U5 = - V1 + z15 = 1+4 = 5 V5 = -5.

V2 = - U3 + z23 = -6+3=-3 U2 = 3.

Для всех свободных переменных проверим условие Vi + Uj < zij.

x12: V1+U2 = -1+3 = 2.

x21: V2+U1 = -3+1 = -2.

x24: V2+U4 = -3+3=0.

x25: V2+U5 = -3+5=2.

x31: V3+U1 = -6+1=-5.

x32: V3+U2 = -6+3=-3.

x34: V3+U4 = -6+3=-3.

x35: V3+U5 = -6+5=-1.

x41: V4+U1 = -3+1=-2.

x42: V4+U2 = -3+3=0.

x43: V4+U3 = -3+6=3.

x45: V4+U5 = -3+5=2 = z45=2.

x51: V5+U1 = -5+1=-4.

x52: V5+U2 = -5+3=-2.

x53: V5+U3 = -5+6=1.

x54: V5+U4 = -5+3=-2.

Для свободной переменной х45 это условие не выполняется. Следовательно, свободную переменную х45 следует перевести в базис.

В новом решении:

свободные переменные х12 =х15 = х21 = х24 = х25 = х31 = х32 = х34 = х35 = х41 = х42 = х43 = х51 = =х52 = х53 = х54 = 0;

базисные переменные х11 = х22 = х33 = х55 = 0, х13 = 10, х14=90, х23=60, х44 = -50, х45 = 50 е.о.

значение целевой функции.

Z = z13×13+z14×14+z23×23+z45×45 = 5*10+2*90+3*60+2*50 = 510 у.е.

Вновь присвоим каждой строке потенциал Vi, а каждому столбцу — потенциал Uj. Зададим произвольно значение одного из потенциалов (U1 = 1).

По выражению Vi + Uj = zij вычислим значение остальных потенциалов.

U3 = - V1 + z13 = 1+5 = 6 V3 = -6.

U4 = - V1 + z14 = 1+2 = 3 V4 = -3.

U5 = - V4 + z45 = 3+2 = 5 V5 = -5.

V2 = - U3 + z23 = -6+3=-3 U2 = 3.

Для всех свободных переменных проверим условие Vi + Uj < zij.

x12: V1+U2 = -1+3 = 2.

x15: V1+U5 = -1+4 = 3.

x21: V2+U1 = -3+1 = -2.

x24: V2+U4 = -3+3=0.

x25: V2+U5 = -3+5=2.

x31: V3+U1 = -6+1=-5.

x32: V3+U2 = -6+3=-3.

x34: V3+U4 = -6+3=-3.

x35: V3+U5 = -6+5=-1.

x41: V4+U1 = -3+1=-2.

x42: V4+U2 = -3+3=0.

x43: V4+U3 = -3+6=3.

x51: V5+U1 = -5+1=-4.

x52: V5+U2 = -5+3=-2.

x53: V5+U3 = -5+6=1.

x54: V5+U4 = -5+3=-2.

Нет ни одной свободной переменной, перевод которой в базис улучшит решение. Полученное решение является оптимальным.

Оптимальная схема информационной сети.