Материал: Математические методы и модели в экономике. Амелин С.В
Распределительный метод решения транспортной задачи
Пусть дан некоторый опорный план. Для каждой свободной клетки таблицы перевозок вычислим алгебраические суммы стоимостей в вершинах цикла ij. Так, для клетки (4,1) получим
41 = 6 – 5 + 4 – 3 + 1 – 2 = 1.
Если все ij неотрицательны ( ij 0), то задача решена, т.е. найден оптимальный план перевозок.
Допустим, есть хотя бы одно отрицательное значениеij, тогда среди отрицательных ij выбираем наименьшее и для этой клетки i0, j0 делаем сдвиг по циклу пересчета на величину0, равную наименьшей из перевозок, стоящих в отрицательных вершинах цикла. Полученный новый опорный план будет лучше предыдущего, при этом целевая функция умень-
шится на величину |
0 i |
j . |
|
|
0 0 |
Замечания: |
|
|
1.Каждая сумма ij начинается с положительного числа и кончается отрицательным. Количество всех слагаемых четное.
2.Если опорный план вырожденный, то возможен
сдвиг по циклу пересчета на величину = 0. При этом значение целевой функции не изменится, а изменятся базисные клетки.
Найдем решение задачи, первоначальный опорный план которой получен методом северо-западного угла, и введем дополнительное условие: груз из пункта А2 в пункт В3 не может быть доставлен:
130
|
В1 |
|
В2 |
|
В3 |
В4 |
|
Для всех свободных |
|
А1 |
- 5 |
|
+ 4 |
2 |
5 |
30 |
клеток вычислим ij: |
||
|
20 |
|
10 |
|
|
|
|
|
13 = 2 – 1 + 3 – 4 = 0, |
|
|
6 |
|
|
1 |
М |
3 |
70 |
14 = 5 – 1 + 2 – 1 + 3 – 4 = |
А2 |
|
|
|
|
|
|
|
||
|
|
70 |
|
|
|
|
|
= 4, |
|
|
|
|
|
|
|
|
|
||
|
+ |
2 |
- |
|
3 |
1 |
8 |
50 |
21 = 6 – 5 + 4 – 1 = 4, |
|
|
|
|
|
|
||||
А3 |
|
|
|
|
|
|
|
|
23 = М – 1 + 3 – 1 = |
|
|
10 |
|
|
40 |
|
|
||
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
= М + 1, |
|
|
6 |
|
|
3 |
2 |
1 |
100 |
|
А4 |
|
|
|
|
|
|
|
24 = 3 – 1 + 2 – 1 + 3 – 1 = |
|
|
|
|
|
|
30 |
70 |
|
||
|
|
|
|
|
|
|
= 5, |
||
|
20 |
|
90 |
|
70 |
70 |
|
||
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
||
31 = 2 – 3 + 4 – 5 = -2, 34 = 8 – 1 + 2 – 1 = 8, |
|||||||||
41 = 6 – 5 + 4 – 3 + 1 – 2 = 1, 42 = 3 – 3 + 1 – 2 = -1. |
|||||||||
Поскольку не все ij 0, план перевозок не оптимален. Среди ij < 0 выбираем наименьшее. Это 31 = -2. Делаем сдвиг по циклу пересчета для свободной клетки (3,1) на величину 0. Этот цикл проходит через базисные клетки (1,1), (1,2) и (3,2). В этом цикле две отрицательные клетки (1,1) и (3,2). Им соответствуют перевозки 20 и 10. В качестве 0 выбираем меньшее из этих чисел, т.е. 0 = 10. После сдвига по циклу пересчета на величину 0 переходим к следующему опорному плану:
|
В1 |
|
В2 |
|
В3 |
В4 |
|
|
А1 |
- |
5 |
4 |
+ 2 |
5 |
30 |
||
|
10 |
|
20 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
1 |
|
М |
3 |
70 |
А2 |
|
|
|
|
|
|
|
|
|
|
|
70 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
+ |
|
2 |
3 |
|
- 1 |
8 |
50 |
А3 |
10 |
|
|
40 |
|
|
||
|
|
|
|
|
||||
|
|
|
6 |
3 |
2 |
1 |
100 |
|
А4 |
|
|
|
|
|
|
|
|
|
|
|
|
30 |
70 |
|
||
|
|
|
|
|
|
|||
|
20 |
|
90 |
70 |
70 |
|
||
|
|
|
|
|
|
|
|
|
Делаем второй шаг распределительного метода. Находим значения ij для всех свободных клеток
13 = 2 – 5 + 2 – 1 = -2,14 = 5 – 1 + 2 – 1 + 2 – 5 = = 2,
21 = 6 – 5 + 4 – 1 = 4,
23 = М – 1 + 4 – 5 + 2 - 1 = М – 1 0,
131
24 = 3 – 1 + 4 – 5 + 2 – 1 + 2 – 1 = 3,32 = 3 – 4 + 5 – 2 = 2,34 = 8 – 1 + 2 – 1 = 8,41 = 6 – 2 + 1 – 2 = 3,
42 = 3 – 4 + 5 – 2 + 1 – 2 = 1.
f(х) = 10 5 + 20 4 + 70 1 + 10 2 + 40 1 + 30 2 + 70 1 = 390.
Делаем сдвиг по циклу пересчета для свободной клетки (1,3) на величину 0 = 10. Переходим к новому опорному плану:
|
В1 |
В2 |
|
В3 |
|
В4 |
|
|
Найдем ij для этой |
||
А1 |
5 |
- |
|
4 |
+ |
2 |
5 |
|
30 |
таблицы |
|
|
|
|
|
|
|
|
|
||||
|
|
20 |
|
|
10 |
|
|
|
|
|
11 = 5 – 2 + 1 – 2 = 2, |
|
6 |
|
1 |
|
М |
3 |
|
70 |
14 = 5 – 2 + 2 – 1 = 4, |
||
А2 |
|
|
|
|
|
|
|
|
|
||
|
70 |
|
|
|
|
|
|
|
|
21 = 6 – 1 + 4 – 2 + 1 – 2 |
|
|
|
|
|
|
|
|
|
|
|
||
|
2 |
|
|
3 |
|
|
1 |
8 |
|
50 |
= 6, |
|
|
|
|
|
|
|
|
||||
А3 |
20 |
|
|
|
30 |
|
|
|
|
|
23 = М – 2 + 4 – 1 = |
|
|
|
|
|
|
|
|
|
|||
|
6 |
+ |
|
3 |
- |
|
2 |
1 |
|
100 |
= М + 1, |
А4 |
|
|
|
|
|
|
|
24 = 3 – 1 + 4 – 2 + 2 – 1 |
|||
|
|
|
30 |
|
70 |
|
|
||||
|
|
|
|
|
|
= 5, |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
20 |
90 |
|
70 |
|
70 |
|
|
32 = 3 – 4 + 2 – 1 = 0, |
||
|
|
|
|
|
34 = 8 – 1 + 2 – 1 = 8, |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
41 = 6 – 2 + 1 – 2 = 3, |
|
42 = 3 – 4 + 2 – 2 = -1. |
||||||||
f(х) = 20 4 + 10 |
2 + 70 1 + 20 |
2 + 30 1 + 30 2 + 70 1 = 370. |
|||||||||
Делаем сдвиг по циклу пересчета для свободной клетки (4,2) на величину 0 = 20.
Переходим к новому опорному плану:
132
|
В1 |
В2 |
В3 |
В4 |
|
Определим значения ij |
|
5 |
4 |
2 |
5 |
30 |
11 = 5 – 2 + 1 – 2 = 2, |
А1 |
|
|
|
|
||
|
|
30 |
|
|
12 = 4 – 2 + 2 – 3 = 1, |
|
|
|
|
|
|
||
|
6 |
1 |
М |
3 |
70 |
14 = 5 – 1 + 2 – 2 = 4, |
|
|
|
||||
А2 |
|
70 |
|
|
|
21 = 6 – 1 + 3 – 2 + 1 – 2 = |
|
|
|
|
|
||
|
2 |
3 |
1 |
8 |
50 |
= 5, |
А3 |
|
|
|
|
23 = М – 1 + 3 – 2 = |
|
20 |
|
30 |
|
|
||
|
|
|
|
= М 0, |
||
|
6 |
3 |
2 |
1 |
100 |
|
А4 |
|
|
|
|
24 = 3 – 1 + 3 – 1 = 4, |
|
|
20 |
10 |
70 |
|
||
|
|
|
32 = 3 – 3 + 2 – 1 = 1, |
|||
|
20 |
90 |
70 |
70 |
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
34 = 8 – 1 + 2 – 1 = 8, |
41 = 6 – 2 + 1 – 2 = 3. |
||||
f(х) = 30 2 + 70 1 + 20 2 + 30 1 + 20 3 + 10 2 + 70 1 = 350.
Для этого плана все ij > 0. Следовательно, этот опорный план оптимальный.
Для расчёта задач транспортного типа в среде Excel (рис. 65) необходимо ввести в таблицу тарифы на перевозку единицы груза по различным маршрутам (например, в ячейки B3:Е6), величину предложения поставщиков (например, в ячейки F3:F6) и величину спроса потребителей (например, в ячейки B7:Е7). Для размещения искомых значений переменных необходимо зарезервировать свободные ячейки (например, ячейки B9:Е12). Математические выражения для системы ограничений по спросу и предложению вводятся (например, в ячейки F9:F12 и B13:E13 соответственно) с помощью функции СУММ (рис. 66). Целевая функция вводятся (например, в ячейку F13) с помощью функции СУММПРОИЗВ из категории Математические (рис. 67). Для этого необходимо выбрать в меню Вставка строку Функция….
133
Рис. 65. Ввод исходных данных транспортной задачи в Excel
Рис. 66. Табличное представление транспортной задачи в Excel
Аргументами функции СУММПРОИЗВ являются: Массив1 - адреса матрицы тарифов перевозок, Массив2 – адреса
134