Ю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

Related Images: