Системный подход ориентирует исследователя на рассмотрение объекта как системы.

Основы системного анализа

Системный подход

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

Системный подход ориентирует исследователя на рассмотрение объекта как системы.

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

Процесс применения системного подхода – тоже система, следовательно, это процесс должен строиться на основе системного подхода

Системный анализ

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

Методология системного анализа опирается на системный подход

Системный анализ используется при необходимости выбора определенных методов, средств, способов действия в рамках решения любой задачи или проблемы

В рамках системного анализа для обеспечения лучшего выбора характеристик системы по сути производится сокращение исходного множества альтернатив

Сокращение множества альтернатив до единственной альтернативы производится с учетом целей системы более высокого уровня

Анализ и синтез системы

Анализ системы – процесс исследования системы, в процессе которого по известным параметрам системы и внешней среды определяются показатели функционирования системы

Синтез системы – процесс исследования системы, при котором по требуемым показателям функционирования системы и имеющимся ограничениям на ресурсы в известных условиях внешней среды (в том числе и меняющихся) требуется определить параметры системы

На практике синтез систем проводится путем многократного анализа системы при изменяющихся наборах параметров и (или) структуры системы. Это приводит к чрезвычайно большим (практически не реализуемым) потребностям в вычислительных мощностях для получения решения задачи синтеза системы.

Основным инструментом анализа и синтеза систем является математическое моделирование

Инструментарий СА

• Строгие формальные методы (математика, вычислительная техника, моделирование)

• Неформальные эвристические методы (экспертные оценки, морфологический анализ, др.)

• Натурные наблюдения и эксперименты

• Практически подтвержденные полезные приемы, рекомендации, советы

Основные этапы исследования систем

• Постановка задачи

– Формирование модели цели системы

– Выбор (формализация) критерия предпочтения

• Разработка математической модели

• Проведение расчетов

• Выработка рекомендаций

Постановка задачи является наиболее важным и наименее формализованным из этапов исследования системы

Наиболее формализованными этапами являются разработка математической модели и проведение расчетов

Процедура исследования системы является рекуррентной – всегда возможен возврат к любому из предыдущих этапов

Постановка задачи исследования системы

Задачи этапа

• Составление (выбор, определение) модели цели системы т.е. списка функциональных требований к системе

• Формирование системы допущений, используемых при исследовании системы

• Формирование множества альтернатив и выявление ограничений этого множества

• Выбор показателей свойств системы, которые должны определяться количественно

• Построение критерия предпочтения

• Формулировка постановки задачи

Особенности процесса постановки задачи

Процесс является сложным и не формализуемым математически. Обусловлен объективными свойствами исследуемой систем и субъективными данными исследователя.

В результате различные исследователи могут формировать различные постановки задачи исследования одной и той же системы (то же может относиться и к другим этапам системного анализа)

Постановка задачи является итеративным процессом

• Обусловлено итеративностью процесса мышления (различные варианты принятия решений, некоторые могут заводить в тупик, что требует возврата)

• Обусловлено итеративностью процесса исследования вследствие появления новой информации из внешней среды и в процессе исследования, что может потребовать пересмотра принятых ранее решений.

Этапы постановки задачи

• Постановка задачи в первоначальном виде: опирается на неполную информацию, часто на интуитивные представления, обычно формулируется не четко и в дальнейшем подвергается существенным изменениям

• Развитие постановки задачи: требует сбора и обработки дополнительной информации, конкретизации цели исследований, целесообразно проводить с содержательной (расширение постановки задачи по горизонтали и вертикали) и организационной (анализ располагаемых ресурсов, определение порядка проведения работ) точек зрения

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

Содержание блоков алгоритма

• Первоначальная постановка задачи – проводится по данным заказчика работ

• Выбор расширенной задачи – содержание указано ранее

• Описание цели системы – опирается на изучение цели вышестоящей системы, должно обеспечить обоснование цели исследуемой системы, возможна корректировка ранее сформулированной цели. Необходимо участие заказчика в выборе цели. Заканчивается описанием цели системы в виде списка функциональных требований к системе

• Описание системы – включает описание состава и структуры системы, перечень основных функций системы и ее компонентов

