Библиографическое описание:

Семахин А. М., Баталов И. С. Динамическое программирование в решении задачи оптимального размещения электронных компонентов системы управления // Молодой ученый. — 2013. — №6. — С. 144-146.

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

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

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

Динамическое программирование возникло в 1951–1953 годах благодаря работам Р. Беллмана [1, с. 158]. В основе динамического программирования лежит принцип оптимальности Р. Беллмана, заключающийся в замене решения исходной многомерной задачи последовательностью задач меньшей размерности. Принцип Р. Беллмана используется для принятия решений в многоэтапных процессах и формулируется следующим образом: если в каждом из состояний дальнейшее поведение системы не зависит от того, как она попала в это состояние, то дальнейшая траектория должна быть оптимальной. Под траекторией понимается последовательность состояний, в которых находится система [2, с. 171].

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

где  — затраты на  шаге.

В соответствии с принципом оптимальности Р. Беллмана  выбираются таким образом, чтобы суммарные затраты на последующие этапы были минимальны. Суммарные затраты зависят от состояния  и складываются из затрат на  шаге  и на последующих шагах. Суммарные затраты на все этапы обозначим , тогда оптимальное управление на каждом шаге определяется по рекуррентному уравнению динамического программирования [2, с. 173].

,

где  — состояние системы;

 — затраты на  этапе;

 — затраты на следующем этапе.

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

,

где  — затраты на последнем шаге n [2, c. 174].

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

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

Размещение электронных компонентов на панели системы управления — многоэтапный процесс. Решение задачи определяется методом динамического программирования (метод Р. Беллмана).

Пусть  — электронный компонент системы управления технологическим оборудованием ( — пустой электронный компонент), ,  — уникальное место размещения электронного компонента, ,  — бинарная переменная (=1 —  электронный компонент размещен на  месте, иначе =0). Оценка эффективности (полезность)  размещения  электронного компонента на  месте размещения.

Математическая модель оптимального размещения электронных компонентов системы управления имеет вид

 Целевая функция

при ограничениях

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

Ограничение 2 обеспечивает уникальность места расположения электронного компонента на электромонтажной схеме системы управления.

Ограничение 3 налагает неотрицательность на искомые переменные.

Ограничение 4 налагает дискретность на искомые переменные.

Множество  сформировано в результате решения задачи оптимизации структуры электромонтажной схемы системы управления модульной компрессорной станцией, выпускаемой ОАО “Курганхиммаш” [3, c. 92].

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

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

На рис.1 представлена сетевая модель задачи оптимизации размещения электронных компонентов системы управления.

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

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

Если задано начальное состояние управляемой системы, то задача решается в обратном направлении, а если конечное, то в прямом. Если заданы как начальное, так и конечное состояния, то задача усложняется [1, c. 173].

С вычислительной точки зрения алгоритм обратной прогонки более эффективный, чем алгоритм прямой прогонки [4, c. 445].

Модели динамического программирования включают три основных элемента:

1.      Определение этапов.

2.      Определение на каждом этапе вариантов решения.

3.      Определение состояний на каждом этапе [4, c.446].

Результаты проведенных исследований позволили сделать выводы.

1.                                 Разработана математическая модель динамического программирования размещения электронных компонентов электромонтажной схемы системы управления модульной компрессорной станцией, выпускаемой ОАО “Курганхиммаш”.

2.                                 Математическая модель позволяет сократить затраты и сроки проектирования электромонтажной схемы. Повысить обоснованность принимаемых решений.

Литература:

1.                                    Конюховский П. В. Математические методы исследования операций в экономике. — СПб.: Издательство «Питер», 2000. — 208 с.

2.                                    Струченков В. И. Методы оптимизации. Основы теории, задачи, обучающие компьютерные программы: Учебное пособие/В. И. Струченков. — М.: Издательство «Экзамен», 2005. — 256 с.

3.                                    Семахин А. М., Баталов И. С. Математическая модель оптимизации структуры электромонтажной панели системы управления. Ежемесячный научный журнал “Молодой ученый” № 4 (51). — Чита, ООО «Издательство молодой ученый», 2013. — с.91–94.

4.                                    Таха Х. А. Введение в исследование операций. 7-е издание: Пер. с англ. М.: Издательский дом “Вильямс”, 2005–912 c.

Обсуждение

Социальные комментарии Cackle