Математика · объяснение и практика

Как выбрать наименее затратное целое решение по знаку коэффициента

Как выбрать оптимальную пару из целых решений: подставить полное семейство в линейную стоимость, определить направление изменения и не спутать допустимость с минимумом.

Синяя и оранжевая половины складываются в целый круг.

В теме Теория чисел: углубление · Учебная карта

В маршруте Новые структуры целой арифметики · 10 тем

Главная мысль

После отбора всех допустимых целых решений подставьте их параметрическую запись в стоимость. Получится C(t)=A+Bt на конечном целом промежутке. При B>0 минимум находится на левом конце, при B<0 — на правом, а при B=0 все допустимые пары имеют одинаковую стоимость.

Допустимая пара ещё не является лучшей

Уравнение расхода может разрешать несколько сочетаний двух видов предметов. Проверка целого равенства отвечает, подходит ли сочетание, но не выбирает самое дешёвое. Сначала нужны все допустимые пары: найденная наугад пара не доказывает минимума. В этой статье полная однопараметрическая серия уже построена, а ограниченный целый промежуток её параметра установлен.

Пусть x=x₀+ut и y=y₀+vt, где t — целое от L до U включительно. Для заданных цен p и q стоимость равна px+qy. Подстановка даёт C(t)=px₀+qy₀+(pu+qv)t. Это новое условие выбора среди подходящих решений. Число предметов и их стоимость являются разными величинами: меньшее x не обязательно означает меньшую общую сумму.

Сравнить соседние значения стоимости

При увеличении t на единицу стоимость меняется ровно на B=pu+qv. Положительное B означает возрастание, отрицательное — убывание. Поэтому на непустом конечном промежутке достаточно выбрать соответствующий край. Здесь не нужен перебор всего списка, но нужен аргумент, что промежуток действительно включает все допустимые решения.

Рассмотрим 6x+10y=60 при неотрицательных целых x и y. Полная серия x=5t, y=6−3t допускает t=0,1,2. Зададим стоимость C=2x+5y в условных единицах. Тогда C(t)=30−5t: дополнительный шаг уменьшает сумму на пять. Минимум достигается при t=2, то есть x=10, y=0, и равен 20. Исходное равенство при этом сохраняется.

Пример

Проверьте минимум непосредственным сравнением трёх допустимых пар в этой модели.

Для (0;6), (5;3), (10;0) стоимости равны соответственно 30, 25 и 20. Совпадение с выбором правой границы подтверждает расчёт; округление произвольной действительной пары здесь не применялось.

Разобрать равенство цен и границы метода

Если в той же серии задать C=3x+5y, получится постоянная стоимость 30: коэффициент при t равен нулю. Тогда все три допустимые пары оптимальны. Нельзя назвать единственной лучшей ту, которую первой выписали. Дополнительный критерий, например меньшее число предметов, допустим только при явном добавлении в условие.

При пустом промежутке выбирать нечего: задача не имеет допустимого решения. На единственной допустимой точке минимум уже определён независимо от B. Для нелинейной стоимости, скидки после порога или нескольких независимых целых параметров правило одного крайнего t без нового доказательства не действует. Это точная учебная модель выбора, а не оценка настоящих цен и не совет по закупкам.

От чтения к действию

А теперь — вы

Все допустимые пары заданы x=1+4t, y=9−3t при целом t=0,1,2. Как выбрать минимум стоимости C=3x+2y?

Частые вопросы

Почему нельзя просто взять наименьшее число предметов?

Цены видов могут различаться. Оптимизируют именно указанную функцию px+qy; минимальное x, минимальное x+y и минимальная стоимость вообще не обязаны совпадать.

Что означает нулевой коэффициент при параметре?

При линейной стоимости она одинакова на всём непустом допустимом промежутке. Все соответствующие пары дают минимум; уникальность без дополнительного условия не следует.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться