Эксперт по сдаче вступительных испытаний в ВУЗах
КТ 3 Транспортная задача
Задание. На комбинатах ЖБК имеются Х
i единиц железобетонных панелей, размешенных в i-х складских помещениях. Их необходимо доставить на j-е объекты с учетом их потребностей (У
j). Стоимость перевозки единицы продукции от i-ro поставщика к j-му потребителю известна для всех возможных вариантов доставки и равна С
ij руб (рис.1). Исходные данные по вариантам указаны в табл. 13 и 14.
Составьте план перевозки (А
ij) железобетонных изделий так, чтобы общая стоимость этих перевозок была наименьшей и потребности всех потребителей были бы удовлетворены. Задачу решите двумя способами: методом северо-западного угла и методом наименьшей стоимости.
Рис. 1. Графическое изображение транспортной задачи
Таблица 1
Исходные данные по стоимости и объемам поставок
| 1-я цифра |
С31 |
С32 |
С33 |
2-я цифра |
Х1 |
С34 |
С41 |
С42 |
С43 |
3-я цифра |
С44 |
Х2 |
Х3 |
Х4 =У1+У2+У3+У4–Х1–Х2–Х3 |
| 0 |
2 |
4 |
6 |
0 |
25 |
4 |
2 |
1 |
2 |
0 |
3 |
18 |
36 |
| 1 |
1 |
5 |
1 |
1 |
15 |
1 |
5 |
2 |
2 |
1 |
2 |
16 |
42 |
| 2 |
2 |
0 |
2 |
2 |
10 |
5 |
2 |
1 |
6 |
2 |
3 |
25 |
41 |
| 3 |
5 |
7 |
5 |
3 |
30 |
1 |
5 |
3 |
0 |
3 |
3 |
24 |
35 |
| 4 |
0 |
1 |
2 |
4 |
5 |
4 |
0 |
1 |
4 |
4 |
2 |
15 |
5 |
| 5 |
1 |
2 |
7 |
5 |
35 |
5 |
1 |
2 |
5 |
5 |
0 |
17 |
16 |
| 6 |
4 |
5 |
2 |
6 |
45 |
1 |
3 |
3 |
1 |
6 |
1 |
10 |
28 |
| 7 |
1 |
8 |
4 |
7 |
50 |
2 |
1 |
0 |
1 |
7 |
5 |
19 |
24 |
| 8 |
2 |
7 |
3 |
8 |
10 |
2 |
1 |
5 |
0 |
8 |
1 |
17 |
39 |
| 9 |
4 |
2 |
1 |
9 |
25 |
0 |
1 |
3 |
4 |
9 |
4 |
14 |
38 |
Таблица 2
Исходные данные по стоимости и объемам потребления
| 1-я цифра |
С11 |
С12 |
У1 |
2-я цифра |
С13 |
С14 |
С21 |
У2 |
3-я цифра |
С22 |
С23 |
С24 |
У3 |
У4 |
| 0 |
1 |
2 |
36 |
0 |
8 |
2 |
3 |
15 |
0 |
1 |
6 |
2 |
12 |
32 |
| 1 |
3 |
2 |
24 |
1 |
3 |
1 |
2 |
31 |
1 |
4 |
1 |
2 |
34 |
21 |
| 2 |
5 |
1 |
5 |
2 |
4 |
1 |
3 |
12 |
2 |
2 |
5 |
3 |
40 |
13 |
| 3 |
2 |
7 |
14 |
3 |
2 |
0 |
7 |
35 |
3 |
3 |
0 |
2 |
22 |
24 |
| 4 |
3 |
0 |
16 |
4 |
3 |
4 |
1 |
24 |
4 |
1 |
2 |
7 |
14 |
25 |
| 5 |
8 |
5 |
24 |
5 |
1 |
2 |
1 |
22 |
5 |
8 |
3 |
2 |
29 |
23 |
| 6 |
2 |
3 |
20 |
6 |
5 |
2 |
6 |
28 |
6 |
3 |
2 |
1 |
26 |
15 |
| 7 |
1 |
1 |
10 |
7 |
3 |
0 |
4 |
11 |
7 |
4 |
1 |
2 |
30 |
28 |
| 8 |
3 |
5 |
35 |
8 |
6 |
1 |
2 |
19 |
8 |
1 |
3 |
0 |
16 |
27 |
| 9 |
0 |
2 |
41 |
9 |
9 |
1 |
3 |
15 |
9 |
7 |
3 |
6 |
34 |
17 |
Решение
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов согласно своему варианту (шифр 410):
| |
1 |
2 |
3 |
4 |
Запасы |
| 1 |
3 |
0 |
3 |
1 |
15 |
| 2 |
2 |
1 |
6 |
2 |
18 |
| 3 |
0 |
1 |
2 |
1 |
36 |
| 4 |
5 |
2 |
2 |
3 |
22 |
| Потребности |
16 |
31 |
12 |
32 |
|
Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 15 + 18 + 36 + 22 = 91
∑b = 16 + 31 + 12 + 32 = 91
Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой. Занесем исходные данные в распределительную таблицу.
Этап I. Поиск первого опорного плана.
- Используя метод северо-западного угла, построим первый опорный план транспортной задачи. План начинается заполняться с верхнего левого угла.
Искомый элемент равен c
11=3. Для этого элемента запасы равны 15, потребности 16. Поскольку минимальным является 15, то вычитаем его. x
11 = min(15,16) = 15.
| 3 |
x |
x |
x |
15 — 15 = 0 |
| 2 |
1 |
6 |
2 |
18 |
| 0 |
1 |
2 |
1 |
36 |
| 5 |
2 |
2 |
3 |
22 |
| 16 — 15 = 1 |
31 |
12 |
32 |
|
Искомый элемент равен c
21=2. Для этого элемента запасы равны 18, потребности 1. Поскольку минимальным является 1, то вычитаем его.
x
21 = min(18,1) = 1.
| 3 |
x |
x |
x |
0 |
| 2 |
1 |
6 |
2 |
18 — 1 = 17 |
| x |
1 |
2 |
1 |
36 |
| x |
2 |
2 |
3 |
22 |
| 1 — 1 = 0 |
31 |
12 |
32 |
|
Искомый элемент равен c
22=1. Для этого элемента запасы равны 17, потребности 31. Поскольку минимальным является 17, то вычитаем его.
x
22 = min (17,31) = 17.
| 3 |
x |
x |
x |
0 |
| 2 |
1 |
x |
x |
17 — 17 = 0 |
| x |
1 |
2 |
1 |
36 |
| x |
2 |
2 |
3 |
22 |
| 0 |
31 — 17 = 14 |
12 |
32 |
|
Искомый элемент равен c
32=1. Для этого элемента запасы равны 36, потребности 14. Поскольку минимальным является 14, то вычитаем его.
x
32 = min (36,14) = 14.
| 3 |
x |
x |
x |
0 |
| 2 |
1 |
x |
x |
0 |
| x |
1 |
2 |
1 |
36 — 14 = 22 |
| x |
x |
2 |
3 |
22 |
| 0 |
14 — 14 = 0 |
12 |
32 |
|
Искомый элемент равен c
33=2. Для этого элемента запасы равны 22, потребности 12. Поскольку минимальным является 12, то вычитаем его.
x
33 = min(22,12) = 12.
| 3 |
x |
x |
x |
0 |
| 2 |
1 |
x |
x |
0 |
| x |
1 |
2 |
1 |
22 — 12 = 10 |
| x |
x |
x |
3 |
22 |
| 0 |
0 |
12 — 12 = 0 |
32 |
|
Искомый элемент равен c
34=1. Для этого элемента запасы равны 10, потребности 32. Поскольку минимальным является 10, то вычитаем его.
x
34 = min(10,32) = 10.
| 3 |
x |
x |
x |
0 |
| 2 |
1 |
x |
x |
0 |
| x |
1 |
2 |
1 |
10 — 10 = 0 |
| x |
x |
x |
3 |
22 |
| 0 |
0 |
0 |
32 — 10 = 22 |
|
Искомый элемент равен c
44=3. Для этого элемента запасы равны 22, потребности 22. Поскольку минимальным является 22, то вычитаем его.
x
44 = min(22,22) = 22.
| 3 |
x |
x |
x |
0 |
| 2 |
1 |
x |
x |
0 |
| x |
1 |
2 |
1 |
0 |
| x |
x |
x |
3 |
22 — 22 = 0 |
| 0 |
0 |
0 |
22 — 22 = 0 |
|
| |
B1 |
B2 |
B3 |
B4 |
Запасы |
| A1 |
3[15] |
0 |
3 |
1 |
15 |
| A2 |
2[1] |
1[17] |
6 |
2 |
18 |
| A3 |
0 |
1[14] |
2[12] |
1[10] |
36 |
| A4 |
5 |
2 |
2 |
3[22] |
22 |
| Потребности |
16 |
31 |
12 |
32 |
|
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность потребителей удовлетворена, а план соответствует системе ограничений транспортной задачи.
- Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n — 1 = 7. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 3*15 + 2*1 + 1*17 + 1*14 + 2*12 + 1*10 + 3*22 = 178
Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем
предварительные потенциалы u
i, v
j. по занятым клеткам таблицы, в которых u
i + v
j = c
ij, полагая, что
u
1 = 0.
u
1 + v
1 = 3; 0 + v
1 = 3; v
1 = 3
u
2 + v
1 = 2; 3 + u
2 = 2; u
2 = -1
u
2 + v
2 = 1; -1 + v
2 = 1; v
2 = 2
u
3 + v
2 = 1; 2 + u
3 = 1; u
3 = -1
u
3 + v
3 = 2; -1 + v
3 = 2; v
3 = 3
u
3 + v
4 = 1; -1 + v
4 = 1; v
4 = 2
u
4 + v
4 = 3; 2 + u
4 = 3; u
4 = 1
| |
v1=3 |
v2=2 |
v3=3 |
v4=2 |
| u1=0 |
3[15] |
0 |
3 |
1 |
| u2=-1 |
2[1] |
1[17] |
6 |
2 |
| u3=-1 |
0 |
1[14] |
2[12] |
1[10] |
| u4=1 |
5 |
2 |
2 |
3[22] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u
i + v
j > c
ij
(1;2): 0 + 2 > 0; ∆
12 = 0 + 2 — 0 = 2 > 0
(1;4): 0 + 2 > 1; ∆
14 = 0 + 2 — 1 = 1 > 0
(3;1): -1 + 3 > 0; ∆
31 = -1 + 3 — 0 = 2 > 0
(4;2): 1 + 2 > 2; ∆
42 = 1 + 2 — 2 = 1 > 0
(4;3): 1 + 3 > 2; ∆
43 = 1 + 3 — 2 = 2 > 0
Max (2,1,2,1,2) = 2
Выбираем максимальную оценку свободной клетки (1;2): 0
Для этого в перспективную клетку (1;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
| |
1 |
2 |
3 |
4 |
Запасы |
| 1 |
3[15][-] |
0[+] |
3 |
1 |
15 |
| 2 |
2[1][+] |
1[17][-] |
6 |
2 |
18 |
| 3 |
0 |
1[14] |
2[12] |
1[10] |
36 |
| 4 |
5 |
2 |
2 |
3[22] |
22 |
| Потребности |
16 |
31 |
12 |
32 |
|
Цикл приведен в таблице (1,2 → 1,1 → 2,1 → 2,2).
Из грузов х
ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 1) = 15. Прибавляем 15 к объемам грузов, стоящих в плюсовых клетках и вычитаем 15 из Х
ij, стоящих в минусовых клетках. В результате получим новый опорный план.
| |
B1 |
B2 |
B3 |
B4 |
Запасы |
| A1 |
3 |
0[15] |
3 |
1 |
15 |
| A2 |
2[16] |
1[2] |
6 |
2 |
18 |
| A3 |
0 |
1[14] |
2[12] |
1[10] |
36 |
| A4 |
5 |
2 |
2 |
3[22] |
22 |
| Потребности |
16 |
31 |
12 |
32 |
|
Проверим оптимальность опорного плана. Найдем
предварительные потенциалы u
i, v
j. по занятым клеткам таблицы, в которых u
i + v
j = c
ij, полагая, что
u
1 = 0.
u
1 + v
2 = 0; 0 + v
2 = 0; v
2 = 0
u
2 + v
2 = 1; 0 + u
2 = 1; u
2 = 1
u
2 + v
1 = 2; 1 + v
1 = 2; v
1 = 1
u
3 + v
2 = 1; 0 + u
3 = 1; u
3 = 1
u
3 + v
3 = 2; 1 + v
3 = 2; v
3 = 1
u
3 + v
4 = 1; 1 + v
4 = 1; v
4 = 0
u
4 + v
4 = 3; 0 + u
4 = 3; u
4 = 3
| |
v1=1 |
v2=0 |
v3=1 |
v4=0 |
| u1=0 |
3 |
0[15] |
3 |
1 |
| u2=1 |
2[16] |
1[2] |
6 |
2 |
| u3=1 |
0 |
1[14] |
2[12] |
1[10] |
| u4=3 |
5 |
2 |
2 |
3[22] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u
i + v
j > c
ij
(3;1): 1 + 1 > 0; ∆
31 = 1 + 1 — 0 = 2 > 0
(4;2): 3 + 0 > 2; ∆
42 = 3 + 0 — 2 = 1 > 0
(4;3): 3 + 1 > 2; ∆
43 = 3 + 1 — 2 = 2 > 0
max(2,1,2) = 2
Выбираем максимальную оценку свободной клетки (3;1): 0
Для этого в перспективную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
| |
1 |
2 |
3 |
4 |
Запасы |
| 1 |
3 |
0[15] |
3 |
1 |
15 |
| 2 |
2[16][-] |
1[2][+] |
6 |
2 |
18 |
| 3 |
0[+] |
1[14][-] |
2[12] |
1[10] |
36 |
| 4 |
5 |
2 |
2 |
3[22] |
22 |
| Потребности |
16 |
31 |
12 |
32 |
|
Цикл приведен в таблице (3,1 → 3,2 → 2,2 → 2,1).
Из грузов х
ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 2) = 14. Прибавляем 14 к объемам грузов, стоящих в плюсовых клетках и вычитаем 14 из Х
ij, стоящих в минусовых клетках. В результате получим новый опорный план.
| |
B1 |
B2 |
B3 |
B4 |
Запасы |
| A1 |
3 |
0[15] |
3 |
1 |
15 |
| A2 |
2[2] |
1[16] |
6 |
2 |
18 |
| A3 |
0[14] |
1 |
2[12] |
1[10] |
36 |
| A4 |
5 |
2 |
2 |
3[22] |
22 |
| Потребности |
16 |
31 |
12 |
32 |
|
Проверим оптимальность опорного плана. Найдем
предварительные потенциалы u
i, v
j. по занятым клеткам таблицы, в которых u
i + v
j = c
ij, полагая, что
u
1 = 0.
u
1 + v
2 = 0; 0 + v
2 = 0; v
2 = 0
u
2 + v
2 = 1; 0 + u
2 = 1; u
2 = 1
u
2 + v
1 = 2; 1 + v
1 = 2; v
1 = 1
u
3 + v
1 = 0; 1 + u
3 = 0; u
3 = -1
u
3 + v
3 = 2; -1 + v
3 = 2; v
3 = 3
u
3 + v
4 = 1; -1 + v
4 = 1; v
4 = 2
u
4 + v
4 = 3; 2 + u
4 = 3; u
4 = 1
| |
v1=1 |
v2=0 |
v3=3 |
v4=2 |
| u1=0 |
3 |
0[15] |
3 |
1 |
| u2=1 |
2[2] |
1[16] |
6 |
2 |
| u3=-1 |
0[14] |
1 |
2[12] |
1[10] |
| u4=1 |
5 |
2 |
2 |
3[22] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u
i + v
j > c
ij
(1;4): 0 + 2 > 1; ∆
14 = 0 + 2 — 1 = 1 > 0
(2;4): 1 + 2 > 2; ∆
24 = 1 + 2 — 2 = 1 > 0
(4;3): 1 + 3 > 2; ∆
43 = 1 + 3 — 2 = 2 > 0
max(1,1,2) = 2
Выбираем максимальную оценку свободной клетки (4;3): 2
Для этого в перспективную клетку (4;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
| |
1 |
2 |
3 |
4 |
Запасы |
| 1 |
3 |
0[15] |
3 |
1 |
15 |
| 2 |
2[2] |
1[16] |
6 |
2 |
18 |
| 3 |
0[14] |
1 |
2[12][-] |
1[10][+] |
36 |
| 4 |
5 |
2 |
2[+] |
3[22][-] |
22 |
| Потребности |
16 |
31 |
12 |
32 |
|
Цикл приведен в таблице (4,3 → 4,4 → 3,4 → 3,3).
Из грузов х
ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 3) = 12. Прибавляем 12 к объемам грузов, стоящих в плюсовых клетках и
вычитаем 12 из Х
ij, стоящих в минусовых клетках. В результате получим новый опорный план.
| |
B1 |
B2 |
B3 |
B4 |
Запасы |
| A1 |
3 |
0[15] |
3 |
1 |
15 |
| A2 |
2[2] |
1[16] |
6 |
2 |
18 |
| A3 |
0[14] |
1 |
2 |
1[22] |
36 |
| A4 |
5 |
2 |
2[12] |
3[10] |
22 |
| Потребности |
16 |
31 |
12 |
32 |
|
Проверим оптимальность опорного плана. Найдем
предварительные потенциалы u
i, v
j. по занятым клеткам таблицы, в которых u
i + v
j = c
ij, полагая, что
u
1 = 0.
u
1 + v
2 = 0; 0 + v
2 = 0; v
2 = 0
u
2 + v
2 = 1; 0 + u
2 = 1; u
2 = 1
u
2 + v
1 = 2; 1 + v
1 = 2; v
1 = 1
u
3 + v
1 = 0; 1 + u
3 = 0; u
3 = -1
u
3 + v
4 = 1; -1 + v
4 = 1; v
4 = 2
u
4 + v
4 = 3; 2 + u
4 = 3; u
4 = 1
u
4 + v
3 = 2; 1 + v
3 = 2; v
3 = 1
| |
v1=1 |
v2=0 |
v3=1 |
v4=2 |
| u1=0 |
3 |
0[15] |
3 |
1 |
| u2=1 |
2[2] |
1[16] |
6 |
2 |
| u3=-1 |
0[14] |
1 |
2 |
1[22] |
| u4=1 |
5 |
2 |
2[12] |
3[10] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u
i + v
j > c
ij
(1;4): 0 + 2 > 1; ∆
14 = 0 + 2 — 1 = 1 > 0
(2;4): 1 + 2 > 2; ∆
24 = 1 + 2 — 2 = 1 > 0
max(1,1) = 1
Выбираем максимальную оценку свободной клетки (1;4): 1
Для этого в перспективную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
| |
1 |
2 |
3 |
4 |
Запасы |
| 1 |
3 |
0[15][-] |
3 |
1[+] |
15 |
| 2 |
2[2][-] |
1[16][+] |
6 |
2 |
18 |
| 3 |
0[14][+] |
1 |
2 |
1[22][-] |
36 |
| 4 |
5 |
2 |
2[12] |
3[10] |
22 |
| Потребности |
16 |
31 |
12 |
32 |
|
Цикл приведен в таблице (1,4 → 1,2 → 2,2 → 2,1 → 3,1 → 3,4).
Из грузов х
ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 1) = 2. Прибавляем 2 к объемам грузов, стоящих в плюсовых клетках и вычитаем 2 из Х
ij, стоящих в минусовых клетках. В результате получим новый опорный план.
| |
B1 |
B2 |
B3 |
B4 |
Запасы |
| A1 |
3 |
0[13] |
3 |
1[2] |
15 |
| A2 |
2 |
1[18] |
6 |
2 |
18 |
| A3 |
0[16] |
1 |
2 |
1[20] |
36 |
| A4 |
5 |
2 |
2[12] |
3[10] |
22 |
| Потребности |
16 |
31 |
12 |
32 |
|
Проверим оптимальность опорного плана. Найдем
предварительные потенциалы u
i, v
j. по занятым клеткам таблицы, в которых u
i + v
j = c
ij, полагая, что
u
1 = 0.
u
1 + v
2 = 0; 0 + v
2 = 0; v
2 = 0
u
2 + v
2 = 1; 0 + u
2 = 1; u
2 = 1
u
1 + v
4 = 1; 0 + v
4 = 1; v
4 = 1
u
3 + v
4 = 1; 1 + u
3 = 1; u
3 = 0
u
3 + v
1 = 0; 0 + v
1 = 0; v
1 = 0
u
4 + v
4 = 3; 1 + u
4 = 3; u
4 = 2
u
4 + v
3 = 2; 2 + v
3 = 2; v
3 = 0
| |
v1=0 |
v2=0 |
v3=0 |
v4=1 |
| u1=0 |
3 |
0[13] |
3 |
1[2] |
| u2=1 |
2 |
1[18] |
6 |
2 |
| u3=0 |
0[16] |
1 |
2 |
1[20] |
| u4=2 |
5 |
2 |
2[12] |
3[10] |
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u
i + v
j ≤ c
ij.
Минимальные затраты составят: F(x) = 0*13 + 1*2 + 1*18 + 0*16 + 1*20 + 2*12 + 3*10 = 94
Анализ оптимального плана.
Из 1-го склада необходимо груз направить к 2-у потребителю (13 ед.), к 4-у потребителю (2 ед.)
Из 2-го склада необходимо весь груз направить к 2-у потребителю.
Из 3-го склада необходимо груз направить к 1-у потребителю (16 ед.), к 4-у потребителю (20 ед.)
Из 4-го склада необходимо груз направить к 3-у потребителю (12 ед.), к 4-у потребителю (10 ед.)
Ссылка на первоисточник:
www.adobe.com/ru/