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

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

В зависимости от условий задачи распределения ресурсов делятся на три класса.

1. Заданы и работы, и ресурсы. Требуется распределить ресурсы между работами таким образом, чтобы максимизировать некоторую меру эффективности (скажем, прибыль) или минимизировать ожидае­мые затраты (издержки производства). Например, предприятию уста­новлено производственное задание в рамках оговоренного срока. Известны мощности предприятия. При изготовлении продукции изделия проходят обработку на разных станках. Естественным яв-ся ограничение — одновременно на одном станке может обрабатываться только одна единица продукции. Мощности предприятия ограниченны и не позволяют для каждого изделия использовать наилучшую технологию. Требуется выбрать такие способы производства для каждой единицы продукции, чтобы выполнить задание с минимальными затратами.

2. Заданы только наличные ресурсы. Требуется определить, какой состав работ можно выполнить с учетом этих ресурсов, чтобы обеспечить максимум некоторой меры эффективности. Приведем пример. Имеется предприятие с определенными производственными мощностями. Требуется произвести планирование ассортимента и объема выпуска продукции, которые позволили бы максимизировать доход предприятия.

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

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

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

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

.

Некоторым промежуточным вариантом между крайне пессимистическими вариантами и крайне оптимистическими яв-ся критерии пессимизма-оптимизма (критерий Гурвица):

Где 0≤β≤- «коэффициент пессимизма» или, если хотите, «коэффициент оптимизма». При β=1 оценка превращается в минимальную, а при β=0 она максимально оптимистична. Необходимо подчеркнуть, что определение значения β – это прерогатива руководителя, и с этой точки зрения, оценка чрезвычайно субъективна. А также

где a_i – коэффициенты важности критериев (весовые коэффициенты), определяемые в большинстве случае субъективно; ; с – некоторое фиксированное значение критерия f(x_i), например, некоторое его усредненное значение; f(x_i)- частный i-й показатель (критерий) эффективности; f_j(x_i) – частный i-й показатель (критерий) эффективности j-й альтернативы (проекта).

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

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

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

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

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

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

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

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

Одной из областей приложения системного анализа яв-ся область выбора инвестиционного проекта. Как показывает опыт, реализация большинства методов анализа и отбора инвестиционных проектов на практике так или иначе связана с использованием основных показателей экономической эффективности: чистый дисконтированный доход (Net Present Value – NPV), внутренняя норма рентабельности дохода (Internal Rate of Return –IRR), срок окупаемости проекта (Pay Back Period – РВP), индекс рентабельности инвестиций (Profitability Index –PI). Свертка этих показателей, выделение главного критерия, построение векторов предпочтений, использование различных правил отбора и т.д. предполагают, что их значения известны или же найти их не представляет труда. Однако, как было показано выше - это не всегда так, и возникают задачи анализа и представления исходных данных проекта и как следствие - выбор руководителем используемых математических моделей детального моделирования денежных потоков проекта. Эта ситуация при большом числе рассматриваемых инвестиционных проектов требует больших затрат ресурсов и времени.

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

где: δ - коэффициент дисконтирования; r - простая норма прибыли; d - норма амортизации (обратно пропорциональная сроку службы); t_c — длительность инвестиционной фазы проекта; Δt - время выхода проекта на номинальную мощность.

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

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

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

16. Дайте определение и приведите описание модели онтологического анализа.

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

Онтологический анализ – аналитическая работа с целью определения и объединения релевантных информационно-логических и функциональных аспектов исследуемой системы в соответствующей содержательной онтологии [Гаврилова]. Онтологический анализ направлен на исследование и интерпретацию системных связей в сложных предметных областях с применением методов и средств компьютерного моделирования.

Онтологический анализ используется в системах искусственного интеллекта, так как необходим для исследования плохо структурированных предметных областей, какой яв-ся, например, область управления сложными системами в проблемных ситуациях. Современное определение термина “онтология” в теории искусственного интеллекта неоднозначно; для практического использования наиболее подходящим яв-ся определение онтологии как знаний, формально представленных на базе концептуализации. Концептуализация предполагает описание множества объектов и понятий, знаний о них и связей между ними. Для структурирования знаний о предметной области предложено использовать три основные категории [26]:

