Составители:
Рубрика:
234
Подставляя выражение (6.51) в целевую функцию (6.50), получаем следующую
транспортную задачу. Требуется найти абсолютный минимум функции
∑∑
= =
=
m
i
n
j
ijiij
xxcXf
1 1
)()(
(6.52)
где
С
ij
(x
i
) = с
i
(0)+t
ij
±
ϕ
i
(x
i
)x
i
,
- затраты на поставку при условиях:
∑∑
==
=≤=≥
m
i
jij
n
j
iijiij
bxaxxx
11
.;;0
(6.53)
Для большинства видов производства целевая функция (6.52) монотонно
возрастает и вогнута. В этом случае произведение
ϕ
i
(x
i
)x
i
берется со знаком минус. Для
некоторых же видов производства, например при эксплуатации месторождений полезных
ископаемых и т. п., функция (6.52) также монотонно возрастает и выпукла; здесь
ϕ
i
(x
i
)x
i
берется со знаком плюс. В последнем случае функция имеет единственный минимум,
который, однако, не будет являться одним из опорных планов. Оптимальный план может
быть любой граничной точкой выпуклого многогранника, определяемого системой
ограничений (6.53). В первом случае, когда целевая функция (6.52) вогнута оптимальный
план обязательно является одним из опорных планов. Но в этом случае задача имеет
множество локальных минимумов, каждый из которых также достигается в некоторой
вершине выпуклого многогранника, представляющей некоторый опорный план.
В случае вогнутости целевой функции задача в принципе может быть решена при
помощи перебора всех опорных планов с вычислением целевой функции для каждого
опорного плана. Однако при достаточно большом числе неизвестных x
ij
такой перебор
практически неосуществим ввиду колоссально большого количества вычислений.
Существуют методы решения транспортных задач с выпуклой целевой функцией
или с вогнутой при
ϕ
i
(x
i
) = k
i
, равной постоянной величине. Однако алгоритмы этих
1
Этот способ, предложенный В.В. Шерстобитовым, был доложен на Всесоюзной
межвузовской научно-технической конференции, проходившей в июне 1968 года в
Московском лесотехническом институте. Нами впервые был опубликован в 1974 г. [9].
методов очень сложные и требуют вычислений большого объема. Поэтому мы
рассмотрим лишь весьма простой приближенный способ решения транспортной задачи
при любых дифференцируемых однотипных функциях
ϕ
i
(x
i
), при которых целевая функция
(6.52) является выпуклой или вогнутой
1
. Рассмотрим сначала случай вогнутости целевой
функции, соответствующий уменьшению производственных затрат на единицу продукции
при увеличении ее объема. Этот случай наиболее соответствует действительности.
Для вогнутой функции, заданной на выпуклом множестве, имеет место неравенство
(
)
(
)
),()(
000
XfXfXXXf −≥−⋅∇ (6.54)
из которого видно, что любой локальный минимум функции f(X) в точке X
0
одновременно
является локальным минимумом линейной функции ∇f(X
0
)X в той же точке X
0
. Значит, и
точки абсолютного минимума для этих функций также совпадают. Таким образом, задача
абсолютной минимизации функции (6.52) при условиях (6.53) оказывается эквивалентной
задаче абсолютной минимизации линейной функции.
Страницы
- « первая
- ‹ предыдущая
- …
- 232
- 233
- 234
- 235
- 236
- …
- следующая ›
- последняя »
