Содержание к диссертации
Введение
Глава 1. Модель динамического взаимодействия двух промышленных предприятий 16
1.1. Постановка задачи 16
1.2. Условия существования, единственности и оптимальности 16
1.3. Проблема тривиальности решения сопряженной задачи 23
1.4. Регуляризация принципа Максимума 25
1.5. Продолжение решений по параметру 33
Глава 2. Математическое моделирование линейных динамических систем со смешанными ограничениями 34
2.1. Постановка параметрической задачи оптимального управления ... 34
2.2. Необходимые условия оптимальности для общей задачи оптимального управления. Принцип максимума Понтрягина и формализм Дубовицкого-Милютина 38
2.3. Линейные параметрические модели с ограничениями смешанного типа 41
2.4. Условия оптимальности для линейных задач 43
2.5. Задачи оптимального управления 1 и 2 43
Глава 3. Решение линейных задач оптимального управления со смешанными ограничениями методом дискретизации по времени 49
3.1. Построение конечно-разностной аппроксимации модели 49
3.2. Схема решения параметрических задач оптимального управления. 52
3.2.1. Получение аппроксимации решения прямой задачи 57
3.2.2. Выделение множества активных ограничений 58
3.2.3. Построение аппроксимации решения сопряженной задачи 59
3.3. Сходимость дискретных аппроксимаций 61
Глава 4. Задачи линейного программирования 72
4.1. Различные формы задач линейного программирования (ЛП) 72
4.2. Двойственность в задачах ЛП 73
4.3. Метод эллипсоидов 77
4.4 Метод внутренней точки 79
4.5. Барьерно-проективные методы 80
4.6. Устойчивость задач ЛП 85
4.7. Регуляризация неустойчивых задач 88
4.8. Обобщённая задача ЛП 90
Выводы 92
Список публикаций автора 92
Литература 94
Приложение 1 104
Приложение 2 112
- Условия существования, единственности и оптимальности
- Постановка параметрической задачи оптимального управления
- Построение конечно-разностной аппроксимации модели
- Двойственность в задачах ЛП
Введение к работе
Развитие отечественного промышленного производства за счет повышения эффективности взаимодействия промышленных предприятий может обеспечить решение целого ряда острых производственных и социально-экономических проблем в условиях кризиса. При этом необходимо отметить, что замещение импорта должно помочь развитию отечественного производства и проведению технического перевооружения российских предприятий, значительный износ оборудования которых приводит к снижению эффективности промышленного производства в целом. Эти вопросы становятся достаточно актуальными в современных условиях экономического кризиса.
Отметим, что показатели конкурентоспособности улучшаются при объединении предприятий в рамках корпорации. Большую роль приобретают методики и технологии, которые позволяют повысить уровень производственных и социальных показателей. Особо важное значение приобретают методы подготовки и принятия эффективных управленческих решений.[33-35],[54].
Наступивший кризис промышленного производства выявил очевидную необходимость пересмотра методов управления промышленными предприятиями в сторону улучшения эффективности потребления ресурсов. Настоящая работа посвящена решению важной частной задачи — улучшению эффективности взаимодействия промышленных предприятий. Цель работы.
Целью работы является: построение модели взаимодействия промышленных предприятий в условиях кризиса производства; решение задач оптимального управления с фазовыми и смешанными ограничениями (схема Дубовицкого-Милютина [9]-[11]) для разработанной модели; решение задач линейного программирования большой размерности методом продолжения решения по параметру [24]-[30]; на основании проведенных исследований - предоставить возможность выработки обоснованных эффективных управленческих решений для оптимального развития промышленного производства в условиях кризиса. Методы исследования. Основным инструментом для решения поставленных задач является принцип максимума (схема Дубовицкого-Милютина) и метод продолжения решения по параметру. Поставленные задачи (за счет дискретизации обыкновенных дифференциальных уравнений) сводятся к задачам линейного и нелинейного программирования большой размерности [20]-[23], [36]-[39], [43], [44], [53], [55], [62], [63],[87-97]. Применение принципа максимума в дискретном варианте сводит первоначальную задачу к задаче линейного программирования большой размерности. В качестве параметра выступает время. Это позволяет сначала на малом отрезке решать задачу малой размерности и затем полученное приближение используется при его продолжении по параметру. Научная новизна.
Решена новая важная задача эффективного управления ресурсами с учетом взаимодействия двух промышленных предприятий в условиях кризиса производства.
Разработан новый эффективный подход к решению задачи линейного программирования большой размерности за счет продолжения решения по параметру. Для интегрирования жестких систем обыкновенных дифференциальных уравнений разработаны специальные явные схемы [24]-[29], [63], [80], которые показали свою эффективность при численном решении указанных систем. Также были применены методы параметризации при качественном и численном решении задачи взаимодействия двух промышленных предприятий [33]. В предложенной модели принцип максимума выполняется тривиально, т.е. является вырожденным. Для построения содержательного принципа максимума в правые части обыкновенных дифференциальных уравнений вводятся малые параметры, которые позволяют исследовать задачу с помощью классического принципа максимума [1]-[16]. Данный подход является новым, так как по существу применяется регуляризация основной задачи в отличие от известных работ, в которых регуляризация применяется для сопряженной системы уравнений. Обоснованность научных положений.
Теоретические положения и выводы диссертации сформулированы в виде утверждений и теорем, которые строго доказаны. Практическая ценность.
Модели, методы и алгоритмы, разработанные в диссертации, применялись для решения практических задач взаимодействия промышленных предприятий, а также в учебном процессе в Московском Физико-Техническом институте и в Вычислительном Центре РАН. Предложенные методы продолжения решения по параметру, а также методы регуляризации вырожденных задач могут быть использованы в теоретических исследованиях при решении прикладных задач оптимального управления. Был адаптирован пакет прикладных программ БАЛАНС-2 для решения задачи ЛП и использован для практических численных расчетов показателей эффективности производства на модельном примере (с применением метода продолжения решения по параметрам).[27], [41],[62],[80].
Апробация работы.
Основные положения исследования докладывались и обсуждались на международной конференции в Черногории (International Conference «Nonlinear Analysis and Optimization Problems», Montenegrin Academy of Sciences and Arts, Petrovac, Montenegro, October 06th - 10th , 2008), на 14-ой Байкальской школе-семинаре СО РАН «Методы оптимизации и их приложения». (Иркутск-Байкал 2-8-го июля 2008г.) и на научных семинарах в МФТИ и в ВЦ РАН.
Личный вклад.
1) Проведен качественный и количественный анализ задачи эффективного управления взаимодействием двух промышленных предприятий.
2) Разработан прямой численный метод построения гипотезы по определению множества активных индексов для задачи управления с ограничениями типа неравенств (геометрия оптимальной траектории).
3) Предложена регуляризация вырожденного случая принципа максимума.
4) Разработан явный эффективный численный метод решения жестких систем ОДУ.
5) Автором адаптирован пакет прикладных программ БАЛАНС-2, использование которого позволяет выработать обоснованные управленческие решения.
Публикации. Основные результаты исследования отражены в восьми публикациях. Список работ приведен в конце автореферата. В совместных работах автору принадлежит 50% результатов.
Структура и объем работы.
Диссертация состоит из введения, четырех глав, шести рисунков, одной таблицы и двух приложений. Список использованной литературы составляет 109 наименований.
Условия существования, единственности и оптимальности
Необходимые условия оптимальности для задачи 1 формулируются в терминах принципа максимума Понтрягина с использованием сопряженных переменных цг(і). Связь сопряженных переменных y/{t) и переменных задачи 2 дается следующими леммами:
Лемма 1. Если при допустимом управлении задачи 1 существует вектор сопряженных переменных y/{t), константа у0 0 и векторы множителей Лагранжа Л((), ju(t), удовлетворяющие дифференциальным уравнениям и краевым условиям для y/{f), условиям Блисса и условиям дополняющей нежесткости для A,(t), ju(t), то Я(/) и y/(t) являются допустимыми управлением и фазовым вектором задачи 2. Лемма 2. Если существуют допустимые управления u (t), v(t), 77 задач 1 и 2, и они удовлетворяют условиям (2.5.9)-(2.5.11), то вектор траектории x(t) задачи (2.5.5)-(2.5.8), соответствующей управлению v(/), является вектором сопряженных переменных y/(t) задачи (2.5.1)-(2.5.4) при y/Q = -\. На основании лемм 1 и 2 теорема 1 переформулируется следующим образом: Теорема 2. Если при данном допустимом управлении u (t) задачи 1 существуют число 0=-1, кусочно-гладкая вектор-функция y/{t), измеримые вектор-функции Я(7) 0, /j(t) 0 и вектор /? 0 такие, что выполняются условия (2.5.12)-(2.5.15), то u (t) - оптимальное управление задачи 1. Таким образом, теорема 2 дает возможность использовать сопряженные переменные y/{t) для доказательства оптимальности полученного решения в задаче ОУ. Третья глава посвящена вопросу нахождения первого приближения геометрии оптимальной траектории при смешанных ограничениях, типа неравенств. Исследуется вопрос об эффективном (с точки зрения затрат машинных ресурсов) способе нахождения- численного решения задач 1 и 2. Требование эффективного решения обусловлено многократным решением задач 1 и 2 при различных значениях параметров. Известно, что достаточно экономичные методы решения задач класса 1—2 базируются на использовании методов прогонки, требующих априорного разделения для каждого te[0,T] множества условий gj(x,u,t) 0;j = l,m на подмножествах активных и неактивных ограничений. При этом, как правило, используются какие-либо специфические особенности системы ограничений. В этом случае приемлемой альтернативой сложным схемам решения задач оптимального управления методом прогонки может служить схема формирования гипотезы о геометрии оптимальной траектории задачи 1-2, основанная на использовании приближенного решения, получаемого путем дискретизации времени. Преимущества предлагаемого метода заключаются в том, что он не различает отдельные ограничения на ограничения по фазам, управлениям или смешанным ограничениям. Следовательно, метод решения дискретизированной задачи не будет обладать недостатками метода прогонки. Дискретизированная задача является задачей ЛП, и в этой задаче фазовые и управляющие переменные уже неразличимы, что является преимуществом данного подхода. Следовательно, для получения решения дискретизированной задачи необходимо надежное программное средство.
Суть рассматриваемой схемы выделения множества активных ограничений заключается в дискретизации времени и сведении исходной задачи 1-2 к вспомогательной задаче математического программирования с конечным числом переменных. Дифференциальные уравнения при этом заменяются конечно-разностными по схеме Эйлера первого или второго порядка точности. Подобные задачи рассмотрены в трудах Ю.Г. Евтушенко. Решение данной вспомогательной задачи рассматривается как некоторое приближение к решению исходной, и на его основании производится выделение подмножества активных ограничений.
Приведена иллюстрация применения теоремы об устойчивости для различных случаев изменения параметров задачи. Сначала рассмотрены случаи, когда изменяется только один из параметров: с, Ь или А. Затем случаи, когда меняются пары параметров, и, наконец, последний случай одновременного изменения всех трех параметров. Далее рассматриваются частные случаи устойчивости задачи ЛП. В четвертой главе излагаются различные формы задач линейного программирования (ЛП), куда входят также несобственные задачи. Здесь для решения задачи ЛП предлагается метод введения параметра в целевую функцию. Это дало возможность получить эффективную оценку решения задачи ЛП. Кроме того использовался адаптированный пакет прикладных программ БАЛАНС - 2, обеспечивающих многократное формирование условий нахождения решения и создания необходимых для анализа выходных файлов. Была использована реализация для ОС Windows 2К-ХР базовой версии алгоритма анализа неполных математических моделей (разработанная в 1985 году в IIASA, в рамках проекта Regional Development, на языке "Fortran-IV" для ПЭВМ Altus-2. Авторы: Ким К.В. и Умнов А.Е.), адаптированная для языка C++ на кафедре высшей математики МФТИ в рамках совместных исследований с ЗАО «Оптимизационные системы и технологии» [62], [68]-[77]. В комплекс программных средств решения задач ЛП были включены модули диагностики и анализа качества (получаемых на основе найденных решений) гипотез об оптимальной геометрии фазовых траекторий. Специальные программные средства были разработаны для решения сопряженных задач, проверки формализма Понтрягина-Дубовицкого-Милютина и прямой проверки оптимальности решения на множестве допустимых вариаций.
Постановка параметрической задачи оптимального управления
Отметим, что задача (2.1.12) в принципе может быть сведена к задаче без параметров, подобной (2.1.1)-(2.1.3) путем переопределения компонент вектора параметров p(t) в дополнительные компоненты вектора управлений и(0 и включения условий, задающих множество Q, в систему (2.1.3). И, следовательно, с формальной точки зрения нет необходимости выделять параметрические задачи в отдельный класс. Однако практика использования математического моделирования управляемых динамических систем в ряде случаев оправдывает такое выделение.
Дело не только в том, что при попытке включения параметров в структуру вектора управлений имеет место, весьма нежелательное с точки зрения минимизации затрат вычислительных ресурсов, увеличение размерности решаемой задачи (поскольку, в крайнем случае, число компонент вектора управления может возрасти от значения г до r + q). Существенно более серьезной проблемой при данном подходе оказывается вполне возможное усложнение структуры задачи (2.1.1)-(2.1.3), которое может стать причиной невозможности использования ранее применявшихся алгоритмов решения этой задачи в исходной постановке (например, задача может превратиться из линейной в нелинейную). Напротив, искусственное переопределение части компонент вектора управлений в компоненты вектора параметров может не только снизить суммарные затраты вычислительных ресурсов, но и позволит использование более простых и надежных алгоритмов, в тех случаях, когда параметризация упрощает структуру исходной задачи оптимального управления. В данной работе исследуется случай, когда с помощью параметризации исходной линейной задачи (2.1.9)-(2.1.11) становится возможным получить решение нелинейной (по совокупности управлений и параметров) задачи оптимального управления со смешанными ограничениями. При этом используются технологии получения решений линейных задач оптимального управления. При использовании метода параметризации для линейной задачи (2.1.9)-(2.1.11) осуществляется включение параметров p{t) в какие-либо из коэффициентов задачи а„ (О А (0, ,(0, (0 и rf,(O,et(O c,(f),u 7(0» ПРИ i,l = [l,n],j = [l,m] и к = [1,г] таким образом, что по совокупности управлений unew (О задача перестает быть линейной. Следует отметить, что при произвольном включении параметров в коэффициенты исходной линейной задачи практически всегда получается нелинейная задача оптимального управления, а значит использование метода параметризации, в котором для каждого фиксированного значения параметра решается линейная задача оптимального управления, расширяет класс решаемых задач. Необходимые условия оптимальности для общей задачи оптимального управления. Принцип максимума Понтрягина и формализм Дубовицкого-Милютина
Рассмотрим задачу оптимального управления со смешанными ограничениями (2.1.1)-(2.1.3). Предполагается, что ограничения (2.1.3) независимые. С содержательной точки зрения это означает, что эти ограничения могут быть удовлетворены локально в каждой точке (t, х) за счет выбора управлений. Формально это означает, что в каждой точке {x,u,t), для которой эти ограничения выполнены,
Построение конечно-разностной аппроксимации модели
Рассмотрим вопрос об эффективном (с точки зрения затрат машинных ресурсов) способе нахождения численного решения задачи (2.3.1)-(2.3.3). Требование эффективного решения обусловлено многократным решением задачи (2.3.4)-(2.3.6) при различных значениях параметров. Известно [24]-[30], [43]-[51], что достаточно экономичные методы решения задач класса (2.3.1)-(2.3.3) базируются на использовании методов прогонки, требующих априорного разделения для каждого /є [0,7] множества условий на подмножества активных и неактивных ограничений.
При этом, как правило [23]-[51], используются какие-либо специфические особенности системы ограничений (2.3.3). Например, в случае, когда набор условий (2.3.3) распадается на подсистемы фазовых и управляющих ограничений, оказывается возможным сведение (2.3.1)-(2.3.3) к некоторой краевой задаче.
В рассматриваемом случае, однако, наличие ограничений смешанного типа (то есть условий, связывающих одновременно фазовые и управляющие переменные) создает существенные трудности для использования метода прогонки, и потому решение исходной задачи оказывается сложнее используемых в вычислительной практике алгоритмов из-за большого числа возможных вариантов разбиения множества условий (2.1.3) на активные и неактивные. В [30] показано, что, хотя данное разбиение и является функцией времени, для задач класса (2.3.1)-(2.3.3) существует конечное число интервалов на промежутке t є [О, г], на которых множество активных ограничений не меняется. Однако для использования метода прогонки необходимо проверить все возможные варианты разбиения множества индексов ограничений на активные и неактивные, причем в зависимости от времени. Итогом получается комбинаторная задача с огромным числом вариантов перебора даже для небольшого количества смешанных ограничений. В этом случае приемлемой альтернативой сложным схемам решения задач оптимального управления методом прогонки может служить схема формирования гипотезы о геометрии оптимальной траектории задачи (2.3.1)-(2.3.3), основанная на использовании приближенного решения, получаемого путем дискретизации времени. Преимущества этого метода заключаются в том, что он не различает отдельные ограничения на ограничения по фазам, управлениям или смешанные ограничения, следовательно, метод решения дискретизованной задачи не будет обладать недостатками метода прогонки. Дискретизованная задача является задачей нелинейного (линейного в линейном случае) программирования, и в этой задаче фазовые и управляющие переменные уже неразличимы, что является преимуществом данного подхода. Следовательно, для получения решения дискретизованной задачи необходимо только надежное программное средство (решатель).
Суть рассматриваемой схемы выделения множества активных ограничений заключается в дискретизации времени и сведении исходной задачи (2.3.1)-(2.3.3) к вспомогательной задаче математического программирования с конечным числом переменных. Дифференциальные уравнения при этом заменяются конечно-разностными по схеме Эйлера первого или второго порядка точности [Евтушенко]. Решение данной вспомогательной задачи можно рассматривать как некоторое приближение к решению исходной, и на его основании произвести выделение подмножества активных ограничений. Приведем детальное описание предлагаемой вычислительной процедуры для общей задачи (2.1.1)-(2.1.3). Пусть временной промежуток [О, Т] разбит на N интервалов одинаковой длины h = —. Тогда разностная аппроксимация уравнений (2.1.2) позволяет перейти от задачи (2.1.1)-(2.1.3) к некоторому ее разностному аналогу. В последующем изложении при аппроксимации дифференциальных уравнений используется одно и то же выбранное разностное отношение, для которого и приводятся формулы. В случае выбора другого, отличного от предложенного, разностного отношения, все формулы также примут другой вид в соответствии с выбранным разностным отношением.
Двойственность в задачах ЛП
Как сказано выше, она представляет из себя задачу линейного программирования относительно переменных хк, ик, / = [1,и], y = [l,r], к = [о, N]. Так как при решении параметрических линейных задач оптимального управления (2.3.4)-(2.3.6) на нижнем уровне решается задача при фиксированных значениях параметров, то в данной записи можно не указывать зависимость столбцов и матриц от параметров. Другими словами, при решении задач нижнего уровня параметры задачи фиксированы, и можем ограничиться записью (3.1.5)-(3.1.7). Решив задачу (3.1.5)-(3.1.7), можно получить приближенные значения фазовых переменных и управлений непрерывной задачи (2.1.9)-(2.1.11) в точках tk=kh, k = 0,N. И выбрав подходящее є для формулы (3.1.4), можно выполнить
Чтобы сформировать правдоподобную гипотезу о геометрии оптимальных траекторий, необходимо при анализе решения аппроксимационных задач четко разделять ограничения типа неравенств на активные и неактивные в каждый момент времени tk =kh. Напомним, раничение типа неравенства называется активным в момент времени t, если в этот момент оно превращается в равенство. Формирование правдоподобной гипотезы позволяет сократить время второго шага решения, на котором и происходит получение оптимального управления и проверка сформированной гипотезы с использованием условий оптимальности. Из опыта решения задач выявлено два основных случая, при которых сформированные гипотезы получаются неоднозначными. Во-первых, в случае быстрого роста управлений возможна неоднозначность в определении того, как изменяется управление в данный момент времени, что происходит - быстрый рост или скачок? Во-вторых, это случай, когда в точке дискретизации значение ограничения мало по абсолютной величине (например, 0 \gj(x,u,t] e 10"7). При этом не существует однозначного ответа на вопрос, является ли эта малая величина значением ограничения (и ограничение является неактивным), или же это погрешность, компьютерных вычислений (а само ограничение является активным). Для обоих случаев предложены и реализованы способы устранения неоднозначности. В первом случае возможно применение схемы повышения разрешающей способности, описанной в [67], либо применение различных схем дискретизации с переменным шагом, имеющих сгущения узлов в окрестностях интересующих точек. Во втором случае увеличение разрядной сетки решателя позволяет однозначно установить активность ограничения, так как при этом уменьшаются погрешности компьютерных вычислений. Подробнее эти случаи рассматриваются в 3.5-3.6.
Для более надежного формирования гипотезы о поведении оптимальных траекторий иногда бывает полезным получить не только аппроксимацию решения прямой (исходной) задачи, но и аппроксимацию решения сопряженной задачи. Под аппроксимацией решения сопряженной задачи будем понимать значения сопряженных переменных ц/1 it), i = l,n в точках дискретизации tk=kh. Опишем процесс получения аппроксимации решения сопряженной задачи.
