- •Методические указания
- •Часть 2 Модуль 2
- •Общие сведения
- •Венгерский метод в задаче о назначениях и в задаче о кратчайшем пути.
- •Алгоритм решения задачи венгерским методом
- •Решить транспортную задачу с ограничением пропускной способности
- •Алгоритм решения задачи закрытого типа
- •Транспортная задача по критерию времени
Решить транспортную задачу с ограничением пропускной способности
Для такого типа транспортных задач, когда например клиенты принимают некоторые виды грузов в строго ограниченном количестве, решается задача с ограничением пропускной способности. Данные задачи могут решаться несколькими методами, в том числе методом потенциалов. В левом верхнем углу ячейки задаётся ограничение пропускной способности, если пропускная способность не указана, то её величина принимается равной . Всё остальное аналогично транспортной задаче.
Алгоритм решения задачи закрытого типа
1-й шаг – построение первого опорного плана любым известным методом построения с учётом пропускной способности клеток;
2-й шаг – построение системы потенциалов. В отличие от стандартной задачи базисных клеток больше чем n+m-1. Те клетки, в которых величина перевозок равна пропускной способности, являются небазисными. Их необходимо проверять. Число базисных клеток должно составлять m+n-1. Если число меньше, то в качестве базисной можно принять любую свободную клетку.
Условием оптимальности для задачи с ограничением пропускной способности является отсутствие потенциальных клеток. Проверка для всех небазисных клеток осуществляется по трём условиям:
Для клеток с нулевой перевозкой:
(1.1)
Для всех базисных клеток:
(1.2)
Для клеток, в которых величина перевозки соответствует величине пропускной способности:
(1.3)
Последнее условие можно переписать так:
(1.4)
Где - стоимость перевозки в соответствующей клетке; - потенциал соответствующего столбца; - потенциал соответствующей строки; - величина перевозки в соответствующей клетке; - пропускная способность клетки; - величина возможной экономии на каждую единицу увеличения пропускной способности клетки.
В свободных клетках величина нарушения – положительное число.
В клетках с пропускной способностью – отрицательное.
3-й шаг – Выявление абсолютного по модулю нарушения, которое и будет началом цикла пересчёта. Цикл пересчёта – замкнутый контур ходом ладьи.
В том случае, когда в выбранной клетке с нарушением перевозка равна пропускной способности, порядковую нумерацию замкнутого контура начинают с 0, а не с 1. Тогда в чётных клетках величину перевозки уменьшают, а в нечётных – увеличивают.
В задачах с ограничениями пропускной способности величина, на которую изменяют план в клетках замкнутого контура хул, определяется не только минимальной перевозкой в чётных клетках, но и минимальной величиной, на которую можно увеличить перевозку в нечётных клетках по условиям пропускной способности:
(1.5)
Алгоритм повторяется до тех пор, пока не будут выполнены все 3 условия оптимальности.
Пример: Решить транспортную задачу, минимизируя стоимость перевозки грузов.
Таблица 1.1
пост. Ai |
11 |
40 |
27 |
33 |
30 |
24 |
потр.Вj |
||||||
30 |
15 |
18 |
8 3 |
8 8 |
24 |
18 |
35 |
23 |
8 2 |
12 |
6 4 |
35 |
7 10 |
28 |
17 |
11 |
5 6 |
21 |
9 4 |
12 |
40 |
6 12 |
4 5 |
22 |
24 |
35 |
20 |
32 |
29 |
24 |
16 |
20 |
8 9 |
24 |
Решение Строим начальный план любым из известных методов (например, методом наименьшей стоимости), учитывая пропускную способность клеток (Таблица 1.2). Находим клетку 2.2 со стоимостью 2 и помещаем в неё перевозку, равную пропускной способности. Затем находим клетку 1.3 и проделываем ту же операцию и так до тех пор, пока не будет распределена вся перевозка.
Таблица 1.2
пост. Ai |
11,5, К |
40,32, 28,14, 5 |
27,19, 14,К |
33,27, 19,9, К |
30,21, 13,К |
24,17, К |
потр.Вj |
||||||
30,22, 14,9,К |
5 15 |
9 18 |
8 8 3 |
8 8 8 |
24 |
18 |
35,27, 21,14,1 |
23 |
8 8 2 |
12 |
6 6 4 |
13 35 |
7 7 10 |
28,19, 14,К |
17 |
14 11 |
5 5 6 |
21 |
9 9 4 |
12 |
40,36, 30,13, 4 |
6 6 12 |
4 4 5 |
22 |
9 24 |
35 |
17 20 |
32,24, 10,К |
29 |
24 |
14 16 |
10 20 |
8 8 9 |
24 |
Если всю перевозку распределить не удастся, то производим коррекцию величины перевозки в клетках до полного распределения перевозки. (Таблица 1.3).
Таблица 1.3
пост. Ai |
11,5, К |
40,32, 28,14, 5, 4, К |
27,19, 14,К |
33,27, 19,9,К, -4,К |
30,21, 13,К, -1,К |
24,17, К |
Ui |
потр.Вj |
|||||||
30,22, 14,9,К |
* 5 15 |
* 9 18 |
8 8 3 |
8 8 8 |
24 |
18 |
-6 |
35,27, 21,14,1,К |
23 |
8 8 2 |
+ 12 |
6 6 4 |
* 14 35 |
7 7 10 |
18 |
28,19, 14,К,1,К |
17 |
* 1 5 11 |
5 5 6 |
21 |
9 * 8 4 |
12 |
-13 |
40,36, 30,13,4,К |
6 6 12 |
4 4 5 |
22 |
* 13 24 |
35 |
* 17 20 |
4 |
32,24, 10,К,4,К |
29 |
* 4 24 |
* 14 16 |
* 6 20 |
8 8 9 |
24 |
0 |
Vj |
21 |
24 |
16 |
20 |
17 |
16 |
|
После перераспределения величин перевозки считаем общую стоимость проекта:
C=15*5+18*9+3*8+8*8+2*8+4*6+14*35+10*7+11*15+5*6+4*8+ 12*6+5*4+24*13+20*17+24*4+14*16+20*6+9*8=75+162+24+64+16+24+490+70+165+30+32+72+20+312+340+96+224+120+72=2408
Отмечаем базисные клетки, в которых перевозка меньше пропускной способности. Количество их должно составлять 6+5-1=10. Если количество загруженных клеток с величиной перевозки меньше пропускной способности меньше m+n-1, то в качестве базисной можно выбрать любую свободную клетку или клетку, в которой перевозка равна пропускной способности.
Далее строим систему потенциалов и проверяем условие оптимальности плана. Присвоим строке 5 потенциал 0 и, исходя из условия 1.2, определим потенциалы оставшихся клеток.(Таблица 1.3)
Проверяем выполнение условий оптимальности во всех не базисных клетках. Для этого воспользуемся формулами 1.1. – 1.3., результаты заносим в таблицу 1.3. Выделяем те клетки, в которых наблюдается не соответствие с неравенствами 1.1-1.3. (Таблица 1.4)
Таблица 1.4
-
0
0
-7
-6
13
8
-16
-40
-22
-34
0
-24
9
0
+3
14
0
9
-13
-23
2
0
14
0
8
0
0
0
-8
8
Среди выбранных клеток выделяем клетку 2.3. с самым большим по модулю нарушением и строим ходом ладьи замкнутый контур, используя только базисные клетки. (Таблица 1.3). В нашей задаче это клетки 2.3, 5.3, 5.2, 3.2, 3.5, 2.5. По формуле 1.5. определяем величину перевозки, которую передвигаем. min (14;1). Перемещаем 1-у единицу.
Улучшенный план представлен в таблице 1.5.
Новая стоимость перевозки составит:
C=15*5+18*9+3*8+8*8+2*8+12*1+4*6+13*35+10*7+11*14+5*6+4*9+12*6+5*4+24*13+20*17+24*5+13*16+20*6+9*8=75+162+24+64+16+12+24+455+70+154+30+36+72+20+312+340+120+208+120+72=2386
Далее проделываем аналогичные операции до полного исчезновения клеток с нарушением неравенств 1.1-1.3. В этом случае план является оптимальным.
Дальнейшее решение представлено в таблицах 1.5-1.10.
Таблица 1.5
пост. Ai |
11 |
40 |
27 |
33 |
30 |
24 |
Ui |
потр.Вj |
|||||||
30 |
* 5 15 |
* 9 18 |
8 8 3 |
8 8 8 |
24 |
18 |
-6 |
35 |
23 |
8 8 2 |
* 1 12 |
6 6 4 |
* 13 35 |
7 7 10 |
-4 |
28 |
17 |
* 14 11 |
5 5 6 |
21 |
9 9 4 |
12 |
-13 |
40 |
6 6 12 |
4 4 5 |
22 |
* 13 24 |
35 |
* 17 20 |
4 |
32 |
29 |
* 5 24 |
* 13 16 |
* 6 20 |
8 8 9 |
24 |
0 |
Vj |
21 |
24 |
16 |
20 |
39 |
16 |
|
Таблица 1.6
-
0
0
-7
-6
-9
8
6
-18
0
-12
0
-2
9
0
+3
14
-22
9
-13
-23
2
0
-8
0
8
0
0
0
-30
8
Таблица 1.7
пост. Ai |
11 |
40 |
27 |
33 |
30 |
24 |
Ui |
потр.Вj |
|||||||
30 |
* 5 15 |
18 |
8 8 3 |
8 8 8 |
* 9 24 |
18 |
-15 |
35 |
23 |
8 8 2 |
* 10 12 |
6 6 4 |
* 4 35 |
7 7 10 |
-4 |
28 |
17 |
* 14 11 |
5 5 6 |
21 |
9 9 4 |
12 |
-13 |
40 |
6 6 12 |
4 4 5 |
22 |
* 1 3 24 |
35 |
* 17 20 |
4 |
32 |
29 |
* 14 24 |
* 4 16 |
* 6 20 |
8 8 9 |
24 |
0 |
Vj |
30 |
24 |
16 |
20 |
39 |
16 |
|
Новая стоимость перевозки составит: C==2305
Таблица 1.8
-
0
9
+2
+3
0
17
-3
-18
0
-12
0
-2
0
0
+3
14
-22
9
-22
-23
2
0
-8
0
-1
0
0
0
-30
8
Таблица 1.9
пост. Ai |
11 |
40 |
27 |
33 |
30 |
24 |
Ui |
потр.Вj |
|||||||
30 |
* 5 15 |
18 |
8 8 3 |
8 8 8 |
* 9 24 |
18 |
-7 |
35 |
23 |
8 8 2 |
* 14 12 |
6 6 4 |
35 |
7 7 10 |
-4 |
28 |
17 |
* 1 4 11 |
5 5 6 |
21 |
9 9 4 |
12 |
-13 |
40 |
6 6 12 |
4 4 5 |
22 |
* 9 24 |
* 4 35 |
* 17 20 |
4 |
32 |
29 |
* 1 4 24 |
* 0 16 |
* 10 20 |
8 8 9 |
24 |
0 |
Vj |
22 |
24 |
16 |
20 |
31 |
16 |
|
Новая стоимость перевозки составит: C==2273
Таблица 1.8
-
0
1
-6
-5
0
9
5
-18
0
-12
8
-2
8
0
+3
14
-14
9
-14
-23
2
0
0
0
7
0
0
0
-22
8
Таблица 1.9
пост. Ai |
11 |
40 |
27 |
33 |
30 |
24 |
Ui |
потр.Вj |
|||||||
30 |
* 5 15 |
18 |
8 8 3 |
8 8 8 |
* 9 24 |
18 |
-7 |
35 |
23 |
8 8 2 |
* 14 12 |
6 6 4 |
35 |
7 7 10 |
-4 |
28 |
17 |
* 19 11 |
5 6 |
21 |
9 9 4 |
12 |
-13 |
40 |
6 6 12 |
4 4 5 |
22 |
* 9 24 |
* 4 35 |
* 17 20 |
4 |
32 |
29 |
* 9 24 |
* 5 16 |
* 10 20 |
8 8 9 |
24 |
0 |
Vj |
22 |
24 |
16 |
20 |
31 |
16 |
|
Новая стоимость перевозки составит: C==2258
Таблица 1.10
-
0
1
-6
-5
0
9
5
-18
0
-12
8
-2
8
0
+3
14
-14
9
-14
-23
2
0
0
0
7
0
0
0
-22
8
Так как нарушение в клетках отсутствует, план является оптимальным. Минимальная стоимость при этом составит 2258.
ЗАДАЧА 2