Транспортные задачи
Пример 1.
Требуется решить
транспортную задачу, условия которой, представлены в таблице X.
|
Поставщики |
Потребители |
Запасы |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 |
2 |
6 |
3 |
1 |
11 |
X= |
А2 |
3 |
7 |
8 |
5 |
11 |
|
А3 |
9 |
2 |
4 |
5 |
8 |
|
Потребность |
5 |
9 |
9 |
7 |
30 |
(Тарифы перевозок
выделены синим)
Задача является
сбалансированной, так как запасы груза и потребности равны.
1. Построение
начального плана перевозок
Действуем по правилу северо-западного
угла и получаем:
|
ai |
bj |
|||
|
5 |
9 |
9 |
7 |
|
X= |
11 |
7 5Ю |
8 6 Я |
5
|
3 |
|
11 |
2 |
4 3Ю |
5 8 Я |
9 |
|
8 |
6 |
3 |
1 1Ю |
2 7 |
Находим критерий для начального плана
перевозок:
(Количество
распределяемого груза выделено красным)
2. Вычисляем
потенциалы и оценки следующим образом:
Вводим потенциалы:
Ui - сопоставим пунктам
отправления
Vj - сопоставим пунктам
назначения
|
ai |
bj |
||||
|
5 |
9 |
9 |
7 |
||
|
U1 |
11 |
7 5 |
8 6 |
5 |
3 |
X= |
U2 |
11 |
2 |
4 3 |
5 8 |
9 |
|
U3 |
8 |
6 |
3 |
1 1 |
2 7 |
|
|
|
V1 |
V2 |
V3 |
V4 |
Для базисных клеток выполняется
равенство Vj-Ui=Cij, эта система
содержит m+n-1 равенство. Первоначально
любой из вершин U или V присваиваем любое значение,
остальные U и V вычисляются из (1).
V1-U1=7 U1=0;V1=7; V2-U1=8 V2=8;
V2-U2=4 U2=4; V3-U2=5 V3=9;
V3-U3=1 U3=8; V4-U3=2 V4=10;
Находим оценки для небазисных клеток:
D13=V3-U1-C13=9-0-5=4 D14=V4-U1-C14=10-0-3=7
D21=V1-U2-C21=7-4-2=1 D24=V4-U2-C24=10-4-9=
-3
D31=V1-U3-C31=7-8-6=
-7 D32=V2-U3-C32=8-8-3=
-3
Строим
матрицу оценок для начального плана перевозок D1:
0 |
0 |
4 |
7 |
1 |
0 |
0 |
-3 |
-7 |
-3 |
0 |
0 |
Так как есть положительные оценки, то
план не является оптимальным.
3. Строим цикл
пересчета в матрице X на клетке kr.
Строим замкнутый цикл, вершины
которого, принадлежат базисным клеткам. Строить начинаем из клетки kr, значение которой является
максимальным в матрице D1
, это будет значение 7 в клетке 1,4 (выделена зеленым). Нумерацию вершин производим так, чтобы
выделенная клетка была четной.
(цепь выделена красным, первоначальная вершина
*)
|
ai |
bj |
|||
|
5 |
9 |
9 |
7 |
|
X= |
11 |
7 5 |
8 6 Я |
5
|
3 Ь* |
|
11 |
2 |
4 3Ю |
5 8 Я |
9 |
|
8 |
6 |
3 |
1
1Ю |
2 Э 7 |
Далее,
двигаясь по циклу, посчитаем q1=min(Xij
), XijОнечетным,
Получится
q1=min(6,8,7)=6.
4. Строим новую
матрицу X из старой.
Двигаемся по циклу и прибавляем q1
к четным вершинам и вычитаем из нечетных, получим:
|
ai |
bj |
|||
|
5 |
9 |
9 |
7 |
|
X1= |
11 |
7 5 |
8
|
5
|
3 6 |
|
11 |
2 |
4 9 |
5 2 |
9 |
|
8 |
6 |
3 |
1 7 |
2 1 |
Критерий
Lk=Lk-1-qk-1* maxDij;
L1=150-6*7=108
5. Строим новую
матрицу D путем преобразования из
предыдущей:
1)
Отмечаем элементы являющиеся базисными в новом решении, максимальный элемент
выделяем особо.
2) Строим цепочку выделения, она
строится от особо выделенного элемента по строкам затем по столбцам, каждый
элемент попавший в цепочку выделяет и строку и столбец, кроме выделенного
элемента, он только строки.
3) К выделенным столбцам прибавляем
выделенный элемент, из выделенных строк – вычитаем.
(базисные в новом X отмечены жирным курсивным шрифтом,
красным отмечены выделенные строки и столбцы)
Итерация 2
|
0 |
0 |
4 |
7 |
-7 |
|
0 |
-7 |
-3 |
0 |
D1= |
1 |
0 |
0 |
-3 |
|
D2= |
8 |
0 |
0 |
-3 |
|
-7 |
-3 |
0 |
0 |
|
|
0 |
-3 |
0 |
0 |
|
+7 |
|
|
|
|
|
|
|
|
|
Повторяем пункт 3:
|
ai |
bj |
|||
|
5 |
9 |
9 |
7 |
|
X2= |
11 |
7 5Ю |
8
|
5
|
3 6 Я |
|
11 |
2 Э * |
4 9 |
5 Ь2 |
9 |
|
8 |
6 |
3 |
1 Э 7 |
2
Ь1 |
q2=min(5,1,2)=1.
Повторяем пункт 4:
|
ai |
bj |
|||
|
5 |
9 |
9 |
7 |
|
X2= |
11 |
7 4 |
8
|
5
|
3 7 |
|
11 |
2 1 |
4 9 |
5 1 |
9 |
|
8 |
6 |
3 |
1 8 |
2
|
Критерий
L2=108-1*8=100
Далее повторяем пункты 5, 3, 4 до тех
пор, пока все значения матрицы D будут не
положительны.
Итерация 3
|
0 |
-7 |
-3 |
0 |
|
|
0 |
1 |
5 |
0 |
D2= |
8 |
0 |
0 |
-3 |
-8 |
D3= |
0 |
0 |
0 |
-11 |
|
0 |
-3 |
0 |
0 |
|
|
0 |
-3 |
0 |
-8 |
|
|
+8 |
+8 |
|
|
|
|
|
|
|
|
ai |
bj |
|||
|
5 |
9 |
9 |
7 |
|
X2= |
11 |
7 4 Я |
8
|
5 Ь* |
3 7 |
|
11 |
2
1Ю |
4 9 |
5 Э 1 |
9 |
|
8 |
6 |
3 |
1 8 |
2 |
q3=min(4,1)=1
|
ai |
bj |
|||
|
5 |
9 |
9 |
7 |
|
X2= |
11 |
7 3 |
8
|
5 1 |
3 7 |
|
11 |
2 2 |
4 9 |
5
|
9 |
|
8 |
6 |
3 |
1 8 |
2
|
Критерий L3=100-1*5=95
Итерация 4
|
0 |
1 |
5 |
0 |
-5 |
|
0 |
1 |
0 |
0 |
D3= |
0 |
0 |
0 |
-11 |
-5 |
D4= |
0 |
0 |
-5 |
-11 |
|
0 |
-3 |
0 |
-8 |
|
|
-3 |
2 |
0 |
-3 |
|
+5 |
+5 |
|
+5 |
|
|
|
|
|
|
+
|
ai |
bj |
|||
|
5 |
9 |
9 |
7 |
|
X3= |
11 |
7 3Ю |
8
|
5 1 Я |
3 7 |
|
11 |
2 Э 2 |
4
Ь9 |
5
|
9 |
|
8 |
6 |
3 Э * |
1 Ь8 |
2 |
q4=min(8,3,9)=3
|
ai |
bj |
|||
|
5 |
9 |
9 |
7 |
|
X3= |
11 |
7
|
8
|
5 4 |
3 7 |
|
11 |
2 5 |
4 6 |
5
|
9 |
|
8 |
6 |
3 3 |
1 5 |
2
|
Критерий L4=95-3*2=89
Итерация 5
|
0 |
1 |
0 |
0 |
-2 |
|
-2 |
-1 |
0 |
-2 |
D4= |
0 |
0 |
-5 |
-11 |
|
D5= |
0 |
0 |
-5 |
-11 |
|
-3 |
2 |
0 |
-3 |
-2 |
|
-5 |
0 |
0 |
-5 |
|
|
|
+2 |
+2 |
|
|
|
|
|
|
Все элементы матрицы D5 неположительны,
следовательно, на 4ой итерации получили искомое решение X4.
Пример 2.
Требуется решить
транспортную задачу, условия которой, представлены в таблице X.
|
Поставщики |
Потребители |
Запасы груза |
||
|
В1 |
В2 |
В3 |
||
|
А1 |
5 |
7 |
6 |
50 |
X= |
А2 |
6 |
6 |
5 |
40 |
|
А3 |
8 |
4 |
5 |
20 |
|
Потребность в грузе |
18 |
21 |
33 |
|
Предыдущая задача была сбалансирована
в ней
Эта же задача не сбалансирована, так
как, в ней присутствует избыток запасов.
Как решать такую задачу ?
1.
Находим разницу между запасами и заявками
.
2.
Вводим фиктивный пункт отправления, которому
припишем фиктивную заявку равную избытку запасов, а стоимости перевозок сделаем
равными нулю, получим:
|
Поставщики |
Потребители |
Запасы груза |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 |
5 |
7 |
6 |
0 |
50 |
X= |
А2 |
6 |
6 |
5 |
0 |
40 |
|
А3 |
8 |
4 |
5 |
0 |
20 |
|
Потребность в грузе |
18 |
21 |
33 |
38 |
110 |
3.
Так как мы свели задачу к сбалансированной,
далее решаем, как и предыдущую:
Итерация 1
|
ai |
bj |
|||
|
18 |
21 |
33 |
38 |
|
X= |
50 |
5 18Ю |
7 21Ю |
6 11 Я |
0 |
|
40 |
6 |
6 |
5 22Ю |
0 18 Я |
|
20 |
8 |
4 |
5 |
0 20 |
Вычисляем
потенциалы:
V1-U1=5 U1=0;V1=5 V2-U1=7 V2=7+U1=7
V3-U1=6 V3=6+U1=6 V3-U2=5 U2=V3-5=1
V4-U2=0 V4=0+1=1 V4-U3=0 U3=V4-0=1
Находим оценки для небазисных вершин:
D14=V4-U1-C14=1-0-0=1 D21=V1-U2-C21=5-1-6=
-2
D22=V2-U2-C22=7-1-6=0 D31=V1-U3-C31=5-1-8=
-4
D32=V2-U3-C32=7-1-4=2 D33=V3-U3-C33=6-1-5=0
Матрица
D1 имеет вид:
0 |
0 |
0 |
1 |
-2 |
0 |
0 |
0 |
-4 |
2 |
0 |
0 |
Построим цикл пересчета:
|
ai |
bj |
|||
|
18
|
21 |
33 |
38 |
|
X= |
50 |
5 18 |
7 20Ю |
6 11 Я |
0 |
|
40 |
6 |
6 |
5 22Ю |
0 18 Я |
|
20 |
8 |
4 Э * |
5 |
0 Ь20 |
q1=min(21,22,20)=20.
|
ai |
bj |
|||
|
18 |
21 |
33 |
38 |
|
X1= |
50 |
5 18 |
7 1 |
6 31 |
0 |
|
40 |
6 |
6 |
5 2 |
0 38 |
|
20 |
8 |
4 20 |
5 |
|
Итерация 2
Строим новую матрицу D:
|
0 |
0 |
0 |
1 |
|
|
0 |
0 |
0 |
1 |
D1= |
-2 |
0 |
0 |
0 |
|
D2= |
-2 |
0 |
0 |
0 |
|
-4 |
2 |
0 |
0 |
-2 |
|
-6 |
0 |
-2 |
-2 |
|
ai |
bj |
|||
|
18
|
21 |
33 |
38 |
|
X1= |
50 |
5 18 |
7 1 |
6 31 Я |
0 Ь* |
|
40 |
6 |
6 |
5
2Ю |
0 Э 38 |
|
20 |
8 |
4 20 |
5 |
|
q2=min(31,38)=31
|
ai |
bj |
|||
|
18 |
21 |
33 |
38 |
|
X2= |
50 |
5 18 |
7 1 |
6
|
0 31 |
|
40 |
6 |
6 |
5 33 |
0 7 |
|
20 |
8 |
4 20 |
5 |
|
Итерация 3
|
0 |
0 |
0 |
1 |
-1 |
|
0 |
0 |
-1 |
0 |
D2= |
-2 |
0 |
0 |
0 |
|
D3= |
-1 |
1 |
0 |
0 |
|
-6 |
0 |
-2 |
-2 |
-1 |
|
-6 |
0 |
-3 |
-3 |
|
+1 |
+1 |
|
|
|
|
|
|
|
|
|
ai |
bj |
|||
|
18 |
21 |
33 |
38 |
|
X2= |
50 |
5 18 |
7 1Ю |
6
|
0 31 Я |
|
40 |
6 |
6 Э * |
5 33 |
0 Ь7 |
|
20 |
8 |
4 20 |
5 |
|
q3=min(1,7)=1
|
ai |
bj |
|||
|
18 |
21 |
33 |
38 |
|
X3= |
50 |
5 18 |
7
|
6
|
0 32 |
|
40 |
6 |
6 1 |
5 33 |
0 6 |
|
20 |
8 |
4 20 |
5 |
|
Итерация 4
|
0 |
0 |
-1 |
0 |
-1 |
|
0 |
-1 |
-2 |
0 |
D3= |
-1 |
1 |
0 |
0 |
-1 |
D4= |
-1 |
0 |
-1 |
0 |
|
-6 |
0 |
-3 |
-3 |
-1 |
|
-6 |
-1 |
-4 |
-3 |
|
+1 |
|
|
+1 |
|
|
|
|
|
|
Все элементы матрицы D4 неположительны,
следовательно, на 4ой итерации получили искомое решение X3.