Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Составляем таблицу значений lij. Таблица будет заполнена ниже главной диагонали, т.к. матрица стоимости перевозок симметрична.
Первая сверху строка и первый слева столбец и клетки главной диагонали не заполняются, т.к. параметр lij вычисляется при i¹j¹0.
lij= di0 + d0j - dij
l21= d20 + d01 - d21 =6+4-3=7
P1 | P2 | P3 | P4 | P5 | P6 | |
P1 | - | - | - | - | - | - |
P2 | - | - | - | - | - | |
P3 | - | - | - | - | ||
P4 | - | - | - | |||
P5 | - | - | ||||
P6 | - |
Выбираем начальное тривиальное решение S.
Составляем таблицу для g i и объёмности перевозок по контурам решения S.
g i | Q{ Pi } | |
P0,P1,P0 | g 1 =1 | Q{P1}=C 1=4 |
P0,P2,P0 | g 2 =1 | Q{P2}=C 2=6 |
P0,P3,P0 | g 3 =1 | Q{P3}=C 3=3 |
P0,P4,P0 | g 4 =1 | Q{P4}=C 4=1 |
P0,P5,P0 | g 5 =1 | Q{P5}=C 5=8 |
P0,P6,P0 | g 6 =1 | Q{P6}=C 6=2 |
1). l63= 12 =maximum
g6 = g3 =1 и Q{P6}+ Q{P3}=C 6+ C 3=2+3=5< C =10
Образуем класс {P6,P3} и выделяем l63 кружком в таблице. Значения g i не изменяются.
2). l62= 10 > 0
Пробуем объединить классы {P6,P3} и {P2}:
g6 = g2 =1 и Q{P6}+ Q{P3}+ Q{P2}=C 6+ C 3+ C 2=2+3+6=11 > C =10
Вычёркиваем l62 в таблице. Значения g i не изменяются.
3). l53= 10 > 0
Пробуем объединить классы {P6,P3} и {P5}:
g5 = g3 =1 и Q{P5}+ Q{P6}+ Q{P3}=C 5+ C 6+ C 3=8+2+3=13 > C =10
Вычёркиваем l53 в таблице. Значения g i не изменяются.
4). l31= 9 > 0
Пробуем объединить классы {P6,P3} и {P1}:
g1 = g3 =1 и Q{P3}+ Q{P6}+ Q{P1}=C 3+ C 6+ C 1=3+2+4=9 < C =10
Образуем класс {P6,P3,P1}. Отмечаем клетку l31 в таблице.
Находим новые значения g i: g6 = g1 =1; g3 =0
5). l32= 9 > 0
g3 =0, g2 =1 Условие а) не выполняется. Поэтому вычеркиваем клетку l32.
6). l51= 7 > 0
g5 = g1 =1 и Q{P5}+ Q{P1}+ Q{P6}+ Q{P3}=C 5+ C 1+ C 6+ C 3=8+4+2+3=17 > C =10
Вычёркиваем l51 в таблице. Значения g i не изменяются.
7). l21= 7 > 0
g2 = g1 =1 и Q{P2}+ Q{P1}+ Q{P6}+ Q{P3}=C 2+ C 1+ C 6+ C 3=6+4+2+3=15 > C =10
Вычёркиваем l21 в таблице. Значения g i не изменяются.
8). l64 = 5 > 0
g6 = g4 =1 и Q{P6}+ Q{P3}+ Q{P1}+ Q{P4}=C 6+ C 3+ C 1+ C 4=2+3+4+1=10 = C =10
Образуем класс {P4,P6,P3,P1}. Отмечаем клетку l64 в таблице.
Находим новые значения g i: g1 = g4 =1; g3 = g6 =0
9). l65 = 5 > 0
g6 =0, g5 =1 Условие а) не выполняется. Поэтому вычеркиваем клетку l65.
10). l61 = 4 > 0
Но {P6} и {P1} уже в одном классе! Поэтому вычеркиваем клетку l61.
11). l41 = 4 > 0
Но {P4} и {P1} тоже уже в одном классе! Поэтому вычеркиваем клетку l41.
12). l52= 3 > 0
Пробуем объединить классы {P5} и {P2}:
g5 = g2 =1 и Q{P5}+ Q{P2}=C 5+ C 2=8+6=14 > C =10. Условие не выполнено.
Вычеркиваем клетку l52 в таблице.
13). l54= 3 > 0
Пробуем объединить классы {P4, P6, P3, P1,} и {P5}:
g5 = g4 =1. Очевидно, что S Q{P} будет > C =10. Условие не выполнено.
Вычеркиваем клетку l54 в таблице.
14). l42= 2 > 0
Пробуем объединить классы {P4, P6, P3, P1,} и {P2}:
g2 = g4 =1. Очевидно, что S Q{P} будет > C =10. Условие не выполнено.
Вычеркиваем клетку l42 в таблице.
15). l43 = 2 > 0
Но {P4} и {P3} уже в одном классе! Поэтому вычеркиваем клетку l41.
Все элементы l43 мы рассмотрели. У нас получились такие маршруты, являющиеся решением задачи:
(Р0,Р4,Р6,Р3,Р1,Р0)= d04 + d46 + d63 + d31 + d10 =2+2+1+3+4=12;
(Р0,Р2,Р0)= d02 + d20 =6+6=12;
(Р0,Р5,Р0)= d05 + d50 =4+4=8;
Общая стоимость перевозок: 12+12+8=32.
Полученная ранее стоимость перевозок без учёта метода Флетчера-Кларка была равна 44, что больше 32.
Дата публикования: 2015-01-13; Прочитано: 208 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!