Библиотека Рефераты Курсовые Дипломы Поиск
Библиотека Рефераты Курсовые Дипломы Поиск
сделать стартовой добавить в избранное
Кефирный гриб на сайте www.za4et.net.ru

Компьютеры, Программирование Компьютеры, Программирование     Программное обеспечение Программное обеспечение

Основные принципы решения транспортной задачи

Коврик для запекания, силиконовый "Пекарь".
Коврик "Пекарь", сделанный из силикона, поможет Вам готовить вкусную и красивую выпечку. Благодаря материалу коврика, выпечка не
202 руб
Раздел: Коврики силиконовые для выпечки
Пакеты с замком "Extra зиплок" (гриппер), комплект 100 штук (150x200 мм).
Быстрозакрывающиеся пакеты с замком "зиплок" предназначены для упаковки мелких предметов, фотографий, медицинских препаратов и
148 руб
Раздел: Гермоупаковка
Браслет светоотражающий, самофиксирующийся, желтый.
Изготовлены из влагостойкого и грязестойкого материала, сохраняющего свои свойства в любых погодных условиях. Легкость крепления позволяет
66 руб
Раздел: Прочее

Реферат В данной работе изложены основные принципы решения транспортной задачи, в частности ѕ задача о коммивояжере. В работе использовано 5 источников, она содержит 29 страниц, 2 приложения, программу, написанную на языке Си. Содержание Реферат Содержание Введение 1.Постановка задачи о коммивояжере 2. Метод ветвей и границ 3. Использование верхних оценок 4. Решение с заданной точностью Заключение Список используемой литературы Приложение 1 Приложение 2 Введение Проблема оптимизации является в определенном смысле, пожалуй, самой острой проблемой современности. В любой сфере деятельности человек всегда ищет оптимальное решение. Существует класс задач, которые не удовлетворяют принципу оптимальности, и, следовательно, для этих задач метод динамического программирования непосредственно использован быть не может. Их решение требует развития специальных способов последовательного анализа вариантов. В частности, к такому классу задач относится задача о коммивояжере (бродячем торговце). Данная работа описывает нахождение оптимального решения задачи о коммивояжере, применяя метод ветвей и границ. 1.Постановка задачи о коммивояжере Рассмотрим задачу о коммивояжере (бродячем торговце). Предположим, что бродячий торговец должен, покинув город, которому мы присвоим номер 1 (рис. 1), объехать еще -1 городов и вернуться снова в город номер 1. В его распоряжении есть дороги, соединяющие эти города. Он должен выбрать свой маршрут - порядок посещения городов так, чтобы путь, который ему придется пройти, был как можно короче. Основное условие этой задачи состоит в том, что коммивояжер не имеет права возвращаться снова в тот город, в котором он однажды уже побывал. Это условие будем называть условием (a). Мы считаем, что расстояние между двумя городами - функция - определено. Разумеется, функция может означать не только расстояние, но, например, время или издержки в пути и т. д. Поэтому в общем случае , а функции естественно приписать значение Ґ. Длина l пути S определяется формулой: .(1) Сумма в выражении (1) распространена по всем индексам i и j, удовлетворяющим условию (a), т. е. условию, что каждый из индексов i и j входит в выражение (1) один и только один раз. Функция является, таким образом, аддитивной - она представима в виде суммы слагаемых, однако сама задача - задача отыскания минимума l - в силу ограничения (a) не является аддитивной и не удовлетворяет принципу оптимальности. Рис.1. Рассмотрим плоскость , х, где - дискретный аргумент, принимающий значения 0, 1, 2, . . . , , соответствующие этапам путешествия бродячего торговца. Значение =0 соответствует его начальному положению в городе номер 1, - 1 - переходу из города номер 1 в город, который он выбрал первым для посещения, и т. д., = означает последний этап его путешествия - возвращение в город номер 1. Аргумент х теперь также принимает дискретные значения 1, 2,. . . , (рис. 2). Соединим точку (0,1) с точками (1,1), (1,2), ., (,1 ) и длинам отрезков, соединяющих эти точки, припишем значения . Далее точки (1, s) - узлы, лежащие на первой вертикали, мы соединим со всеми узлами второй вертикали, длинам отрезков мы припишем значения и т.

