Содержание

 
 

 

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

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

    Транспортный  комплекс выполняет почти 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

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