Дискретное программирование (стр. 4 из 4)

Для случая задачи (D2(q), f) преобразование симплекс-таблицы, получаемое на базе аналогичных рассуждений, приведено на рис.6.

Очевидным недостатком алгоритма метода ветвей и границ при решении задач большой размерности является необходимость перебрать слишком большое количество вариантов перед тем, как будет найден оптимальный план. Однако он отчасти может быть преодолен, если ограничиться поиском не оптимального, а просто "хорошего" (близкого к оптимальному) плана. О степени такой близости и скорости приближения к экстремуму нетрудно судить по изменению значений оценок.

Подчеркнем, что приведенная реализация метода ветвей и границ является одной из многих. Помимо нее, например, очень популярна версия метода решения задачи коммивояжера, в которой для ветвления и построения оценок используют специфические свойства данной модели.

6. Заключение

Дискретные оптимизационные задачи находят широкое применение в различных областях, где используются математические методы для анализа происходящих там процессов. Необходимость решения таких задач приводит к тому, что дискретная оптимизация становится важным элементом образования специалистов, связанных с ее применением при решении задач, возникающих в приложениях. Поэтому технология решения задач дискретного программирования должна стать одной из важных составных частей современного математического образования для специалистов по прикладной математике. В настоящее время разработаны современные методы и алгоритмы решения задач дискретного программирования. Разработаны пакеты прикладных программ, позволяющие решать ряд стандартных задач дискретного программирования. Знание существа применяемых алгоритмов и технологий их реализации позволяет более эффективно использовать разработанные пакеты. При возникновении новых нестандартных задач реализация алгоритмов их решения требует информации о технологии решения задач дискретной оптимизации.

Для изучения материала необходимы знания основ математического анализа, линейной алгебры, линейного программирования и основ теории графов.