д. Точки ( -1, s) соединим с точкой ( , 1). В результате мы построили некоторый граф, каждая ломаная которого, соединяющая точку (0,1) с точкой ( , 1), описывает путь коммивояжера. Нашу задачу мы можем теперь сформулировать следующим образом. Среди всех ломаных, принадлежащих этому графу и соединяющих точки (0,1) и ( ,1), и удовлетворяющих условию (a), найти ломаную кратчайшей длины. Условие (a) состоит теперь в том, что искомая ломаная пересекает (в узле) каждую из прямых х = i один и только один раз. Рис. 2. Рассмотрим узел Р, лежащий на третьей вертикали (см. рис. 2). Если бы условие (a) отсутствовало, то выбор траектории, которая соединяет точку Р с точкой ( , 1), не зависел бы от того пути, который привел нас в точку Р. В данном случае ситуация иная, и если два коммивояжера находятся в точке Р, но один из них пришел в это состояние, двигаясь вдоль траектории, проходящей через точку Q, а второй через точку R, то их состояния существенно отличаются друг от друга. Коммивояжер, который двигался по второй траектории, уже побывал в городах номер 2 и номер 5 и в будущем он уже не имеет права снова заезжать, в эти города. Что касается коммивояжера, который двигался вдоль первой траектории, то он побывал в городах номер 3 и номер 6; он не имеет права возвращаться в эти города, но зато он еще обязан посетить города номер 2 и номер 5 и т.д. Поскольку функция определена на конечном множестве точек, то и функция также определена на конечном множестве точек. Следовательно, задача определения минимума функции l сводится к перебору некоторого конечного множества значений этой функции, и проблема носит чисто вычислительный характер. Однако именно вычислительные трудности здесь огромны. Легко подсчитать, что число возможных вариантов (число значений функции l) равно ( -1)!. Таким образом, непосредственно перебрать и сравнить между собой все возможные пути, по которым может следовать бродячий торговец, для достаточно большого количества городов практически невозможно. Возникает проблема построения такого метода последовательного анализа вариантов, который выделял бы по возможности большое количество неперспективных вариантов и сводил задачу к перебору относительно небольшого количества &quo ;подозрительных&quo ; вариантов. 2. Метод ветвей и границОснова этого, ныне широко распространенного метода состоит в построении нижних оценок решения, которые затем используются для отбраковки неконкурентоспособных вариантов. Функция принимает конечное число значений , которые мы можем представить в виде таблицы (рис. 3). Предположим, что мы выбрали некоторый путь S. Его длина будет равна (2) причем сумма (2) распространена по i, j так, что каждый из индексов встречается в ней один и только один раз. Величины с двумя одинаковыми индексами мы приняли равными Ґ. Так как в каждый из вариантов s входит только один элемент из каждой строки и столбца, то мы можем проделать следующую операцию, которая здесь называется приведением матрицы. Обозначим через h, наименьший элемент из строки номера i и построим новую матрицу C элементами . Матрица C определяет новую задачу коммивояжера, которая, однако, в качестве оптимальной будет иметь ту же последовательность городов.

Между величинами и будет существовать, очевидно, следующая связь: Заметим, что в каждой из строк матрицы C будет теперь, по крайней мере, один нулевой элемент. Далее обозначим через наименьший элемент матрицы C, лежащий в столбце номера j, и построим новую матрицу С с элементами Величины h и называются константами приведения. Оптимальная последовательность городов для задачи коммивояжера с матрицей С будет, очевидно, такой же, как и для исходной задачи, а длины пути для варианта номера s в обеих задачах будут связаны между собой равенством ,(3) Где ,(4) т.е. равна сумме констант приведения. Обозначим через l решение задачи коммивояжера, т. е. , где минимум берется по всем вариантам s, удовлетворяющим условию (a). Тогда величина будет простейшей нижней оценкой решения: (5) Будем рассматривать теперь задачу коммивояжера с матрицей С, которую мы будем называть приведенной матрицей. Рассмотрим путь, содержащий непосредственный переход из города номера i в город номера j , тогда для пути s , содержащего этот переход, мы будем иметь, очевидно, следующую нижнюю оценку: Следовательно, для тех переходов, для которых , мы будем иметь снова оценку (5). Естественно ожидать, что кратчайший путь содержит один из таких переходов - примем это соображение в качестве рабочей гипотезы. Рассмотрим один из переходов, для которого , и обозначим через множество всех тех путей, которые не содержат перехода из i в j. Так как из города i мы должны куда-то выйти, то множество содержит один из переходов i ® k, где k№i; так как в город номера j мы должны прийти, то множество содержит переход т® i, где т№ i. Следовательно, некоторый путь , из множества , содержащий переходы i ® k и т® i , будет иметь следующую нижнюю оценку: . Обозначим через Тогда очевидно, что для любого множества путей мы будем иметь оценку (6) Мы предполагаем исключить некоторое множество вариантов , поэтому мы заинтересованы выбрать такой переход i®j, для которого оценка (6) была бы самой высокой. Другими словами, среди нулевых элементов матрицы С выберем тот, для которого максимально. Это число обозначим через . Таким образом, все множество возможных вариантов мы разбили на два множества I и I . Для путей из множества I, мы имеем сценку (5). Для путей из множества Iоценка будет следующей: .(7) Рассмотрим теперь множество I, и матрицу С. Так как все пути, принадлежащие этому множеству, содержат переход i®j, то для его исследования нам достаточно рассмотреть задачу коммивояжера, в которой города номеров i и j совпадают. Размерность этой задачи будет уже равна - 1, а ее матрица получится из матрицы С вычеркиванием столбца номера j и строки номера i. Поскольку переход i®j невозможен, то элемент принимаем равным бесконечности. Рассмотрим случай =3 (рис. 4, а) и предположим, что мы рассматриваем тот вариант, который содержит переход 3®2. Тогда задача коммивояжера после вычеркивания третьей строки и второго столбца вырождается в тривиальную. Ее матрица изображена на рис. 4, б). В этом случае мы имеем единственный путь, и его длина будет, очевидно, равна сумме Итак, если в результате вычеркивания строки номера i и столбца номера j мы получим матрицу второго порядка, то задачу можно считать решенной.

