Градиентный метод первого порядка

Содержание
Введение
Градиентные методы оптимизации
Градиентный методпервого порядка
Алгоритм градиентного метода
Математическоеописание системы и значения переменных
Построение математической модели
Алгоритм реализациирешения задачи построения динамической модели
Апробирование машинной программы
Результаты работыпрограммы
Вывод
Список литературы
Листинг программы
/>/>/>/>Введение
Насовременном этапе научно-технического прогресса необыкновенно возрастает рольсредств, позволяющих рационально использовать ресурсы, выделенные для решениянароднохозяйственных задач. Кибернетика предлагает такие средства, какисследование операций, теория систем, математическое моделирование, теорияэксперимента, вычислительная техника и др.
Частьэтих методов предназначена для увеличения эффективности научного эксперимента навсех стадиях разработки, исследования, проектирования и эксплуатациипроизводств. Единство теории и практики эксперимента совместно с вычислительнойтехникой образуют комплекс автоматизированного эксперимента, предназначенныйдля повышения производительности научного труда.
Объекты,на которых проводятся эксперименты, отличаются прежде всего протекающими в нихпроцессами. Объект, на котором осуществляется планируемый эксперимент,характеризуется обязательным условием — все входные переменные, или факторы, x1, x2, ..., xn должны быть управляемыми. Этоготребует сама постановка условий построения динамической модели, предполагающихактивное вмешательство в ход эксперимента. Такой объект технологии называютобъектом исследования.
Необходимыми и достаточными условием для определения любойотрасли знаний как науки является наличие: предмета исследования, методаисследования и средства для реализации этого метода. Для кибернетики как наукипредметом исследования являются системы любой природы и их управляемость,методом исследования — математическое моделирование, стратегией исследования — системный анализ, а средством исследования — вычислительные машины.
Кибернетикавключает в себя такие понятия, как системы, информация, хранение и переработкаинформации, управление системами и оптимизация систем. При этом кибернетикашироко пользуется методом математического моделирования и стремится к получениюконкретных результатов, позволяющих анализировать и синтезировать изучаемыесистемы, прогнозировать их оптимальное поведение и выявлять каналы и алгоритмыуправления.
Методыкибернетики не только позволяют создавать оптимально функционирующий процессили систему, но указывают пути выбора и использования оптимального режима, атакже оптимального управления процессом или системой.
Понятие«системы» дает возможность осуществить математическую формализацию изучаемыхобъектов, обеспечивающую глубокое проникновение в их сущность и получениешироких обобщений и количественных закономерностей.
Всякаясистема состоит из взаимосвязанных и взаимодействующих между собой и с внешнейсредой частей и в определенном смысле представляет собой замкнутое целое (иначеее нельзя было бы назвать системой).
Система- это достаточно сложный объект, который можно расчленить (провестидекомпозицию) на составляющие элементы, или подсистемы. Эти элементыинформационно связаны друг с другом и с окружающей средой объекта. Совокупностьсвязей образует структуру системы. Система имеет алгоритм функционирования,направленный на достижение определенной цели.
Системныйанализ — это стратегия изучения сложных систем. В качестве метода исследованияв нем используется математическое моделирование, а основным принципом являетсядекомпозиция сложной системы на более простые подсистемы. В этом случаематематическая модель системы строиться по блочному принципу: общая модельподразделяется на блоки, которым можно дать сравнительно простые математическиеописания. Необходимо иметь в виду, что все подсистемы взаимодействуют междусобой, составляя общую единую математическую модель.
Воснове стратегии системного анализа лежат следующие общие положения:
1.Четкая формулировка цели исследования;
2.Постановка задачи по реализации этой цели и определение критерия эффективностирешения задачи;
3.Разработка развернутого плана исследования с указанием основных этапов инаправлений решения задач;
4.Пропорционально — продвижение по всему комплексу взаимосвязанных этапов ивозможных направлений;
5.Организация последовательных приближений и повторных циклов исследований на отдельныхэтапах;
6.Принцип нисходящей иерархии анализа и восходящей иерархии синтеза в решениисоставных частных задач и т.п.
Системныйанализ организует наши знания об объекте таким образом, чтобы помочь выбратьнужную стратегию либо предсказать результаты одной или нескольких стратегий,представляющихся целесообразными темами, кто должен принимать решения. Спозиции системного анализа решаются задачи моделирования, оптимизации,управления и оптимального проектирования систем.
Особыйвклад системного анализа в решение различных проблем заключается в том, что онпозволяет выявить факторы и взаимосвязи, которые в последствии могут оказатьсявесьма существенными, дает возможность видоизменить методику наблюдений ипостроить эксперимент так, чтобы эти факторы были включены в рассмотрение, иосвещает слабые места гипотез и допущений. Как научный подход системный анализс его акцентом на последовательное рассмотрение явлений в соответствии сразными уровнями иерархии и на проверку гипотез с помощью строгих выборочныхпроцедур создает мощные инструменты познания физического мира и объединяет этиинструменты в систему гибкого, но строгого исследования сложных явлений.
Математическоемоделирование осуществляется в три взаимосвязанные стадии:
1.Формализация изучаемого процесса — построение математической модели (составлениематематического описания);
2.Программирование решения задачи (алгоритмизация), обеспечивающего нахождениечисленных значений определяемых параметров;
3.Установление соответствия (адекватности) модели изучаемому процессу.
Построениематематической модели:
Вкаждом конкретном случае математическую модель создают, исходя из целевойнаправленности процесса и задач исследования, с учетом требуемой точностирешения и достоверности используемых исходных данных. При анализе полученныхрезультатов возможно повторное обращение к модели с целью внесения коррективовпосле выполнения части расчетов.
Построениелюбой математической модели начинают с формализованного описания объектамоделирования. При этом аналитический аспект моделирования состоит в выражениисмыслового описания объекта на языке математики в виде некоторой системыуравнений и функциональных соотношений между отдельными параметрами модели.Основным приемом построения математического описания изучаемого объектаявляется блочный принцип. Согласно этому принципу, после того как определеннабор элементарных процессов, каждый из них исследуется по блокам в условиях,максимально приближенных к условиям эксплуатации объекта моделирования.
Врезультате каждому элементарному технологическому оператору ставиться всоответствие функциональный элементарный оператор с параметрами, достаточноблизкими к истинным значениям.
Следующийэтап моделирования состоит в агрегировании функциональных элементарныхоператоров в общий функциональный результирующий оператор, который ипредставляет математическую модель объекта. Важным фактором агрегированияявляется правильная взаимная координация отдельных операторов, которая невсегда возможна вследствие трудностей учета естественных причинно-следственныхсвязей между отдельными элементарными процессами.
Привыборе модели необходимо учитывать следующее:
— модель должна наиболее точно отражать характер потоков вещества и энергии придостаточно простом математическом описании;
— параметрымодели могут быть определены экспериментальным или другим путем;
— вслучае гетерогенных систем модели выбираются для каждой фазы в отдельности,причем для обеих фаз они могут быть одинаковыми или различными.
Припостроении математического описания используют уравнения таких видов:
— алгебраические уравнения;
— обыкновенные дифференциальные уравнения;
— дифференциальные уравнения в частных производных.
Алгоритмизацияматематических моделей:
Послесоставления математического описания и выбора соответствующих начальных играничных условий необходимо провести второй этап моделирования — довестизадачу до логического конца, т. е. выбрать метод решения и составить программу(алгоритм).
Впростейших случаях, когда возможно аналитическое решение системы уравненийматематического описания, необходимость в специальной разработке моделирующегоалгоритма, естественно, отпадает, так как вся информация может быть получена изсоответствующих аналитических решений. Когда математическое описаниепредставляет собой сложную систему конечных и дифференциальных уравнений, отвозможности построения достаточно эффективного моделирующего алгоритма можетсущественно зависеть практическая применимость математической модели. Вособенности это важно при использовании модели для решения задач, в которых онавходит в качестве составной части более общего алгоритма, например, алгоритмаоптимизации. Как правило, в таких случаях для реализации математической моделиприходиться применять средства вычислительной техники; фактически без нихнельзя ставить и решать сколько-нибудь сложные задачи математическогомоделирования и тем более задачи оптимизации, при решении которых расчеты поуравнениям математического описания обычно многократно повторяются.
Широкоразвитые в настоящее время методы численного анализа позволяют решать широкийкруг задач математического моделирования.
Выборчисленного метода:
Привыборе метода для решения уравнений математического описания обычно ставитьсязадача обеспечения максимального быстродействия при минимуме занимаемойпрограммой памяти. Естественно, при этом должна обеспечиваться заданнаяточность решения. Прежде чем выбрать тот или иной численный метод, необходимопроанализировать ограничения, связанные с его использованием, например,подвергнуть функцию или систему уравнений аналитическому исследованию, врезультате которого выявиться возможность использования данного метода. Приэтом весьма часто исходная функция или система уравнений должна быть соответствующимобразом преобразована с тем, чтобы можно было эффективно применить численныйметод. Преобразованием или введением новых функциональных зависимостей частоудается значительно упростить задачу.
Привыборе метода существенным моментом является размерность задачи. Некоторыеметоды эффективны при решении небольших задач, однако, с увеличением числапеременных объем вычислений настолько возрастает, что от них приходитьсяотказаться. Задачи такого класса обычно встречаются при решении системуравнений, поиске оптимальных значений параметров многомерных функций. Присоответствующем выборе метода можно уменьшить время, затрачиваемое на решениезадачи и объем занимаемой машиной памяти.
Составлениеалгоритма решения:
Желательносоставить четкое описание последовательности вычислительных и логическихдействий, обеспечивающих решение, т.е. составить алгоритм решения задачи.Основными требованиями к форме и содержанию записи алгоритма являются егонаглядность, компактность и выразительность. В практике математическогообеспечения вычислительных машин широкое распространение получил графическийспособ описания алгоритмов. Этот способ основан на представлении отдельныхэлементов алгоритма графическими символами, а всего алгоритма — в виде блоксхемы. При этом набор графических символов не является произвольным, он регламентировантехнической документацией по математическому обеспечению ЭВМ и соответствующимиГОСТами.
Методыоптимизации:
Оптимизациязаключается в нахождении оптимума рассматриваемой функции или оптимальныхусловий проведения данного процесса. Для оценки оптимума необходимо преждевсего выбрать критерий оптимизации. В зависимости от конкретных условий вкачестве критерия оптимизации можно взять технологический критерий, напримермаксимальный съем продукции с единицы объема аппарата, экономический критерий — минимальную стоимость продукта при заданной производительности.
Наоснове выбранного критерия оптимизации составляется так называемая целеваяфункция, или функция выгоды, представляющая собой зависимость критерияоптимизации от параметров, влияющих на его значение. Задача оптимизациисводиться к нахождению экстремума (максимума или минимума) целевой функции.
Следуетиметь в виду, что проблема оптимизации возникает в тех случаях, когданеобходимо решать компромиссную задачу преимущественного улучшения двух илиболее количественных характеристик, различным образом влияющих на переменныепроцесса при условии их взаимной балансировки. Например, эффективность процессабалансируют с производительностью, качество — с количеством, запас единицпродукции — с их реализацией, производительность — с затратами.
Дляавтоматически управляемых процессов или систем различают две стадииоптимизации: статическую и динамическую.
Проблемасоздания и реализации оптимального стационарного режима процесса решаетстатическая оптимизация, создания и реализации системы оптимального управленияпроцессом — динамическая оптимизация.
Взависимости от характера рассматриваемых математических моделей применяютсяразличные математические методы оптимизации. Многие из них сводятся к нахождениюминимума или максимума целевой функции. Линии, вдоль которых целевая функция сохраняетпостоянное значение при изменении входящих в нее параметров, называютсяконтурными или линиями уровня.
Привыборе метода оптимизации необходимо учитывать возможные вычислительныетрудности, обусловленные объемом вычислений, сложностью самого метода,размерностью самой задачи и т.п.
Целесообразнопо возможности проводить предварительную оценку положения оптимума какой-либоконкретной задачи. Для этого необходимо рассмотреть исходные и основныесоотношения между переменными. Для сокращения размерности задач частоиспользуется прием выделения наиболее существенных переменных
Согласнопринятой терминологии факторы x1, x2, ..., xn — это измеряемые и регулируемые входные переменные объекта (независимыепеременные); помехи f1, f2, ..., fs — это не контролируемые, случайным образом изменяющиеся переменныеобъекта; выходные переменные y1, y2, ..., ym — это контролируемые переменные, которые определяются факторами исвязаны с целью исследования. Часто в планируемом эксперименте у называютпараметром оптимизации (технологический или экономический показатель процесса).
Факторыx1, x2, ..., xn иногда называют основными, посколькуони определяют условия эксперимента. Помехи f1, f2, ..., fs — как правило недоступны дляизмерения. Они проявляются лишь в том, что изменяют влияние факторов навыходные переменные. Объект исследования может иметь несколько выходныхпеременных. Опыт показывает, что в большинстве случаев удается ограничитьсяодним параметром оптимизации, и тогда вектор Y превращается в скаляр y.
Количествофакторов и характер их взаимосвязей с выходной переменной определяют сложностьобъекта исследования. При наличии качественной статистической информации офакторах и зависящей от них выходной переменной можно построить математическуюмодель объекта исследования и функцию отклика y= f(x1, x2, ..., xn), связывающую параметр оптимизации с факторами, которыеварьируются при проведении опытов.
Пространствос координатами x1, x2, ..., xn принято называть факторным, аграфическое изображение функции отклика в факторном пространстве — поверхностьюотклика.
Приописании объектов, находящихся в стационарном состоянии, математическая модельчаще всего представляется полиномом:
 
Y= f(x1, x2, ..., xn, Я1, Я2,…,Яn). (1)
Посколькув реальном процессе всегда существуют неуправляемые и неконтролируемыепеременные, величина у носит случайный характер. Поэтому при обработкеэкспериментальных данных получаются так называемые выборочные коэффициентырегрессии b, b1, ..., bi, ..., bn, являющиеся оценками коэффициентов Я0, Я1,..., Яi,..., Яn.
Тогдаматематическая модель в форме уравнения регрессии в общем случае будет иметьвид:
/>(2)
Еслианализируются нестационарные, т. е. изменяющиеся во времени состояния объекта,что характерно для динамического процесса, приходится рассматривать неслучайные величины, как ранее, а случайные процессы. Случайный процесс можно рассматриватькак систему, состоящую из бесконечного множества случайных величин. Примоделировании таких объектов использовать модель в виде (2) уженедопустимо — необходимо переходить к специальным интегрально-дифференциальныммоделям и методам. В нашем случае – это градиентный метод первого порядка.
Составлениюплана эксперимента всегда должны предшествовать сбор априорной информации длясоставления характеристики объекта исследования, опыты по наладкеэкспериментальной установки и при необходимости — опыты для установленияобласти определения наиболее существенных факторов и выходной переменной.
Теориейи практикой эксперимента выработаны определенные требования (условия), которымдолжны удовлетворять независимые и зависимые переменные. Поэтому на стадии подготовкик проведению эксперимента весьма полезны приведенные ниже рекомендации.
1.При выборе выходной переменной необходимо учитывать, что она должна иметьколичественную характеристику, т. е. должна измеряться; должна однозначнооценивать (измерять) работоспособность объекта исследования; быть статистическиэффективной, т. е. иметь возможно меньшую дисперсию при проведении опытов (этопозволяет четко различать опыты); отражать как можно более широкий спектрисследуемого явления, т. е. обладать универсальностью (практически этотребование обеспечить трудно, тогда рекомендуют пользоваться так называемойобобщенной переменной); иметь достаточно четкий физический смысл.
2.При выборе факторов нужно выполнять следующие требования: фактор должен бытьрегулируемым, т. е. определенным регулирующим устройством фактор долженизменяться от значения x’iдозначения x’’i; точность изменения и управленияфактором должна быть известна и достаточно высока (хотя бы на порядок вышеточности измерения выходной переменной), очевидно, что низкая точностьизмерения фактора уменьшает возможности воспроизведения эксперимента; связьмежду факторами должна быть как можно меньшей (в пределе должна отсутствовать),это свойство называют однозначностью факторов, что соответствует независимостиодного фактора от другого.
Рядтребований предъявляется одновременно к факторам и выходной переменной: факторыи выходная переменная должны иметь области определения, заданнымитехнологическими или принципиальными ограничениями; области определенияфакторов должны быть таковы, чтобы при их предельных значениях значениевыходной переменной оставалось в своих границах; между факторами и выходнойпеременной должно существовать однозначное соответствие (причинно-следственнаясвязь).
Успехсовременного экспериментирования в значительной степени обязан теорииэксперимента, которая призвана дать экспериментатору ответы на следующие вопросы:
1.  Как нужно организовать эксперимент,чтобы наилучшим образом решить поставленную задачу (в смысле затрат времени, средствили точности результатов).
2.  Как следует обрабатывать результатыэксперимента, чтобы получить максимальное количество информации об исследуемомобъекте.
3.  Какие обоснованные выводы можносделать об исследуемом объекте по результатам эксперимента.
Основойтеории эксперимента является статистическое представление об эксперименте(рассматриваются случайные величины или случайные функции). Это представлениеотвечает действительности: как правило, итоги эксперимента связаны с некоторойнеопределенностью, получающейся в результате влияния неконтролируемых факторов,случайного характера процесса на микроуровне, изменений условий эксперимента,ошибок измерения и др.
Теорияэксперимента указывает исследователю точную логическую схему и способы поискарешения задач на разных этапах исследования. Можно представить весь процессисследования циклами, повторяющимися после решения каждой из последовательныхзадач исследования, причем объем знаний об объекте непрерывно увеличивается.
Цельнастоящей работы состоит в построении динамической модели заданногоэксперимента, широко используемой при решении задач лабораторных и промышленныхисследований. В работе рассмотрены основные методы и алгоритмы, относящиеся кидентификации динамических систем градиентным методом первого порядка.
/>/>Моделирование и программирование динамических систем
Методдинамического программирования применяется для многостадийных процессов,характеризуемых последовательностью решений и тем, что состояние системызависит только от предыдущего шага, т. е. не зависит от ранее сделанных шагов.
Втаких случаях используется принцип оптимальности, который формулируется вследующем виде: оптимальная стратегия обладает таким свойством, что, каково быни было начальное состояние и начальное решение, последующие решения должныприниматься, исходя из оптимальной стратегии относительно состояния,получаемого в результате первого решения.
Основнаяидея динамического программирования и заключается в том, что если какой-либопоток изменяется на каждой стадии процесса, то, если на последней стадии режимработы (независимо от режима работы на всех стадиях) не будет оптимальным поотношению к поступающему на нее потоку, не будет оптимальным и режим всегомногостадийного процесса в целом.
Применениеметода динамического программирования состоит в определении такого режимаработы стадии, который максимизирует доход на этой и всех последующих стадияхдля любых возможных состояний поступающего на нее потока. Обычно рассмотрениеначинается с последней стадии процесса. Оптимальный режим всего процессаопределяется постадийно.
Такимобразом, метод динамического программирования предполагает разбиениеанализируемого процесса во времени или пространстве на стадии или ступени. Вкачестве стадии можно принять единицу времени (минута или час), единичныйэлемент оборудования (тарелка в ректификационной колонне или реактор в цепочкереакторов).
Влюбом случае стадия или ступень – это математическая абстракция, применяемаядля представления непрерывной переменной в дискретном виде. Состояние системыхарактеризуется совокупностью переменных, описывающих систему на любой стадиипроцесса.
Каждаястадия характеризуется входными xi-1 и выходными xiпараметрами, а также параметрами управления ui. При помощи управляющих воздействийоптимизируется результирующая оценка эффективности многостадийного процесса,определяемая как аддитивная функция результатов, получаемых на каждой стадии ui(x1i-1, ui):
/> (1)
Значениекритерия оптимальности RN зависит от совокупности uN управляющих воздействий на всех стадиях. Совокупность управленийназывается стратегией управления многостадийным процессом.
Основнымуравнением динамического программирования является функциональное уравнениевида:
/>, (2)
где /> -оптимизируемая функция N-стадийногопроцесса, максимальное значение критерия RN.
Максимизацияпервого слагаемого r1(x0,u1), представляющего собой частныйкритерий, характеризующий первую стадию, проводится только по управлению u1.
Член />естьзначение оптимизируемой функции на последующих N-1 стадиях и максимизируется выбором управлений на всехстадиях, ui (I = 1,…,N),поскольку значение x1 зависит от управления u1.
Выражение(2) представляет собой рекуррентное соотношение, характеризующеепоследовательность функций />последняя из которых />отвечаетискомому решению оптимальной задачи. Стратегия решения выражается системойвыбранных значений ui –членов уравнения (2), где i = 1,2, ..., N; система дает решениефункционального уравнения. Оптимальная стратегия выражается системой функций ui, которые максимизируют правую частьуравнения (2), а именно: /> для i = 1, 2, ..., N.
Частоважно знать сам характер оптимальной стратегии, нежели значение оптимизируемойфункции. В ходе определения функции fN(x) получаютодновременно последовательность решений ui или стратегию также в виде функцииномера стадии i.
Решениерекуррентных уравнений обычно выполняется численными методами. Частоиспользуется следующая последовательность расчета с применением вычислительноймашины: сначала находят f1(x), затем по найденному значению функции f1(x) поуравнению ( 1 ) определяют функцию f2(x); далее последовательно определяют f3(x) из f2(x) ит.д.
Прирешении задач оптимизации и моделировании динамической системы методомдинамического программирования необходимо обратить внимание на следующиеосновные положения:
А)оптимизируемый процесс должен быть дискретно-распределенным во времени илипространстве (многостадийный процесс);
Б)отдельные стадии процесса должны обладать относительной независимостью, т.е.вектор выходных параметров любой стадии должен зависеть только от векторавходных параметров на эту стадию и управления на ней;
В)критерий оптимальности всего процесса должен быть сформулирован как аддитивнаяфункция критериев оптимальности каждой стадии.
Есливыполняются эти условия, необходимо правильно сформулировать задачуоптимизации. При формулировке задачи оптимизации и моделирования должны бытьвыявлены: 1) параметры, характеризующие состояние каждой стадии; 2) управляющиепараметры на каждой стадии; 3) ограничения, которые накладываются на параметрысостояния процесса и управляющие параметры. Кроме того, должно быть составленоматематическое описание для каждой стадии и определен критерий оптимальности.
 />/>/>Градиентные методыоптимизации
Градиентныеметоды оптимизации относятся к численным методам поискового типа. Ониуниверсальны, хорошо приспособлены для работы с современными цифровымивычислительными машинами и в большинстве случаев весьма эффективны при поискеэкстремального значения нелинейных функций с ограничениями и без них, а такжетогда, когда аналитический вид функции вообще неизвестен. Вследствие этогоградиентные, или поисковые, методы широко применяются на практике.
Сущностьуказанных методов заключается в определении значений независимых переменных,дающих наибольшие изменения целевой функции. Обычно для этого двигаются вдольградиента, ортогонального к контурной поверхности в данной точке.
Различныепоисковые методы в основном отличаются один от другого способом определениянаправления движения к оптимуму, размером шага и продолжительностью поискавдоль найденного направления, критериями окончания поиска, простотойалгоритмизации и применимостью для различных ЭВМ. Техника поиска экстремумаоснована на расчетах, которые позволяют определить направление наиболеебыстрого изменения оптимизируемого критерия.
Есликритерий задан уравнением
/>, (3)
тоего градиент в точке (x1, x2,…, xn) определяется вектором:
/>. (4)
Частнаяпроизводная /> пропорциональна косинусу угла,образуемого вектором градиента с i-йосью координат. При этом
/> (5)
Нарядус определением направления градиентного вектора основным вопросом, решаемым прииспользовании градиентных методов, является выбор шага движения по градиенту.Величина шага в направлении gradFв значительной степени зависит от вида поверхности. Если шаг слишком мал,потребуются продолжительные расчеты; если слишком велик, можно проскочитьоптимум. Размер шага />должен удовлетворять условию, прикотором все шаги от базисной точки лежат в том же самом направлении, что иградиент в базисной точке. Размеры шага по каждой переменной xi вычисляются из значений частныхпроизводных в базовой (начальной) точке:
/>, (6)
где К– константа, определяющая размеры шага и одинаковая для всех i-х направлений. Только в базовойточке градиент строго ортогонален к поверхности. Если же шаги слишком велики вкаждом i-м направлении, вектор из базиснойточки не будет ортогонален к поверхности в новой точке.
Есливыбор шага был удовлетворительным, производная в следующей точке существенноблизка к производной в базисной точке.
Длялинейных функций градиентное направление не зависит от положения наповерхности, для которой оно вычисляется. Если поверхность имеет вид
/>
то
/> /> />
икомпонента градиента в i-мнаправлении равна
/>. (7)
Длянелинейной функции направление градиентного вектора зависит от точки наповерхности, в которой он вычисляется.
Несмотряна существующие различия между градиентными методами, последовательностьопераций при поиске оптимума в большинстве случаев одинакова и сводится к следующему:
а)выбирается базисная точка;
б)определяется направление движения от базисной точки;
в)находится размер шага;
г)определяется следующая точка поиска;
д)значение целевой функции в данной точке сравнивается с ее значением впредыдущей точке;
е) вновьопределяется направление движения и процедура повторяется до достиженияоптимального значения.
 />/>/>Градиентный методпервого порядка
