Содержание к диссертации
Введение
Глава 1. Место задач распределения ресурсов в иерархических системах в классе задач математического программирования 14
1.1. Моделирование технических объектов как многоуровневых иерархических систем 14
1.2. Задачи оптимального распределения ресурсов в сложных системах как задачи математического программирования 16
1.2.1. Оптимальное распределение ресурсов как задача исследования операций 16
1.2.2. Постановка общей задачи математического программирования. Классификация задач 18
1.2.3. Примеры задач распределения ресурса в сложных иерархических системах .21
1.3. Содержательное описание проблемы оптимального распределения ресурса в
иерархических системах с активными элементами 29
1.3.1. Задачи согласования параметров для участков газотранспортной системы 30
1.3.2. Задачи поиска оптимальных режимов функционирования производственной системы с многорежимным оборудованием 32
1.3.3. Проблема поиска оптимальных режимов функционирования систем отопления 33
1.3.4. Общая проблема оптимального распределения ресурсов в иерархических системах с активными элементами 34
Глава 2. Общая математическая модель и постановка оптимизационных задач распределения ресурсов в иерархических системах с активными элементами 37
2.1. Общая математическая модель распределения ресурсов в иерархических системах с активными элементами 37
2.2. Частные подмодели распределения ресурсов в иерархических системах с активными элементами 42
2.2.1. Транспорт природного газа в газотранспортных системах с газоперекачивающими мощностями в качестве активных элементов 42
2.2.2. Функционирование производственной системы с многорежимным оборудованием в качестве активных элементов 52
2.2.3. Функционирование системы водяного отопления с насосами сетевой воды в качестве активных элементов 57
2.3. Постановки оптимизационных задач распределения ресурсов в иерархических
системах с активными элементами 64
2.3.1. Общая постановка задачи оптимального распределения ресурсов в иерархических системах с активными элементами 65
2.3.2. Постановка задачи оптимизации режимов транспорта природного газа в газотранспортных системах 65
2.3.3. Постановка задачи поиска оптимальных режимов функционирования производственной системы 68
2.3.4. Постановка задачи поиска оптимальных режимов функционирования систем теплоснабжения 69
Глава 3. Алгоритмы решения задач распределения ресурсов виерархических системах с активными элементами 71
3.1. Алгоритм решения задачи оптимального распределения ресурсов в
иерархических системах с активными элементами. Общий случай 71
3.2. Алгоритмы решения задач оптимизации режимов транспорта природного газа в
газотранспортных системах 83
3.2.1. Случай отдельного активного элемента газотранспортной системы 84
3.2.2. Случай газотранспортной системы с активными и пассивными элементами .88
3.3. Случай фрагмента системы отопления с насосными установками в качестве активных элементов 90
3.4. Алгоритм решения задач оптимального функционирования производственной системы 91
Глава 4. Программные средства решения задач распределения ограниченных ресурсов в системах с активными элементами 95
4.1. Структура пользовательского интерфейса программной системы распределения
ресурсов в иерархических системах с активными элементами 95
4.1.1. Модуль базы данных 97
4.1.2. Модуль выполнения решения 99
4.1.3. Модуль представления решения 101
4.1.4. Системные требования 103
4.2. Типовые сценарии решения задач распределения ресурсов в иерархических системах с активными элементами 103
4.3. Решение прикладных задач распределения ресурсов в иерархических системах с использованием разработанных программных средств 109
4.3.1. Решение задач оптимального согласования входов и выходов газотранспортной системы 109
4.3.2. Решение задач поиска оптимальных режимов функционирования производства с многорежимным оборудованием 117
Заключение 125
Список литературы
- Задачи оптимального распределения ресурсов в сложных системах как задачи математического программирования
- Задачи поиска оптимальных режимов функционирования производственной системы с многорежимным оборудованием
- Транспорт природного газа в газотранспортных системах с газоперекачивающими мощностями в качестве активных элементов
- Типовые сценарии решения задач распределения ресурсов в иерархических системах с активными элементами
Задачи оптимального распределения ресурсов в сложных системах как задачи математического программирования
Возникновение теории электрических цепей, как исходная точка формирования «графового» и системного подходов к их математической формализации, ведет свое начало с публикаций Г.Кирхгоффа, относящихся к середине 19-го века. В них были описаны законы равенства нулю векторной суммы токов в местах соединения нескольких проводников. Также были описаны связи сопротивления, тока и электродвижущей силы в рамках последовательности проводников некоторого замкнутого контура, на основании которых было возможно составлять алгебраическую систему уравнений для расчета электрических цепей [71]. Указанные законы лежат в основе методов анализа электрических схем [108].
Протяженные транспортные системы жидких и газообразных продуктов
Представление систем каналов, газо-, нефте- и продуктопроводов, сетей теплоснабжения в виде многоуровневых иерархических систем связано с расчетом режимов их функционирования, и основывается как на законах Кирхгоффа по аналогии с электрическими цепями для описания сохранения массы в точках стыка потоков транспортируемой среды (узлов графовой модели), так и на законах механики сплошной среды для описания изменения параметров транспортируемого продукта в рамках проводников (ветвей графовой модели) [1, 16, 71, 99].
Автомобильные и железнодорожные трассы
С момента возникновения задач, связанных с описанием транспортных потоков, обусловленных, прежде всего проблемами логистики и потребностью регулирования дорожного движения, были предприняты попытки представить потоки транспортных средств в рамках различных моделей, включая моделирование на основе теории равновесия, механики сплошных сред, стохастических моделей, и др. [22]. При этом широко использовался аппарат теории графов [5, 10, 17, 18, 44, 48, 49, 62, 65, 66, 74, 98, 107, 113, 114], а также задач математического программирования, в частности, транспортных задач [33, 43, 52].
Потребность управления сложными, в том числе экономическими и техническими производственными объектами вызвала к жизни специальные методы, облегчающие принятие правильных решений. Эти методы принято объединять термином исследование операций [2, 6, 26, 28, 29, 30, 34, 42, 46, 47, 59, 64, 85, 95, ПО, 115, 116, 121].
Под исследованием операций понимают набор методов выработки количественно-обоснованных объективных рекомендаций по поддержке принятия оптимальных решений. Характерной особенностью исследования операций является системный подход к поставленной проблеме, который заключается в том, что любая решаемая задача должна рассматриваться с точки зрения влияния на критерии функционирования системы в целом [2].
Под операцией понимается любое мероприятие, или система действий, направленное на достижение определенной цели. С целью эффективного решения задач обоснованного принятия решений для операций строятся математическое модели, которые являются результатом частичной абстракции и идеализации реальных объектов, что позволяет перевести дальнейшие исследования в математическую область. Показатель эффективности операций, или целевая функция, может принимать численные значения и являться критерием оценки их качества. Благодаря построению математических моделей операций, их эффективность может быть оценена численно, то есть становится функцией от параметров х1,х2,...,хп, конкретный набор которых определяет стратегию по принятию решения: f = f(xi,x2,-,x„). (1.1) Здесь / - эффективность операции, или целевая функция; xhx2,...,xn - набор факторов, или условий проведения операции, от которых зависит ее эффективность; п - количество факторов. Если в целевой функции (1.1) все факторы являются или заранее установленными, или поддающимися управлению, то имеем дело с детерминированной задачей исследования операций [24].
По своему смыслу и постановкам множество задач исследования операций можно разбить на классы, наиболее распространенными из которых являются: задачи управления запасами, задачи замены и ремонта оборудования, задачи массового обслуживания, задачи календарного планирования (теории расписаний), задачи транспортного типа (выбора маршрутов перевозок), задачи сетевого планирования и управления, задачи планировки и размещения объектов, комбинированные задачи, и задачи распределения ресурсов.
Задачи поиска оптимальных режимов функционирования производственной системы с многорежимным оборудованием
Будем рассматривать сложную систему, состоящую из совокупности взаимозависимых элементов. Совокупность элементов определяет сетевую иерархическую систему и моделируется связным взвешенным ориентированным графом без петель и контуров. Вершины графа определяют элементы системы, а дуги - связи между элементами. Веса графа соответствуют характеристикам вершин, причем мы будем различать «входные» и «выходные» характеристики. Для элементов системы применяются «управления», которые преобразуют входные характеристики в выходные с определенными «затратами». Характеристики элементов выбираются из допустимых областей значений. Для каждого элемента задано множество управлений, допустимых для этого элемента. В общем случае граф, моделирующий сложную систему, может иметь вершины, полустепени исходов которых равны нулю («выходные» элементы), полустепени заходов и исходов большие или равные единице («промежуточные элементы), полу степени заходов равны нулю («входные» элементы).
Для каждого входного элемента и каждого выходного элемента определены значения параметров, характеризующих функционирование системы. Требуется найти такую стратегию управления активными элементами, чтобы были согласованы заданные параметры входных, промежуточных и выходных элементов системы с минимальными суммарными затратами на примененные управления. [84].
Пусть G = (V,A), AczV2 - ориентированный граф без петель и контуров. Множество вершин графа V соответствует элементам системы, множество дуг А - связям между ними. Через K(v) обозначим множество элементов, непосредственно предшествующих элементу, а через ДУ)- множество элементов непосредственно следующих за элементом V , V G V . Через Vex и Veblx обозначим множество входных и выходных элементов, где у входных элементов множества Vex нет предшествующих, Vex = \V\K(V) = 0,VGV}, а у выходных элементов множества Veblx нет последующих, Veblx = {v Q(y) = 0,VGV}. Пусть / - множество характеристик системы, Uv - множество допустимых управлений, соответствующих элементу v, v є V; wv - вектор, определяющий значения характеристик на входе v-ro элемента системы, VGV, wv єR I; W n QjV- минимальные и максимальные возможные значения характеристики / на входе v -го элемента системы, a Htv и Stv - минимальные и максимальные возможные значения характеристики / на выходе v-ro элемента системы, 0 W? Qvt, 0 Нгу Svt, IGI,VGV; p{wv,uv)- вектор-функция, преобразующая входные характеристики элемента v в его выходные характеристики под воздействием допустимых управлений uv, 4 (wv\uv) є Ж , uv GUV,VGV ; fv \4 (wv ,uv )) - вектор-функция, в соответствии с которой вычисляются входные характеристики элемента v по выходным характеристикам всех элементов, непосредственно предшествующих элементу v, uv G\JV,V GK(V),VEV; (f)(wv ,uv)- функция, определяющая затраты, которые получит система, если для элемента v будет применен вектор допустимых управлений иv, uv G UV , v є V. Обозначим через (f - заданные значения характеристик для входного элемента v,veVex, а через gv- заданные значения характеристик для тгвЫХ -.V г \1\ —V г \1\ выходного элемента v,v є V ,Ц є к , g є к .
Введение множества допустимых управлений Uv подразумевает, что иерархическая система формализуется в виде совокупности активных и пассивных элементов. Применение того или иного управления для активного элемента при заданных входных параметрах по-разному реализует выходные параметры. При этом система приобретает «доход», связанный как со значениями входных и выходных параметров, так и с примененными управлениями. Пассивные элементы автоматически преобразуют входные параметры в выходные.
Математическая модель рассматриваемой сложной системы включает в себя следующие ограничения: W W] Ql,rGl,VGV. (2.1) (Характеристики системы на входах всех элементов системы ограничены сверху и снизу) Н] ф ],uv) S],iGl,uv GU\VGV . (2.2) (Характеристики системы на выходах всех элементов системы ограничены сверху и снизу) wv=qv,VGVex. (2.3) (Характеристики входных элементов системы определены в соответствии с заданными значениями) fc \uv) = g\veVm. (2.4) (Характеристики выходных элементов системы определены в соответствии с требуемыми по регламенту значениями) wv=fv(kw\uvlvGK(v)l йуєи\ує\Гвх. (Соблюдение баланса между входными характеристиками некоторого промежуточного элемента системы и выходными характеристиками непосредственно предшествующих ему элементов) . Следуя концепции введенных ранее активных и пассивных элементов, модель (2.1)-(2.5) можно преобразовать далее к иному виду. Введем множества активных Vа и пассивных Vp элементов, Vа V, Vp є V, Vа U Vp = V, Vа П Vp = 0. При этом, только к активным элементам системы применимы допустимые управления из множества Uv.
Введем дополнительные обозначения. Пусть теперь fiv(wv,uv,5)-вектор-функция, преобразующая входные характеристики элемента v в его выходные характеристики под воздействием допустимых управлений uv, (j v{wv,uv,8)&w I, причем 8 - параметр, принимающий значение 1, если v Va (соответствующий элемент с номером v является активным), и 0 -если v =Vp (элемент с номером v является пассивным), uv&Uv,v&V; fv( fiv(ws,us,S),sGK(v))- вектор-функция, в соответствии с которой вычисляются входные характеристики элемента v по выходным характеристикам всех элементов, непосредственно предшествующих элементу v, v є V. Здесь и далее предполагается, что вид функций, преобразующих входные характеристики элементов, предшествующих элементу v, в его выходные характеристики, определяется самим элементом
Транспорт природного газа в газотранспортных системах с газоперекачивающими мощностями в качестве активных элементов
Задачи оптимального распределения ресурсов для разветвленных систем транспорта газа относятся к задачам оптимального планирования. Подобные задачи имеют место на стадии проектирования или модернизации реальных участков магистральных систем транспорта жидких и газообразных углеводородов. Ввиду сложности таких объектов, здесь является целесообразным применение подхода на основе теории многоуровневых иерархических систем [83]. «Многоуровневость» систем транспорта газа проявляется в возможности их декомпозиции на составляющие элементы. В качестве «атомарных» элементов здесь можно рассматривать цеха компрессорных станций и разделяющие их линейные части магистральных газопроводов. Здесь дается конкретизация алгоритма решения задач распределения ресурсов для цехов компрессорных станций как «атомарных» активных элементов газотранспортных систем.
Случай отдельного активного элемента газотранспортной системы
Ранее было показано, что задачу распределения ресурсов, формализующую процесс согласования параметров участка газотранспортной системы по критерию минимизации суммарных затрат, можно сформулировать так. Необходимо при заданных давлениях и коммерческих расходах на входах и выходах газотранспортной системы определить такие управляющие воздействия на активные элементы, при которых с наименьшими суммарными затратами оказываются согласованными заданные значения входных и выходных характеристик системы. Определяющим здесь является необходимость оптимизировать функционирование активных элементов, в качестве которых для газотранспортной системы выступают цеха компрессорных станций.
При решении указанной задачи для компрессорного цеха необходимо учитывать функциональную зависимость, связывающую потребляемую приводом газоперекачивающего агрегата мощность с коммерческим расходом перекачиваемого газа при условии, что все прочие параметры фиксированы. Математическая формулировка такой задачи была приведена в Главе 2 (см. соотношения (2.22)-(2.27),(2.59)). Решение поставленной задачи определяет, какие газоперекачивающие агрегаты и с какой производительностью должны работать в каждом компрессорном цехе. В Главе 2 показано, что такая задача относится к классу NP-трудных, для решения которых не существует точных алгоритмов, в общем случае отличных от полного перебора [120]. Анализ значений параметров реальных компрессорных станций показывает [60], что для решения таких задач, учитывая современное состояния средств вычислительной техники, можно находить точные решения, используя приведенный ниже переборный алгоритм решения оптимизационной задачи (2.22)-(2.27), (2.59) для системы из одного отдельного активного элемента газотранспортной системы. Для решения поставленной задачи необходимо проверить на т совместность N = 2т пт П ( /+ - щ +1) наборов, и из совместных наборов /=1 выбрать тот, на котором достигается минимальное значение критерия (2.59). Здесь п - число интервалов, на которое мы разбиваем значения коммерческого объема газа между минимально возможным и максимально допустимым, т - число различных групп агрегатов. Пусть к],к2,...,кт -произвольный допустимый набор, где kt- количество агрегатов z-ой группы, которые будут использованы в планируемом периоде, / = 1, т. Тогда для этого набора решаем следующую задачу:
Рассмотрим конкретный пример, параметры которого соответствуют одному из цехов КС-21 ЛІТУ МГ «Моркинское», ООО «Волготрансгаз» [85]. В компрессорном цехе функционируют 5 полнонапорных газоперекачивающих агрегатов: с двумя центробежными нагнетателями типа PCL-1002 , и с тремя нагнетателями типа 235-21-1 [4]. Характеристики нагнетателей каждого типа достаточно близки, поэтому число групп газоперекачивающих агрегатов для рассматриваемого компрессорного цеха будет /77=2. Давление на входе компрессорного цеха составляет РуХ= 5.472 МПа. Требуемое выходное давление для цеха составляет р ых= 7.114 МПа. Известно также, что компрессорный цех должен «перекачивать» газ в количестве, равном jeblx= 90 млн. м /сут. Для рассматриваемого примера примем число интервалов для диапазона расходов п=5. Ограничения по возможному количеству использованных агрегатов для каждой группы следующие: т =0, ГГІ2=0, т\=2, т\=Ъ.
Типовые сценарии решения задач распределения ресурсов в иерархических системах с активными элементами
Общая задача оптимизации функционирования производственных систем заключается в нахождении эффективного расписания изготовления всех изделий, удовлетворяющего всем требованиям, предъявляемым к функционированию производства. Критерием оценки расписания является максимизация или минимизация некоторых показателей работ и ресурсов [25].
При решении задач определения оптимального расписания для случая производства больших интегральных схем (БИС) в соответствии с постановкой (2.29)-(2.38), (2.60) будем рассматривать в качестве оптимального расписание, удовлетворяющее критерию минимизации суммарных затрат активных элементов производственной системы. При этом минимизация общих потерь при невыполнении работ в установленные сроки не рассматривается в качестве критерия, таким образом, имеем однокритериальный вариант задачи (2.29)-(2.38), (2.60). Кроме того, в качестве затрат активных элементов рассматриваются не материальные затраты, а затраты временного ресурса на выполнение производственных операций.
Ставится задача: для участка микроэлектронного производства БИС определить режимы функционирования и сменно-суточные задания для каждого вида производственного оборудования, применение которых приведет к минимизации времени изготовления изделий БИС (построить оптимальное расписание), для годового интервала планирования производства с 10 сентября 2009 года по 11 сентября 2010 года.
Исходные данные для задачи следующие. Процесс производства изделия состоит из семи партий. Общее число операций составляет 1513, число типов оборудования равно 30. Исходное сырье представляет из себя наборы партий пластин, из которых изготавливаются интегральные схемы. Технологический процесс изготовления БИС можно условно разбить на две стадии - от запуска пластин в производство до операции резки и от операции резки до
Каждая партия пластин определяет количество кристаллов, которые будут участвовать в процессе производства интегральных схем. Технология изготовления кристаллов, определяемых одной партией пластин, на первой стадии - одинакова. Для каждой технологической операции однозначно определено оборудование, на котором эта технологическая операция должна выполняться, а также время ее выполнения на оборудовании. Технологические операции «гидромеханическая обработка - химическая обработка - окисление» должны выполняться последовательно и без перерывов.
Для нижеследующих технологических операций задано время пролеживания : 121 — операционный контроль (время пролеживания для операции составляет 120 минут); — опрессовка (время пролеживания составляет 30 минут).
Для нижеследующих технологических операций задано межоперационное время: — термообработка (межоперационное время составляет 2 мин.); — нанесение защитного покрытия (межоперационное время составляет 4 ч.). Результаты решения описанной задачи по построению эффективного расписания всего комплекса операций производства БИС с оптимальными сроками изготовления приводятся ниже.
В работе проведена классификация задач математического программирования, и в их классе определено место задач распределения ресурсов в сложных иерархических системах. Рассмотрены подходы к представлению технических и производственных объектов в виде сложных иерархических систем. Рассмотрены концепции активных и пассивных элементов сложных систем с иерархическими связями, формализуемых графовыми моделями. Конкретизированы понятия активных и пассивных элементов систем. Содержательно сформулирована общая проблема распределения ресурсов в иерархических системах, которая конкретизирована на примерах актуальных задач, связанных с транспортом газа, производством продукции и работой систем теплоснабжения.
Построена общая математическая модель распределения ресурсов в иерархических системах с соответствующими ограничениями. Математическая модель конкретизируется в рамках частных подмоделей, связанных с различными практическими приложениями. Проведено исследование построенных математических моделей, в рамках них поставлены задачи математического программирования.
Построена общая математическая модель распределения ресурсов, в иерархических системах с активными элементами, введены основные ограничения для модели. Математическая модель конкретизируется на частные подмодели, связанные с транспортом газа в разветвленных трубопроводных системах, с планированием выпуска продукции на производствах, оснащенных многорежимным оборудованием, а также с поиском оптимальных по мощности режимов фрагментов сетей теплоснабжения. Проведено исследование построенных математических моделей. В рамках построенных математических моделей поставлены оптимизационные задачи.
Приводятся алгоритмы решения поставленных оптимизационных задач распределения ресурсов в сложных иерархических системах с активными элементами, среди которых комбинация фронтальных алгоритмов и дихотомического деления допустимых ресурсных интервалов, а также процедуры сетевого планирования.
Описаны структура интерфейса и типовые сценарии для интерактивного программного обеспечения решения задач распределения ресурсов в иерархических системах с активными элементами. Приведены примеры решения прикладных задач с использованием разработанных программных средств, среди которых задачи расчетного оптимального согласования входов и выходов участка газотранспортной системы, и задача поиска оптимальных режимов промышленного производства микроэлектронной продукции.
