Новости
09.05.2023
с Днём Победы!
07.03.2023
Поздравляем с Международным женским днем!
23.02.2023
Поздравляем с Днем защитника Отечества!
Оплата онлайн
При оплате онлайн будет
удержана комиссия 3,5-5,5%








Способ оплаты:

С банковской карты (3,5%)
Сбербанк онлайн (3,5%)
Со счета в Яндекс.Деньгах (5,5%)
Наличными через терминал (3,5%)

ЗАДАЧИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ В ЭКОНОМИКЕ

Авторы:
Город:
Оренбург
ВУЗ:
Дата:
11 февраля 2017г.

В статье рассмотрены общая схема многошагового процесса, условия применения метода динамического программирования, постановка и модель задачи динамического программирования, принцип оптимальности и функция Беллмана, этапы решения задачи: условная оптимизация и безусловная оптимизация. Проведен обзор учебных пособий, в которых представлены методы динамического программирования, применяющиеся для решения различных экономических задач. В статье рассмотрены построения математических моделей динамического программирования на примере двух различных постановок задач календарного планирования трудовых ресурсов. Составлены рекуррентные соотношения для каждого этапа решения задачи о найме. Задача решена с использованием электронного процессора MS Excel. На этапе условной оптимизации значения рекуррентных формул вычислялись с помощью логической функции “ЕСЛИ”. Рассмотрены преимущества применения метода динамического программирования в экономике.

Ключевые слова: принцип оптимальности, многошаговые процессы, состояние, управление, рекуррентные формулы.

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

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

Идея метода динамического программирования, геометрическая интерпретация, требования, предъявляемые к задачам, решаемым методом динамического программирования, рекуррентные соотношения Беллмана для некоторых задач описаны во многих учебных пособиях [1, 3, 4, 5, 6, 7, 8, 9].

В учебнике К.В. Балдина, Н.А. Брызгалова, А.В. Рукосуева “Математическое программирование” рассмотрены решения задачи об оптимальном распределении однородного ресурса и задачи об оптимальной загрузке транспортного средства неделимыми предметами методом динамического программирования [1, с. 142-152].

В учебном пособии Б.А. Баллод, Н.Н. Елизаровой “Методы и алгоритмы принятия решений в экономике” дана характеристика многоэтапного управляемого процесса, представлены модели задач распределения ресурсов между предприятиями и оптимального выбора маршрута [2, с. 96-101].

Построение математической модели динамического программирования на примере задач распределения инвестициями, управления производством и запасами освящено в учебном пособии под редакцией В.А. Колемаева  и В.И. Соловьева [4, с. 76-86], также – на примере задачи распределения капитальных вложений в учебном пособии В.В. Христиановского и В.П. Щербина [10, с. 118-128].

Рассмотрены решения с помощью таблиц (вручную) задачи о найме в учебном пособии П.В. Конюховского [5, с. 93-101] и в учебном пособии под редакцией Ф.Л. Шарова [7, с. 175-181].

В учебном пособии М.А. Тынкевич представлены решения задачи о кратчайщем пути в транспортной сети, задачи управления запасами, задачи замены оборудования методом динамического программирования [8, с. 107-120].

Решения задач выбора оптимальной стратегии обновления оборудования и оптимального маршрута перевозки грузов, построения оптимальной последовательности операций в коммерческой деятельности методом динамического программирования рассмотрены в учебнике Г.П. Фомина [9, с. 361-389].

Реализацию метода  динамического программирования  рассмотрим на примере решения  задачи планирования рабочей силы или задачи о найме.

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

Задача 1.

Для функционирования некоторого предприятия в течение четырех месяцев (нумеруемых от 1 до 4) по нормам требуются следующие количества работников одинаковой квалификации: m1=3, m2=4, m3=5, m4=2.

Перед началом первого месяца (в нулевом  месяце) фактически имеется ξ0=2 сотрудника. Администрация планирует в конце каждого месяца k (кроме последнего) корректировать число работающих на величину xk, k=0,1,..4, х4=0. На прием одного сотрудника необходимо затратить 9 у.е., а на увольнение – 6 у.е. Предполагается, что расходы на содержание избыточного работника составляют 8 у.е., а в случае нехватки персонала приходится нести затраты в размере 12 у.е. за каждое вакантное место.

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

В начале решения запишем в аналитической форме функции издержек на прием-увольнение сотрудников u(x) , а также на содержание ненормативного штата g(x). С этой целью введем функции:






