Н. В. Куцубина системный анализ при принятии решений

108 
−
≤ 3
, 
≥ 0,
≥ 0.
Графическое решение задачи дано на рис. 4.12. 
Приведенная к стандартной форме задача имеет вид: максимизиро-
вать 
Z
=3
x
1 
+ 2
x
2
при ограничениях 
−
+ 2
+
= 4
, 
3
+ 2
+
= 14
, 
−
+
= 3
, 
≥ 0,
≥ 0,
≥ 0,
≥ 0,
≥ 0
. 
Рис. 4.12. Графическое
представление ограничений
Представим целевую функцию и ограничения в виде таблицы 
(табл. 4.4). Базисными переменными являются 
х
3
, 
х
4
, и 
х
5
. Из таблицы бе-
рем начальное допустимое базисное решение: положив
х
1 
= 0, 
х
2 
= 0,
получим 
х
3 
= 4, 
х
4 
= 14, 
х
5
=3. Значение целевой функции 
Z
= 3
x
1 
+ 2
x
2
= 0 
(точка А). 
Таблица 4.4 
Значения целевой функции и ограничений 
Базис 
х
i
 
Постоянные 
3 
2 
0 
0 
0 
х
1
х
2
 
х
3
 
х
4
 
х
5
 
х
3
 
-1 
2 
1 
0 
0 
4 
х
4
 
3 
2 
0 
1 
0 
14 
х
5
 
1 
-1 
0 
0 
1 
3 
 
Рассмотрим новые базисные переменные 
x
3
, 
x
4
и 
x
1
(табл. 4.5). Для 
этого: 
1) прибавим третью строку к первой, чтобы исключить переменную
x
1
; 
2) умножим третью строку на (-3) и прибавим ее ко второй строке, 
чтобы исключить переменную 
x
3
; 
3) третью строку оставим без изменения. 
Электронный
архив
УГЛТУ

109 
Таблица 4.5 
Значения целевой функции и ограничений с новыми базисными данными 
Базис
 
х
1
х
2
х
3
х
4
х
5
Постоянные
 
х
3
 
0 
1 
1 
0 
1 
7 
х
4
 
0 
5 
0 
1 
-3 
5 
х
1
 
1 
-1 
0 
0 
1 
3 
Приравнивая 
х
5 
= 0 и 
х
2 
= 0, получим:
х
3 
= 7;
х
4 
= 5;
х
1 
= 3;
Z
= 3∙3 = 9 (точка В на рис. 4.12). 
Введем базисное решение 
х
2
, выведя из базиса переменную 
х
4
, для 
этого:
1) вторую строку уменьшим в 5 раз и вычтем ее из первой строки;
2) вторую строку разделим на 5;
3) разделив вторую строку на 5 и сложив ее с первой строкой, полу-
чим третью строку. 
Получим новые значения целевой функции и ограничений (табл. 4.6). 
Таблица 4.6 
Значения целевой функции и ограничений
Базис
 
х
1
х
2
х
3
х
4
х
5
Постоянные
 
х
3
 
0 
0 
1 
-1/5 
8/5 
6 
х
2
 
0 
1 
0 
1/5 
-3/5 
1 
х
1
 
1 
0 
0 
1/5 
2/5 
4 
Приравнивая 
х
4 
= 0; 
х
5 
= 0, получим: 
х
3 
= 6;
х
2 
= 1;
х
1 
= 4;
Z
C
= 3∙4 + 2∙1 = 14.
Введем переменную x
5
в базис, для этого:
1) первую строку умножим на 5/8;
2) первую строку умножим на 3/8 и прибавим вторую строку;
3) из третьей строки вычтем первую строку, разделенную на 4, полу-
чим окончательное значение целевой функции (табл. 4.7). 
Таблица 4.7 
Значения целевой функции и ограничений 
Базис
 
х
1
х
2
х
3
х
4
х
5
Постоянные
 
х
5
 
0 
0 
5/8 
-1/8 
1 
15/4 
х
2
 
0 
1 
3/8 
1/8 
0 
13/4 
х
1
 
1 
0 
-1/4 
1/4 
0 
5,2 
Электронный
архив
УГЛТУ

110 
Приравнивая 
х
3 
= 0,
х
4 
= 0, получим: 
х
5 
= 14/15;
х
2 
= 13/4;
х
1 
= 5/2;
Z
D
= 3∙5/2 + 2∙13/4 = 14. 
Максимальное значение целевой функции 
Z
= 14 находится на пря-
мой CD (см. рис. 4.12), т.е. задача имеет множественные решения. 
Анализ чувствительности в линейном программировании 
В ряде задач линейного программирования возникает необходимость 
изменять некоторые параметры системы (финансы, производственные 
мощности, ресурсы и т.п.), что приводит к изменению найденного опти-
мального решения. Для выявления этих изменений проводят анализ чув-
ствительности.
 
