Стариков А.В., Кущева И.С. Экономико-математическое и компьютерное моделирование: методические указания
Подождите немного. Документ загружается.
31
Стоимости перевозок (в р. за м
3
) проставлены в правом верхнем углу каждой
клетки так называемой транспортной таблицы (табл. 3.1).
Отыскание опорного плана ТЗ
Прежде всего, необходимо получить опорный план. Это допустимое
решение ТЗ, которое используется в качестве начального базисного решения
при нахождении оптимального решения методом потенциалов. В данной работе
рассматриваются три метода нахождения опорного плана: северо-западного
угла, наименьшей стоимости и Фогеля.
Таблица 3.1
Самый простой метод отыскания опорного решения ТЗ – метод северо–
западного угла (СЗУ) – состоит в последовательном заполнении клеток
транспортной таблицы. На каждом шаге метода из всех не вычеркнутых клеток
выбирается самая левая верхняя клетка (северо-западный угол таблицы). Как
правило, опорное решение, полученное таким способом (табл. 3.2), значительно
отличается от оптимального, поскольку при его отыскании нигде не
учитывается стоимость перевозок.
Проверим, является ли полученный план допустимым. В нём сумма
перевозок по строке равна запасу соответствующего ПО, а сумма перевозок по
столбцу – заявке соответствующего ПН. Все заявки удовлетворены, все запасы
израсходованы (сумма запасов равна сумме заявок и выражается числом 130,
стоящим в правом нижнем углу таблицы).
Проанализируем, является ли план перевозок, данный в табл. 3.2,
опорным. Так как число свободных клеток в таблице равно (m–1)(n–1)=2·3=6,
план является опорным.
Общие затраты на перевозку при этом будут равны
ПО\ПН
B
1
B
2
B
3
B
4
Запасы a
i
5
2
6
11
A
1
35
4
7
12
8
A
2
45
9
1
3
10
A
3
50
Заявки b
j
30 10 65 25 130
32
Z =30 ⋅ 5+5 ⋅ 2+5 ⋅ 7+40 ⋅ 12+25 ⋅ 3+10 ⋅ 25=1000 [р.]
Таблица 3.2
Более эффективный метод наименьшей стоимости предполагает
сначала заполнение клетки, соответствующей минимальной стоимости
перевозки груза, затем заполняется клетка с тем же свойством среди
оставшихся незаполненных и т.д.
В рассматриваемом примере наименьшая стоимость перевозки груза в
табл. 3.1 соответствует клетке (3,2): c
32
=1. В неё записывается наименьшее из
чисел a
3
и b
2
, т.е. 10 (ПН B
2
подал заявку на 10 тыс. м
3
, что полностью
удовлетворяется из запасов ПО A
3
, причем там остается ещё 40 тыс. м
3
). Среди
оставшихся клеток наименьшая стоимость перевозок соответствует клетке (1,2):
c
12
=2, но поскольку заявка ПН B
2
уже удовлетворена, она пропускается.
Следующей будет клетка (3,3), в которую можно записать число 40 (количество
груза, оставшееся в ПО A
3
). Далее берется клетка (2,1) и в неё вносится число
30 и т.д. В результате получается табл. 3.3.
ПО\ПН
B
1
B
2
B
3
B
4
Запасы a
i
5
2
6
11
A
1
30 5 35
4
7
12
8
A
2
5 40 45
9
1
3
10
A
3
25 25 50
Заявки b
j
30 10 65 25 130
33
Таблица 3.3
Этот план также является допустимым и опорным. Общие затраты на
перевозку по этой методике будут равны:
Z =30 ⋅ 4+10 ⋅ 1+40 ⋅ 3+25 ⋅ 6+10 ⋅ 11+15 ⋅ 8=630 [р.]
На каждом шаге метода Фогеля для каждой строки (столбца)
вычисляются штрафы как разность между двумя наименьшими стоимостями
строки (столбца). После этого выбирается максимальный штраф из всех
штрафов столбцов и строк. Далее в строке или столбце с максимальным
штрафом заполняется клетка с минимальной стоимостью (табл. 3.4).
ПО\ПН
B
1
B
2
B
3
B
4
Запасы a
i
5
2
6
11
A
1
25 10 35
4
7
12
8
A
2
30
15 45
9
1
3
10
A
3
10 40
50
Заявки b
j
30 10 65 25 130
34
Таблица 3.4
Если существует несколько одинаковых по величине штрафов, то
выбирается и заполняется в соответствующих строках или столбцах клетка с
наименьшей стоимостью. Если клеток с наименьшей стоимостью несколько, то
из них выбирается клетка с максимальным суммарным штрафом (максимальная
сумма штрафов по строке и столбцу, образующих клетку).
Для рассматриваемого примера на первой итерации для первой строки
считается разница между двумя наименьшими стоимостями: 5–2=3. Аналогично
высчитываются штрафы для второй и третей строки, а также для всех столбцов.
Далее, так как имеется несколько одинаковых по величине штрафов,
согласно правилу выбирается строка или столбец с наименьшей стоимостью –
это первая строка (наименьшая стоимость 2). В клетку (1,2) записывается число
10. Поскольку заявка В
2
полностью удовлетворена, в этом столбце штрафов
далее ставятся прочерки.
На второй итерации снова рассчитываются штрафы по столбцам и
строкам, исключая вычеркнутые клетки столбца В
2
. Для строки A
1
это будет
значение: 6–5=1. Теперь максимальный штраф соответствует строке A
3
, а
значит заполнится клетка (3,3) значением 50. Так как все запасы ПО A
3
исчерпаны, все оставшиеся клетки строки вычеркиваются и т.д. В результате
получится табл. 3.4.
Общие затраты на перевозку по этой методике будут равны
Z =10 ⋅ 5+10 ⋅ 2+15 ⋅ 6+20 ⋅ 4+25 ⋅ 8+50 ⋅ 3=590 [р.]
ПО\ПН
B
1
B
2
B
3
B
4
Запасы a
i
№1 №2 №3 №4
5
2
6
11
A
1
10 10 15 – 35
3 1 1 6
4
7
12
8
A
2
20 – – 25 45
3 4 4 4
9
1
3
10
A
3
– – 50 – 50
2 6 – –
Заявки b
j
30 10 65 25 130
№1
1 1 3 2
№2
1 – 3 2
№3
1 – 6 3
№4
1 – – 3
35
Метод Фогеля дает решение очень близкое к оптимальному, а иногда и
само оптимальное решение.
Задание 2. Составить транспортную таблицу задачи. Найти опорное
решение методами северо-западного угла, наименьшего элемента и Фогеля.
Проверить, для каждого метода, является ли полученное решение допустимым
и опорным. Подсчитать общую стоимость плана перевозок для каждого
варианта решения.
Решение ТЗ методом потенциалов
После того как был составлен опорный план перевозок, необходимо
выяснить, является ли этот план оптимальным. Для этого используется метод
потенциалов. Этот метод предполагает выполнение следующих этапов.
1. Каждому A
i
поставщику ставится в соответствие некоторая переменная
u
i
, называемая потенциалом данного ПО. Каждому потребителю B
j
ставится в
соответствие некоторая переменная v
j
, называемая потенциалом данного ПН.
2. Для отыскания значений этих переменных, т.е. потенциалов
поставщиков и потребителей, составляется и решается система уравнений. При
этом каждой занятой клетке (i, j) соответствует своё уравнение, имеющее вид
ijji
cvu
=
+
. (3.7)
Всего составляется m+n–1 уравнений по числу занятых клеток. Число
переменных в системе равно m+n, т.е. на единицу больше числа уравнений.
Поэтому система легко решается: одной из переменных придают произвольное
значение (обычно нуль) и затем однозначно определяют значения остальных
переменных.
3. Для каждой свободной клетки вычисляется сумма потенциалов
соответствующего ей поставщика и потребителя
skks
vuz
+
=
. (3.8)
Эту сумму называют псевдостоимостью. Далее, для этой же клетки
вычисляется разность между стоимостью перевозки и псевдостоимостью, так
называемая теневая стоимость
ksksks
cz
−
=
∆
. (3.9)
Примечание. Разность
ksksks
zc
−
=
∆
называется симплексной разностью
и также может быть использована при объяснении метода потенциалов.
Если для всех свободных клеток полученные теневые стоимости
отрицательны, значит исходный опорный план уже оптимален. Иными словами,
36
опорный план оптимален, если для каждой свободной клетки псевдостоимость
не превышает стоимость перевозки. Нулевые значения теневых стоимостей для
свободных клеток свидетельствуют о наличии альтернативного оптимального
плана.
4. Наличие хотя бы одной свободной клетки с отрицательной теневой
стоимостью свидетельствует о том, что оптимальное решение ещё не
достигнуто. В этом случае ищется клетка с наибольшей положительной
величиной ∆
ks
, определяется для неё цикл, и совершается перенос груза.
За начало цикла принимается вершина цикла с наибольшей разностью ∆
ks
,
и ей приписывается знак плюс. Остальные вершины цикла находятся в
заполненных клетках, их знаки чередуются по часовой стрелке.
Выбирается наименьшее из количеств грузов, стоящих в отрицательных
вершинах, которое переносится по циклу. Эта величина соответственно
отнимается в отрицательных и прибавляется в положительных вершинах цикла.
5. В результате перераспределения груза получается новый план,
заведомо лучший, чем предыдущий.
Затем процедуру повторяют с первого этапа до тех пор, пока не будет
найдено оптимальное решение за конечное число итераций.
Для примера решения задачи методом потенциалов берется опорный
план, полученный методом СЗУ (табл. 3.2).
В соответствии с количеством и порядковым номером поставщиков и
потребителей вводятся переменные u
1
, u
2
, u
3
, v
1
, v
2
, v
3
, v
4
– потенциалы
поставщиков и потребителей. Для каждой занятой клетки табл. 3.2
записываются уравнения вида (3.7)
u
1
+v
1
=5, u
1
+v
2
=2, u
2
+v
2
=7, u
2
+v
3
=12, u
3
+v
3
=3, u
3
+v
4
=10.
Примем v
1
=0, после чего находятся из записанной системы уравнений
значения других потенциалов. Они указаны в табл. 3.5 в левых нижних углах
клеток запасов ПО и заявок ПН.
37
Таблица 3.5
В левых нижних углах клеток перевозок указаны, рассчитанные в
соответствии с (3.8), псевдостоимости. Соответственно, теневые стоимости
будут равны
∆
13
=7–6=1, ∆
14
=14–11=3, ∆
21
=10–6=6, ∆
24
=19–8=11, ∆
31
= 1–9= –8, ∆
32
=–2–1= –3.
Как видно не все полученные значения отрицательные, следовательно,
опорный план в табл. 3.6 не оптимален. В клетке (2,4) получается наибольшая
положительная теневая стоимость ∆
24
=11, значит она выбирается в качестве
начала цикла. Имеется единственно возможный цикл: (2,4)→(3,4)→(3,3)→(2,3).
Положительными будут вершины (2,4) и (3,3), отрицательными – (3,4) и (2,3).
Наименьшее количество в отрицательной вершине цикла (клетка (3,4)) равно 25
единиц груза. Это число вычитается в отрицательных вершинах и прибавляется
в положительных, в итоге получается новый план перевозок (табл. 3.6).
Общая стоимость перевозок равна
Z =30 ⋅ 5+5 ⋅ 2+5 ⋅ 7+15 ⋅ 12+25 ⋅ 8+50 ⋅ 3= 725 (р.)
Таким образом, стоимость перевозок уменьшилась на 1000 – 725 = 275
единиц. Это можно было предсказать и не подсчитывая полную стоимость
плана. Действительно, так называемая цена цикла представленная
алгебраической суммой стоимостей, стоящих в вершинах цикла (со знаком
плюс, если перевозки в этой вершине увеличиваются, и со знаком минус – если
уменьшаются), в данном случае равна: – 10 + 3 – 12 + 8 = –11. Значит, при
переносе одной единицы груза по этому циклу стоимость перевозок
уменьшается на 11. В табл. 3.6 перенесено 25 единиц груза, значит, стоимость
перевозок должна уменьшиться на 11⋅25 = 275 единиц, что и произошло.
ПО\ПН
B
1
B
2
B
3
B
4
Запасы a
i
0
-
3
2
9
5
2
6
11
A
1
30 5
35
5
5
2
7
14
4
7
12
8
A
2
5 40 45
10
10
7
12
19
9
1
3
10
A
3
25 25 50
1
1
–
2
3
10
Заявки b
j
30 10 65 25 130
38
Таблица 3.6
На второй итерации метода потенциалов опять для каждой занятой клетки
нового опорного плана записываются уравнения вида 3.7 и определяются новые
значения потенциалов (табл. 3.6).
u
1
+v
1
=5, u
1
+v
2
=2, u
2
+v
2
=7, u
2
+v
3
=12, u
3
+v
3
=3, u
2
+v
4
=8.
Находятся значения теневых стоимостей для незанятых клеток:
∆
13
=1; ∆
14
= –8; ∆
21
=6; ∆
31
= –8; ∆
32
= –3; ∆
34
= –11.
Так как имеются положительные значения симплексных разностей,
олученный план не является оптимальным. Наибольшее значение соответствует
клетке (2,1) и равно ∆
21
=10–4=6. Снова составляется единственно возможный
цикл: (2,1)→(1,1)→(1,2)→(2,2). Определяются знаки вершин цикла:
положительные – (2,1) и (1,2), отрицательные – (1,1) и (2,2). Количество
переносимого по циклу груза равно 5 и находится в клетке (2,2). В результате
получается новый план перевозок, представленный в табл. 3.7.
Суммарные затраты на перевозки будут равны
Z =25 ⋅ 5+10 ⋅ 2+5 ⋅ 4+15 ⋅ 12+25 ⋅ 8+50 ⋅ 3= 695 (р.)
На третьей итерации на основе опорного плана табл. 3.7 получается новая
система уравнений:
u
1
+v
1
=5, u
1
+v
2
=2, u
2
+v
1
=4, u
2
+v
3
=12, u
3
+v
3
=3, u
2
+v
4
=8.
Находятся значения теневых стоимостей для незанятых клеток
∆
13
=7, ∆
14
= –2, ∆
22
= –6, ∆
31
= –14, ∆
32
= –7, ∆
34
= –11.
ПО\ПН
B
1
B
2
B
3
B
4
Запасы a
i
5
2
7
3
5
2
6
11
A
1
30 5 35
0
5
2
7
3
4
7
12
8
A
2
5 15 25 45
5
10
7
12
8
9
1
3
10
A
3
50 50
-
4
1
-
2
3
-
1
Заявки b
j
30 10 65 25 130
39
Таблица 3.7
Наибольшее значение теневой стоимости соответствует клетке (1,3) и
равно ∆
24
=19–8=7. Составляется цикл: (1,3)→(2,3)→(2,1)→(1,1). Вершины со
знаком плюс – (2,1) и (1,2), со знаком минус – (1,1) и (2,2). Количество
переносимого по циклу груза равно 15 и находится в клетке (2,3). В результате
получается новый план перевозок представленный в табл. 3.8.
Таблица 3.8
Суммарные затраты на перевозки будут равны
Z =10 ⋅ 5+10 ⋅ 2+15 ⋅ 6+20 ⋅ 4+25 ⋅ 8+50 ⋅ 3= 590 (р.)
На четвертой итерации опять для каждой занятой клетки полученного
нового опорного плана рассчитываются значения потенциалов (табл. 3.8).
u
1
+v
1
=5, u
1
+v
2
=2, u
1
+v
3
=6, u
2
+v
1
=4, u
2
+v
4
=8, u
3
+v
3
=3.
ПО\ПН
B
1
B
2
B
3
B
4
Запасы a
i
5
2
13
9
5
2
6
11
A
1
25 10 35
0
5
2
13
9
4
7
12
8
A
2
5 15 25 45
-
1
4
1
12
8
9
1
3
10
A
3
50 50
-
10
-
5
-
8
3
-
1
Заявки b
j
30 10 65 25 130
ПО\ПН
B
1
B
2
B
3
B
4
Запасы a
i
5
2
6
9
5
2
6
11
A
1
10 10 15 35
0
5
2
6
9
4
7
12
8
A
2
20 25 45
-
1
4
1
5
8
9
1
3
10
A
3
50 50
-
3
2
-
1
3
6
Заявки b
j
30 10 65 25 130
40
Находятся значения теневых стоимостей для незанятых клеток:
∆
14
= –2, ∆
22
= –6, ∆
23
= –7, ∆
31
= –7, ∆
32
= –2, ∆
34
= –4.
Все симплексные разности получились отрицательными, значит данный
план перевозок является оптимальным.
Выше отмечалось, что транспортная таблица, содержащая опорное
решение ТЗ, должна содержать ровно m+n–1 занятых клеток. Случай, когда
число занятых клеток меньше указанного, называется вырожденным. Этот
случай соответствует слиянию (говорят еще, склеиванию) двух опорных точек в
одну. Для отыскания оптимального решения при вырожденном опорном плане
необходимо ввести нулевую перевозку (говорят, расклеить опорные точки),
чтобы использовать в качестве заполненной одну из пустых клеток. Такая
клетка определяется при расчете потенциалов: это – та свободная клетка,
значений потенциалов которой не хватает для решения системы уравнений вида
(3.7). В дальнейшем с этой клеткой оперируют как с занятой.
Задание 3. Для ТЗ, полученной от преподавателя, найти оптимальный
план перевозок методом потенциалов, использовав опорный план, полученный
методом СЗУ.
Открытая модель транспортной задачи
На практике достаточно редко суммарный запас поставщиков и общее
количество груза, заявленное потребителями, совпадают. Как правило, они
различаются. Эта ТЗ называется несбалансированной или открытой.
Математическая модель такой задачи называется открытой моделью.
Если сумма запасов больше суммы заявок
∑∑
==
>
n
j
j
m
i
i
ba
11
,
то все заявки могут быть удовлетворены, но при этом не все запасы будут
израсходованы. Задача может быть сведена к сбалансированной ТЗ, если ввести
в рассмотрение некий «фиктивный» пункт назначения B
ф
, условно приписав
ему заявку, равную избытку запасов над заявками
∑∑
==
−=
n
j
j
m
i
i™
bab
11
. (3.10)
Тогда задача сводится к ТЗ с правильным балансом. Стоимости перевозок
из ПО A
i
в фиктивный ПН B
ф
принимаются равными нулю: ведь фактически в
пункт B
ф
ничего перевозиться не будет. Поэтому для любого пункта
отправления стоимость c
iф
=0.