• Описание внешней среды – описание условий и возможных вариантов взаимодействия системы с внешней средой, характеристик внешней среды, подлежащих учету

• Описание операций системы – формирование логической модели операции по достижению цели и/или поддержанию структуры системы

Содержание блоков алгоритма (продолжение)

• Выбор множества альтернатив – формирование множества допустимых значений управляющих (и управляемых) параметров системы

• Выбор показателей и критерия предпочтения – составление перечня и формализация оцениваемых показателей и критерия, формирование перечня информации, необходимой для расчета показателей и критерия

• Определение объектов моделирования и синтеза – обеспечивает сужение задачи за счет исключения компонентов системы и воздействий внешней среды, слабо влияющих на решение задачи

• Декомпозиция задачи – разделение расширенной задачи на составные части

• Подготовка исходных данных – сбор необходимой информации для решения задачи

• Формулировка постановки решаемой задачи – формализованная запись альтернатив с ограничениями и критерия

Список функциональных требований к системе

• Является моделью цели системы

• Должен учитывать функциональные, технические, конструктивные, технологические, эксплуатационные, экономические, организационные и т.д. требования

• Включает две группы показателей

– Результаты функционирования системы

– Важнейшие свойства и/или параметры системы, обеспечивающие достижение цели

• Формализуется в виде

– qi = qiтреб

– qi ≥ qiтреб (qi ≤ qiтреб)

– qi → min (qi → max)

• Формируется из качественных требований к системе путем их конкретизации

Классификационные шкалы

Простейший вид шкал - определяет различимость любых двух объектов по какому-либо признаку.

Все объекты относятся к одному из классов (обозначению), внутри класса объекты неразличимы (по определяющему признаку)

В рамках классификационной шкалы отношения между состояниями объектов (и их обозначениями) удовлетворяют аксиомам тождества

• Либо А=В, либо А≠В

• Если А=В, то В=А

• Если А=В и В=С, то А=С

(Здесь символ «=» - обозначение эквивалентности, если А, В, С – числа, то данный символ означает равенство)

Порядковые (ранговые) шкалы

Аксиомы упорядоченности:

4. Если A>B, то B<A

5. Если A>B и B>C, то A>C

Интервальные шкалы

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

Вторичная обработка включает арифметические и т.д. действия, в том числе статистическую обработку. При этом среднее значение остается условной величиной, но средний интервал и, тем более, среднеквадратическое отклонение, имеют физический смысл.

Примеры: длина, вес, прочие физические величины

Пример влияния показателя на решение

Альтернатива, если,

Свертка критериев

Исходная задача: Новая задача:

Экспертные оценки

При ограничениях

Управление по KPI

• Задание требуемых значений для всех показателей функционирования системы

• Задача определения цели функционирования системы и значений KPI переносится на уровень руководства системой (более высокий уровень управления)

• Система KPI должна обеспечивать эффективность функционирования системы в целом

• Система KPI должна быть переменной во времени, чтобы отражать изменения условий функционирования системы

• Управление по KPI может быть сведено к случаю перехода к показателю функционирования системы более высокого уровня

Модель системы – формализованное описание логико-математических зависимостей между показателями функционирования (производительности, качества, надежности, стоимости и т.п.) с одной стороны и альтернативами достижения цели и характеристиками системы и внешней среды – с другой стороны

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

Схема моделирования

Адекватность модели

Адекватность модели

• Модель должна служить средством решения задачи

• Адекватность – соответствие целям моделирования и реальному объекту

• Адекватность достигается компромиссом между представительностью (достоверностью) и умеренной сложностью (работоспособностью модели)

• Используется принцип существенности: используются только факторы, существенные по отношению к цели моделирования

• Выбор существенных факторов осуществляется по: литературе, качественному анализу реальности, эвристическим методам, суждениям исследователя, расчетам (факторный анализ)

Работоспособность модели

• Работоспособность модели – возможность получения результата в условиях располагаемых ресурсов (программных средств, вычислительной техники, затрат, времени, квалификации и количества персонала)

• Работоспособность достигается быстродействием, устойчивостью и модифицируемостью

• Быстродействие – свойство обеспечить получение результатов в требуемое время

• Устойчивость – способность работать в широком диапазоне изменения входных параметров