· статическая онтология – в нее входят сущности предметной области, их свойства и отношения;

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

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

Под формальной моделью MO онтологической системы [3] понимается триада вида:

M ^O = < O ^meta, {O ^app}, Inf ^F>,

где O ^meta – онтология верхнего уровня (метаонтология);

{O ^app} – множество предметных онтологий и онтологий задач предметной области;

Inf ^F – модель машины вывода, ассоциированной с онтологической системой M ^O.

Формально предметная онтология состоит из множества терминов предметной области, организованных в таксономию, их определений и атрибутов, а также связанных с ними аксиом и правил вывода [52], то есть модель предметной онтологии - это упорядоченная тройка вида:

O ^app = <T,R,F>,

где T – конечное множество концептов (понятий, терминов) предметной области, которую представляет онтология O ^app;

R – конечное множество отношений между концептами (понятиями, терминами) заданной предметной области;

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

Естественным ограничением, накладываемым на множество T, яв-ся его конечность и не пустота. Множества R и F также должны быть конечными, а граничные случаи, связанные с их пустотой, яв-ся следующие.

При R = 0 и F = 0 онтология O app трансформируется в словарь (V):

O app = V = <T,{},{}>.

При R ¹ 0 и F = 0 онтология представляет собой тезаурус (Th), состоящий из множества концептов и множества отношений, отражающих специфику конкретной предметной области .

O app = Th = <T,R,{}>.

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

Тезаурус.Термин тезаурус(от греч. thesauros - сокровищница, богатство, клад, запас и т. п.) в общем случае характеризует «совокупность научных знаний о явлениях и законах внешнего мира и духовной деятельности людей, накопленную всем человеческим обществом» [Д3].

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

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

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

Правила (Gl, G2) формирования смысловыражающих элементов второго и третьего уровней в тезаурус не входят, в тезаурусе определяется только вид и наименование уровня, характер и вид смысловыражающих элементов.Иногда вместо термина смысловыражающие элементы используется термин синтаксические единицы тезауруса. На наш взгляд, это менее удачный термин, так как при формировании элементов нового множества смысловыражающих элементов каждого последующего уровня (при образовании слов из букв, фраз и предложений из слов, и т. д.) у элементов вновь образованного множества появ-ся новый смысл, т. е. как бы прояв-ся закономерность целостности, и это хорошо отражает термин «смысловыражающий элемент».В таком толковании понятие тезауруса можно конструктивно использовать при создании искусственных языков - языков моделирования, автоматизации проектирования, информационно-поисковых языков. Оно позволяет охарактеризовать язык с точки зрения уровней обобщения, ввести правила их использования при индексировании информации.

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

Сущностями метаонтологии O^meta яв-ся такие понятия, как «объект», «атрибут», «значение», «отношение» и т.п. В качестве базового модуля онтологии используется модель метаонтологии. Онтология высшего порядка, в общем случае, яв-ся графом, порожденным включенными в нее отношениями, такими как is_a (быть элементом класса), part_of (являться частью), connected_with (быть связанным с), "роль-событие" и другими отношениями.

Из приведенного определения онтологической системы следует, что разработку онтологии следует начинать с простейшей понятийной модели - словаря терминов предметной области, совместно используемого для упрощения коммуникации, общения, запоминания и представления. Словарь V разрабатывается на этапе объектного моделирования предметной области, при этом используются словари, уже существующие в данной области. Разработанный словарь служит материалом для представления лингвистической компоненты системы поддержки принятия решений. Для более полного и системного лингвистического описания предметной области нужен тезаурус Th, разработка которого потребует создания специальных методов и алгоритмов анализа и моделирования. Предметом дальнейших исследований яв-ся определение множества функций интерпретации F, заданных на концептах и отношениях онтологии предметной области O app. В большинстве предметных областей управления сложными системами (авиация, энергетика, вычислительные сети) существует значительное количество текстовых документов, содержащих описания конкретных критических ситуаций, устанавливающих регламент и стандарты управления объектами в критических ситуациях. Однако использование только текстовой базы предметной области для разработки тезауруса привносит инородные контекстуальные связи, не относящиеся к рассматриваемой проблеме. Тем не менее, при разработке баз знаний в качестве источников знаний чаще всего рассматриваются знания, содержащиеся в текстах, относящихся к предметной области, и знания экспертов, выявляемые инженерами знаний в процессе диалогов. Предлагается использовать третий источник знаний –визуальную модель процесса, разработанную с использованием UML, в качестве средства, аккумулирующего знания экспертов, описания процесса управления и опыт проектирования информационных систем. Следовательно, предметно – ориентированный тезаурус системы поддержки принятия решений должен объединять тезаурус экспертов в данной предметной области, тезаурус, формируемый на основе лингвистического анализа методических, нормативных, регламентирующих документов, а также тезаурус, формируемый по результатам моделирования процессов управления в проблемных ситуациях.

