Задача коммивояжера
Категория реферата: Рефераты по математике
Теги реферата: понятие культуры, отчет о прохождении практики
Добавил(а) на сайт: Жигалов.
Предыдущая страница реферата | 1 2 3 4 5 6 7 | Следующая страница реферата
4. Пробить j-тое отверстие, затратив время tj.
Конкретный вид функций t(x), t(y), t(z) зависит от механических свойств пресса и достаточно громоздок. Явно выписывать эти функции нет необходимости
Действия 1-3 (переналадка с i-того отверстия j-тое) происходит одновременно, и пробивка происходит немедленно после завершения самого длительного из этих действий. Поэтому
С[i,j] = max(t(x), t(y), t(z))
Теперь, как и в предыдущем случае, задача составления оптимальной программы для дыропробивного пресса сводится к ЗК (здесь - симметричной).
Выводы
1. Изучены эвристический, приближенный и точный алгоритмы решения ЗК.
Точные алгоритмы решения ЗК – это полный перебор или усовершенствованный перебор. Оба они, особенно первый, не эффективны при большом числе вершин графа.
2. Предложен собственный эффективный метод решения ЗК на основе построения выпуклого многоугольника и включения в него центральных вершин (городов).
3. Проведён анализ наиболее рациональных методов решения ЗК и определены области их эффективного действия: для малого числа вершин можно использовать точный метод лексического перебора; для большого числа вершин рациональнее применять метод ветвей и границ или метод автора работы (Анищенко Сергея Александровича).
4. Изучены практические применения ЗК и задачи с переналадками, сводимые к ЗК.
5. Приведены тексты программ, позволяющие решить ЗК различными методами.
Литература
1. О. Оре Графы и их применение. Пер. с англ. под ред. И.М. Яглома. -
М., «Мир», 1965, 174 с.
2. В. П. Сигорский. Математический аппарат инженера. - К., «Техніка»,
1975, 768 с.
3. Ю. Н. Кузнецов, В. И. Кузубов, А. Б. Волощенко. Математическое программирование: учебное пособие. 2-е изд. перераб. и доп. - М.;
Высшая школа, 1980, 300 с., ил.
4. Е. В. Маркова, А. Н. Лисенков. Комбинаторные планы в задачах многофакторного эксперимента. – М., Наука, 1979, 345 с.
5. Е. П. Липатов. Теория графов и её применения. - М., Знание, 1986, 32 с.
6. В. М. Бондарев, В. И. Рублинецкий, Е. Г. Качко. Основы программирования. – Харьков, Фолио; Ростов на Дону, Феникс, 1998, 368 с.
7. Ф. А. Новиков Дискретная математика для программистов. - Санкт-
Петербург, Питер, 2001, 304 с., ил.
8. Приложения
Рекомендуем скачать другие рефераты по теме: конспекты по литературе, шпаргалки бесплатно.
Предыдущая страница реферата | 1 2 3 4 5 6 7 | Следующая страница реферата