'''{{ Задача о минимуме|definition=Необходимо найти минимальную/максимуме скалярного произведения''' - задача о нахождении минимальной/максимальной максимальную суммы попарных произведений для двух заданных упорядоченных наборов чисел. }} == Решение == Скалярным произведением двух упорядоченных последовательностей чисел будем называть число <tex>S = x_1 y_1 + x_2 y_2 + \ldots + x_m y_m</tex> {{ Теорема |about=о минимуме/максимуме скалярного произведениях<ref name = "wiki" /> |statement=Минимум скалярного произведения достигается при сопоставлении возрастающей последовательности <tex>x_1 \ldots x_m</tex> и убывающей последовательности <tex>y_1 \ldots y_m</tex>. При сопоставлении возрастающей <tex>y_1 \ldots y_m</tex> достигается максимум.
== Решение =|proof=Скалярным произведением двух упорядоченных последовательностей Будем считать, что последовательность <tex>x_i</tex> отсортирована по возрастанию. Покажем, что если существуют пары чисел будем называть число <tex>S = x_1 y_1 (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_2 y_2 x_j y_j > x_j y_i + x_i y_j</tex>, а следовательно данное скалярное произведение не является минимальным.Проделав такую замену для всех <tex>y_i < y_j</tex> получим отсортированную по убыванию последовательность <tex>y_i</tex>, и скалярное произведение такой пары последовательностей будет минимальным.. + x_m y_mАналогично для получения максимума во всех парах чисел <tex>(x_i, y_i)</tex>{{Теорема|about=о минимумеи <tex>(x_j, y_j)</максимуме скалярного произведения|statement=Минимум скалярного произведения достигается при сопоставлении возрастащей последовательности tex>, таких что <tex>x_1..x_mx_i < x_j</tex> и убывающей последовательности <tex>y_1..y_my_i > y_j</tex>. При сопоставлении возрастающим нужно менять местами <tex>x_1..x_my_i</tex> и <tex>y_1..y_my_j</tex> достигается максимум.В результате получится отсортированная по возрастанию последовательность, и скалярное произведение в таком случае будет максимальным.}}
Данная теорема нашла себе практическое применение в теории [[Теорема Радо-Эдмондса (жадный алгоритм)|proof=1. Будем считать, что <tex>x_i</tex> отсортирована по возрастаниюматроидов]] и [[Flow shop| расписаний]].
2. Покажем, что если существуют пары чисел == Примечания == <texreferences>(x_i, y_i)</tex> и <tex>(x_j, y_j)</tex>, такие что <texref name = "wiki">x_i < x_j<[https:/tex> и <tex>y_i < y_j</tex>, то скалярное произведение можно уменьшить, поменяв местами <tex>y_i<ru.wikipedia.org/tex> и <tex>y_j<wiki/tex>. Так так<tex>(x_j Перестановочное_неравенство Википедия {{-- x_i)(y_j - y_i) > 0}} Перестановочное неравенство]</texref>, то <tex>x_i y_i + x_j x_j > x_j y_i + x_i y_j</texreferences>.
3.Проделав такую замену для всех <tex>y_i < y_j</tex> получим отсортированную по убыванию последовательность <tex>y_i</tex>==См.также==* [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]* [[Теорема Кэли]]* [[Матричное представление перестановок]]
4. Аналогично для получения максимума во всех парах чисел <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>. В результате получится отсортированная по возрастанию последовательность.}}== Литература Источники информации ==1. * Романовский И. В. Дискретный анализ. — 3-е изд. — СПб.: Невский Диалект; БХВ-Петербург, 2003. — С. 320— ISBN 5-7940-0114-3. [[Категория: Дискретная математика и алгоритмы]] [[Категория: Комбинаторика ]] [[Категория: Свойства комбинаторных объектов]]