Это было для нас большим облегчением, так как даже в самые тяжелые периоды войны передвижение войск и грузов в тыловых районах проходило беспрепятственно. Русская авиация использовалась в основном для решения тактических задач, и начиная с лета 1943 года самолеты русских висели с утра до вечера над полем боя. Хорошо бронированные штурмовики русских атаковали главным образом на бреющем полете, и летчики-штурмовики проявляли при этом большую смелость и мужество. Ночные бомбардировщики действовали, как правило, в одиночку, стремясь, видимо, прежде всего помешать ночному отдыху наших частей. Организация взаимодействия между авиацией и наземными войсками непрерывно улучшалась; в то же время качественное превосходство немецкой авиации постепенно исчезало. Но в тактическом отношении русские всегда уступали нам, а их летчики не могли сравниться с нашими пилотами. Россия была первой страной, где начали широко экспериментировать в области использования парашютных и воздушно-посадочных войск. «Осо-авиахим» подготовил до войны многие тысячи парашютистов

1. Оценка безотказной работы технической аппаратуры (задачи)

2. Расчетные работы по электротехнике (задача №5)

3. Программное обеспечение системы принятия решений адаптивного робота

4. Задачи и виды электронной коммерции. Алгоритм работы платежной системы Rapida

5. Обеспечение надежности инвестиционного решения

6. Программа, методические указания, задания для выполнения контрольной работы и контрольные вопросы для студентов з/о специальностей: 060500 «Бухучет, анализ и аудит», 060400 «Финансы и кредит»
7. Решение транспортной задачи методом потенциалов
8. Решение задач транспортного типа методом потенциалов

9. Постановка и решение транспортной параметрической задачи

10. Решение военно-логистических задач по выбору оптимального маршрута для военно-транспортных средств

11. Решение транспортной задачи с правильным балансом

12. Методы решения транспортных задач

13. Принципы разработки алгоритмов и программ для решения прикладных задач

14. Решение задач моделирования и оптимизации с помощью программ Excel и Mathcad

15. Решение задачи с помощью программ Mathcad и Matlab

16. Решение задачи с помощью программ Mathcad и Matlab

Увлекательная настольная игра "Этажики", новая версия.
На игровом поле две карты — карта с этажом, на котором находятся игроки, и карта с воздушным шаром. Шар перемещает всех на определённое
632 руб
Раздел: Карточные игры
Магнитный театр "Колобок".
Увлекательное театральное представление с любимыми героями русской народной сказки «Колобок» и вашим ребенком в роли главного режиссера.
308 руб
Раздел: Магнитный театр
Компрессор для подкачки шин С-12.
Автокомпрессор — это электрическое устройство, предназначенное для накачивания шин на колесах. В отличие от механического насоса, при
732 руб
Раздел: Насосы, компрессоры автомобильные

17. Решение задачи с помощью программ Mathcad и Matlab

18. Антивирусные программы. Матричный принцип печати. Решение задач на ЭВМ

19. Решение задач по курсу "семейное право"

20. Задача про транспортную систему. Подбор вариантов проезда с учетом кол-ва пересадо, длительности, видов транспорта (самолет, авто, поезд, водн.) (и класса)

21. Формирование структуры электронного учебника и решение задач на ней

22. Транспортная задача
23. Графы. решение практических задач с использованием графов (С++)
24. Лабораторная работа №5 по "Основам теории систем" (Транспортные задачи линейного программирования)

