AlexnderRT
Новичок
|
    
Привет всем участникам форума!
Помогите, пожалуйста, решить задачу по метрическим пространствам. Условие задачи следующее:
Пусть X = {(x1, ..., x2) є R^m : xi >= 0, x1 + ... + x2 = 1},
а d - некоторя метрика на множестве {1, 2, ..., m}. Обозначим
Q(x, y) = {Z = zij : zij >= 0, Sum(j = 1 ... m)zij = xi, Sum(i = 1 ... m)zij = yj, для всех i, j = 1, ..., m} (то есть, для двух m-мерных векторов x и y Q(x, y) - множество матриц Z с неотрицательными элементами таких, что i-ая строчная сумма элементов матрицы равна i-тому элементу вектора x, а j-ая столбцевая сумма элементов матрицы равна j-тому элементу вектора y).
Требуется доказать, что
r(x, y) = inf ( Sum(i,j = 1, ..., m) d(i, j)*zij )
zєQ(x, y)
является метрикой.
r(x, y) = 0 <=> x = y становится очевидным, если, к примеру, рассмотреть матрицу Z и D = d(i, j) как вектора в пространстве R^m^2.
r(x, y) = r(y, x) также очевидно.
Но как доказать неравенство треугольника r(x, y) <= r(x, z) + r(z, y)?
Возможно, с помощью метода математической индукции, но как тогда получить базу индукции (для m = 2)?
Если у кого-то есть хоть какие-то идеи по решению этой задачи, пожалуйста, ответьте.
Большое спасибо.
(Сообщение отредактировал AlexnderRT 15 сен. 2008 21:25)
|
Всего сообщений: 5 | Присоединился: сентябрь 2008 | Отправлено: 14 сен. 2008 1:29 | IP
|
|
Roman Osipov 
Долгожитель
|
   
В вашей записи Sum(i,j = 1, ..., m) d(i, j)*zij есть величина постоянная для данных X, Y при данной метрике d.
Проверьте корректность записи условия.
|
Всего сообщений: 2356 | Присоединился: май 2007 | Отправлено: 14 сен. 2008 14:56 | IP
|
|
AlexnderRT
Новичок
|
Если вы имели в виду, что новая и старая метрики обозначены одной и той же буквой d, то это я уже исправил. Что касается d(i, j), где d - некоторая метрика на {1, 2, ..., m}, то D = (d(i, j)) i, j = 1 ... n - постоянная матрица.
|
Всего сообщений: 5 | Присоединился: сентябрь 2008 | Отправлено: 15 сен. 2008 21:31 | IP
|
|
AlexnderRT
Новичок
|
Насколько я понимаю,
inf ( Sum(i,j = 1, ..., m) d(i, j)*zij )
zєQ(x, y)
должен достигаться, так как Sum(i,j = 1, ..., m) d(i, j)*zij - это линейная форма от m^2 переменных, причём рассматриваемая в некоторой замкнутой области, находящейся внутри первого октанта (ввиду условий zij >= 0, Sum(j = 1 ... m)zij = xi >= 0, Sum(i = 1 ... m)zij = yj >= 0). То есть, инфимум можно заменить на минимум, так?
|
Всего сообщений: 5 | Присоединился: сентябрь 2008 | Отправлено: 15 сен. 2008 21:42 | IP
|
|
ProstoVasya
Долгожитель
|
Конечно минимум достигается. Предлагаю посмотреть на задачу с точки зрения линейного программирования (возможно, она от туда и появилась). Тогда перед нами транспортная задача (матрица d(i,j) - матрица цен перевозок единицы продукта). Неравенство треугольника становится на уровне размахивания руками очевидным. Действительно, нам надо перевезти X = {(x1, ..., xm) в Z=(z1,...,zm) за наименьшую цену, а мы по пути должны перевести товар сначала в Y=(y1,...,ym). Конечно, этот заезд скажется на цене перевозки.
Правда, не понятно причём здесь условие метрики на матрицу D = (d(i, j)).
|
Всего сообщений: 1268 | Присоединился: июнь 2008 | Отправлено: 16 сен. 2008 9:01 | IP
|
|
|
Форум
Задача по теории метрических пространств
