Содержание к диссертации
Введение
ГЛАВА 1. Построение математической модели функционирования предприятия 9
1.1. Основные понятия математической теории управления экономикой 9
1.2. Описание простейшего однопродуктового элемента экономики 14
1.3. Математическое описание модели функционирования предприятия 21
Выводы 42
ГЛАВА 2. Численные методы решения задачи планирования деятельности предприятия 43
2.1. Преобразование исходной задачи к задаче линейного программирования с дискретным временем 43
2.2. Вычисление дуальной функции с помощью лагранжева ослабления соединенных ограничений 56
2.3. Решение дуальной задачи с помощью алгоритма субградиента 61
2.4. Сравнение с методов Данцига-Вольфе 67
Выводы 71
ГЛАВА 3. Решение задач оптимизации и анализа решения линейных динамических систем при неполной информации 72
3.1. Задача экономического планирования в терминах и понятиях стохастического программирования 72
3.2. Оценка решения задачи прогнозирования методами имитационного моделирования 73
3.3. Решение задачи двухэтапного планирования при неполной информации методами стохастического программирования 75
Выводы 85
ГЛАВА 4. Структура программного обеспечения для статистической оценки решения линейных динамических систем при неполной информации 86
4.1. Программное обеспечение и его функциональные возможности 86
4.2. Структура программного обеспечения 87
4.2. Краткое описание блоков, входящих в состав программного обеспечения 88
Выводы 92
ГЛАВА 5. Оптимизация распределения нагрузки в энергосистеме 93
5.1. Постановка и алгоритм решения детерминированной задачи 93
5.2. Решение задачи прогнозирования результатов работы энергосистемы при неполной информации 100
5.3. Решение задачи планирования распределения нагрузки в энергосистеме при неполной информации 103
Выводы 106
Заключение 107
Литература 109
- Описание простейшего однопродуктового элемента экономики
- Вычисление дуальной функции с помощью лагранжева ослабления соединенных ограничений
- Решение задачи двухэтапного планирования при неполной информации методами стохастического программирования
- Краткое описание блоков, входящих в состав программного обеспечения
Введение к работе
Актуальность проблемы. Задача совершенствования системы управления экономикой на базе экономико-математических методов является одной из главнейших практических и научных проблем современного этапа развития общества. В настоящее время экономические расчеты опираются, как правило, на аппарат линейного программирования, разработанный в 40-х годах и не учитывающий ряд важных особенностей экономических объектов. В задачах планирования и прогнозирования такой особенностью является неполная информация о параметрах планирования. Для решения данных задач в условиях неполной информации, перспективным является использование методов имитационного моделирования и стохастического программирования.
Цель работы: Разработать математические и информационные средства для оптимизации функционирования предприятия с позиций линейных динамических систем с дискретным контролем в условиях неполной информации. Применить полученные результаты в задаче распределения нагрузки в энергосистеме.
Цель достигается путём решения следующих задач:
-
Сформулировать постановку задачи оптимизации линейной динамической системы с дискретным контролем, описывающей функционирование предприятия с учетом присущих ему финансовых механизмов деятельности и запаздываний в системе.
-
На основе аппарата имитационного моделирования и стохастического программирования разработать метод оптимизации линейных динамических систем с дискретным контролем в условиях неполной информации.
-
Создать информационные средства прогнозирования деятельности предприятия.
-
Решить проблему оптимизации нагрузки в энергосистеме при неполной информации.
Научная новизна диссертации состоит в разработке и исследовании методов оптимизации особого класса линейных динамических систем с дискретным контролем при неполной информации, возникающих в задачах планирования и прогнозирования на предприятии. В частности:
С позиций линейных динамических систем разработана математическая модель функционирования предприятия, учитывающая временные запаздывания и основные компоненты работы предприятия: закупка сырья, выпуск продукции, ее хранение, воспроизводство фондов, деятельность персонала, финансовые взаимоотношение предприятия с дебиторами, кредиторами и фискальными органами, различные стратегии маркетинга.
Предложен модифицированный метод стохастического квазиградиента, обеспечивающий двухэтапное планирование деятельности предприятия.
Разработан и исследован статистический метод оптимизации линейных динамических систем с дискретным контролем, основанный на декомпозиции исходной задачи и принципах имитации систем.
Практическая ценность диссертации заключается в разработке методических, алгоритмических и программных средств оптимизации и оценки решения статистических линейных динамических систем с дискретным контролем, ориентированных на реализацию проблемы планирования и прогнозирования на предприятиях при неполной информации.
Научные результаты диссертационной работы могут быть использованы в задачах планирования и прогнозирования на предприятии в условиях, когда процесс функционирования предприятия описывается линейной динамической системой, в том числе, когда параметры планирования частично неопределенны.
Методы исследования. Для решения поставленных задач были использованы аппарат линейного и стохастического программирования, теоремы лагранжевой двойственности, метод имитационного моделирования.
Автор защищает:
-
Линейную динамическую модель функционирования предприятия, описывающую основные компоненты и механизмы финансово-хозяйственной деятельности предприятия.
-
Метод оптимизации линейных динамических систем с использованием принципов декомпозиции и верхней оценки дуальной функции; результаты его сравнения с методом Данцига-Вольфе.
-
Имитационную модель оптимизации статистических линейных динамических систем с дискретным контролем при неполной информации о параметрах планирования, обеспечивающую решение задачи прогнозирования результатов работы предприятия.
-
Модифицированный метод стохастического квазиградиента в задаче двухэтапного планирования на предприятии.
-
Программные средства, реализующие методику статистического оценивания решений линейных динамических систем; результаты их применения при оптимизации распределения нагрузке в энергосистеме на примере ОАО "Красноярскэнерго".
Реализация результатов работы. Разработанные методы оптимизации статистических линейных динамических систем и программное обеспечение внедрено в ОАО "Красноярскэнерго" для использования в работе по планированию работы предприятий энергосистемы.
Апробация работы. Основные положения диссертации представлялись и докладывались на региональных, Всероссийских и Международных конференциях: Международной конференции "Математические модели и методы их исследования (задачи механики сплошной среды, экологии, технологических процессов, экономики)" (г. Красноярск, 1999); первом Всероссийском симпозиуме "Стратегическое планирование и развитие предприятий" (г. Москва, 2000); региональной конференции "Образование XXI века: инновационные технологии, диагностика и управление в условиях информатизации и гуманизации" (г. Красноярск, 2000).
Публикации. Результаты проведенных теоретических и экспериментальных исследований опубликованы в 6 печатных работах.
Структура и объем работы. Диссертационная работа состоит из введения, пяти глав, заключения, библиографии (71 наименование), содержит 109 страниц машинописного теста, иллюстрируется 6 рисунками.
Описание простейшего однопродуктового элемента экономики
В математической экономике получили распространение два типа моделей - управляемые и прогнозные. В управляемых моделях можно выделить три группы переменных: 1) фазовые координаты - переменные, которыми принято характеризовать текущее состояние объекта (например, производственные мощности, запасы продуктов, объемы трудовых и финансовых ресурсов); 2) управляющие воздействия (или управления) - переменные, влияющие на изменение этого состояния и поддающиеся целенаправленному выбору (например, приросты мощностей, выпуски и перевозки продуктов); 3) исходные данные и внешние воздействия - начальные значения фазовых координат и другие параметры и функции времени, задаваемые извне (например, удельные сырьевые и фондообразующие затраты).
Разделения не заданных извне экономических переменных на фазовые координаты и управления в значительной мере условно. Это дань традиционной терминологии, сложившейся в задачах оптимального управления с дифференциальными связями. Однако среди экономических задач встречаются случаи, когда такая классификация невозможна, и тогда необходимым признаком управляемой модели будет просто ее не замкнутость.
Управляемая модель позволяет при фиксированных исходных данных и внешних воздействиях определять фазовые координаты как функции времени, если только заданы управления как функции времени (или как функции времени, фазовых координат и внешних воздействий). Таким образом, управляемая модель может использоваться как для целей прогноза, т.е. отвечать на вопрос: "что будет, если..." (данный режим называется в литературе режим функционирования), так и для целей оптимального планирования, отвечая на вопрос: "как управлять, чтобы достичь желаемых результатов" (данный режим получил название режима планирования). В отличие от управляемых моделей, в прогнозных моделях управления не выделены явно. Такие модели не могут использоваться в режиме планирования, а в режиме функционирования они могут давать только один вариант прогноза, отвечающего на вопрос: "что будет, если сохранять старые тенденции в управлении". Это связано с тем, что при построении чисто прогнозных моделей к экономике относятся как к "черному ящику": не описывая внутренних механизмов, сразу устанавливают функциональные связи между выходами и входами объекта; в этих связях предусматривают параметрические свободы, которые используют для согласования результатов расчета по модели с поведением реального объекта. Однако в экономике нет возможностей для проведения экспериментов на достаточно представительном множестве законов управления. Поэтому функциональные связи между входами и выходами объекта нельзя установить достаточно адекватно. Таким образом, для планового способа управления экономикой управляемые модели экономических процессов предпочтительнее, чем чисто прогнозные модели, ибо в последних реальные управляющие воздействия не отражаются явно и поэтому не доступны формализованному выбору. В данной работе исследуется управление на экономическом уровне, то есть задача состоит в том, чтобы сбалансировать по входам и выходам все производственные процессы и выбрать направление развития, обеспечивающее достижение социальных или иных целей. На экономическом уровне каждый отдельный технологический процесс считается неуправляемым, но остается возможность повторять процессы во времени и пространстве, отказываться от старых процессов и вводить новые из набора возможных. Число повторений, места и моменты этих повторений, отключений и пусков, финансовые и административные воздействия составляют управления экономического уровня. В результате такого разделения управляющих воздействий достигается уменьшение размерности задачи на экономическом уровне (уменьшается как число управлений, так и число фазовых координат, поскольку не надо следить за состоянием каждого производственного процесса). Периоды колебаний параметров производственных процессов, как правило, много меньше характерных масштабов времени для экономических задач, поэтому на экономическом уровне в качестве таких параметров можно использовать величины, усредненные по периоду колебаний: постоянными нормами расхода сырья, постоянными нормами трудовых затрат и т. п., зависящими только от типа производственного процесса. Все экономико-математические модели, рассматривающиеся в литературе, специализируются по уровням иерархии существующей системы экономического управления: межотраслевой баланс и эконометрические модели - верхний уровень, регионально-отраслевые модели - средний уровень, модели предприятий - нижний уровень. Данная работа посвящена моделям нижнего уровня - моделям предприятий. Этот класс моделей обслуживает задачи календарного планирования и оперативного управления производством на уровне предприятия. Модели предприятий специализируются в зависимости от характера производства - непрерывного или дискретного. Непрерывные производства, описываются в терминах потоков продуктов (отсюда проистекает второе название - поточные производства). Потоки характеризуются своей интенсивностью - количеством продукции в единицу времени. К непрерывным относятся производства, выпускающие "делимую" продукцию: жидкости, металл, ткани и. т. п., а также "неделимую" продукцию (детали), в тех случаях, когда число деталей, выпускаемых за характерное для задачи время, намного больше единицы. В противном случае производство нужно рассматривать как дискретное. Задачи календарного планирования и оперативного управления для непрерывного производства ставятся в двух основных вариантах: 1) распределение материальных и энергетических потоков при фиксированной схеме включения агрегатов.
Вычисление дуальной функции с помощью лагранжева ослабления соединенных ограничений
Если 0, то СТОП: текущее решение главной задачи есть оптимальное решение задачи II. Значение этого оптимального решения v, а оптимальные переменные текущей главной задачи позволяют определить оптимальное решение задачи по формуле:
Вычислим значение дуальной функции при текущем : Это значение является минорантой оптимума . Также вычислим оптимальное значение текущей главной задачи , где k - количество столбцов в главной задаче на текущей итерации. Это значение является мажорантой оптимума , так как главная задача получается из задачи II заменой некоторого числа переменных нулями. Таким образом, для проверки критерия остановки нам необходимо проверить условие:
Если оно выполняется, то СТОП, требуемая точность вычисления оптимального значения достигнута. Оптимальное решение задачи вычисляется также как и в пункте в). Таким образом, метод Данцига-Вольфе отличается от метода субградиента, описанного выше, способом выбора последовательности . При этом метод Данцига-Вольфе имеет следующие недостатки по сравнению с описанным выше методом субградиента: 1. Для реализации метода Данцига-Вольфе на ЭВМ необходимо хранить в памяти ЭВМ все полученные на предыдущих итерациях значения (или значения ). В методе субградиента этого не требуется. Таким образом, необходимый для реализации метода Данцига-Вольфе объем памяти возрастает с увеличением требуемой точности решения. 2. На каждом шаге процедура выбора нового значения сопряжена с решением задачи линейного программирования. При этом количество столбцов в матрице ограничений данной задачи увеличивается на 1 на каждой итерации метода Данцига-Вольфе. Вследствие этого с возрастанием числа итераций данная задача становится сложнее, а следовательно увеличивается длительность итерации. Кроме того, если требуемая точность решения задачи достаточно высока и для ее достижения необходимо провести большое число итераций, то в этом случае на конечных шагах алгоритма для получения значения нам придется решать задачу линейного программирования большой размерности. Процедура выбора нового значения в методе субградиента значительно проще: = + . При этом для получения значения шага необходимо провести преобразование = ( ). Множество в подавляющем большинстве случаев невелико, так как и должно выполняться условие / = Z(j). Поэтому в процессе преобразования = ( ) решается система уравнений с, как правило, небольшим числом переменных. Кроме того, сложность данной системы уравнений примерно одинакова на каждой итерации алгоритма субградиента.
Сходимость метода Данцига-Вольфе, по оценкам специалистов [31], является достаточно медленной, особенно в окрестности оптимума. 1. Переход к дискретному времени обеспечивает решение проблемы оптимизации линейной динамической системы в классе задач линейного программирования. Предложено эффективное разбиение матрицы ограничений полученной задачи, что позволило свести ее решение к последовательности решения задач линейного программирования значительно меньшей размерности. 2. Разработаны методика определения верхней оценки дуальной функции и основывающийся на ней алгоритм оптимизации линейных динамических систем с использованием принципов декомпозиции. 3. Преимущество разработанного метода оптимизации линейных динамических систем по сравнению с методом Данцига-Вольфе состоит в более простой процедуре формирования последовательностей , сходящейся к решению дуальной задачи, и , сходящейся к решению исходной задачи. Для реализации на ЭВМ разработанного метода требуется значительно меньший объем памяти, чем для реализации метода Данцига-Вольфе.
Рассматриваются задачи оптимизации и анализа решения статистических линейных динамических систем с дискретным контролем. Для получения статистических оценок оптимума целевой функции и решения используется метод имитационного моделирования. Для решения задачи оптимизации статистических линейных динамических систем с дискретным контролем большой размерности, возникающих в задачах двухэтапного планирования на предприятии, разрабатывается модифицированный алгоритм стохастического квазиградиента, позволяющий использовать декомпозицию системы.
Решение задачи двухэтапного планирования при неполной информации методами стохастического программирования
Блок решения основной задачи является главным и реализуется при помощи алгоритма оптимизации линейных динамических систем с использованием декомпозиции, описанного в главе 2. Блок решения задач линейного программирования является вспомогательным и реализуется на основе модифицированного симплекс-метода с использованием операции, предотвращающей зацикливание. Блок генерации случайных параметров задачи перед каждой имитацией выдает случайные нормально распределенные параметры задачи с заданными математическим ожиданием и дисперсией. Блок статистической обработки результатов после каждой имитации, на основании анализа полученных к данному моменту выборок, выдает статистические характеристики решения задачи.
Созданное программное обеспечение использует в качестве файла данных специальный файл Microsoft Excel, содержащий именованные диапазоны. Программа может создать шаблон файла данных, содержащий незаполненные таблицы для всех необходимых входных данных. Для создания файла данных пользователю необходимо только ввести данные в таблицы шаблона. Входными данными являются: 1. Математические ожидания неточно заданных параметров, 2. Дисперсии неточно заданных параметров, 3. Верхние и нижние пороговые значения оптимального решения. Процесс считывание данных из файла происходит следующим образом. Пользователь должен выбрать файл данных, после чего с данным файлом устанавливается соединение. Каждая таблица с данными соответствует определенному именованному диапазону. Считывание данных происходит посредством ODBC драйвера для файлов Microsoft Excel. Блок 2: Интерфейс. При помощи интерфейса пользователь вводит требуемую точность вычисления оптимума функции цели при решении каждой из главных задач, количество имитаций в эксперименте, а также задает параметры других целей эксперимента. После этого может быть начат эксперимент. Эксперимент состоит из последовательных имитации. В начале каждой имитации в специальном блоке происходит генерирование случайных параметров задачи на основе полученных из файла данных статистических характеристик каждого параметра. После этого полученные параметры передаются в блок решения основной задачи. В блоке решения основной задачи происходит поиск оптимального решения основной задачи при полученных параметрах. Полученное решение передается для обработки в блок статистической обработки результатов. Пользователь может в любой момент прервать проведение эксперимента, а затем продолжить его. При этом все полученные ранее данные будут сохранены, а при возобновлении эксперимента пользователем он начинается с последней незавершенной имитации. Блок 3: Генерация параметров задачи. На основании полученных из файла данных математического ожидания и дисперсии генерируется случайная нормально распределенная величина для каждого из неточно заданных параметров. Процесс генерации происходит следующим образом. Создается OLE - объект приложение Microsoft Excel, после чего в данном приложении открывается специальный файл. В определенные две ячейки (B2 и C2) этого файла записываются математическое ожидание параметра и его дисперсия соответственно, после чего в третьей ячейке, где записана формула =НОРМОБР(СЛЧИС();B2;C2) автоматически генерируется случайная нормально распределенная величина с введенными математическим ожиданием и дисперсией. Возможен также другой метод генерации случайных чисел с нормальным распределением при помощи центральной предельной теоремы. Как видно из описания, данный блок программного обеспечения может быть легко адаптирован к отличным от нормального законам распределения, а также к случаю, когда закон распределения параметров задачи неизвестен, а известна выборка их значений.
В данном блоке решается детерминированная задача линейного программирования, в которой неточно заданные параметры заменены случайными числами, полученными из блока генерации параметров задачи. Перед началом алгоритма определяется множество допустимых решений данной задачи. Если оно пусто, или состоит из единственного вектора, то решение главной задачи заканчивается. Если какие-то переменные могут принимать только одно допустимое значение, то эти переменные при решении не учитываются, и решается задача с меньшим количеством переменных. Задача решается посредством поиска оптимума дуальной функции с помощью алгоритма субградиента и метода выбора шага, описанных в главе 2. Для решения вспомогательных задач соответствующая информация передается в блок решения задач линейного программирования, откуда после обработки возвращается решение и значение оптимума вспомогательной задачи. Блок 5: Решение задачи линейного программирования. Для решения вспомогательных задач используется модифицированный симплекс-алгоритм. Для каждой из задач указывается исходный реализуемый базис (данная матрица для задачи оптимизации распределения нагрузки в энергосистеме приводится в главе 5). Пусть m - число ограничений вспомогательной задачи.
Краткое описание блоков, входящих в состав программного обеспечения
Вернемся к решению задачи (5.1) - (5.6). Рассмотрим теперь задачу составления оптимального плана производства электроэнергии при неполной информации. Введем следующие обозначения: M[X] - математическое ожидание случайной величины X, dev[X] - среднеквадратичное отклонение случайной величины X. Одними из актуальных задач, возникающих при управлении производством, являются задачи прогнозирования результатов работы предприятия. Одна из простых задач такого типа может быть сформулирована следующим образом. План работы энергосистемы составляется в условиях полной информации, планирование происходит в рамках построенной в данной главе модели, то есть оптимальный план соответствует оптимальному решению задачи (5.1) - (5.6). Нам нужно оценить статистические характеристики оптимума целевой функции до поступления полной информации о параметрах планирования, имея информацию только о виде распределения, математическом ожидании и дисперсии параметров планирования. Эту задачу можно решить при помощи метода имитационного моделирования, как было описано в главе 3. Для решения данной задачи прогнозирования под построенную модель функционирования энергосистемы было адаптировано описанное в главе 4 программное обеспечение. Исходные данные для экспериментов, приведенные в приложении, брались на основе анализа реальных данных работы предприятий энергосистемы ОАО "Красноярскэнерго", г. Красноярск, за 1995 - 1996 годы. Предполагалось, что параметры задачи распределены нормально. Каждый эксперимент состоял из 55 имитаций. В первом эксперименте среднеквадратичное отклонение каждого из параметров было равно 0,05 , где M - математическое ожидание рассматриваемого параметра. Во втором эксперименте среднеквадратичное отклонение каждого из параметров было равно 0,15 . Полученные выборки оптимумов целевой функции и результаты их статистической обработки представлены в приложении. Пользуясь полученными результатами оценим ширину доверительного интервала, в котором с вероятностью 95% должно лежать математическое ожидание оптимума функции цели (см. (3.6)). Имеем = 0,025, = 1,96, M = 55. Для первого эксперимента 120885,1 руб., поэтому 2 = 2 x 1,96 x 120885,1 / = 63896,5 руб. Так как выборочное среднее для данного эксперимента = 4728191 руб., то 1,35%. Для второго эксперимента 288916,7 руб., поэтому 2 = 2 x 1,96 x 288916,7 / = 152713,5 руб. Так как выборочное среднее для данного эксперимента = 4713211 руб., то 3,2%. Оба результата являются вполне удовлетворительными. График зависимости выборочного среднего для выборки оптимумов целевой функции на каждой имитации для обеих экспериментов представлен на рисунке 5.1. Горизонтальной линией на этом рисунке указано решение детерминированной задачи, т.е. когда среднеквадратичное отклонение параметров задачи равно нулю.
Другой интересной задачей, возникающей при управлении производством, является задача определения плана, когда некоторые из параметров планирования являются неточно заданными. Одну из задач данного типа можно сформулировать следующим образом. Будем считать, что планирование происходит в два этапа. Первый план составляется до момента начала планирования. При составлении этого плана мы обладаем полной информацией о параметрах задачи для t , , а для параметров задачи при t нам известны только их вид распределения, математическое ожидание и дисперсия. В момент времени , , мы получаем дополнительную информацию (обозначим ее ) о неточно заданных параметрах, и с этого момента все параметры задачи считаются точно заданными. В этот момент составляется второй план (коррекция), который и реализуется с момента . При этом коррекция плана ухудшает значение целевой функции на величину . На коррекцию накладывается естественное условие = 0, , где - множество индексов компонент, для которых . Это есть не что иное, как задача двухэтапного стохастического программирования, рассмотренная нами для общей задачи в главе 3.
