Файл: Учебнометодическое пособие по дисциплине Логистика производства для инженеров техники и технологий по специальности 230104 Системы автоматизированного проектирования.pdf

77
Допустим, что есть маршруты транспортировки от каждого рудника к каждому комбинату, т.е. мы имеем двудольный граф, связывающий два вида хозяйствующих субъектов, и возможность выбора маршрутов перевозки.
Общая идея, на которой основаны алгоритмы решения сетевых задач, состоит в том, что на каждой итерации выполняются два из трех условий:
•
Допустимость исходной задачи, т.е. соотношения (3.7) – (3.10);
•
Допустимость двойственной задачи (3.12) – (3.13);
•
Условие дополнительной нежесткости.
Матричная форма записи транспортной задачи в данном примере, с учетом структуры связей, представленных на рис. 2.4, имеет вид.
Объем перевозок
x
11
x
12
x
13
x
14
x
21
x
22
x
23
x
24
x
31
x
32
x
33
x
34
1
1
1
1
1
< S
1
2
1
1
1
1
< S
2
3
1
1
1
1
< S
3
П
ос
т
ав
щ
ик
и
(3.15)
1 -1
-1
-1
< D
1
2
-1
-1
-1
< D
2
3
-1
-1
-1
< D
3
П
от
ре
би
т
ел
и
4
-1
-1
-1
< D
4
c
11
c
12
c
13
c
14
c
21
c
22
c
23
c
24
c
31
c
32
c
33
c
34
min
Сетевую модель приведем к виду классической транспортной задачи, описываемому матрицей порядка m х n, в данном случае это 3 х 4. В каждой ячейке даны стоимость транспортировки c
ij
и объем перевозимого продукта x
ij
в качестве переменной. Запишем матрицу для этой задачи, в которой показаны значения исходных данных:
Рудник 3
ГОК 4
Рис. 3.4. Структура задачи транспортировки продукции рудников на горно- обогатительные комбинаты
Рудник 1
Рудник 2
ГОК 3
ГОК 2
ГОК 1 x
11
x
34
S
i
D
j
S
1
= 60
D
2
= 50 с
11
= 2 с
34
= 9
S
3
= 100
PDF created with pdfFactory Pro trial version www.pdffactory.com

78
1
2
3
4
Поставки
1 c
11
= 2
x
11
c
12
= 3
x
12
c
13
= 11
x
13
c
14
= 7
x
14
S
1
= 60
2 c
21
= 1
x
21
c
22
= 0
x
22
c
23
= 6
x
23
c
24
= 1
x
24
S
2
= 10
3 c
31
= 5
x
31
c
32
= 8
x
32
c
33
= 15
x
33
c
34
= 9
x
34
S
3
= 100
Спрос
D
1
= 70
D
2
= 50
D
3
= 30
D
4
= 20
(3.16)
Применение алгоритма решения транспортной задачи.
Этапы решения данной задачи были представлены выше. Приведем общие соображения последовательности ее решения с использованием алгоритма симплекс-метода. Пусть есть пробное допустимое базисное решение, содержащее m + n – 1 маршрутов. Направим единичный поток по небазисному маршруту, тогда для сохранения допустимости необходимо снять единицу с базисного маршрута в тех же строке и столбце, где находится новый маршрут.
Эти два изменения ведут к единичным изменениям потоков грузов по всем другим базисным переменным. Эти потоки увеличивают или уменьшают по схеме изменений, которая определяется однозначно, до тех пор пока базисная переменная не уменьшится до нуля, т.е. будет выведена из базиса.
Эту сложную процедуру можно упростить за счет использования теоремы двойственности и структуры сети. Для заданного базисного решения значение переменной, определяемое введением единицы небазисной переменной, равно разности левой и правой частей ограничения двойственной задачи, относящегося к этой переменной. Таким образом, задача состоит в том, чтобы решить m + n – 1 ограничений двойственной задачи, соответствующих текущему базису
v
i
+ w
j
= c
ij
для каждой базисной переменной x
ij
, (3.17)
а затем определить значения
v
i
+ w
j
– c
ij
для небазисной переменной x
ij
. (3.18)
Полученные в (2.17) величины соответствуют коэффициентам нулевой строки симлексной матрицы. Если их значение положительно, небазисная переменная может быть введена в следующий базис. Если же в (3.17) все значения неположительные, а решение допустимо и для прямой, и для двойственной задачи, то это текущее базисное решение оптимальное.
Теперь будем решать задачу, представленную матрицей (3.16).
1. Следует определить исходный пробный базис, содержащий m + n – 1 маршрутов. Пусть поставщик в строке 1 отправляет всю продукцию по самому дешевому маршруту (1, 1). Потенциал данного поставщика исчерпан, а потребителю, соответствующему столбцу 1, требуется еще 10 единиц. Дадим поставку в 10 единиц по строке 2 по самому дешевому маршруту (2, 2). Далее поставки в 100 единиц по строке 3 распределим по остальным маршрутам, где есть неудовлетворенный спрос. В результате получим матрицу (3.19).
PDF created with pdfFactory Pro trial version www.pdffactory.com