При использовании алгоритмов динамического программирования, если задано начальное состояние управляемой системы, то задача решается в обратном направлении, а если – конечное состояние, тo – в прямом. Наконец, если заданы как начальное, так и конечное состояния, то задача существенно усложняется.

Полагаем k=4. На данном этапе функция состояния Λ4(ξ) может быть найдена непосредственно, если учесть, что x4*= 0 и u(0)=0:

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





Расчеты проведены с помощью таблиц, которые показывают, что в третьем месяце выгоднее не брать пятого работника, а компенсировать его отсутствие дополнительными выплатами за сверхурочную работу [5, 7].

Рассмотрим подробное решение другой задачи о найме, составим ее математическую модель и решим с применением MS Excel, так как во многих учебных пособиях рассмотрены решения задач вручную [3, 4, 5, 6, 7, 8, 9], в некоторых – с применением языков программирования [10].

Задача 2.

Пусть для реализации проекта строительный подрядчик определил минимальные потребности в рабочей силе на ближайшие пять недель следующим образом: 5, 7, 8, 5 и 6 рабочих соответственно. Затраты на содержание избытка рабочей силы составляют 400 д.е. за одного рабочего в неделю, а наем рабочей силы на протяжении одной недели – 500 д.е. (независимо от количества принимаемых на работу человек) и 300 д.е. за обучение одного нового рабочего в неделю.

Как регулировать  численность рабочих в период реализации проекта, чтобы суммарные затраты были минимальными?

Решение:

b1=5, b2=7, b3=8, b4=5, b5=6, C0=500, C1=300, C2=400. 

Затраты, связанные с необходимостью дополнительного найма (xi –xi-1) рабочих:

C0+C1(xi – xi-1)= 500+300 (xi – xi-1), xi > xi-1                                    (6)

 

Затраты, связанные с необходимостью содержать избыток (xi–bi) рабочей силы

C2(xi – bi)=400 (xi – bi), xi > bi , i=1,2,3,4,5.                         (7)

 

Условная оптимизация – решение задачи в обратном направлении:

Решение задачи начинаем с последнего (5-го шага). По условию на этом этапе должны работать 6 работников.  На предыдущем шаге в штате могло быть 5 работников (необходимый  минимум), или  6 работников (с учетом численности на 5-м шаге). b5=6, x5=6; x4= {5;6}.

Функция Беллмана для последнего шага имеет вид:



Значение функции вычисляем в MS Excel с помощью логической функции “ЕСЛИ”, записав в ячейку С20, копируем в ячейку С21.

На четвертом шаге потребуется 5 работников, однако, учитывая, что на следующем этапе должны работать 6 исполнителей, в штате может быть 5 или 6 человек. В таблице 2 значения х4 = 5; 6, b4=5, x4= {5;6} ; x3=8.


На третьем шаге потребуется 8 работников, а на втором этапе в штате должно быть 7 исполнителей (необходимый минимум) или 8 исполнителей (с учетом потребностей следующего этапа). Поэтому в таблице 3 х2 = 7, 8, b3=8, x3=8; x2= {7;8}.

Запишем рекуррентную формулу:


Формула затрат – в ячейке С40, копируем в ячейку С41.

На втором шаге потребуется 7 или  8 работников (с учетом потребностей  следующего этапа).

Поэтому в таблице 4 х2 = 7, 8, х1 = 5, 6, 7, 8 (с учетом потребностей следующих этапов), b2=7, x2= {7;8} ; x1= {5,6,7;8}.

Запишем рекуррентную формулу:




Формула затрат (в строке 54 – текстовая запись) – в ячейке B50, копируем в ячейки B51 по B53,аналогично, из ячейки C50, копируем в ячейки C51 по C53.

На первом шаге потребуется 5, 6, 7 или 8 работников (с учетом потребностей следующих этапов). Поэтому в таблице 5 х1 = 5, 6,7, 8 , х0 = 0, b1=5,  x1= {5,6,7;8}.

Запишем рекуррентную формулу:





Из последней таблицы (рисунок 5) следует, минимальные суммарные затраты равны 4200 д.е. Безусловная оптимизация.

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

Поиск оптимального решения начинаем  с таблицы 5 (рисунок 5, k=1), из которой следует, что перед началом работ необходимо нанять 5 рабочих, (x1=5) стоимость равна (д.е.).500 + 5× 300 = 2000

В таблице 4 (рисунок 4, k=2) в первом столбце находим строку (x1=5), соответствующую 5-ти

