Методы нелинейного и целочисленного программирования

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

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

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

Определение

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

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

Далее мы более подробно рассмотрим основные вопросы, связанные с использованием методов нелинейного и целочисленного программирования.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >