Графическим способом найти экстремумы

Сервис для решения задач по линейному программированию

и другие интересные типовые задачи English

Пример №2. Решение задачи линейного программирования графическим методом.
Функция достигает наименьшего значения в точке

при следующих ограничениях:

	x1	+	2 x2	≤	8
	x1	—	x2	≤	2
	x1	+	2 x2	≥	4
	x1	≥	1

x₁ ≥ 0 x₂ ≥ 0

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

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

Последние два шага служат непосредственно для получения ответа. (см. шаг 5 — шаг 6)

Это стандартная схема решения. Если область допустимых решений представляет собой точку или пустое множество, то решение будет короче.

По условию задачи: x₁ ≥ 0 x₂ ≥ 0.

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

Рассмотрим неравенство 1 системы ограничений.

Построим прямую: x₁ + 2 x₂ = 8

Найдены коородинаты двух точек (0, 4) и (8 ,0). Соединяем их и получаем необходимую прямую (1).

Нас интересуют точки расположенные выше или ниже построенной прямой (1) ?
Вернемся к исходному неравенству.

Преобразуем неравенство, оставив в левой части только x₂

Знак неравенства ≤ . Следовательно, нас интересуют точки расположенные ниже построенной прямой (1).

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

Рассмотрим неравенство 2 системы ограничений.

Найдены коородинаты двух точек (0, -2) и (2 ,0). Соединяем их и получаем необходимую прямую (2).

Нас интересуют точки расположенные выше или ниже построенной прямой (2) ?
Вернемся к исходному неравенству.

Преобразуем неравенство, оставив в левой части только x₂

Знак неравенства ≥ . Следовательно, нас интересуют точки расположенные выше построенной прямой (2).

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

Рассмотрим неравенство 3 системы ограничений.

Построим прямую: x₁ + 2 x₂ = 4

Найдены коородинаты двух точек (0, 2) и (4 ,0). Соединяем их и получаем необходимую прямую (3).

Нас интересуют точки расположенные выше или ниже построенной прямой (3) ?
Вернемся к исходному неравенству.

Преобразуем неравенство, оставив в левой части только x₂

Знак неравенства ≥ . Следовательно, нас интересуют точки расположенные выше построенной прямой (3).

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

Рассмотрим неравенство 4 системы ограничений.

Построим прямую: x₁ = 1

Данная прямая параллельна оси OX₂ и проходит через точку (1,0) (4)

Знак неравенства ≥ . Следовательно, нас интересуют точки расположенные правее построенной прямой (4).

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

Строим вектор C = (2, 2), координатами которого являются коэффициенты функции F.

Будем перемещать «красную» прямую, перпендикулярно вектору C , от левого нижнего угла к правому верхнему.

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

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

Функция F достигает наименьшего значения в точке A. (см. рисунок)

Найдем координаты точки A.
Точка A одновременно принадлежит прямым (3) и (4).

	x1	+	2 x2	=	4	=>	x1 = 1
	x1	=	1	x2 = 3/2

Вычислим значение функции F в точке A (1,3/2).

F (A) = 2 * 1 + 2 * 3/2 = 5

x₁ = 1

x₂ = 3/2

F _min = 5

Замечание: если возникли сомнения, что функция F достигает своего минимума в точке А, необходимо найти значение функции в интересующей точке и сравнить с F(A).

Источник

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

Чтобы найти ее оптимальное решение, нужно выполнить следующие действия:

1. Найти ОДР, определяемую ограничениями задачи. Если окажется, что эта область пуста, то это означает, что задача не имеет решения.
2. Построить семейство линий уровня целевой функции f(х₁, х₂) = C при различных значениях числового параметра С.
3. При решении задачи на минимум определить направление убывания, а для задачи на максимум — направление возрастания линий уровня ЦФ.
4. Найти точку ОДР, через которую проходит линия уровня с наименьшим в задаче на минимум (соответственно, наибольшим в задачи на максимум) значением параметра С. Эта точка будет оптимальным решением. Если ЦФ не ограничена снизу в задаче на минимум (сверху — в задаче на максимум), то это означает, что задача не имеет оптимального решения.
5. Найти координаты точки оптимума и определить в ней значение ЦФ.

