 |
 |
 |
 |
|
 |
 |
85
и содержит только целые компоненты, то, значит, найдено решение основной задачи (4.2)-(4.3). В
противном случае среди всех концевых подмножеств, полученных как на предыдущих (D
i
(q)
), так и на
текущем (D1
(q)
, D2
(q)
) этапе, выбирается область с наибольшей оценкой
?(
D
i
(q)
). Она становится текущим
рассматриваемым подмножеством (D
(q+1)
). Далее производится перенумерация концевых множеств и
вычислительный процесс итеративно повторяется.
При решении задач (D1
(q)
, f) и (D2
(q)
, f) можно воспользоваться результатами решения предыдущей
задачи (D
(q)
,
f). Рассмотрим вариант организации вычислительного процесса на примере задачи (
D
1
(q)
, f)
(для (
D
2
(q)
, f) он выглядит аналогично с точностью до знаков неравенств).
Предположим, что на последнем шаге решения задачи (D
(q)
, f) был получен оптимальный базис
?.
Без
ограничения общности можно считать, что он состоит из первых m столбцов матрицы задачи. Данное
предположение делается исключительно для обеспечения наглядности дальнейшего изложения и оче-
видно, что его выполнения можно всегда добиться за счет простой перенумерации векторов а
j
. По
аналогии с предыдущим параграфом введем обозначения для элементов матрицы задачи (D
(q)
, f) и ее
вектора ограничений относительно базиса
ˆ
:
Тогда система ограничений задачи (D
(q)
, f) может быть представлена как
а получаемая на ее основе система ограничений задачи (
D
1
(q)
, f) как
или
где х
n+1
?
0
— фиктивная переменная, которой соответствует нулевой коэффициент в целевой функции,
добавляемая для преобразования неравенства в строгое равенство.
Очевидно, что 1
?
k
?m
, т. к. небазисные компоненты оптимального плана (m+1
?
j
?n
) равны нулю, т. е.
являются заведомо целочисленными. Тогда с учетом сделанных предположений о виде базиса
ˆ
можно
записать: