Методом «северо-западного» угла найдем опорный план перевозок:
Сток Исток |
|
|
|
| Запасы: | ||||
| 10 | 7 | 6 | 8 | 31 | ||||
22 | 9 | ||||||||
| 5 | 6 | 5 | 4 | 48 | ||||
25 | 23 | ||||||||
| 8 | 7 | 6 | 7 | 38 | ||||
18 | 20 | ||||||||
Заявки: | 22 | 34 | 41 | 20 | 117 |
1. Составленный с помощью метода «северо-западного угла» опорный план имеет шесть базисных клеток в соответствующей ему транспортной таблице, что позволяет его использовать без модификаций для дальнейшего решения задачи.
r = n + m – 1 = 4 + 3 – 1 = 6
Посчитаем теперь стоимость найденного опорного плана:
L = 22×10 + 9×7 + … = 796
Попытаемся улучшить найденный опорный план перевозок методом циклических переносов.
2. Вычислим цену цикла для каждой свободной клетки. Количество свободных клеток в транспортной таблице данного опорного плана равно: k = 3×2 = 6.
3. Для всех свободных переменных (клеток) с отрицательной ценой цикла вычислим максимальное количество груза, которое можно перенести по соответствующему циклу. Очевидно, что максимальное количество груза, которое можно переместить по некоторому выбранному циклу будет равно минимальному значению груза среди отрицательных клеток цикла.
4. Теперь для всех свободных переменных с отрицательной ценой циклов вычислим характеристику 
. Полученные значения будем использовать при выборе конкретного цикла пересчета на данной итерации алгоритма.
ij | 2,1 | 2,4 | 31 |
g | - 4 | - 2 | - 2 |
x | 22 | 20 | 18 |
gx | - 88 | - 40 | - 36 |
5. Выберем ту свободную переменную, которой соответствует наименьшее значение величины 
и перенесем 
единиц груза по циклу, соответствующему выбранной переменной: (ij) = (2,1); g21 = - 4; 
.
Сток Исток |
|
|
|
| Запасы: | ||||
| 10 | 7 | 6 | 8 | 31 | ||||
22 | 9 | ||||||||
| 5 | 6 | 5 | 4 | 48 | ||||
25 | 23 | ||||||||
| 8 | 7 | 6 | 7 | 38 | ||||
18 | 20 | ||||||||
Заявки: | 22 | 34 | 41 | 20 | 117 |
Таким образом, мы уменьшим значение целевой функции L – стоимость плана перевозок – на 88 единиц. Новому улучшенному плану перевозок будет соответствовать следующая таблица перевозок:
Сток Исток |
|
|
|
| Запасы: | ||||
| 10 | 7 | 6 | 8 | 31 | ||||
31 | |||||||||
| 5 | 6 | 5 | 4 | 48 | ||||
22 | 3 | 23 | |||||||
| 8 | 7 | 6 | 7 | 38 | ||||
18 | 20 | ||||||||
Заявки: | 22 | 34 | 41 | 20 | 117 |
Полученный на этапе 5 первой итерации алгоритма новый план перевозок имеет шесть базисных клеток в соответствующей ему транспортной таблице (см. таблицу выше), что позволяет его использовать без модификаций для дальнейшего решения задачи.
r = 6
Стоимость найденного плана перевозок равна:
L = 31×7 + 22×5 + … = 708
Попытаемся опять улучшить найденный опорный план перевозок. Для этого перейдем к пункту 2 алгоритма:
2. Вычислим цену цикла для каждой свободной переменной:
3. Вычислим максимальное количество груза, которое можно перенести по циклу с отрицательной ценой. Результаты расчетов, проделанных в предыдущем пункте, показали, что данная таблица содержит всего одну переменную и соответствующую ей свободную клетку. Таким образом, на данной итерации алгоритма нет необходимости в выборе цикла переноса.
.
4. Для единственной свободной переменной рассчитаем значение критерия :
.
Сток Исток |
|
|
|
| Запасы: | ||||
| 10 | 7 | 6 | 8 | 31 | ||||
31 | |||||||||
| 5 | 6 | 5 | 4 | 48 | ||||
22 | 3 | 23 | |||||||
| 8 | 7 | 6 | 7 | 38 | ||||
18 | 20 | ||||||||
Заявки: | 22 | 34 | 41 | 20 | 117 |
Перенесем 
единиц груза по циклу
(2,4)+, (3,4)-, (3,3)+, (2,3)-, уменьшив этим значение целевой функции на 40 единиц. Новому улучшенному плану перевозок будет соответствовать следующая таблица перевозок:
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
Основные порталы (построено редакторами)