Есть несколько государств. Есть набор критериев оценки.
Для каждого из государств и каждого критерия высчитывается значение этой оценки.
Рассмотрим государство Альфия. В нем планируется составить рейтинг государств. Рейтинг планируется организовать по принципу средневзвешенной оценки, т.е.
Рейтинг(государство) = вес1 * Критерий1ДляЭтогоГосударства + ... + весi * КритерийiДляЭтогоГосударства
Еще до начала этой задачи, критерии были подобраны таким образом, что для Альфии нет абсолютно доминирующего государства, т.е. любое государство хотя бы по одному признаку хуже Альфии. (потому что государство, лучшее по всем критериям, всегда окажется выше Альфии в рейтинге любой средневзвешенной оценке)
Вопрос: всегда ли в таком случае найдется такой набор весов, чтобы Альфия оказалось первой? Если да, то почему, если нет, то каковы необходимые и достаточные условия существования таких весов?
Здравствуйте, Nuseraro, Вы писали:
N>Есть несколько государств. Есть набор критериев оценки. N>Для каждого из государств и каждого критерия высчитывается значение этой оценки.
N>Рассмотрим государство Альфия. В нем планируется составить рейтинг государств. Рейтинг планируется организовать по принципу средневзвешенной оценки, т.е. N>Рейтинг(государство) = вес1 * Критерий1ДляЭтогоГосударства + ... + весi * КритерийiДляЭтогоГосударства N>Еще до начала этой задачи, критерии были подобраны таким образом, что для Альфии нет абсолютно доминирующего государства, т.е. любое государство хотя бы по одному признаку хуже Альфии. (потому что государство, лучшее по всем критериям, всегда окажется выше Альфии в рейтинге любой средневзвешенной оценке)
N>Вопрос: всегда ли в таком случае найдется такой набор весов, чтобы Альфия оказалось первой? Если да, то почему, если нет, то каковы необходимые и достаточные условия существования таких весов?
Не всегда. Есть 3 государства A, B и C, с оценками (a1, a2), (b1, b2) и (c1, c2) соответственно, причем a1 < b1; a2 > b2 и a1 > c1; a2 < c2. Первый коэффициент wlog можно принять за 1. Чтобы A оказалось первым, требуется подобрать k так, чтобы
a1 + k*a2 > b1 + k*b2
a1 + k*a2 > c1 + k*c2
т.е
(a1-c1)/(c2-a2) > k > (b1-a1)/(a2-b2)
что возможно только если (a1-c1)/(c2-a2) > (b1-a1)/(a2-b2).
N>Вопрос: всегда ли в таком случае найдется такой набор весов, чтобы Альфия оказалось первой? Если да, то почему, если нет, то каковы необходимые и достаточные условия существования таких весов?
Перейдём к векторам, так удобнее будет.
Каждому государству соответствует вектор признаков f
Есть вектор весов w.
Рейтинг государства Омегия r(Омегия) = f_Омегия·w
Разница между рейтингами Альфии и Омегии d(Омегия) = r(Омегия)-r(Альфия) = (f_Омегия-f_Альфия)·w
Поэтому сразу перейдём к относительным признакам s_Омегия = f_Омегия-f_Альфия
Известно, что в каждом векторе s хотя бы одна компонента отрицательная.
Теперь соберём признаки всех государств в стопку, получим матрицу S = { s_1, s_2, ... }
Получим относительные рейтинги одним махом: d = S·w
Наша задача — получить d, у которого все компоненты отрицательные.
Это мы пришли к основной задаче линейного программирования.
S·w < 0
Ну, а поскольку я в линейном программировании не силён, то просто приведу пример, когда решения нет.
Два государства, у одного признаки [1,-1], у другого — [-1,1].
Как ни крути, получаем систему неравенств
+w1-w2 < 0
-w1+w1 < 0
которая, очевидно, несовместная.
Здравствуйте, Nuseraro, Вы писали:
N>Вопрос: всегда ли в таком случае найдется такой набор весов, чтобы Альфия оказалось первой? Если да, то почему, если нет, то каковы необходимые и достаточные условия существования таких весов?
Перекуём баги на фичи!