79
1
2
3
4
Поставки
1
c
11
= 2
60
c
12
= 3
x
12
=0
c
13
= 11
x
13
= 0
c
14
= 7
x
14
= 0
S
1
= 60
2
c
21
= 1
x
21
=0
c
22
= 0
10
c
23
= 6
x
23
= 0
c
24
= 1
x
24
= 0
S
2
= 10
3
c
31
= 5
10
c
32
= 8
40
c
33
= 15
30
c
34
= 9
20
S
3
= 100
Спрос
D
1
= 70
D
2
= 50
D
3
= 30
D
4
= 20
(3.19)
Значение целевой функции для данного варианта доставки равно:
2 х 60 + 0 х 10 + 5 х 10 + 8 х 40 + 15 х 30 + 9 х 20 = 1120.
Шаг 2 алгоритма предполагает оценку каждого неиспользованного маршрута для проверки возможности улучшения целевой функции. Для этого можно рассмотреть, например, маршрут (1, 2). Из матрицы (3.19) видно, что выделенную на новый маршрут единицу надо изъять из потока по старому маршруту (1, 1). Тогда для удовлетворения спроса по столбцу 1 придется доставить еще одну единицу по маршруту (3, 1). А эту единицу придется забрать у маршрута (3, 2).
Чтобы представить эти изменения, надо построить следующую матрицу по образу (3.19). Далее надо определить, приведут ли эти действия к уменьшению значения целевой функции. И так далее.
Вместе с тем нет необходимости в каждом случае определять конкретную схему изменений. Все это можно сделать быстрее, оценивая значения переменных двойственной задачи и сравнивая затем различия между правыми и левыми частями двойственных ограничений, соответствующих небазисным маршрутам. Это позволяет сделать структура сети.
В (3.17) показана система линейных равенств, из которых получаем пробные значения переменных двойственной задачи. Двойственная задача для шести базисных маршрутов в данном случае принимает следующий вид.
v
1
+ w
1
= 2 маршрут (1, 1),
v
2
+ w
2
= 0 маршрут (2, 2),
v
3
+ w
1
= 5 маршрут (3, 1),
v
3
+ w
2
= 8 маршрут (3, 2), (3.20)
v
3
+ w
3
= 15 маршрут (3, 3),
v
3
+ w
4
= 9 маршрут (3, 4).
Двойственные переменные соответствуют пунктам отправки и назначения, а связывающие их уравнения определяют маршрут. Получили систему из 6 уравнений с семью неизвестными. Надо выбрать одну переменную и задать ей любое произвольное значение. Например, значение, равное нулю. Выберем v
3
, поскольку она входит в четыре соотношения (3.20), и примем для удобства ее значение равным нулю, т.е. v
3
= 0. Исключить одну переменную можно в силу избыточности системы ограничений на спрос и поставки, где одно ограничение, как было показано выше, линейно зависит от других. Теперь можно найти значения всех остальных переменных.
PDF created with pdfFactory Pro trial version www.pdffactory.com

