Ю2.21

Задача: Имеются три раствора полезного вещества с концентрациями [latex]p_{1}, p_{2}, p_{3}[/latex] каждый и стоимостью [latex]s_{1}, s_{2}, s_{3}[/latex] соответственно. Можно ли смешать их так, чтобы получить раствор с заданной концентрацией [latex]p[/latex] наименьшей стоимости [latex]s[/latex]?
Указание. Пусть [latex]\alpha_{1}, \alpha_{2}, \alpha_{3}[/latex]- долевые содержания растворов в смеси. Тогда для получения заданной концентрации [latex]p[/latex] необходимо [latex]p_{1}\alpha_{1} + p_{2}\alpha_{2} + p_{3}\alpha_{3}=p[/latex].
Кроме того, нужно учесть условие «комплектности смеси»: [latex]\alpha_{1} + \alpha_{2} + \alpha_{3} = 1[/latex]; [latex]\alpha_{1} \ge 0; \alpha_{2} \ge 0; \alpha_{3} \ge 0;[/latex] При этих условиях необходимо найти наименьшее значение линейной функции: [latex]s = \min _{ \alpha_{1}, \alpha_{2}, \alpha_{3} } { ( s_{1} \alpha_{2} + s_{2} \alpha_{2} + s_{3} \alpha_{3} ) }[/latex].
С учётом ограничений задача сводится к минимизации линейной функции одного переменного на отрезке, однако искомые выражения и условия получаются достаточно громоздкими. Можно показать, что в решении будут участвовать не более двух растворов. Тогда достаточно среди вариантов:
а) [latex]\alpha_{1} = 0[/latex];
б) [latex]\alpha_{2} = 0[/latex];
в) [latex]\alpha_{3} = 0[/latex];
Выбрать оптимальный, и затем провести необходимые расчеты.
Тесты

1 2 3 p s Комментарий
[latex]p_{i}[/latex] 0 0 0 0 10 Пройден
[latex]s_{i}[/latex] 10 12 14
[latex]p_{i}[/latex] 0 10 30 0 10 Пройден
[latex]s_{i}[/latex] 10 20 30
[latex]p_{i}[/latex] 15.3 49.2 51.6 37.4 29.56 Пройден
[latex]s_{i}[/latex] 40 10 20
[latex]p_{i}[/latex] 30 30 30 40 Impossible Пройден
[latex]s_{i}[/latex] 25 14 40
[latex]p_{i}[/latex] 20.3 20.3 20.3 20.3 30 Пройден
[latex]s_{i}[/latex] 30 40 50
[latex]p_{i}[/latex] 30 40 50 20 Impossible Пройден
[latex]s_{i}[/latex] 19 31 22
[latex]p_{i}[/latex] 20 60 80 40 40 Пройден
[latex]s_{i}[/latex] 60 20 100
[latex]p_{i}[/latex] 20 50 90 50 15.71 Пройден
[latex]s_{i}[/latex] 10 80 20
[latex]p_{i}[/latex] 10 60 90 62.5 62.5 Пройден
[latex]s_{i}[/latex] 190 10 20

Код программы:

Метод решения:
Задача сводится к решению системы уравнений:
[latex]\begin{cases} p_{1} \alpha_{2} + p_{2} \alpha_{2} + p_{3} \alpha_{3} = p,\\ \alpha_{1} + \alpha_{2} + \alpha_{3} = 1,\\ s = \min _{ \alpha_{1}, \alpha_{2}, \alpha_{3} } { ( s_{1} \alpha_{2} + s_{2} \alpha_{2} + s_{3} \alpha_{3} ) }; \end{cases}[/latex]

Безусловно, из первых двух уравнений системы можно найти общее решение с одной свободной переменной. Тогда для решения понадобится отыскать минимум линейной функции одной переменной. Тем не менее, автор задачника советует упростить расчеты и сократить список переменных до двух. Поочерёдно приравнивая к нулю каждую из них, рассчитаем стоимость всех возможных вариантов состава смеси и выберем самый дешевый.

