IX Международная студенческая научная конференция Студенческий научный форум - 2017

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

Немалую роль в экономике играет динамическое программирование – один из разделов математического программирования, в котором процесс решения может быть разбит на отдельные этапы. Динамическое программирование помогает найти оптимальное решение для экономических задач: равномерное распределение ресурсов, определение пути наименьшей стоимости. Например:

«Турист решил отправиться из города Q₁ в город Q₁₆. К конечному пункту он может добраться разными путями. На каждом маршруте расположены по 6 мелких населенных пунктов, расстояние между которыми не одинаковое. Туристу необходимо спланировать маршрут так, чтобы километраж был минимальным».

Решение:

Отметим, что любой путь из пункта Q₁ в пункт Q₁₆ включает 6 шагов (на рисунке каждый шаг это стрелочка). Начнем поиск оптимального маршрута от конечного пункта, положив n = 1.

f₁₍₁₄) = с₁₄,₁₆ = 3; f₁₍₁₅) = с_15,16 = 5.

n = 2.

Определим f₂ в пунктах Q₁₁, Q₁₂), Q₁₃:

f₂(11) = с₁₁,₁₄ + f₁(14) = 4 + 3 =7;

f₂(12) = min{с₁₂,₁₄ + f₁(14); с₁₂,₁₅ + f₁(15)} = с₁₂,₁₄ + f₁(14) = 2 + 3 =5;

f₂(13) = с₁₃,₁₅ + f₁(15) = 9 + 5 =14.

Видим, что маршрут во втором шаге проходит через пункт Q₁₂, потому пункты Q₇, Q₁₀. Q₁₁, Q₁₃ не входят в маршрут.

n = 3.

Третий шаг содержит пункты Q₈, Q₉ (пункты Q₇ и Q₁₀ не входят в маршрут):

f₃(8) = с₈,₁₂ + f₂(12) = 4 + 5 =9;

f₃(9) = с₉,₁₂ + f₂(12) = 7 + 5 = 12;

n = 4.

4-й шаг содержит пункты Q₄, Q₅, Q₆:

f₄(4) = с₄,₈ + f₃(8) = 2 + 9 =11;

f₄(5) = min{ с₅,₈ + f₃(8); с₅,₉ + f₃(9)} = с₅,₈ + f₃(8) = 2 + 9 = 11;

f₄(6) = с₆,₉ + f₃(9) = 1 + 12 =13;

n = 5.

f₅(2) = min{с₂,₄ + f₄(4); с₂,₅ + f₄(5) }= с₂,₄ + f₄(4) =5 + 11 = 16;

f₅(3) = с₃,₅ + f₄(5) = 1+11 = 12.

n = 6.

f₆(1) = min{с₁,₂ + f₅(2); с₁,₃ + f₅(3) } = с₁,₃ + f₅(3) = 4+12 =16или

f₆(1) = с₁,₃ + f₅(3) = с₁,₃ + с₃,₅ + f₄(5) = с₁,₃ + с₃,₅ + с₅,₈ + f₃(8) = с₁,₃ + с₃,₅ + с₅,₈ + с₈,₁₂ + f₂(12) = с₁,₃ + с₃,₅ + с₅,₈ + с₈,₁₂ + с₁₂,₁₄ + f₁(14) =с₁,₃ + с₃,₅ + с₅,₈ + с₈,₁₂ + с₁₂,₁₄ + с₁₄,₁₆и оптимальный путь определен: Q₁- Q₃- Q₅- Q₈- Q₁₂- Q₁₄- Q₁₆.

Код для цитирования: Скопировать