Применение теории динамического программирования для КУП "СПЕЦКОММУНТРАНС", Основные понятия и обозначения - Применение экономико-математических методов и моделей в управлении производством (на примере КУП "Спецкоммунтранс")

Основные понятия и обозначения

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

В настоящее время оно в основном развивается в планировании приложений различного рода многоэтапных процессов.

Динамическое программирование - это математический метод поиска оптимального управления, специально приспособленный к многошаговым процессам. Рассмотрим пример такого процесса для предприятия КУП "Спецкоммунтранс".

Как известно, КУП "СПЕЦКОММУНТРАНС" наряду с ниже следующими предприятиями входит в состав коммунального производственного унитарного предприятия гомельского управления жилищно-коммунальным хозяйством (КПУП ГУ ЖКХ):

КУП "Гомельгорсвет";

КУП "Горэлектротранспорт";

КУП "Гостиничное хозяйство";

КУП "Лещинец";

КУП "БелТис";

КПУП "Гомельводоканал";

КПУП "Гомельзеленстрой";

КАУП "ГорСАП";

КОУП "Парс";

КРСУП "Гомельремстрой";

КЖРЭУП "Советское";

КЖРЭУП "Новобелицкое";

КЖРЭУП "Железнодорожное";

КЖРЭУП "Центральное";

КЖРЭУП "Костюковское".

А КПУП ГУ ЖКХ осуществляет планирование деятельности данной группы предприятий условно на N лет. Здесь шагом является один год. В начале первого года на развитие предприятий выделяются средства, которые должны быть как-то распределены между этими предприятиями. В процессе их функционирования выделенные средства частично расходуются. Каждое предприятие за год приносит некоторый доход, зависящий от вложенных средств. В начале года имеющиеся средства могут перераспределяться между предприятиями: каждому из них выделяется какая-то доля средств.

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

Перед нами типичная задача динамического программирования, в которой рассматривается управляемый процесс - функционирование группы предприятий. Управление процессом состоит в распределении (и перераспределении) средств. Управляющим воздействием (УВ) является выделение каких-то средств каждому из предприятий в начале года.

УВ на каждом шаге должно выбираться с учетом всех его последствий в будущем. УВ должно быть дальновидным, с учетом перспективы. Нет смысла выбирать на рассматриваемом шаге наилучшее УВ, если в дальнейшем это помешает получить наилучшие результаты других шагов. УВ на каждом шаге надо выбирать "c заглядыванием в будущее", иначе возможны серьезные ошибки.

Действительно, предположим, что в рассмотренной группе предприятий одни заняты выпуском предметов потребления, а другие производят для этого машины. Здесь можно рассматривать и любой другой пример, где работа одной группы предприятий каким-либо образом от деятельности другой группы предприятий. Для рассматриваемого предприятия КУП "Спецкоммунтранс" это будет: ремонт и ввод в эксплуатацию машин и тракторной техники - первое подразделение, и работа машин при уборке и вывозе мусора - второе подразделение. Причем целью является получение за N лет максимального объема выпуска предметов потребления. Пусть планируются капиталовложения на первый год. Исходя их узких интересов данного шага (года), мы должны были бы все средства вложить в производство предметов потребления, пустить имеющиеся машины на полную мощность и добиться к концу года максимального объема продукции. Но правильным ли будет такое решение в целом? Очевидно, нет. Имея в виду будущее, необходимо выделить какую-то долю средств и на производство машин. При этом объем продукции за первый год, естественно, снизится, зато будут созданы условия, позволяющие увеличивать ее производство в последующие годы.

В формализме решения задач методом динамического программирования будут использоваться следующие обозначения:

N - число шагов.

    - вектор, описывающий состояние системы на k-м шаге. - начальное состояние, то есть, состояние на 1-м шаге. - конечное состояние, т. е. состояние на последнем шаге.

XK - область допустимых состояний на k-ом шаге.

- вектор УВ на k-ом шаге, обеспечивающий переход системы из состояния xK-1 В состояние xK.

UK - область допустимых УВ на k-ом шаге.

WK - величина выигрыша, полученного в результате реализации k-го шага.

    S - общий выигрыш за N шагов. - вектор оптимальной стратегии управления или ОУВ за N шагов.

SK+1() - максимальный выигрыш, получаемый при переходе из любого состояния в конечное состояние при оптимальной стратегии управления начиная с (k+1)-го шага.

S1() - максимальный выигрыш, получаемый за N шагов при переходе системы из начального состояния в конечное при реализации оптимальной стратегии управления. Очевидно, что S = S1(), если - фиксировано.

Метод динамического программирования опирается на условие отсутствия последействия и условие аддитивности целевой функции.

Условие отсутствия последействия. Состояние, в которое перешла система за один k-й шаг, зависит от состояния и выбранного УВ и не зависит от того, каким образом система пришла в состояние, то есть

(8)

Аналогично, величина выигрыша WK зависит от состояния и выбранного УВ, то есть

(9)

Условие аддитивности целевой функции. Общий выигрыш за N шагов вычисляется по формуле

(10)

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

Условие отсутствия последействия позволяет сформулировать принцип оптимальности Белмана.

Принцип оптимальности. Каково бы ни было допустимое состояние системы перед очередным i-м шагом, надо выбрать допустимое УВ на этом шаге так, чтобы выигрыш WI на i-м шаге плюс оптимальный выигрыш на всех последующих шагах был максимальным.

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

Управление может быть хорошим или плохим, эффективным или неэффективным. Эффективность управления оценивается показателем S. Возникает вопрос: как выбрать шаговые управления, чтобы величина S обратилась в максимум?

Поставленная задача является задачей оптимального управления, а управление, при котором показатель S достигает максимума, называется оптимальным. Оптимальное управление многошаговым процессом состоит из совокупности оптимальных шаговых управлений:

(11)

Таким образом, перед нами стоит задача: определить оптимальное управление на каждом шаге (i=1,2,...N) и, значит, оптимальное управление всем процессом.

Похожие статьи




Применение теории динамического программирования для КУП "СПЕЦКОММУНТРАНС", Основные понятия и обозначения - Применение экономико-математических методов и моделей в управлении производством (на примере КУП "Спецкоммунтранс")

Предыдущая | Следующая