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

Программирования

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

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

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

1. Находят ОДР задачи, определяемую соотношением (2); если она пуста, то задача не имеет решения.

2. Строят гиперповерхность f (x₁, x₂, … x_n) = h.

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

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

Найти max функции f = x₂ - x₁² + 6x₁ (3)

При условиях

2х₁ + 3х₂ £ 24

х₁ + 2х₂ £ 15

3х₁ + 2х₂ £ 24

х₂ £ 4,

х₁,х₂ ³ 0.

Решение: F нелинейна, следовательно, это задача НП;

1. ОАВС - ОДР

Следовательно, нужно определить такую точку многоугольника ОАВС, в которой функция принимает max значение.

2. Построим линию уровня F = x₂ - x₁² +6x₁ = h,

где h – некоторая постоянная, и исследуем ее поведение при различных h. При каждом h получаем параболу, которая тем выше относительно ОХ, чем больше h.

Действительно,

F = x₂ - x₁² +6x₁ = h = ® парабола x₂ = x₁² - 6x₁ – h или х₂ = (х₁ – 3)²+h-9.

Рассмотрим h = 9 х₂ = (х₁ – 3)²

h = 11 х₂ = (х₁ – 3)² + 2

h = 13 х₂ = (х₁ – 3)² + 4

Функция F принимает максимальное значение в точке касания одной из парабол с границей многоугольника ОАВС. В данном случае это точка Д, в которой линия уровня F = x₂ - x₁² +6x₁ = 13 касается стороны многоугольника ОАВС.

При каждом h получаем параболу, которая тем выше отн. ОХ, чем больше h.

Действительно,

F = x₂ - x₁² +6x₁ = h = ® парабола x₂ = x₁² - 6x₁ – h или х₂ = (х₁ – 3)²+h-9

Рассмотрим h = 9 х₂ = (х₁ – 3)²

h = 11 х₂ = (х₁ – 3)² + 2

h = 13 х₂ = (х₁ – 3)² + 4

Координаты точки D находим из уравнений, соответствующих преобразованным ограничениям (1) и (2):

x₂ - x₁² +6x₁ = 13, х₂ = 4, откуда х₁* = 3; х₂* = 4.

U_max, F_max = 13 при х* = (3;4).

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

Дата добавления: 2014-01-11