17.Дайте определение и приведите описание модели онтологии

Модель онтологического анализа есть модель машины вывода Inf F, ассоциированной с онтологической системой. На машину вывода возлагаются задачи активации сущностей и отношений, описывающих конкретную задачу, то есть организация динамической компоненты базы знаний.Разработанный подход предусматривает создание модели онтологии в виде совокупности модулей, где каждый модуль описывает терминологию некоторого раздела предметной области. Таким образом, в процессе структуризации стратегического управления предприятием, включающая онтологию делового процесса, представляется в виде иерархической системы (рис. 5.2).

Рис. 5.2.. Иерархия уровней онтологии стратегического управления предприятием

Разрабатываемая онтология состоит из:

• классов ПрО (classes);

• экземпляров (individuals, instances);

• отношений между классами и экземплярами (properties, slots). Основные типы отношений в разрабатываемой онтологии: «часть-целое» (part-of), «экземпляр класса» (instance of), «иерархия» (is-a));

• ограничений и условий принадлежности, относящихся к классам и экземплярам (axioms and facts).

Методика разработки онтологии в силу ее сложности специфична для каждой задачи. В соответствии с этим и происходит разработка предметной онтологии. Существуют основные этапы, стандартные для разработки любой онтологии, а методы и средства, которые используются, выбираются в работе с учетом специфики предметной области и анализа существующих в этой области разработок. Этап Iвключает разработку концептуальной структуры онтологии и предварительную идентификацию концептов, таксономии, связей, функций и аксиом. Этап IIвключает формализацию знаний и концептуально структурирует экземпляры классов. Подразделяется на следующие под этапы: формализация онтологического языка: представление объектов в форме классов и атрибутов, представление свойств и отношений; программная реализация интерфейса пользователя для доступа к онтологии.

Потенциальными пользователями онтологии яв-ся управляющие (ЛПР), аналитики, технологи ГТМ, специалисты в области информационных технологий и инженерии знаний. Были проанализированы существующие за рубежом методики разработки онтологии и выявлено, что может являться исходными данными для этого:

· предметный тезаурус; ключевые слова от экспертов;

· документы из Internet (с автоматической разметкой);

· словари (форматы XML или SGML) - полуструктурированные исходные данные;

· web- документы, составленные на естественном языке;

· тексты предметной области; аннотированные тексты; концепты-примитивы от экспертов;

· аннотированные документы;

· управляемый словарь;

· схема базы данных;

· запросы пользователя.

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

18.Рассмотрите методику разработки онтологии

Рассмотрим процесс разработки онтологии на примере онтологии в стратегическом управлении.

В качестве редактора разрабатываемой онтологии было выбрано средство построения онтологии Stanford’s Protégé 3.1.1 с OWL – дополнением для кодирования онтологии и базы знаний. Protégé располагает интуитивно понятным интерфейсом для построения иерархии классов, а также позволяет определить характеристики (свойства) классов данных и объектов и отношения между ними. Преимущества редактора онтологий Protégé 3.1.

· Графическое представление. Позволяет с помощью средств визуализации создавать, редактировать, отлаживать онтологии.

· Проверка полноты знаний и степени логической корректности и непротиворечивости ссылок в онтологии производится автоматически.

· Предоставляется возможность разработки онтологии параллельно несколькими пользователями.

