Содержание

 
 

 

     Транспорт удовлетворяет одну из важнейших  потребностей человека- потребность в перемещении. Однако практически ни один вид транспорта (кроме автомобильного) не может обеспечить доставку «от двери до двери». Такое перемещение возможно только в четком взаимодействии отдельных частей транспортного комплекса.

    Транспортный  комплекс РФ является элементом единой транспортной системы, государственное управление которым осуществляет Министерство транспорта  России. В транспортный комплекс входят зарегистрированные юридические лица и индивидуальные предприниматели, осуществляющие на воздушном, железнодорожном, автомобильном, морском, внутреннем водном, городском пассажирском и промышленном транспорте перевозочную и транспортно-экспедиторскую деятельность, а также работы, связанные с обслуживанием путей сообщения, проведением научных исследований и подготовкой кадров, производством транспортных средств и технологического оборудования.

    Транспортный  комплекс выполняет почти 97% перевозок  пассажиров и более 60% общего пассажирооборота, более 83% отправлений всех грузов и 11,5% грузооборота.

    В то же время, несмотря на определенные практические достижения, в транспортном комплексе имеется много нерешенных проблем. Это:

• недостаточность развития транспортных ресурсов;
• ухудшение состояния технических средств транспорта;
• отсутствие единых технологий;
• недостаток грамотных специалистов в области управления ЕТС.

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

    Целью курсовой работы является выбор маршрута следования коммивояжера с наименьшей продолжительностью по времени при использовании различных видов транспорта .

    Задание на курсовую работу

    Имеется шесть населенных пунктов, матрица транспортных расстояний между которыми представлена ниже

 

    Каждый  пункт имеет путь сообщения со всеми остальными. Коммивояжер, выезжая из одного пункта, должен побывать в других по одному разу и вернуться в исходный пункт.

1. Используя метод ветвей и границ , определить в каком порядке следует объезжать пункты, чтобы расстояние было минимальным.
2. Выбрать экономически целесообразный способ поездки коммивояжера по рассчитанному маршруту, сравнив технико-экономические характеристики железнодорожного, воздушного и автомобильного транспорта.
3. Рассчитать и сравнить :

• Продолжительность (время) следования коммивояжера по маршруту при использовании различных видов транспорта;

• Материальные затраты на поездку
• Стоимость пассажиро-часов пребывания коммивояжера в пути;
• Используя метод построения совмещенных графиков работы различных видов транспорта, показать графически преимущество выбранного варианта

Определение порядка объезда  городов

Осуществим  приведение матрицы С по строкам  и столбцам. Приведенную матрицу  представим в виде таблицы, приводящие константы по строкам и столбцам запишем справа и внизу матрицы

            

      

= 
 

Определим оценку множества  , вычислив сумму приводящих констант:

V( )= =2414+188= 2602

Выберем пары городов-претендентов на ветвление, т.е.(i,j), для которых =0

=0, =0, =0, =0, =0, =0, =0

Для выделенных претендентов подсчитаем оценки по формуле:

P(ij)=

P(1,6)=102+0=102

P(2,4)=0+292=292

P(2,5)=0+49=49

P(3,6)=87+0=87

P(4,2) = 49+285=334

P(5,3)=283+61=344

P(6,1)=126+87=213

Для ветвления выберем пару претендентов с максимальной оценкой P(ij),т.е. пару P(5,3)=344 
 
 

Произведем  ветвление: , где =(5,3), = .

Вычислим  оценку для  :

V( )=V( )+P(5,3)=2602+344=2946

Построим  матрицу  , для этого вычеркнем в матрице _{пятую строку и третий столбец. Чтобы избежать образования замкнутых подциклов,  запретим переезд из города 3 в город 5 и выполним процесс приведения.} 

 

= 
 

Определим оценку для подмножества

_{Так как V ‹ V , то на следующем шаге разбиваем подмножество}

_{Выберем пары городов –претендентов  на ветвление:}

=0, =0, =0, =0, =0, =0

Для выделенных претендентов подсчитаем оценки:

P(1,6)=493+0=493

P(2,4)=0+689=689

P(2,5)=0+49=49

P(3,6)=87+0=87

P(4,2)=49+387=436

P(6,1)=529+87=616

_{Для ветвления выберем  пару  претендентов с максимальной оценкой  P(2,4)=689}

_{Произведем  ветвление: , где и .}

_{Вычислим оценку для :}

V( )=V( )+P(2,4)=2602+689=3291

Построим  матрицу  , вычеркнув вторую строку и четвертый столбец в матрице и выполним процесс приведения, запретив переезд из города 4 в город 2. 

                  

=  

Вычислим  оценку для  :

V( )=V( )+ =2602+436= 3038

Так как V( )‹V( ), то на следующем шаге производим ветвление подмножества _.

_{Выберем пары претендентов на ветвление:}

=0, =0, =0, =0, =0

Определим для выбранных претендентов оценки:

P(1,6)=106+0=106

P(3,2)=0+196=196

P(3,6)=0+0=0

P(4,5)=561+409=970

P(6,1)=196+87=283

_{Для ветвления выберем  пару  претендентов с максимальной оценкой  P(4,5)=970}

Произведем  ветвление:

_{,где  и}

Вычислим  оценку для :

V( )=V( )+P(4,5)=3038+970=4008

Построим  матрицу  , вычеркнув четвертую строку и пятый столбец в матрице  

₌ 

_{Поскольку полученная матрица  является приведенной, оценка для подмножества равна оценке для подмножества :}V( )=V( )=3038

