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

Введение

Нередко для решения каких-либо задач приходиться прибегать к помощи математической модели. Математическая модель – это представления одного или нескольких реальных объектов в математической форме, то есть в виде систем математических уравнений, формул, неравенств. Замена реально существующего объекта исследования его математической моделью называется математическим моделированием. Метод решения задач с помощью математического моделирования используют во многих сферах: в экономике, в физике, в медицине, в программировании и в подобных. Одним из видов математического моделирования является динамическое программирование. Динамическое программирование ­– это решение задачи путем разбиения её на простые подзадачи. Каждая последующая часть задачи рекурсивна предыдущей. При этом такой способ помогает на каждой итерации отслеживать изменения параметров всей системы что помогает найти в ней закономерности.

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

Цели данной работы:

Сформулировать идею демонического программирования.

Определить роль динамического программирования в экономике

Решить несколько экономических задач методом динамического программирования

Идея динамического программирования

Определение «динамическое программирование» впервые было сформулировано американским математиком Ричардом Беллманом в 1940-х годах. Он писал, что ответ на задачу может быть получен путем решения задачи, которая является подзадачей первой. В 1954 году Ричард Беллман уточнил это определение до современного варианта.

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

Оптимальная подструктура задачи означает, что ответ на определенную задачу может быть найден путем нахождения оптимального решения задачи меньшего размера (подзадачи). Например, простая задача про графы, где надо найти кротчайший путь от точки А до точки F имеет оптимальную подструктуру.

Рис.1 - Кратчайший путь (A, C, E, D, F) между вершинами A и F во взвешенном ориентированном графе.

Суть задачи в том, чтобы найти наименьшее расстояние из вершины А до вершины F. Поэтапно, начиная с вершины А находим наименьшую сумму расстояний полученные на предыдущих шагах. Сумма в вершине А = 0, т.к. это начала пути. Сумма в вершине В = 4, как видно по графе. До вершины С существует 2 пути: А-С и A-B-C. Сумма А-С=2, а сумма A-B-C=9, т.к. известно что до вершины В существует только 1 путь и он равен 4, а из В-С=5. Суммируя 2 этих пути и получаем 9. Далее необходимо выбрать наименьший (оптимальный) путь из А в С и получаем ответ 2, т.к. А-С < A-B-C или 2<9. Аналогичное решение и для следующих вершин. В итоге будет найден минимальный путь от А-F

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

Решение экономической задачи методом динамического программирования.

Рассмотрим одну из простых экономических задач про распределения инвестиций.

Некая фирма выделила 5 миллионов рублей для модернизации 4-х предприятий. Для достижения заданной цели было создано 3 альтернативах проекта для каждого j-того предприятия. Каждый проект имеет суммарные затраты и доход. Для каждого предприятия нужно выбрать такие проекты, чтобы фирма получила максимальную выгоду, при это каждое предприятие может реализовать не более 1 проекта.

Таблица 1- Задача распределения 5 миллионов рублей.

x_j – номер проекта для j-того предприятия.

c_j – суммарные расходы от проекта для j-того предприятия в миллионах рублей.

R_j – Доход от реализованного проекта для j-того предприятия в миллионах рублей в год.

Из таблицы видно, что 1 проект является пустым, т.е R и c =0;

Один из самых простых способов решения данной задачи, является обычный перебор. Если количество вариантов не велико, то данный способ вполне приемлемы, но в данном случаи легче всего эту задачу решить методом динамического программирования.

Суть решения такова: сначала строим таблицу для четвертого предприятия и вписываем туда расчеты доходов при использовании каждого проекта и находим наиболее выгодные варианты для каждого состояния системы. Затем строим таблицу для третьего и четвертого предприятия и опять находим наиболее оптимальные варианты для 3 предприятия. Далее по аналогии со вторым и первым предприятием и в конце для всех 4-х. Всего будет 4 этапа.

Таблица 2 - Этап 4. Предприятие 4.

Опишем построение таблицы 2. В таблице рассчитывается максимальный доход предприятия от проекта x {R₄(x₄)} для 6 различных состояний y₄∈ {0, . . . , 5} – это количество расходов. Заметим, что y₄ <= 5. Из таблицы 1 видно, что при x_j = 1 на всех 4 предприятиях доходы и расходы от данного проекта равны нулю. Отмечаем это в столбце «x₄ = 1» для каждого состояния y. В столбце «x₄ = 2», аналогично заносим данные из таблицы 1. Заметим, что при y₄ = 0 и y₄ = 1 в столбце «x₄ = 2» стоят прочерки. Поскольку из таблицы 1 видно, что на реализацию проекта на данном предприятии необходимо с₄=2 (затрат), то столбце «x₄ = 2» заполняем, начиная с y₄=2. Далее переходим к столбцу «Оптимальное решение». Здесь необходимо для каждого состояния y₄ найти функцию f₄(y₄) (максимальное число дохода среди различных проектов x₄) и x₄^* (номер проекта x₄, где было найден максимальный доход). Например, что при состоянии y₄ = 0 в столбце {R₄(x₄)} стоит 0 и черта. Ноль больше чем ничего (-), поэтому в столбце «Оптимальное решение» записываем максимальное число дохода(f₄(0) =0) и номер проекта с максимальным доходом(x₄^*(0) =1). Найдены оптимальные решения для всех состояний системы

Далее переходим к 3 этапу, где рассчитывается максимальный доход от 4 и 3 предприятия в совокупной работе.

Таблица 3 - Этап 3. Предприятие 4 и 3.

