Использование метода динамического программирования при решении дискретных технико-экономических задач
Наведено методичний підхід до вирішення дискретних оптимізованих завдань на прикладі розподілу ресурсів у технологічних (організованих) процесах виробництва. Процес розподілу ресурсу реалізується поетапно: на кожному етапі здійснюються розрахунки витрат на використання ресурсу; при зворотному перебі...
Збережено в:
| Опубліковано в: : | Економіка промисловості |
|---|---|
| Дата: | 2011 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут економіки промисловості НАН України
2011
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/37299 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Использование метода динамического программирования при решении дискретных технико-экономических задач / А.В. Ляхов, Д.С. Шмидт // Економіка пром-сті. — 2011. — № 4. — С. 131-134. — Бібліогр.: 3 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860212050066669568 |
|---|---|
| author | Ляхов, А.В. Шмидт, Д.С. |
| author_facet | Ляхов, А.В. Шмидт, Д.С. |
| citation_txt | Использование метода динамического программирования при решении дискретных технико-экономических задач / А.В. Ляхов, Д.С. Шмидт // Економіка пром-сті. — 2011. — № 4. — С. 131-134. — Бібліогр.: 3 назв. — рос. |
| collection | DSpace DC |
| container_title | Економіка промисловості |
| description | Наведено методичний підхід до вирішення дискретних оптимізованих завдань на прикладі розподілу ресурсів у технологічних (організованих) процесах виробництва. Процес розподілу ресурсу реалізується поетапно: на кожному етапі здійснюються розрахунки витрат на використання ресурсу; при зворотному перебігу остаточно визначаються мінімальні витрати на весь процес. 
Ключові слова: оптимізація, ресурси, 
витрати, динамічне програмування.
Приведен методический подход к решению дискретных оптимизированных задач на примере распределения ресурсов в технологических (организованных) процессах производства. Процесс распределения ресурса осуществляется поэтапно: на каждом этапе при прямом ходе производятся расчеты затрат на использование ресурса; при обратном ходе окончательно определяются минимальные затраты на весь процесс. 
Ключевые слова: оптимизация, ресурсы, затраты, динамическое программирование.
The methodical approach to solving discrete optimization problems is presented on the example of distribution of resources in the technological (organizational) processes of manufacture. The process of distribution of a resource is realized stage by stage: at each stage the calculation of resources costs is made during a direct production; during the reverse production the minimal costs are calculated for the whole process.
Keywords: optimization, resources, costs, dynamic programming.
|
| first_indexed | 2025-12-07T18:14:25Z |
| format | Article |
| fulltext |
УДК 519.854.001.26+303.092.5 Александр Васильевич Ляхов,
канд. техн. наук, доц.,
Даниил Сергеевич Шмидт
Донецкий национальный
технический университет
ИСПОЛЬЗОВАНИЕ МЕТОДА ДИНАМИЧЕСКОГО
ПРОГРАММИРОВАНИЯ ПРИ РЕШЕНИИ
ДИСКРЕТНЫХ ТЕХНИКО-ЭКОНОМИЧЕСКИХ ЗАДАЧ
С целью минимизации затрат,
связанных с процессами, реализуемыми во
времени и в пространстве, возможно
использовать метод динамического
программирования. Этот метод позволяет
оптимизировать распределение
ограниченного ресурса по этапам, если весь
процесс можно четко разделить на
последовательно расположенные места
потребления данного ресурса.
В общем виде нужно найти такое
управление U, при котором затраты З
обращаются в минимум
З = min{3(U)}. (1)
Задача решается в два захода – прямом
и обратном. При первом заходе оптимизация
производится методом последовательного
приближения от первого шага (этапа)
процесса к последнему, а затем, наоборот, от
последнего к первому. При первом заходе,
идя от предыдущих шагов к последующим,
находят условно оптимальное управление.
При втором заходе оптимизация начинается
от последнего шага, для которого
оптимальное управление известно,
последовательно переходя от условных к
оптимальным управлениям.
При решении поставленной задачи
оптимального распределения ресурсов по
шагам (этапам), если нет соответствующих
зависимостей, детерминированно на каждом
этапе производятся расчеты – для каждого
варианта необходимо знать затраты ( в
денежном выражении), вызванные
потреблением ресурса. После каждого этапа
ресурс перераспределяется в зависимости от
финансовых затрат и заранее назначенных
технических или иных вариантов
использования ресурса. Задача решается в
таких условиях: распределяемые ресурсы
ограничены, финансовые затраты условно
неограничены.
Схематически рассматриваемый
процесс можно упрощенно представить
следующим образом:
1-й этап 2-й этап 3-й этап n-й этап
Рассмотрим прямой ход.
1-й этап. Из возможных вариантов
потребления ресурса выбираются те, которые
удовлетворяют всем технологическим
требованиям (условиям, ограничениям). Как
правило, увеличение количества вариантов
только усложняет процесс решения задачи.
Но если мы не укладываемся в заранее
разработанные ряды вариантов потребления
распределяемого ресурса по этапам,
некоторые ряды на отдельных этапах могут
быть расширены при условии соблюдения
заранее оговоренных требований.
Итак, на первом этапе запишем
ограниченный ряд технических или
организационных параметров (значений) и
для них рассчитаем затраты и потребляемые
ресурсы
1 2 3 1
1 1 1 1
1 2 3
1 1 1 1
1 2 3
B: 1 ,2 ,3 , ... ;
З: З ,З ,З , ... З ;
Р: Р ,Р ,Р , ... Р ,
n
n
n
где В – варианты параметров – порядковые
номера ;
З – затраты, связанные с реализацией
технического (организационного)
мероприятия соответствующего параметра,
грн.
Р – ресурс, необходимый для
реализации мероприятия, соответствующего
параметра, ед. измерения.
© А.В. Ляхов, Д.С. Шмидт, 2011
2-й этап. Он технологически
(организационно) отличается от первого.
Составляются и рассчитываются следующие
исходные данные:
2 2 2 2
2 2 2 2
1 2 3
2 2 2 2
1 2 3
1,2 1,2 1,2 1,2
1 2 3
1,2 1,2 1,2 1,2
1 2 3
1 ,2 ,3 , ... ;
З ,З ,З , ... З ;
Р ,Р ,Р , ... Р ;
З ,З ,З , ... З ;
Р ,Р ,Р , ... Р ,
n
n
n
n
n
где 1, 2З – суммарные затраты на 1-м и 2-м
этапах, грн.;
1,2Р – суммарные потребленные
ресурсы на 1-м и 2-м этапах, ед. измерения.
Суммарным затратам 1, 2З ,
соответствующим ресурсам 1,2Р , для двух
этапов, – найдем условные оптимальные
значения, используя данные (табл. 1 и 2).
Таблица 1
Суммарные затраты на первых двух этапах
1,2Р 1, 2
1З 1, 2
2З 1, 2
3З ... 1, 2З n
1, 2
1Р
1, 2
2Р
1, 2
3Р
.
1, 2Р n
1,2Р 2
1Р 2
2Р 2
3Р ... 2Р n
На втором этапе, как это было и на
первом, назначаются несколько значений
технического (организационного) параметра,
для них рассчитываются затраты и ресурсы.
В табл. 1 в нижней строке записаны
значения ресурса (Р2) на втором этапе при
различных параметрах. В левом крайнем
столбце (Р1,2) представлены сверху - вниз, по
уменьшению, суммарные ресурсы для двух
этапов процесса. В клетках таблицы на
пересечении столбцов и строк располагаем
затраты для двух этапов. Первое слагаемое
из них – это затраты для второго этапа, оно
соответствует значениям ресурса нижней
строки. Второе слагаемое – затраты,
связанные с использованием ресурса на
первом этапе. Определяются они следующим
образом. Из суммарного значения ресурса
1, 2
1Р , записанного внизу в левом нижнем
столбце, вычтем ресурс нижней строки 2
1Р ,
получим разность ( 1, 2 2
1Р - Рn ), с которой
войдем в ряд значений ресурса на первом
этапе и соответственно введенному ресурсу
получим затраты, например, 1Зn . Сложим
затраты 2 1 1, 2З +З Зn n n и запишем в табл. 1 на
пересечении строки 1, 2Р n и столбца 1
1, 2З .
Таким образом, заполним всю табл. 1. Опыт
показал, что минимальные суммарные
затраты расположены по диагонали этой
таблицы.
Таблица 2
Условно оптимальные затраты на двух этапах
2Р 2
1Р 2
2Р 2
3Р ... 2Р n
1, 2З 1, 2
1З 1, 2
2З 1, 2
3З ... 1, 2З n
1,2Р 1, 2
1Р 1, 2
2Р 1, 2
3Р ... 1, 2Р n
Табл. 2 заполняется так. В нижней
строке записываются суммарные ресурсы
для двух этапов в возрастающем порядке ; в
средней – условно оптимальные затраты
тоже для двух этапов. Для этого из табл.1 по
столбцам, последовательно, слева – направо,
выбираются суммарные затраты на двух
этапах и минимальные – заносятся в табл.2.
Следует отметить, что при
формировании табл.1 не всегда удается
попасть в узлы сетки предыдущих этапов,
полученной в результате условной
оптимизации. Для получения
промежуточных значений следует
воспользоваться интерполяционной
формулой
1
1 1 1
Р Р ,
Р Р (З З ) З
і
і і і і і
где 1 1Р , Зі і – суммарные ресурсы и
суммарные затраты для всех этапов (без
последнего) в i-м узле сетки;
Р , Зі і – суммарные ресурсы и
суммарные затраты для всех этапов (без
последнего) в i-м узле сетки;
Н1 – суммарные ресурсы для всех
этапов в промежуточной точке между i+1 и
i-м узлами сетки.
3-й этап. Расчеты выполняются
аналогично описанным на втором этапе.
Подбираем и рассчитываем исходные
данные
3 3 3 3
3 3 3 3
1 2 3
3 3 3 3
1 2 3
1,2,3 1,2,3 1,2,3 1,2,3
1 2 3
1,2,3 1,2,3 1,2,3 1,2,3
1 2 3
1 ,2 ,3 , ... ;
З ,З ,З , ... З ;
Р ,Р ,Р , ... Р ;
З ,З ,З , ... З ;
Р ,Р ,Р , ... Р .
n
n
n
n
n
Заполняются табл. 3 и 4.
Таблица 3
Суммарные затраты на трех этапах
1,2,3Р 1,2,3
1З 1,2,3
2З 1,2,3
3З ... 1,2,3Зn
1,2,3
1Р
1,2,3
2Р
1,2,3
3Р
...
1,2,3Рn
3Р 3
1Р 3
2Р 3
3Р ... 3Р n
Таблица 4
Условно оптимальные затраты на трёх этапах
3Р 3
1Р 3
2Р 3
3Р ... 3Р n
1,2,3З 1,2,3
1З 1,2,3
2З 1,2,3
3З ... 1,2,3Зn
1,2,3Р 1,2,3
1Р 1,2,3
2Р 1,2,3
3Р ... 1,2,3Рn
Надо иметь в виду, что в табл.4
суммарные затраты ( 1,2,3З ) должны быть
условно минимальные для трех этапов.
Дальнейшие расчеты для оставшихся
этапов производятся аналогично, кроме
последнего.
Расчеты на последнем этапе в отличие
от предыдущих имеют такую особенность,
что здесь нужно получить оптимальные
суммарные затраты при ограниченных в
целом ресурсах для всех этапов.
В начале запишем исходные данные,
соответствующие последнему этапу (m).
1 2 3
1 2 3
1 , 2 , 3 , ..., ;
З , З , З , ..., З ;
P , P , P , ..., P .
m m m m
m m m m
n
m m m m
n
n
Затем из фиксированной величины
ресурсов (Р) вычтем ресурсы первого
параметра на последнем этапе ( 1Pm ) и с этой
разностью войдем в итоговую таблицу
предпоследнего этапа (m-1) и в соответствии
с величиной ( 1P Pm ) найдем суммарные
затраты для всех этапов без последнего ; к
этим затратам прибавим затраты на
последнем этапе ( 1З m ) , получим
оптимальные затраты реализации процесса
целиком.
В конкретных задачах, кроме
оптимальных затрат, необходимо знать
параметры на этапах, при которых эти
затраты получены, т.е. необходимо решить
обратную задачу. Для того, чтобы
определить параметр на предыдущем этапе,
нужно из фиксированной величины общих
ресурсов вычесть ресурсы последнего этапа
( 1P Pm ) и с этой разностью войти в сетку
суммарных ресурсов на предпоследнем этапе
и найти соответствующий параметр процесса
на предпоследнем этапе. Далее, из ( 1P Pm )
вычесть ресурс ( 1P m ), соответствующий
найденному параметру на предпоследнем
этапе и с этим ресурсом ( 1
1P P Pm m ) войти
в следующую сетку суммарных ресурсов на
третьем этапе, начиная с конца процесса, и в
соответствии с величиной этого ресурса
найти параметр на указанном этапе. Такая
процедура поиска параметров на оставшихся
этапах выполняется аналогично. На
последнем этапе при обратном ходе с
оставшимися ресурсами входим в сетку
первого этапа и находим соответствующий
параметр. В результате получим искомые
параметры при минимальных затратах.
Необходимо проверить решение
задачи. Для этого затраты, соответствующие
найденным параметрам, следует сложить и
должны получиться оптимальные суммарные
затраты для всего процесса с допустимым
отклонением от оптимальных.
Описанный алгоритм поиска
оптимального решения не трудно
переложить на компьютерную программу.
Литература
1. Беллман Я. Прикладные задачи
динамического программирования / Я. Бел-
лман, С. Дрейфус. – М.: Наука, 1965.
2. Вентцель Е.С. Элементы
динамического программирования /
Е.С. Вентцель. – М.: Наука, 1964.
3. Иванов Н.И. Использование метода
динамического программирования при
решении вопросов вскрытия и подготовки
шахтных полей / Н.И. Иванов, А.В. Ляхов //
Уголь Украины. – 1968.
Представлена в редакцию 10.11.2011 г.
|
| id | nasplib_isofts_kiev_ua-123456789-37299 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1562-109Х |
| language | Russian |
| last_indexed | 2025-12-07T18:14:25Z |
| publishDate | 2011 |
| publisher | Інститут економіки промисловості НАН України |
| record_format | dspace |
| spelling | Ляхов, А.В. Шмидт, Д.С. 2012-10-02T16:49:56Z 2012-10-02T16:49:56Z 2011 Использование метода динамического программирования при решении дискретных технико-экономических задач / А.В. Ляхов, Д.С. Шмидт // Економіка пром-сті. — 2011. — № 4. — С. 131-134. — Бібліогр.: 3 назв. — рос. 1562-109Х https://nasplib.isofts.kiev.ua/handle/123456789/37299 519.854.001.26+303.092.5 Наведено методичний підхід до вирішення дискретних оптимізованих завдань на прикладі розподілу ресурсів у технологічних (організованих) процесах виробництва. Процес розподілу ресурсу реалізується поетапно: на кожному етапі здійснюються розрахунки витрат на використання ресурсу; при зворотному перебігу остаточно визначаються мінімальні витрати на весь процес. 
 Ключові слова: оптимізація, ресурси, 
 витрати, динамічне програмування. Приведен методический подход к решению дискретных оптимизированных задач на примере распределения ресурсов в технологических (организованных) процессах производства. Процесс распределения ресурса осуществляется поэтапно: на каждом этапе при прямом ходе производятся расчеты затрат на использование ресурса; при обратном ходе окончательно определяются минимальные затраты на весь процесс. 
 Ключевые слова: оптимизация, ресурсы, затраты, динамическое программирование. The methodical approach to solving discrete optimization problems is presented on the example of distribution of resources in the technological (organizational) processes of manufacture. The process of distribution of a resource is realized stage by stage: at each stage the calculation of resources costs is made during a direct production; during the reverse production the minimal costs are calculated for the whole process.
 Keywords: optimization, resources, costs, dynamic programming. ru Інститут економіки промисловості НАН України Економіка промисловості НТП та організація виробництва Использование метода динамического программирования при решении дискретных технико-экономических задач Використання методу динамічного програмування при вирішенні дискретних техніко-економічних завдань Using the method of dynamic programming when solving discrete technical and economic problems Article published earlier |
