Презентация на тему Тема дипломной работы –Оптимизация маршрутов перевозокв компании ООО Массив

В" занимается производством и продажей мебели.  Предприятие является
серийным производителем в Республике

Башкортостан стульев и столов из массива
и шпона березы . Предлагает широкий
ассортимент продукции для комплектации
помещений различного назначения.
Компания OOО «Массив» имеет несколько собственных торговых точек, а так же продукцию компании можно приобрести у партнеров фирмы.

ООО «Массив» на базе формирования оптимальных маршрутов перевозки мебели.
Задачи:

средства, цель которого состоит в том, чтобы посетить все

заданные объекты за кратчайший срок (с наименьшими затратами). Данную задачу можно представить как задачу о коммивояжере

Постановка задачи
Имеется N городов, которые должен обойти коммивояжер с минимальными затратами. При этом на его маршрут накладывается два ограничения:

маршрут должен быть замкнутым, то есть коммивояжер должен вернуться в тот город, из которого он начал движение;
в каждом из городов коммивояжер должен побывать точно один раз, то есть надо обязательно обойти все города, при этом, не побывав ни в одном городе дважды.

- матрица расстояний, где Di j - расстояние из

i-го пункта в j-й. Найти: Xi j - матрицу переходов с компонентами: Xi j = 1, если коммивояжер совершает переход из i-го пункта в j-й, Xi j = 0, если не совершает перехода,
где i, j = 1..N и ij. Функция цели - суммарная протяженность маршрута F, которую необходимо минимизировать, запишется в следующем виде: Ограничения: Условия прибытия в каждый пункт и выхода из каждого пункта только по одному разу выражаются следующими равенствами:
, j = 1..N , i = 1..N Для обеспечения непрерывности маршрута вводятся дополнительно N переменных Ui≥0 (i = 1..N ) и N2 дополнительных ограничений: Ui - Uj + N  Xi j  N-1, i, j = 1..N, i  j.

границ
Жадные алгоритмы
Метод минимального
остовного дерева
Алгоритм «ближайшего
соседа»
Алгоритм «k-ближайших
соседей»
Алгоритм «муравьиной
колонии»
Генетические

алгоритмы

Алгоритм Прима

Алгоритм Борувки

Алгоритм ветвей и границ основан на следующих построениях:

1.

Вычисление оценки. Пусть G' G, тогда φ(G') называется нижней
оценкой, если для любого х є G' выполняется неравенство f(x) ≥ φ(G').
2.Ветвление (разбиение множества G на подмножества). Положим
и разобьем множество на r1
непересекающихся подмножеств

Для K-го множества разбиение будет

Данную процедуру разбиения можно представить в виде дерева

Поэтому, разбивая в процессе ветвления подмножество

G’ G на непересекающиеся подмножества
будем предполагать, что φ(G1’) ≥ φ (G’), причем хотя бы для некоторых номеров выполняется φ( ) ≥ φ (G’).

4.Вычисление планов (допустимых решений). Если на шаге ветвления
с номером k известен план , на шаге с номером (k + 1) — план и если
, то план забывается и вместо него сохраняется план
Наилучшее из полученных допустимых решений принято называть рекордом.

5.Признак оптимальности. Пусть G = . Тогда план является
оптимальным, т.е. , если выполняется условие


Если признак оптимальности выполнен, то решение закончено.

программы
Программный комплекс
«МАРШРУТ» (МГТУ им. Баумана)
Программа нахождения
оптимального маршрута

перевозок (УГАТУ, каф. ВМК)

данные

1-Иглино Ленина 2а-Чишмы Революционная 19-Уфа Менделеева 21-Уфа Индустриальное шоссе

4а-Уфа Кольцевая 65/1-Уфа Войкова1

Ленина 18а-Янаул Победы 88а-Янаул Советская2-Янаул Советская6-Бирск 8 марта 1г-Бирск

Мира 1г-Бирск Коммунистическая 172-Нефтекамск Карла Маркса 9-Нефтекамск Комсомольский проспект 28-Нефтекамск Победы4-Уфа Войкова 1

Жуковского 1а-Ишимбай Губкина 31-Ишимбай Левый берег 4-Стерлитамак Ивлева 12-Стерлитамак

Коммунистическая 51-Стерлитамак Лазурная 13-Стерлитамак Глинки 11-Стерлитамак Гоголя 111-Стерлитамак Ленина 2б-Салават Октябрьская 56/9-Салават Уфимская 8б-Салават Ленина 20/18-Салават Салавата Юлаева 31-Кумертау Станционная 13/1-Уфа Войкова 1