Принцип динамического программирования

 

Принцип динамического программирования Беллмана состоит в следующем. Если существует оптимальная траектория, то каждый ее остаточный фрагмент также является оптимальной траекторией. Если отыскание одного последнего шага проще, чем отыскание всех шагов сразу, то может быть построена итеративная процедура с отысканием итоговой траектории по этим фрагментам, т.е. задача решается «с конца».

При графическом решении таких задач строится поле оптимальных направлений для каждой точки.

Например, в пространстве фазовых траекторий строим поверхности одинаковой цены пути до цели, начиная от ε-окрестности цели. Первая такая поверхность строится легко, она совпадает с точкой цели. Следующие поверхности строятся так близко, что можно применить линеаризацию для исчисления цены пути. Поверхность, соединяющая точки одинаковой длины для предыдущей поверхности равной цены является новой поверхностью. И так далее.

На рис.1. показан пример решения лабиринта на этом принципе. Движение разрешено только по клеточкам (включая движение вдоль стены, если ее граница совпадает с линией клеточки). Решение осуществляется по следующему алгоритму: каждому углу клеток, начиная с ближайших к финишу точки, приписывается цена, соответствующая оставшемуся расстоянию до финиша. При различных способах движения от данного угла до финиша фиксируется кратчайший путь и углу в качестве характеристики присваивается минимальное расстояние. Таким образом, в соответствии с одним вариантом движения граница старта получает цену 50, по другому пути – 36, а по третьему – 32.

Интуитивный принцип «лучше плохо ехать, чем хорошо стоять» или «лучше приближаться, чем удаляться» не всегда выполняется. Иной раз кратчайшее расстояние начинается с таких шагов, которые направлены не по направлению к цели, а в противоположном направлении.

Обязательный принцип состоит в том, что на каждом этапе критерий оптимальности должен быть тот же самый, изменения критерия недопустимо. Изменение метода поиска оптимальной траектории может иметь место, при условии, что сам критерий не меняется.

Пример неправильного действия: если одну траекторию оптимизировать «по цене», а другую – «по времени», можно половину пути пройти пешком, а вторую проехать на такси. В итоге будет чрезмерно дорого и чрезмерно долго.

Рис.1. Поиск кратчайшего расстояния методом динамического программирования.

 

Другой пример: на одном этапе вызваться перетаскивать грузы, дабы получить освобождение от бесплатного образования, а на втором этапе, допустим, заплатить за образование, чтобы снизить свои усилия по получению знаний и лучше подготовиться к экзаменам, то в целом получается, что обучающийся заплатил за то, чтобы работать грузчиком (хотя на самом деле за это должны платить зарплату). Кажущийся выигрыш в одном и кажущийся выигрыш в другом на разных этапах на деле обращается в чистый проигрыш.

Пример того, что методику поиска оптимума можно на разных этапах менять, лишь бы критерий не менялся: скажем, начальные настройки регулятора могут быть получены градиентным способом, а окончательные – простым дроблением шага и анализом результата (подобно тому, как осуществляется поразрядное уравновешивание в АЦП). Градиентный способ на начальном этапе позволяет правильно указать направление и даже величину шагов по направлению к оптимуму, поэтому он более эффективен. На последних этапах градиент мал, вычисления градиента по сложности не уменьшаются, поиск может затянуться, процедура оптимизации – зациклиться. Тогда как простое дробление шага может привести к нужному результату за фиксированное количество шагов при фиксированной требуемой точности.

Примеры из социологии.

Разрезание «государственного» пирога по Беллману. При условии, что пирог требуется разделить на N частей, и каждый имеет право отрезать и выбрать себе кусок, получится, что первые будут отрезать и выбирать большие куски. Если сформулировать правило, в соответствии с которым первый отрезающий будет последним выбирающим, то каждый будет заинтересован в отрезании долей, равных 1/ N. При этом первый берущий вообще не должен ничего резать. В политике это означает, что делить бюджет должны не те, кто возглавляет ведомства, которые будут этот бюджет тратить. Например, конгресс делит бюджет по статьям или по министерствам, а министерства уже получают эти доли, но сами конгрессмены не заинтересованы в увеличении чьей-то доли, дабы не вносить субъективности (т.е., естественно, необъективности, неправильности).

