Методическое пособие для выполнения контрольной работы по дисциплине
жүктеу/скачать 0.49 Mb.
|
- Бұл бет үшін навигация:
- Задача коммивояжера Агент по сбыту собирается посетить каждый из n городов по одному разу, выехав из одного города и вернувшись в него же. Обозначим расстояние между городами i
Построимсеть данной задачи. Находим кратчайшие расстояния из вершины x0. в xj согласно алгоритму Форда. Начальный шаг. Вершине x0 присваивается метка (0;x), остальным метка (+;x), Общий шаг. Начнем с вершины x0, имеющей конечную метку 0=0. Из нее выходят две дуги (0;1) и (0;2). Дуга (0;1) вершине x1 дает метку 1=0+l01=0+10=10. Так как вершина x1 ещё не имеет меток, то ей присваивается метка (10;x0). Дуга (0;2) вершине x2 дает метку 2=0+l02=0+11=11, и этой вершине присваивается метка (11; x0). Так как нет других путей, ведущих в x1, x2, то полученные метки будут окончательными. Из вершины x1 выходят три дуги (1;3), (1;4) и (1;6) к вершинам x3, x4 и x6, не имеющие пока меток. Вычислим метки для этих трех вершин: 3=1+l13=10+8=18, 4=1+l14=10+23=33 и 6=1+l16=10+12=22. Соответствующие вершины будут иметь следующие метки: (18;x1), (33;x1)и (22;x1), причем метка вершины x4 будет окончательной. Из вершины x2 выходят три дуги (2;3), (2;5) и (2;6). Вычислим метки для трех вершин x3, x5 и x6: 3=2+l23=11+4=15, 5=2+l25=11+6=17 и 6=2+l26=11+18=29. Соответствующие вершины будут иметь следующие метки: (15;x2), (17;x2)и (29; x2), причем метка вершины x5 будет окончательной. Для вершины x3 имеем прежнюю метку (18;x1) и новую метку (15;x2). Так как 15<18, то метка пересматривается и окончательной становится новая метка(15;x2). Для вершины x6 имеем прежнюю метку (22;x1) и новую метку (29;x2). Так как 22<29, то оставляем прежнюю метку, причем она не является окончательной. Так как вершина x3 имеет метку (15;x2) и из нее выходит единственная дуга (3;7), ведущая в непомеченную вершину x7, то получаем 7=3+l37=15+13=28 и метку (28;x3), являющейся неокончательной. Вершина x4 имеет метку (33;x1) и из нее выходят две дуги (4;6) и (4;8). Вычисляем: 6=4+l46=33+9=42, что больше, чем 22 и, следовательно, остается прежняя метка (22; x1); 8=4+l48=33+15=48 и присваивается новая метка (48;x4). Вершина x5 имеет метку (17;x2) и из нее выходит одна дуга (5;7). Вычисляем 7=5+l57=17+8=25. Так как предыдущая метка вершины x7 (28;x3) больше, то полученная метка (25;x5) будет окончательной. Из вершины x6выходит единственная дуга (6;8), для которой 8=6+l68=22+13=35. Так как полученная метка (35;x6) меньше, чем уже имеющаяся (48;x4), то вершине приписываем метку (35;x6). Из вершины x7, имеющей окончательную метку, выходят две дуги (7;6) и (7;8). Вычисляем 6=7+l76=25+8=33 и 8=7+l78=25+17=42. Так как полученная для x6 новая метка (33;x7) больше, чем метка (22; x1). Для вершины x8 полученная новая метка(42;x7) больше имеющейся (35;x6), то последняя метка будет окончательной. Окончательно, результаты решения сведем в таблицу.
Задание 4. Построить сетевой график, установить кратчайшие пути и найти расстояние от x1 до всех узлов сети: x12=9; x13=5; x14=5; x29=14-m; x26=4; x32=8; x36=10; x35=8; x43=3+n; x45=4; x48=15-k; x37=3; x58=7; x65=9; x67=3+2k; x69=6; x79=2+m; x7,10=6;x87=11; x8,10=12-n; x9,10=7. Задача коммивояжера Агент по сбыту собирается посетить каждый из n городов по одному разу, выехав из одного города и вернувшись в него же. Обозначим расстояние между городами i и j как cij. Тогда задача коммивояжера математически буде записана следующим образом: Решить задачу коммивояжера – это значит найти цикл. Данная задача является частным случаем целочисленного программирования. Одним из методов решения такой задачи будет метод ветвей и границ, суть которого состоит из двух этапов: вычисление нижней границы и ветвление. Метод ветвей и границ довольно трудоемок, поэтому мы будем решать задачу коммивояжера табличным способом. Условия задачи коммивояжера задаются в виде матрицы расстояний, причем, если дуги xixj нет в графе задачи, то вместо cij будет “-“, при чем не обязательно cij=cji.
Решим задачу коммивояжера на примере конкретной задачи, заданной следующей матрицей расстояний:
Первым действием в решении данной задачи является так называемая операция приведения матрицы, которая основывается на том, что при уменьшении чисел какой-либо строки на одно и то же число длины всех маршрутов уменьшаются на это же число, так как в длину каждого маршрута в качестве слагаемого входят только по одному числу из каждой строки (столбца). Кратчайший маршрут при этом сохраняется, но его длина уменьшается на это число. В последнем столбце таблицы записаны минимальные значения по строкам. Вычитая эти числа из соответствующих строк, получим следующую таблицу:
Вычитая число 15 из столбца А4, мы получаем новую таблицу, которая называется приведенной:
Числа, которые вычитались, называются постоянными приведения. Так как каждая постоянная приведения входит как слагаемое в длину любого маршрута, то за нижнюю границу можно принять сумму всех постоянных приведения: L=L0+l, где l=(9+11+9+17+3+11)+(15)=75. Это начальный шаг алгоритма (применяется однократно). Следующим шагом алгоритма является ветвление, так называемый общий шаг, который применяется неоднократно. Каждый раз нужно определить способ ветвления, а именно, выбирается дуга жүктеу/скачать 0.49 Mb. Достарыңызбен бөлісу:
|