Файл: 4. сетевые оптимизационные модели общие свойства сетевых моделей.pdf

1
4. СЕТЕВЫЕ ОПТИМИЗАЦИОННЫЕ МОДЕЛИ
4.1. Общие свойства сетевых моделей
Сетевой моделью называется математическая модель, структура которой может быть изображена в виде графа, называемого сетью. Сеть есть множество узлов (вершин) и множество дуг (ребер), соединяющих различные пары узлов. На каждой дуге задана определенная ориентация, поэтому сеть является ориентированной.

2
x
ij
- объем перевозки
c
ij
- затраты на перевозку единицы продукции
Транспортная задача
1. Модель классической транспортной задачи
Кратко сущность классической транспортной задачи состоит в следующем. Пусть имеются m различных поставщиков (предприятий или пунктов отправления), располагающих продукцией одного и того же типа, которую они могут отправить n потребителям (пунктам назначений). При этом предприятие i может отгрузить не более S
i
единиц продукции, а потребителю j требуется не менее D
j
единиц. Затраты на перевозку единицы груза из пункта отправления i в пункт назначения j равны c
ij
. Требуется так распределить потребителей по поставщикам, чтобы минимизировать общие транспортные затраты. Сеть, соответствующая данной задаче, приведена на рис.33.
Рис. 33. Сеть классической транспортной задачи
Данной сети соответствует следующая модель транспортной задачи:
),
,
1
,
,
1
(
,...
2
,
1
,
0
спрос)
(
),
,
1
(
1
е)
предложени
(
),
,
1
(
1
min,
1 1
n
j
m
i
ij
x
n
j
j
D
m
i
ij
x
m
i
i
S
n
j
ij
x
ij
x
m
i
n
j
ij
c
















(1) где S
i
и D
j
– положительные целые числа.
Условия транспортной задачи можно записать в виде матрицы условий (рис.34), которая будет использована нами в дальнейшем при применении алгоритма оптимизации.
В этой матрице каждая строка соответствует одному пункту отправления, а каждый столбец – пункту назначения. с
11
с
12
с
1n с
21
с
22
с
2n с
m1
с m2
с mn
S
1
S
2
S
m
-D
1
-D
2
-D
n

3
ПН
ПО
1 2

n
Поставки
1
c
11
x
11
c
12
x
12

c
1n
x
1n
S
1 2
c
21
x
21
c
22
x
22

c
2n
x
2n
S
2






m
c
m1
x
m1
c
m2
x
m1

c
mn
x
mn
S
m
Спрос
D
1
D
2

D
n



i
j
j
D
i
S
Рис. 34. Матрица условий классической транспортной задачи
Примеры:
Дана сеть классической транспортной задачи:
1) Построить матрицу условий классической транспортной задачи:
ПО
ПН
4 5
6
ПОСТАВКИ
1 4
2 1
7
x
14
x
15
x
16
2 7
9 5
12
x
24
x
25
x
26
3 7
3 4
9
x
34
x
35
x
36
Спрос 10 10 8
28 4
2 1
7 9
5 7
3 4
1 2
3 6
5 4
7 12 9
- 10
-10
- 8

4
2) По матрице условий построить математическую модель:
Вводим переменные - x ij объем перевозки продукции от поставщика i к потребителю j. Используя формулы (1), получаем:
ЦФ - минимизация транспортных затрат, поэтому умножаем для каждого объема перевозки (x ij
) на соответствующее c ij
(затраты на перевозку единицы продукции) и все складываем.
Ограничения:
Записываем суммы по строкам (для поставщиков) и приравниваем к объемам поставки.
Записываем суммы по столбцам (для потребителей) и приравниваем к объемам спроса.
Тогда получаем ММ
4x
14
+ 2x
15
+ x
16
+ 7x
24
+ 9x
25
+ 5x
26
+ 7x
34
+ 3x
35
+ 4x
36

min,
x
14
+ x
15
+ x
16
=
7,
x
24
+ x
25
+ x
26
=
12,
x
34
+ x
35
+ x
36
=
9,
x
14
+
x
24
+
x
34
=
10,
x
15
+
x
25
+ x
35
=
10,
x
16
+
x
26
+ x
36
=
8,
x
ij
≥0, i=1,2,3 j=4,5,6
2. Транспортная задача с промежуточными пунктами
Большое практическое значение имеет обобщение классической транспортной модели на случай, когда некоторые пункты служат для перевалки грузов.
На рис.35 представлена схематическая карта в виде сети. Узлы сети соответствуют 4 пунктам (складам). Положительное число, стоящее у пункта (склада), обозначает избыток запасов в пункте (на пункте), который должен быть распределен в системе. Отрицательное число обозначает потребность пункта (склада) в дополнительных запасах.
Таким образом, в пункте (на складе) 1 избыток запасов, а в пункте (на складе) 4 требуются дополнительные запасы. Распределяемый ресурс может транспортироваться через пункты (склады) 2 и 3, поэтому эти

5 пункты (склады) называются промежуточными. Пункт (Склад) 1 является источником (пунктом отправления), а склад 4 – стоком (пунктом назначения). Необходимо так перераспределить запасы на складах, чтобы общие транспортные расходы при этом были минимальными.
2.1 Построим модель транспортной задачи по заданной сети
Модель строится следующим образом.
ЦФ (используя формулу ЦФ из (1)): Каждая дуга именуется переменной x ij
. Затем составляется сумма – вес дуги (затраты на перевозку) * на переменную дуги и т.д. для всех дуг. Функция минимизируется.
Ограничения:
1) количество ограничений равно числу пунктов в сети.
2) для каждого пункта сети записываем сумму: если дуга исходит из пункта, то переменная x ij берется со знаком «+», если входит – со знаком «-«. Данная сумма приравнивается числу у вершины
Для данной сети получаем математическую модель:
13 x
12
+12 x
13
+8 x
14
+14 x
24
+12 x
34

min,
x
12
+ x
13
+ x
14
=
1,
– x
12
+ x
24
=
0,
– x
13
+ x
34
=
0,
– x
14
– x
24
–
x
34
=
–1,
x
ij
> 0 для всех (i, j).
2.2 Решим обратную задачу – по заданной ММ построить сеть.
Имеем математическую модель:
15x
12
+ 21 x
13
+ 9 x
14
+ 5 x
23
+ 24 x
24
+ 8x
34

min,
x
12
+ x
13
+ x
14
=
1,
–x
12
+ x
23
+ x
24
=
0,
–x
13
–x
23
+ x
34
= 0,
2 3
1 4
+1
-1 13 14 8
12 12

6
–x
14
– x
24
–
x
34
= –1,
x
ij
> 0 для всех (i, j).
Получаем сеть:
2.3 Построим матрицу условий классической транспортной
задачи для транспортной задачи с промежуточными пунктами по
заданной сети
Рис. 35. Пример транспортной сети с промежуточными пунктами
Матрица классической транспортной задачи строится следующим образом: каждая строка матрицы соответствует пункту с избытком запасов, а столбец – пункту с недостатком запасов. Для приведенного примера соответствующая матрица приведена на рис. 36. В этой матрице
c
’
ij
есть минимальные затраты на перемещение единицы груза из пункта i в пункт j. Таким образом, прежде чем строить данную матрицу, необходимо найти кратчайший путь из каждого узла, в котором имеется избыток запасов, в каждый узел, где их недостаток.
2 3
1 4
+1
-1 15 24 9
21 8
5
-3 1
7 3
2 4
5 8
6
+10 0
0 0
+2
-8
-1
C
12
C
23
C
25
C
43
C
47
C
78
C
54
C
45
C
56
C
67

7
ПН
ПО
3 6
8
Поставки
1 4
c
’
13
X
13
c
’
16
X
16
c
’
18
X
18 10
c
’
43
X
43
c
’
46
X
46
c
’
48
X
48 2
Спрос
3 1
8 12
Рис. 36. Матрица условий, соответствующая сети на рис. 35
Пример
Имеем транспортную сеть с промежуточными пунктами. Видим, что пунктами отправления
(поставщиками, истоками) являются п.1 и п.4 (т.к. у них имеется запас продукции). Пунктами назначения – п.3 и п.5 (т.к. у них есть недостаток продукции). П.2 является промежуточным.
Создаем матрицу условий: ПО – 1 и 4; ПН – 3 и 5. Для записи затрат, соответствующих перевозу товара из ПО в ПН, найдем все кратчайшие пути от узлов истоков до узлов стоков:

- т.к. ранее не было найдено пути в данный пункт
1) Найдем кратчайшие пути из пункта 1 (из первого пункта отправления) в п. 3 и 5 всеми возможными путями:
Из п.1 в п.2, 3 1
0
y

,


2
min 0 2,
2
y

  
,


3
min 0 3,
3
y

  
;
Из пункта 2 в п. 3,4, 5:
2 2
y

,
3
min(2 4,3)
3
y



,
4
min(2 3, )
5
y

  
,


5
min 2 4,
6
y

  
;
Из пункта 3 в п. 4:
3 3
y

,
4
min(3 5,5)
5
y



;
+3
-2 3
2 3
1 4
5
+1
-2 2
3 4
3 4
1 5

8
Найдем кратчайшие пути из пункта 4 в п. 5:
4 5
y

,
5
min(5 1,6)
6
y



;
5 6
y

2) Найдем кратчайшие пути из пункта 4 (из второго пункта отправления):
Найдем кратчайшие пути из пункта 4 в п. 5:
4 0
y

,
5
min(0 1, ) 1
y

  
;
Найдем кратчайшие пути из пункта 4 в п. 3:
5 1
y