Деление зарплат по голосованию большинства. Если председательствующий будет ставить на голосование предложение обездолить одного (за какую-то реальную или надуманную вину) и раздать его долю остальным, он будет всегда получать поддержку большинства. За M постановок на голосование можно наказать порциями по 1/ K членов (или групп) общества общим числом в M / K. Требование поддержки простым большинством выполняется при K >2, а квалифицированным большинством – при K >3. Таким образом, за требуемое количество итераций он может обездолить не меньшинство, а большинство. Чтобы обездолить все 100% (кроме себя любимого), достаточно в самом примитивном случае трех голосований. Для более завуалированных действий потребуется больше голосований, но суть останется той же: манипулируя мнением большинства, можно подавить не только меньшинство, а также и большинство членов общества, имеющих право голоса. Это достигается именно потому, что критерии между разными голосованиями меняются. Фиксация и преемственность критериев (законов), таким образом, служит основой полезности демократии. Именно поэтому для изменения законов обычно требуется не простое большинство, а квалифицированное большинство (т.е. более 2/3 присутствующих) при условии явки квалифицированного кворума (т.е. более 2/3 списочного состава).

Критерий maximin (максимум из минимума) или minimax (минимум из максимума). Часто применятся в теории игр для минимизации риска или максимизации прибыли для самого плохого случая. В оценке общества тоже защищенность самого бесправного члена общества – показатель его гуманности (но не имеет ничего общего с принципом демократии). Суд Линча – тоже демократический аппарат. Приговор Сократа в Афинах также был осуществлен по всем правилам «демократического» голосования.

 

Литература

 

1. Норенков И.П. Основы автоматизированного проектирования. Изд-е второе. М.: Изд-во МГТУ им. Н.Э. Баумана. 2002.

2. Владимир Малюх. Введение в современные САПР. Курс лекций. М. ДМК Пресс. 2010.192 с.

3. Сайт разработчика MexBIOS Development Studio http://www.mechatronica-pro.com/

4. В. А. Жмудь. Моделирование и оптимизация систем управления в среде VisSim // Труды семинара по автоматике и программной инженерии, посвященного юбилею ОАО «Новосибирский институт программных систем» (ОАО «НИПС») 16.04.2012, Новосибирск, типогр. ЗАО «КАНТ». С.90–140. – с сайта http://www.nips.ru/index.php?option=com_content&view=article&id=140&Itemid=303/

5. Жмудь В. А. Моделирование и оптимизация систем управления лазерным излучением в среде VisSim: учеб. пособие / В. А. Жмудь; Новосиб. гос. техн. ин-т. – Новосибирск: Изд-во НГУ, 2009. – 116 c.

6. С.Г. Герман-Галкин. Компьютерное моделирование полупровод­нико­вых систем. MatLAB 6.0. СПб.: Корона. 2001.

7. С.Г. Герман-Галкин. MatLAB 6.0 & Simulink. Проектирование мехатрон­ных систем на ПК. Учебное пособие для вузов. СПб.: Корона. 2008.

8. В.П. Дьяконов. Simulink 5/6/7. Самоучитель. М.: ДМК-Пресс. 2008.

9. Суранов А.Я. LabVIEW 7: Справочник по функциям. М.:ДМК Пресс. 2008.

10. Кузин Л.Т. Основы кибернетики. Т.1. Математические основы кибернетики. Учеб. пособие для студентов втузов. М. Энергия. 1973.

ПРИЛОЖЕНИя

Приложение 1. Система технической документации на АСУ

 

