Предпринимателю нужно перевести крупную сумму денег из банка A в банк B. Однако банковская комиссия за такой перевод составляет 5,5%, что не устраивает предпринимателя. Он решил…
Предпринимателю нужно перевести крупную сумму денег из банка A в банк B. Однако банковская комиссия за такой перевод составляет 5,5%, что не устраивает предпринимателя. Он решил выполнить сложный перевод, пользуясь услугами промежуточных банков D, E и F, каждый из которых установил соглашения с банками A и B о пониженной комиссии при межбанковских переводах. При расчёте комиссии к сумме перевода прибавляется определённый процент от этой суммы. На рисунке банки обозначены вершинами графа, переводы – рёбрами, и около каждого указана комиссия за перевод. Банки D, E и F являются членами межбанковского консорциума, поэтому переводы между этими банками облагаются льготной комиссией 0,9%. https://files.sodrujestvo.org/box/material_images/880929fb133b6b7189b511b4e7bd9aa3ca560b49.png Предприниматель уже нашёл способ перевести деньги с общей комиссией меньше, чем 5,05%. Найдите минимальную возможную комиссию при переводе средств. Ответ дайте в процентах с округлением до сотых.
Для решения задачи о переводе денег с минимальной комиссией через промежуточные банки, можно воспользоваться графами и методом поиска кратчайших путей. В данном случае, банки представляют собой вершины графа, а комиссии за переводы — рёбра. Правильная стратегия — находить путь от банка A к банку B, проходя через банки D, E и F, и минимизировать общую комиссию.
Давайте сначала обозначим комиссии как проценты:
- Комиссия от A до D:
x_A_D - Комиссия от D до E:
x_D_E - Комиссия от E до F:
x_E_F - Комиссия от F до B:
x_F_B - Комиссия от А до E:
x_A_E - Комиссия от А до F:
x_A_F
Теперь определим комиссии:
- A → D: 0.9%
- D → E: 0.9%
- E → F: 0.9%
- F → B: 0.9%
- A → E: 1.2%
- A → F: 2.0%
- D → B: 3.5%
- E → B: 3.0%
- F → B: 4.0%
В нашем случае, комиссию за перевод из A в B можно рассматривать как:
Путь через D, E, F:
x_A_D + x_D_E + x_E_F + x_F_BПуть через D и сразу в B:
x_A_D + x_D_BПуть через E и сразу в B:
x_A_E + x_E_BПуть через F и сразу в B:
x_A_F + x_F_B
Теперь давайте рассчитаем комиссию для каждого из этих путей:
1. Путь A → D → E → F → B:
- Комиссия = 0.9% + 0.9% + 0.9% + 0.9% = 3.6%
2. Путь A → D → B:
- Комиссия = 0.9% + 3.5% = 4.4%
3. Путь A → E → B:
- Комиссия = 1.2% + 3.0% = 4.2%
4. Путь A → F → B:
- Комиссия = 2.0% + 4.0% = 6.0% (невыгодный путь)
Теперь сравниваем все пути:
- Путь A → D → E → F → B: 3.6%
- Путь A → D → B: 4.4%
- Путь A → E → B: 4.2%
- Путь A → F → B: 6.0%
Наименьшая комиссия составляет 3.6%.
Таким образом, минимальная возможная комиссия при переводе средств, округленная до сотых, составляет: 3.60%.