· Функция слияния. Осуществляет поддержку при объединении разных онтологии в одну и возможность их сравнения.

· Лексическая поддержка. Поддержка лексических ссылок онтологических элементов (например, синонимов) и обработки лексического содержания (например, поиск/ фильтрация онтологических терминов).

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

· Соответствие требованиям стандартов Semantic Web [14].

На рис. 5.3 показан фрагмент онтологии стратегического управления, разработанный с использованием Protege 3.1. Онтология, разработанная в Protege 3.1, может быть экспортирована в различные форматы, например RDF(S), OWL, XML Schema в соответствии со стековой архитектурой Semantic Web (рис.4.1). Это позволяет широко использовать онтологию как пользователями, так и делает её машинно-читаемой и совместимой с другими онтологиями и программами.

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

Другим приложением онтологии яв-ся ее использование в системах информационного поиска.

Для представления категорий в логике первого порядка могут применяться два основных способа: представление с помощью предикатов или с помощью объектов. Категории служат для организации и упрощения базы знаний с помощью наследования. Например, если известно, что все экземпляры категории «Еда» съедобны, и сформулировано утверждение, что класс «Фрукты» - это подкласс класса «Еда», а яблоки – подкласс класса «Фрукты», то становится известным, что каждое яблоко съедобно. Отдельные яблоки наследуют свойство съедобности в силу своей принадлежности к категории «Еда».

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

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

1. Любой объект – элемент некоторой категории: BB₂ Basketballs

2. Любая категория – подкласс другой категории, например:Basketballs

3. Все элементы категории имеют некоторые свойства, например

X Basketballs→Round (X)

4. Элементы категории могут быть распознаны по некоторым свойствам, например:

Orange(X) ∩ Round (X) ∩Diameter (X)=”9.5” ∩X Balls→ X Basketballs

5. Вся категория в целом имеет некоторые свойства, например:

Dogs Domesticalspecies

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

19.Проанализируйте процесс построения моделей системы

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

Понятие модели системы играет важную роль в проведении системных исследований любой направленности.

Модель-это искусственно создаваемый образа конкретного объекта, процесс или явления, в конечном счете, любой системы

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

Модель-это отобращение реальной системы , имеющее определенное объективное соответствие ей и позволяющее прогнозировать и исследовать ее функциональные характеристики, определяющие взаимодействие системы с внешней средой

При составлении модели отражают отдельные стороны функционирования системы, т.е. то специфичное, что направлено на решение поставленной целевой установки общей задачи системного анализа. Сходство двух объектов с точки зрения выполнения каких-либо функций, целей или задач позволяет утверждать, что между ними существует отношение оригинала и модели. В задачах системного исследования первоочередной интерес представляет сходство поведения модели и объекта, выраженное на каком-либо формальном языке и изучаемое путем преобразований соответствующих формул или высказываний. Так приходим к понятию математической модели, являющейся основой аналитических исследований и имитационных экспериментов на ЭВМ. Математические модели можно классифицировать таким же образом, как это было проделано в случае классификации систем. Остановимся на описании классов, имеющих принципиально различный характер в подходе к построению моделей, а именно, охарактеризуем следующие типы моделей: детерминированные, вероятностные и игровые модели.

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

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

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

20.Дайте определение и сформулируйте поставку задач математического программирования

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

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

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

Мат/ое программирование подразделяется на линейное, целочисленное, нелинейное, динамическое программирование. Рассмотрим нек/ые постановки задач, методы и алгоритмы их решения.

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

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

Класс задач оптимизации, в к/ых область определения переменных состоит из отдельных изолированных точек, составляет предмет изучения дискретного программирования.

Широкий класс нелинейных и дискретных задач может решаться с использованием идеи рекуррентного подхода (методов типа мат/ой индукции), являющихся основой динамического программирования, идея к/ого первоначально была предложена Р. Беллманом. Для решения задач оптимизации со случайными параметрами разработано стохастическое программирование .К мат/ому программированию относят также бесконечномерное программирование, в рамках к/ого предложены методы решения экстремальных задач с бесконечным числом переменных (например, такие, в к/ых набором переменных яв-ся ф/и или набор ф/й) и минимизируется (максимизируется) ф/онал. Развиты также методы решения задач оптимизации, в к/ых переменная принимает только два значения «истинно» - «ложно» или «да» — «нет». Такие методы относят к булевому программированию .