1. Виды и комплектность документов ГОСТ 34.201-89
2. Обозначение документов ГОСТ 34.201-89
3. ГОСТ 24.103-84 Автоматизированные системы управления. Общие положения
4. ГОСТ 24.104-85 Автоматизированные системы управления. Общие требования Раздел 3 заменен на ГОСТ 34.603-92
5. Требования к содержанию документа «Техническое задание» ГОСТ 34.602-89
6. ГОСТ 24.202-80 Требования к содержанию документа «Технико-экономическое обоснование»
7. ГОСТ 24.203-80 Требования к содержанию общесистемных документов
8. ГОСТ 24.204-80 Требования к содержанию документа «Описание постановки задачи»
9. ГОСТ 24.205-80 Требования к содержанию документов по информационному обеспечению
10. ГОСТ 24.206-80 Требования к содержанию документов по техническому обеспечению
11. ГОСТ 24.207-80 Требования к содержанию документов по программному обеспечению
12. ГОСТ 24.208-80 Требования к содержанию документов стадии «Ввод в эксплуатацию»
13. ГОСТ 24.209-80 Требования к содержанию документов по организационному обеспечению
14. ГОСТ 24.210-82 Требования к содержанию документов по функциональной части
15. ГОСТ 24.211-82 Требования к содержанию документа «Описание алгоритма»
16. Состав и содержание работ по стадиям ГОСТ 34.601-90

 

Приложение 2. Выдержки из ГОСТ 34.601-90. Автоматизированные системы. Стадии создания

Настоящий стандарт распространяется на автоматизи­рован­ные системы (АС), используемые в различных видах деятель­ности (исследование, проектирование, управление и т.п.), включая их сочетания, создаваемые в организациях, объеди­нениях и на предприятиях (далее - организациях).

Стандарт устанавливает стадии и этапы создания АС. В прило­жении 2.1 приведено содержание работ на каждом этапе.

ОБЩИЕ ПОЛОЖЕНИЯ

1.1. Процесс создания АС представляет собой совокупность упорядоченных во времени, взаимосвязанных, объединённых в стадии и этапы работ, выполнение которых необходимо и достаточно для создания АС, соответствующей заданным требованиям.

1.2. Стадии и этапы создания АС выделяются как части процесса создания по соображениям рационального планирования и организации работ, заканчивающихся заданным результатом.

1.3. Работы по развитию АС осуществляют по стадиям и этапам, применяемым для создания АС.

1.4. Состав и правила выполнения работ на установленных настоящим стандартом стадиях и этапах определяют в соответствующей документации организаций, участвующих в создании конкретных видов АС.

Перечень организаций, участвующих в работах по созданию АС, приведён в приложении 2.2.

СТАДИИ И ЭТАПЫ СОЗДАНИЯ АС

2.1. Стадии и этапы создания АС в общем случае приведены в таблице.

Стадии	Этапы работ
1. Формирование требований к АС	1.1. Обследование объекта и обоснование необходимости создания АС. 1.2. Формирование требований пользователя к АС. 1.3. Оформление отчёта о выполненной работе и заявки на разработку АС (тактико-технического задания)
2. Разработка концепции АС.	2.1. Изучение объекта. 2.2. Проведение необходимых научно-исследовательских работ. 2.3. Разработка вариантов концепции АС, удовлетворяющего требованиям пользователя. 2.4. Оформление отчёта о выполненной работе.
3. Техническое задание.	Разработка и утверждение технического задания на создание АС.
4. Эскизный проект.	4.1. Разработка предварительных проектных решений по системе и её частям. 4.2. Разработка документации на АС и её части.
5. Технический проект.	5.1. Разработка проектных решений по системе и её частям. 5.2. Разработка документации на АС и её части. 5.3. Разработка и оформление документации на поставку изделий для комплектования АС и (или) технических требований (технических заданий) на их разработку. 5.4. Разработка заданий на проектирование в смежных частях проекта объекта автоматизации.
6. Рабочая документация.	6.1. Разработка рабочей документации на систему и её части. 6.2. Разработка или адаптация программ.
7. Ввод в действие.	7.1. Подготовка объекта автоматизации к вводу АС в действие. 7.2. Подготовка персонала. 7.3. Комплектация АС поставляемыми изделиями (программными и техническими средствами, программно-техническими комплексами, информационными изделиями). 7.4. Строительно-монтажные работы. 7.5. Пусконаладочные работы. 7.6. Проведение предварительных испытаний. 7.7. Проведение опытной эксплуатации. 7.8. Проведение приёмочных испытаний.
8. Сопровождение АС	8.1. Выполнение работ в соответствии с гарантийными обязательствами. 8.2. Послегарантийное обслуживание.

