Главная » Просмотр файлов » Метод ветвей и границ

Метод ветвей и границ (1021741), страница 3

Файл №1021741 Метод ветвей и границ (Метод ветвей и границ) 3 страницаМетод ветвей и границ (1021741) страница 32017-07-10СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Теперь множеству тоже сопоставим некую матрицу M1,2. Для этого в матрице M1 заменим на ¥ число в клетке и полученную в результате матрицу приведем. Сумму констант приведения запомним, а полученную матрицу обозначим через M1,2. Прибавим запомненную сумму констант приведения к числу j(G) и полученное число, обозначаемое в дальнейшем через j( ), сопоставим множеству .

Теперь выберем между множествами и то, на котором минимальна функция j (т.е. то из множеств, которому соответствует меньшее из чисел j( ) и j( )).

Заметим теперь, что в проведенных рассуждениях использовался в качестве исходного только один фактический объект – приведенная матрица весов данного орграфа. По ней было выделено определенное ребро графа и были построены новые матрицы, к которым, конечно, можно все то же самое применить.

При каждом таком повторном применении будет фиксироваться очередное ребро графа. Условимся о следующем действии: перед тем, как в очередной матрице вычеркнуть строку и столбец, в ней надо заменить на ¥ числа во всех тех клетках, которые соответствуют ребрам, заведомо не принадлежащим тем гамильтоновым циклам, которые проходят через уже отобранные ранее ребра.

К выбранному множеству с сопоставленными ему матрицей и числом j повторим все то же самое и так далее, пока это возможно.

Доказывается, что в результате получится множество, состоящее из единственного обхода коммивояжера, вес которого равен очередному значению функции j; таким образом, оказываются выполненными все условия, обсуждавшиеся при описании метода ветвей и границ.

После этого осуществляется улучшение рекорда вплоть до получения окончательного ответа.

3.2 Условие задачи

Студенту Иванову поручили разнести некоторые важные документы из 12-ого корпуса. Но, как назло, у него на это очень мало времени, да и еще надо вернуться обратно. Нужно найти кротчайший путь. Расстояния между объектами даны в таблице

.

12-ый корпус

Белый дом

КРК «Премьер»

Администрация

5-ый корпус

12-ый корпус

0

6

4

5

2

Белый дом

6

0

3

3,5

4,5

КРК «Премьер»

4

3

0

5,5

5

Администрация

5

3,5

5,5

0

2

5-ый корпус

2

4,5

5

2

0

3.3 Математическая модель задачи

Для решения задачи присвоим каждому пункту маршрута определенный номер: 12-ый корпус – 1, Белый дом – 2, КРК «Премьер» – 3, Администрация – 4 и 5-ый корпус – 5. Соответственно общее количество пунктов . Далее введем альтернативных переменных , принимающих значение 0, если переход из i-того пункта в j-тый не входит в маршрут и 1 в противном случае. Условия прибытия в каждый пункт и выхода из каждого пункта только по одному разу выражаются равенствами (8) и (9).

(8)

(9)

Для обеспечения непрерывности маршрута вводятся дополнительно n переменных и дополнительных ограничений (10).

(10)

Суммарная протяженность маршрута F, которую необходимо минимизировать, запишется в следующем виде:

(11)

В нашем случае эти условия запишутся в следующем виде:

(8 а)

(9 а)

(10 а)

(11 а)

3.4 Решение задачи методом ветвей и границ

задача коммивояжер ветвь граница

1) Анализ множества D.

Найдем оценку снизу Н. Для этого определяем матрицу минимальных расстояний по строкам (1 где расстояние минимально в строке).

=> ;

Аналогично определяем матрицу минимальных расстояний по столбцам.

=> ;

;

Выберем начальный план: . Тогда верхняя оценка:

. Очевидно, что , где означает переход из первого пункта в j-тый. Рассмотрим эти подмножества по порядку.

2) Анализ подмножества D12.

;

;

;

;

;

3) Анализ подмножества D13.

;

;

;

;

4) Анализ подмножества D14.

;

;

;

;

;

5) Анализ подмножества D15.

;

;

;

;

;

6) Отсев неперспективных подмножеств.

;

Подмножества D13 и D15 неперспективные. Т.к. , но , то далее будем рассматривать подмножество D14.

.

7) Анализ подмножества D142.

;

;

;

;

;

8) Анализ подмножества D143.

;

;

;

;

9) Анализ подмножества D145.

;

;

;

;

;

10) Отсев неперспективных подмножеств

;

Подмножество D143 неперспективное. Т.к. , но , то далее будем рассматривать подмножество D145.

.

11) Анализ подмножества D1452.

;

;

;

;

;

12) Анализ подмножества D1453.

;

;

;

;

;

;

Оптимальное решение: .

.

Таким образом, маршрут студента: 12-ый корпус – Администрация – 5-ый корпус – Белый дом – КРК Премьер – 12-ый корпус.


Список литературы

  1. Абрамов Л.А., Капустин В.Ф. Математическое программирование. – Л.: Изд-во ЛГУ, 1981. -328 с.

  2. Алексеев О.Г. Комплексное применение методов дискретной оптимизации. – М.: Наука, 1987. -294 с.

  3. Корбут А.А., Финкелгейн Ю.Ю. Дискретное программирование. М.: Наука. 1969. -240 с

  4. Кузнецов Ю.Н. и др. Математическое программирование: Учебное пособие. – 2-е изд., перераб и доп. – М.: Высшая школа, 1980. -300 с.

  5. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. – М.: Мир, 1985. -213 с.

Размещено на Allbest.ru

Характеристики

Тип файла
Документ
Размер
2,22 Mb
Тип материала
Высшее учебное заведение

Список файлов лекций

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6451
Авторов
на СтудИзбе
305
Средний доход
с одного платного файла
Обучение Подробнее