23.Дайте общую математическую формулировку задачи линейного программ-ния

Задачи линейного программирования относятся к категории оптимизационных. Они находят широкое применение в различных областях практической деятельности: при организации работы транспортных систем, в управлении промышленными предприятиями, при составлении проектов сложных систем. Многие распространенные классы задач системного анализа, в частности, задачи оптимального планирования, распределения различных ресурсов, управления запасами, календарного планирования, межотраслевого баланса укладываются в рамки моделей линейного программирования. Несмотря на различные области приложения, данные задачи имеют единую постановку: найти значения переменных x₁, …, x_n, доставляющие оптимум заданной линейной формы z=c₁x₁ + c₂x₂+… + c_nx_n при выполнении системы ограничений, представляющих собой также линейные формы.

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

Задача линейного программирования формулируется так:

Определить максимум линейной формы

F(x₁,…,x_n )=max(c₁x₁+…+c_nx_n) (8.3)

при условии, что точка (х₁, х₂,..., х_n) принадлежит некоторому множеству D, которое определяется системой линейных неравенств

(8.4)

Любое множество значений (х₁*, х₂*,..., х_n*), которое удовлетворяет системе неравенств (8.4) задачи линейного программирования, яв-ся допустимым решением данной задачи. Если при этом выполняется неравенство

c₁х₁^o+ c₂ х₂^o+..+ c_n х_n^o ≥ c₁х₁+ c₂ х₂+..+ c_n х_n

для всего множества значений x₁, х₂,..., х_n, то значение х₁^o..х_n^o яв-ся оптимальным решением задачи линейного программирования.

Задачу линейного программирования удобно представлять в векторной форме, тогда она будет выглядеть следующим образом: найти max F(x) = max (c^Tx) при условии АХ ≤Ро; Х≥0,

где с = (с₁,с₂,..., с_n) представляет собой n-мерный вектор, составленный из коэффициентов целевой функции, причем с^T-транспонированная вектор-строка; х = (х₁, х₂,..., х_п) - п-мерный вектор переменных решений;

- m-мерный вектор свободных членов ограничений;

Матрица А размером (m×n) - матрица, составленная из коэффициентов всех линейных ограничений:

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

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

F(x) = c_lx₁+c₂x₂+... + c_nx_n при ограничениях

a₁₁х₁ +а₁₂х₂ +...+а_1пх_n=b₁

а₂₁х₁ +а₂₂х₂ +...+а_2пх_n=b_1…

…

а_m1х₁ +а_m2х₂ +...+а_mпх_n=b₁

x_t,x₂,...,x_n>0.

