Применение теории динамического программирования для КУП "СПЕЦКОММУНТРАНС", Основные понятия и обозначения - Применение экономико-математических методов и моделей в управлении производством (на примере КУП "Спецкоммунтранс")
Основные понятия и обозначения
Динамическое программирование как самостоятельная дисциплина сформировалась в пятидесятых годах двадцатого века. Большой вклад в ее развитие внес американский математик Р. Бельман. Дальнейшее развитие динамическое программирование получило в трудах зарубежных ученых Робертса, Ланга и др.
В настоящее время оно в основном развивается в планировании приложений различного рода многоэтапных процессов.
Динамическое программирование - это математический метод поиска оптимального управления, специально приспособленный к многошаговым процессам. Рассмотрим пример такого процесса для предприятия КУП "Спецкоммунтранс".
Как известно, КУП "СПЕЦКОММУНТРАНС" наряду с ниже следующими предприятиями входит в состав коммунального производственного унитарного предприятия гомельского управления жилищно-коммунальным хозяйством (КПУП ГУ ЖКХ):
КУП "Гомельгорсвет";
КУП "Горэлектротранспорт";
КУП "Гостиничное хозяйство";
КУП "Лещинец";
КУП "БелТис";
КПУП "Гомельводоканал";
КПУП "Гомельзеленстрой";
КАУП "ГорСАП";
КОУП "Парс";
КРСУП "Гомельремстрой";
КЖРЭУП "Советское";
КЖРЭУП "Новобелицкое";
КЖРЭУП "Железнодорожное";
КЖРЭУП "Центральное";
КЖРЭУП "Костюковское".
А КПУП ГУ ЖКХ осуществляет планирование деятельности данной группы предприятий условно на 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) и, значит, оптимальное управление всем процессом.
Похожие статьи
-
Для достижения поставленной цели предприятию требуются материалы, оборудование, энергия, рабочая сила и другие ресурсы. Каждое предприятие такими...
-
Динамическое программирование Динамическое программирование -- один из разделов оптимального программирования, в котором процесс принятия решения и...
-
Теория игр исследует оптимальные стратегии в ситуациях игрового характера. К ним относятся ситуации, связанные с выбором наивыгоднейших производственных...
-
Модели теории игр. Основные определения и термины В разных областях целенаправленной деятельности, например при разработке и эксплуатации АСУ, часто...
-
Наиболее ранним способом формализации экономико-математических и ТС является представление физических явлений с помощью систем дифференциальных...
-
Постановка задачи применительно для КУП "СПЕЦКОММУНТРАНС": двум погрузчикам разной мощности, это автомобили ТО 28 и ТО 49, за 23 часа нужно погрузить на...
-
Основные понятия теории экономико-математического моделирования Кибернетический подход к исследованию экономико-математических систем Обычно...
-
В зависимости от содержания задачи может быть два случая: когда ребра графа G единичной длины; когда ребра графа произвольной длины. Для каждого из этих...
-
Применительно к предприятию КУП "СПЕЦКОММУНТРАНС" данная задача представляет собой задачу нахождения наилучшего маршрута движения автомобиля,...
-
Модели линейного программирования. Основные определения Еще одним классом задач экономико-математического моделирования являются задачи линейного...
-
Важным этапом изучения явлений предметов процессов является их классификация, выступающая как система соподчиненных классов объектов, используемая как...
-
При решении экономических задач часто анализировать ситуации, в которых сталкиваются интересы двух или более конкурирующих сторон, преследующих различные...
-
Основные понятия сетевых и графовых моделей Объектом исследования является сеть, состоящая из узлов и линий связи. Предполагается, что в сети имеется два...
-
Анализ комплексных расходов позволяет выявить дополнительные резервы снижения затрат на производство продукции [16], повышения эффективности...
-
Структура производства и управления КУП "СПЕЦКОММУНТРАНС" Краткая технико-экономическая характеристика В январе 1949г. по решению Гомельского...
-
Из перечисленного обзора типов ММ, составляющих предмет ИСО, можно выделить следующие особенности ММ ИСО [3]. - Системный подход, заставляющий...
-
Это раздел математического программирования, изучающий методы решения таких экстремальных задач, в которых результаты (эффективность) возрастают или...
-
Большое число экономических и планово-производственных задач связано с распределением каких-либо, как правило, ограниченных ресурсов (сырья, рабочей...
-
Системы массового обслуживания -- это такие системы, в которые в случайные моменты времени поступают заявки на обслуживание, при этом поступившие заявки...
-
Основные направления совершенствования организационной структуры предприятия ОАО "Огонек". Любую перестройку структуры управления необходимо оценивать, в...
-
В начале пятилетнего периода работы предприятию выделена сумма в C руб. для приобретения нового оборудования. Стоимость одного комплекта оборудования...
-
При управлении подвижными объектами (такими, например, как мобильные роботы, подводные аппараты и т. п.) часто имеет место неопределенность цели, когда...
-
Задача о загрузке рюкзака (задача о ранце) - Метод динамического программирования для решения задач
Постановка задачи. Пусть имеются N видов грузов с номерами. Единица груза j-го вида имеет все aJ. Если груз j-го вида берется в количестве xJ, то его...
-
Иногда необходимо управлять сложными комплексами взаимосвязанных работ, направленных на достижение определенных целей. Примерами таких комплексов в...
-
В предыдущем разделе мы определили, что существуют различные виды управления: производственное, техническое, государственное, идеологическое,...
-
Система управление и его основные элементы С раннего детства человеку знакомо понятие "управление". Сначала мы сталкиваемся с управлением автомобилем,...
-
В современных условиях эффективность деятельности предприятия, прежде всего, определяется эффективностью использования главного ресурса - людей....
-
Конкретные модели процессов управления в социальных и экономических системах исходят из общей методологии, которую и формулируем в настоящей статье....
-
Совершенствование системы управления - сложный и непрерывный процесс воздействия, направленный на более целесообразную организацию управляющей системы...
-
На сегодняшний день основным видом деятельности ОАО "Огонек" является розничная торговля. В процессе труда человек вступает во взаимодействие с...
-
Модель в общем смысле (обобщенная модель) есть создаваемый с целью получения и (или) хранения информации специфический объект (в форме мысленного образа,...
-
МЕТОДЫ ОПИСАНИЯ СОЦИАЛЬНО-ПОЛИТИЧЕСКИХ И ЭКОНОМИЧЕСКИХ ПРОЦЕССОВ Динамический образ системы. Системный процесс В своей повседневной жизни процессами люди...
-
Основные понятия линейного программирования - Оптимальное программирование
Математические исследования отдельных экономических проблем, математическая формализация числового материала проводилась еще в XIX веке. При...
-
Цель и задачи исследования операций Исследование операций - научная дисциплина, занимающаяся разработкой и практическим применением методов наиболее...
-
СТРУКТУРЫ УПРАВЛЕНИЯ ЛОГИСТИЧЕСКИМИ СИСТЕМАМИ - Понятие и виды логистической системы
Объектом логистическими системами, как известно является сквозной материальный поток, тем не менее на отдельных участках управление им имеет известную...
-
Программное управление Относительно просто может быть сформулирована так называемая задача программного управления. В ней предполагается, что управляющие...
-
Теоретическое обоснование математического моделирования - Математические методы и модели в экономике
Коммерческая деятельность в том или ином виде сводится к решению таких задач: как распорядиться имеющимися ресурсами для достижения наибольшей выгоды или...
-
Организационная характеристика ОАО "Огонек". ОАО "Огонек" является юридическим лицом. Оно имеет самостоятельный баланс, расчетный счет в банке, печать со...
-
Принципы оптимальности в изучении социально-экономических процессов рынка труда
Принципы оптимальности в изучении социально-экономических процессов рынка труда Муравьева Мария Петровна С точки зрения системного анализа рынок труда...
-
Комментарии к третьему разделу курсовой работы В третьем разделе курсовой работы студенту предлагается определить оптимальную стратегию заказа в условиях...
Применение теории динамического программирования для КУП "СПЕЦКОММУНТРАНС", Основные понятия и обозначения - Применение экономико-математических методов и моделей в управлении производством (на примере КУП "Спецкоммунтранс")