Лингвистическое программное обечениеп

  • 12 сент. 2011 г.
  • 4126 Слова
Министерство образования и науки Российской Федерации
Федеральное агентство по образованию
Государственное образовательное учреждение
ОРЕНБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
Аэрокосмический институт
Кафедра систем автоматизации производства

КУРСОВАЯ РАБОТА

по дисциплине
«Лингвистическое и программное обеспечение САПР »
«ПО САПР: транспортная задача (решение методами: ветвей играниц, полного перебора)»

ОГУ 230104.65.5008.09ПЗ

Руководитель работы:
_________________Русяев А.С.
«___»_________________2010г.
Исполнитель:
Студент гр. 07 САП_______________Канафеев Э. Р.
«___»_________________2010г.

Оренбург 2010
АННОТАЦИЯ

Пояснительная записка содержит 26 страниц, в том числе 8 источников и 1 приложение. К пояснительной записке прилагается диск с выполненной программой, программным кодом и пояснительной запиской вэлектронном виде.
Задача о коммивояжере состоит в том, чтобы объехать заданные города по одному разу в таком порядке, чтобы пройденное расстояние было минимальным.
Такая задача актуальна во многих областях, таких как автомобильные, судовые и железнодорожные перевозки, расчет авиационных линий, конвейерное производство.

Содержание

1 Введение……………………………………………………………………..52 Техническое задание .....................................................................................6
3 Описание программы ....................................................................................7
4 Теоретическая часть………...........................................................................8
5 Практическаячасть…..................................................................................15
Список использованных источников ............................................................21
Приложение А .................................................................................................22

Введение

Задача коммивояжера классическая задача анализа данных иматематического программирования, которая заключается в определении оптимального маршрута для коммивояжера, который должен объехать все порученные ему города и вернуться назад за минимальное время или с наименьшими затратами на проезд.
Задача формулируется следующим образом. Имеется граф, узлы которого представляют собой точки (города), которые должен посетить коммивояжер. Ребра графа образуют пути,связывающего два или более узла. Требуется найти путь, который минимизирует (или максимизирует) некоторый критерий оптимальности (время, стоимость переезда, совокупный критерий и т.д.). При этом на допустимые маршруты могут быть наложены некоторые ограничения, например, запрет возвращения к уже пройденному узлу.
Задача о коммивояжере считается одной из самых сложных в математическом программировании, посколькувычислительные затраты нелинейно возрастают с ростом числа узлов, которые должны быть включены в маршрут. Например, для 4-х точек число возможных маршрутов всего 6. Однако для 11 точек оно составит уже более 3,5 млн., а для n точек количество маршрутов равно (n – 1)!. Таким образом, задача, заключается в поиске упрощенных методов решения, позволяющих отказаться от последовательного перебора всехвозможных маршрутов.

1 Техническое задание

1. “Задача коммивояжера” – Коммивояжер должен выйти из первого города, посетить по разу в неизвестном порядке города 1,2,3..n и вернуться в первый город.
2. Основания для разработки:
Выполнение курсовой работы по курсу «Лингвистическое и программное обеспечение САПР».
3. Назначение...
tracking img