2.2. Стадии этапы, выполняемые организациями – участ­никами работ по созданию АС, устанавливаются в договорах и техни­ческом задании на основе настоящего стандарта.

Допускается исключить стадию "Эскизный проект" и отдель­ные этапы работ на всех стадиях, объединять стадии "Техни­чес­кий проект" и "Рабочая документация" в одну стадию "Техно­рабочий проект". В зависимости от специфики создаваемых АС и условий их создания допускается выполнять отдельные этапы работ до завершения предшест­вующих стадий, параллельное во времени выполнение этапов работ, включение новых этапов работ.

 

ПРИЛОЖЕНИЕ 2.1
(справочное)

СОДЕРЖАНИЕ РАБОТ

1. На этапе 1.1. "Обследование объекта и обоснование необходимости создания в АС" общем случае проводят:

• а) сбор данных об объекте автоматизации и осуществляемых видах деятельности;
• б) оценку качества функционирования объекта и осуществляемых видах деятельности, выявление проблем, решение которых возможно средствами автоматизации;
• в) оценку (технико-экономической, социальной и т.д.) целесообразности создания АС.

2. На этапе 1.2. "Формирование требований пользователя к АС" проводят:

• а) подготовку исходных данных для формирования требований АС (характеристика объекта автоматизации, описание требований к системе, ограничения допустимых затрат на разработку, ввод в действие и эксплуатацию, эффект, ожидаемый от системы, условия создания и функционирования системы);
• б) формулировку и оформление требований пользователя к АС.

3. На этапе 1.3. "Оформление отчёта о выполненной работе и заявки на разработку АС (технико-технического задания)" проводят оформление отчета о выполненных работах на данной стадии и оформление заявки на разработку АС (тактико-технического задания) или другого заменяющего её документа с аналогичным содержанием.

4. На этапах 2.1. "Изучение объекта" и 2.2. "Проведение научно-исследовательских работ" организация-разработчик проводит детальное изучение объекта автоматизации и необходимые научно-исследовательские работы (НИР), связанные с поиском путей и оценкой возможности реализации требований пользователя, оформляют и утверждают отчёты о НИР.

5. На этапе 2.3. "Разработка вариантов концепции АС и выбор варианта концепции АС, удовлетворяющего требованиям пользователя" в общем случае, проводят разработку альтернативных вариантов концепции создаваемой АС и планов их реализации; оценку необходимых ресурсов на их реализацию и обеспечение функционирования; оценку преимуществ и недостатков каждого варианта; определение порядка оценки качества и условий приёмки системы; оценку эффектов, получаемых от системы.

6. На этапе 2.4. "Оформление отчёта о выполненной работе" подготавливают и оформляют отчет, содержащий описание выполненных работ на стадии описания и обоснования предлагаемого варианта концепции системы.

7. На этапе 3.1. "Разработка и утверждение технического задания на создание АС" проводят разработку, оформление, согласование и утверждение технического задания на АС и, при необходимости, технических заданий на части АС.

8. На этапе 4.1. "Разработка предварительных проектных решений по системе и её частям" определяются: функции АС; функции подсистем, их цели и эффекты; состав комплексов задач и отдельных задач; концепция информационной базы, её укрупнённая структура; функции системы управления базой данных; состав вычислительной системы; функции и параметры основных программных средств.

9. На этапе 5.1. "Разработка проектных решений по системе и её частям" обеспечивает разработку общих решений по системе и её частям, функционально-алгоритмической структуре системы, по функциям персонала и организационной структуре, по структуре технических средств, по алгоритмам решения задач и применяемым языкам, по организации и ведению информационной базы, системе классификации и кодирования информации, по программному обеспечению.

10. На этапах 4.2. и 5.2. "Разработка документации на АС и её части" проводят разработку, оформление, согласование и утверждение документации в объёме, необходимом для описания полной совокупности принятых проектных решений и достаточном для дальнейшего выполнения работ по созданию АС. Виды документов - по ГОСТ 34.201-89.

11. На этапе 5.3. "Разработка и оформление документации на поставку изделий для комплектования АС и (или) технических требований (технических заданий) на их разработку" проводят: подготовку и оформление документации на поставку изделий для комплектования АС; определение технических требований и составление ТЗ на разработку изделий, не изготовляемых серийно.