• Модифицируемость – способность допускать изменения (ограниченные) в процессе развития модели

Классификация моделей по практическому применению

Имитационные модели

Проведение расчетов

Выполнение работ данного этапа (практически всегда) требует проведения компьютерных вычислений

Чем сложнее система, тем меньше шансов, что для нее будет применимо стандартное программное обеспечение. На практике даже наиболее продвинутые комплексы прикладных программ, настраиваемые на особенности функционирования системы, не обеспечивают проведения эффективных расчетов

Применение специально разработанных методов расчета и поиска оптимальных характеристик системы обычно позволяет повысить эффективность системы на 5-15%

Проблемы принятия решений

При принятии решения руководителем обычно возникают следующие проблемы:

• На практике часто приходится иметь дело с многокритериальными задачами

• Наличие показателей функционирования системы имеющих разную измеримость

• Недостаток времени на получение необходимых исходных данных и/или разработку моделей

• Отсутствие (обычно некоторой части) информации о показателях функционирования системы и/или характеристиках внешней среды

• Влияние на процесс и результат решения субъективных мнений и предпочтений руководителя (ЛПР – лица, принимающего решения)

БЛОК 07 – описание систем

Модель – убрать здесь

Эволюция понятия модели:

• Материальные объекты

• Чертежи, рисунки, карты, т.п.

• Математические (абстрактные) модели

• Любые знания и представления о реальном мире

Примеры функционального описания системы

Таблица 1

Таблица 2

Графы

Пример дерева функций системы

Сверху вниз

Снизу вверх

Состав системы

Состав системы – перечень подсистем (компонентов, элементов), из которых состоит система

Элементы – неделимы

Выделение подсистем определяется двумя способами:

Классификация элементов

Структурные связи

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

Выделяют связи

Информационные

Энергетические

Вещественные

Характеристики связей

Сильные – слабые

Прямые и обратные связи

Обратные связи — основа саморегулирования и развития систем, приспособления их к изменяющимся условиям существования, в основном, выполняют осведомляющие функции, отражая изменение состояния системы в результате управляющего воздействия на нее и служат для управления процессами, наиболее распространены информационные обратные связи.

Система с обратной связью

Функции обратной связи

• Противодействие тому, что делает сама система, когда она выходит за установленные пределы функционирования

• Компенсация возмущений и поддержание состояния устойчивого равновесия системы или движения по заранее заданной траектории в пространстве состояний системы;

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

• Выработка управляющих воздействий на объект управления по плохо формализуемому закону.

Примеры не иерархических структур

Лидирующие подсистемы

Лидирующей называется подсистема, удовлетворяющая следующим требованиям:

• подсистема не имеет детерминированного взаимодействия ни с одной подсистемой;

• подсистема является управляющей (при непосредственном или опосредованном взаимодействии) по отношению к части (наибольшему числу подсистем);

• подсистема либо не является управляемой (подчиненной), либо управляется наименьшим (по сравнению с другими) числом подсистем.

Где

S={S_i} — множество элементов и их свойств, i=1,…,N;

К — композиция

(Все множества считаются конечными)

Пример структурной схемы системы

Аспекты информации

Ценность информации

Основные формы информации

• осведомляющая — движущаяся преимущественно от объектов управления к соответствующим узлам управления (как правило, осведомляющая информация передается по каналам обратной связи);

• управляющая — движется в обратном направлении и содержит указания, директивы и т.п.;

• преобразующая — определяет закономерности поведения узла управления и алгоритмы функционирования его отдельных элементов.

Описание системы

Соответствие свойств и переменных, описывающих систему:

D: S_i = [S_i,j, j={1,N}] → X_i = [X_i,j,j={1,N}],

где S_i — i-ое свойство, X_i — переменная

Формальное представление системы в виде множества (одно из существующих определений):

S = (X, T, R, Z),

T — множество параметров

Z — цель исследований

Множество состояний системы

C={X1×X2×…×XN}

Функция ограничений

f₀ = 1, если с ⊂ C^,

f₀ = 0, если с П _in; C^,

где с — вектор состояния системы, C^ — подмножество полного множества состояний

f₀: C^ → Т, Т → C^

Для стохастической системы

f₀: |С| → [0,1]

