Математическое программирование и моделирование экономических процессов. Коробов П.Н. - 235 стр.

UptoLike

ВУЗ: 

СПбГЛТУ | Санкт-Петербург

Составители: 

Рубрика: 

235
∑∑
= =
∂
∂
=∇
m
i
n
j
ij
ij
x
x
Xf
XXf
1 1
0
0
.
)(
)( (6.55)
Однако постоянные коэффициенты
ij
ij
x
xf
c
∂
∂
=
)(
0
нам неизвестны, поскольку
неизвестна точка Х
0
, в которой достигается абсолютный минимум функции (6.55).
Поэтому для нахождения точки X
0
задача решается последовательными сближениями. На
первом этапе полагаем
ϕ
i
(x
i
)=0 и решаем линейную транспортную задачу минимизации
целевой функции
[ ]
∑∑
= =
+=
m
i
n
j
ijiji
xtcXf
1 1
1
.)0()(
(6.56)
при ограничениях (6.53). Обозначим оптимальный план этой задачи через
)1(
0
X . На втором
этапе вычисляем постоянные коэффициенты
ij
ij
x
xf
c
∂
∂
=
)(
)1(
0
)1(
и решаем задачу минимизации
линейной функции
∑∑
= =
=∇
m
i
n
j
ijij
xcXXf
1 1
)1()1(
0
,)(
(6.57)
и таким образом получаем оптимальный план
)2(
0
X . Таким же образом перейдем от
)2(
0
X к
третьему оптимальному плану
)3(
0
X .
Этот процесс очень быстро сходится к некоторому опорному плану
0
X , который
и принимается за решение задачи.
Проверка эффективности способа на ряде примеров показывает, что указанные
сближения приводят к точному абсолютному минимуму целевой функции (6.52), в случае
если матрица размеров mxn
А=[c
i
(0)+t
ij
]
mxn
(6.58)
имеет существенно различные по величине элементы. Если элементы матрицы А
постоянны (особенно по строкам) или относительно мало различаются, то указанный
процесс может сходиться к локальному минимуму, отличному от абсолютного. Однако в
этом случае целевая функция изменяется относительно мало и полученный локальный
минимум, не совпадающий с абсолютным минимумом, может приниматься за хороший
приближенный результат.
Применение указанного процесса сближения для выпуклой функции, как правило, не
сходится к одному опорному плану. Здесь обычно получается цикл повторяющихся
опорных планов и за приближенное решение задачи принимается тот опорный план в
цикле, который дает наименьшее значение целевой функции (6.52). Если процесс
сближений сойдется к одному опорному плану, то это будет означать, что абсолютный
минимум находится в одной из вершин выпуклого многогранника и мы получаем (в силу
единственности решения для выпуклой функции) точное решение задачи. Для ускорения
сходимости к циклу опорных планов следует на первом этапе минимизировать линейную
форму
[
]
∑∑
= =
=
m
i
ij
n
j
iij
xxcXf
1 1
*
,)(max)( (6.59)

Страницы