12. На этапе 5.4 "Разработка заданий на проектирование в смежных частях проекта объекта автоматизации" осуществляют разработку, оформление, согласование и утверждение заданий на проектирование в смежных частях проекта объекта автоматизации для проведения строительных, электротехнических, санитарно-технических и других подготовительных работ, связанных с созданием АС.

13. На этапе 6.1 "Разработка рабочей документации на систему и её части" осуществляют разработку рабочей документации, содержащей все необходимые и достаточные сведения для обеспечения выполнения работ по вводу АС в действие и её эксплуатации, а также для поддержания уровня эксплуатационных характеристик (качества) системы в соответствии с принятыми проектными решениями, её оформление, согласование и утверждение. Виды документов по ГОСТ 34.201-89.

14. На этапе 6.2 "Разработка или адаптация программ" проводят разработку программ и программных средств системы, выбор, адаптацию и (или) привязку приобретаемых программных средств, разработку программной документации в соответствии с ГОСТ 19.101.

15. На этапе 7.1 "Подготовка объекта автоматизации к вводу АС в действие" проводят работы по организационной подготовке объекта автоматизации к вводу АС в действие, в том числе:

• реализацию проектных решений по организационной структуре АС;
• обеспечение подразделений объекта управления инструктивно-методическими материалами;
• внедрение классификаторов информации.

16. На этапе 7.2 "Подготовка персонала" проводят обучение персонала и проверку его способности обеспечить функционирование АС.

17. На этапе 7.3 "Комплектация АС поставляемыми изделиями (программными и техническими средствами, программно-техническими комплексами, информационными изделиями)" обеспечивают получение комплектующих изделий серийного и единичного производства, материалов и монтажных изделий, проводят входной контроль их качества.

18. На этапе 7.4 "Строительно-монтажные работы" проводят:

• выполнение работ по строительству специализированных зданий (помещений) для размещения технических средств и персонала АС;
• сооружение кабельных каналов;
• выполнение работ по монтажу технических средств и линий связи;
• испытание смонтированных технических средств;
• сдачу технических средств для проведения пусконаладочных работ.

19. На этапе 7.5 "Пусконаладочные работы" проводят:

• автономную наладку технических и программных средств,
• загрузку информации в базу данных и проверку системы её ведения;
• комплексную наладку всех средств системы.

20. На этапе 7.6 "Проведение предварительных испытаний" осуществляют:

• а) испытания АС на работоспособность и соответствие техническому заданию в соответствии с программой и методикой предварительных испытаний;
• б) устранение неисправностей и внесение изменений в документацию на АС, в том числе эксплуатационную в соответствии с протоколом испытаний;
• в) оформление акта о приёмке АС в опытную эксплуатацию.

21. На этапе 7.7 "Проведение опытной эксплуатации" проводят:

• опытную эксплуатацию АС;
• анализ результатов опытной эксплуатации АС;
• доработку (при необходимости) программного обеспечения АС;
• дополнительную наладку (при необходимости) технических средств АС;
• оформление акта о завершении опытной эксплуатации.

22. На этапе 7.8 "Проведение приёмочных испытаний" проводят:

• а) испытания на соответствие техническому заданию в соответствии с программой и методикой приёмочных испытаний;
• б) анализ результатов испытания АС и устранение недостатков, выявленных при испытаниях;
• в) оформление акта о приёмке АС в постоянную эксплуатацию.

23. На этапе 8.1 "Выполнение работ в соответствии с гарантийными обязательствами" осуществляются работы по устранению недостатков, выявленных при эксплуатации АС в течении установленных гарантийных сроков, внесению необходимых изменений в документацию по АС.

24. На этапе 8.2 "Послегарантийное обслуживание" осуществляют работы по:

• а) анализу функционирования системы;
• б) выявлению отклонений фактических эксплуатационных характеристик АС от проектных значений;
• в) установлению причин этих отклонений;
• г) устранению выявленных недостатков и обеспечению стабильности эксплуатационных характеристик АС;
• д) внесению необходимых изменений в документацию на АС.

 

ПРИЛОЖЕНИЕ 2.2
(справочное)