доцент кафедры «Высшая математика и прикладная информатика»
Самарского государственного технического университета, г. Самара
E-mail: smirnovamilan@mail.ru
В настоящее время актуальной является экологическая проблема сбора, вывоза и переработки полиэтиленового мусора. В статье рассматривается одна из задач оптимизации вывоза отходов и их переработки, как задача динамического программирования Задача по оптимальному перевозу и переработке полиэтиленовых отходов сведена к задаче распределения ресурсов согласно критерию минимизации.
Ключевые слова: динамическое программирование, инвариантность, целочисленность, уравнение Беллмана, оптимизация, критерий устойчивости.
Задача о минимизации затрат на вывоз полиэтиленового мусора и его обработки относится к задачам динамического программирования. Общая задача оптимизации, чтобы ее можно было описать моделью динамического программирования (ДП) должна удовлетворять следующим условиям[1,2]:
1. Задача может интерпретироваться как n-шаговый процесс управления, а показатель эффективности процесса может быть представлен в аддитивной форме, т.е. как сумма показателей эффективности на каждом шаге.
2. Структура задачи инвариантна относительно числа шагов п, т. е. должна быть определена для любого n и не зависеть от этого числа.
3. На каждом шаге состояние системы определяется конечным числом s параметров состояния и управляется конечным числом r переменных управления, причем s и r не зависят от числа шагов п.
4. Выбор управления на k-м шаге не влияет на предшествующие шаги, а состояние в начале этого шага есть функция только предшествующего состояния и выбранного на нем управления (отсутствие последействия).
Построение модели ДП сводится к следующим основным моментам:
- выбирают способ деления процесса на шаги; вводят параметры состояния 
и переменные управления 
на каждом шаге процесса; записывают уравнение состояния
(1)
- вводят показатели эффективности на k-м шаге 
и суммарный показатель – целевую функцию
(2)
- вводят в рассмотрение условные максимумы 
показателя эффективности от k-гo шага (включительно) до конца процесса и условные оптимальные управления на k-м шаге 
из ограничений задачи определяют для каждого шага множества Dk допустимых управлений на этом шаге; записывают основные для вычислительной схемы ДП функциональные уравнения Беллмана
(3)
(4)
Несмотря на единообразие в общем построении модели ДП, приведенном выше, вычислительная схема строится в зависимости от размерности задачи, характера модели (дискретной или непрерывной), вида функций (1), (2) и других характеристик модели [2,3].
Задача по оптимальному вывозу и переработке полиэтиленовых отходов может быть сведена к задаче распределения ресурсов по критерию минимизации с учетом условий целочисленности, накладываемых на переменные. Известны пункты, в которых можно переработать полиэтиленовые отходы(например. бутылки). Определены затраты на вывоз и переработку отходов.. Необходимо так распределить количество полиэтиленовых отходов, чтобы затраты на их вывоз и переработку были минимальные. В задаче введены следующие обозначения: х — количество распределяемого ресурса, которое можно использовать различными способами, xi — количество ресурса, используемого по i-му способу i=1. …, n, gi(xi) — функция расходов, равная, величине затрат на перевозку при использовании ресурса xi по i-му способу; φk(x) — наименьшие затраты, которые нужно произвести при использовании ресурса х первыми k способами. Необходимо минимизировать общую величину затрат при освоении ресурса x всеми способами:
(5)
при ограничениях
В трех районах города предприниматель планирует переработать пять видов полиэтиленовых отходов. Необходимо распределить отходы таким образом, чтобы обеспечить минимальные суммарные затраты на их вывоз и переработку. Значения функции затрат gi(x) приведены в табл. 1
Таблица1
Значения функции затрат
| x | |||||
| g1(x) | |||||
| g2(x) | |||||
| g3(x) |
Здесь gi(х) — функция расходов в млн. руб., характеризующая величину затрат на вывоз и переработку от количества полиэтиленовых отходов в i-м районе; φk(x) — наименьшая величина затрат в млн. руб., которые нужно произвести при вывозе и переработке отходов в первых k районах. Решение задачи проводилось с использованием рекуррентных соотношений: для первого района
для остальных районов
Задача решается в три этапа.
1-й этап. Если все отходы перерабатывать только в первом районе, то
минимально возможные затраты при х = 5 составляют 76 млн руб.
2-й этап. Определяют оптимальную стратегию при переработке отходов только в первых двух районах по формуле
Определяются φ2(l) через выражения:
g2(1) + φ1(0) = 10 + 0 = 10,
g2(0) + φ1(l)= 0 +11 = 11,
φ2(l) = min (10, 11) = 10.
Аналогично вычисляются φ2(2)=: min (19, 21, 18) = 18:
φ2(3) = min (34, 30, 28, 35) = 28.φ2(4) = min (53, 45, 37, 45, 51) = 37.
φ2(5) = min (75, 64, 52, 54, 61, 76) = 52.
3-й этап. Определяют оптимальную стратегию по переработке отходов пяти видов в трех районах по формуле
φ3(x) = min{g3(x3) + φ2(x – х3)}. φ3(5) = min (74, 64, 54, 48, 46, 52) = 46.
Минимально возможные затраты при х = 5 составляют 46 млн. руб.Определены затраты на переработку полиэтиленовых отходов от 1-го до 3-го этапа. Вернемся 3-го к 1-му этапу. Минимальные затраты в 46 млн руб. на 3-м этапе получены как 9 + 37, т.е. 9 млн руб. соответствуют переработке одного вида полиэтиленовых отходов в третьем районе (см. табл. 1). Согласно 2-му этапу 37 млн руб. получены как 19 + 18, т.е. 19 млн руб. соответствуют переработке двух видов полиэтиленовых отходов во втором районе. Согласно 1-му этапу 18 млн руб. соответствуют переработке двух видов отходов в первом районе. Оптимальная стратегия состоит в переработке одного вида отходов предприятия в третьем районе, по два вида отходов предприятия во втором и первом районах, при этом минимальная стоимость вывоза и переработки составит 46 млн.руб.
Список использованной литературы
1. Калихман И.Л., Войтенко М.А. “Динамическое программирование в примерах и задачах”, Москва ”Высшая школа”, 1979
2. Косоруков О.А., Мищенко А.В. “Исследование операций”, Москва, 2003,448с.
3. М.А..Евдокимов, Л.Н.Смирнова, Т.А.Бенгина и др. Исследование операций. Линейное программирование. Динамическое программирование. Элементы теории игр, Сетевое планирование. Учебное пособие.-Самар.гос.техн.ун-т.самара,2014-164с.