рабочим на первом этапе. По числу 2200 этой строки находим в столбце х2 = 8. Следовательно, на втором этапе дополнительно принимают 3 рабочих (минимум – 7 рабочих). Стоимость приема, обучения трех рабочих и содержания одного избыточного работника равна 500 + 3×300 + 400 =1800 (д.е.).

Рассмотрим таблицу 3 (рисунок 3, k=3). В строке этой таблицы, соответствующей восьми рабочим,

находим х3 = 8 число 400. Отсюда следует, что на третьем этапе численность рабочих в штате остается неизменной.

Из таблицы 4 (рисунок 4, k=2)  следует, что х4 = 6. Двое рабочих получают расчет. Стоимость содержания одного избыточного работника равна 400 д.е. Из таблицы 1 находим х5 = 6.

Суммарные затраты равны:

Fmin = (500 + 5 × 300) + (500 + 3× 300) + 400 + 400 = 2000+1400+800=4200 д.е.

Процесс нахождения  оптимального решения  можно представить следующей схемой: (x1=5) Þ

(x2=8) Þ (x3=8) Þ (x4=6) Þ (x5=6).

Fmin=4200 (д.е.)

По первоначальной схеме: (x1=5) Þ (x2=7) Þ (x3=8) Þ (x4=5) Þ (x5=6).

Суммарные затраты составляют:

F= (500 + 5 × 300) + (500 + 2 × 300) + (500 + 300) + (500 + 300) = 4700 (д.е.)

Таким образом, экономия составила 4700 д.е.–4200 д.е.=500 д.е. Анализ чувствительности решения.

Метод динамического программирования дает возможность анализа чувствительности к изменению исходных данных C0, C1, C2, bi/. Изменив в решенной задаче о найме значения C0, C1, C2, получили новое значение Fmin.



В Excel автоматически вычисляется оптимальное решение:

Аналогично, изменяя bi/, i=1,..5, получим новое оптимальное решение.

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

Выводы.

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

2.    Метод динамического программирования позволяет свести n-мерную задачу оптимизации  к совокупности задач меньшей размерности.

3.     Метод динамического программирования применим при любом способе задания и любом допустимом множестве состояний и управлений. Этого преимущества лишены классические методы оптимизации и другие вычислительные методы математического программирования.

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

5.   Решение задачи динамического программирования с применением MS Excel облегчает работу и избавляет нас от рутинных действий при расчетах.

 

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

 

1.    Балдин К.В., Брызгалов Н.А., Рукосуев А.В. Математическое программирование: Учебник .М: Дашков и Ко, 2012 – с.219. . – Режим доступа : Электронно-библиотечная система : Университетская   библиотека.   http://biblioclub.ru/index.php?page=book_red&id=112201

2.      Баллод Б. А., Елизарова Н. Н. Методы и алгоритмы принятия решений в экономике [Электронный ресурс] : учебное пособие / Б. А. Баллод, Н.Н. Елизарова - Финансы и статистика, 2009. – Режим доступа : Электронно-библиотечная система : Университетская библиотека.http://www.biblioclub.ru/index.php?page=book_view&book_id=85071

3.    Динамическое программирование в экономических задачах c применением системы SciLab / Н.П.Визгунов. — Н.Новгород: ННГУ, 2011.

4. Колемаев В. А. Практикум по исследованию операций в экономике: Учебное пособие для вузов / В. А.  Колемаев, В.И. Соловьев,  И.С. Карандаев и др.; Под ред. В. А. Колемаева и В. И. Соловьева. – М., 2007. – 192 с.

5.   Конюховский П. В.Математические методы исследования операций. Пособие для подготовки к экзамену. – СПб.: Питер, 2001.

6. Кофман А. Методы и модели исследования операций. – М.: Мир, 1966.

7.       Математические        методы        исследований        в        экономике:        Учебное пособие   /   Под   ред.   Ф.Л.   Шарова.   –   3-е   изд.,   доп.   и   перераб.   –    М.: МИЭП, 2010. – 192 с.

8.   Тынкевич М.А. Экономико-математические методы (исследование операций). – Кемерово, 2000.– 177с.

9.    Фомин, Г. П. Математические методы и модели в коммерческой деятельности Учебник для вузов/ Г. П. Фомин. - М.: Финансы и статистика, 2009. - 544 с.

Христиановский В.В., Щербина В.П. Экономико-математические методы и модели: теория и практика: Учебное пособие. - Донецк, ДонНУ, 2010. – 335с.