ЗАДАЧИ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. СЕТЕВОЕ ПЛАНИРОВАНИЕ И УПРАВЛЕНИЕ

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

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

/(xyx„...,xw) (8.1)

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

_______ (8.2)

g, (х{х2,..xj = b (i = к + 1,

где f и gt - некоторые известные функции n переменных, a b( - заданные числа.

В результате решения задачи должна быть определена точка X* = (х*, х*2,..., х*я), координаты которой удовлетворяют соотношениям (8.2), и такая, что для всякой другой точки X- (х, х„ xj, удовлетворяющей условиям (8.2), выполняется неравенство х*2, .... х*я) > /(X, Ху . , Хп) [f(xx, jQ Х2,..Х„) ].

Если f и g. - линейные функции, то данная задача является задачей линейного программирования.

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

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

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

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

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

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

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

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

  • 1. Находят область допустимых решений задачи, определяемую соотношениями (8.2) (если она пуста, то задача не имеет решения).
  • 2. Строят гиперповерхность f( х2, ..xj = h.
  • 3. Определяют гиперповерхность наивысшего (наинизшего) уровня или устанавливают неразрешимость задачи из-за неограниченности функции (8.1) сверху (снизу) на множестве допустимых решений.
  • 4. Находят точку области допустимых решений, через которую проходит гиперповерхность наивысшего (наинизшего) уровня, и определяют в ней значение функции (8.1).

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

^(Л) = л2-л-21 + 6х,

(8.3)

при условиях

{1 + Зх2 < 24, х, + 2х,< 15, Зх,+2х2<24,

х2<4, х,Л>0.

  • (8.4)
  • (8.5)

Решение. Так как целевая функция (8.3) нелинейная, то задача (8.3) - (8.5) является задачей нелинейного программирования. Областью допустимых решений данной задачи является многоугольник ОАВС (рис. 8.1). Следовательно, для нахождения ее решения нужно

Рис. 8.1

определить такую точку многоугольника ОАВС, в которой функция (8.3) принимает максимальное значение. Построим линию уровня F = х2 - х2 + 6х( = А, где h - некоторая постоянная, и исследуем ее поведение при различных значениях А. При каждом значении А получаем параболу, которая тем выше отдалена от оси Охг чем больше значение А (рис. 8.1). Значит, функция F принимает максимальное значение в точке касания одной из парабол с границей многоугольника ОАВС. Координаты точки D можно найти из системы уравнений

х2 + 6х( = 13, х2 = 4.

(8.6)

Решая эту систему, получим х* = 3; х* = 4. Итак, Fmax = 13 при А” = (3; 4).

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

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

^(Л) = (х,-3)2 + (х2-4)2 (8.7) при условиях

  • 1 + 2 > 7, Юх, 2<8, -18х, +4х2< 12, х,Л>0.
  • (8.8)
  • (8.9)

Решение. Областью допустимых решений задачи (8.7) - (8.9) является треугольник (рис. 8.2). Полагая значение целевой функции (8.7) равным некоторому числу А, получаем линии уровня, а именно окружности (х1 - З)2 + (х2 - 4)2 = А с центром Е (3; 4) и радиусом 4h. С увеличением (уменьшением) числа А значения функции F соответственно увеличиваются (уменьшаются).

Проводя из точки Е окружности разных радиусов, видим, что минимальное значение целевая функция принимает в точке D, в которой окружность касается области решений. Для определения координат этой точки воспользуемся равенством угловых коэффициентов прямой 10х1 - х2 = 8 и касательной к окружности в точке D. Из уравнения прямой х, = 10х1 - 8 видим, что ее угловой коэффициент в точке D равен 10. Угловой же коэффициент касательной к окружности в точке D определим как значение производной функции х2 от переменной х( в этой точке. Рассматривая х, как неявную функцию переменной х. и дифференцируя уравнение окружности, получим.

2(х | - 3) + 2(х 2 - 4)х j = 0, откуда х2 = -(г 1 - 2)/(х 2 - 4)

Рис. 8.2

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

f X] + 10х2 = 43,

| 10х| 2 = 8,

откудах* = 123/101; х* = 422/101. Таким образом, Fmm - (123/101 - З)2 + + (422/101 -4)2 = 324/101.

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

Рис. 8.3

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

Яф0 = (х,-4)2 + (х2-3)2 при условиях

  • | + Зх, > 6, Зх, - 2х2< 18, -X, + 2х,<8, х,.х2>0.
  • (8.Ю)
  • (8.11)
  • (8.12)

Решение. Областью допустимых решений исходной задачи является многоугольник ABCDE (рис. 8.3), а линиями уровня - окружности (х, - 4)2 + (х2 - З)2 = h с центром F (4; 3) и радиусом R = ^h.

На рис. 8.3. видно, что целевая функция принимает минимальное значение в точке F (4; 3), а максимальное - в точке Е (13; 10,5). Следовательно, F =0hF = 137.25. ’ min max

Рис. 8.4

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

IV(X) = Зх, + 2

при условиях

I х2 + х2 <25,

1 Л1Л2—

х,.х2>0.

  • (8.13)
  • (8.14)
  • (8.15)

Решение. Область решений задачи (8.13) - (8.15) изображена на рис. 8.4. Здесь построены две линии уровня, представляющие собой прямые. Максимальное значение целевая функция задачи принимает в точке ?, в которой прямая касается окружности х2 + х2 = 25. Для определения координат точки Е воспользуемся равенством угловых коэффициентов прямой Зх( + 2 = h (где h - некоторая постоянная) и касательная к окружности в точке Е. Рассматривая х2 как неявную функцию переменной х|5 почленно дифференцируем уравнение окружности х2 + х2 = 25 и получим 2х( + Ix^ = 0, или х'2 = -х(2.

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

Зх( - 4х, = 0 ,

х2 + х2 =25 ,

откуда Fmax = З2 + 42 = 25.

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