Санкт-Петербургский Государственный Университет
Факультет Прикладной Математики - Процессов Управления
Кафедра Моделирования Социально - Экономических Систем
Румянцев Николай Николаевич
Дипломная работа
"Модель многоагентного взаимодействия в задаче
территориального размещения в сети
распределительных пунктов."
Зав. кафедрой:
Д.ф.-м.н.,
Проф.
Малафеев
Олег
Алексеевич
Научный руководитель:
Д.ф.-м.н.,
Проф.
Малафеев
Олег
Алексеевич
Рецензент:
Д.ф.-м.н.,
Проф.
Пичугин
Юрий
Александрович
Санкт-Петербург
2016
Оглавление
Введение ........................................................................................................ 3
Неформальная постановка задачи территориального размещения
пунктов распределения в транспортной сети.......................................................4
Формализация задачи территориального размещения пунктов
распределения в транспортной сети...................................................................... 5
Обзор литературы .........................................................................................7
Гл а в а 1 . З а д ач а т е р р и т о р и а л ь н о г о р а з м е щ е н и я в с е т и
распределительных пунктов. Примеры. ...............................................................8
1.1. Пример размещения двух пунктов распределения при заданном
расположении двух источников сырья и четырех покупателей .........8
1.2. Пример размещения двух пунктов распределения при заданном
расположении двух источников сырья и шести покупателей...........13
1.3. Пример размещения трех пунктов распределения при заданном
расположении трех источников сырья и восьми покупателей .........21
Выводы ........................................................................................................ 31
Заключение ..................................................................................................31
Литература....................................................................................................32
2
Введение.
Прокладка транспортных сетей в условиях, осложненных различными
обстоятельствами, является нетривиальной задачей, требует
формализованного подхода к ее решению. При построении допустимой
транспортной сети исходят из экологической, географической,
геополитической, экономической обстановки. Наличие заповедных зон,
особенности ландшафта местности, взаимоотношение между государствами,
через которые будет проходить транспортная сеть, а также стоимость её
возведения, все это накладывает жесткие требования на построение
транспортной сети.
Рассмотрим некоторое геополитическое пространство, заданное в виде
сети, где взаимодействуют несколько акторов и присутствуют источники
сырья, в которых, оптом закупается товар, пользующийся спросом у группы
покупателей. Товар доставляется из источника сырья в пункт распределения.
Цена каждого товара в пункте распределения равна сумме его стоимости в
источнике сырья и транспортных издержек при доставке его до пункта
распределения плюс наценка продавца. Необходимо в соответствии с
выбранным принципом оптимальности расположить пункты распределения.
3
Неформальная постановка задачи размещения пунктов
распределения в транспортной сети.
Рассматривается следующая задача. В некоторых точках сети
располагаются покупатели и источники сырья. Для каждого агента на
множестве рёбер задаётся функция транспортно-коррупционных издержек,
которая обозначает затраты на перемещение по данному ребру. Такая
функция задается отдельно для покупателей и отдельно для продавцов. Все
точки сети связаны, т.е. из любой точки сети существует и возможно
неединственный путь в любую другую точку сети.
Для каждого покупателя определенно количество товара, который он
желает приобрести. Сумма затрат на удовлетворение своего спроса для
каждого из покупателей равна сумме всех денег, потраченных им на покупку
товара, и сумме всех транспортно-коррупционных издержек, которые он
тратит для перемещения до пункта распределения.
Необходимо расположить пункты распределения продукта в
соответствии с выбранным принципом оптимальности. В данной работе это
компромиссное решение.
4
Формализация задачи территориального размещения
пунктов распределения в транспортной сети.
Пусть на плоскости задана сеть с пропускной способностью (N, k), где N
– конечное множество узлов, k – функция пропускной способности, которая
сопоставляет каждому ребру сети (x, y) неотрицательное число k(x, y) ≥ 0.
Пусть также в некоторых узлах сети, располагаются источники сырья, данное
сырьё является продуктом, стоимости единицы продукта для продавцов в
различных источниках сырья составляют набор чисел L = ( l 1 , . . . , l h ). От
источника сырья продукт доставляется в пункты распределения для
дальнейшей продажи, а в узлах, составляющих множество K = ( k 1 , . . . ,
kj
. . . k s ) располагаются покупатели этого продукта.
Для каждого ребра сети (x, y) определенно значение функции
транспортно-коррупционных издержек C a( x , y) для перемещения единицы
продукта для продавцов:
C a ( x , y) = C 'a ( x , y)
+ γ a (x , y) ,
где C 'a( x , y) величина транспортных издержек, γ a (x , y) коррупционные
издержки на ребре (x, y) для продавцов.
Также для каждого ребра сети (x, y) определенно значение функции
транспортно-коррупционных издержек C b( x , y) для перемещения по
данному ребру покупателей:
C b ( x , y) = C 'b ( x , y)
+ γ b (x , y) ,
где C 'b( x , y) величина транспортных издержек, γ b (x , y) коррупционные
издержки на ребре (x, y) для покупателей. Далее, в свободных узлах сети
может располагаться h пунктов распределения составляющих множество M =
( m 1 , . . . , mi , . . . m h ), в каждый из которых доставляется продукт.
Стоимость продукта P в пункте распределения для покупателей равна сумме
его стоимости в источнике сырья, где данный продукт закупают,
транспортных издержек при доставке его до пункта распределения и наценки
продавца:
5
P h = l h + C h( x , y) + T h ,
где l h стоимость продукта для продавцов в источнике сырья, C h( x , y)
сумма транспортно-коррупционных издержек на пути от источника сырья до
пункта распределения, T h наценка продавца. Владельцы пунктов
распределения желают их разместить в вершинах сети наиболее выгодным
для них образом с точки зрения максимизации получаемого дохода от
продажи этого продукта.
Таким образом, возникает задача размещения пунктов распределения в
некоторых точках сети в соответствии с выбранным принципом
оптимальности. В данной работе в качестве принципа оптимальности
рассматривается компромиссное решение.
Для нахождения компромиссного решения в задаче размещения нам
необходимо знать значение функции выигрыша каждого игрока. Игроками в
нашей задаче являются продавцы размещающие пункты распределения.
Значение функции выигрыша каждого игрока есть стоимость количества
продукта, который у него купили.
Алгоритм нахождения компромиссного решения.
i1
Шаг 1. Пусть Z множество допустимых решений z s ∈ Z , где
j1
p1 m 1
),
¿
z s =¿
i
j
…, pl mn )), i1=1,´i´1 ; j 1= 1,´ j́1 ; il =1,´ íl ; j n=1,´ j́ n – это возможные вершины
l
n
¿
расположения пунктов распределения при указанных ценах, а s – индекс,
которым перенумеровываются все допустимые решения и s = 1, . . . , ś .
6
z
z
(¿¿ s)
(¿ ¿ s ), … , R n ¿
R1 ¿
– доход i-ого пункта распределения при заданном z s .
z
R 1 (¿¿ s)
max ¿
s
Построим идеальный вектор
¿
z
R n (¿¿ s)
max ¿
– максимальное значение
s
M = [ M 1 ,… , M n ] =¿
дохода j-ого пункта распределения.
Шаг 2. Для каждого допустимого решения z s , s = 1, . . . , ś
составим матрицу невязок, которая в данном случае будет иметь вид
z
(¿¿ s)
M 1 −R 1 ¿
¿
z
, где s = 1, . . . ,
(¿¿ s)
M n −R n ¿
¿
A ¿=¿
ś .
Шаг 3. В полученной матрице невязок для каждого решения z s , s = 1,
. . . , ś из столбцов ( α s ,… , β s ) выбираем максимальное значение
δ s =max {α s , … , β s } .
s
Шаг 4. Выбираем минимальное из этих максимальных решений
min δ s , что и будет являться компромиссным решением.
s
Обзор литературы.
7
Информация о сетях, потоках в сетях представлены в книге [ 1 ] . Вопросы,
затрагивающие теорию игр и возможности её приложений рассмотрены в
книге [ 2 ] . Задачи относящиеся к области линейного программирования,
теории матричных игр представлены в книгах [ 3 ] , [ 4 ] .
Глава 1
Задача территориального размещения в сети
распределительных пунктов. Примеры.
1.1 Пример размещения двух пунктов распределения при
заданном расположении двух источников сырья и четырех
покупателей.
8
Рассматривается сеть N, изображенная на рисунке 1, содержащая 30
вершин x 0 , x 1 , x 2 ,…, x 29 и 51 ребро. На ребрах сети заданы два
значения функции транспортно-коррупционных издержек, одно для
продавцов, а другое для покупателей. В вершинах x 0 и x 29 находятся
источники сырья, на рисунке 1 они выделены красным цветом, стоимость
единицы продукта для продавцов в этих вершинах l 1=2 и l 2=3
соответсвенно. В сети выделено четыре вершины x 22 , x 15 , x 12 , x 16 в
которых продавцы могут расположить свои пункты распределения, на
рисунке 1 они выделены зеленым цветом, пункты распределения не могут
располагаться в одной вершине. Наценка продавца составляет 100% от
суммы издержек на покупку товара и на перевозку товара вдоль пути из
источника сырья в пункт распределения. Также в вершинах x 8 , x 21 , x 19 ,
x 26
располагаются покупатели, на рисунке 1 они выделены желтым цветом.
Рис.1
Транспортно-коррупционные издержки C a( x , y) = C 'a ( x , y) +
γ a (x , y)
для продавцов и C b( x , y) = C 'b ( x , y) + γ b (x , y) для покупателей
представлены в следующей таблице, где (x , y ) ребро сети, C 'a ( x , y)
транспортные издержки, γ a (x , y) коррупционные издержки на ребре (x, y)
для продавцов,
'
C b ( x , y)
транспортные издержки, γ b (x , y) коррупционные
издержки на ребре (x, y) для покупателей:
(x , y )
'
C a ( x , y)
γ a (x , y)
'
C b ( x , y)
9
γ b (x , y)
C a ( x , y)
C b ( x , y)
(0,11)
(11,4)
(4,14)
(14,18)
(18,23)
(23,26)
(26,29)
(29,28)
(28,25)
(25,21)
(21,9)
(9,12)
(12,7)
(7,5)
(5,1)
(1,0)
(0,6)
(11,6)
(4,13)
(14,16)
(18,19)
(18,24)
(23,24)
(29,27)
(28,27)
(25,22)
(25,15)
(21,15)
(21,2)
(9,2)
(9,3)
(12,3)
(7,8)
(5,8)
(1,8)
(8,6)
(6,13)
(13,16)
(16,20)
(20,19)
(19,17)
(17,22)
(22,24)
1
12
0
12
13
0
6
6
14
4
13
3
2
13
1
8
10
1
6
13
7
9
6
1
2
12
10
3
9
13
4
6
2
12
6
13
1
8
0
11
5
4
13
3
6
1
9
2
8
7
7
6
9
7
3
2
0
6
9
9
3
6
2
0
1
8
6
0
8
5
9
4
7
1
4
2
7
6
9
2
4
1
9
9
10
2
6
6
3
2
6
1
4
3
6
2
0
2
6
5
8
8
5
1
1
5
3
6
6
0
1
3
7
5
5
0
0
3
7
4
3
6
1
7
6
6
3
5
1
10
2
3
5
4
5
5
0
1
3
4
2
3
4
1
1
2
3
6
6
3
6
4
4
5
1
5
1
3
3
1
1
3
2
5
5
1
5
6
1
1
1
2
5
4
18
1
21
15
8
13
13
20
13
20
6
4
13
7
17
19
4
12
15
7
10
14
7
2
20
15
12
13
20
5
10
4
19
12
22
3
12
1
20
14
14
15
8
9
8
6
11
6
4
4
9
6
2
5
10
6
9
10
8
7
7
8
9
10
10
5
2
8
8
8
8
1
1
6
9
9
8
7
6
13
7
7
4
7
6
(24,27)
(17,15)
(17,20)
(20,2)
(2,10)
(10,3)
(3,8)
(10,13)
13
13
4
13
3
5
10
3
0
5
9
4
9
10
6
1
3
0
1
5
3
0
7
1
5
4
5
4
5
4
2
1
13
18
13
17
12
15
16
4
8
4
6
9
8
4
9
2
Таблица 1
Посчитаем транспортно-коррупционные издержки при доставке
продукта в каждую из четырех точек возможного расположения пунктов
распределения. Высчитаем вес кратчайших путей в графе от источников
сырья до точек возможного расположения пунктов распределения:
x0
x 29
x 22
x 15
x 12
x 16
53
38
54
47
39
71
25
61
Таблица 2
С учетом наценки продавца 100%, цена продукта во всех четырех
точках возможного расположения пунктов распределения:
x0
x 29
x 22
x 15
x 12
x 16
106
76
108
94
78
142
50
122
Таблица 3
Далее, посчитаем матрицу минимальных издержек всех путей из точек
расположения всех покупателей во все точки возможного расположения
пунктов распределения:
x 22
x8
x 21
x 19
x 26
26
14
11
22
x 15
20
8
8
25
x 12
15
7
22
30
x 16
26
19
14
31
Таблица 4
Построим матрицу доходов продавцов R i
в зависимости от выбора
ими расположения. Всего у нас 6 ситуаций:
(22,15) (22,12) (22,16) (15,12) (15,16) (12,16)
1
304
152
0
0
0
0
11
2
0
156
200
312
200
200
Таблица 5
i1
j1
p1 m 1
i
j
), p2 m2
¿
¿
z s =¿
2
Пусть Z множество допустимых решений z s ∈ Z , где
2
)), i1 ,i 2=1,2; j1 , j2=12,15,16,22 – это возможные вершины расположения
пунктов распределения при указанных ценах, а s – индекс, которым
перенумеровываются все допустимые решения и s = 1, . . . , ś .
z
R 1 (¿¿ s)
max ¿
s
¿
z
R 2 (¿¿ s)
max ¿
Построим идеальный вектор
–
s
M = [ M 1 ,… , M n ] =[ M 1 , M 2 ] =¿
максимальное значение дохода j-ого завода-магазина. В данном случае
M = ( 304,312 ) .
Для каждого допустимого решения z s , s = 1, . . . , ś составим
матрицу невязок, которая в данном случае будет иметь вид
z
(¿¿ s)
M 1 −R 1 ¿
¿
z
, где s =
(¿¿ s)
M 2 −R 2 ¿
¿
A ¿=¿
1, . . . , ś . ( α s , β s ) обозначают первый и второй столбцы соответственно.
( )
0
152
304
304
304
304
312
156
112
0
112
112
12
В полученной матрице невязок для каждого решения z s , s = 1, . . . ,
ś
{α s , β s } .
из столбцов ( α s , β s ) выбираем максимальное δ s =max
s
Выбираем минимальное из этих максимальных решений
min δ s =(152,156) , что и будет являться компромиссным решением.
s
Согласно найденному компромиссному решению, пункты
распределения необходимо расположить в точках x 12 и x 22 .
1.2 Пример размещения двух пунктов распределения при
заданном расположении двух источников сырья и шести
покупателей.
Рассматривается сеть N изображенная на рисунке 1, содержащая 42
вершины x 0 , x 1 , x 2 ,…, x 41 и 70 ребер. На ребрах сети заданы два
значения функции транспортно-коррупционных издержек, одно для
продавцов, а другое для покупателей. В вершинах x 0 и x 12 находятся
источники сырья, на рисунке 1 они выделены красным цветом, стоимость
единицы продукта для продавцов в этих вершинах l 1=2 и l 2=3
соответсвенно. В сети выделено четыре вершины x 5 , x 21 , x 37 , x 39 в
которых продавцы могут расположить свои пункты распределения, на
рисунке 1 они выделены зеленым цветом, пункты распределения не могут
располагаться в одной вершине. Наценка продавца составляет 100% от
суммы издержек на покупку товара и на перевозку товара вдоль пути из
источника сырья в пункт распределения. В вершинах
x 33 ,
x 41
x8 ,
x9 ,
x 18 ,
x 20 ,
сети N располагаются покупатели, на рисунке 1 они выделены
желтым цветом.
13
Рис.1
На участке сети (0,34) и (12,26) транспортно-коррупционные издержки
зависят от количества продукта n которое необходимо провезти по ребру и
равны 10n для ребер (14,15),(16,17),(25,29) и (27,28), 20 + n для ребер (15,17)
и (14,16), 10 + n для ребер (15,16),(25,24) и (23,28), 5 + n для ребер (29,27) и
(24,23), n для (29,24) и (27,23).
Рассмотрим участок сети (0,34) состоящий из семи дуг, где необходимо
провезти три единицы продукции из вершины x 0 в вершину x 34 .
Рассмотрим 3 пути, по которым могут провезти продукты, и составим
систему уравнений, чтобы найти решение, соответствующее равновесию по
Нэшу. Составим таблицу, в которой распишем возможные пути.
Рис.2
номер
пути
номера дуг, входящих
в путь
1 1-4
14
2 1-3-5
3 2-5
Таблица 1
Издержки, необходимые на преодоление каждого сегмента зависят от
количества продукта в данном сегменте. Пусть x1, x2, x3 – количество
продукта, провозимое по пути с соответствующим индексом. Тогда
соответственно, издержки, затраченные на каждый путь можно записать так:
1.
2.
3.
10 ( x 1+ x 2 ) +20+ x 1 – для первого маршрута
10 ( x 1+ x 2 ) +10+ x 2+10 ( x2 + x 3 ) – для второго маршрута
20+x 3 +10 ( x2 +x 3 ) – для третьего маршрута
После упрощения получим следующие выражения:
1.
2.
3.
11 x 1 +10 x 2+20
10 x 1+21 x 2 +10 x 3+10
10 x 2 +11 x 3 +20
Для равновесия по Нэшу все эти значения должны быть равны, это
приводит к системе уравнений:
11 x 1 +10 x 2+20
= 10 x1+21 x2 +10 x 3+10 = 10 x2 +11 x3 +20
При этом знаем, что x 1+ x2+ x3=3 , тогда составим и решим следующую
систему уравнений:
{
x 1 −11 x 2 −10 x3 =−10
11 x 1−11 x 3 =0
x 1 + x 2 + x 3=3
Решением уравнения является:
{
23
13
−7
x2=
13
23
x3=
13
x 1=
При подстановке полученного решения в исходную систему вычислим
1
общие издержки на участке (0,34), которые будут равны 34 13 .
15
Далее рассмотрим участок сети (12,26) состоящий из 10 дуг, где
необходимо провезти три единицы продукции из вершины x 12 в вершину
x 26 .
Рассмотрим 4 пути, по которым могут провезти продукты, и составим
систему уравнений, чтобы найти решение, соответствующее равновесию по
Нэшу. Составим таблицу, в которой распишем возможные пути.
Рис.3
номер
номера дуг, входящих
пути
в путь
1-4-7
1-3-5-6-7
2-5-6-7
2-5-8
1
2
3
4
Таблица 2
Издержки, необходимые на преодоление каждого сегмента зависят от
количества продукта в данном сегменте. Пусть x1, x2, x3, x4 – количество
продукта, провозимое по пути с соответствующим индексом. Тогда
соответственно, издержки, затраченные на каждый путь можно записать так:
1.
2.
3.
4.
10 ( x 1+ x 2 ) +5+ x1 +10 ( x 1+ x2 +x 3 ) – для первого маршрута
10 ( x 1+ x 2 ) + x 2+5+( x 2 +x 3 + x 4 ) + x 2 + x3 +10 ( x 1 + x2 + x3 ) – для второго маршрута
10+ ( x 3 + x 4 ) +5+ ( x 2+ x 3 + x 4 ) +x 2 + x3 +10 ( x 1 + x2 + x 3 ) – для третьего маршрута
10+ ( x 3 + x 4 ) +5+ ( x 2+ x 3 + x 4 ) +10+ x 4 – для четвертого маршрута
После упрощения получим следующие выражения:
1.
2.
3.
4.
21 x 1+20 x 2 +10 x 3+5
20 x 1 +23 x 2 +12 x 3+ x 4 +5
10 x 1+12 x 2 +13 x 3 +2 x 4 +15
x 2 +2 x 3 +3 x 4 +25
16
Для равновесия по Нэшу все эти значения должны быть равны, это
приводит к системе уравнений:
21 x 1 +20 x2 +10 x 3+5=20 x 1+23 x 2 +12 x 3 +x 4 +5=10 x 1 +12 x 2 +13 x 3 +2
x 4 +15=¿ x 2 +2 x3 +3 x 4 +25
При этом знаем, что x 1 + x2+ x3 + x4 =3 , тогда составим и решим
следующую систему уравнений:
{
x 1−3 x 2−2 x 3− x 4 =0
11 x 1 +8 x 2 −3 x 3 −2 x 4=10
21 x1 +19 x 2 +8 x 3−3 x 4 =20
x 1 +x 2 + x3 + x4 =3
Решением уравнения является:
{
31
23
−7
x2=
46
x 3=0
83
x 4=
46
x 1=
При подстановке полученного решения в исходную систему вычислим
6
общие издержки на участке (12,26), которые будут равны 30 23 .
Транспортно-коррупционные издержки C a( x , y) = C 'a ( x , y) +
γ a (x , y)
для продавцов и C b( x , y) = C 'b ( x , y) + γ b (x , y) для покупателей
представлены в следующей таблице, где (x , y ) ребро сети, C 'a ( x , y)
транспортные издержки, γ a (x , y) коррупционные издержки на ребре (x, y)
для продавцов,
'
C b ( x , y)
транспортные издержки, γ b (x , y) коррупционные
издержки на ребре (x, y) для покупателей:
(x , y )
C a ( x , y)
γ a (x , y)
C b ( x , y)
γ b (x , y)
C a ( x , y)
C b ( x , y)
(0,1)
(1,4)
(4,5)
(5,9)
(9,10)
(10,11)
15
4
8
14
1
5
15
9
0
2
6
7
15
4
5
3
1
3
15
5
0
6
2
3
30
13
8
16
7
12
30
9
5
9
3
6
'
'
17
(11,12)
(12,13)
(13,8)
(8,7)
(7,6)
(6,3)
(3,2)
(2,0)
(1,18)
(4,18)
(5,19)
(9,35)
(10,37)
(10,30)
(10,41)
(11,41)
(13,40)
(8,40)
(8,32)
(8,38)
(7,38)
(6,21)
(6,20)
(3,20)
(2,20)
(20,22)
(22,21)
(21,38)
(38,33)
(22,33)
(33,31)
(18,19)
(19,36)
(36,35)
(35,37)
(37,34)
(34,36)
(34,33)
(31,37)
(33,32)
(32,39)
(39,31)
(39,40)
15
15
3
4
12
12
6
15
3
8
7
6
7
9
12
2
6
13
14
8
13
5
5
6
1
4
13
1
5
4
13
13
13
5
10
2
5
12
11
3
2
2
7
15
15
1
5
4
5
1
15
3
2
3
1
10
9
6
10
10
6
5
2
4
1
3
2
4
7
0
8
3
6
4
3
3
3
4
7
6
9
6
6
6
6
7
15
15
3
2
2
1
4
15
2
7
3
3
3
7
8
5
2
4
4
6
1
2
6
4
0
1
2
2
4
1
1
8
3
5
3
5
0
1
1
1
3
2
4
18
15
15
3
5
2
6
1
15
6
6
2
3
3
2
5
5
0
6
3
5
2
2
3
1
5
1
4
4
2
6
5
3
0
4
3
4
1
6
0
4
2
5
4
30
30
4
9
16
17
7
30
6
10
10
7
17
18
18
12
16
19
19
10
17
6
8
8
5
11
13
9
8
10
17
16
16
8
14
9
11
21
17
9
8
8
14
30
30
6
7
4
7
5
30
8
13
5
6
6
9
13
10
2
10
7
11
3
4
9
5
5
2
6
6
6
7
6
11
3
9
6
9
1
7
1
5
5
7
8
(39,26)
(26,30)
(41,30)
(30,31)
3
4
5
13
0
9
2
0
5
2
3
2
3
1
1
0
3
13
7
13
8
3
4
2
Таблица 3
Вычислим транспортно-коррупционные издержки при доставке
продукта в каждую из четырех точек возможного расположения пунктов
распределения. Для этого воспользуемся алгоритмом Флойда и высчитаем
вес кратчайших путей в графе от источников сырья до точек возможного
расположения пунктов распределения:
x5
x 21
71
84
x0
x 12
x 37
72
67
x 39
43
58
68
33
Таблица 4
Таким образом, с учетом наценки продавца 100%, цена продукта во
всех четырех точках возможного расположения пунктов распределения:
x5
x0
x 12
x 21
146
174
x 37
148
140
x 39
90
122
140
72
Таблица 5
Далее, посчитаем матрицу минимальных весов всех путей из точек
расположения всех покупателей во все точки возможного расположения
пунктов распределения:
x5
x8
x9
x 18
x 20
x 33
x 41
x 21
28
9
16
25
16
25
x 37
15
28
34
8
12
24
x 39
19
9
24
16
7
7
12
17
32
19
10
13
Таблица 6
Построим матрицу доходов продавцов в зависимости от выбора ими
расположения. Всего у нас 6 ситуаций:
(5,21) (5,37) (5,39) (21,37) (21,39) (37,39)
1
292
0
0
0
0
0
2
560
540
432
540
432
432
Таблица 7
19
i1
j1
p1 m 1
i
j
), p2 m2
¿
¿
z s =¿
2
Пусть Z множество допустимых решений z s ∈ Z , где
2
)), i1 ,i 2=1,2, j1 , j2 =5,21,37,39 – это возможные вершины расположения
пунктов распределения при указанных ценах, а s – индекс, которым
перенумеровываются все допустимые решения и s = 1, . . . , ś .
z
R 1 (¿¿ s)
max ¿
s
¿
z
R 2 (¿¿ s)
max ¿
Построим идеальный вектор
–
s
M = [ M 1 ,… , M n ] =[ M 1 , M 2 ] =¿
максимальное значение дохода j-ого завода-магазина. В данном случае
M = ( 292,560 ) .
Для каждого допустимого решения z s , s = 1, . . . , ś составим
матрицу невязок, которая в данном случае будет иметь вид
z
(¿¿ s)
M 1 −R 1 ¿
¿
z
, где s =
(¿¿ s)
M 2 −R 2 ¿
¿
A ¿=¿
1, . . . , ś . ( α s , β s ) обозначают первый и второй столбцы соответственно.
( )
0
0
292 20
292 128
292 20
292 128
292 128
В полученной матрице невязок для каждого решения z s , s = 1, . . . ,
ś
{α s , β s } . Выбираем
из столбцов ( α s , β s ) выбираем максимальное δ s =max
s
20
δ s =(0,0) , что и будет
минимальное из этих максимальных решений min
s
являться компромиссным решением.
Согласно найденному компромиссному решению, пункты
распределения необходимо расположить в точках x 5 и x 21 .
1.3 Пример размещения трех пунктов распределения при
заданном расположении трех источников сырья и восьми
покупателей.
Рассматривается сеть N, изображенная на рисунке 1, содержащая 61
вершину x 0 , x 1 , x 2 ,…, x 60 и 89 ребер. На ребрах сети заданы два
значения функции транспортно-коррупционных издержек, одно для
продавцов, а другое для покупателей. В вершинах x 0 , x 8 , x 18 находятся
источники сырья, на рисунке 1 они выделены красным цветом, стоимость
единицы продукта для продавцов в этих вершинах l 1=2 , l 2=3 , l 3=2
соответственно. В сети выделено четыре вершины x 37 , x40 , x 52 , x 60 в которых
продавцы могут расположить свои пункты распределения, на рисунке 1 они
выделены зеленым цветом, пункты распределения не могут располагаться в
одной вершине. Наценка продавца составляет 100% от суммы издержек на
покупку товара и на перевозку товара вдоль пути из источника сырья в пункт
распределения. В вершинах x 25 , x35 , x49 , x 51 , x 53 , x54 , x55 , x 58 сети N
располагаются покупатели, на рисунке 1 они выделены желтым цветом.
21
Рис.1
На участке сети (0,7) и (8,15) транспортно-коррупционные издержки
зависят от количества продукта n которое необходимо провезти по ребру и
равны 5n для ребер (3,4),(5,6),(13,14) и (9,10), 15 + n для ребер (4,6) и (3,5), 5
+ n для ребер (4,5),(12,14) и (9,11), 10 + n для ребер (10,13) и (11,12), n для
(12,13) и (10,11).
Рассмотрим участок сети (0,7) состоящий из семи дуг, где необходимо
провезти две единицы продукции из вершины x 0 в вершину x 7 .
Рассмотрим 3 пути, по которым могут провезти продукты, и составим
систему уравнений, чтобы найти решение, соответствующее равновесию по
Нэшу. Составим таблицу, в которой распишем возможные пути.
Рис.2
номер номера дуг,
22
пути
входящих в путь
1 1-4
2 1-3-5
3 2-5
Таблица 1
Издержки, необходимые на преодоление каждого сегмента зависят от
количества продукта в данном сегменте. Пусть x1, x2, x3 – количество
продукта, провозимое по пути с соответствующим индексом. Тогда
соответственно, издержки, затраченные на каждый путь можно записать так:
4.
5.
6.
5 ( x1 + x 2 ) +15+ x1 – для первого маршрута
5 ( x1 + x 2 ) +5+ x2 +5 ( x 2 + x3 ) – для второго маршрута
15+ x 3 +5 ( x 2+ x 3 ) – для третьего маршрута
После упрощения получим следующие выражения:
4.
5.
6.
6 x 1 +5 x 2 +15
5 x 1 +11 x 2 +5 x 3 +5
5 x 2 +6 x 3 +15
Для равновесия по Нэшу все эти значения должны быть равны, это
приводит к системе уравнений:
6 x 1 +5 x2 +15 =
5 x 1 +11 x 2 +5 x 3 +5
= 5 x 2 +6 x3 +15
При этом знаем, что x 1+ x2+ x3=2 , тогда составим и решим следующую
систему уравнений:
{
x 1 −6 x 2−5 x 3 =−10
6 x1 −6 x 3 =0
x1 +x 2 + x 3 =2
Решением уравнения является:
{
x 1 =0,25
x 2=1,5
x 3 =0,25
При подстановке полученного решения в исходную систему вычислим
общие издержки на участке (0,7), которые будут равны 24.
Далее рассмотрим участок сети (8,15) состоящий из 10 дуг, где
необходимо провезти две единицы продукции из вершины x 8
x 15 .
23
в вершину
Рассмотрим 4 пути, по которым могут провезти продукты, и составим
систему уравнений, чтобы найти решение, соответствующее равновесию по
Нэшу. Составим таблицу, в которой распишем возможные пути.
Рис.3
номер
пути
1
2
3
4
номера дуг, входящих
в путь
1-4-7
1-3-5-6-7
2-5-6-7
2-5-8
Таблица 2
Издержки, необходимые на преодоление каждого сегмента зависят от
количества продукта в данном сегменте. Пусть x1, x2, x3, x4 – количество
продукта, провозимое по пути с соответствующим индексом. Тогда
соответственно, издержки, затраченные на каждый путь можно записать так:
5.
6.
7.
8.
5 ( x1 + x 2 ) +10+ x1 +5 ( x1 +x 2+ x 3 ) – для первого маршрута
5 ( x1 + x 2 ) + x 2 +10+( x 2 +x 3 + x 4 ) + x 2 + x3 +5 ( x 1 + x 2+ x 3 ) – для второго маршрута
5+ ( x3 + x 4 ) +10+ ( x 2+ x 3 + x 4 ) +x 2 + x3 +5 ( x 1+ x 2+ x 3 ) – для третьего маршрута
5+ ( x3 + x 4 ) +10+ ( x2 + x 3 + x4 ) +5 +x 4 – для четвертого маршрута
После упрощения получим следующие выражения:
5.
6.
7.
8.
11 x 1 +10 x 2+5 x 3 +10
10 x 1+13 x 2 +7 x 3 + x 4 +10
5 x 1 +7 x 2 + 8 x 3 + 2 x 4 +15
x 2 +2 x3 +3 x 4 +20
Для равновесия по Нэшу все эти значения должны быть равны, это
приводит к системе уравнений:
11 x1 +10 x 2+5 x 3 +10=10 x1 +13 x 2 +7 x 3+ x 4 +10=¿
¿ 5 x 1 +7 x 2 + 8 x 3 + 2 x 4 +15=x 2+2 x 3+3 x 4 +20
24
При этом знаем, что x 1 + x2+ x3 + x4 =2 , тогда составим и решим
следующую систему уравнений:
{
x1 −3 x 2−2 x3 −x 4 =0
6 x 1+3 x 2 −3 x 3−2 x 4 =5
11 x 1 +9 x 2+3 x 3−3 x 4 =10
x1 + x 2 +x 3 + x 4 =2
Решением уравнения является:
{
14
13
1
x2=
13
x 3=0
11
x4 =
13
x1=
При подстановке полученного решения в исходную систему вычислим
8
общие издержки на участке (8,15), которые будут равны 22 13 .
Транспортно-коррупционные издержки C a( x , y) = C 'a ( x , y) +
γ a (x , y)
для продавцов и C b( x , y) = C 'b ( x , y) + γ b (x , y) для покупателей
представлены в следующей таблице, где (x , y ) ребро сети, C 'a ( x , y)
транспортные издержки, γ a (x , y) коррупционные издержки на ребре (x, y)
для продавцов,
'
C b ( x , y)
транспортные издержки, γ b (x , y) коррупционные
издержки на ребре (x, y) для покупателей:
'
'
(x , y )
C a ( x , y)
γ a (x , y)
C b ( x , y)
γ b (x , y)
C a ( x , y)
C b ( x , y)
(0,1)
(1,45)
(45,46)
(46,47)
(47,30)
(30,18)
(18,23)
(23,44)
(44,43)
(43,16)
(16,8)
(8,17)
15
1
6
3
3
12
12
10
11
7
15
15
15
3
10
3
6
3
1
9
4
1
15
15
15
7
4
5
7
2
7
3
7
2
15
15
15
4
2
5
4
1
4
2
0
5
15
15
30
4
16
6
9
15
13
19
15
8
30
30
30
11
6
10
11
3
11
5
7
7
30
30
25
(17,42)
(42,41)
(41,24)
(24,31)
(31,29)
(29,40)
(40,38)
(38,39)
(39,2)
(2,0)
(1,55)
(45,55)
(46,34)
(47,35)
(30,20)
(18,19)
(23,21)
(44,53)
(43,54)
(16,54)
(17,51)
(42,51)
(41,51)
(41,56)
(24,60)
(31,26)
(29,57)
(40,48)
(38,58)
(39,58)
(2,58)
(55,34)
(34,33)
(33,35)
(35,20)
(20,19)
(19,21)
(21,53)
(53,50)
(50,54)
(50,49)
(49,15)
(15,51)
12
8
1
1
3
9
1
12
6
15
5
6
2
13
1
13
8
1
1
1
12
1
6
11
0
1
6
9
13
5
2
7
2
4
13
1
5
11
12
12
8
12
12
7
8
8
7
2
9
0
8
10
15
5
5
3
2
5
8
2
8
3
4
4
5
1
7
2
3
1
4
5
1
1
6
9
7
3
2
5
9
8
6
5
10
1
5
3
6
7
3
8
5
0
8
15
2
1
6
4
8
7
7
2
4
0
1
7
2
2
5
3
6
7
4
6
7
7
2
2
4
8
3
0
8
3
4
2
3
26
5
3
1
5
2
5
1
3
6
15
4
5
1
2
5
6
1
2
3
1
5
1
4
5
6
5
5
3
3
1
6
4
1
4
4
4
4
0
4
3
2
5
3
19
16
9
8
5
18
1
20
16
30
10
11
5
15
6
21
10
9
4
5
16
6
7
18
2
4
7
13
18
6
3
13
11
11
16
3
10
20
20
18
13
22
13
10
6
7
12
5
13
6
3
14
30
6
6
7
6
13
13
8
4
7
1
6
8
6
7
11
8
11
10
7
7
13
11
3
6
8
12
7
0
12
6
6
7
6
(15,27)
(51,27)
(56,60)
(27,60)
(26,28)
(28,57)
(57,48)
(48,58)
(33,32)
(32,20)
(32,7)
(32,36)
(32,52)
(7,48)
(7,52)
(7,25)
(52,22)
(20,36)
(36,22)
(22,25)
(22,59)
(25,28)
(22,26)
(21,36)
(36,59)
(59,37)
(26,37)
(59,49)
(37,15)
(26,27)
9
7
6
9
12
14
0
8
10
11
9
9
8
8
14
3
2
6
2
8
8
13
12
2
2
6
1
8
6
5
2
4
8
5
2
6
9
4
2
8
2
7
1
7
7
2
6
2
9
1
4
8
4
9
2
7
7
10
1
4
8
2
6
3
6
5
6
8
3
5
8
0
4
5
1
3
5
3
6
8
7
5
6
1
6
3
2
0
7
4
3
0
2
4
3
2
1
0
2
5
6
3
2
3
5
2
2
4
1
4
1
2
0
5
4
4
3
2
4
5
11
11
14
14
14
20
9
12
12
19
11
16
9
15
21
5
8
8
11
9
12
21
16
11
4
13
8
18
7
9
11
2
8
7
9
7
7
8
5
10
14
3
6
8
6
5
7
7
7
12
8
7
6
6
10
7
5
2
11
9
Таблица 3
Вычислим величину транспортно-коррупционных издержек при
доставке продукта в каждую из четырех точек возможного расположения
пунктов распределения. Для этого воспользуемся алгоритмом Флойда и
высчитаем вес кратчайших путей в графе от источников сырья до точек
возможного расположения пунктов распределения:
x 37
x0
x8
x 18
62
30
46
x 40
52
65
79
x 52
44
62
48
Таблица 4
27
x 60
68
48
68
С учетом наценки продавца 100%, цена продукта во всех четырех
точках возможного расположения пунктов распределения:
x0
x8
x 18
x 37
x 40
x 52
x 60
128
66
96
108
138
162
92
130
100
140
102
140
Таблица 5
Далее, посчитаем матрицу минимальных издержек всех путей из точек
расположения всех покупателей во все точки возможного расположения
пунктов распределения:
x 37
x 25
x 35
x 49
x 51
x 53
x 54
x 55
x 58
21
31
9
16
23
21
39
36
x 40
23
41
40
37
39
52
49
13
x 52
11
17
17
24
15
29
25
22
x 60
32
43
22
9
35
34
51
47
Таблица 6
Построим матрицу доходов продавцов R i
в зависимости от выбора
ими расположения. Всего у нас 4 ситуации:
(37,40,52
1
2
3
)
0
528
0
(37,40,60)
0
528
0
(37,52,60)
0
528
0
(40,52,60)
644
102
0
Таблица 7
i1
Пусть Z множество допустимых решений z s ∈ Z , где
i3
j3
p3 m3 )), i ,i ,i =1,2,3 ; j , j , j =37,40,52,60
1 2 3
1
2
3
¿
j1
p1 m 1
i
j
), p2 m2 ),
¿
¿
z s =¿
2
– это возможные вершины
расположения пунктов распределения при указанных ценах, а s – индекс,
которым перенумеровываются все допустимые решения и s = 1, . . . , ś .
28
2
z
R 1 (¿¿ s)
max ¿
s
¿
z
R 2 (¿¿ s)
max ¿
Построим идеальный вектор
–
s
¿
z
R 3 (¿¿ s)
max ¿
s
M = [ M 1 ,… , M n ] =[ M 1 , M 2 , M 3 ] =¿
максимальное значение дохода j-ого завода-магазина. В данном случае
M = ( 644,528,0 ) .
Для каждого допустимого решения z s , s = 1, . . . , ś составим
матрицу невязок, которая в данном случае будет иметь вид
z
(¿¿ s)
M 1−R 1 ¿
¿
z
(¿¿ s)
M 2−R 2 ¿ , где s =
¿
z
(¿¿ s)
M 3−R 3 ¿
¿
A ¿=¿
1, . . . , ś . ( α s , β s , µs ) обозначают первый, второй и третий столбцы
соответственно.
(
644
644
644
0
0
0
0
426
0
0
0
0
)
В полученной матрице невязок для каждого решения z s , s = 1, . . . ,
ś
{α s , β s , µs } .
из столбцов ( α s , β s , µs ) выбираем максимальное δ s =max
s
29
Выбираем минимальное из этих максимальных решений
min δ s =(0,426,0) , что и будет являться компромиссным решением.
s
Согласно найденному компромиссному решению, пункты
распределения необходимо расположить в точках x 40 , x 52 , x 60 .
Выводы.
Результатом проделанной работы, может стать следующий вывод:
поставленная задача решена полностью и проиллюстрирована на трёх
численных примерах. Первый пример описывает случай размещения двух
пунктов распределения в вершинах сети при заданном расположении двух
источников сырья и четырёх покупателей. Второй пример описывает
размещение двух пунктов распределения при заданном расположении двух
источников сырья и шести покупателей. Третий пример описывает случай
размещения трёх пунктов распределения при заданном расположении трёх
источников сырья и восьми покупателей. Для всех трёх примеров используя
принцип оптимальности, такой как компромиссное решение, в результате
вычислений найдено оптимальное расположение пунктов распределения в
узлах сети.
Заключение.
Рассмотренная в работе модель размещения в узлах сети с пропускной
способностью пунктов распределения, закупающих продукт по
фиксированным ценам в источнике сырья, с целью продажи данной
продукции покупателям, размещенным в узлах сети, с помощью
представленного алгоритма, проиллюстрированного на трёх примерах,
позволяет найти оптимальное размещение пунктов распределения в узлах
сети. Данная работа может быть использована на практике. В качестве
30
примера могут быть рассмотрены промежуточные пункты распределения
сырья, которые необходимо расположить в городах, различно удалённых друг
от друга.
Литература
[ 1 ] Малафеев О.А., Зубова А.Ф. Математическое и компьютерное
моделирование социально экономических систем на уровне многоагентного
взаимодействия (введение в проблемы равновесия, устойчивости и
надежности). – СПб.: Изд-во СпбГУ, 2006
[ 2 ] В.Н.Колокольцов, О.А.Малафеев, Теория игр для всех (моделирование
процессов конкуренции и кооперации)
[ 3 ] Гейл Д. Теория линейных экономических моделей. М.: Издательство
иностранной литературы, 1963. 408 с.
[ 4 ] Хемди А.Таха. Введение в исследование операций. М.-СПб-Киев:
Издательский дом "Вильямс 2005. 912 c.
31
Отзывы:
Авторизуйтесь, чтобы оставить отзыв