требованием, чтобы переменные принимали только целочисленные значения- задачи целочисленного программирования. В отличие от последних, в задачах дискретного программирования областью допустимого изменения каждой переменной является некоторое заданное конечное множество.
В ряде задач ЛП и НП процессы зависят от времени - от нескольких периодов (этапов). При решении таких многоэтапных задач необходимо учитывать развитие экономического процесса (например, распределение ресурсов между предприятиями по годам планируемого периода). Такие задачи относятся к задачам динамического программирования.
На практике часто встречаются задачи, в которых на состояние системы и на значение критерия оказывают влияние случайные факторы. В таких задачах управляемый процесс не полностью определяется начальными условиями и выбранным управлением. Они относятся к задачам стохастического программирования. В данном случае уже не имеет смысла поиск экстремума целевой функции, т.к. это теперь случайная величина. Обычно на практике в качестве целевой функции выбирают ее математическое ожидание.
Класс ЗНП шире класса ЗЛП. Например, производственные затраты в большинстве случаев не пропорциональны объему выпуска, а зависят от него нелинейно, доход от реализации продуктов производства оказывается нелинейной функцией цен и т.д.
Критериями в задачах оптимального планирования часто служат:
· максимум прибыли,
· минимум себестоимости,
· минимум капитальных затрат;
в качестве переменных величин выступают объемы выпуска различных видов продукции; в число ограничений входят производственные функции, характеризующие связь между выпуском продукции и затратами трудовых и материальных ресурсов, объем которых лимитирован.
Если все эти функции f, gi, hj дифференцируемы в Rn , то (4.1) называется гладкой задачейнелинейного программирования.
Существующие методы НП применимы лишь при известных предположениях о характере ограничений и целевой функции задачи.
Система ограничений (8.2) определяет область допустимых решений. В отличие от задачи ЛП она не всегда является выпуклой. Даже если область допустимых решений является выпуклой, то в ряде задач целевая функция может иметь несколько локальных экстремумов. С помощью большинства же вычислительных методов можно найти точку локального оптимума, но нельзя установить, является ли она точкой глобального (абсолютного) оптимума или нет.
Наиболее изучены задачи выпуклого программирования (ЗВП) - задачи нахождения минимума выпуклой (или максимума вогнутой) функции, заданной на выпуклом замкнутом множестве.
Сформулируем общую постановку ЗВП.
Минимизировать f(X) при ограничениях gi(X) ≤ 0, i = 1.. и hi(X) = 0, i = k + 1..m., где f(X)- выпуклая функция и каждая функция, задающая ограничение в виде неравенства,- выпуклая функция (ограничения образуют выпуклое множество), а ограничения в виде равенств - линейны.
При этом можно показать справедливость следующего положения: локальный минимум является также и глобальным минимумом. Аналогично локальный максимум является глобальным максимумом, если целевая функция вогнутая, а ограничения образуют выпуклое множество.
Частный случай ЗВП- задачи линейного и квадратичного программирования, которые исследованы более подробно. В ЗЛП, имеющей оптимальное решение, целевая функция всегда выпуклая, а ограничения образуют выпуклое множество, так что локальный оптимум всегда является в то же время и глобальным оптимумом. Ограничения в задаче квадратичного программирования те же, что и в ЗЛП, а целевая функция выпуклая.
Общая классификация методов решения задач НП приведена на рисунке
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