где с_[,с₂,...,с_п - коэффициенты целевой функции, a_tJ, i = \, 2,...,n,j = 1, 2,...,m -коэффициенты системы ограничений, а b₁,b_г,...,b_n - свободные члены, которые считаются неотрицательными.

Вектор X = (xi, х₂,..., xj, удовлетворяющий ограничениям задачи ЛП, называется допустимым решениемили планом.Допустимый план X* =(xl,x'₂,...,x'_n), при котором целевая функция задачи ЛП принимает максимальное (минимальное) значение, на­зывается оптимальным планом.

Иными словами, каноническая задача линейного программирования (ЛП) состоит в нахождении среди всех решений выписанной выше системы линейных уравнений такого ее неотрицательного решения, на котором достигает своего минимального (максимального) значения линейная целевая функция z от и переменных.В задаче линейного программирования общего вида вместо некоторых (всех) равенств в ограничениях записаны нестрогие неравенства в ту или другую сторону; при этом усло­вие неотрицательности переменных может отсутствовать для части или же для всех переменных. Известно, что решение любой задачи линейного программирования может быть сведено к решению канонической задачи, представляемой в форме (1) или (4).Линейное программирование (ЛП) первоначально развивалось как направление, разрабатывающее новые подходы к решению задач минимизации выпуклых функций на выпуклом множестве (см. выпуклое программирование). Понятие целевой функции , удобное для приложений, сформировалось позднее.

Наиболее простым и распространенным методом решения канонической задачи линейного программирования до сих пор яв-ся симплекс-метод, предложенный в 40-е годы прошлого века Дж. Данцигом. Геометрически идею симплекс-метода в упрощенной форме можно выразить следующим образом. Допустимым множеством в задаче линейного программирования яв-ся некоторое многогранное множество и-мерного векторного пространства (в частном случае n = 2 - это выпуклый и не обязательно ограниченный многоугольник). Работа симплекс-метода начинается с некоторой начальной вершины (начального опорного плана) многогранного множества. Специальным образом выясняется, нет ли среди соседних вершин такой, в которой значение целевой функции лучше? Если такая вершина находится, то она и принимается за следующее приближение. После этого вновь исследуются соседние вершины для полученного приближения и т. д. до тех пор, пока не будет получена вершина, среди соседних вершин которой не существует вершины с лучшим значением целевой функции. Такая вершина яв-ся оптимальной. Она соответствует оптимальной точке (оптимальному решению) задачи линейного программирования.В настоящее время разработан широкий круг различных численных методов решения задач линейного профаммирования, каждый из которых учитывает ту или иную специфическую особенность имеющейся задачи линейного профаммирования.

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

24.Рассмотрите пример графического решения задачи линейного программирования

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

Постановка данной задачи выглядит следующим образом.

Имеется множество переменных X = (x₁, х₂,..., х_n). Целевая функция линейно зависит от управляемых параметров:

(8.1)

Имеются ограничения, которые представляют собой линейные формы

где . (8.2)

Графическое решение задачи приведено на рисунке 8.1.

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

Существует два крайних положения линии уровня, когда она «касается» допустимого множества. Этим двум положениям в данном случае соответствуют две точки «касания» -начало координат (0, 0) и точка (9, 13). Первая из этих точек - точка минимума, а вторая - максимума данной функции F вида (1) на допустимом множестве (2).

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

25.Рассмотрите пример решения задачи линейного программирования симплекс-методом

Рассмотрим задачу линейного программирования в следующем виде: найти максимум линейной формы 4х₁ + 3х₂ при ограничениях

x₁ ≤;4000, х₂ ≤;6000, х₁ +2/3х₂≤6000, х₁,х2 > 0.

Каноническая форма задачи линейного программирования будет иметь вид

4x₁ + 3x₂ + 0x₃ + 0x₄ + 0x₅ → max;

1х₁ + 0х ₂ + 1х₃ + 0x₄ + 0x₅, = 4000; 0х₁ + 1х ₂ + 0х₃ + 1x₄ + 0x₅, = 6000;

1х₁ + 2/3х₂ + 0х₃ + 0x₄ + 1x₅ = 6000; 1х₁+2/3 х₂+ 0х₃ + 0x₄ + 1x₅ =6000.

Составим исходную симплекс-таблицу (табл. 10.2).

Таблица 10.2

Поскольку -4 < -3 < 0, то в качестве направляющего выбираем первый столбец. Составив отношение вида , определяем направляющую строку. Для этого находим минимальное отношение

min Следовательно, направляющая строка - первая, направляющий элемент — а₁₁=1- Применив первый шаг симплексного преобразования, получим новую таблицу (табл. 10.3).

Таблица 10.3

На данном этапе в качестве направляющего столбца выбираем второй, направляющая строка - третья, т.к. 2000/(2/3)<6000/1<4000/1 Применим следующий шаг симплексного преобразования. В результате получим

Табл. 10.4.

Так как а₀₃ = -1/2 < 0, то направляющий столбец А₃ направляющая строка- вторая, направляющий элемент а₂₃=3/2 • Выполним очередной шаг преобразования, получим еще одну таблицу (табл. 10.5).

Поскольку в индексной строке все элементы положительны, это означает, что найдено оптимальное решение х₁₀= 2000, х₂₀ = 6000, х₃₀ = 2000. Искомое значение целевой функции равно 4 х₁ + Зх₂= 26000.

Алгоритм симплекс-метода сводится к следующему.

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

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

3. На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент.

4. Если имеется несколько одинаковых по величине симплекс-отношений, то выбирают любое из них. То же самое относится к положительным элементам последней строки симплекс-таблицы.

5. После нахождения разрешающего элемента переходят к следующей таблице. Неизвестные переменные, соответствующие разрешающей строке и столбцу, меняют местами. При этом базисная переменная становится свободной переменной и наоборот. Симплекс-таблица преобразована следующим образом (табл. 10.4):

17. Элемент табл. 10.4, соответствующий разрешающему элементу табл. 10.3, равен обратной величине разрешающего элемента.

7. Элементы строки табл. 10.4, соответствующие элементам разрешающей строки табл. 10.3, получаются путем деления соответствующих элементов табл. 10.3 на разрешающий элемент,

8. Элементы столбца табл. 10.4, соответствующие элементам разрешающего столбца табл. 10.3, получаются путем деления соответствующих элементов табл. 10.3 на разрешающий элемент и берутся с противоположным знаком.

9. Остальные элементы вычисляются по правилу прямоугольника: мысленно вычерчиваем прямоугольник в табл. 10.3, одна вершина которого совпадает с разрешающим элементом, а другая - с элементом, образ которого мы ищем; остальные две вершины определяются однозначно. Тогда искомый элемент из табл. 10.4 будет равен соответствующему элементу табл. 10.3 минус дробь, в знаменателе которой стоит разрешающий элемент, а в числителе - произведение элементов из двух неиспользованных вершин прямоугольника.

10. Как только получится таблица, в которой в последней строке все элементы отрицательны, считается, что минимум найден. Минимальное значение функции равно свободному члену в строке целевой функции, а оптимальное решение определяется свободными членами при базисных переменных. Все свободные переменные в этом случае равны нулю.

11. Если в разрешающем столбце все элементы отрицательны, то задача не имеет решений (минимум не достигается).

21.Приведите классификацию моделей математического программирования

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

Одним из направлений мат/ого программирования яв-ся линейное программирование, в к/ом ярко прояв-ся специфические трудности нахождения экстремума на границе допустимой области переменных. В отличие от линейного программирования теория экстремальных задач, в к/ой целевая ф/я и/или ф/и, задающие ограничения, не линейны, называется нелинейным программированием. В частности, таковым яв-ся квадратичное программирование, в к/ом изучается задача нахождения экстремума квадратичной ф/и при линейных ограничениях типа равенств и/или неравенств. Линейное программирование первоначально развивалось как направление, разрабатывающее новые подходы к решению задач минимизации выпуклых ф/й, т. е. в рамках выпуклого программирования. Выпуклое программирование посвящено нахождению экстремума выпуклой целевой ф/и на выпуклом множ/ве, обычно задаваемом в виде с/мы выпуклых неравенств. Класс задач оптимизации, в к/ых область определения переменных состоит из отдельных изолированных точек, составляет предмет изучения дискретного программирования. Широкий класс нелинейных и дискретных задач может решаться с использованием идеи рекуррентного подхода (методов типа мат/ой индукции), являющихся основой динамического программирования, идея к/ого первоначально была предложена Р. Беллманом. Для решения задач оптимизации со случайными параметрами разработано стохастическое программирование .К мат/ому программированию относят также бесконечномерное программирование, в рамках к/ого предложены методы решения экстремальных задач с бесконечным числом переменных (например, такие, в к/ых набором переменных яв-ся ф/и или набор ф/й) и минимизируется (максимизируется) ф/онал. Развиты также методы решения задач оптимизации, в к/ых переменная принимает только два значения «истинно» - «ложно» или «да» — «нет». Такие методы относят к булевому программированию. Методы мат/ого программирования находят свое применение в самых различных областях техники и экономики.

В настоящее время экономическую теорию невозможно представить без экономико-мат/их методов, основанных на результатах мат/ого программирования. Здесь достаточно упомянуть модели календарного планирования или упорядочения во времени, расписания, потоковые или транспортные модели; модели распределения и назначе­ния; модели износа и замены оборудования.

Методы математического программирования находят свое применение в самых различных областях техники и экономики.

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

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

Например, если основная задача имеет вид

Ах ≤b , х≥0, f(с,х) → max, (11.1)

то двойственная к ней задача также яв-ся задачей линейного программирования:

А^Ту≥ с, у≤0, f(b, у)→ min. (11.2)

Здесь х = (x₁,х₂,... ,х_n); b = (b₁, b₂,…,b_т); с = (с₁, с₂,..., с_n); у = (y₁,y₂,... ,у_m);

f(c,x)= (11.3)

(b,y)= транспонированная матрица A.

Основная и двойственная к ней задачи образуют пару взаимно двойственных задач: двойственная задача к двойственной оказывается основной задачей.

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

1) если прямая задача яв-ся задачей максимизации, то двойственная задача будет задачей минимизации и наоборот;

2) коэффициенты целевой функции прямой задачи с = (с₁, с₂,..., с_n) становятся свободными членами ограничений двойственной задачи;

