Особенность построения транспортной задачи

Размещено на http://www.allbest.ru/

1. Общая математическая модель задачи принятия решений заданного типа

Транспортная задача - это задача отыскания таких путей перевозки продукта от пунктов производства к пунктам потребления, при которых общая стоимость перевозок оказывается минимальной.

Под продуктом подразумевается мощность, передаваемая от источников к потребителям. Источниками питания - пункты производства, потребители - пункты потребления. Минимизации подлежат затраты на схему сети, состоящей из линий, связывающих узлы источников и потребителей.

Пусть в проектируемой системе имеется i = 1,2, ... n узлов источников и j = 1,2, ... m узлов потребителей. Мощность каждою из источников составляет Аi, а мощность каждого из потребителей - Вj единиц мощности (е.м.). Известно взаимное расположение узлов источников и потребителей. Стоимость передачи единицы мощности от узла i к узлу j (удельная стоимость) составляет Zij у.е/е.м. Искомые мощности, передаваемые по линиям между узлами i и j, обозначим Xij.

В реальных схемах сетей часто оказывается целесообразной передача мощности через промежуточные (транзитные) узлы. Такими транзитными узлами могут быть как узлы потребителей, так и узлы источников. На рисунке 1 в качестве примера приведены простейшие схемы сетей, поясняющие понятие "транзит мощности".

Рисунок 1 - Поясняющие схемы к понятию “транзит мощности”

На рисунке 1,а показано взаимное расположение узлов источника А1 и потребителей В2 и В3. В схеме рисунок 1,б нет транзита мощности через узлы. Здесь мощность передастся непосредственно от источника А1 к потребителям В2 и В3 по линиям 12 и 13. В схеме рисунка 1,в мощность к потребителю В3 передается через промежуточный (транзитный) узел потребителя В2. Величина транзитной мощности, передаваемой через узел В2, равна мощности потребителя В3.

Транзитную мощность обозначим переменной с двумя одинаковыми индексами, соответствующими номеру узла, через который она протекает. Для схемы рисунок 1,в транзитная мощность X22=B3. Можно показать, что транзитным узлом может быть и узел источника питания.

При решении транспортных задач с транзитом мощности всем узлам схемы присваивается единая нумерация 1,2,... (n+m).

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

Стоимость передачи мощности между узлами i и j не зависит от направления этой мощности, поэтому в рассматриваемой задаче принимается Zij=Zji.

Для оценки удельных затрат Zii на передачу через i-й узел транзитной мощности Xii обратимся к рисунку 1,в. Затраты на сеть, показанную на этом рисунке, составляют Z=Z12X12+Z23X23. Транзитная мощность Х22 и удельные затраты Z22 на ее передачу через узел 2 не входят в выражение целевой функции Z. Следовательно, удельные затраты на передачу транзитной мощности через любой i-й узел Zii=0.

Ограничениями в транспортной задаче будут балансы мощности во всех узлах. В частности, для узла В2 схемы рисунок 1,в баланс мощности запишется в виде X12 = В2 + Х22 ИЛИ Х12 -- Х22 = В2.

В общем случае для любого j-го потребителя сумма мощностей, притекающих от всех других узлов, за вычетом транзитной мощности Хjj равна мощности этого потребителя

Аналогично можно записать уравнение баланса мощности для любого i-го источника. Сумма мощностей, оттекающих от i-го источника ко всем другим узлам, за вычетом транзитной мощности Xii равна мощности этого источника

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

Для решения транспортной задачи составляется транспортная матрица. Матрица квадратная размером (m+n)(m+n). Общий вид такой матрицы показан в таблице 1.

В центре каждой недиагональной клетки матрицы указывается искомые величины мощностей Xij, протекающих между узлами i и j.В центре каждой диагональной клетки матрицы указывается величина транзитной мощности Xii, протекающей через узел i. Как отмечалось выше, эти мощности входят в решение задачи со знаком минус. В правом нижнем углу каждой недиагональной клетки матрицы указывается заданная величина удельной стоимости передачи мощности Zij между узлами i и j. В правом нижнем углу каждой диагональной клетки матрицы указывается величина удельной стоимости передачи транзитной мощности через узел i. Как отмечалось выше, все Zii =0.