Если обнаруживается, что оптимальное решение можно 
значительно улучшить путем небольших изменений заданных параметров, 
то целесообразно реализовать эти изменения. Кроме того, во многих слу-
чаях оценки параметров получаются путем статистической обработки ре-
троспективных данных (например, ожидаемый сбыт, прогнозы цен и за-
трат). Оценки, как правило, не могут быть точными. Если удается опреде-
лить, какие параметры в наибольшей степени влияют на значение целевой 
функции, то целесообразно увеличить точность оценок именно этих пара-
метров, что позволит повысить надежность рассматриваемой модели и по-
лучаемого решения. 
4.5. Нелинейное программирование при решении задач 
оптимизации 
 
Нелинейное программирование применяется при решении задач,
в которых нелинейны и (или) целевая функция, и (или) ограничения в виде 
равенств и неравенств и для которых методы математического анализа 
оказываются непригодными. Нелинейное программирование представляет 
наиболее характерный метод оптимизации при проектировании машин
и технологических процессов и служит для выбора наилучшего плана
распределения ограниченных материальных, финансовых и трудовых
ресурсов.
Метод множителей Лагранжа 
Метод множителей Лагранжа применяется в тех случаях, когда целе-
вая функция и ограничения представлены нелинейными функциями не-
скольких переменных. Одним из методов решения подобных задач являет-
ся метод множителей Лагранжа, при котором задача с ограничениями пре-
образуется в элементарную задачу безусловной оптимизации, в которой 
используются некоторые неизвестные параметры, называемые множите-
лями Лагранжа.
Электронный
архив
УГЛТУ

111 
Пусть целевая функция 
N
переменных
( ;
; … ;
) → min (4.12)
при ограничении 
ℎ ( ;
; … ;
) = 0. (4.13)
По методу Лагранжа эта задача преобразовывается в следующую за-
дачу безусловной оптимизации:
( ; ) = ( ) − ℎ ( ), (4.14)
где
L
(
x; λ
) – функция Лагранжа; 
 λ
– неизвестная постоянная, называемая множителем Лагранжа; 
ограничение 
( ; ) = ( ;
; … ;
) − ℎ ( ;
; … ;
),
частные производные
= 0;
= 0;
= 0;
= 0.
Для поиска условного минимума функции (4.12) при ограничении 
(4.13) необходимо составить функцию Лагранжа (4.14), взять частные про-
изводные от этой функции и приравнять их к нулю. Из системы уравнений, 
образованных частными производными, найти точки, соответствующие 
минимуму целевой функции. Эти точки принадлежат одному из множеств: 
множеству стационарных точек или множеству точек границы. Подставив 
найденные точки в целевую функцию, получаем ее минимальное (макси-
мальное) значение.
Пример. 
Минимизировать 
Z
= 
x
1 
+ 
x
2
при ограничении
x
1
2
+
x
2
2 
= l. 
Задача решается следующим способом. 
Функция Лагранжа 
L(x; λ)
= 
f
(
x
1
+
x
2
) − 
λ
(
x
1
2
+ 
x
2
2
− 1). 
Частные производные функции Лагранжа:
= 1 − 2
= 0;
= 1 − 2
= 0;
=
+
− 1 = 0.
Эта система трех уравнений с тремя неизвестными дает следующие 
решения
. 
Из первых двух уравнений имеем 
х
1 
= 
х
2
; из третьего уравнения 
х
1,2
=±
√
. 
Максимальное и минимальное решения целевой функции:
Z
min
= - 
√
- 
√
=-
√2
; Z
max
=
√2
. 
Электронный
архив
УГЛТУ

112 
Развитием метода Лагранжа при нелинейном программировании яв-
ляется метод квадратического программирования. 
Задачи квадратического программирования характеризуются квад-
ратной зависимостью целевой функции и линейной зависимостью ограни-
чений:
Z = 
∑
+
∑
∑
→max; q
i
(x) =
∑
x
j 
≥ b
i
x
j
≥ 0. (4.15) 
Для решения этих задач разработаны методы, основанные на теореме 
Куна - Таккера, которые представляют собой обобщение метода множите-
лей Лагранжа для определения экстремума при наличии ограничений, 
представляющих не только равенства, но и неравенства. 

жүктеу/скачать 6,77 Mb.

Достарыңызбен бөлісу: