х
В
,
х
В
= (
х
1
,…,
х
m
).
Вектор коэффициентов при базисных переменных
c
B
= (
c
1
,…,
с
m
).
Поскольку небазисные переменные равны нулю, значение целевой
функции
Z
, соответствующее начальному допустимому базисному реше-
нию, равно:
=
+
+ ⋯ +
,
,
,
,
≥ 0
.
Рассмотрим применение метода Гаусса – Жордана для решения сле-
дующей задачи: максимизировать
Z
= 3
x
1
+ 2
x
2
при ограничениях:
−
+ 2
≤ 4
,
3
+ 2
≤ 14
,
Электронный
архив
УГЛТУ
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)
Для решения этих задач разработаны методы, основанные на теореме
Куна - Таккера, которые представляют собой обобщение метода множите-
лей Лагранжа для определения экстремума при наличии ограничений,
представляющих не только равенства, но и неравенства.
Достарыңызбен бөлісу: |