Отметим, что в отличие от задачи ЛП точка оптимума в задаче НП не обязательно находится на границе ОДР. Ею также может быть внутренняя точка этого множества.

Пример . В задаче выпуклого программирования требуется:

1. найти решение графическим методом;
2. написать функцию Лагранжа и найти ее седловую точку, используя решение, полученное графически.

F(X) = x₁ 2 +(x₂-2) 2
2x₁+x₂ ≥ 7
x₁+2x₂ ≥ 5

Решение. 1) Строим два ограничения, тем самым определяя ОДР. Можно использовать этот калькулятор. Также удобно строить ограничения через этот сервис.

Затем строим функцию цели. В данном случае это окружность.

Поскольку задача минимума, то ищем первое касание линии уровня области ОДР. В данном случае это точка пересечения с прямой 2x₁+x₂-7=0.
Найдем точку пересечения. Для этого построим уравнение касательной, проходящей через центр окружности O(0;2) и перпендикулярно прямой 2x₁+x₂-7=0 (можно использовать этот калькулятор). Получаем: 2x₂-x₁-4=0. Решая систему уравнений:
2x₁+x₂-7=0
2x₂-x₁-4=0,
получаем: x₁=2, x₂=3.

2) Найдем экстремум функции F(X) = x₁ 2 +(x₂-2) 2 , используя калькулятор Функция Лагранжа :
L( X , λ )=F( X )+∑(λ_i·φ_i)
где F( X ) — целевая функция вектора X; φ_i(X) — ограничения в неявном виде (i=1..n)
В качестве целевой функции, подлежащей оптимизации, в этой задаче выступает функция: F(X) = x₁ 2 +(x₂-2) 2
Перепишем ограничение задачи в неявном виде:
φ₁(X) = 7 — (2*x₁+x₂) = 0 (X₁)
φ₂(X) = 5 — (x₁+2*x₂) = 0 (X₂)
Составим вспомогательную функцию Лагранжа: L(X, λ) = x₁ 2 +(x₂-2) 2 — λ₁*(7 — (2*x₁+x₂)) — λ₂*(5 — (x₁+2*x₂))
Необходимым условием экстремума функции Лагранжа является равенство нулю ее частных производных по переменным х_i и неопределенным множителям λ.
Составим систему:
∂L/∂x₁ = 2*λ₁+λ₂+2*x₁ = 0
∂L/∂x₂ = λ₁+2*λ₂+2*x₂-4 = 0
∂L/∂λ₁ = 2*x₁+x₂-7 = 0
∂L/∂λ₂ = x₁+2*x₂-5 = 0
Решив данную систему, получаем:
а) для случая X₁: x₁ = λ₁/2 + λ₂ + 2; x₂ = 7 — 2x₁
Откуда можно найти такие λ₁ ≥ 0, λ₂ ≥ 0. Пусть λ₂ = 0. Тогда λ₁ = 2; x₁ = 2; x₂ = 3.
Поскольку λ₂ ≥ 0, то данное решение удовлетворяет условиям Куна-Таккера. Z_min(2;3)=5

б) для случая X₂: x₂ = λ₁/2 + λ₂ + 2; x₁ = 5 — 2x₂
Откуда можно найти такие λ₁ ≥ 0, λ₂ ≥ 0. Пусть λ₂ = 0. Тогда λ₁ = 2/5; x₁ = 11/5; x₂ = 3/5.
Поскольку λ₁ ≥ 0, то данное решение удовлетворяет условиям Куна-Таккера. Z_min(11/5;3/5)=6.8

Минимальное значение составит Z_min(2;3)=5.

Источник

Графический метод

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

Задача с линейной целевой функцией и нелинейной системой ограничений

Пример 1. Найти глобальные экстремумы функции

Решение. Область допустимых решений — часть окруж­ности с радиусом 4, которая расположена в первой четверти (рис. 28.1).