Мера нечеткости (энтропия)

H = −∑p(C_i)log₂(C_i)

Если p(C_i) = 1, то Н = 0

Если p(C_i) = 1/|C|, то H = log₂|C|.

0 ≤ Н ≤ log₂|C|

Типы сложности систем

• Структурная (организационная)

• Динамическая (временная)

• Информационная (информационно-логическая, инфологическая)

• Вычислительная (реализации, исследования)

• Алгоритмическая (конструктивная)

• Развития (эволюции, самоорганизации)

Упрощение систем

Общий вид задачи упрощения:

Для системы заданной на множестве переменных X с полным множеством состояний С необходимо найти вариант упрощенной системы на подмножестве переменных X' ⊂ X или подмножестве состояний C' ⊂ C

Основные виды упрощения:

• сокращение множества переменных

• объединение состояний системы в классы эквивалентности

Структурирование системы

Информационная система

Информационная система - система, в которой ее элементы, цель, ресурсы и структура рассматриваются, в основном, на информационном уровне (сохраняются и другие уровни рассмотрения, но такое рассмотрение играет вспомогательную роль)

Общие понятия управления

Существование системы протекает во времени под влиянием внешних воздействий (факторов) согласно внутренним свойствам системы

Цикл управления

• сбор информации о системе

• обработка и анализ информации

• получение информации о траектории

• выявление управляющих параметров

• определение ресурсов для управления

• управление траекторией системы

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

История развития ТАУ

Регуляторы хода часов (15-16 века)

Роль ТАУ сейчас

ТАУ используется при проектировании практически всех технических устройств и систем, но значение теории автоматического управления в настоящее время переросло рамки технических систем. Большое внимание уделяется изучению процессов саморегулирования в живых организмах и в биологических системах. Динамически управляемые процессы характерны также для различных организационно-технических и социально-экономических систем, при этом, по мере глобализации и информатизации экономических процессов и развития глобальных информационно-коммуникационных систем происходит расширение применения основных положений и результатов ТАУ.

Основные понятия и определения теории автоматического управления

Классификация операций
(Содержание проблемы автоматического управления)

Замена человеческого труда
(Содержание проблемы автоматического управления)

Замена человеческого труда в рабочих операциях – механизация, используется:

• При выполнении работ, требующих значительных физических усилий

• При работах во вредных условиях

• Для сокращения монотонных операций

Замена человеческого труда в операциях управления – автоматизация, используется:

• При выполнении операций, требующих большого количества расчетов

• При недостатке времени для принятия решений

• В автономно действующих устройствах и системах

• В сложных устройствах и системах для управления отдельными процессами

Степени автоматизации

Автоматизированная (частично автоматическая) система – система, в которой часть операций выполняется автоматическими устройствами, а другая часть (обычно наиболее ответственная) выполняется человеком (людьми)

Состав системы управления
(Содержание проблемы автоматического управления)

Виды операций управления

Вид оператора А

Алгоритм функционирования

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

Принципы управления

Фундаментальные принципы управления, определяющие каким образом осуществляется увязка алгоритмов функционирования и управления с фактическим функционированием или причинами, вызывающими отклонение координат системы от требуемых значений:

РАЗОМКНУТОЕ УПРАВЛЕНИЕ

КОМПЕНСАЦИЯ

ОБРАТНАЯ СВЯЗЬ

Компенсационные системы

Замкнутые системы

Разделение управления

Программа управления Х0(t)=аt+b

Релейный

Релейный с гестерезисом

Пропорционально-релейный

Импульсный

Экстремальный

Системы стабилизации

Программное управление

Может быть построен датчик программы по заданному алгоритму функционирования. Программное управление можно осуществлять по любому из фундаментальных принципов управления или по их комбинации (приведенные выше схемы)

Следящие системы

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

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

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

Оптимальное управление

Основная область применения – системы, эффективность которых зависит от всего хода процесса (интегральные затраты, суммарная прибыль, т.п.). Требуют значительного информационного обеспечения и выработки управления в соответствии с оптимизационными алгоритмами, которые реализуются с помощью вычислительной техники.

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

Состав адаптивной системы

Измерительный блок

Вычислительный блок

Блок управления

Блок настройки параметров

Адаптивное управление

