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

В общем виде задача нелинейного программирования состоит в определении максимального (минимального) значения функции

(1)

При условии, что ее переменные удовлетворяют соотношениям

(2)

Где F И Gi — некоторые известные функции П переменных, a Bi — Заданные числа.

Здесь имеется в виду, что в результате решения задачи будет определена точка координаты которой удовлетворяют соотношениям (2) и такая, что для всякой другой точки удовлетворяющей условиям (2), выполняется неравенство

Для решения сформулированной задачи в такой общей постановке не существует универсальных методов. Однако для отдельных классов задач, в которых сделаны дополнительные ограничения относительно свойств функций F и Gi, разработаны эффективные методы их решения. В частности, ряд таких методов имеется для решения задач нелинейного программирования (1) - (2) при условии, что F — вогнутая (выпуклая) функция и область допустимых решений, определяемая ограничениями (25) и (26), — выпуклая.

Если F и Gi — линейные функции, то задача (1), (2) является задачей линейного программирования.

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

В евклидовом пространстве система ограничений (2) определяет область допустимых решений задачи. В отличие от задачи линейного программирования она не всегда является выпуклой.

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

Процесс нахождения решения задачи нелинейного программирования (1), (2) с использованием ее геометрической интерпретации включает следующие этапы:

1. Находят область допустимых решений задачи, определяемую соотношениями (2) (если она пуста, то задача не имеет решения).

2. Строят поверхность

3. Определяют гиперповерхность наивысшего (наинизшего) уровня или устанавливают неразрешимость задачи из-за неограниченности функции (1) сверху (снизу) на множестве допустимых решений.

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

1.24. Найти максимальное значение функции

(3)

При условиях

(4)

(5)

Решение. Так как целевая функция (3) нелинейная, то задача (3) - (5) является задачей нелинейного программирования. Областью допустимых решений данной задачи является многоугольник ОАВС (рис. 14). Следовательно, для нахождения ее решения нужно определить такую точку многоугольника ОАВС, в которой функция (3) принимает максимальное значение. Построим линию уровня где H — некоторая постоянная, и исследуем ее поведение при различных значениях H. При каждом значении H получаем параболу, которая тем выше отдалена от оси Ox1, чем больше значение H (рис. 14). Значит, функция F принимает максимальное значение в точке касания одной из парабол с границей многоугольника ОАВС. В данном случае это точка D (рис. 14), в которой линия уровня касается стороны АВ многоугольника ОАВС. Координаты точки D можно найти из системы уравнений

(6)

Решая эту систему, получим Итак, При .

Как видим, в задаче (3) - (5) точка максимального значения целевой функции не является вершиной многоугольника решений. Поэтому процедура перебора вершин, которая использовалась при решении задач линейного программирования, неприменима для решения данной задачи.

1.25. Найти максимальное и минимальное значения функции

(7)

При условиях

(8)

(9)

Решение. Областью допустимых решений задачи (7) - (9) является треугольник АВС (рис. 15). Полагая значение целевой функции (7) равным некоторому числу H, получаем линии уровня, а именно окружности с центром Е(3; 4) и радиусом . С увеличением (уменьшением) числа H значения функции F соответственно увеличиваются (уменьшаются).

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

Из уравнения прямой видим, что ее угловой коэффициент в точке D равен 10. Угловой же коэффициент касательной к окружности в точке D определим как значение производной функции от переменной в этой точке. Рассматривая как неявную функцию переменной и дифференцируя уравнение окружности, получим

Откуда

Приравнивая найденное выражение числу 10, получаем одно из уравнений для определения координат точки Е. Присоединяя к нему уравнение прямой, на которой лежит точка Е, имеем систему

Откуда Таким образом,

Как видно из рис. 15, целевая функция принимает максимальное значение в точке С(2; 12). Ее координаты определены путем решения системы уравнений прямых, на пересечении которых находится точка С. Таким образом, максимальное значение функции

1.26. Найти максимальное и минимальное значения функции

(10)

При условиях

(11)

(12)

Решение. Областью допустимых решений исходной задачи является многоугольник ABCDE (рис. 16), а линиями уровня - окружности с центром Е(4; 3) и радиусом .

Из рис. 16 видно, что целевая функция принимает минимальное значение в точке F(4; 3), а максимальное — в точке С(13; 10,5). Следовательно, и .

1.27. Найти максимальное значение функции

(13)

При условиях

(14)

(15)

Решение. Область решений задачи (13) - (15) изображена на рис. 17. На этом рисунке построены две линии уровня, представляющие собой прямые. Из рис. 17 видно, что максимальное значение целевая функция задачи принимает в точке Е, в которой прямая касается окружности Для определения координат точки Е воспользуемся равенством угловых коэффициентов прямой (где H — некоторая постоянная) и касательной к окружности в точке Е. Рассматривая как неявную функцию переменной , почленно дифференцируем уравнение окружности и получим

или

Приравнивая найденное выражение числу , получаем одно из уравнений для определения координат точки Е. В качестве второго уравнения возьмем уравнение окружности. Таким образом, для определения координат точки Е имеем систему

Откуда Значит,

< Предыдущая		Следующая >