25. Лабораторная работа №6 по "Основам теории систем" (Решение задачи о ранце методом ветвей и границ)

26. Решение смешанной задачи для уравнения гиперболического типа методом сеток

27. Решение оптимизационной задачи линейного программирования

28. Решение задач линейного программирования

29. Решение задачи линейного программирования

30. Решение задач линейной оптимизации симплекс – методом

31. Метод Алексея Юрьевича Виноградова для решения краевых задач

32. Решение задач на построение сечений в многогранниках методом следов

Сушилка для белья Vileda "Мультифлекс".
Компактная (занимает мало места, удобно размещать даже в небольшом помещении). Очень устойчивая. С защитным покрытием от воздействий
5739 руб
Раздел: Сушилки напольные
Мягкий пол "Ассорти", универсальный, 60x60 см, 1.44 кв.м.
Размер 1 листа: 60x60 см. Площадь4 листов: 1.44 кв.м. Состав: 1 красный лист, 1 желтый лист, 1 зеленый лист, 1 синий лист.
1080 руб
Раздел: Прочие
Дорожка массажная "Морской Берег", с "камнями".
Массажная дорожка с камнями «Морской берег» является отличным средством профилактики плоскостопия, рефлексотерапии и расслабления.
1268 руб
Раздел: Коврики

33. Несколько способов решения одной геометрической задачи

34. Возможности радиолокационного тренажера NMS-90 и его использование для решения задач расхождения судов в условиях ограниченной видимости

35. Решение обратной задачи вихретокового контроля

36. Маркетинг: решение исследовательских задач

37. Овладение методикой построения экономико-математических моделей, решение конкретных задач по стратегическому планированию и прогнозированию

38. Решение творческих задач методом блочных альтернативных сетей: объектно-ориентированные представления
39. Создание программных продуктов для решения задач
40. Приложения определенного интеграла к решению некоторых задач механики и физики

41. К решению нелинейных вариационных задач

42. Методы решения некорректно поставленных задач

43. Решение задач линейной оптимизации симплекс – методом

44. Решение задач с помощью ортогонального проектирования

45. Решения смешанной задачи для уравнения гиперболического типа методом сеток

46. Приложения определенного интеграла к решению некоторых задач механики и физики

47. Применение движений к решению задач

48. О методике решения задач на относительность движения при изучении основ кинематики в 9 классе общеобразовательной школы

Карандаши цветные "Kores", 24 цвета, с точилкой.
Двусторонние цветные карандаши имеют насыщенные цвета. Трехгранная форма корпуса снижает усталость и придает дополнительный комфорт.
311 руб
Раздел: 13-24 цвета
Кружка фарфоровая "FIFA 2018. Забивака. Триумф!", 480 мл.
Объем: 480 мл. Материал: фарфор.
401 руб
Раздел: Кружки, посуда
Чайник со свистком из нержавеющей стали "Mayer & Boch", 2,5 л.
Чайник со свистком металлический. Материал: нержавеющая сталь, бакелит, литое дно. Объем: 2,5 литра. Чайник выполнен из высококачественной
400 руб
Раздел: Чайники из нержавеющей стали

49. Построения коллектива с акцентом на решение задач или на поддержание отношений в нем

50. Пример решения задачи по механике

51. Эвристические методы решения творческих задач

52. Влияние использования схем, чертежей, иллюстраций на формирование ЗУН при обучении младших школьников решению задач на движение

53. Пути повышения эффективности обучения решению задач

54. Структура и динамика процессов решения задач
55. Развитие профессионального оперативного мышления будущего учителя в ходе решения психолого-педагогических задач
56. От решения задач к механизмам трансляции деятельности

57. Нечеткая логика при решении криминологических задач

58. Дифференциальные уравнения движения точки. Решение задач динамики точки

59. Решение обратных задач теплопроводности для элементов конструкций простой геометрическо формы

60. Решение задач по химии

61. Задачи по экономике с решениями

62. Задачи по экономике с решениями

63. Применение новейших экономико-математических методов для решения задач

64. Решение многокритериальной задачи линейного програмирования

Подарочная расчёска для волос "Полина".
Стильная детская расчёска дарит радость и комфорт. Этот практичный аксессуар по достоинству оценят как маленькие модницы, так юные
372 руб
Раздел: Расчески, щетки для волос
Мягкий пол, универсальный, 60x60 см, бежево-коричневый.
Мягкое модульное универсальное покрытие, предназначенное для дома, детских игровых зон, торговых центров, спортивных залов и площадок
1043 руб
Раздел: Прочие
Набор разделочных досок на подставке.
Материал: полипропилен. Размер: 335х240х78 мм. В наборе: 3 разделочные доски. В ассортименте без возможности выбора.
453 руб
Раздел: Пластиковые

