Диссертация (1152184), страница 22
Текст из файла (страница 22)
6 сетевой модели возможно найтисамый длинный путь (максимальный вес) от узла 0 на этапе = 0 до узла 5 на этапе = 3.Обозначим через � � величину самого длинного пути (наибольшего веса),ведущего в узел на этапе . Поскольку = 0 – это исходный этап, 0 (0) ≡ 0. Далеевычисления производятся поэтапно.Этап 1. Так как узел 0 на этапе = 0 с каждым из шести узлов1 = (0,1,2,3,4,5) на этапе = 1 соединяет единственная линия, самый длинныйпуть (наибольший вес) до узла 1 определяется формулой � � = 0 (0) + 1 (0, 1 ),где 1 (0, 1 ) – длина (вес) линии (0, 1 ).
Соответственно вычисляем 1 (0) = 0,1 (3) = 6, 1 (1) = 5, 1 (4) = 6, 1 (2) = 6, 1 (5) = 6.Полученные результаты представлены в виде сетевой модели на рисунке 34.Указанный на каждой линии вес представляет собой номер варианта,ассоциированного с этой дугой. Пунктирными линиями показаны оптимальныерешения для каждого этапа. Числа над окружностями указывают значение веса насамом длинном пути до соответствующего узла. На основании этих чиселвыполним вычисления на этапе 2.Этап 2. На данном этапе вычисляются величины самых длинных путей довсех узлов 2 = (0,1,2,3,4,5). В отличие от этапа 1 количество линий, входящих водин из узлов на этапе 2, может быть больше одной.
В результате имеемВеличина самогоВеличина самогоДлинаmax�� длинного пути � + � линии ��.� длинного пути � = по допустимым(1 , 2 )до узла 1до узла 2линиям (1 , 2 )132Этап 1f00Этап 2Этап 3f1f1f2f200000000555511116688222266131333336614144444661717555511f30Рисунок 34 – Оптимальное решение задачи модернизации и развитияаппаратной части ПАКЗапишем это равенство в математической форме:2 (2 ) =max{1 (1 ) + 2 (1 , 2 )}.по допустимымлиниям (1 , 2 )Выполним вычисления по данной формуле: 2 (0) =0, 2 (1) = 5, 2 (2) = 8,2 (3) = 13, 2 (4) = 14, 2 (5) = 17.Полученные результаты графически показаны на рис.
7 (этап 2),представлены линии, соответствующие вычисленным значениям 2 . Как и ранее,на линиях указаны веса соответствующих проектов.Этап 3. Аналогично этапу 2 соотношение, определяющее самый длинныйпуть 3 (3 ) до узла 3 запишем в следующем виде:1333 (3 ) =max{2 (2 ) + 3 (2 , 3 )}.по допустимымлиниям (2 , 3 )В результате вычислений находим 3 (5) = 17.Любой связанный путь от узла 0 на этапе = 0 до узла 5 на этапе = 3определяет оптимальное решение задачи модернизации и развития ПАК в условияхзаданного (ограниченного конкретной суммой) финансирования.
Всего имеетсятри различных решения, которые приведены в таблице 8.Таблица 8 – Варианты решения задачи проектирования ПАКОптимальный путьОптимальный набор вариантов(0,1), (0,4), (4,5)(2,3,2)(0,1), (0,5), (5,5)(2,4,1)(0,2), (2,4), (4,5)(3,2,2)Всем трем решениям соответствует один и тот же уровень предполагаемогодохода, а именно 3 = 17.Разработанные сетевые модели в дальнейшем применяются для построениямоделей динамического программирования.
Структура модели динамическогопрограммирования основывается на рекуррентных вычислительных процедурах.Как было рассмотрено выше, задача декомпозируется на три этапа. Расчеты(вычисления) на определенном этапе выполняются на основе обобщеннойинформации о максимальной суммарной предполагаемой прибыли (самомбольшом суммарном весе), полученном в результате вычислений на всехпредыдущих этапах.
Отдельные, промежуточные решения, полученные напредыдущих этапах, не представляют существенной ценности. Все последующиевычисления строятся определенным оптимальным способом, вне зависимости отрешений, полученных на предыдущих этапах. Все вышесказанное представляетсобойсущностьпринципаоптимальности,составляющегофундаментвычислительного аппарата динамического программирования.При разработке сетевой модели очень важным является решение задачиопределения значения , которое дает возможность исключать из дальнейшихрасчетов недопустимые или неоптимальные линии и соответствующие варианты.134В процессе работы аппарат динамического программирования используетаналогичный метод, оперирующий понятием «состояния» системы. Под этимсостоянием можно понимать взаимное объединение этапов в некоторую системукомпромиссов,обусловленныхограниченнымколичествомопределенногоресурса.Рекуррентное соотношение динамического программирования для решениярассматриваемой задачи можно записать в видеmax� � � + −1 �−1 �� , = 1,2,3, � � = по допустимымвариантам где 0 (0 ) ≡ 0 по определению.
Приведенное равенство действительно являетсярекуррентным, так как величина � � на этапе вычисляется по известномузначению −1 �−1 �, полученному на предыдущем этапе − 1 при 0 (0 ) = 0.Чтобы представить рекуррентное соотношение в корректной математическойформе, необходимо сделать два замечания, которые устранят кажущиеся различиямежду моделью динамического программирования и сетевой моделью длярассматриваемой задачи модернизации и развития ПАК.Во-первых, заметим, что � � является функцией единственного аргумента .
Отсюда следует, что правая часть рекуррентного соотношения должна бытьвыражена через , а не через −1 . В случае сетевой модели разность между и−1 равна величине инвестиций в проект на этапе , то есть � � = − −1 .На основании этого становится возможным выразить −1 через спомощью равенства −1 = − � �. Такая замена обеспечивает болеекорректную математическую запись рекуррентного соотношения.Во-вторых, необходимо представить в математической форме ограничение,разрешающее рассматривать для вычислений только допустимые варианты.Аналогично решению задачи при помощи сетевой модели можно использоватьравенство � � = − −1 .
Однако это ограничение уже было введено вышепутем замены −1 = − � � в функции −1 �−1 �. Чтобы обеспечить полную135корректность, следует в явном виде учесть неравенство −1 ≥ 0, откуда − � � ≥ 0 или � � ≤ .Такимобразом,рекуррентноесоотношениединамическогопрограммирования имеет следующий вид:0 (0 ) ≡ 0, � � = max � � � + −1 � − � ��� , = 1,2,3.
� �≤Выполним согласно приведенной формуле решение задачи модернизации иразвитияПАКавтоматизациитехнологическихиобеспечивающихпроизводственных процессов.1 (1 ) =2 (2 ) =3 (3 ) =max {1 (1 )}.1 (1 )≤11 =1,2,3max �2 (2 ) + 1 �2 − 2 (2 )��.2 (2 )≤22 =1,2,3,4max �3 (3 ) + 2 �3 − 3 (3 )��.3 (3 )≤33 =1,2Оптимальное решение задачи возможно найти из приведенных таблиц.Сначала рассматривается этап 3.
При 3 = 5 оптимальный проект имеет либо3∗ = 1 либо 3∗ = 2. Пусть сначала 3∗ = 1. Так как 3 (1) = 0, на этапах 2 и 1 2 =3 − 3 (1) = 5. На этапе 2 из 2 = 5 следует 2∗ = 4. 2 (4) = 4, откуда 1 = 5 − 4 =1. На этапе 1 из 1 = 1 следует, что 1∗ = 2. Таким образом получается, что (2,4,1)есть оптимальный набор вариантов для соответствующих этапов 1,2,3.Приведенные выше вычисления оперируют этапами (1,2,3) в естественномпорядке их расположения, что представляется логичным и удобным длярассмотрения.Однакоопытпримененияметодовдинамическогопрограммирования показывает, что оперирование этапами в обратном порядкеболее эффективно. Особенно это касается случаев, когда этапы расположены другза другом в хронологическом порядке, то есть имеют временную составляющую.Часто при применении метода «прямой прогонки» невозможно определитьсостояние систем таким образом, чтобы на него не влияли предыдущие состояния,136что следует из принципа оптимальности.
Применение же метода «обратнойпрогонки» позволяет решить эту проблему. На рисунке 35 показано, какопределяется состояние системы при прямом и обратном порядке вычислений.Рисунок 35 – Определение состояния системы при прямом и обратномпорядках вычисленийКак видно из рисунка 33, и являются состояниями системы на различныхэтапах при прямом и обратном порядке вычислений соответственно.
Обозначим ( ) как максимальный доход. Рекуррентное соотношение для процедурыобратной прогонки будет иметь следующий вид: � � =4 (4 ) ≡ 0,max � � � + +1 � − � ��� , = 1,2,3. � �≤Порядок поэтапных вычислений определяется последовательностью этапов3 → 2 → 1 . Ниже приведены результаты расчетов для всех трех этапов.Этап 1:3 (3 ) =3max {3 (3 )}3 (3 )≤33 =1,23 (3 )Оптимальное решение03 = 103 = 2–3 (3 )03∗10332113720332303324033250332Этап 2:2 (2 ) =2max �2 (2 ) + 3 �2 − 2 (2 )��2 (2 )≤22 =1,2,3,4Оптимальное решение2 (2 ) + 1 �2 − 2 (2 )�02 = 10+0=02 = 2–2 = 3–2 = 4–2 (2 )02∗10+3=3–––3120+3=38+0=8––8230+3=38+3=119+0=9–11240+3=38+3=119+3=12 12+0=12123 или 450+3=38+3=119+3=12 12+3=151541Этап 3:1 (1 ) =15max �1 (1 ) + 2 �1 − 1 (1 )��2 (1 )≤11 =1,2,3Оптимальное решение3 (3 ) + 2 �3 − 3 (3 )�1 = 10+15 = 15Оптимальное1 = 25+12 = 17решение1 = 36+11 = 17можно1 на этапе 1 и двигаясь далее до 3 на этапе 3.1 (1 )17определить,1∗2 или 3начинаяс138Выводы по главе 3По результатам изучения существующих современных патентов разработанафункциональная схема автоматизации процесса горячего копчения рыбы на основеразрабатываемого универсального ПАК, в котором управление осуществляетсяпосредствомпрограммногопакета,исполняемогонаединоймини-ЭВМ.По результатам анализа функциональной схемы автоматизации и на основеопределенных совместно с главным технологом ООО «РИФ» значенийпрограммныхуправленийразработанаматематическаямодельсистемыавтоматического управления процессом горячего копчения рыбы.Методом Красовского Н.Н.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
