Составители:
Рубрика:
35
ных переменных. Если можно установить, что не существует допусти-
мого дополнения со значением целевой функции, превосходящим оцен-
ку x
0
t
, то положить оценку x
0
t+1
= x
0
t
и вернуться к шагу 1. Иначе перей-
ти к шагу 3.
Шаг 3. Если расширенное частичное решение – полное (содержит
все n переменных), то зафиксировать его, положить оценку x
0
t+1
равной
значению целевой функции и вернуться к шагу 1. Иначе перейти к шагу 4.
Шаг 4. Выбрать любую свободную переменную x
k
, не входящую в
расширенное частичное решение. Внести две задачи в основной спи-
сок. В одной из них положить x
k
= 0, в другой x
k
= 1. Положить x
0
t+1
= x
0
t
и вернуться к шагу 1. После опустошения основного списка частичных
решений полученная оценка x
0
t
является оптимальной.
17. Бинарное решение задач линейного программирования
методом ветвей и частичных решений
(пример решения)
Максимизировать
3x
1
+ 6x
2
+ 3x
3
+ 6x
4
+13x
5
(61)
при ограничениях
– 3x
1
– 6x
2
+ 6x
3
+ 12x
4
+ 7x
5
≤ 8, i = 1; (62)
6x
1
+ 12x
2
– 3x
3
– 6x
4
+ 7x
5
≤ 8, i = 2; (63)
x
j
= {0, 1}, j = 1, 2, …, 5. (64)
Примем x
0
1
= 0, что соответствует допустимому решению, в котором
все x
j
равны нулю (x
j
= 0). Введем в основной список два частичных
решения (ЧР): ЧР1 (x
5
= 1) и ЧР2 (x
5
= 0). Выбор x
5
объясняется тем, что
при x
5
= 1 приращение оценки целевой функции является максималь-
ным.
На шаге 1 рассмотрим ЧР1. Допустимое дополнение со значением
целевой функции (ЦФ), превосходящим оценку x
0
1
= 0, должно удов-
летворять условиям (62) – (64), а также условию
– 3x
1
– 6x
2
– 3x
3
– 6x
4
– 13x
5
≤ – 1, i = 0. (65)
На шаге 2 найдем свободные переменные, значения которых опреде-
ляются только соблюдением условий (62)–(65). Применим условие (60).
Для i = 1 и k = 4 условие (60) примет вид
Страницы
- « первая
- ‹ предыдущая
- …
- 33
- 34
- 35
- 36
- 37
- …
- следующая ›
- последняя »