Таблица 1

X11 Z11=0	X12 Z12	X13 Z13	X14 Z14	A1=…
X21 Z21	X22 Z22	X23 Z23	X24 Z24	A2=…
X31 Z31	X32 Z32	X33 Z33	X34 Z34	B3=…
X41 Z41	X42 Z42	X43 Z43	X44 Z44	B4=…
A1=0	A2=0	B3=…	B4=…	Z=…

Справа от матрицы в дополнительном столбце источников питания указываются заданные мощности источников А1 и A2. мощности потребителей в этом столбце нулевые (B3=0, B4=0), поскольку они не являются источниками. Снизу от матрицы в дополнительной строке потребителей указываются заданные мощноcти потребителей B3 и B4 мощности источников в этой строке нулевые (A1=0, A2=0), поскольку они не являются потребителями. На пересечении дополнительной строки и столбца записывается значение целевой функции Z.

Каждая i-я строка матрицы соответствует уравнению баланса мощности i-го источника, каждый j-й столбец - уравнению баланса мощности j-го потребителя.

В процессе решения транспортной задачи все переменные разделяются на базисные (не равные нулю) и свободные (равные нулю). Каждая базисная переменная Хij соответствует присутствию в схеме линии между узлами i и j, поскольку мощность, протекающая между узлами i и j, не равна нулю. Каждая свободная переменная Xij соответствует отсутствию в схеме линии между узлами i и j, поскольку мощность, протекающая между узлами i и j, равна нулю. Следует отметить, что все транзитные переменные Xij всегда являються базисными, независимо от того, равны они нулю или нет.

Итак, имеется транспортная матрица, в которой следует определить значения переменных Хij и Хii.

Процесс решения транспортной задачи начинается с получения допустимого решения. Исходное допустимое решение может быть получено методом минимальной удельной стоимости по следующему алгоритму:

1. В транспортной матрице выбирается клетка с минимальным значением удельной стоимости Zij. Если имеется несколько таких клеток, то выбирается любая.

2. В выбранную клетку в качестве базисной переменной Xij заносится наименьшая из двух величин, взятых из клетки i дополнительного столбца источников и клетки j дополнительной строки потребителей. При этом выполняется баланс мощности по строке i или столбцу j, в которые входит переменная Хij.

3. В остальные клетки строки i или столбца j, для которых выполнен баланс мощности, заносятся нули. Большая из двух величин, взятых из клетки i дополнительного столбца источников и клетки j дополнительной строки потребителей, условно заменяется разностью этих двух величин.

4. Из оставшихся незаполненных клеток транспортной матрицы вновь выбирается клетка с минимальным значением Zij. Далее пункты 2 и 3 повторяются до полного заполнения всех клеток транспортной матрицы.

После получения допустимого решения по выражению (3.1) рассчитывается значение целевой функции Z.

Оценим количество базисных и свободных переменных в транспортной задаче. Из курса теоретической электротехники известно, что для сети из (m+n) узлов можно составить [(m+n)-1] независимых уравнений но первому закону Кирхгофа (уравнений баланса мощности). Таким образом, количество отличающихся от нуля (базисных) переменных будет [(m+n)-1]. Кроме того, в транспортной задаче каждому узлу соответствует базисная транзитная переменная. Таким образом, общее количество базисных переменных в транспортной задаче составляет [2(m+n)-1].

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

Пусть в полученном допустимом решении (таблица 2) 7 базисных переменных выделены цветом. Остальные 9 переменных свободные (равные нулю). В соответствии с методом потенциалов каждой строке и каждому столбцу транспортной матрицы присваивается свой потенциал (таблицу 2):

строкам - потенциалы Vi, (i=1, 2,... n+m);

столбцам - потенциалы Ui (i=1, 2,... n+m).

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

Vi + Uj = Zij