80
v
3
= 0,
w
4
= 9 – v
3
= 9,
w
3
= 15 – v
3
= 15,
w
2
= 8 – v
3
= 8,
w
1
= 5 – v
3
= 5, (3.21)
v
2
= 0 – w
2
= 0 – 8 = – 8,
v
1
= 2 – w
1
= 2 – 5 = – 3.
Теперь, зная значения переменных, найденных на предыдущем шаге, можно последовательно получить значения всех двойственных переменных.
Эту возможность обеспечивает наличие сетевой структуры.
Далее рассмотрим свойства треугольной структуры, которая обеспечит получение решения транспортной задачи. Термин триангуляция используется для описания структуры, которая позволяет последовательно получить значения переменных. Система линейных уравнений имеет треугольную
структуру, если можно сгруппировать переменные и уравнения так, чтобы переменная, стоящая на первом месте в l-м уравнении, являлась также l-й неизвестной и не появлялась больше ни в одном уравнении, номер которого больше l.
Уравнения (3.20), как можно видеть, принимают треугольную структуру, с учетом того, что мы приняли v
3
= 0. Если выбрать другую двойственную переменную и придать ей произвольное значение (например, равенство нулю), то потребуется изменить порядок следования уравнений, чтобы получить треугольную структуру в явном виде.
Из теорем двойственности следует, что свойством треугольной структуры обладает также система уравнений прямой задачи, которая определяет значения базисных переменных x
ij
. Запишем ограничения, описывающие сохранение потока в сети. Для этого запишем ограничения, исключив маршруты, не вошедшие в базис, а также ставшее избыточным уравнение поставки, соответствующее строке 3; это эквивалентно выбору v
3
= 0.
x
11
= 60 строка 1,
x
22
= 10 строка 2,
x
11
+ x
31
= 70 столбец 1,
x
22
+ x
32
= 50 столбец 2, (3.22)
x
33
= 30 столбец 3,
x
34
= 20 столбец 4.
Здесь строка коэффициентов l–го уравнения является столбцом коэффициентов при l–й переменной в (3.20), где система уравнений имеет вид верхнего треугольника, не считая v
3
. Система (3.22) имеет вид нижнего треугольника. Ее можно решить последовательно, начиная с переменной x
11
Теперь можно получить оценку каждого не входящего в базис маршрута по формуле (3.18). Используя значения переменных, найденные в (3.21), и подставляя их последовательно в (3.18), получим в результате следующие значения.
PDF created with pdfFactory Pro trial version www.pdffactory.com

81
– 3 + 8 – 3 = 2маршрут (1, 2),
– 3 + 15 – 11 = 1 маршрут (1, 3),
– 3 + 9 – 7 = – 1 маршрут (1, 4),
– 8 + 5 – 1 = – 4 маршрут (2, 1), (3.23)
– 8 + 15 – 6 = 1 маршрут (2, 3),
– 8 + 9 – 1 = 0маршрут (2, 4).
Каждое положительное значение указывает на возможность уменьшения значения целевой функции. Из трех таких маршрутов наибольшую оценку имеет маршрут (1, 2), его и надо выбрать. По сути это соответствует симплекс- критерию 1 (минимизации).
Шаг 3. Определим величину потока, направленного по маршруту (1, 2).
Для того чтобы перейти на этот маршрут, необходимо уменьшить потоки по маршрутам (1, 1) и (3, 2). Потоки по ним в текущем решении, как было показано в (2.19), имели значения 60 и 40. Таким образом, наибольшее допустимое увеличение потока по маршруту (1, 2) равно 40, поэтому маршрут
(3, 2) из нового базиса исключается.
Шаг 4. Внесем изменения в маршруты перевозки грузов. Получаем второе базисное решение. Схема изменений базисных переменных для этого маршрута имеет вид.
1
2
3
4
Поставки
1
20
40
S
1
= 60
2
10
S
2
= 10
3
50
30
20
S
3
= 100
Спрос
D
1
= 70
D
2
= 50
D
3
= 30
D
4
= 20
(3.24)
Общие затраты на этом этапе равны:
Общие затраты на первом этапе – экономия от смены маршрута =
= 1120 – 2 х 40 = 1040.
Итерация 2. Переходим к шагу 2 для проверки оптимальности найденного второго решения или возможности его дальнейшего улучшения. Двойственные отношения в новом базисе принимают вид.
v
2
+ w
2
= 0 маршрут (2, 2),
w
2
+ v
1
= 3 маршрут (1, 2),
v
1
+ w
1
= 2 маршрут (1, 1),
w
1
+ v
3
= 5 маршрут (3, 1), (3.25)
w
3
+ v
3
= 15 маршрут (3, 3),
w
4
+ v
3
= 9 маршрут (3, 4).
Уравнения и переменные в (3.25) представлены в треугольном формате относительно переменной v
3
. Легко показать, что переменные в решении имеют значения, которые студентам предлагается найти самостоятельно: v
3
= 0,
PDF created with pdfFactory Pro trial version www.pdffactory.com