,
2
min(1 3, )
4
y

  
;
2 4
y

,
3
min(4 4, )
8
y

  
;
3 8
y

;
1
y
 
Запишем матрицу условий классической транспортной задачи:
ПО
ПН
3 5
ПОСТАВКИ
1 3
6 3
x
13
x
15
4 8
1 1
x
43
x
45
Спрос 2 2
4
3. Метод потенциалов
Для поиска оптимального решения транспортной задачи используется метод потенциалов.
Метод потенциалов включает те же шаги, что и симплексный алгоритм. Сущность этого метода рассмотрим на примере классической транспортной задачи, матрица условий которой приведена на рис. 37.

9
МУ
ПН
ПО
1
2
3
Поставки
1
2
20
7 7
20
2
1
20
1
20
1
10
50
3
9
5 8
10
10
Спрос
40
20
20
80
Рис.37
Шаг 1. Необходимо выявить любой допустимый базис исходной задачи, состоящий из (m+n-1) переменной. Для выполнения данного шага будем использовать так называемый метод северо-западного угла.
Название метода обусловлено тем, что распределение поставок по потребителям начинается с верхнего левого угла, который на географических картах соответствует северо-западу.
При этом сначала полностью распределим мощность первого поставщика, затем – второго и так далее. Элементы полученного таким образом исходного базиса поместим в соответствующие клетки матрицы условий (рис.37). (Не обращайте пока внимание на выделенные числа и предшествующие им знаки «+» и «-»).
Начальное значение целевой функции:
2*20+1*20+1*20+1*10+8*10 = 170
Итерация 1
Шаг 2. Ищется такая небазисная переменная x
ij
, за счет включения которой в базис можно улучшить значение целевой функции.
Построим матрицу оценок (рис.38):
1) В этой матрице сначала заполняются клетки, соответствующие базисным маршрутам. Во все эти клетки ставится цифра 0.
2) Затем записывается любое значение какой-то одной двойственной переменной.

10 3) Затем проставляются значения всех остальных двойственных переменных такие, чтобы для всех клеток с 0 выполнялось:

i
+

j
= c
ij
.
4) После этого во всех клетках, соответствующих небазисным переменным, записывается

i
+

j
- c
ij
.
МО
ПН
ПО
1
2
3

i
1
2
0
7
-5
7
-5
0
2
1
0
1
0
1
0
-1
3
9
-1
5
3
8
0
6
j

2
2
2
Рис.38
Если каждое значение оценки небазисной переменной в матрице оценок не положительно, то исходное базисное решение является оптимальным. Если указанная величина для какой-то небазисной переменной положительна, то соответствующая переменная является кандидатом на включение в следующий базис. Если таких переменных несколько, из них в базис включается та, которой соответствует наибольшее значение

i
+

j
-c
ij
Значит, в нашем примере ввести в базис необходимо переменную x
32
Шаг 3. Находится тот маршрут, который исключается из базиса.
Поставим знак «+» в той клетке матрицы условий, которая соответствует вновь вводимой переменной, в примере это клетка (3,2)
(рис.37). Так как мы будем брать для нового маршрута продукцию у поставщика 3, мы должны уменьшить на эту же величину какую-то прежнюю поставку от того же поставщика. Это вызовет необходимость скомпенсировать спрос соответствующего потребителя за счет другого поставщика и т.д. В результате мы должны выявить на матрице условий

11 замкнутый контур (цикл), который содержит вновь вводимую переменную x
32
. Каждый элемент цикла со знаком «+» обязательно компенсируется двумя элементами со знаком «-», один из которых записывается в этой же строке, а второй – в этом же столбце. Цикл
(контур) перераспределения не обязательно должен быть четырехугольным, но все его углы обязательно должны быть прямыми.
После того, как в матрице условий обозначен цикл из знаков «+» и «-
», необходимо определить предельную величину перераспределения по данному циклу. Эта величина определяется наименьшим содержимым клетки со знаком «-». В рассматриваемом примере (см. рис.37) первой обращается в 0 переменная x
33
. Ее мы и исключим из базиса.
Шаг 4. Определяются значения переменных нового базиса.
Содержимое клеток матрицы условий со знаком «+» увеличивается, а со знаком «-» уменьшается на величину переменной, исключенной из базиса. В примере эта величина равна 10 (см. рис. 37).
Значения переменных нового базиса поместим в матрицу условий для следующей итерации (рис.39).
МУ
ПН
ПО
1
2
3
Поставки
1
2
20
7 7
20
2
1
20
1
10
1
20
50
3
9
5
10
8
10
Спрос
40
20
20
80
Рис.39
Значения переменных нового базиса: x
11
=20, x
21
=20, x
22
=10, x
23
=20,
x
32
=10.
Целевая функция равна: 2*20+1*20+1*10+1*20+5*10 = 140