65. Приемы решения научных задач в русловедении

66. Опыт применения сейсморазведки ОГТ для решения инженерно-геологических задач

67. Применение спектральной сейсморазведки для решения задач инженерной геологии

68. Применение политического дискурс-анализа в решении идеологических задач (На примере медиатизации политических текстов)

69. Решение инженерно-технических задач в среде Mathcad

70. Методы решения задач
71. Нахождение опорного плана транспортной задачи
72. Решение экономических задач с помощью VBA

73. Использование языка программирования Visual Basic для решения математических задач

74. Построение математических моделей при решении задач оптимизации

75. Транспортная задача и задача об использовании сырья

76. Основные подходы к оценке стоимости бизнеса и перспективы их применения к решению задач управления инновационными предприятиями

77. Решение задач по дисциплине "Страхование"

78. Решение задач по управленческому учету

79. Использование результатов изучения психологических особенностей обвиняемого для решения уголовно-правовых и уголовно-процессуальных задач расследования

80. Примеры задач и их решение по уголовному процессу

Планшет для пастелей "Бабочка" А3, 20 листов.
Планшет для пастелей "Бабочка" на жесткой подложке - незаменимый помощник художника. Благодаря жесткому основанию, бумага на
320 руб
Раздел: Папки для акварелей, рисования
Шкатулка музыкальная "Сидящая балерина".
Музыкальная шкатулка для украшений с классической музыкой. Когда шкатулка открыта - звучит музыка и фигурка кружится. Необычное зеркальце,
1511 руб
Раздел: Шкатулки музыкальные
Москитная сетка "Папитто" универсальная на молниях, черная.
Москитная сетка подходит для коляски с перекидной ручкой, для прогулочной коляски, у которой ручка сзади, а также для коляски типа
424 руб
Раздел: Дождевики, чехлы для колясок

81. Примеры решения задач по уголовному процессу

82. Алгоритмы численного решения задач

83. Использование информатики для решения экономических задач

84. Метод программирования и схем ветвей в процессах решения задач дискретной оптимизации

85. Практикум по решению линейных задач математического программирования

86. Примеры решения задач по программированию
87. Реализация на ЭВМ решения задачи оптимальной политики замены оборудования
88. Решение задач линейного программирования

89. Решение задач линейного программирования симплекс методом

90. Решение задач нелинейного программирования

91. Решение задач с помощью современых компьютерных технологий

92. Решение задачи линейного программирования графическим методом

93. Решение задачи с помощью математической модели и средств MS Excel

94. Решение математических задач средствами Excel

95. Решение прикладных задач методом дихотомии

96. Решение финансовых задач при помощи Microsoft Excel

Набор мебели для спальни "Коллекция".
Очень стильный и яркий набор кукольной мебели "Спальня" станет прекрасным украшением кукольного домика. Миниатюрная кровать
579 руб
Раздел: Спальни, кроватки
Накладка на унитаз "Disney. Frozen" (белая).
Унитазная накладка подходит всем стандартным туалетам. Благодаря прорезиненным краям накладка не скользит, что гарантирует безопасность
406 руб
Раздел: Сиденья
Магнит для досок Hebel Maul 6176199, круглый, 20 штук.
Цвет: разные цвета. Диаметр магнита: 20 мм. Форма магнита: круглый. Количество в упаковке: 20 штук.
595 руб
Раздел: Магниты канцелярские

97. Решение экономических и бухгалтерских задач с использованием инструментария Visual Basic For Application

98. Симплекс метод решения задачи линейного программирования

99. Экспертная система для решения задачи о коммивояжере

100. Алгоритм решения задач


Поиск Рефератов на сайте za4eti.ru Вы студент, и у Вас нет времени на выполнение письменных работ (рефератов, курсовых и дипломов)? Мы сможем Вам в этом помочь. Возможно, Вам подойдет что-то из ПЕРЕЧНЯ ПРЕДМЕТОВ И ДИСЦИПЛИН, ПО КОТОРЫМ ВЫПОЛНЯЮТСЯ РЕФЕРАТЫ, КУРСОВЫЕ И ДИПЛОМНЫЕ РАБОТЫ. 
Вы можете поискать нужную Вам работу в КОЛЛЕКЦИИ ГОТОВЫХ РЕФЕРАТОВ, КУРСОВЫХ И ДИПЛОМНЫХ РАБОТ, выполненных преподавателями московских ВУЗов за период более чем 10-летней работы. Эти работы Вы можете бесплатно СКАЧАТЬ.