Составители:
Рубрика:
27
Можно показать, что, выполнив шаг 1, получаем решение задачи в виде
x
0
+ x
2
+ 3x
3
= 39;
x
1
+ 4/7x
2
+ 1/7x
3
= 1+ 6/7. (42)
Поскольку значение x
1
– дробное, нужно добавить отсекающее огра-
ничение с коэффициентами, равными дробным частям коэффициентов
из равенства (3), взятых с отрицательным знаком:
– 4/7x
2
– 1/7x
3
+ x
4
= – 6/7, (43)
где x
4
– вторая дополняющая переменная.
Выполняя шаг 2, решаем задачу линейного программирования (42),
дополнив ее ограничением (43). Новое оптимальное решение выража-
ется уравнениями
x
0
+ (2+3/4)x
3
+ (1+3/4) x
4
= (37+1/2);
x
1
+ x
4
= 1;
x
2
+ 1/4x
3
– (1 + 3/4)x
4
= – 1/2. (44)
Поскольку x
2
– дробное, составим новое отсекающее уравнение,
пользуясь дробными коэффициентами последней строки из решения (44):
– 1/4x
3
– 1/4x
4
+ x
5
= – 1/2. (45)
Выполняя шаг 3, решаем задачу линейного программирования (42),
дополнив ее ограничением (45). Новое оптимальное решение выража-
ется уравнениями
x
0
+ x
1
+ 11x
5
= 33;
– x
1
+ x
3
x
5
= 1;
2x
1
+ x
2
+ x
5
= 3;
x
1
+ x
4
= 1. (46)
Поскольку полученное решение x
1
= 0, x
2
= 3 и x
3
= 1 – целочислен-
ное, поставленная задача является решенной.
14. Метод ветвей и границ
Это мощный метод нелинейной оптимизации, дающий точное реше-
ние. Используется для алгоритмических целевых функций f(x), где x∈A.
Для определения
m
in (
)
xA
fx
∈
находят нижнюю границу f(x), которую обо-
значим через G(f(x), A). Она должна обладать следующими свойствами:
Страницы
- « первая
- ‹ предыдущая
- …
- 25
- 26
- 27
- 28
- 29
- …
- следующая ›
- последняя »