| spellingShingle | Использование метода динамического программирования при решении дискретных технико-экономических задач Ляхов, А.В. Шмидт, Д.С. НТП та організація виробництва |
| title | Использование метода динамического программирования при решении дискретных технико-экономических задач |
| title_alt | Використання методу динамічного програмування при вирішенні дискретних техніко-економічних завдань Using the method of dynamic programming when solving discrete technical and economic problems |
| title_full | Использование метода динамического программирования при решении дискретных технико-экономических задач |
| title_fullStr | Использование метода динамического программирования при решении дискретных технико-экономических задач |
| title_full_unstemmed | Использование метода динамического программирования при решении дискретных технико-экономических задач |
| title_short | Использование метода динамического программирования при решении дискретных технико-экономических задач |
| title_sort | использование метода динамического программирования при решении дискретных технико-экономических задач |
| topic | НТП та організація виробництва |
| topic_facet | НТП та організація виробництва |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/37299 |
| work_keys_str_mv | AT lâhovav ispolʹzovaniemetodadinamičeskogoprogrammirovaniâprirešeniidiskretnyhtehnikoékonomičeskihzadač AT šmidtds ispolʹzovaniemetodadinamičeskogoprogrammirovaniâprirešeniidiskretnyhtehnikoékonomičeskihzadač AT lâhovav vikoristannâmetodudinamíčnogoprogramuvannâpriviríšennídiskretnihtehníkoekonomíčnihzavdanʹ AT šmidtds vikoristannâmetodudinamíčnogoprogramuvannâpriviríšennídiskretnihtehníkoekonomíčnihzavdanʹ AT lâhovav usingthemethodofdynamicprogrammingwhensolvingdiscretetechnicalandeconomicproblems AT šmidtds usingthemethodofdynamicprogrammingwhensolvingdiscretetechnicalandeconomicproblems |