Изменения

|definition=задача о нахождении минимальнойНеобходимо найти минимальную/максимальной максимальную суммы попарных произведений для двух заданных упорядоченных наборов чисел.

Скалярным произведением двух упорядоченных последовательностей чисел будем называть число <tex>S = x_1 y_1 + x_2 y_2 + ... \ldots + x_m y_m</tex>

|about=о минимуме/максимуме скалярного произведениях<ref>[http://ru.wikipedia.org/name = "wiki" /Перестановочное_неравенс.. Транс-неравенство или перестановочное неравенство]</ref> |statement=Минимум скалярного произведения достигается при сопоставлении возрастащей возрастающей последовательности <tex>x_1..\ldots x_m</tex> и убывающей последовательности <tex>y_1..\ldots y_m</tex>. При сопоставлении возрастающей <tex>y_1..\ldots y_m</tex> достигается максимум.

Будем считать, что последовательность <tex>x_i</tex> отсортирована по возрастанию. Покажем, что если существуют пары чисел <tex>(x_i, y_i)</tex> и <tex>(x_j, y_j)</tex>, такие что <tex>x_i < x_j</tex> и <tex>y_i < y_j</tex>, то скалярное произведение можно уменьшить, поменяв местами <tex>y_i</tex> и <tex>y_j</tex>. Так как в нашем случае <tex>(x_j - x_i)(y_j - y_i) > 0</tex>, то <tex>x_i y_i + x_j y_j > x_j y_i + x_i y_j</tex>, а следовательно данное скалярное произведение не является минимальным. Проделав такую замену для всех <tex>y_i < y_j</tex> получим отсортированную по убыванию последовательность <tex>y_i</tex>, и скалярное произведение такой пары последовательностей будет минимальным. Аналогично для получения максимума во всех парах чисел <tex>(x_i, y_i)</tex> и <tex>(x_j, y_j)</tex>, таких что <tex>x_i < x_j</tex> и <tex>y_i > y_j</tex> нужно менять местами <tex>y_i</tex> и <tex>y_j</tex>. В результате получится отсортированная по возрастанию последовательность, и скалярное произведение в таком случае будет максимальным.

Данная теорема нашла себе практическое применение в теории [[Теорема Радо-Эдмондса (жадный алгоритм)|матроидов ]] и [[Flow shop| расписаний]].

== Примечание Примечания == <references><ref name = "wiki">[https://ru.wikipedia.org/wiki/Перестановочное_неравенство Википедия {{---}} Перестановочное неравенство]</ref></references>

== Литература См. также==* [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]* [[Теорема Кэли]]* [[Матричное представление перестановок]] == Источники информации ==