А так  как V( )‹V( ), то для ветвления на очередном шаге выберем подмножество V( ). 

Выберем пары городов-претендентов на ветвление:

=0, =0, =0, =0

Для выделенных претендентов подсчитаем оценки:

P(1,6)=106+0=106

P(3,2)=0+106=106

P(3,6)=0+0=0

P(6,1)=196+87=283

_{Для ветвления выберем  пару  претендентов с максимальной оценкой P(6,1)=283}

Произведем  ветвление:

_{,где  и}

Вычислим  оценку для  :

V( )=V( )+P(6,1)=3038+283=3321

Построим  матрицу  , вычеркнув шестую строку и первый столбец в матрице и выполним процесс приведения, запретив переезд из города 1 в город 6

.   

₌ 

Вычислим  оценку для  :

V( )=V( )+ =3038+106= 3144

Полученная  матрица имеет размерность 2х2 и  допускает включение в матрицу  только двух пар городов (1,2) и (3,6)

В результате получаем цикл _,

_{отвечающий  подмножеству  , длина которого равна 3144.}

_{Сравним длину этого цикла с полученными ранее оценками для неветвленных подмножеств. Последовательность объезда городов можно представить следующим образом:5→3→6→1→2→4→5} 

Подмножество  V( )=2946‹V( )=3144. Это подмножество может привести к образованию цикла с меньшей оценкой, поэтому оно должно быть подвергнуто анализу. Для этого восстановим исходную матрицу и запретим проезд из города 5 в город 3, одновременно выполнив приведение.

₌ 
 
 
 

Определим оценку множества  , вычислив сумму приводящих констант:

_{=2602+283+61=2946}

Выберем пары городов-претендентов на ветвление, т.е.(i,j), для которых =0

=0, =0, =0, =0, =0, =0, =0, =0

Для выделенных претендентов подсчитаем оценки

P(1,6)=41+0=41

P(2,3)=0+65=65

P(2,4)=0+9=9

P(2,5)=0+49=49

P(3,6)=87+0=87

P(4,2)=49+2=51

P(5,6)=2+0=2

P(6,1)=65+2=67

_{Для ветвления выберем пару  претендентов с максимальной оценкой P(3,6)=87} 

Произведем  ветвление:

, где  =(3,6), = .

Вычислим  оценку для

V( )=V( )+P(3,6)=2946+87=3033

Построим  матрицу  , для этого вычеркнем в матрице _{третью строку и шестой столбец. Чтобы избежать образования замкнутых подциклов,  запретим переезд из города 6 в город 3 и выполним процесс приведения}

 

₌  
 

Вычислим оценку для :

V( )=V( )+ =2946+43=2989

А так  как V( )‹V( ), то для ветвления на очередном шаге выберем подмножество V( ).

Выберем пары городов-претендентов на ветвление

=0, =0, =0, =0, =0, =0, =0 =0

Р(1,3)=368+0=368

Р(2,3)=0+0=0

Р(2,4)=0+7=7

P(2,5)=0+49=49

P(4,2)=49+0=49

P(5,1)=0+0=0

P(5,2)=0+0=0

P(6,1)=529+0=529

_{Для ветвления выберем  пару  претендентов с максимальной оценкой  P(6,1)=529}

, где _{и .}

Вычислим  оценку для

V( )=V( )+P(6,1)=2989+529=3518

Построим матрицу , для этого вычеркнем в матрице _{шестую строку и первый столбец и выполним процесс приведения}

 

₌ 

_{Поскольку полученная матрица является приведенной, оценка для подмножества равна оценке для подмножества = 2989}

А так  как V( )‹V( ), то для ветвления на очередном шаге выберем подмножество V( ).

Выберем пары городов-претендентов на ветвление

=0, =0, =0, =0, =0, =0

P(1,3)=368+0=368

P(2,3)=0+0=0

P(2,4)=0+7=7

P(2,5)=0+49=49

P(4.2)=49+0=49

P(5,2)=7+0=7

Расчеты привели нас к замкнутому подциклу _{3→6→1→3}

_{Запретим  проезд из города 1 в  город 3 и постоим  матрицу  заново,выполнив  процесс приведения}

 

₌ 

V( )=V( )+ =2989+368=3357

Так как V( )‹V( ), то для ветвления на очередном шаге выберем подмножество V( ).

Выберем пары городов-претендентов на ветвление

=0, =0, =0, =0, =0, =0

P(1,5)=84+0=84

P(2,3)=0+332=332

P(2,4)=0+7=7

P(2,5)=0+0=0

P(4.2)=49+0=49

P(5,2)=7+0=7

_{Для ветвления выберем  пару  претендентов с максимальной оценкой P(2,3)=332}

, где _и

Вычислим  оценку для

V( )=V( )+P(2,3)=3357+332=3689

Построим  матрицу  , для этого вычеркнем в матрице _{вторую строку и третий столбец и выполним процесс приведения} 

 

₌  

V( )=V( )+ =3357+7=3364

Так как V( )‹V( ), то для ветвления на очередном шаге выберем подмножество V( ).

Выберем пары городов-претендентов на ветвление

=0, =0, =0 , =0

P(1,5)=54+0=84

P(4,2)=49+0=49

P(5,2)=0+0=0

P(5,4)=0+546=546

_{Для ветвления выберем пару  претендентов с максимальной оценкой P(5,4)=546}

, где _и

Вычислим  оценку для

V( )=V( )+P(5,4)=3364+546=3910

Построим  матрицу  , для этого вычеркнем в матрице _{пятую строку и четвертый столбец и запретим проезд из города 4 в город 5, выполним процесс приведения}