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

3. Область допустимых решений может состоять из нескольких частей.

Пример 2. Дана система ограничений:

x₁x₂  4

x₁ + x₂  5

x₁  7

x₂  6

x₁ 0, x₂  0.

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

Возьмем первое ограничение и заменим неравенство на равенство: . Выразим х₂ через х₁: , х₁0. Данное выражение геометрически представляет собой гиперболу.

Рис.2. Область допустимых решений состоит из двух частей

Заменив во втором ограничении тип ограничения неравенство на равенство (=), имеем уравнение граничной прямой: х₁+х₂=5. Полуплоскость х₁+х₂  5 не содержит точку начало координат (0; 0).

Третье ограничение: x₁  7, граничная прямая параллельна оси ОХ₂ , полуплоскость слева от граничной прямой.

Четвертое ограничение: x₂  6, граничная прямая параллельна оси ОХ₁ , полуплоскость ниже граничной прямой.

Условия неотрицательности переменных: x₁ 0, x₂  0 - первая координатная четверть.

Область допустимых решений на рисунке закрашена темным цветом и состоит из двух отдельных частей: ABCD и KLMN.

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

Пример 3. Найти min Z = (x₁ – 2)² + (x₂ –2)²

x₁ + 2x₂  10

x₁ + x₂  1

x₁ 0, x₂  0

1. Н

   x₁+2x₂  10

   x₁+2x₂ = 10

   аходим область допустимых решений (рис.3).

x1	0	10
x2	5	0

Точка (0,0)полуплоскости

x1	0	1
x2	1	0

x₁+x₂ ≥ 1

x₁+x₂ = 1

Точка (0,0)полуплоскости

Рис. 3. Оптимальное решение достигается во внутренней точке ОДР

Область допустимых решений – многоугольник АВСD – непустая ограниченная выпуклая область.

2. Найдем min Z = (x₁ – 2)² + (x₂ – 2)² . Целевая функция - концетрические окружности произвольного радиуса с центром в точке K(2, 2),

Оптимальное решение достигается в точке K(2, 2), которая является внутренней точкой области допустимых решений, при этом значение целевой функции min Z = (2 – 2)² + (2 – 2)² = 0.

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

Пример 4.

max Z = x₁²+x₂²

x₁x₂  4

x₁ + x₂  5

x₁  7

x₂  6

x₁ 0, x₂  0

Область допустимых решений состоит из двух отдельных частей: АВСD и KLMN (рис.4).

Если Z = 1, то x₁²+x₂² =1 - окружность с центром в точке (0;0) и радиусом, равным 1. Пусть Z = 4, тогда - окружность с центром в точке (0;0) и радиусом, равным 2. Увеличивая значение Z, мы видим, что максимальное значение функция достигает в точках С и М соответственно в частях ОДР АВСD и KLMN. В них имеем локальный максимум. Найдем координаты точек.

Найдем координаты точки С и вычислим в ней значение Z.

; С ( ; 6).

Найдем координаты точки М и вычислим в ней значение Z.

; М .

Рис. 4. Область допустимых решений состоит из двух отдельных частей: АВСD и KLMN. Глобальный максимум в точке М , max Z = .

Оптимальное решение для части ABCD – точка C(2/3;6), а для части KLMN оптимальное решение - точка М(7;4/7). Сравнив значения целевой функции в этих точках, можно найти глобальный максимум.

Сравнивая значения Z в точках С и М делаем вывод, что максимальное значение целевой функции достигается в точке М , max Z = . Это глобальный максимум.

Определение 1. Функция f(Х) достигает локального максимума в точке , если для всех точек , лежащих в малой окрестности точки , имеет место неравенство .

Определение 2. Функция f(Х) достигает глобального (абсолютного) максимума в точке , если для всех точек , принадлежащих области допустимых решений, справедливо неравенство .