Опишем построение таблицы 3. Как и во второй таблице записываем 6 различных состояния системы y₃∈ {0, . . . , 5}. Также x₃ = 1, 2 и 3 соответствуют номерам проектов. Стоит заметить, что добавляется x₃ =3, т.к по таблице 1 видно, что третье производство имеет возможность реализовать третий проект. В отличие от 2 таблицы максимальный доход предприятия рассчитывается по формуле R₃(x₃) + f₄(y₃ − c₃(x₃)), где R₃(x₃)– доход третьего предприятия при реализации различный проектов, а второе слагаемое формулы f₄(y₃ − c₃(x₃)) – предыдущий этап решения. Значения для f₄(y₃ − c₃(x₃)) берутся предыдущей таблицы 4 этапа. Заметим, что y₃ − c₃(x₃) = y₄., т.к если из денег y₃, выделенных на предприятие 3 и 4 вычесть c₃(x₃) (затраты на реализацию проекта 3 на предприятие 3 ), то в результате останется y₄ для предприятия 4. Столбец «x₃ = 1» соответствует пустому проекту, следовательно y₄= y₃ и в качестве второго слагаемого приписываем оптимальный доход f₄(y₄) = 3. Не забываем, что на реализацию проекта на 4 предприятии уже потрачено 2 миллиона рублей, следовательно, и прибавляем второе слагаемое начиная со второго состояния(y₃=2). Далее столбец «x₃ = 2» при y₃=0 нет возможности реализовать 2 проект на 3 предприятие, т.к. c₃(x₂)=1. С y₁=1 по y₁=2 хватает средств только на реализацию проекта на 3 предприятии, уже с y₁=3 прибавляем слагаемое f₄(y₄) = 3 полученное на предыдущем. Аналогично рассчитывается столбец «x₃ = 3». В столбце «Оптимальное решение» по аналогии со 2 таблицы рассчитываем f₃(y₃) и x₃^* для каждого состояния. Далее находим оптимальные решения для всех состояний системы f₃(y₃) и x₃^*.

Аналогично решаются и последние 2 этапа.

Этап 2. Предприятия 2, 3 и 4:

Таблица 4 - Этап 2. Предприятие 4, 3 и 2.

Заметим, что на этапе y₃=4 получается несколько оптимальных решений – это при x₂ = 1 и при x₂ = 2. В обоих случаях получается максимальный доход f₂(y₂) = 9.

Этап 1. Предприятия 1, 2, 3 и 4.

Таблица 5. Этап 1 - Предприятие 4, 3, 2 и 1.

Когда все 4 таблицы заполнены и для каждого предприятия были найдены оптимальные решения, осталось найти оптимальное решение для всей задачи. Из последней таблицы 5 видно, что оптимальное решение для первого предприятия это реализация второго проекта с доходом 12 миллионов рублей(f₁(5) = 12, x₁^* = 2 ). Из 1 таблицы находим характеристики 2 проекта для 1 предприятия – это (c₁(2), R₁(2)) = (1, 3). Следовательно, на предприятия 2, 3 и 4 остается 5-1=4 миллиона рублей. Подчеркиваем данное оптимальное решение.

Далее анализируем таблицу 4 2 этапа и подчеркиваем y₂ = 4. Подчеркиваем f₂(y₂) = 9 и x₂^*= 1. На предприятия 3 и 4 остается 4-0=4 миллиона рублей.

Анализируем таблицу 3 3 этапа и подчёркиваем y₃ = 4, f₂(y₂) = 9 и x₂^*= 3. Затраты на реализацию 3 проекта на 3 предприятия составляет c₃ =2. На 4 предприятие остается 4-2= 4 миллиона рублей.

Как потратить оставшиеся 2 миллиона рублей оптимально видно по таблице 2 видно сразу. Подчеркиваем y₄ = 3, f₂(y₂) = 3 и x₂^*= 2.

В Итоге получаем ответ как эффективно потратить 5 миллионов на 4 предприятия. Для этого на каждом предприятии выбираем проекты x^*=(2,1,3,2). При таком распределении будет получен максимальных доход фирмы в размере 12 миллионов рублей.

Данную задачу легко проверить просто просуммировать все затраты от реализаций выбранных проектов на конкретные предприятия (∑_jс_j(x_j^*) = 1+0+2+2 = 5 миллионов рублей) и общий доход фирмы((∑_jR_j(x_j^*) = 3+0+6+3 = 12 миллионов рублей ).

Данная задача имеет 2 оптимальных решения. Второе оптимальное решение x^*₍₂₎ = (2,2,2,1).

Заключение.

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

Список литературы:

Визгунов Н.П., Динамическое программирование в экономических задачах c применением системы SciLab — Нижний Новгород.: 2011. - 70 с: ил.

works.doklad.ru [Электронный ресурс] / Динамическое программирование - Режим доступа : https://works.doklad.ru/view/WUzmvLAKQE8.html , свободный. – Загл. с экрана.

lms2.sseu.ru [Электронный ресурс] / Динамическое программирование - Режим доступа : https://lms2.sseu.ru/courses/eresmat/course2/razd3_2/par3_1k2.htm, свободный. – Загл. с экрана.

masters.donntu.org [Электронный ресурс] / Динамическое программирование в решении производственных задач - Режим доступа : http://masters.donntu.org/2007/fvti/toichkina/diss/index.htm#newness, свободный. – Загл. с экрана.

Беллман Р. Динамическое программирование. — М.: Изд-во иностранной литературы, 1960.

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