82
w
4
= 9,
w
3
= 15,
w
1
= 5, (3.26)
v
1
= 2 – w
1
= – 3,
w
2
= 3 – v
1
= 6,
v
2
= 0 – w
2
= – 6.
Оценки маршрутов теперь равны.
– 3 + 15 – 11 = 1 маршрут (1, 3),
– 3 + 9 – 7 = – 1маршрут (1, 4),
– 6 + 5 – 1 = – 2 маршрут (2, 1),
– 6 + 15 – 6 = 3 маршрут (2, 3), (3.27)
– 6 + 9 – 1 = 2 маршрут (2, 4),
0 + 6 – 8 = – 2маршрут (3, 2).
Наибольшее положительное значение имеет маршрут (2, 3), он и вводится в новое решение. Для этого необходимо изменить схему маршрутов. Поток по маршрутам (2, 2), (1, 1) и (3, 3) уменьшается. Маршрут (2, 2) выводится из базиса раньше, когда общее изменение потока равно 10. Поэтому величины, стоящие в ячейках матрицы (3.28), представляют собой потоки третьего пробного базиса. Схема изменений базисных переменных и потоков для маршрута (2, 3) имеет вид:
1
2
3
4
Поставки
1
20 – 10
40 – 10
S
1
= 60
2
10 – 10
+ 10
S
2
= 10
3
50 + 10
30 – 10
20
S
3
= 100
Спрос
D
1
= 70
D
2
= 50
D
3
= 30
D
4
= 20
(3.28)
Общие затраты на этом этапе равны:
Общие затраты на втором этапе – экономия от смены маршрута =
= 1040 – 1 х 30 = 1010.
Далее заметим, что нет необходимости рассматривать двойственные уравнения для всех базисных переменных. Можно упростить процедуру выполнения шага 2 алгоритма, сведя ее к заполнению оценками таблицы размером m х n, в данном случае – 3 х 4.
Выполним упрощенную процедуру для итерации 3.
Сначала создадим таблицу (3.29), в которой запишем значения всех переменных в верхних углах ячеек и символ 0 для каждого маршрута, входящего в базис при текущем решении. Получим оценки небазисных маршрутов в третьем решении.
Необходимо выбрать любую из величин v
i
или w
j
и придать ей произвольное значение. Предположим, что по-прежнему v
3
= 0, и это значение записано справа от строки 3. Ищем в данной строке базисные маршруты.
Находим, что в строке 3 это маршруты (3, 1), (3, 3) и (3, 4). Двойственное
PDF created with pdfFactory Pro trial version www.pdffactory.com

83 уравнение для каждого из этих маршрутов позволяет найти значение другой двойственной переменной. Здесь это переменные w
j
= 5, w
j
= 15, w
j
= 9, значения которых следует записать под столбцами таблицы.
1
2
3
4
v
i
1
c
11
= 2
0
c
12
= 3
0
c
13
= 11
x
13
=10
c
14
= 7
– 10
– 30
2
c
21
= 1
– 50
c
22
= 0
– 30
c
23
= 6
x
23
= 0
c
24
= 1
– 10
– 90
3
c
31
= 5
0
c
32
= 8
– 20
c
33
= 15
0
c
34
= 9
0
0
w
j
50
60
150
90
(3.29)
Получим четвертое, и оптимальное, базисное решение.
1
2
3
4
Поставки
1
50
10
S
1
= 60
2
10
S
2
= 10
3
70
10
20
S
3
= 100
Спрос
D
1
= 70
D
2
= 50
D
3
= 30
D
4
= 20
(3.30)
Общие (наименьшие) затраты теперь равны:
Общие затраты на третьем этапе – экономия от смены маршрута =
= 1010 – 1 х 10 = 1000.
Таким образом, получено оптимальное решение данного примера транспортной задачи.
Заметим, что в отечественной литературе этот подход к решению называется метод потенциалов.