Линиями уровня целевой функции являются параллельные прямые с угловым коэффициентом, равным -2. Глобальный минимум достигается в точке O (0, 0), глобальный максимум — в точке А касания линии уровня и окружности. Проведем че­рез точку А прямую, перпендикулярную линии уровня. Прямая проходит через начало координат, имеет угловой коэффициент 1/2 и уравнение x₂ = 1/2х₁.

откуда находим х₁ = 8 /5, x₂ = 4 /5, L = 16 /5 + 4 /5 = 4 .

Ответ. Глобальный минимум, равный нулю, достигается в точке O (0, 0), глобальный максимум, равный 4 , — в точке А(8 /5, 4 /5).

Задача с нелинейной целевой функцией и линейной системой ограничений

Пример 2. Найти глобальные экстремумы функции

Решение. Область допустимых решений — OABD (рис. 28.2). Линиями уровня будут окружности с центром в точке O₁. Максимальное значение целевая функция имеет в точке D(9, 0), минимальное — в точке O₁ (2, 3). Поэтому

Ответ. Глобальный максимум, равный 58, достигается в точке D (9, 0), глобальный минимум, равный нулю, — в точке O₁ (2, 3).

Пример 3. Найти глобальные экстремумы функции

Решение. Область допустимых решений — OABD (рис. 28.3). Линии уровня представляют собой окружности с центром в точке O₁ (6, 3). Глобальный максимум находится в точке O (0, 0) как самой удаленной от точки O₁. Глобальный минимум расположен в точке Е, находящейся на пересечении прямой 3x₁ + 2x₂ = 15 и перпендикуляра к этой прямой, про­веденного из точки O₁.

Найдем координаты точки Е: так как угловой коэффици­ент прямой 3x₁ + 2x₂ = 15 равен -3/2, то угловой коэффициент перпендикуляра O₁Е равен 2/3. Из уравнения прямой, прохо­дящей через данную точку О₂ с угловым коэффициентом 2/3, получим

находим координаты точки Е: х₁ = 51/13, x₂ = 21/13, при этом L(Е) = 1053/169.

Координаты точки Е можно найти следующим образом: дифференцируя выражение (x₁ — 6) 2 + (x₂ — 3) 2 как неявную функцию по x₁, получим

Приравниваем полученное значение к тангенсу угла накло­на прямой 3x_­1 + 2x₂ = 15:

Решаем систему уравнений

получим координаты точки Е: х₁ = 51/13, x₂ = 21/13.

Ответ. Глобальный максимум, равный 52, находится в точке O (0, 0). Глобальный минимум, равный 1053/169, нахо­дится в точке E (51/13, 21/13).

Задача с нелинейной целевой функцией и нелинейной системой ограничений

Пример 4. Найти глобальные экстремумы функции

Решение. Областью допустимых решений является ок­ружность с радиусом 4, расположенная в первой четверти (рис. 28.4). Линиями уровня будут окружности с центром в точке O₁ (2, l).

Глобальный минимум достигается в точке O₁. Глобальный максимум — в точке А (0, 4), при этом

Ответ. Глобальныи минимум, равный нулю, достигается в точке O₁ (2, l), глобальный максимум, равный 13, находится в точке А (0, 4).

Пример 5. Найти глобальные экстремумы

Решение. Область допустимых решений не является вы­пуклой и состоит из двух частей (рис. 28.5). Линиями уровня являются окружности с центром в точке O (0, 0).

Найдем координаты точек А и В, решая систему

Получим А (1, 4), В (4, 1). В этих точках функция имеет гло­бальные минимумы, равные 17. Найдем координаты точек D и Е, решая системы

откуда получаем D (2/3, 6) и L(D) = 328/9, E (7, 4/7) и L(E) = 2417/49.

Ответ. Целевая функция имеет два глобальных миниму­ма, равных 17, в точках А (1, 4) и B (4, 1), глобальный макси­мум, равный 2417/49, достигается в точке E (7, 4/7).

studopedia.org — Студопедия.Орг — 2014-2021 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.005 с) .

Источник