Постановка и решение дискретных оптимизационных задач методом дискретного программирования и методом ветвей и границ на примере классической задачи коммивояжера. Этапы построения алгоритма ветвей и границ и его эффективность, построение дерева графов.
Аннотация к работе
1. Дискретные оптимизационные задачи 1.1 Постановка задач дискретного программирования 1.2 Алгоритм метода ветвей и границ6 2. Постановка задачи коммивояжера 3. Хотя конечной целью оптимизации является отыскание наилучшего или оптимального решения, обычно приходится довольствоваться улучшением известных решений, а не доведением их до совершенства. По ходу дела ему приходится принять целый ряд решений: брать ли с собой зонтик?. Допусти, организуется работа городского транспорта. Они будут рассмотрены на примере задачи коммивояжера. 1.1 Постановка задач дискретного программирования Под задачей дискретного программирования (дискретной оптимизации) понимается задача математического программирования F(x0) = min f(x), x є G, множество допустимых решений которой конечно, т.е. Пусть i - произвольный город (i I N), а V - любое подмножество городов, не содержащее города 1 и города i. Для решаемой задачи В(i, V) - функция Беллмана.