Самонастраивающиеся системы

Беспоисковые СНС

Компенсационные СНС на основе принципа инвариантности

Предусматривается компенсация возмущающих воздействий на регулируемые координаты от параметрических и внешних возмущений. В этих условиях система (показатель качества) становится инвариантной к указанным воздействиям.

М-Э – модель эталон

УС – устройство сравнения

Входной сигнал g(е) подается на вход системы и на модель-эталон. На выходе модели-эталона формируется выходной сигнал «как должно быть». Полученный сигнал сравнивается с реальным выходом системы в УС. Там же вырабатывается управляющий сигнал для корректировки параметров регулятора системы управления. При этом необходимо получить (синтезировать) законы самонастройки, что бывает затруднительно (управление в виде синтеза)

В некоторых системах возможно не получать импульсную функцию, а поддерживать ее в заданном состоянии, однако данный подход возможен не всегда. При этом используется аппарат построения фазочастотных характеристик системы.

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

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

Обучающиеся системы

Цель обучения: построение поверхности (поверхностей), разделяющей предъявляемые точки в пространстве состояний системы на заданное (иногда определяемое) количество классов: цель/не цель, рост продаж/случайный всплеск и т.п. Разделение на два класса обычно носит название задачи идентификации.

Проблемы классификации

Обучение с поощрением

Классифицирующему автомату предъявляются точки, для которых известна их принадлежность какому-либо классу, данная информация также сообщается автомату. После определенного цикла обучения на примерах автомат строит поверхность, разделяющую пространство состояний системы на разные классы (разделяющую поверхность). Затем автомат может самостоятельно определять для новых точек их принадлежность какому-либо классу.

Примеры алгоритмов обучения с поощрением:

Метод секущих плоскостей

Метод потенциальных функций

Метод секущих плоскостей

Точки вводятся в автомат последовательно: вначале 2 точки, затем точки добавляются по одной. По первым двум точкам строится произвольная плоскость, которая их разделяет. При добавлении новой точки, если нет противоречия, то набор плоскостей сохраняется. Если возникает противоречие, точка отнесена не к тому классу, вводятся новая плоскость, чтобы снять противоречие. При увеличении количества плоскостей области сужается и вероятность возникновения противоречия уменьшается. По завершению обучения удаляются лишние элементы гиперплоскостей и строится единая (кусочно-линейная) поверхность, по которой в дальнейшем разделяются точки.

Метод потенциальных функций

Считается, что классы могут быть отделены друг от друга (обычно метод применяется для двух разделимых классов). Метод позволяет при определенных условиях за конечное число шагов построить границу, отделяющую классы. Граница ищется в виде функции:

Ф(х)=∑сi ψi(x), i=1,…,∞

ψi(x) – система функций разложения

∑(сi /λi)↑2<∞; ∑λi↑2<∞; i=1,…,∞

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

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

Самообучающиеся системы

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

Математические модели

БЛОК 13

Делимые и неделимые

Метод ветвей и границ.

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

Метод максимального элемента
(метод последовательных назначений)

Вогнутые функции

Выпукло-вогнутые функции

Обобщения моделей метода МЭ

Неаддитивный критерий

Решение квазиоптимальное.

Для того, чтобы траектория системы в пространстве ее состояний была оптимальна, необходимо и достаточно, чтобы она была оптимальна, начиная с любой своей точки, независимо от того как система оказалась в этой точке траектории.

Суть метода – поэтапная минимизация (максимизация) функции многих переменных согласно схеме:

Постановка задачи:

Определить вектор Х^*={x_i^*}, i=1…n, так чтобы

В:

i=1…n, -целые числа.

Аналогично:

По методу математической индукции (для общего вида):

При k=n: (**)

Использование приведенных рекуррентных соотношений для i=n,n-1,…,1 с начальными условиями(**) дает оптимальное решение задачи.

Сетевые модели

• Транспортная задача

• Задача о минимальном покрытии

• Задача о кратчайшем маршруте

• Задача о максимальном потоке

• Задача о формировании сети минимальной стоимости

• Сетевое планирование

• Теория расписаний

Транспортная задача

Имеется n складов А₁, А₂, …, А_n, и m потребителей В₁, В₂, …, В_m.