Воспользуйтесь поиском к примеру Реферат        Грубый поиск Точный поиск
Вхід в абонемент


Интернет реклама УБС






Задачи нелинейного программирования

Особенности нелинейного программирования

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

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

Итак, линейные модели мы можем считать первым приближение реальной задачи. В тех случаях, когда существует широкий выбор допустимых планов и наше представление о характере оптимального связи не совсем полное, линейные модели могут быть неадекватными.

В большинстве случаев нелинейность модели обусловливается, как правило, структурными соотношениями экономического процесса или непропорциональностью изменения затрат, выпуска продук-ции, показателей качества.

В общей постановке задачу нелинейного Программиро-ния (НЛП) записывают так:

(1)

(max) z (x1, x2, ..., xn), (2)

где F1 (x), ..., Fn (x), z (x), x = (x1, x2, ..., xn) - произвольные фун-кции. В конкретных задачах часть ограничений (или все) могут быть неровностями. Кроме того, на неизвестные могут излагаться условия неотрицательности и т.п.

Одной из основных особенностей задач НЛТ есть возможность различными способами задавать целевую функцию. Если в линейном случае она была строго монотонной и достигала своего оптимального значения лишь в вершине многоугольника решения; то картина совсем другая. Например! также график функции, одной переменной, свидетельствует о том, что она уже имеет много локальных максимумов.

Вторая особенность задач НЛП следует из нарушения свойства выпуклости многоугольника решений задач ЛП. Легко привести примеры задач, где область решений задачи НЛП будет многосвязных.

Геометрическая интерпретация задач, нелинейного программирования

Для большей наглядности проиллюстрируем эти случаи игра-чески. Рассмотрим случай двух переменных с ограничениями-неравенствами.

Пример 1. Найти наибольшее и наименьшее значения функции

при таких ограничениях:

Система ограничений линейная, поэтому область решений стекла подается с многоугольника решений.

Нетрудно заметить, что целевую функцию можно записать следующим образом:

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

zmin = (6-l) 2 + (0-2) 2 = 29.

Аналогично zmax - (1 - I) 2 + (2 - 2) 2 = 0. В данном случае наименьшее значение функции содержится в области раз-вязки, а больше всего - на ее границе. Если в этом же примере рассмотреть функцию z = (x1 - 4) 2 + (х2 - 4) 2.

zmax = (4-0) 2 + (4-0) 2 = 32

zmin =

Пример 2. Найти наибольшее и наименьшее значения функции

при таких ограничениях:

Oбласть решений является несвязной - состоит из двух отдельных частей. Имеем два одинаковых локальных минимума. Координаты этих точек можно найти как решение системы уравнений:

Легко проверить, что имеем и два локальных максимума.