Приоптимизации методом градиента оптимум исследуемого объекта ищут в направлениинаиболее быстрого возрастания (убывания) выходной переменной, т.е. внаправлении градиента. Но прежде чем сделать шаг в направлении градиента,необходимо его рассчитать. Градиент можно рассчитать либо по имеющейся модели
grady(X)= /> ,
моделирование динамический градиентный полиномиальный
где /> -частная производная по i-му фактору;
i, j,k – единичные векторы в направлении координатных осей факторного пространства,либо по результатам n пробных движений в направлении координатных осей.
Еслиматематическая модель статистического процесса имеет вид линейного полинома,коэффициенты регрессии bi которого являются частными производнымиразложения функции y = f(X) в ряд Тейлора по степеням xi, то оптимумищут в направлении градиента с некоторым шагом hi:
пкфв н(Ч)=и1р1+и2р2+…+итрт
Направлениекорректируют после каждого шага.
Методградиента вместе с его многочисленными модификациями является распространенными эффективным методом поиска оптимума исследуемых объектов. Рассмотрим одну измодификаций метода градиента – метод крутого восхождения.
Методкрутого восхождения, или иначе метод Бокса-Уилсона, объединяет в себедостоинства трех методов — метода Гаусса-Зейделя, метода градиентов и методаполного (или дробного) факторного экспериментов, как средства получениялинейной математической модели. Задача метода крутого восхождения заключается втом, чтобы шаговое движение осуществлять в направлении наискорейшеговозрастания (или убывания) выходной переменной, то есть по grad y(X). В отличии от метода градиентов,направление корректируется не после каждого следующего шага, а при достижении внекоторой точке на данном направлении частного экстремума целевой функции, какэто делается в методе Гаусса-Зейделя. В точке частного экстремума ставитсяновый факторный эксперимент, определяется математическая модель и вновьосуществляется крутое восхождение. В процессе движения к оптимуму указаннымметодом регулярно проводиться статистический анализ промежуточных результатовпоиска. Поиск прекращается, когда квадратичные эффекты в уравнении регрессиистановятся значимыми. Это означает, что достигнута область оптимума.
Опишемпринцип использования градиентных методов на примере функции двух переменных
/> (8)
приналичии двух дополнительных условий:
/>, />.(9)
Этотпринцип (без изменения) можно применить при любом числе переменных, а такжедополнительных условий. Рассмотрим плоскость x1, x2 (Рис. 1). Согласно формуле (8)каждой точке соответствует некоторое значение F. На Рис.1 линии F = const, принадлежащие этой плоскости,представлены замкнутыми кривыми, окружающими точку M*, в которой Fминимально. Пусть в начальный момент значения x1 и x2 соответствуют точке M0. Цикл расчета начинается с серии пробных шагов.Сначала величине x1 дается небольшое приращение />; вэто время значение x2 неизменно. Затем определяетсяполученное при этом приращение /> величины F, которое можно считать пропорциональным значению частнойпроизводной
/> (10)
(есливеличина />всегда одна и та же).
/>
Рис.1
Далеедается приращение /> величине x2. В это время x1 = const. Получаемое при этом приращение /> величины F является мерой другой частнойпроизводной:
/>. (11)
Определениечастных производных ( 10 ) и ( 11 ) означает, что найден вектор с координатами /> и />,который называется градиентом величины F и обозначается так:
/>.(12)
Известно,что направление этого вектора совпадает с направлением наиболее крутоговозрастания величины F.Противоположное ему направление – это «наискорейший спуск», другими словами,наиболее крутое убывание величины F.
Посленахождения составляющих градиента пробные движения прекращаются иосуществляются рабочие шаги в направлении, противоположном направлениюградиента, причем величина шага тем больше, чем больше абсолютная величинавектора grad F. Эти условия осуществляются, если величины рабочих шагов /> и /> пропорциональныполученным ранее значениям частных производных:
/>, />, (13)
гдеα – положительная константа.
Послекаждого рабочего шага оценивается приращение /> величины F. Если оно оказывается отрицательным, то движение происходитв правильном направлении и нужно двигаться в том же направлении M0M1 дальше. Если же в точке M1 результат измерения показывает, что />, то рабочие движенияпрекращаются и начинается новая серия пробных движений. При этом определяетсяградиент gradF в новой точке M1, затем рабочее движение продолжается по новомунайденному направлению наискорейшего спуска, т. е. по линии M1M2, и т.д. Этот метод называется методом наискорейшегоспуска/крутого восхождения.
Когдасистема находится вблизи минимума, показателем чего является малое значениевеличины
/> (14)
происходитпереключение на более «осторожный» метод поиска, так называемый методградиента. От метода наискорейшего спуска он отличается тем, что послеопределения градиента gradFделается лишь один рабочий шаг, а затем в новой точке опять начинается серияпробных движений. Такой метод поиска обеспечивает более точное установлениеминимума по сравнению с методом наискорейшего спуска, между тем как последнийпозволяет быстрее приблизиться к минимуму. Если в процессе поиска точка Мдоходит до границы допустимой области и хотя бы одна из величин М1,М2 меняет знак, метод меняется и точка М начинает двигаться вдольграницы области.
Эффективностьметода крутого восхождения зависит от выбора масштаба переменных и видаповерхности отклика. Поверхность со сферическими контурами обеспечивает быстроестягивание к оптимуму.
Кнедостаткам метода крутого восхождения следует отнести:
1.Ограниченность экстраполяции. Двигаясь вдоль градиента, мы основываемся наэкстраполяции частных производных целевой функции по соответствующимпеременным. Однако форма поверхности отклика может изменяться и необходимоизменять направление поиска. Другими словами, движение на плоскости не можетбыть продолжительным.
2.Трудность поиска глобального оптимума. Метод применим для отыскания тольколокальных оптимумов./>/>/>Алгоритмградиентного метода
Представимпоследовательность расчета: расчет составляющих градиента.
Практическирасчет составляющих градиента реализуется вычислением произведений коэффициентоврегрессии на соответствующие интервалы варьирования значимых факторов.
Тогдауравнение
пкфв н(Ч)= и1р1 + и2р2 + … + итрт
приметвид
grad />(X)= b1/> + b2/> + … + bn/>
т.е.в качестве шагов крутого восхождения выбираются интервалы варьированияфакторов.
Выборбазового фактора:
Фактор,для которого произведение коэффициента регрессии на интервал варьированиямаксимально, принимается базовым:
max (bi/>) = a
Выборшага крутого восхождения:
Длябазового (или другого) фактора выбирают шаг крутого восхождения ha. Обычно его выбирают по советутехнологов или по имеющейся априорной информации.
Пересчетсоставляющих градиента:
Здесьиспользуется условие: умножение составляющих градиента на любое положительноечисло дает точки, также лежащие на градиенте.
Составляющиеградиента пересчитывают по выбранному шагу крутого восхождения базовогофактора:
hi= /> (*)
Коэффициентыbi в выражении (*) берутся со своимизнаками, шаги hiокругляют.
Принятиерешений после крутого восхождения:
Послетого, как экспериментальная проверка определила некоторую оптимальную точку,крутое восхождение считается завершенным. Здесь, как и ранее, необходимопринимать решения, которые зависят, прежде всего, от эффективности крутоговосхождения. Большое влияние на результаты принятия решений оказываетинформация об адекватности или неадекватности линейной модели и о положенииобласти оптимума. Конечно, сведения о положении области оптимума носят весьманеопределенный характер и зависят от конкретной задачи, где переменнаясостояния – например, прочность материала на разрыв. Однако можно безошибочнооценить положение оптимума, если переменная состояния — выход целевого продуктав процентах.
 />/>/>Математическоеописание системы и значения переменных
Внашем случае имеем:
Припостроении математической модели определённого в условии технологическогопроцесса одновременно решается задача оптимизации поверхности отклика />, тоесть определяются значения факторов, при которых />, что означает, что />.Известно, что одним из наиболее эффективных методов решеня задачи являетсяградиентный метод. Согласно ему в данном случае (исходя из условий задачи) изкаждой точки направление движения осуществляется в сторону, противоположнуюсамому градиенту. Отсюда в каждой точке необходимо провести расчет градиентаследующего вида:
/>, гдеi и k – единичные орты
Какправило, определить всю математическую модель процесса достаточно сложно,поэтому здесь нужно воспользоваться следующей процедурой:
1.  В окрестности начальной точки
/> 
производитсяполный факторный эксперимент или дробный факторный эксперимент. Мы будемиспользовать полный факторный эксперимент.
Следуетохарактеризовать общие положения проведения полного факторного эксперимента:
Применениеполного факторного эксперимента позволяет найти оптимальное расположение точекв факторном пространстве и осуществить линейное преобразование координат, благодарячему обеспечивается возможность преодолеть недостатки классическогорегрессионного анализа, в частности корреляцию между коэффициентами уравнениярегрессии.
Некоторые обозначения длядальнейшего понимания изложения материала:
Xj-факторы;
Рj- регрессионные коэффициенты системы;
Y- выходная переменная (функцияотклика);
М [f]- математическое ожидание помехи;
D [f] – дисперсия помехи;
l – число уровней ;
k – количество факторов;
Уровень факторов – границаисследования области по данному параметру;
Точка с координатами (Х0(1),Х0(2),…) — центр плана, или основной уровень;
/> — единица варьирования, или интервалварьирования;
S – дисперсия;
вектор В — вектор коэффициентов регрессии;
N — число опытов в матрице планирования;
Р — коэффициент взаимодействия;
bj-несмешанные оценки;
/> - генеральные коэффициенты;
S2воспр — дисперсия воспроизводимости;
tj — критерийСтьюдента;
F – критерий Фишера.
Выборплана исследования эксперимента определяется постановкой задачи исследования иособенностями объекта. Пусть имеем математическую модель системы:
/>
Такженам известны характер помехи и статистические параметры: М[f] = 0 и D[f] = 0,8.Необходимо отметить, что под помехами понимают ряд факторов, искажающихрезультаты опыта. Если существуют определённые априорные сведения об источникепомех, то можно построить оптимальные планы исследования, учитывающие ихвлияние, и повысить таким образом точность анализа результата.
Вданной задаче требуется провести полный факторный эксперимент.
Полныйфакторный эксперимент, или метод планирования эксперимента позволяет свести кминимуму число необходимых опытов и одновременно получить оптимальные значенияискомых функций. При планировании эксперимента, условия опыта представляютсобой фиксированное число значений для каждого фактора. Полный факторныйэксперимент фактически представляет собой применение классических методанаименьших квадратов и регрессионного анализа, проводимых по определённомуплану.
Процесс исследованияобычно разбивается на отдельные этапы. Информация, полученная после каждогоэтапа, определяет дальнейшую стратегию эксперимента. Таким образом возникаетвозможность оптимального управления экспериментом. Планирование экспериментапозволяет одновременно варьировать все факторы и получать количественные оценкиосновных эффектов и эффектов взаимодействия.
Интересующиеисследователя эффекты определяются со значительно меньшей ошибкой, чем та,которая характерна для других методов исследования.
В конечном счете,применение методов планирования эксперимента значительно повышает эффективностьэксперимента.
Так как при планированиипо схеме полного факторного эксперимента реализуются все возможные комбинациифакторов на всех выбранных для исследования уровнях, то необходимое числоопытов N при полном факторном экспериментеопределяется по формуле: N=lk.
Если экспериментыпроводятся только на двух уровнях при двух значениях факторов и при этом впроцессе эксперимента осуществляются все возможные комбинации из k факторов, то такой план носитназвание полный факторный эксперимент типа 2k.
Описание алгоритма моделирования сводится кследующему:
1. Определяетсядля любого фактора:
Х0 j = (Хjmax+ Хjmin ) / 2,
/> = (Хjmax- Хjmin) / 2, j = 1,2,…..k ;
 
2. Отосновной системы координат (Х1, Х2, …Хn)переходим к безразмерной системе координат (U1, U2, …Un) cпомощью формулы перехода:
Uj= (Хj — Хj0) / />, j =1,2,…..k;
В безразмерной системе координат верхний уровень равен+1, а нижний равен –1, координаты центра плана равны нулю и совпадают с началомкоординат.
3. Планэксперимента:
В матрицу планирования (Табл. 1.1) записываются всевозможные значения граничных величин в натуральном масштабе.
Таблица1.1Номер опыта Значения факторов в натуральном масштабе выход /> />
X1
X2 …
Xn Y /> 1
X11
X 12 …
X 1 n
Y1 /> 2
X 21
X2 2 …
X 2 n
Y2 /> …. … … … … ... /> N
X N1
X N2 …
XNn
YN />
4.  Введём фиктивный столбец U0в матрицу и запишем матрицу в безразмерной форме(Табл.1.2):
Таблица 1.2Номер опыта фиктивный столбец Значения факторов в безразмерной системе координат Выход
U0
U1
U2 …
Un У 1 +1 +1 +1 … +1
У1 2 +1 -1 +1 … +1
У2 ... … … … … …. … N +1 -1 -1 … -1
УN
5. Приведёмполную матрицу планирования (Табл. 1.3.):
Таблица 1.3
Номер
опыта Значения факторов Выход В натуральном масштабе В безразмерной системе координат
X1
X2 …
Xn
U 0
U1
U2 …
Un Y 1
X11
X12 …
X1n +1 +1 +1 … +1
Y1 2
X21
X22 …
X2n +1 -1 +1 … +1
Y2 … … … … … … … … … … … N
XN1
X N2 …
XNn +1 -1 -1 … -1
YN
Предложенный план эксперимента обладает следующимисвойствами:
Свойство симметричности.

/>;
Свойство нормировки.
/>;
Свойство ортогональности.
/>, ( l/>j, l,i =1…k );
Следует отметить, что ортогональные планы полныйфакторный эксперимент ( для линейных моделей ) обладают также рототабельностью.Последнее предполагает равенство и минимальность дисперсий предсказанныхзначений выходной переменной для всех точек факторного пространства. По законунакопления ошибок для дисперсии предсказанных уравнением регрессии значенийвыходной переменной можно записать:
s2y= s2b0 + s2b1U12 + … + s2bnUn2
 
Дисперсии коэффициентов регрессии равны между собою,поэтому
s2y= s2bi/>
 
С учетом того, что
/>,

Где /> - радиус сферы имеем
s2y= s2bi/>.
Отсюда ясно, что дисперсия предсказанного значениявыходной переменной зависит только от радиуса сферы. Это свойстворототабельности эквивалентно независимости дисперсии выходной переменной отвращения координат в центре плана и оправдано при поиске оптимума градиентнымиметодами. Интуитивно понятно, что исследователю удобно иметь дело с такойинформацией, содержащейся в уравнении регрессии, которая равномерно «размазана»по сфере радиусом />. Действительно такое положениеможно признать разумным, ибо с помощью уравнения регрессии будутпредприниматься попытки предсказать положение ещё неизвестных участковфакторного пространства. Равноценность этих участков в смысле ошибкипредсказания, по-видимому, является необходимой.
Свойство ортогональности существенно облегчает процессвычисления коэффициентов, так как корреляционная матрица (UТU)-1становится диагональной, и коэффициенты будут равны 1/N;
6. С учетомсвойства ортогональности можно вычислить вектор В коэффициентов регрессии:/>
/>
Следовательно, любой коэффициент уравнения регрессии bjопределяется скалярным произведением столбца Y насоответствующий столбец Uj, деленным на число опытов N в матрицепланирования:

/>
Вычислим коэффициенты регрессии линейного уравнения :
/>
Если в рассмотрение ввести более полное уравнениерегрессии с коэффициентами взаимодействия Р, то используя процедуру методанаименьших квадратов, получим:
/>.
Пользуясь планом, представленным в табл. 1.2, можноперечислить коэффициенты регрессии и записать в табл.1.4:
Y = Р0+ Р1U1 + Р2U2 + … + РnUn+ … +
+…+P13U1U3 + P23U2U3+ … + P123U1U2U3…
Таблица 1.4Номер опыта
U0
U1
U2 …
Un …
/>
/>
/> … У 1 +1 +1 +1 … +1
… -1 +1 +1
…
У1 2 +1 -1 +1 … +1
… -1 -1 +1
…
У2 … … … … … … … … … … … … N +1 -1 -1 … -1
… -1 +1 +1
…
УN
P12, P23 — эффекты двойного взаимодействия, а P123 — эффекты тройного взаимодействия. Эффектывзаимодействия определяют аналогично линейным эффектам:
/>.
 
