Курсовая работа

  • 06 апр. 2012 г.
  • 2483 Слова
ВВЕДЕНИЕ
Цель моей курсовой работы – разобраться в чём суть метода ветвей и границ, научиться решать задачи и использовать его.
Необходимость принятия наилучших решений очень стара. Люди, приступая к осуществлению своих мероприятий, раздумывали над их возможными последствиями и принимали решения, выбирая тем или другим образом зависящие от них параметры - способы организации мероприятий. Но допоры, до времени решения могли приниматься без специального математического анализа, просто на основе опыта и здравого смысла.
Например: человек вышел утром из дому, чтобы поехать на работу. По ходу дела ему приходится принять целый ряд решений: брать ли с собой зонтик? В каком месте перейти улицу? Каким видом транспорта воспользоваться? И так далее. Разумеется, все эти решения человек принимаетбез специальных расчетов, просто опираясь на имеющийся у него опыт и на здравый смысл. Для обоснования таких решений никакая наука не нужна, да вряд ли понадобится и в дальнейшем.
Однако возьмем другой пример. Допустим, организуется работа городского транспорта. В нашем распоряжении имеется какое-то количество транспортных средств. Необходимо принять ряд решений, например: какое количество и какихтранспортных средств направить по тому или другому маршруту? Как изменять частоту следования машин в зависимости от времени суток? Где поместить остановки? И так далее.
Эти решения являются гораздо более ответственными, чем решения предыдущего примера. В силу сложности явления, последствия каждого из них не столь ясны. Для того, чтобы представить себе эти последствия, нужно провести расчеты. Аглавное, от этих решений гораздо больше зависит. В первом примере неправильный выбор решения затронет интересы одного человека, во втором - может отразиться на деловой жизни целого города.
Наиболее сложно обстоит дело с принятием решений, когда речь идет о мероприятиях, опыта, в проведении которых еще не существует и, следовательно, здравому смыслу не на что опереться, а интуиция может обмануть.
Пусть,например, составляется перспективный план развития вооружения на несколько лет вперед. Образцы вооружения, о которых может идти речь, еще не существуют, никакого опыта их применения нет. При планировании приходится опираться на большое количество данных, относящихся не столько к прошлому опыту, сколько к предвидимому будущему. Выбранное решение должно по возможности гарантировать нас от ошибок,связанных с неточным прогнозированием, и быть достаточно эффективным для широкого круга условий. Для обоснования такого решения приводится в действие сложная система математических расчетов.
Вообще, чем сложнее организуемое мероприятие, чем больше вкладывается в него материальных средств, чем шире спектр его возможных последствий, тем менее допустимы так называемые "волевые" решения, не опирающиеся на научныйрасчет, и тем большее значение получает совокупность научных методов, позволяющих заранее оценить последствия каждого решения, заранее отбросить недопустимые варианты и рекомендовать те, которые представляются наиболее удачными.


Глава 1. Теоретическая часть.
Историческая справка.
Впервые метод ветвей и границ был предложен Лендом и Дойгом в 1960 для решения общей задачи целочисленноголинейного программирования. Интерес к этому методу и фактически его “второе рождение” произошло в 1963 г. В связи с работой Литтла, Мурти, Суини и Кэрела, посвященной задаче комивояжера. Начиная с этого момента, появилось большое число работ, посвященных методу ветвей и границ и различным его модификациям. Столь большой успех объясняется тем, что авторы первыми обратили внимание на широту возможностей метода,отметили важность использования специфики задачи и сами воспользовались спецификой задачи коммивояжера.
Основа метода ветвей и границ.
В основе метода ветвей и границ лежит идея последовательного разбиения множества допустимых решений на подмножества. На каждом шаге метода элементы разбиения подвергаются проверке для выяснения, содержит данное подмножество...
tracking img