3) свободные члены ограничения прямой задачи b = (b₁, b₂,…,b_т) становятся свободными членами целевой функции двойственной задачи;

4) матрицу ограничений двойственной задачи получают транспонированием матрицы ограничения прямой задачи;

5) знаки неравенств в ограничениях изменяются на обратные;

6) число ограничений прямой задачи равно числу переменных двойственной задачи, а число ограничений двойственной задачи равно числу переменных прямой задачи.

Основная теорема двойственности:

Либо обе задачи двойственной пары разрешимы, и тогда (с, х*) = (b, у*), либо обе задачи не имеют решения. Здесь х*,у* - оптимальные планы пары двойственных задач.

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

Содержательный анализ двойственной задачи, в том числе и неизвестных у₁ у₂, ... , у_m, полностью определяется содержательным смыслом прямой задачи.

Так, например, если основная задача (11.1) яв-ся задачей производственного планирования, где А - технологическая матрица, b_i - количество i-го ресурса, x_j - объем выпуска j-го продукта, i = 1, 2, ... m, j = 1, 2, ... n, то целью решения двойственной задачи (11.2) оказывается нахождение так называемых двойственных оценок ресурсов y_i, которые также называют маргинальными (предельными) данными ресурсов.

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

Если маргинальные цены не превосходят рыночных (у_i*≤ q_i, i=1,2,..., m), то производство, для которого они были рассчитаны, не сможет получить прибыль р от своей производственной деятельности: для любого плана выпуска x.