7. Проверкаоднородности дисперсии и значимости коэффициентов регрессии.
Если дополнительно поставить параллельные опыты, можноопределить s2воспр — дисперсию воспроизводимости,проверить значимость коэффициентов регрессии, а при наличии степеней свободы –адекватность уравнения.
В связи с тем, что корреляционная матрица (U*U)-1для спланированного эксперимента есть матрица диагональная
/>,
коэффициенты уравнения регрессии некоррелированы междусобой. Значимость коэффициентов уравнения регрессии можно проверять для каждогокоэффициента в отдельности, пользуясь критерием Стьюдента: />. Исключение изуравнения регрессии незначимого коэффициента не скажется на значениях остальныхкоэффициентов. При этом выборочные коэффициенты bjоказываются так называемыми несмешанными оценками для соответствующихгенеральных коэффициентов βj:
bj/> βj, т. е. величины коэффициентов уравнения регрессии характеризуют вкладкаждого фактора в величину y.
Диагональные элементы корреляционной матрицы равнымежду собой, поэтому все коэффициенты уравнений
Y = /> и Y = Р0+ Р1U1 + Р2U2 + … + РnUn+ … +
+ … + /> 
oпределяютсяс одинаковой точностью:
sbj= s2воспр/>
 
8. Проверкаадекватности уравнения
Проверка адекватности уравнения проводится по критериюФишера:
Рассчитывается значение
F= s2ост/ s2воспр; s2ост />,
где m — число значимых коэффициентов в уравнении регрессии.
2.  После проведения полного факторногоэксперимента определены коэффициенты регрессии
/>
Тогдачастные производные будут пропорциональны />.
3.  Делая, с учетом последнего выражения,шаг в сторону, противоположную среднему, определяем новую точку /> и опятьпроводим эксперимент.
4.  Повторяем первые три шага, пока неприблизимся к точке экстремума. При приближении к точке экстремума алгоритмначинает работать плохо при близости к нулю частных производных, то естьлинейная модель становится неадекватной и требует введения квадратичных членов.
Поусловию дано:

/>
/>/>, T =20, U(t) = 15 – 0.1t, />.
Уравнениевыхода системы:
 
/>, />, />.
Значениепараметров системы:
 
/>, />.
Характерпомехи и ее статистические параметры:
Нормальноераспределение />
/>.
Здесь/>-вектор состояния системы; /> — вектор наблюдения; />-вектор помехи; А, В, С – матрицы коэффициентов (параметров) системы; [0, T] – интервал определения системы.
Необходимо
— составить в соответствии с математическим ожиданием системы ее имитационнуюмодель для формирования реализации вектора и состояния системы на интервалеопределения;
— составить алгоритм и программу решения задачи построения динамической модели всоответствии с заданным типом модели методом идентификации и точностью решениязадачи;
— отладить программу;
— провести расчеты и анализ полученных результатов.
 />/>/>Построениематематической модели
Учитываяхарактер помехи можно составить следующую имитационную модель системы дляформирования реализации вектора и состояния системы на интервале определения:
 
/>,
/>, />; />.
Здесь/>-вектор состояния системы; /> — вектор состояния модели; /> -матрицы коэффициентов модели.
/>, T =20, U(t) = 15 – 0.1t, />.
Здесь[0, T] – интервал определения системы.
Уравнениевыхода системы:
/>, />, />.
Здесь/>-вектор наблюдения; /> — вектор помехи; С – матрицакоэффициентов (параметров) системы.
Значениепараметров системы:

/>, />.
ЗдесьА, В – матрицы коэффициентов (параметров) системы.
Характерпомехи и ее статистические параметры:
Помехаимеет нормальное распределение с математическим ожиданием, равным />./>/>/>Алгоритм реализациирешения задачи построения динамической модели
Идеяпостроения требуемой динамической системы состоит в следующем: для заданногозначения параметра t с его интервала определенияградиентным методом первого порядка находим соответствующее значение параметра x, который изменяется динамически.Поэтому необходимо в каждый момент ti найти оптимальное соответствующее значение фактора х ифункции отклика у, которые наиболее близко описывали бы исходную систему.Помеха имеет нормальное распределение, поэтому включаем ее в функцию откликатаким образом, как показано в выше предложенных формулах.
Дляпоиска решения необходимо рассчитать оптимальный шаг />.
Этоделается по выше указанной формуле ( 6 ) – поиск шага варьирования. Именно таки реализуем в программном решении данной задачи.
Дляпоиска оптимального решения используем матрицы коэффициентов модели />, спомощью которых определяем соответствующее значение функции отклика. Все вышесказанное реализовано в предлагаемой программе, в которой реализовано решениезадачи построения динамической модели в соответствии с заданным типом моделиметодом идентификации и точностью решения задачи. Программа отлажена наупрощенных тестовых примерах с использованием информации, полученной отимитационной тестовой модели.
Проведенанализ полученных результатов, что также отражено в предложенной программе./>/> />Апробирование машинной программы
Как было отмечено ранее, в данной программе кромеручного ввода исходных значений факторов Х (т. е. задание так называемой«нулевой точки») существует задание количества факторов и количества опытов,как по умолчанию, так и непосредственно пользователем.
Программа исследований программного эксперимента:
Решает задачу оптимизации поверхности отклика. Вначале работы требуется задать значения функции отклика Y, длякоторых и будет найдены соответствующие значения факторов X,при которых функция отклика принимает максимальное значение.
/>
1.Задаемколичество факторов и экспериментов

Получаем значения факторов в натуральном масштабе,заполняем матрицу планирования.
2.Производимкодирование в безразмерной системе координат, для каждого фактора определяютсянулевые уровни и интервалы варьирования. Они будут использованы для определенияградиента в данной точке.
/>
/>
3.Получаемзначения коэффициентов регрессии.
4.Считаемвыборочные дисперсии, и если они однородны, выводим значение дисперсиивоспроизводимости
5.Проверяем назначимость коэффициенты регрессии.
В данном случае все коэффициенты значимы.
6. Получаем информацию о том, описывает ли уравнениеэксперимент адекватно.
7. Делаем шаг в сторону, противоположную градиенту инаходим новую точку (набор факторов).
8. Для нового набора переходим к шагу 2. Выполняемуказанные действия до тех пор, пока не приблизимся к точке экстремума, на чтоуказывает убыль последующих значений функции отклика./>/>/>Результаты работыпрограммы
Матрицазначений функции отклика системы:
/>.
Матрицапомех:
/>.
Найденныезначения факторов, про которых функция отклика принимает максимальное значение:
/>

/> Вывод
В данном курсовом проектерассматривался градиентный метод первого порядка, в качестве ядра которогоиспользовался полный факторный эксперимент первого порядка, что предполагаеттакое проведение исследований, которое позволяет некоторым оптимальным образомполучить информацию об объекте, оформить её в виде полиномиальной линейноймодели и провести её статистический анализ. Так же в работе был составленалгоритм моделирования, на основе которого была написана программа дляпроведения исследований градиентным методом.

 Список литературы