Аналитическое решение в данном случае тривиально:
[latex]\begin{cases} p_{i} \alpha_{i} + p_{j} \alpha_{j} = p,\\ \alpha_{i} + \alpha_{j} = 1; \end{cases} \Rightarrow \begin{cases} \alpha_{i} = \frac { p-p_{i} } { p_{j}-p_{i} },\\ \alpha_{j} = 1-\alpha_{i}; \end{cases} s = s_{i} \alpha_{i} + s_{j} \alpha_{j};[/latex]

Для большей наглядности применяется функция c_price (calculate price), в теле которой рассмотрены крайние случаи:
1) Если [latex]p_{1}=p_{2}=p[/latex], то нужно выбрать раствор наименьшей стоимости.
2) Если [latex]p_{1}=p_{2} \ne p[/latex], то решений нет.
3) Если [latex]p_{1}=p \ne p_{2}[/latex], то [latex]s = s_{1}[/latex]. Аналогично в случае [latex]p_{2}=p \ne p_{1}[/latex].
4) Если доля раствора в смеси [latex]\alpha 1[/latex], то решений нет.

Подробности реализации:
Использовались данные целочисленного типа и данные с плавающей точкой (двойной точности, т.к. в условии задачи нет ограничений на значения переменных, лежащие в рамках здравого смысла.

Протестировать работу программы можно по ссылке.
Реализация на Java: http://ideone.com/qTQpMX

Іванов Вячеслав Володимирович
Іванов Вячеслав Володимирович

Latest posts by Іванов Вячеслав Володимирович (see all)

7 thoughts on “Ю2.21

  1. — Пожалуйста, сделайте ссылку на код в IDEone
    — Приведите полный текст из задачника (с указанием). Иначе не понятен выбор метода решения.
    — Вы использовали массивы и циклы. А задача на ветвление. Всего лишь нужно вычислить состав для трёх случаев (если возможно) и выбрать наименьший. Получается несколько простых условий.

    Меня будет мучить совесть, но я не могу зачесть. Извините. Нужно переделать.
    Постарайтесь уложиться в не очень большое число строк кода. Лучше в 3-4 раза меньше чем сейчас.

    • У меня есть вариант решения, который короче данного примерно в три раза, но разве это не решение уже другой задачи? Размер программы обусловлен тем, что в указании сказано вначале выбрать переменные, а уже потом проводить какие-либо вычисления, что закономерно усложняет алгоритм. Иначе «указание» усложняет проблему на порядок, что не очень-то педагогично, хотя, разумеется, может иметь место.

  2. Давайте подумаем, как немного упростить решение. Представим концентрации в виде точек на координатной прямой. Чтобы задача решалась необходимо, чтобы комбинируемые концентрации находились по разные стороны от нужной. А стороны всего две. Значит какие-то две концентрации могут оказаться по одну сторону от р. Т.е. один вариант можно отбросить без вычислений если никакая концентрация не равна требуемой.

    Последняя фраза автора намекает, что можно без вычислений отбросить ещё один вариант. Тогда действительно функция не понадобится. Вы знаете как это можно сделать?

    Оценку я поставил, но мелкие «придирки» нужно поправить обязательно:
    — Уже во второй программе наблюдаю у Вас сдвиги на 1 позицию правее или левее чем нужно. Вы так что-то выделяете? Или это случайность?
    — Зачем «спрятали» if в 17-й строке?

    • Мысли по этому поводу были, некоторые присутствовали в первой версии решения, но у меня код при таком подходе становился только более громоздким. Безусловно, должны быть способы именно упростить задачу, но я их, признаю, пока что не вижу, хотя и буду искать.
      1) То ли я подсмотрел у Артура Леонидовича, то ли видел в одном из вариантов рекомендаций по оформлению кода, но сдвигом на одну позицию я выделял условные операторы. Впрочем, читаемости коду это не особо прибавляет.
      2) Не подумал, что в маленьком окошке строка «спрячется», в редакторе такой проблемы не возникало. В любом случае, я где надо добавил фигурные скобки и перенос строки.