Для рассматриваемой сети количество неизвестных потенциалов 8. Количество уравнений равно количеству базисных переменных, т. е. 7. Система из 7 уравнений с 8 неизвестными имеет бесконечное количество решений. Для получения однозначною решения необходимо задаться значением одного из потенциалов, например U1 = 1 (таблицу 2). Остальные потенциалы однозначно определятся по тем же уравнениям.

Таблица 2

	U1=1	U2=…	U3=…	U4=…
V1=…	X11 0	X12=0 Z12	X13 Z13	X14=0 Z14	A1=…
V2=…	X21=0 Z21	X22 0	X23 Z23	X24 Z24	A2=…
V3=…	X31=0 Z31	X32=0 Z32	X33 0	X34=0 Z34	B3=…
V4=…	X41=0 Z41	X42=0 Z42	X43=0 Z43	X44 0	B4=…
	A1=0	A2=0	B3=…	B4=…	Z=…

В соответствии с методом потенциалов для всех свободных переменных проверяется условие

Vi + Uj < Zij

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

Если для какой-то свободной переменной условие не выполняется, эту свободную переменную следует перевести в базис, поскольку такой перевод уменьшит целевую функцию Z.

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

При увеличении свободной переменной X34 нарушатся балансы мощности в строке 3 и столбце 4. Для сохранения балансов мощности в строке 3 и столбце 4 необходимо найти базисные переменные, которые следует уменьшать. Пусть это будут базисные переменные X33 и Х24. Поставим в соответствующих клетках знаки минус. Далее для сохранения балансов мощности в строке 2 и столбце 3 базисную переменную X23 следует увеличить. Поставим в соответствующей клетке знак плюс.

Таблица 3

Таблица 4

Итак, при одинаковом изменении переменных X34, X24, X23, X33 в соответствии со знаками плюс или минус балансы мощности во всех строках и столбцах сохранятся. Решение останется допустимым. В результате выполненных действий в транспортной матрице получен замкнутый цикл (цикл пересчета), вершины которого отмечены знаками плюс и минус. Начальная вершина цикла лежит в клетке свободной переменной (X34), которая переводится в базис. Все остальные вершины лежат в клетках базисных переменных (X24, X23 и X33).

Знак плюс в вершине цикла соответствует увеличению переменной, знак минус -- ее уменьшению.

Оценим, на сколько можно увеличить переменную X34. Базисные переменные X23 и Х33 не ограничивают увеличения переменной Х34, поскольку переменные X23 и X33 тоже увеличиваются. Напомним, что транзитная переменная Х33 входит в решение задачи со знаком минус. Ограничивать увеличение переменной X34 будет только базисная переменная X24, которая будет уменьшаться и, достигнув нулевого значения, станет свободной переменной.

Таким образом, увеличивать базисную переменную Х34 можно до значения Х24. После этого переменная X24 станет свободной (X24=0), а переменная Х34 станет базисной (X34>0).

Получим новое решение, представленное в таблице 4. После получения нового решения рассчитывается значение целевой функции Z.

Процедура повторяется до получения оптимального решения.

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

В проектируемой информационной сети имеется 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 у.е.

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

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

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

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

0	10	5	2	4	А1=100
10	0	3	2	4	А2=60
5	3	0	5	6	В3=0
2	2	5	0	2	В4=0
4	4	6	2	0	В5=0
А1=0	А2=0	В3=70	В4=40	В5=50	Z=

Исходное допустимое решение найдем методом наименьшей удельной стоимости. Перемещаясь по транспортной матрицы сверху вниз выбираем клетку 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 полностью израсходован, поэтому в остальные клетки вписываем нули.

00	010	105	402	504	А1=100
010	00	603	02	04	А2=60
05	03	00	05	06	В3=0
02	02	05	00	02	В4=0
04	04	06	02	0	В5=0
А1=0	А2=0	В3=70	В4=40	В5=50	Z=510

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

узел 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 = z13x13+z14x14+z15x15+z23x23 = 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

	U1 = 1	U2 = 3	U3 = 6	U4 = 3	U5 = 5
V1=-1	0 0	0 10	10 5	40 2	50 4	А1=100
V2=-3	0 10	0 0	60 3	0 2	0 4	А2=60
V3=-6	0 5	0 3	0 0	0 5	0 6	В3=0
V4=-3	0 2	0 2	0 5	0 0	0 2	В4=0
V5=-5	0 4	0 4	0 6	0 2	0	В5=0
	А1=0	А2=0	В3=70	В4=40	В5=50	Z=510

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

x12: V1+U2 = -1+3 = 2<z12=10

x21: V2+U1 = -3+1 = -2<z21=10

x24: V2+U4 = -3+3=0<z24=2

x25: V2+U5 = -3+5=2<z25=4

x31: V3+U1 = -6+1=-5<z31=5

x32: V3+U2 = -6+3=-3<z32=3

x34: V3+U4 = -6+3=-3<z34=5

x35: V3+U5 = -6+5=-1<z35=6

x41: V4+U1 = -3+1=-2<z41=2

x42: V4+U2 = -3+3=0<z42=2

x43: V4+U3 = -3+6=3<z43=5

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

x51: V5+U1 = -5+1=-4<z51=4

x52: V5+U2 = -5+3=-2<z52=4

x53: V5+U3 = -5+6=1<z53=6

x54: V5+U4 = -5+3=-2<z54=2

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

	U1 = 1	U2 = 3	U3 = 6	U4 = 3	U5 = 5
V1=-1	0 0	0 10	10 5	90 2	50 4	А1=100
V2=-3	0 10	0 0	60 3	0 2	0 4	А2=60
V3=-6	0 5	0 3	0 0	0 5	0 6	В3=0
V4=-3	0 2	0 2	0 5	-50 0	50 2	В4=0
V5=-5	0 4	0 4	0 6	0 2	0	В5=0
	А1=0	А2=0	В3=70	В4=40	В5=50	Z=510

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

свободные переменные

х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 = z13x13+z14x14+z23x23+z45x45 = 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

	U1 = 1	U2 = 3	U3 = 6	U4 = 3	U5 = 5
V1=-1	00	010	105	902	504	А1=100
V2=-3	010	00	603	02	04	А2=60
V3=-6	05	03	00	05	06	В3=0
V4=-3	02	02	05	-500	502	В4=0
V5=-5	04	04	06	02	0	В5=0
	А1=0	А2=0	В3=70	В4=40	В5=50	Z=510

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

x12: V1+U2 = -1+3 = 2<z12=10

x15: V1+U5 = -1+4 = 3<z15=4

x21: V2+U1 = -3+1 = -2<z21=10

x24: V2+U4 = -3+3=0<z24=2

x25: V2+U5 = -3+5=2<z25=4

x31: V3+U1 = -6+1=-5<z31=5

x32: V3+U2 = -6+3=-3<z32=3

x34: V3+U4 = -6+3=-3<z34=5

x35: V3+U5 = -6+5=-1<z35=6

x41: V4+U1 = -3+1=-2<z41=2

x42: V4+U2 = -3+3=0<z42=2

x43: V4+U3 = -3+6=3<z43=5

x51: V5+U1 = -5+1=-4<z51=4

x52: V5+U2 = -5+3=-2<z52=4

x53: V5+U3 = -5+6=1<z53=6

x54: V5+U4 = -5+3=-2<z54=2

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

Размещено на http://www.allbest.ru/

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

4. Решение частной математической модели на ЭВМ

Заключение и выводы

В данной работе было рассмотрено построения оптимальной информационной сети с помощью решение транспортной задачи методом потенциалов вручную и на ЭВМ. В результате решения этой задачи была получена оптимальная схема информационной сети.

Список использованных источников

1) В.Н. Костин. Оптимизационные задачи электроэнергетики - СПб.: Изд-во СЗТУ, 2007 - 102 с.

2) Бодров В.И., Лазарева Т.Я., Мартемьянов Ю.Ф. Математические методы принятия решений: Учеб. пособие. Тамбов: Изд-во ТГТУ, 2004 г. - 124 с.

3) Бодров В.И., Лазарева Т.Я., Мартемьянов Ю.Ф. Методы исследования операций при принятии решений: Учебное пособие. Тамбов: Изд-во ТГТУ, 2004 г. - 160 с.

Размещено на Allbest.ru

...