р(х) = (с, х) - (b, q) ≤, (с, х*) - (b, q) ≤ (с, х*) - (b. у*) = 0.

И, наоборот, если у_i* > q_i, i= 1, 2,..., т, то реализация оптимального производственного плана х* принесет положительную прибыль.

р(х*) = (с, х*) - (b, q) = (А, у*) - (b, q) = (b, y*-q)> 0,

размер которой ограничивается: а) средствами, выделяемым на закупку ресурсов; b) объемом рынка ресурсов; с) технологическими условиями производства.

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

В частности, следующее важное утверждение:

Если задача линейного программирования не вырождена и С(х*) представляет собой максимум ее линейной формы при заданных ограничениях, то дс(х*)/дb_i = у_i*, i = 1,2,..., т.

Таким образом, с математической точки зрения оптимальные оценки определяют влияние свободных членов b, условий-ограничений на оптимальную величину целевой функции. Иными словами, вычисление наряду с оптимальным планом х* = (х₁*, х₂*, ... , х_n*) связанных с ним оптимальных оценок у* = {у₁*, у₂*, ... , y_т*) позволяет ввести относительную важность отдельных ресурсов (b₁*, b₂*.....b_m*) для достижения поставленной цели (максимизации ).

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

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

29.Приведите содержательные постановки задач, приводящие к моделям дискретного программирования

30.Дайте общую математическую формулировку задач дискретного программирования

Математические модели задач дискретного программирования.По структуре математической модели задачи дискретного программирования разделяют на следующие классы:

1) задачи с неделимостями;

2) экстремальные комбинаторные задачи;

3) задачи на несвязных и на невыпуклых плоскостях;

4) задачи с разрывными целевыми функциями.

Рассмотрим существо некоторых