Исследовательская работа: Задача коммивояжера


Чтобы посмотреть презентацию с оформлением и слайдами, скачайте ее файл и откройте в PowerPoint на своем компьютере.
Текстовое содержимое слайдов:

Задача о коммивояжереЗадача коммивояжера
Постановка задачи коммивояжераКоммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2, 1, 3,..n и вернуться в первый город. Расстояния между городами известны.Вопрос:В каком порядке следует обходить города, чтобы замкнутый путь ( тур) коммивояжера был кратчайшим. Постановка задачи коммивояжераjТ=(1,2,3..n) - городаt=(j1,j2,..,jn,j1) – тур коммивояжераЗадача состоит в том, чтобы найти такой тур t, чтобы минимизировать функционал Условия: 1) Сij0; Cji=∞ 2) Сij= Сji. 3)Сij+ СjkCik Методы решения ЗКЖадный алгоритм;Деревянный алгоритм;Перебор в лексикографическом порядке;Метод Ветвей и границ; Задача:Коммивояжер должен объездить 6 городов: Уфу, Стерлитамак, Нефтекамск, Салават, Мелеуз и Туймазы. Для того, чтобы сократить расходы, он хочет построить такой маршрут, чтобы объездить все города точно по одному разу и вернуться в исходный город с минимумом затрат. Исходный город – Нефтекамск. Исходная матрица{08FB837D-C827-4EFA-A057-4D05807E0F7C}УфаСтерлитамакНефтекамскСалаватМелеузТуймазыУфа∞125228156205205Стерлитамак125∞3533180321Нефтекамск228353∞384433220Салават15631384∞103352Мелеуз20580433103∞322Туймазы205321220352322∞ Решение задачи Жадным алгоритмом Расстояние, пройденное коммивояжером равно:220+205+125+31+103+433=1117 км Решение задачи Деревянным алгоритмом Коммивояжер проедет расстояние, равное:353+31+103+322+205+228=1242 км Решение задачи лексикографическим переборомРасстояние, пройденное коммивояжером, составляет 1029 километров Решение задачи методом ветвей и границ Дана следующая матрица:{08FB837D-C827-4EFA-A057-4D05807E0F7C}N1234561∞1252281562052052125∞35331803213228353∞384433220415631384∞103352520580433103∞3226205321220352322∞ Найдем в каждой строке число, равное минимальному элементу{08FB837D-C827-4EFA-A057-4D05807E0F7C}N1234561─1252281562052052125─35331803213228353─384433220415631384─103352520580433103─3226205321220352322─ Вычтем из каждой строки число, равное минимальному элементу этой строки.{08FB837D-C827-4EFA-A057-4D05807E0F7C}N123456Минимальный элемент строки1─010331180180125294─3220492903138133─164213022041250353─72321315125035323─242806011615147117─205  Найдем в каждом столбце число, равное минимальному элементу{08FB837D-C827-4EFA-A057-4D05807E0F7C}N1234561─010331180180294─32204929038133─164213041250353─723215125035323─2426011615147117─ Далее вычтем из каждого столбца число, равное минимальному элементу этого столбца{08FB837D-C827-4EFA-A057-4D05807E0F7C}N1234561─08831131180294─3070029038133─164164041250338─233215125033823─24260116014768─Минимальныйэлементстолбца00150490 Для выделения претендентов на включение в множество дуг, по которым проводится ветвление, найдем степени в нулевых элементах этой матрицы (суммы минимумов по строке и столбцу).Наибольшая степень Ветвление проводим по дуге (3, 6): Таким образом получим маршрут коммивояжера: (3,6,5,4,2,1,3) или (Нефтекамск Туймазы Мелеуз Салават Стерлитамак Уфа Нефтекамск ). Коммивояжер пройдет расстояние:220+322+103+31+125+228=1029 (километров) I этап {EB344D84-9AFB-497E-A393-DC336BA19D2E}x1=6,5 x2=0 x3=3,5 min165    ограничения  33не менее3323не менее2313,5не менее12II этап В задачу были введены новые переменные и ее решение было выполнено симплексным методом Решение задачи было проверено с помощью пакета Microsoft Excel Так же была составлена программа на языке Pascal для решения задач симплексным методом III этап Решение целочисленных задач линейного программирования Рассмотрены метод Гомори и метод ветвей и границПрограмма на языке Pascal была переделана и для решения целочисленных задач IV этапРассмотрена одна из задач целочисленного программирования – транспортнаяНа складе «Дом-Сон» имеется 100 комплектов мебели, «Уют-плюс» - 250, «Идель» - 200 и на складе «DEFO» - 300 комплектов. Стоимость одного комплекта мебели со склада «Дом-Сон» в торговые центры «Три кита», «Комфорт мебель», «Башмебель-плюс», «Мебель холл» и «Белоречье» стоят соответственно – 10, 7, 4, 1, 4единиц стоимости. Со склада «Уют-плюс» в эти же центры – 2, 7, 10, 6, 11; «Идель» – 8, 5, 3, 2, 2, а со склада «DEFO» – 11, 8, 12, 16, 13 единиц. В первый магазин необходимо доставить 200 комплектов мебели, во второй – 200, в третий – 100, в четвертый – 100, и в пятый магазин 250 комплектов. Необходимо составить план так, чтобы затраты были минимальными.

Приложенные файлы

  • pptx fail25
    Размер файла: 653 kB Загрузок: 1