close

Вход

Забыли?

вход по аккаунту

?

lab 4

код для вставкиСкачать
Министерство образования и науки Российской Федерации
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ
ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
"ОРЕНБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ"
Финансово-экономический факультет
Кафедра математических методов и моделей в экономике
Отчет по расчетно-графической работе №4
по дисциплине "Методы оптимальных решений"
Руководитель работы
____________ А.В Раменская "____"_____________20___г.
Исполнитель студент группы 12Эк(б)УФУ
____________М.М.Сайфутдинов
"____"_____________20___г.
Оренбург 2013
Задача коммивояжера. Имеется n городов. Расстояние (Sij)n x n - матрица расстояний.
Коммивояжёр должен побывать во всех городах и вернуться в свой. Необходимо найти минимальный замкнутый маршрут, если n = 6.∞
i j1234561∞152082410215∞3018352832030∞162212481816∞1938524352219∞4061028123840∞ Для определения нижней границы множества воспользуемся операцией редукции. di = min(j) dij i j123456di1∞1520824108215∞301835281532030∞16221212481816∞19388524352219∞401961028123840∞10 dj = min(i) dij i j1234561∞712016220∞15320133818∞410040108∞1130551630∞21601822830∞dj0720100 После вычитания минимальных элементов получаем полностью редуцированную матрицу.
i j1234561∞01006220∞13310133811∞4004036∞13055910∞21601102820∞ Сумма минимальных элементов определяет нижнюю границу h: h1 = ∑di + ∑dj h1 = 8+15+12+8+19+10+0+7+2+0+10+0 = 91 Элементы матрицы dij соответствуют расстоянию от пункта i до пункта j. Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город. Шаг №1. Оценка нулевых элементов редуцированной матрицы.
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на ∞ (бесконечность) и определяем для них сумму образовавшихся минимальных элементов, они приведены в скобках. i j123456di1∞0(3)100(0)62020(3)∞133101333811∞40(1)0(2)040(1)36∞130155910(1)∞21160(0)110(1)2820∞0dj0310120 Q(1,2) = 0 + 3 = 3; Q(1,4) = 0 + 0 = 0; Q(2,1) = 3 + 0 = 3; Q(3,5) = 0 + 1 = 1; Q(3,6) = 0 + 2 = 2; Q(4,1) = 1 + 0 = 1; Q(5,4) = 1 + 0 = 1; Q(6,1) = 0 + 0 = 0; Q(6,3) = 0 + 1 = 1. Наибольшее Qij = 3 для ребра (1,2).
Исключение ребра (1,2) проводится путем исключения всех элементов 1-ой строки и 2-го столбца, в которой элемент d21 заменяем на ∞. В результате получим другую сокращенную матрицу (5 x 5), которая подлежит операции приведения. После операции приведения сокращенная матрица будет иметь вид: i j13456di2∞1331013338∞4000406∞13005510∞2106002820∞0dj000003 Нижняя граница равна: H2 = 91 + 3 = 94 Шаг №2. Оценка нулевых элементов
i j13456di2∞100(7)710738∞40(1)0(10)040(1)6∞13015510(1)∞21160(0)0(1)2820∞0dj0101100 Q(2,4) = 7 + 0 = 7; Q(3,5) = 0 + 1 = 1; Q(3,6) = 0 + 10 = 10; Q(4,1) = 1 + 0 = 1; Q(5,4) = 1 + 0 = 1; Q(6,1) = 0 + 0 = 0; Q(6,3) = 0 + 1 = 1; Наибольшее Qij = 10 для ребра (3,6). Исключение ребра (3,6) проводится путем исключения всех элементов 3-ой строки и 6-го столбца, в которой элемент d63 заменяем на ∞. В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения. После операции приведения сокращенная матрица будет иметь вид: i j1345di2∞10070406∞105510∞060∞28200dj01012 Нижняя граница подмножества (3,6) равна: H3 = 94 + 2 = 96 Шаг №3. Оценка нулевых элементов
i j1345di2∞90(6)6640(0)5∞0(6)0550(5)0(0)∞060(19)∞281919dj05060 Q(2,4) = 6 + 0 = 6; Q(4,1) = 0 + 0 = 0; Q(4,5) = 0 + 6 = 6; Q(5,3) = 0 + 5 = 5; Q(5,4) = 0 + 0 = 0; Q(6,1) = 19 + 0 = 19; Наибольшее Qij = 19 для ребра (6,1).
Исключение ребра (6,1) проводится путем исключения всех элементов 6-ой строки и 1-го столбца, в которой элемент d16 заменяем на ∞.
В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения. После операции приведения сокращенная матрица будет иметь вид: i j345di2906045∞00500∞0dj0000 Нижняя граница подмножества (6,1) равна: H4 = 96 + 0 = 96 Шаг №4. Оценка нулевых элементов
i j345di2∞0(6)6645∞0(11)550(5)0(0)∞0dj5060 Q(2,4) = 6 + 0 = 6; Q(4,5) = 5 + 6 = 11; Q(5,3) = 0 + 5 = 5; Q(5,4) = 0 + 0 = 0; Наибольшее Qij = 11 для ребра (4,5).
Исключение ребра (4,5) проводится путем исключения всех элементов 4-ой строки и 5-го столбца, в которой элемент d54 заменяем на ∞. В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения. После операции приведения сокращенная матрица будет иметь вид: i j34di2∞0050∞0dj000 Нижняя граница подмножества (4,5) равна: H5 = 96 + 0 = 96 В соответствии с этой матрицей включаем в маршрут ребра (2,4) и (5,3). В результате по дереву ветвлений маршрут образуют ребра: (1,2), (2,4), (4,5), (5,3), (3,6), (6,1).
Оптимальный маршрут: 1 - 2 - 4 - 5 - 3 - 6 - 1.
Длина маршрута = 96 010000000100000001000010001000100000 X =
Smin = 15+18+19+22+12+10 = 96
Документ
Категория
Рефераты
Просмотров
56
Размер файла
118 Кб
Теги
lab
1/--страниц
Пожаловаться на содержимое документа