Решить графоаналитическим методом:
min
j (X
) = - 2x1
- x2
+ x3
(1)
при
2x1
- x2
+ 6x3
£ 12 (2)
3x1
+ 5x2
- 12x3
= 14 (3)
3x1
+ 6x2
+ 4x3
£ 18 (4)
X
³ 0 (5)
Решение:
Этап 1. Построение пространства допустимых решений
Выбираем прямоугольную систему координат: по горизонтальной оси указываем значения переменной х1
, по вертикальной - х2
.
Далее рассмотрим условие неотрицательности переменных (5):
х1
³ 0; х2
³ 0 и х3
³ 0. (6)
Первые два ограничения показывают, что пространство допустимых решений будет лежать в первом квадранте (т.е. выше оси х1
и правее оси х2
).
Из ограничения (3) можно получить:
3x1
+ 5x2
- 12x3
= 14®, (7)
с учётом условия неотрицательности третьей переменной (6) получаем новое ограничение:
. (8)
Подставляем в ограничение (2) найденное значение (7):
2x1
- x2
+ 6x3
£ 12®®
® (9)
Подставляем в ограничение (4) найденное значение (7):
3x1
+ 6x2
+ 4x3
£ 18®®
® (10)
Чтобы учесть получившиеся ограничения, проще всего заменить неравенства на равенства, в результате чего получим уравнения прямых:
,
,
.
Теперь рассмотрим, как графически интерпретируются неравенства. Каждое неравенство делит плоскость (х1, х2) на два полупространства, которые располагаются по обе стороны прямой, которая соответствует данному неравенству.
Точки плоскости, расположенные по одну сторону прямой, удовлетворяют неравенству (допустимое полупространство), а точки, лежащие по другую сторону - нет.
На рис.1 допустимые полупространства показаны стрелками.
Рис.1. Нахождение оптимального решения
Ограничения:
(А)
(В)
(С)
х2
³ 0 (D)
х1
³ 0 (E)
Этап 2. Нахождение оптимального решения
Точки пространства допустимых решений, показанного на рис.1, удовлетворяют одновременно всем ограничениям. Это пространство ограничено отрезками прямых, которые соединяются в угловых точках F, G, H, J и K.
Любая точка, расположенная внутри или на границе области, ограниченной ломаной FGHJK, является допустимым решением, т.к удовлетворяет всем ограничениям.
Пространство допустимых решений содержит бесконечное число точек.
Нахождение оптимального решения требует определения направления убывания целевой функции (1):
min
j (X
) = - 2x1
- x2
+ x3
.
Подставляем в целевую функцию найденное значение (7):
.
Мы приравниваем j (X
) к нескольким убывающим значениям, например, (- 5) и (- 8). Эти значения, подставленные вместо j (X
) в выражение целевой функции, порождают уравнения прямых; для значений (- 5) и (- 8) получаем уравнения прямых:
и
.
На рис.2 эти прямые показаны штрих-пунктирными линиями, а направление убывания целевой функции - толстой стрелкой.
Целевая функция может убывать до тех пор, пока прямые, соответствующие убывающим значениям этой функции, пересекают область допустимых решений. Точка пересечения области допустимых решений и прямой, соответствующей минимально возможному значению целевой функции, и будет точкой оптимума.
Из рис.2 видно, что оптимальное решение соответствует точке Н. Эта точка является местом пересечения прямых (В) и (С), поэтому её координаты х1
и х2
находятся как решение системы уравнений, задающих эти прямые:
Решением этой системы будет:
х1
= 5,36
х2
= 0,16
при этом значение целевой функции равно:
.
Ответ:
Оптимальное решение:
х1
= 5,36
х2
= 0,16
при этом значение целевой функции равно:
j (X
) = - 10,621.
Рис.2. Нахождение оптимальной точки
Задача 2
Найти экстремумы методом множителей Лагранжа.
Решение проиллюстрировать графически.
extr
j (X
) = 3x1
2
+ 2x1
+ 2x2
2
+ 4x2
x3
при
x1
+ 2x2
= 19
x1
+ 2x3
= 11.
Решение:
Обозначим:
g1
(X
) = x1
+ 2x2
- 19 = 0,g2
(X
) = x1
+ 2x3
- 11 = 0.
Функция Лагранжа имеет вид:
Отсюда получаем необходимые условия экстремума в виде системы уравнений:
,
,
,
,
.
Решаем систему уравнений через определители.
Главный определитель:
.
Матрица - столбец левой части системы (свободных членов):
.
Находим остальные определители:
,
,
,
,
.
Находим решение системы уравнений:
,
,
,
,
.
Таким образом, получили одну экстремальную точку.
Определяем матрицу Гессе:
Матрица Гессе положительно определена, поэтому в найденной точке
функция Лагранжа L (X, l) выпуклая и, следовательно, имеется минимум.
Для графической иллюстрации решения выразим координату х3
из функции ограничения g2
(X
):
g2
(X
) = x1
+ 2x3
- 11 = 0®.
Подставим полученное значение в целевую функцию:
j (X
) = 3x1
2
+ 2x1
+ 2x2
2
+ 4x2
x3
= 3х1
2
+ 2х1
+2х2
2
+ 4х2
(5,5 - 0,5х1
) =
j (X
) = 3х1
2
+ 2х1
+2х2
2
+ 22х2
- 2х1
х2
.
Получили общее уравнение кривой второго порядка.
Для получения канонического вида уравнения производим поворот системы координат, освобождаясь от члена, содержащего произведение координат.
Угол поворота j определяется формулой:
® радиан.
При этом получаем новые координаты y и z:
,
.
Подставляем полученные выражения в целевую функцию:
j (y, z) = 3х1
2
+ 2х1
+2х2
2
+ 22х2
- 2х1
х2
=
,
,
,
Получили уравнение эллипса с центром в точке (y = 1,3633; z = - 7,1513), причём линии симметрии эллипса наклонены на угол j = - 0,55375 радиан относительно начальной системы координат х1
х2
.
Пересчитаем координаты центра эллипса:
,
.
На рис.3 представлено графическое решение.
Из рисунка видно, что график уравнения ограничения g1
(X) (сплошная линия) пересекается с графиком целевой функции (пунктирная линия) в точке А.
В точке А с координатами (5,2222; 6,8889) имеется минимум целевой функции:
j (X
) = 3х1
2
+ 2х1
+2х2
2
+ 22х2
- 2х1
х2
= 3 * 5,22222 + 2 * 5,2222 + 2 * 6,88892 + 22 * 6,8889 - 2 * 5,2222 * 6,8889 = 266,78.
На рис.3 представлена также целевая функция с большим значением:
j (X
) = 350.
Центр эллипсов обозначен точкой N (-2,6; -6,8).
Ответ:
Имеется одна точка экстремума - точка минимума (5,2222; 6,8889), при этом целевая функция равна:
j (X
) = 266,78.
Рис.3. Графическое решение
Задача 3
Решить на основе условий Куна-Таккера.
Решение проиллюстрировать графически.
extr
j (X
) = (x1
- 4) 2
+ (x2
- 3) 2
при
3x1
- 2x2
£ 18
x1
+ 2x2
£ 8
Решение:
Обозначим:
g1
(X
) = 3x1
- 2x2
- 18 £0,g2
(X
) = - x1
+ 2x2
- 8 £ 0.
Записываем функцию Лагранжа:
L (X
, S
, l
) = j (X
) - l1
(g1
(X
) + S1
2
) - l2
(g2
(X
) + S2
2
)
L (X
, S
, l
) = (x1
- 4) 2
+ (x2
- 3) 2
- l1
(3x1
- 2x2
- 18 + S1
2
) - l2
(- x1
+ 2x2
- 8 + S2
2
)
Отсюда получаем необходимые и достаточные условия экстремума (условия Куна-Таккера) в виде системы уравнений:
,
,
,
,
,
.
Принимаем (из третьего и четвёртого уравнений системы):
.
Из первого и второго уравнений системы находим:
®,
®,
из пятого уравнения системы:
®,
из шестого уравнения системы:
®.
Таким образом, нашли первую точку:
.
Принимаем (из третьего и четвёртого уравнений системы):
.
Из первого и второго уравнений системы находим:
®,
®,
подставляем в пятое уравнение системы:
®®.
определяем координаты точки экстремума:
,
,
из шестого уравнения системы:
®.
Таким образом, нашли вторую точку:
.
Принимаем (из третьего и четвёртого уравнений системы):
.
Из шестого уравнения системы находим:
®.
Подставляем полученное значение в первое и второе уравнения системы:
®,
®®®
,
.
Подставляем также полученные значения в пятое уравнение системы:
®
.
Таким образом, нашли третью точку:
.
В результате решения системы получаем векторы:
.
В точке
имеем глобальный минимум целевой функции:
j (X
) = (x1
- 4) 2
+ (x2
- 3) 2
= (4- 4) 2
+ (3- 3) 2
= 0.
В точке
имеем седловую точку целевой функции:
j (X
) = (x1
- 4) 2
+ (x2
- 3) 2
= (6,7692- 4) 2
+ (1,1538 - 3) 2
= 11,077.
В точке
имеем седловую точку целевой функции:
j (X
) = (x1
- 4) 2
+ (x2
- 3) 2
= (2,8 - 4) 2
+ (5,4 - 3) 2
= 7,2.
Для графической иллюстрации решения строим графики уравнений ограничений:
g1
(X
) = 3x1
- 2x2
- 18 £ 0®,
g2
(X
) = - x1
+ 2x2
- 8 £ 0®
сплошные линии на рис.4 (графики прямых).
Также строим графики целевой функции для седловых точек (проходящих через точки А и В)
j (X
) = (x1
- 4) 2
+ (x2
- 3) 2
= 11,077®,
j (X
) = (x1
- 4) 2
+ (x2
- 3) 2
= 7,2®,
и минимума (проходящий через точку С) - центр окружности:
j (X
) = (x1
- 4) 2
+ (x2
-
= 0®
пунктирные линии на рис.4 (графики окружностей с центром в точке ).
Из графика также видно, что глобального максимума целевой функции достичь невозможно!
Рис.4. Графическое решение
Ответ:
В точке С
имеем глобальный минимум целевой функции:
j (X
) = 0.
В точке В
имеем седловую точку целевой функции:
j (X
) = 11,077.
В точке А
имеем седловую точку целевой функции:
j (X
) = 7,2.
Глобального максимума целевой функции достичь невозможно.
Задача 4
Получить выражение расширенной целевой функции (РЦФ) и составить блок-схему алгоритма численного решения задачи методом штрафных функций в сочетании с одним из методов безусловной минимизации.
Решить задачу средствами MSExcel.
Решение проиллюстрировать графически.
max
j (X
) = - 2x1
+ 8x2
- x1
2
- x2
2
(11)
при
x1
+ 2x2
£ 12
x1
+ x2
³- 8
X
³ 0
Решение:
Обозначим ограничения:
,
.
Расширенная целевая функция образуется суммой целевой функции и штрафной функции :
.
Штрафную функцию можно построить различными способами. Однако, наиболее часто она имеет вид:
Где
, - некоторые константы, представляющие собой весовые коэффициенты.
Используя штрафную функцию, последовательно переходим от одной расчётной точки к другой до тех пор, пока не получим приемлемое решение. При этом координаты последующей точки находим по формуле:
(12)
где - шаг вычислений.
Чем меньше и , тем быстрее находится приемлемое решение, однако точность определения его снижается. Поэтому итерационный процесс обычно начинают при сравнительно малых значениях и но, продолжая его, эти значения постепенно увеличивают.
Итак, процесс нахождения решения задачи включает следующие этапы:
1. Определение исходного допустимого решения.
2. Выбор шага вычислений.
3. Нахождение по всем переменным частных производных от целевой функции и функций, определяющих область допустимых решений.
4. По указанной ранее формуле (12) нахождение координаты точки, определяющей возможное новое решение.
5. Проверка, удовлетворяют ли координаты найденной точки системе ограничений задачи. Если нет, то переход к следующему этапу. Если координаты найденной точки определяют допустимое решение, то исследование необходимости перехода к последующему допустимому решению. В случае такой необходимости переход к этапу 2, в противном случае найдено приемлемое решение задачи.
6. Установка значения весовых коэффициентов и переход к этапу 4.
Построим область допустимых решений задачи (рис.5) и линии уровня, определяемые целевой функцией (11):
j (X
) = - 2x1
+ 8x2
- x1
2
- x2
2
j (X
) = - (x1
2
+ 2х1
+ 1) + 1 - (x2
2
- 8х2
+ 16) + 16
j (X
) = - (x1
+ 1) 2
+ 1 - (x2
- 4) 2
+ 16
j (X
) = - (x1
+ 1) 2
- (x2
- 4) 2
+ 17 (13)
Рис.5. Область допустимых решений
Линиями уровня служат окружности с центром в точке (- 1;
4). Точка касания одной из этих окружностей с областью допустимых решений и является искомой точкой максимального значения целевой функции.
Из вида целевой функции (11) можно сделать вывод:
чем дальше точка от центра окружности, тем всё меньше целевая функция, максимум целевой функции будет в точке касания окружности вертикальной оси координат (точка А на рис.5), при этом: х1
= 0; х2
= 4
и целевая функция равна:
j (X
) = - (x1
+ 1) 2
- (x2
- 4) 2
+ 17 = - (0 + 1) 2
- (4 - 4) 2
+ 17 = 16.
Для решения задачи методом штрафных функций примем начальное значение допустимого решения:
.
Выбираем шаг вычислений и точность вычислений:
и .
Принимаем весовые коэффициенты:
,
.
Находим частные производные от целевой функции:
,
.
Определяем частные производные от функций ограничения:
,
,
,
.
Далее вычисления производим в среде MSExcel (см. файл KursR_MMPR. xls) по алгоритму, приведённому на Рис.6.
Результат расчёта в среде MSExcel представлен в таблице 1.
Графически решение представлено на рис.5, где максимальное значение целевой функции достигается в точке А (0;
4) и равно:
j (X
) = 16.
Ответ:
В точке
имеем глобальный максимум целевой функции:
j (X
) = 16.
Таблица 1. Результат расчёта в среде MSExcel
№ итерации |
Текущее | Допустимое решение? |
Новое | Допустимое решение? |
Конец расчёта? |
||||||||||
| 1 | 3 | 2 | Да | 0 | 0 | -8 | 4 | -1 | -2 | -1 | 1 | 2,2 | 2,4 | Да | Нет |
| 2 | 2,2 | 2,4 | Да | 0 | 0 | -6,4 | 3,2 | -1 | -2 | -1 | 1 | 1,56 | 2,72 | Да | Нет |
| 3 | 1,56 | 2,72 | Да | 0 | 0 | -5,12 | 2,56 | -1 | -2 | -1 | 1 | 1,048 | 2,976 | Да | Нет |
| 4 | 1,048 | 2,976 | Да | 0 | 0 | -4,096 | 2,048 | -1 | -2 | -1 | 1 | 0,6384 | 3,1808 | Да | Нет |
| 5 | 0,6384 | 3,1808 | Да | 0 | 0 | -3,2768 | 1,6384 | -1 | -2 | -1 | 1 | 0,31072 | 3,34464 | Да | Нет |
| 6 | 0,31072 | 3,34464 | Да | 0 | 0 | -2,62144 | 1,31072 | -1 | -2 | -1 | 1 | 0,048576 | 3,475712 | Да | Нет |
| 7 | 0,048576 | 3,475712 | Да | 0 | 0 | -2,09715 | 1,048576 | -1 | -2 | -1 | 1 | 0 | 3,58057 | Да | Нет |
| 8 | 0 | 3,58057 | Да | 0 | 0 | -2 | 0,838861 | -1 | -2 | -1 | 1 | 0 | 3,664456 | Да | Нет |
| 9 | 0 | 3,664456 | Да | 0 | 0 | -2 | 0,671089 | -1 | -2 | -1 | 1 | 0 | 3,731565 | Да | Нет |
| 10 | 0 | 3,731565 | Да | 0 | 0 | -2 | 0,536871 | -1 | -2 | -1 | 1 | 0 | 3,785252 | Да | Нет |
| 11 | 0 | 3,785252 | Да | 0 | 0 | -2 | 0,429497 | -1 | -2 | -1 | 1 | 0 | 3,828201 | Да | Нет |
| 12 | 0 | 3,828201 | Да | 0 | 0 | -2 | 0,343597 | -1 | -2 | -1 | 1 | 0 | 3,862561 | Да | Нет |
| 13 | 0 | 3,862561 | Да | 0 | 0 | -2 | 0,274878 | -1 | -2 | -1 | 1 | 0 | 3,890049 | Да | Нет |
| 14 | 0 | 3,890049 | Да | 0 | 0 | -2 | 0,219902 | -1 | -2 | -1 | 1 | 0 | 3,912039 | Да | Нет |
| 15 | 0 | 3,912039 | Да | 0 | 0 | -2 | 0,175922 | -1 | -2 | -1 | 1 | 0 | 3,929631 | Да | Нет |
| 16 | 0 | 3,929631 | Да | 0 | 0 | -2 | 0,140737 | -1 | -2 | -1 | 1 | 0 | 3,943705 | Да | Нет |
| 17 | 0 | 3,943705 | Да | 0 | 0 | -2 | 0,11259 | -1 | -2 | -1 | 1 | 0 | 3,954964 | Да | Нет |
| 18 | 0 | 3,954964 | Да | 0 | 0 | -2 | 0,090072 | -1 | -2 | -1 | 1 | 0 | 3,963971 | Да | Да |
Литература
1. Таха Х. Введение в исследование операций, 7-е издание: Пер с англ. - М.: Изд. дом "Вильямс", 2005.
2. Реклейтис Г., Рэйвиндран А., Рэгсдел К. Оптимизация в технике / Пер. с англ. В 2-х кн. Кн.1 - М: Мир, 1986.; Кн.2 - М: Мир, 1986.
3. Акулич И.Л. Математическое программирование в примерах и задачах: Учебное пособие. - М.: Высшая школа, 1986.