Составители:
Рубрика:
32
критерий останова, гарантирующий отклонение результата x
0max
на ве-
личину, не более наперед заданной.
16. Бинарное решение задач линейного программирования
методом ветвей и частичных решений
(теоретическое обоснование)
Выбор оборудования и распределение операций по рабочим местам
решаются с помощью задач линейного программирования, в которых
переменные являются бинарными, т. е. принимают двоичные значения.
В общем виде задача ставится так:
максимизировать
1
n
j
j
j
cx
=
∑
(52)
при ограничениях
1
,
n
ij j i
j
ax b
=
≤
∑
i = 1, 2, …, m, (53)
где условия целочисленности сведены к
x
j
= {0, 1}, j = 1, 2, 3, … , n. (54)
Если учитывать лишь условие (54), то существует 2
n
возможных
выбора значений (x
1
, x
2
, …, x
n
). Разумеется, многие из них недопусти-
мы из-за линейных ограничений (53), и лишь очень небольшое число
являются допустимыми. Рассмотрим некоторое подмножество x
j
, в ко-
тором каждому
x
j
поставлено в соответствие определенное числовое
значение (нуль или единица). Такое подмножество называется частич-
ным решением. Переменные, не вошедшие в частичное решение, назы-
ваются свободными. Любой конкретный набор числовых значений сво-
бодных переменных называется дополнением соответствующего частич-
ного решения. Если частичное решение содержит s переменных, то су-
ществует 2
n–s
дополнения. В рассматриваемом алгоритме каждому час-
тичному решению соответствует неразвернутая вершина дерева реше-
ний. Возможные дополнения для некоторой неразвернутой вершины
порождают дополняющие ветви. Если к некоторому моменту получено
Страницы
- « первая
- ‹ предыдущая
- …
- 30
- 31
- 32
- 33
- 34
- …
- следующая ›
- последняя »
