Элементарные решения неэлементарных задач на графах. Берзин Е.А. - 118 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

120
Например, сместив базу
2=
r
из
1
А в
4
А , для нового варианта размещения
баз
{
}
{
}
{}
4;6;
21
== kkk
r
получим (используются сроки
{}
4;6
∈
i табл. 46):
()
{}
6;65;44;43;62;61;6
0
,
0,9,0,6,16,48=
⎭
⎬
⎫
⎩
⎨
⎧
′
RЭ
jk
r
,
{}{}{} {}
5;4,6,3,2,1
2
4
1
6
==
== rr
jj
,
()
4379970, >=+=
′
Σ
RxЭ .
Примечание. Оптимальное размещение (7.13) баз совпало с
пунктами, в которые требуется доставить наиболее тяжелые грузы
()
5,6
61
== aa , что логически вполне оправдано.
Для более точного учета энергозатрат при перевозках необходимо
принимать во внимание коэффициент, опущенный в (7.11), но
позволяющий получить некоторую дополнительную информацию,
связанную с перевозками грузов. Например, если в качестве единицы
измерения веса взять вес транспортного средства (т.е. 1
=
T
a ), то при 5
=
g
(возможная загрузка транспортного средства в 5 раз больше веса
транспортного средства) коэффициент
T
k в (7.11) будет равен
4,14,01 =+=
T
k , т.е. пассивные энергозатраты составят 40 % от полезных
энергозатрат
П
ji
Э
,
(7.11). Если при прочих равных условиях вдвое
увеличить полезные энергозатраты (возвращение транспорта с полной
загрузкой), то пассивные затраты снизятся до 20 %. Дальнейшее их
снижение возможно только путем увеличения загрузки
ji
g
,
.
7.3. Поиск минимаксных точек на графе
При решении практических вопросов может возникнуть задача,
связанная с таким размещением некоторого объекта на местности, при
котором расстояние от него до самого удаленного пункта было бы по
возможности наименьшим. В качестве подобного объекта можно,
например, рассматривать пункт скорой помощи или пожарное депо.
Необходимо разместить его в такой точке
x
, чтобы наиболее удаленный от
точки пункт района был, насколько это возможно, ближе к точке
x
.
Формальная постановка задачи может быть записана в виде минимаксной
задачи:

Страницы