Поиск верхних и нижних границ для оптимального значения на подобласти допустимых решений. Методы и проблемы решения задач нелинейного программирования. Написание и отладка программы. Создание программы для решения задачи "коммивояжёра" прямым алгоритмом.
Аннотация к работе
Обычно задачу о торговце решают с помощью прямого алгоритма, т.к. для человека расчет такой задачи занимает много времени, и создаются программы для облегчения вычислений. В условиях данной задачи сказано, что коммивояжер должен обойти 7 городов, чтобы найти оптимальный маршрут, расстояние которого будет самым коротким. При этом на его маршрут накладывается два ограничения: - маршрут должен быть замкнутым, то есть коммивояжер должен вернуться в тот город, из которого он начал движение; в каждом из городов коммивояжер должен побывать точно один раз, то есть надо обязательно обойти все города, при этом не побывав ни в одном городе дважды. 4) После того как все города использованы в маршруте, наша задача вернуться в город 1, откуда начинался маршрут, по строке последнего города смотрим расстояние до города 1 и прибавляем его к получившейся сумме расстояний между городов.В данном курсовом проекте был рассмотрен вопрос о создании программы для решения задачи «коммивояжера» прямым алгоритмом. Суть прямого алгоритма в следующем: Имеется N городов, которые должен обойти коммивояжер с минимальными затратами. При этом на его маршрут накладывается два ограничения: - маршрут должен быть замкнутым, то есть коммивояжер должен вернуться в тот город, из которого он начал движение; в каждом из городов коммивояжер должен побывать точно один раз, то есть надо обязательно обойти все города, при этом не побывав ни в одном городе дважды. Для расчета затрат существует матрица условий, содержащая затраты на переход из каждого города в каждый, при этом считается, что можно перейти из любого города в любой, кроме того же самого.Задачи коммивояжера. Прямой алгоритм. Метод ветвей и границ. Модуль программы.Форма 1. using System; using System.Text; using System.Windows.Forms; new_matrix[start, j_min] = second[count]; new_matrix[start, Convert.TOINT16(starting) - 1] = matrix[start, Convert.TOINT16(starting) - 1];Рис.
Введение
В настоящее время существуют такие типы задач как задачи математического программирования. Существуют множество видов таких задач и способов их решения. В данном случае мы будем рассматривать вид задач математического программирования под названием задачи «Коммивояжера». Цель задачи - отыскать наилучший маршрут для торговца, который должен объехать города и вернуться в исходный город, как правило за кратчайшее время или с наименьшими затратами. Такие задачи актуальны во многих областях таких как: автомобильные, судовые, железно - дорожные перевозки или в конвейерном производстве. В условиях задачи указывается критерий маршрута и соответствующие матрицы расстояний или стоимостей и т.д. В задачах указывается, что маршрут должен быть одинарным. В современной интерпретации задачи торговца формулируется так: в произвольном порядке обойти все вершины графа по кратчайшему пути и вернуться в исходную вершину, причем каждая вершина проходится 1 раз. Обычно задачу о торговце решают с помощью прямого алгоритма, т.к. для человека расчет такой задачи занимает много времени, и создаются программы для облегчения вычислений.
В данном курсовом проекте будет рассмотрен вопрос о создании программы для решения задачи «коммивояжера» прямым алгоритмом.
1. Общая часть
1.1 Постановка задачи
1.1.1 Экономическая постановка задачи
В условиях данной задачи сказано, что коммивояжер должен обойти 7 городов, чтобы найти оптимальный маршрут, расстояние которого будет самым коротким.
Расстояния между городами указаны в таблице 1.
Таблица 1.
1 2 3 4 5 6 7
1 5 11 6 3 15 8
2 5 7 12 6 7 2
3 11 7 3 6 3 7
4 6 12 3 2 4 13
5 3 6 6 2 2 5
6 15 7 3 4 1 4
7 8 2 7 13 5 4
1.1.2 Математическая постановка задачи
N - число городов.
Ci j , i, j=1..N - матрица затрат, где Ci j - затраты на переход из i-го города в j-й.
Xi j - матрица переходов с компонентами: Критерий:
Ограничения:
Ui - Uj N ? Xi j ? N-1, i, j = 1..N, i ? j. (4)
Условие (2) означает, что коммивояжер из каждого города выезжает только 1 раз;
Условие (3) о том , что в каждый город въезжает только 1 раз;
Условие (4) обеспечивает замкнутость маршрута, содержащего N городов, и не содержащего замкнутых внутренних петель.
1.2 Обзор существующих решений
Задачи «коммивояжера» решаются несколькими способами: 1.Прямым алгоритмом
Имеется N городов, которые должен обойти коммивояжер с минимальными затратами. При этом на его маршрут накладывается два ограничения: - маршрут должен быть замкнутым, то есть коммивояжер должен вернуться в тот город, из которого он начал движение;
- в каждом из городов коммивояжер должен побывать точно один раз, то есть надо обязательно обойти все города, при этом не побывав ни в одном городе дважды.
Для расчета затрат существует матрица условий, содержащая затраты на переход из каждого города в каждый, при этом считается, что можно перейти из любого города в любой, кроме того же самого. Целью решения является нахождения маршрута, удовлетворяющего всем условиям и при этом имеющего минимальную сумму затрат.
2. Метод ветвей и границ
Общая идея метода может быть описана на примере поиска минимума и максимума функции f(x) на множестве допустимых значений x. Функция f и x могут быть произвольной природы. Для метода ветвей и границ необходимы две процедуры: ветвление и нахождение оценок (границ).
Процедура ветвления состоит в разбиении области допустимых решений на подобласти меньших размеров. Процедуру можно рекурсивно применять к подобластям. Полученные подобласти образуют дерево , называемое деревом поиска или деревом ветвей и границ. Узлами этого дерева являются построенные подобласти.
Процедура нахождения оценок заключается в поиске верхних и нижних границ для оптимального значения на подобласти допустимых решений.
В основе метода ветвей и границ лежит следующая идея если нижняя граница для подобласти A дерева поиска больше, чем верхняя граница какой-либо ранее просмотренной подобласти B, то A может быть исключена из дальнейшего рассмотрения.
Обычно, минимальную из полученных верхних оценок записывают в глобальную переменную m; любой узел дерева поиска, нижняя граница которого больше значения m, может быть исключен из дальнейшего рассмотрения.
Если нижняя граница для узла дерева совпадает с верхней границей, то это значение является минимумом функции и достигается на соответствующей подобласти.
2. Технологическая часть
2.1 Нелинейное программирование. Общий вид задач нелинейного программирования Модели нелинейного программирования. Методы решения задач нелинейного программирования
Нелинейное программирование - случай математического программирования , в котором целевой функцией или ограничением является нелинейная функция .
Задача нелинейного программирования ставится как задача нахождения оптимума определенной целевой функции при выполнении условий где - параметры, s - ограничения, n - количество параметров, s - количество ограничений.
В отличие от задачи линейного программирования, в задаче программирования нелинейного оптимум не обязательно лежит на границе области, определенной ограничениями.
Как правило, в практических задачах необходимо определить наибольшее и наименьшее значения функции (глобальный экстремум) в некоторой области. Говорят, что функция z = f (X) имеет в точке X0 заданной области D глобальный максимум (наибольшее значение) или глобальный минимум (наименьшее значение), если неравенство f(X) ? f(X0) или соответственно выполняется для любой точки X € D.
Если область D замкнута и ограничена, то дифференцируемая функция z = f (X) достигает в этой области своих наибольшего и наименьшего значений или в стационарной точке, или в граничной точке области (теорема Вейерштрасса).
Граница области D аналитически может быть задана системой уравнений (условий) относительно переменных x1, x2, ..., xn. Поэтому, исследуя экстремальные свойства функции на границе, необходимо решить задачу определения условного экстремума.
Условный экстремум. Пусть необходимо найти экстремум функции z = f (x1, x2, ..., xn ) при условии, что переменные x1, x2, ..., xn удовлетворяют, уравнениям ?i (x1, x2, ..., xn ) = 0, i = 1, 2, ..., m,m < n (1)
Предполагается, что функции f и ?i , имеют непрерывные частные производные по всем переменным. Уравнения (1) называют уравнениями связи. Говорят, что в точке удовлетворяющей уравнениям связи(1), функция z = f (X) имеет условный максимум (минимум), если неравенство f(X0) ? f(X) (f(X0) ? f(X)) имеет место для всех точек X, координаты которых удовлетворяют уравнениям связи.
Легко заметить, что задача определения условного экстремума совпадает с задачей нелинейного программирования.
Один из способов определения условного экстремума применяется в том случае, если из уравнений связи (1) m переменных, например x1, x2, ..., xn, можно явно выразить через оставшиеся n - m переменных: xi = ?i (xm 1 , ..., xn ), i = 1, 2, ..., m, (2)
Задача сведена к нахождению локального (глобального) экстремума для функции (3) от n - m переменных. Если в точке функция (3) имеет экстремум, то в точке функция z = f (x1, ..., xn ) имеет условный экстремум.
3. Специальная часть
3.1 Описание метода решения
Для того, чтобы начать решать задачу необходимы условия задачи, в данном случае они представлены в виде таблицы. В таблице даны расстояния между городов.
В условии сказано, что коммивояжер начинает свой маршрут из города 1.
1)По таблице находим город 1 и по строке начинаем искать тот город, который будет давать наименьшее приращение к длине пути или город, ближайший к городу 1.
2) Так как путь только начался то расстояние, пройденное коммивояжером, будет равно нулю, значит к нему прибавляем найденное расстояние.
3) После этого записываем получившуюся сумму, и продолжаем искать город , подходящий к маршруту, после того как следующий город найден, расстояния снова складываются.
4) После того как все города использованы в маршруте, наша задача вернуться в город 1, откуда начинался маршрут, по строке последнего города смотрим расстояние до города 1 и прибавляем его к получившейся сумме расстояний между городов.
5) В результате этих действий находят оптимальный маршрут, с самым коротким расстоянием между городов.
3.2 Решение задачи теста для написания и отладки программы
В данной таблице приведены все условия для решения задачи, а именно длинны путей между городами. Q - расстояние, L - шаг
1 2 3 4 5 6 7
1 5 11 6 3 15 8
2 5 7 12 6 7 2
3 11 7 3 6 3 7
4 6 12 3 2 4 13
5 3 6 6 2 2 5
6 15 7 3 4 1 4
7 8 2 7 13 5 4
Q =
L = 1
=
L = 1->5
Q = Q
L = 1->5->4
Q = Q Q = 5 3 = 8
L = 1->5->4->3
Q = Q
L = 1->5->4->3->6
Q = Q
L = 1->5->4->3->6->7
Q = Q
L = 1->5->4->3->6->7->2
Q = Q
L = 1->5->4->3->6->7->2->1
3.3 Анализ полученных результатов
В результате решения задачи самым оптимальным маршрутом между данными городами был выявлен маршрут, состоящий из семи шагов, а именно: 1->5->4->3->6->7->2->1.
Длинна пройденного пути для этого маршрута оказалась самой наименьшей: Q = 22
3.4 Разработка алгоритма
После того как пользователь запустил исполняемый файл, на рабочем столе появится пустое окно (рис В1), в котором пользователь должен ввести цифру количества столбцов и строк таблицы. Число строк соответствует числу городов. Так как созданная таблица будет квадратная , то пользователю достаточно ввести одну цифру. Данная форма создаст число переменных в соответствии с количеством ячеек таблицы.
Далее открывается окно с созданной таблицей (рис. В2), в которую следует ввести цифры из таблицы, данной в качестве условия пользователю. Цифры соответствуют расстояниям между городами. В данном окне так же возможен выбор города, с которого коммивояжер начнет маршрут. Программа будет проверять минимальный элемент по строке, и суммировать его с количеством уже пройденного пути.
После того, как все поля таблицы заполнены, следует нажать кнопку «Продолжить» будет произведен подсчет согласно формулам подсчета задач коммивояжера.
В третьем окне появится результат подсчетов программы, а именно оптимальный маршрут между данными городами и расстояние, потраченное на прохождение этого маршрута.(рис.В3) ответ будет выведен с помощью цифры с количеством пройденного пути и маршрута в виде цифр и стрелок
После выполнения всех этих действий пользователь может закрыть окно с программой, после чего она завершает работу.
3.5 Обоснование выбора средств разработки
На сегодняшний день существует достаточно языков и сред программирования, при помощи которых можно создавать приложения. Наиболее известные: Delphi, Pascal, C# и т.д.
C#, являясь последним из широко распространенных языков программирования, должен впитать в себя весь имеющийся опыт и вобрать лучшие стороны существующих языков программирования, при этом являясь специально созданным для работы в .NET. Сама архитектура .NET продиктовала ему (как и многим другим языкам, на которых можно писать под .NET) объектно-ориентированную направленность. Конечно, это не является правилом, возможно создание компиляторов даже функциональных языков по .NET, на эту тему существуют специальные работы.
Свой синтаксис C# во многом унаследовал от C и Java. Разработчики, имеющие опыт написания приложений на этих языках, найдут в C# много знакомых черт. Но вместе с тем он является во многом новаторским - аттрибуты, делегаты и события, прекрасно вписанные в общую идеологию языка, прочно заняли место в сердцах .NET - разработчиков. Их введение позволило применять принципиально новые приемы программирования.
Конечно, излюбленным объектом для сравнения с C# у мировой коммьюнити является Java. Также разработанный для работы в виртуальной среде выполнения, имеющей объектно-ориентированную архитектуру и сборщик мусора, осноыванный на механизме ссылок. При сравнении с этим языком сразу выделаются такие особенности, как возможность объявлять несколько классов в одном файле, из чего следует синтаксическая поддержка иерархической системы пространств имен. Из реализации ООП-концепций сходство в механизме наследования и реализации (и в Java и в C# возможно единичное наследование, но множественная реализация интерфейсов, в отличие от C ). Но в Java отсутствуют свойства и индексаторы (а также делегаты и события, но они отсутствуют еще много где). Также есть возможность перечисления контейнеров.
Из вещей, включенных в спецификацию языка, но не являющихся чисто "программистскими" необходимо отметить возможность использование комментариев в формате XML. Если комментарии отвечают специально описанной структуре, компилятор по ним может сгенерировать единый XML-файл документации.
Но C# внес и свои уникальные черты, которые уже были упомянуты - это события, индексаторы, атрибуты и делагаты. Все эти элементы будут обсуждены в следующих частях, сейчас лишь отмечу, что они предоставляют собой очень полезные возможности, которые не останутся невостребованными.
В результате проведенного анализа наиболее популярных средств программирования можно прийти к выводу, что для реализации поставленных задач наиболее всего подходит язык программирования C#.
3.6 Описание программных модулей
Программа состоит из трех частей - форм.
Первая форма отвечает за задание параметров для создаваемой таблицы. Невозможно продолжить работу с программой, пока первая форма не будет заполнена.
Вторая форма полностью зависима от первой и в зависимости от того, какие параметры заданы в первой форме будет создана таблица во второй форме.
Третья форма выводит ответ из результатов работы программы над условиями, заданными во второй форме.
3.7 Тестирование программы
В результате тестирования программы ни одной ошибки, мешающей работе программы, обнаружено не было. Программа работает при любых заданных условиях. В результате решения задачи данной для тестирования программы, было найдено решение этой задачи, ответ которой полностью совпал с ответом, найденным разработчиком самостоятельно. Программа полностью готова к работе, независимо от того, будет ли пользователь следовать инструкции по использованию программы или нет.
У данной программы есть только один недостаток - если при решении задачи могут иметься несколько вариантов решений, то программа будет рассматривать только одно, так что пользователю будет выведена информация только об одном решении.
3.8 Инструкция пользователю
После того как пользователь запустил исполняемый файл, на рабочем столе появится пустое окно (рис В1), в котором пользователь должен ввести цифру количества столбцов и строк таблицы. Число строк соответствует числу городов. Так как созданная таблица будет квадратная , то пользователю достаточно ввести одну цифру.
Далее открывается окно с созданной таблицей (рис. В2), в которую следует ввести цифры из таблицы, данной в качестве условия пользователю. Цифры соответствуют расстояниям между городами. В данном окне так же возможен выбор города, с которого коммивояжер начнет маршрут.
После того, как все поля таблицы заполнены, следует нажать кнопку «Продолжить»
В третьем окне появится результат подсчетов программы, а именно оптимальный маршрут между данными городами и расстояние, потраченное на прохождение этого маршрута.(рис.В3)
Вывод
коммивояжер программирование нелинейный
В данном курсовом проекте был рассмотрен вопрос о создании программы для решения задачи «коммивояжера» прямым алгоритмом.
Суть прямого алгоритма в следующем: Имеется N городов, которые должен обойти коммивояжер с минимальными затратами. При этом на его маршрут накладывается два ограничения: - маршрут должен быть замкнутым, то есть коммивояжер должен вернуться в тот город, из которого он начал движение;
- в каждом из городов коммивояжер должен побывать точно один раз, то есть надо обязательно обойти все города, при этом не побывав ни в одном городе дважды.
Для расчета затрат существует матрица условий, содержащая затраты на переход из каждого города в каждый, при этом считается, что можно перейти из любого города в любой, кроме того же самого. Целью решения является нахождения маршрута, удовлетворяющего всем условиям и при этом имеющего минимальную сумму затрат.
Для того, чтобы начать решать задачу необходимы условия задачи, в данном случае они представлены в виде таблицы 1. В таблице даны расстояния между городов.
В результате решения задачи самым оптимальным маршрутом между данными городами был выявлен маршрут, состоящий из семи шагов, а именно: 1->5->4->3->6->7->2->1.
Длинна пройденного пути для этого маршрута оказалась самой наименьшей: Q = 22
Ответ совпал с ответом задачи, решенной программистом, значит программа написана верно.
Далее была создана инструкция для пользователей, где программа была полностью расписана.
После того как пользователь запустил исполняемый файл, на рабочем столе появится пустое окно (рис В1), в котором пользователь должен ввести цифру количества столбцов и строк таблицы. Число строк соответствует числу городов. Так как созданная таблица будет квадратная , то пользователю достаточно ввести одну цифру.
Далее открывается окно с созданной таблицей (рис. В2), в которую следует ввести цифры из таблицы, данной в качестве условия пользователю. Цифры соответствуют расстояниям между городами. В данном окне так же возможен выбор города, с которого коммивояжер начнет маршрут.
После того, как все поля таблицы заполнены, следует нажать кнопку «Продолжить»
В третьем окне появится результат подсчетов программы, а именно оптимальный маршрут между данными городами и расстояние, потраченное на прохождение этого маршрута.(рис.В3)
Подведем итог, после всех перечисленных шагов, получилась программа, позволяющая высчитать ответ, согласно решению задач «коммивояжера» все пункты были детально рассмотрены и выполнены, благодаря этому цель курсового проекта была достигнута.
Список литературы
1. Агальцов В.П., Валдайская И.В. Математические методы в программировании: Учебник. - М.: ИД «ФОРУМ»: ИНФРА-М, 2006. - 224 с.: ил. - (Профессиональное образование).
2. Голицына О.Л., Попов И.И. Основы алгоритмизации и программирования: Учебное пособие. - М.: Форум: Инфра-М, 2014
3. Орлов В.В. Технологии разработки программных продуктов. - СПБ.: Питер, 2003. - 437 с.
4. Партыка т.Л., Попов И.И. Математические методы: Учебник. - М.: ФОРУМ: ИНФРА-М, 2010. - 464с.: ил. - ( Профессиональное образование)