1.  Ю.П. Зайченко. Исследование операций.“Вища школа”. Киев 1988.
2.  А.Г. Бондарь, Г.А. Статюха, Т. В.Землянкин, И.А. Потяженко. Планирование эксперимента при оптимизации процессовхимической технологии. “Вища школа”. Киев 1980.
3.  В.В. Кафаров. Методы кибернетики вхимии и химической технологии. Москва. «Химия». 1985.
4.  А.В. Бондаренко, Г.А. Статюха.Планирование эксперимента в химической технологии. “Вища школа”. Киев 1976.
5.А. Кофман, Р. Крюон “Массовое обслуживание. Теория и приложения”.6. Е.С.Венцель “Исследование операций”.
/>Листинг программыunitMainUnit;
interface
usesWindows,Classes,Graphics,SysUtils,StdCtrls,Math,Grids, ListControl,
Forms;
type
SelType =(stNONE,stPOINT,stCON); // Тип текущего элемента
PPoint =^TPoint;
TPoint =record
UIN: integer;
Value:integer;
X,Y: integer;
end;
PConnection =^TConnection;
TConnection =record
toPoint:PPoint;
fromPoint:PPoint;
Value:integer;
end;
CurElement =record
ceType:SelType;
element:pointer;
end;
TGraph = class
private
WasChanged:boolean;
ChangedAfter:boolean;
PointRadius:integer;
MaxUIN:integer;
Points:TList;
Connections:TList;
Selected,Current: CurElement;
functionCheckCicle(FP,TP:PPoint):boolean;
functionMouseOverPoint(X,Y:integer):PPoint;
functionMouseOverConnection(X,Y:integer):PConnection;
procedure
DrawConnections(C:TCanvas;minW,minH,maxW,maxH:integer);
procedureDrawPoints(C:TCanvas;minW,minH,maxW,maxH:integer);
procedureClear;
public
constructorCreate;
destructorDestroy;override;
functionMouseOver(X,Y:integer):CurElement;
functionDeleteSelected:boolean;
procedureDrawGraph(C:TCanvas;minW,minH,maxW,maxH:integer);
procedureAddPoint(X,Y:integer;Value:integer);
functionAddConnection(fromPoint,toPoint:PPoint;Value:integer):boolean;
procedureChangeCur(dX,dY:integer);
procedure
ChangeCurAndDrawContur(X,Y,GridDelta:integer;C:TCanvas;DrawFirst,D
rawSecond:boolean);
procedureGetDeltaOfCurrent(X,Y:integer;var dX,dY:integer);
procedureSaveToFile(filename:string);
procedureOpenFromFile(filename:string);
procedureSelectCurrent;
procedureDeselectCurrent;
procedureMoveOnTop;
functionIsChanged:boolean;
functionWasChangedAfter:boolean;
functionGetPoints:TList;
functionGetConnections:TList;
functionGetPointByID(ID:integer):PPoint;
procedureZoomOn(coef:extended);
procedureZoomOff(coef:extended);
procedureChangeValue(Elem:CurElement;Value:integer);
functionGetConsCount:integer;
functionGetPointsCount:integer;
end;
PProcCon =^TProcCon;
PProcPoint =^TProcPoint;
TProcCon =record
Value:integer;
toPoint:PProcPoint;
Next:PProcCon;
end;
TProcPoint =record
UIN: integer;
Value:integer;
Merged:boolean;
UBorder,DBorder: integer;
UCon,DCon:integer;
UFixed,DFixed: boolean;
Prev,Next:PProcCon;
end;
PWay = ^TWay;
TWay = record
Numbers:string;
Length:integer;
Weight:integer;
Current:PProcPoint;
end;
PLinkTask =^TLinkTask;
PProcTask =^TProcTask;
PHolder =^THolder;
THolder =record
Task:PProcTask;
Link:PLinkTask;
Next:PHolder;
end;
TProcTask =record
UIN: integer;
ProcNum:integer;
StartTime:integer;
Length: integer;
Prev:PHolder;
MayBeBefore:boolean;
MayBeAfter:boolean;
Ready:integer;
end;
TLinkTask =record
fromUIN:integer;
toUIN:integer;
fromProc:integer;
toProc:integer;
fromTask:PProcTask;
toTask:PProcTask;
StartTime:integer;
Length:integer;
PrevLink:PLinkTask;
PrevTask:PProcTask;
end;
PPossibleMove= ^TPossibleMove;
TPossibleMove= record
UIN: integer;
processor:integer;
afterUIN:integer;
ProcCount,Time:integer;
CurrentState:boolean;
end;
TSubMerger =class
private
Selected:PProcTask;
MinProcNum:integer;
MaxProcNum:integer;
Points:TList;
Procs: TList;
Links: TList;
AllProcTasks:Tlist;
functionGetProcPointByUIN(UIN:integer):PProcPoint;
functionGetProcTaskByUIN(UIN:integer):PProcTask;
procedureClear;
procedureClearProcs(FreeElements:boolean);
procedureClearLinks(FreeElements:boolean);
procedureFormLinkTasksAndSetTimes(NumOfProcs:integer);
// — Optimization — //
procedureClearPossibleMoves(var List:TList);
functionGetPossibleMoves(UIN:integer):TList;
functionGetTime:integer;
functionGetProcCount:integer;
procedureSaveBackUp(var List:Tlist);
procedureRestoreBackUp(var
List:Tlist;NOP:integer;ClearCurrent:boolean);
public
constructorCreate;
procedureInit(GPoints,GConnections:TList);
procedureDoBazovoe;
procedureSelectTask(UIN:integer);
procedureDeselectTask;
procedureMoveSelectedAfter(ProcNum,UIN:integer);
procedureShowSubMerging(SG:TStringGrid);
functionIncNumOfProc:boolean;
functionDecNumOfProc:boolean;
functionOptimizeOneStep(L1,L2:TLabel):boolean;
procedureOptimizeAuto(Form:TForm;L1,L2:TLabel);
end;
// — — ---//
functionMinInt(I1,I2:integer):integer;
functionMaxInt(I1,I2:integer):integer;
procedureMinMaxInt(I1,I2:integer;Var Min,Max:integer);
implementation
// — Nativefunctions — //
functionMinInt(I1,I2:integer):integer;
begin
if I1
end;
functionMaxInt(I1,I2:integer):integer;
begin
if I1>I2then Result:=I1 else Result:=I2
end;
procedureMinMaxInt(I1,I2:integer;Var Min,Max:integer);
begin
if I1
begin
Min:=I1;
Max:=I2
end
else
begin
Min:=I2;
Max:=I1
end
end;
// — Objects-- //
functionTGraph.GetConsCount:integer;
begin
Result:=Connections.Count
end;
functionTGraph.GetPointsCount:integer;
begin
Result:=Points.Count
end;
procedureTGraph.ZoomOn(coef:extended);
var PP:PPoint;
i:integer;
begin
for i:=0 toPoints.Count-1 do
begin
PP:=Points[i];
PP.X:=round(PP.X*coef);
PP.Y:=round(PP.Y*coef);
end;
end;
procedureTGraph.ZoomOff(coef:extended);
var PP:PPoint;
i:integer;
begin
for i:=0 toPoints.Count-1 do
begin
PP:=Points[i];
PP.X:=round(PP.X/coef);
PP.Y:=round(PP.Y/coef);
end;
end;
constructorTGraph.Create;
begin
inheritedCreate;
MaxUIN:=0;
Points:=TList.Create;
Connections:=TList.Create;
Current.ceType:= stNONE;
Current.element:= nil;
Selected.ceType:= stNONE;
Selected.element:= nil;
PointRadius :=15;
WasChanged :=false;
ChangedAfter:= false;
end;
destructorTGraph.Destroy;
begin
Clear;
Points.Destroy;
Connections.Destroy;
inheritedDestroy
end;
procedureTGraph.Clear;
begin
whilePoints.Count0 do
begin
dispose(PPoint(Points.first));
Points.delete(0);
end;
whileConnections.Count0 do
begin
dispose(PConnection(Connections.first));
Connections.delete(0);
end;
MaxUIN:=0;
Current.ceType:= stNONE;
Current.element:= nil;
Selected.ceType:= stNONE;
Selected.element:= nil;
end;
functionTGraph.DeleteSelected:boolean;
var i:integer;
PP:PPoint;
PC:PConnection;
begin
ifSelected.ceType = stNONE
thenResult:=false
else
begin
WasChanged:=true;
ChangedAfter:=true;
Result:=true;
ifSelected.ceType = stCON then
begin
PC:=Selected.element;
for i:=0 toConnections.Count-1 do
begin
ifConnections[i] = PC then
begin
Connections.delete(i);
break
end;
end;
dispose(PC);
end
else
begin
PP:=Selected.element;
for i:=0 toPoints.Count-1 do
begin
if Points[i] =PP then
begin
Points.delete(i);
break
end;
end;
i:=0;
whilei
begin
PC:=Connections[i];
if(PC.toPoint=PP)or(PC.fromPoint=PP)then
begin
Connections.delete(i);
dispose(PC)
end
else
i:=i+1
end;
dispose(PP)
end;
Selected.ceType:=stNONE;
Selected.element:=nil
end;
end;
procedureTGraph.MoveOnTop;
var PP:PPoint;
num:integer;
begin
ifCurrent.ceType = stPoint then
begin
WasChanged:=true;
// ChangedAfter:=true;
PP:=Current.element;
num:=0;
whilenum
begin
ifPoints[num]=PP then break;
num:=num+1
end;
Points.delete(num);
Points.add(PP)
end;
end;
procedureTGraph.SelectCurrent;
begin
Selected:=Current
end;
procedureTGraph.DeselectCurrent;
begin
Selected.ceType:=stNONE;
Selected.element:=nil
end;
functionTGraph.MouseOverPoint(X,Y:integer):PPoint;
var PP:PPoint;
d,i:integer;
begin
Result:=nil;
fori:=Points.Count-1 downto 0 do
begin
PP:=Points[i];
d :=round(sqrt((X-PP.X)*(X-PP.X)+(Y-PP.Y)*(Y-PP.Y)));
if d
begin
Result:=Points[i];
break
end;
end;
end;
functionTGraph.MouseOverConnection(X,Y:integer):PConnection;
varPC:PConnection;
i:integer;
TX,TY,FX,FY,d:integer;
begin
Result:=nil;
fori:=Connections.Count-1 downto 0 do
begin
PC:=Connections[i];
ifMinInt(PC.fromPoint.X,PC.toPoint.X) = PC.fromPoint.X then
begin
FX:=PC.fromPoint.X;
FY:=PC.fromPoint.Y;
TX:=PC.toPoint.X;
TY:=PC.toPoint.Y
end
else
begin
FX:=PC.toPoint.X;
FY:=PC.toPoint.Y;
TX:=PC.fromPoint.X;
TY:=PC.fromPoint.Y
end;
if(X>=FX-5)and(X
begin
d := (TY-FY)*X+ (FX-TX)*Y + TX*FY — FX*TY;
d :=abs(round(d/sqrt((TY-FY)*(TY-FY)+(FX-TX)*(FX-TX))));
if d
begin
Result:=Connections[i];
break
end
end
end
end;
functionTGraph.MouseOver(X,Y:integer):CurElement;
begin
current.element:=MouseOverPoint(X,Y);
ifcurrent.elementnil then current.ceType:=stPOINT
else
begin
current.element:=MouseOverConnection(X,Y);
ifcurrent.elementnil then current.ceType:=stCON
elsecurrent.ceType:=stNONE
end;
Result:=current;
end;
procedureTGraph.GetDeltaOfCurrent(X,Y:integer;var dX,dY:integer);
var PP:PPoint;
begin
PP:=current.element;
ifPPnil then
begin
dX:=X — PP.X;
dY:=Y — PP.Y
end
else
begin
dX:=0;
dY:=0
end;
end;
procedureTGraph.ChangeCur(dX,dY:integer);
var PP:PPoint;
begin
WasChanged:=true;
// ChangedAfter:=true;
PP:=current.element;
ifPPnil then
begin
PP.X:=PP.X+dx;
PP.Y:=PP.Y+dy
end
end;
procedure
TGraph.ChangeCurAndDrawContur(X,Y,GridDelta:integer;C:TCanvas;Dra
wFirst,DrawSecond:boolean);
var PP:PPoint;
begin
WasChanged:=true;
// ChangedAfter:=true;
ifcurrent.ceTypestNONE then
begin
PP:=current.element;
C.Brush.Style:=bsClear;
C.Pen.Mode :=pmNotXor;
C.Pen.Color:=clBlack;
C.Pen.Width:=1;
if DrawFirstthen C.Ellipse(PP.X-PointRadius,PP.Y-
PointRadius,PP.X+PointRadius,PP.Y+PointRadius);
ifGridDelta>1 then
begin
PP.X:=round(X/GridDelta)*GridDelta;
PP.Y:=round(Y/GridDelta)*GridDelta
end
else
begin
PP.X:=X;
PP.Y:=Y
end;
if DrawSecondthen C.Ellipse(PP.X-PointRadius,PP.Y-
PointRadius,PP.X+PointRadius,PP.Y+PointRadius);
C.Pen.Mode :=pmCopy;
C.Brush.Style:=bsSolid;
end;
end;
proceduregetArrowCoord(Fx,Fy,Tx,Ty:integer;R,Alpha:Integer;var
Ar1X,Ar1Y,Ar2X,Ar2Y:integer);
varCosV,SinV,D,CosAd2:extended;
a,b,c,Descr:extended;
y1,y2,x1,x2:extended;
RCosAd2,RSinAd2:integer;
begin
D :=sqrt((FX-TX)*(FX-TX)+(FY-TY)*(FY-TY));
if D0then CosV := (FX-TX) / D else CosV:=0;
if CosV = 0then
begin
RCosAd2 :=round(R*Cos(Pi*Alpha/360));
RSinAd2 :=round(R*Sin(Pi*Alpha/360));
Ar1X := TX +RSinAd2;
Ar2X := TX — RSinAd2;
if TY>FYthen Ar1Y := TY — RCosAd2
else Ar1Y :=TY + RCosAd2;
Ar2Y := Ar1Y;
end
else
begin
SinV :=(FY-TY) / D;
CosAd2 :=Cos(Pi*Alpha/360);
a:=1;
b:=-2*CosAd2*SinV;
c:=CosAd2*CosAd2-CosV*CosV;
Descr := b*b — 4*a*c;
y1 := (-b — sqrt(Descr))/(2*a);
y2 := (-b +sqrt(Descr))/(2*a);
x1 := (cosAd2- sinV*y1) / cosV;
x2 := (cosAd2- sinV*y2) / cosV;
Ar1X:=round(x1*R)+Tx;
Ar2X:=round(x2*R)+Tx;
Ar1Y:=round(y1*R)+Ty;
Ar2Y:=round(y2*R)+Ty;
end
end;
procedure
TGraph.DrawConnections(C:TCanvas;minW,minH,maxW,maxH:integer);
var i:integer;
PC:PConnection;
Ar1X,Ar1Y,Ar2X,Ar2Y:integer;
Poly:array[0..2]ofWindows.TPoint;
D:extended;
FX,FY,TX,TY:integer;
s:string;
W,H,X,Y:integer;
begin
C.Pen.Color :=clBlue;
for i:=0 toConnections.Count-1 do
begin
C.Brush.Color:= clBlue;
PC:=Connections[i];
ifSelected.element = PC then C.Pen.Width:=2
elseC.Pen.Width:=1;
C.moveto(PC.fromPoint.X,PC.fromPoint.Y);
C.lineto(PC.toPoint.X,PC.toPoint.Y);
FX:=PC.fromPoint.X;
FY:=PC.fromPoint.Y;
TX:=PC.toPoint.X;
TY:=PC.toPoint.Y;
D :=sqrt((FX-TX)*(FX-TX)+(FY-TY)*(FY-TY));
if D0then
begin
TX := round(TX — PointRadius*(TX-FX)/D );
TY := round(TY — PointRadius*(TY-FY)/D );
end;
getArrowCoord(FX,FY,TX,TY,10,45,Ar1X,Ar1Y,Ar2X,Ar2Y);
//
getArrowCoord(PC.fromPoint.X,PC.fromPoint.Y,PC.toPoint.X,PC.toPoint.
Y,Poin tRadius,10,45,Ar1X,Ar1Y,Ar2X,Ar2Y);
Poly[0].x :=TX;
Poly[0].y :=TY;
Poly[1].x :=Ar1X;
Poly[1].y :=Ar1Y;
Poly[2].x :=Ar2X;
Poly[2].y :=Ar2Y;
C.Polygon(Poly);
s:=inttostr(PC.Value);
H:=C.TextHeight('A');
W:=C.TextWidth(s);
X:=round((FX+TX-W)/2)-3;
Y:=round((FY+TY-H)/2)-1;
C.Brush.Color:= clWhite;
C.Rectangle(X,Y,X+W+7,Y+H+2);
C.Brush.style:=bsClear;
C.TextOut(X+3,Y+1,s);
C.Brush.style:=bsSolid;
{ C.moveto(Ar1X,Ar1Y);
C.lineto(PC.toPoint.X,PC.toPoint.Y);
C.moveto(Ar2X,Ar2Y);
C.lineto(PC.toPoint.X,PC.toPoint.Y);
}
end
end;
procedure
TGraph.DrawPoints(C:TCanvas;minW,minH,maxW,maxH:integer);
var i:integer;
PP:PPoint;
H,W:integer;
X1,X2,Y1,Y2:integer;
s:string;
begin
C.Brush.Style:= bsSolid;
C.Brush.Color:= clWhite;
C.Pen.Color :=clBlack;
for i:=0 toPoints.Count-1 do
begin
PP:=Points[i];
ifSelected.element = PP then C.Pen.Width:=2
elseC.Pen.Width:=1;
// C.Ellipse(PP.X-PointRadius,PP.Y-
PointRadius,PP.X+PointRadius,PP.Y+PointRadius+10);
X1:=PP.X-PointRadius;
Y1:=PP.Y-PointRadius;
X2:=PP.X+PointRadius;
Y2:=PP.Y+PointRadius;
if(X1minW)and(Y2>minH)then
C.Ellipse(X1,Y1,X2,Y2);
s:=inttostr(PP.Value);
H:=C.TextHeight('A');
W:=C.TextWidth(s);
C.TextOut(round(PP.X-W/2),round(PP.Y-H/2),s)
end;
C.Brush.Style:= bsClear;
C.Font.Color:=clBlack;
C.Font.Style:=[fsBold];
for i:=0 toPoints.Count-1 do
begin
PP:=Points[i];
s:=inttostr(PP.UIN);
H:=C.TextHeight('A');
W:=C.TextWidth(s);
C.TextOut(round(PP.X+PointRadius-W/2),PP.Y-PointRadius-H-1,s)
end;
C.Font.Style:=[];
C.Brush.Style:= bsSolid;
end;
procedure
TGraph.DrawGraph(C:TCanvas;minW,minH,maxW,maxH:integer);
begin
DrawConnections(C,minW,minH,maxW,maxH);
DrawPoints(C,minW,minH,maxW,maxH);
end;
procedureTGraph.AddPoint(X,Y:integer;Value:integer);
var PP:PPoint;
begin
WasChanged:=true;
ChangedAfter:=true;
MaxUIN:=MaxUIN+1;
new(PP);
PP.UIN:=MaxUIN;
PP.X:=X;
PP.Y:=Y;
PP.Value:=Value;
Points.Add(PP);
end;
function TGraph.CheckCicle(FP,TP:PPoint):boolean;
var List:TList;
PC:PConnection;
CurP:PPoint;
i:integer;
begin
Result:=true;
List:=TList.create;
List.add(TP);
whileList.Count0 do
begin
CurP:=List.first;
List.delete(0);
if CurP = FPthen
begin
Result:=false;
break
end;
for i:=0 toConnections.Count-1 do
begin
PC:=Connections[i];
ifPC.fromPoint = CurP then List.Add(PC.toPoint)
end
end;
List.clear;
List.Destroy
end;
function
TGraph.AddConnection(fromPoint,toPoint:PPoint;Value:integer):boolean;
varPC:PConnection;
begin
if(fromPointtoPoint)and CheckCicle(fromPoint,toPoint) then
begin
WasChanged:=true;
ChangedAfter:=true;
new(PC);
PC.fromPoint:=fromPoint;
PC.toPoint:=toPoint;
PC.Value:=Value;
Connections.Add(PC);
Result:=true
end
else
Result:=false
end;
procedureTGraph.SaveToFile(filename:string);
var f:file;
PP:PPoint;
PC:PConnection;
i:integer;
begin
assign(f,filename);
rewrite(f,1);
BlockWrite(f,Points.Count,SizeOf(integer));
BlockWrite(f,Connections.Count,SizeOf(integer));
for i:=0 toPoints.Count-1 do
begin
PP:=Points[i];
BlockWrite(f,PP,SizeOf(PP));
BlockWrite(f,PP^,SizeOf(PP^));
end;
for i:=0 toConnections.Count-1 do
begin
PC:=Connections[i];
// BlockWrite(f,PC,SizeOf(PC));
BlockWrite(f,PC^,SizeOf(PC^));
end;
close(f);
end;
procedureTGraph.OpenFromFile(filename:string);
type
PAddr =^TAddr;
TAddr = record
Old,New:pointer;
end;
var f:file;
Addresses:TList;
PA:PAddr;
PP:PPoint;
PC:PConnection;
p:pointer;
i,NOP,NOC:integer;
procedureSetNewAddr(iOld,iNew:pointer);
var PA:PAddr;
begin
new(PA);
PA.Old:=iOld;
Pa.New:=iNew;
Addresses.add(PA)
end;
functionGetNewAddr(Old:pointer):pointer;
var i:integer;
begin
Result:=nil;
for i:=0 toAddresses.Count-1 do
ifPAddr(Addresses[i]).Old = Old then
begin
Result:=PAddr(Addresses[i]).New;
Break
end;
end;
begin
MaxUIN:=0;
Clear;
WasChanged:=false;
ChangedAfter:=false;
Addresses:=TList.Create;
assign(f,filename);
reset(f,1);
BlockRead(f,NOP,SizeOf(integer));
BlockRead(f,NOC,SizeOf(integer));
for i:=0 toNOP-1 do
begin
new(PP);
BlockRead(f,p,SizeOf(p));
BlockRead(f,PP^,SizeOf(PP^));
Points.Add(PP);
SetNewAddr(p,PP);
If MaxUIN
end;
for i:=0 toNOC-1 do
begin
new(PC);
BlockRead(f,PC^,SizeOf(PC^));
PC.toPoint:=GetNewAddr(PC.toPoint);
PC.fromPoint:=GetNewAddr(PC.fromPoint);
Connections.Add(PC);
end;
close(f);
whileAddresses.Count0 do
begin
PA:=Addresses.first;
Addresses.Delete(0);
dispose(PA);
end;
Addresses.Destroy
end;
functionTGraph.IsChanged:boolean;
begin
Result:=WasChanged
end;
functionTGraph.WasChangedAfter:boolean;
begin
Result:=ChangedAfter;
ChangedAfter:=false;
end;
functionTGraph.GetPointByID(ID:integer):PPoint;
var PP:PPoint;
i:integer;
begin
Result:=nil;
for i:=0 toPoints.Count-1 do
begin
PP:=Points[i];
if PP.UIN=IDthen
begin
Result:=PP;
break
end;
end;
end;
functionTGraph.GetPoints:TList;
begin
Result:=Points
end;
functionTGraph.GetConnections:TList;
begin
Result:=Connections
end;
procedureTGraph.ChangeValue(Elem:CurElement;Value:integer);
begin
ifElem.elementnil then
begin
caseElem.ceType of
stPOINT:PPoint(Elem.element).Value:=Value;
stCON :PConnection(Elem.element).Value:=Value;
end;
WasChanged:=true;
ChangedAfter:=true
end
end;
// — SubMerger — //
constructorTSubMerger.Create;
begin
Points :=TList.Create;
AllProcTasks:= TList.Create;
Procs:=TList.Create;
Links:=TList.Create
end;
procedureTSubMerger.ClearProcs(FreeElements:boolean);
varPPT:PProcTask;
PH:PHolder;
tmpPoint:pointer;
List:TList;
begin
Selected:=nil;
whileProcs.Count0 do
begin
List:=Procs.first;
Procs.delete(0);
whileList.Count0 do
begin
PPT:=List.first;
List.delete(0);
PH:=PPT.Prev;
whilePHnil do
begin
tmpPoint:=PH.Next;
dispose(PH);
PH:=tmpPoint
end;
PPT.Prev:=nil;
PPT.MayBeAfter:=false;
PPT.MayBeBefore:=false;
ifFreeElements then dispose(PPT);
end;
List.destroy;
end;
ifFreeElements then AllProcTasks.clear;
end;
procedureTSubMerger.ClearLinks(FreeElements:boolean);
varPLT:PLinkTask;
List:TList;
begin
whileLinks.Count0 do
begin
List:=Links.first;
Links.delete(0);
whileList.Count0 do
begin
PLT:=List.first;
List.delete(0);
PLT.PrevLink:=nil;
PLT.PrevTask:=nil;
ifFreeElements then dispose(PLT);
end;
List.destroy;
end;
end;
procedureTSubMerger.Clear;
varPPP:PProcPoint;
PPC:PProcCon;
begin
whilePoints.Count0 do
begin
PPP:=Points.first;
Points.delete(0);
whilePPP.Prevnil do
begin
PPC:=PPP.Prev.Next;
dispose(PPP.Prev);
PPP.Prev:=PPC
end;
whilePPP.Nextnil do
begin
PPC:=PPP.Next.Next;
dispose(PPP.Next);
PPP.Next:=PPC
end;
dispose(PPP)
end;
ClearLinks(true);
ClearProcs(true);
AllProcTasks.Clear;
{
whileFProcTasks.Count0 do
begin
PPT:=FProcTasks.first;
FProcTasks.delete(0);
dispose(PPT)
end;
whileFLinkTasks.Count0 do
begin
PLT:=FLinkTasks.first;
FLinkTasks.delete(0);
dispose(PLT)
end;
}
end;
functionTSubMerger.GetProcPointByUIN(UIN:integer):PProcPoint;
var i:integer;
begin
Result:=nil;
for i:=0 toPoints.Count-1 do
ifPProcPoint(Points[i]).UIN = UIN then
begin
Result:=Points[i];
break
end;
end;
functionTSubMerger.GetProcTaskByUIN(UIN:integer):PProcTask;
var i:integer;
begin
Result:=nil;
for i:=0 toAllProcTasks.Count-1 do
ifPProcTask(AllProcTasks[i]).UIN = UIN then
begin
Result:=AllProcTasks[i];
break
end;
end;
procedureTSubMerger.Init(GPoints,GConnections:TList);
var i:integer;
PP:PPoint;
PC:PConnection;
PPP:PProcPoint;
PPC:PProcCon;
begin
Clear;
for i:=0 toGPoints.Count-1 do
begin
PP:=GPoints[i];
new(PPP);
PPP.UIN :=PP.Uin;
PPP.Value :=PP.Value;
PPP.UBorder:=0;
PPP.DBorder:=$8FFFFFFF;
PPP.UFixed:=false;
PPP.DFixed:=false;
PPP.UCon:=0;
PPP.DCon:=0;
PPP.Prev:=nil;
PPP.Next:=nil;
Points.Add(PPP);
end;
for i:=0 toGConnections.Count-1 do
begin
PC:=GConnections[i];
PPP :=GetProcPointByUIN(PC.fromPoint.UIN);
new(PPC);
PPC.Value :=PC.Value;
PPC.toPoint :=GetProcPointByUIN(PC.toPoint.UIN);
PPC.Next :=PPP.Next;
PPP.Next :=PPC;
PPP :=GetProcPointByUIN(PC.toPoint.UIN);
new(PPC);
PPC.Value :=PC.Value;
PPC.toPoint :=GetProcPointByUIN(PC.fromPoint.UIN);
PPC.Next :=PPP.Prev;
PPP.Prev :=PPC;
end;
end;
procedureSetUBorderToPPP(PPP:PProcPoint;Value:integer);
varPPC:PProcCon;
Fix:boolean;
begin
if PPP.UBorder
PPC:=PPP.Prev;
Fix:=true;
whilePPCnil do
begin
if notPPC.toPoint.DFixed then
begin
Fix:=false;
Break
end;
PPC:=PPC.Next
end;
PPP.UFixed:=Fix
end;
procedureSetDBorderToPPP(PPP:PProcPoint;Value:integer);
varPPC:PProcCon;
Fix:boolean;
begin
if PPP.DBorder> Value then PPP.DBorder := Value;
PPC:=PPP.Next;
Fix:=true;
whilePPCnil do
begin
if not PPC.toPoint.UFixedthen
begin
Fix:=false;
Break
end;
PPC:=PPC.Next
end;
PPP.DFixed:=Fix
end;
procedureSetUBorderDown(PPP:PProcPoint;Value:integer);
varPPC:PProcCon;
workPPP:PProcPoint;
List:TList;
begin
List:=TList.create;
if PPP.UBorder
begin
PPP.UBorder :=Value;
List.Add(PPP);
whileList.Count0 do
begin
workPPP:=List[0];
List.delete(0);
PPC:=workPPP.Next;
whilePPCnil do
begin
ifPPC.toPoint.UBorder
begin
PPC.toPoint.UBorder:=workPPP.UBorder+1;
List.Add(PPC.toPoint)
end;
PPC:=PPC.Next
end;
end;
end;
List.Destroy;
end;
procedureSetDBorderUp(PPP:PProcPoint;Value:integer);
varPPC:PProcCon;
workPPP:PProcPoint;
List:TList;
begin
List:=TList.create;
if PPP.DBorder> Value then
begin
PPP.DBorder :=Value;
List.Add(PPP);
whileList.Count0 do
begin
workPPP:=List[0];
List.delete(0);
PPC:=workPPP.Prev;
whilePPCnil do
begin
ifPPC.toPoint.DBorder > workPPP.DBorder-1 then
begin
PPC.toPoint.DBorder:=workPPP.DBorder-1;
List.Add(PPC.toPoint)
end;
PPC:=PPC.Next
end;
end;
end;
List.Destroy;
end;
procedureSetProcToPPP(PPP:PProcPoint;Value:integer);
varPPC:PProcCon;
begin
PPP.UBorder:=Value;
PPP.DBorder:=Value;
PPP.UFixed:=true;
PPP.DFixed:=true;
PPP.Merged:=true;
PPC:=PPP.Prev;
whilePPCnil do
begin
if notPPC.toPoint.Merged then
begin
//ifPPC.toPoint.DBorder>PPP.UBorder-1 then
SetDBorderToPPP(PPC.toPoint,PPP.UBorder-1);
SetDBorderToPPP(PPC.toPoint,PPP.UBorder-1);
PPC.toPoint.DCon:=PPC.toPoint.DCon+PPC.Value;
end;
PPC:=PPC.Next;
end;
PPC:=PPP.Next;
whilePPCnil do
begin
if notPPC.toPoint.Merged then
begin
//ifPPC.toPoint.UBorder
SetUBorderToPPP(PPC.toPoint,PPP.DBorder+1);
SetUBorderToPPP(PPC.toPoint,PPP.DBorder+1);
PPC.toPoint.UCon:=PPC.toPoint.UCon+PPC.Value;
end;
PPC:=PPC.Next;
end;
end;
procedureTSubMerger.DoBazovoe;
vari,j,p:integer;
PPP:PProcPoint;
PPC:PProcCon;
PW,newPW:PWay;
WorkList:TList;
WaysList:TList;
MaxWayLength:integer;
s: string;
//-->>
Pretender:PProcPoint;
NoChange:boolean;
PretenderCon:integer;
//-->>
PPT:PProcTask;
begin
ClearLinks(true);
ClearProcs(true);
AllProcTasks.Clear;
WaysList :=TList.Create;
WorkList :=TList.Create;
for i:=0 toPoints.Count-1 do
begin
PPP:=Points[i];
PPP.UBorder:=0;
PPP.DBorder:=$7FFFFFFF;
PPP.UCon:=0;
PPP.DCon:=0;
PPP.UFixed:=false;
PPP.DFixed:=false;
PPP.Merged:=false;
WorkList.Add(PPP)
end;
for i:=0 toPoints.Count-1 do
begin
PPP:=Points[i];
PPC:=PPP.Next;
whilePPCnil do
begin
for j:=0 toWorkList.Count-1 do
if PPC.toPoint= WorkList[j] then
begin
WorkList.delete(j);
break
end;
PPC:=PPC.Next
end;
end;
for i:=0 toWorkList.Count-1 do
begin
PPP:=WorkList[i];
new(PW);
PW.Length:=1;
PW.Numbers:=inttostr(PPP.UIN)+',';
PW.Weight:=PPP.Value;
PW.Current:=PPP;
WorkList[i]:=PW
end;
whileWorkList.Count0 do
begin
PW:=WorkList.first;
WorkList.delete(0);
ifPW.Current.Next=nil then WaysList.Add(PW)
else
begin
PPC:=PW.Current.Next;
whilePPCnil do
begin
new(newPW);
newPW.Length:=PW.Length+1;
newPW.Weight:=PW.Weight+PPC.Value+PPC.toPoint.Value;
newPW.Numbers:=PW.Numbers+inttostr(PPC.toPoint.UIN)+',';
newPW.Current:=PPC.toPoint;
WorkList.Add(newPW);
PPC:=PPC.Next
end;
dispose(PW)
end;
end;
MaxWayLength:= 0;
for i:=0 toWaysList.Count-1 do
begin
PW:=WaysList[i];
if PW.Length> MaxWayLength then MaxWayLength:=PW.Length
end;
for i:=0 toPoints.Count-1 do
begin
PPP:=Points[i];
if PPP.Prev =nil then SetUBorderDown(PPP,1);
if PPP.Next =nil then SetDBorderUp(PPP,MaxWayLength);
end;
for i:=0 toPoints.Count-1 do
begin
PPP:=Points[i];
if PPP.UBorder= PPP.DBorder then SetProcToPPP(PPP,PPP.UBorder);
end;
Pretender:=nil;
PretenderCon:=0;
repeat
NoChange:=true;
for i:=0 toPoints.Count-1 do
begin
PPP:=Points[i];
if notPPP.merged then
begin
if PPP.UFixedand PPP.DFixed then
begin
if PPP.UCon> PPP.DCon then SetProcToPPP(PPP,PPP.UBorder)
elseSetProcToPPP(PPP,PPP.DBorder);
Pretender:=nil;
NoChange:=false;
break
end
else
begin
if PPP.UFixedthen
begin
if(Pretender =nil)or(PretenderCon
begin
Pretender:=PPP;
PretenderCon:= PPP.UCon
end;
end
else
if PPP.DFixedthen
begin
if(Pretender =nil)or(PretenderCon
begin
Pretender:=PPP;
PretenderCon:= PPP.DCon
end;
end;
end;
end;
end;
ifPretendernil then
begin
ifPretender.UFixed then SetProcToPPP(Pretender,Pretender.UBorder)
elseSetProcToPPP(Pretender,Pretender.DBorder);
Pretender:=nil;
PretenderCon:=0;
NoChange:=false;
end;
untilNoChange;
for i:=0 toPoints.Count-1 do
begin
PPP:=Points[i];
new(PPT);
PPT.ProcNum:=PPP.UBorder;
PPT.ProcNum:=PPP.DBorder;
PPT.Ready:=0;
PPT.UIN:=PPP.UIN;
PPT.StartTime:=0;
PPT.Length:=PPP.Value;
PPT.Prev:=nil;
PPT.MayBeAfter:=false;
PPT.MayBeBefore:=false;
PPC:=PPP.Prev;
whilePPCnil do
begin
PPT.Ready:=PPT.Ready+1;
PPC:=PPC.next
end;
j:=0;
whilej
begin
ifPProcTask(AllProcTasks[j]).Ready > PPT.Ready then break;
j:=j+1;
end;
AllProcTasks.Add(PPT);
end;
FormLinkTasksAndSetTimes(MaxWayLength);
end;
procedureSetProcTimes(List:TList);
vari,j:integer;
PPT:PProcTask;
PH:PHolder;
Time,dTime:integer;
begin
Time:=1;
for i:=0 toList.Count-1 do
begin
PPT:=List[i];
PPT.StartTime:=Time;
Time:=Time+PPT.Length;
end;
for i:=0 toList.Count-1 do
begin
PPT:=List[i];
Time:=PPT.StartTime;
PH:=PPT.Prev;
whilePHnil do
begin
ifPH.Tasknil then
begin
if Time
Time:=PH.Task.StartTime+PH.Task.Length
end
else
begin
if Time
Time:=PH.Link.StartTime+PH.Link.Length
end;
PH:=PH.Next
end;
if Time > PPT.StartTimethen
begin
dTime:=Time-PPT.StartTime;
PPT.StartTime:=Time;
for j:=i+1 toList.Count-1 do
PProcTask(List[j]).StartTime:=PProcTask(List[j]).StartTime+dTime
end;
end;
end;
procedureSetProcStartTimes(List:TList);
var i:integer;
PPT:PProcTask;
Time:integer;
begin
Time:=1;
for i:=0 toList.Count-1 do
begin
PPT:=List[i];
PPT.StartTime:=Time;
Time:=Time+PPT.Length;
end;
end;
functionPLT_TimeCompare(I1,I2:Pointer):integer;
varD1,D2:integer;
Item1,Item2:PLinkTask;
begin
Item1:=I1;
Item2:=I2;
if Item1.StartTime
else
ifItem1.StartTime>Item2.StartTime then Result:=1
else
begin
ifItem1.toProc = Item2.toProc then
begin
ifItem1.toTask.StartTime
else
ifItem1.toTask.StartTime>Item2.toTask.StartTime then Result:=1
else Result:=0
end
else
begin
D1:=Item1.toProc- Item1.fromProc;
D2:=Item2.toProc- Item2.fromProc;
if D1>D2then Result:=1
else
if D1
else
begin
ifItem1.toProc
else
ifItem1.toProc>Item2.toProc then Result:=1
else
Result:=0
end;
end;
end;
end;
procedureSetLinkTimes(List:TList);
var i:integer;
PLT:PLinkTask;
Time:integer;
begin
for i:=0 toList.Count-1 do
begin
PLT:=List[i];
ifPLT.PrevTasknil then
Time:=PLT.PrevTask.StartTime+PLT.PrevTask.Length
else
Time:=PLT.PrevLink.StartTime+PLT.PrevLink.Length;
PLT.StartTime:=Time;
end;
List.Sort(PLT_TimeCompare);
Time:=1;
for i:=0 toList.Count-1 do
begin
PLT:=List[i];
ifTime>PLT.StartTime then PLT.StartTime:=Time;
Time:=PLT.StartTime+PLT.Length;
end;
end;
зrocedureTSubMerger.FormLinkTasksAndSetTimes(NumOfProcs:integer);
vari,j,k:integer;
PPT,toPPT:PProcTask;
PLT:PLinkTask;
PPP:PProcPoint;
PPC:PProcCon;
PH:PHolder;
tmpPoint:pointer;
List:TList;
begin
ClearLinks(true);
ClearProcs(false);
ifNumOfProcs0 then
begin
List:=TList.Create;;
Procs.Add(list);
for i:=1 toNumOfProcs-1 do
begin
List:=TList.Create;;
Procs.Add(list);
List:=TList.Create;
Links.Add(List)
end;
end;
for i:=0 toAllProcTasks.Count-1 do
begin
PPT:=AllProcTasks[i];
List:=Procs[PPT.ProcNum-1];
List.Add(PPT);
end;
// Формированик Линков
for i:=1 toProcs.Count-1 do
begin
List:=Procs[i];
for j:=0 toList.Count-1 do
begin
PPT:=List[j];
PPP:=GetProcPointByUIN(PPT.UIN);
PPC:=PPP.Prev;
whilePPCnil do
begin
toPPT:=GetProcTaskByUIN(PPC.toPoint.UIN);
iftoPPT.ProcNum = PPT.ProcNum then
begin
new(PH);
PH.Task:=toPPT;
PH.Link:=nil;
PH.Next:=PPT.Prev;
PPT.Prev:=PH;
end
else
begin
new(PLT);
PLT.length:=PPC.Value;
PLT.fromUIN:=toPPT.UIN;
PLT.fromProc:=toPPT.ProcNum;
PLT.toUIN:=PPT.UIN;
PLT.toProc:=PPT.ProcNum;
PLT.fromTask:=toPPT;
PLT.toTask:=PPT;
PLT.StartTime:=0;
PLT.PrevTask:=toPPT;
PLT.PrevLink:=nil;
Tlist(Links[toPPT.ProcNum-1]).Add(PLT);
tmpPoint:=PLT;
fork:=toPPT.ProcNum to PPT.ProcNum-2 do
begin
new(PLT);
PLT.length:=PPC.Value;
PLT.fromUIN:=toPPT.UIN;
PLT.fromProc:=toPPT.ProcNum;
PLT.toUIN:=PPT.UIN;
PLT.toProc:=PPT.ProcNum;
PLT.fromTask:=toPPT;
PLT.toTask:=PPT;
PLT.StartTime:=0;
PLT.PrevTask:=nil;
PLT.PrevLink:=tmpPoint;
Tlist(Links[k]).Add(PLT);
tmpPoint:=PLT
end;
new(PH);
PH.Task:=nil;
PH.Link:=tmpPoint;
PH.Next:=PPT.Prev;
PPT.Prev:=PH;
end;
PPC:=PPC.next
end;
end;
end;
for i:=0 toProcs.Count-1 do
SetProcStartTimes(Procs[i]);
for i:=0 toProcs.Count+Links.Count-1 do
if i mod 2 = 0then SetProcTimes(Procs[i div 2])
elseSetLinkTimes(Links[i div 2])
end;
procedureTSubMerger.ShowSubMerging(SG:TStringGrid);
vari,j,k:integer;
NumOfRows:integer;
List:TList;
PPT:PProcTask;
PLT:PLinkTask;
begin
NumOfRows:=1;
for i:=0 toProcs.Count-1 do
begin
List:=Procs[i];
ifList.Count0 then
begin
PPT:=List.last;
ifNumOfRows
NumOfRows:=PPT.StartTime+PPT.Length;
end;
end;
for i:=0 toLinks.Count-1 do
begin
List:=Links[i];
ifList.Count0 then
begin
PLT:=List.last;
ifNumOfRows
NumOfRows:=PLT.StartTime+PLT.Length;
end;
end;
// Чистим сетку//
SG.RowCount:=NumOfRows;
ifProcs.Count0 then SG.ColCount:=2*Procs.Count
else SG.ColCount:=0;
for i:=1 toSG.RowCount-1 do
for j:=1 toSG.ColCount-1 do SG.Cells[j,i]:='';
for i:=1 toSG.RowCount-1 do
SG.Cells[0,i]:=inttostr(i);
for i:=1 toSG.ColCount-1 do
if i mod 2 = 1then SG.Cells[i,0]:=inttostr((i div 2)+1)
elseSG.Cells[i,0]:='->';
ifSelectednil then
fori:=MinProcNum-1 to MaxProcNum-1 do
begin
List:=Procs[i];
ifList.Count0 then
begin
if(PProcTask(List.first).MayBeBefore)or(Selected=List.first)then
SG.Cells[2*i+1,0]:='m'+SG.Cells[2*i+1,0]
end
else
SG.Cells[2*i+1,0]:='m'+SG.Cells[2*i+1,0]
end;
SG.Cells[0,0]:='';
ifSG.ColCount1 then
begin
SG.FixedCols:=1;
SG.FixedRows:=1;
end;
// Вывод
for i:=0 toProcs.Count-1 do
begin
List:=Procs[i];
for j:=0 toList.Count-1 do
begin
PPT:=List[j];
fork:=PPT.StartTime to PPT.StartTime+PPT.Length-1 do
begin
SG.Cells[2*i+1,k]:=inttostr(PPT.UIN);
if Selected =PPT then SG.Cells[2*i+1,k]:='s'+SG.Cells[2*i+1,k]
else
ifPPT.MayBeAfter then SG.Cells[2*i+1,k]:='m'+SG.Cells[2*i+1,k]
end
end;
end;
for i:=0 toLinks.Count-1 do
begin
List:=Links[i];
for j:=0 toList.Count-1 do
begin
PLT:=List[j];
fork:=PLT.StartTime to PLT.StartTime+PLT.Length-1 do
SG.Cells[2*i+2,k]:=inttostr(PLT.fromUIN)+':'+inttostr(PLT.toUIN);
end;
end;
end;
procedureTSubMerger.SelectTask(UIN:integer);
vari,j:integer;
PPP,tmpPPP:PProcPoint;
PPC,prevPPC:PProcCon;
PPT:PProcTask;
PH:PHolder;
List:TList;
newStartIndex,StartIndex,EndIndex:integer;
Reset:boolean;
begin
Selected:=GetProcTaskByUIN(UIN);
for i:=0 toAllProcTasks.Count-1 do
begin
PPT:=AllProcTasks[i];
PPT.MayBeAfter:=PPT.UINUIN;
PPT.MayBeBefore:=PPT.MayBeAfter
end;
List:=TList.Create;
MinProcNum:=1;
MaxProcNum:=Procs.Count;
PPP:=GetProcPointByUIN(UIN);
PPC:=PPP.Prev;
whilePPCnil do
begin
PPT:=GetProcTaskByUIN(PPC.toPoint.UIN);
if PPT.ProcNum> MinProcNum then MinProcNum:=PPT.ProcNum;
PPC:=PPC.Next
end;
PPC:=PPP.Next;
whilePPCnil do
begin
PPT:=GetProcTaskByUIN(PPC.toPoint.UIN);
if PPT.ProcNum
PPC:=PPC.Next
end;
PPC:=PPP.Next;
whilePPCnil do
begin
List.Add(PPC.toPoint);
PPC:=PPC.Next
end;
whileList.Count0 do
begin
tmpPPP:=List.first;
GetProcTaskByUIN(tmpPPP.UIN).MayBeAfter:=false;
List.Delete(0);
PPC:=tmpPPP.Next;
whilePPCnil do
begin
List.Add(PPC.toPoint);
PPC:=PPC.next
end;
end;
PPC:=PPP.Prev;
whilePPCnil do
begin
List.Add(PPC.toPoint);
PPC:=PPC.Next
end;
whileList.Count0 do
begin
tmpPPP:=List.first;
GetProcTaskByUIN(tmpPPP.UIN).MayBeBefore:=false;
List.Delete(0);
PPC:=tmpPPP.Prev;
whilePPCnil do
begin
List.Add(PPC.toPoint);
PPC:=PPC.next
end;
end;
{ PPC:=PPP.Prev;
whilePPCnil do
begin
PPT:=GetProcTaskByUIN(PPC.toPoint.UIN);
PPT.MayBeAfter:=not (PPT.ProcNum
prevPPC:=PPC.toPoint.Prev;
whileprevPPCnil do
begin
List.Add(prevPPC.toPoint);
prevPPC:=prevPPC.Next
end;
PPC:=PPC.Next
end;
whileList.Count0 do
begin
tmpPPP:=List.First;
List.delete(0);
PPT:=GetProcTaskByUIN(tmpPPP.UIN);
PPT.MayBeAfter:=false;
PPC:=tmpPPP.Prev;
whilePPCnil do
begin
List.Add(PPC.toPoint);
PPC:=PPC.Next
end;
end;
//
PPC:=PPP.Next;
whilePPCnil do
begin
PPT:=GetProcTaskByUIN(PPC.toPoint.UIN);
PPT.MayBeBefore:=not (PPT.ProcNum > MaxProcNum);
prevPPC:=PPC.toPoint.Next;
whileprevPPCnil do
begin
List.Add(prevPPC.toPoint);
prevPPC:=prevPPC.Next
end;
PPC:=PPC.Next
end;
whileList.Count0 do
begin
tmpPPP:=List.First;
List.delete(0);
PPT:=GetProcTaskByUIN(tmpPPP.UIN);
PPT.MayBeBefore:=false;
PPC:=tmpPPP.Next;
whilePPCnil do
begin
List.Add(PPC.toPoint);
PPC:=PPC.Next
end;
end;
}
List.Destroy;
for i:=1 toMinProcNum-1 do
begin
List:=Procs[i-1];
for j:=0 toList.Count-1 do
begin
PPT:=PProcTask(List[j]);
PPT.MayBeAfter:=false;
PPT.MayBeBefore:=false
end;
end;
fori:=MaxProcNum+1 to Procs.Count do
begin
List:=Procs[i-1];
for j:=0 toList.Count-1 do
begin
PPT:=PProcTask(List[j]);
PPT.MayBeAfter:=false;
PPT.MayBeBefore:=false
end;
end;
fori:=MinProcNum to MaxProcNum do
begin
List:=Procs[i-1];
Reset:=false;
for j:=0 toList.Count-1 do
ifSelectedList[j] then
begin
if Reset then
begin
PPT:=PProcTask(List[j]);
PPT.MayBeAfter:=false;
end
elseReset:=not PProcTask(List[j]).MayBeAfter
end;
Reset:=false;
forj:=List.Count-1 downto 0 do
ifSelectedList[j] then
begin
if Reset then
begin
PPT:=PProcTask(List[j]);
PPT.MayBeAfter:=false;
PPT.MayBeBefore:=false;
end
elseReset:=not PProcTask(List[j]).MayBeBefore
end;
end;
end;
procedureTSubMerger.DeselectTask;
var i:integer;
PPT:PProcTask;
begin
Selected:=nil;
for i:=0 toAllProcTasks.Count-1 do
begin
PPT:=AllProcTasks[i];
PPT.MayBeAfter:=false;
PPT.MayBeBefore:=false;
end;
end;
procedureTSubMerger.MoveSelectedAfter(ProcNum,UIN:integer);
var i:integer;
PPT:PProcTask;
begin
ifSelectednil then
begin
ifUIN-1 then
begin
PPT:=GetProcTaskByUIN(UIN);
ifPPT.MayBeAfter then
begin
Selected.ProcNum:=PPT.ProcNum;
AllProcTasks.delete(AllProcTasks.IndexOf(Selected));
AllProcTasks.insert(AllProcTasks.IndexOf(PPT)+1,Selected);
FormLinkTasksAndSetTimes(Procs.Count);
end;
end
else
begin
Selected.ProcNum:=ProcNum;
AllProcTasks.delete(AllProcTasks.IndexOf(Selected));
i:=0;
whilei
begin
ifPProcTask(AllProcTasks[i]).ProcNum=ProcNum then break;
i:=i+1
end;
AllProcTasks.insert(i,Selected);
end;
FormLinkTasksAndSetTimes(Procs.Count);
end;
end;
functionTSubMerger.IncNumOfProc:boolean;
varList:TList;
begin
ifProcs.Count0 then
begin
List:=TList.Create;
Procs.Add(List);
List:=TList.Create;
Links.Add(List);
List:=nil;
Result:=true
end
elseResult:=false
end;
functionTSubMerger.DecNumOfProc:boolean;
vari,FoundNum:integer;
PPT:PProcTask;
begin
FoundNum:=0;
whileFoundNum
begin
ifTList(Procs[FoundNum]).Count=0 then break;
FoundNum:=FoundNum+1
end;
ifFoundNum
begin
Procs.Delete(FoundNum);
for i:=0 toAllProcTasks.Count-1 do
begin
PPT:=AllProcTasks[i];
ifPPT.ProcNum>FoundNum then PPT.ProcNum:=PPT.ProcNum-1;
end;
FormLinkTasksAndSetTimes(Procs.Count);
Result:=true
end
elseResult:=false;
end;
procedureTSubMerger.ClearPossibleMoves(var List:TList);
varPMT:PPossibleMove;
begin
whileList.Count0 do
begin
PMT:=List.first;
List.delete(0);
dispose(PMT)
end;
List.Destroy
end;
functionTSubMerger.GetPossibleMoves(UIN:integer):TList;
var i:integer;
PMT:PPossibleMove;
PPT:PProcTask;
List:TList;
begin
Result:=TList.Create;
SelectTask(UIN);
fori:=MinProcNum-1 to MaxProcNum-1 do
begin
List:=Procs[i];
if(List.Count=0)or((List.Count0)and(PProcTask(List.first).MayBeBefore)
or(Selected=List.first))then
begin
new(PMT);
PMT.UIN:=UIN;
PMT.processor:=i+1;
PMT.afterUIN:=-1;
PMT.Time:=$7FFFFFFF;
PMT.ProcCount:=$7FFFFFFF;
PMT.CurrentState:=false;
Result.Add(PMT);
end;
end;
for i:=0 toAllProcTasks.Count-1 do
begin
PPT:=AllProcTasks[i];
ifPPT.MayBeAfter then
begin
new(PMT);
PMT.UIN:=UIN;
PMT.processor:=PPT.ProcNum;
PMT.afterUIN:=PPT.UIN;
PMT.Time:=$7FFFFFFF;
PMT.ProcCount:=$7FFFFFFF;
PMT.CurrentState:=false;
Result.Add(PMT);
end;
end;
DeselectTask;
end;
functionTSubMerger.GetTime:integer;
var i:integer;
PPT:PProcTask;
List:TList;
begin
Result:=0;
for i:=0 toProcs.Count-1 do
begin
List:=Procs[i];
ifList.Count0 then
begin
PPT:=List.Last;
if Result
PPT.StartTime+PPT.Length-1
end;
end;
end;
functionTSubMerger.GetProcCount:integer;
var i:integer;
begin
Result:=0;
for i:=0 toProcs.Count-1 do
ifTList(Procs[i]).Count0 then Result:=Result+1
end;
functionTSubMerger.OptimizeOneStep(L1,L2:TLabel):boolean;
vari,j:integer;
List,AllMoves:TList;
PPM,bestPPM,workPPM:PPossibleMove;
PPT:PProcTask;
BackUpList:TList;
BackUpNOP:integer;
BestFit:integer;
CurProcCount,CurTime:integer;
MinTime:integer;
Unique:boolean;
PH:PHolder;
CurUIN,MinProcessor:integer;
begin
DeselectTask;
AllMoves:=TList.create;
for i:=0 toAllProcTasks.Count-1 do
begin
PPT:=AllProcTasks[i];
List:=GetPossibleMoves(PPT.UIN);
for j:=0 toList.Count-1 do AllMoves.add(List[j]);
List.clear;
List.Destroy;
end;
CurProcCount:=GetProcCount;
CurTime:=GetTime;
BackUpNOP:=Procs.Count;
SaveBackUp(BackUpList);
for i:=0 toAllMoves.Count-1 do
begin
PPM:=AllMoves[i];
Selected:=GetProcTaskByUIN(PPM.UIN);
Unique:=true;
ifSelected.ProcNum = PPM.processor then
begin
List:=Procs[Selected.ProcNum-1];
PPT:=nil;
for j:=0 toList.Count-1 do
begin
ifPProcTask(List[j]).UIN = PPM.UIN then break;
PPT:=List[j];
end;
if((PPTnil)and(PPT.UIN=PPM.afterUIN))or
((PPT=nil)and(PPM.afterUIN=-1))thenUnique:=false;
end;
PPM.CurrentState:= not Unique;
if Unique then
begin
ifPPM.afterUIN-1 then
(GetProcTaskByUIN(PPM.afterUIN)).MayBeAfter:=true;
MoveSelectedAfter(PPM.processor,PPM.afterUIN);
whileGetProcCountProcs.Count do DecNumOfProc;
PPM.Time:=GetTime;
PPM.ProcCount:=Procs.Count;
RestoreBackUp(BackUpList,BackUpNOP,false);
end
else
begin
PPM.Time:=CurTime;
PPM.ProcCount:=CurProcCount;
end;
end;
Selected:= nil;
RestoreBackUp(BackUpList,BackUpNOP,true);//??
MinTime:=$7FFFFFFF;
for i:=0 toAllMoves.Count-1 do
ifMinTime>PPossibleMove(AllMoves[i]).Time then
MinTime:=PPossibleMove(AllMoves[i]).Time;
//-->>
{ Memo.Lines.Clear;
for i:=0 toAllMoves.Count-1 do
begin
PPM:=AllMoves[i];
Memo.Lines.Add(inttostr(PPM.UIN)+'
'+inttostr(PPM.processor)+':'+inttostr(PPM.afterUIN)+'Time=
'+inttostr(PPM.Time)+'PC='+inttostr(PPM.ProcCount));
ifPPM.CurrentState then Memo.Lines.Add('Was current state!')
end;}
//
// выделяем минимальныевремена
i:=0;
whileiAllMoves.Count do
begin
PPM:=AllMoves[i];
if PPM.Time> MinTime then
begin
AllMoves.delete(i);
dispose(PPM);
end
else i:=i+1
end;
MinProcessor:=$7FFFFFFF;
for i:=0 toAllMoves.Count-1 do
ifMinProcessor>PPossibleMove(AllMoves[i]).ProcCount then
MinProcessor:=PPossibleMove(AllMoves[i]).ProcCount;
i:=0;
whileiAllMoves.Count do
begin
PPM:=AllMoves[i];
ifPPM.ProcCount > MinProcessor then
begin
AllMoves.delete(i);
dispose(PPM);
end
else i:=i+1
end;
i:=0;
CurUIN:=0;
MinProcessor:=0;
whileiAllMoves.Count do
begin
PPM:=AllMoves[i];
ifPPM.UINCurUIN then
begin
CurUIN:=PPM.UIN;
MinProcessor:=PPM.processor;
j:=i+1;
whilejAllMoves.Count do
begin
workPPM:=AllMoves[j];
ifworkPPM.UINCurUIN then break;
ifworkPPM.processor
MinProcessor:=workPPM.processor;
j:=j+1;
end;
end;
if(PPM.CurrentState)or(PPM.processor>MinProcessor)
then
begin
AllMoves.delete(i);
dispose(PPM);
end
else i:=i+1
end;
i:=0;
if MinTime =CurTime then
whilei
begin
PPM:=AllMoves[i];
PPT:=GetProcTaskByUIN(PPM.UIN);
ifPPM.processor = PPT.ProcNum then
begin
AllMoves.delete(i);
dispose(PPM);
end
else i:=i+1
end;
BestFit:=AllMoves.Count-1;
for i:=0 toAllMoves.Count-2 do
begin
PPM:=AllMoves[i];
bestPPM:=AllMoves[BestFit];
if(PPM.Time
((PPM.Time=bestPPM.Time)and(PPM.ProcCount
thenBestFit:=i
end;
ifBestFit-1 then
begin
bestPPM:=AllMoves[BestFit];
Selected:=GetProcTaskByUIN(bestPPM.UIN);
ifbestPPM.afterUIN-1 then
(GetProcTaskByUIN(bestPPM.afterUIN)).MayBeAfter:=true;
MoveSelectedAfter(bestPPM.processor,bestPPM.afterUIN);
whileGetProcCountProcs.Count do DecNumOfProc;
ifL1nil then L1.Caption:=inttostr(bestPPM.Time);
ifL2nil then L2.Caption:=inttostr(bestPPM.ProcCount);
Result:=true
end
elseResult:=false;
//-->>
{ Memo.Lines.Add('');
Memo.Lines.Add('---Min ---');
Memo.Lines.Add('');
for i:=0 toAllMoves.Count-1 do
begin
PPM:=AllMoves[i];
Memo.Lines.Add(inttostr(PPM.UIN)+'
'+inttostr(PPM.processor)+':'+inttostr(PPM.afterUIN)+'Time=
'+inttostr(PPM.Time)+'PC='+inttostr(PPM.ProcCount));
ifPPM.CurrentState then Memo.Lines.Add('Was current state!')
end;}
//
ClearPossibleMoves(AllMoves);
DeselectTask;
end;
functionComparePPT(Item1, Item2: Pointer): Integer;
begin
ifPProcTask(Item1).StartTime
1
else
ifPProcTask(Item1).StartTime>PProcTask(Item2).StartTime then Result:=1
else Result:=0
end;
procedureTSubMerger.OptimizeAuto(Form:TForm;L1,L2:TLabel);
vari,j,k:integer;
List,UINList:TList;
PPT,nextPPT:PProcTask;
Time:integer;
MatchError:boolean;
NewProc:TList;
NOP:integer;
NoChange:boolean;
StartFrom,NewStartFrom:integer;
BackList:TList;
BackTime:integer;
begin
whileOptimizeOneStep(L1,L2) do Form.Update;
Time:=GetTime;
UINList:=TList.Create;
NewStartFrom:=0;
repeat
StartFrom:=NewStartFrom;
NoChange:=true;
for i:=0 toProcs.Count-2 do
begin
NewStartFrom:=i+1;
List:=Procs[i];
for j:=0 to List.Count-1do UINList.Add(List[j]);
List:=Procs[i+1];
for j:=0 toList.Count-1 do UINList.Add(List[j]);
UINList.Sort(ComparePPT);
MatchError:=false;
PPT:=UINList.first;
for j:=1 toUINList.Count-1 do
begin
nextPPT:=UINList[j];
if(PPT.StartTime = nextPPT.StartTime) or
(PPT.StartTime+PPT.Length>nextPPT.StartTime)then
begin
MatchError:=true;
break
end;
PPT:=nextPPT;
end;
if notMatchError then
begin
SaveBackUp(BackList);
BackTime:=GetTime;
NOP:=Procs.Count-1;
ClearLinks(true);
ClearProcs(false);
for j:=0 toUINList.Count-1 do
begin
PPT:=UINList[j];
PPT.ProcNum:=i+1;
AllProcTasks.delete(AllProcTasks.indexOf(PPT));
end;
for j:=0 toAllProcTasks.Count-1 do
begin
PPT:=AllProcTasks[j];
ifPPT.ProcNum>i+1 then PPT.ProcNum:=PPT.ProcNum-1
end;
for j:=0 toUINList.Count-1 do AllProcTasks.add(UINList[j]);
FormLinkTasksAndSetTimes(NOP);
ifBackTime>=GetTime then
begin
NoChange:=false;
NewStartFrom:=0;
whileBackList.Count0 do
begin
PPT:=BackList.first;
BackList.delete(0);
dispose(PPT)
end;
end
elseRestoreBackUp(BackList,NOP+1,true);
break;
end;
UINList.Clear;
end;
UINList.Clear;
untilNoChange;
UINList.Destroy;
end;
procedureTSubMerger.SaveBackUp(var List:Tlist);
varbackPPT,PPT:PProcTask;
i:integer;
begin
List:=TList.Create;
for i:=0 toAllProcTasks.Count-1 do
begin
PPT:=AllProcTasks[i];
new(backPPT);
backPPT^:=PPT^;
backPPT.Prev:=nil;
List.add(backPPT);
end;
end;
procedureTSubMerger.RestoreBackUp(var
List:Tlist;NOP:integer;ClearCurrent:boolean);
varbackPPT,PPT:PProcTask;
i:integer;
begin
Selected:=nil;
ClearLinks(true);
ClearProcs(true);
for i:=0 toList.Count-1 do
begin
backPPT:=List[i];
new(PPT);
PPT^:=backPPT^;
AllProcTasks.add(PPT);
ifClearCurrent then dispose(backPPT);
end;
ifClearCurrent then List.Destroy;
FormLinkTasksAndSetTimes(NOP);
end;
end.