УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС ПО ДИСЦИПЛИНЕ ЕН.04. МАТЕМАТИЧЕСКИЕ МЕТОДЫ (ТЕОРЕТИЧЕСКИЙ БЛОК) ПО СПЕЦИАЛЬНОСТИ 09.02.03 Программирование в компьютерных системах
ДЕПАРТАМЕНТ ОБРАЗОВАНИЯ, НАУКИ И МОЛОДЕЖНОЙ ПОЛИТИКИ ВОРОНЕЖСКОЙ ОБЛАСТИ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ СРЕДНЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ВОРОНЕЖСКОЙ ОБЛАСТИ
«СЕМИЛУКСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИКО-ЭКОНОМИЧЕСКИЙ КОЛЛЕДЖ»
УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС
ПО ДИСЦИПЛИНЕ
ЕН.04. МАТЕМАТИЧЕСКИЕ МЕТОДЫ
(ТЕОРЕТИЧЕСКИЙ БЛОК)
ПО СПЕЦИАЛЬНОСТИ
09.02.03 Программирование в компьютерных системах
ДЛЯ СТУДЕНТОВ ОЧНОЙ ФОРМЫ ОБУЧЕНИЯ
Семилуки. 2014
Одобрено методическим советом ГОБУ СПО ВО «СГТЭК»
Автор-составитель: Евдокимова М.Д., преподаватель ГОБУ СПО ВО «СГТЭК»
Учебно-методический комплекс по дисциплине Математические методы адресован студентам очной формы обучения.
УМКД включает теоретический блок, перечень практических занятий, задания по самостоятельному изучению тем дисциплины, вопросы для самоконтроля, а также вопросы и задания по промежуточной и итоговой аттестации.
© Евдокимова М.Д., 2014
©ГОБУ СПО ВО «СГТЭК»
СОДЕРЖАНИЕ
Наименование разделов
стр
Введение
4
Образовательный маршрут
6
Содержание дисциплины
7
Раздел 1. Основные понятия и принципы моделирования
7
Раздел 2. Основные методологические подходы к решению математических задач, возникающих в ходе практической деятельности людей
27
Раздел 3. Основные методы решения детерминированных задач и задач в условиях неопределенности, возникающих в практической деятельности
80
Контроль и оценка результатов освоения учебной дисциплины
129
Информационное обеспечение дисциплины
133
УВАЖАЕМЫЙ СТУДЕНТ!
Учебно-методический комплекс по дисциплине Математические методы создан Вам в помощь для работы на занятиях, при выполнении домашнего задания и подготовки к текущему и итоговому контролю по дисциплине.
УМК по дисциплине включает теоретический блок, содержание практических занятий, задания для самостоятельного изучения тем дисциплины, вопросы для самоконтроля.
Приступая к изучению новой учебной дисциплины, Вы должны внимательно изучить список рекомендованной основной и вспомогательной литературы. Из всего массива рекомендованной литературы следует опираться на литературу, указанную как основную.
По каждой теме в УМК перечислены основные понятия и термины, вопросы, необходимые для изучения (план изучения темы), а также информация по каждому вопросу из подлежащих изучению. Наличие теоретической информации по теме позволит Вам вспомнить ключевые моменты, рассмотренные преподавателем на занятии.
После изучения теоретического блока приведен перечень практических занятий, выполнение которых обязательно. Наличие положительной оценки по практическим необходимо для получения допуска к экзамену по дисциплине, поэтому в случае отсутствия на уроке по уважительной или неуважительной причине Вам потребуется найти время и выполнить пропущенную работу. В процессе изучения дисциплины предусмотрена самостоятельная внеаудиторная работа, включающая решение задач, углубленную проработку тем, составление информационных таблиц.
По итогам изучения дисциплины проводится экзамен.
В результате освоения дисциплины Вы должны уметь:
составлять простейшие математические модели задач, возникающих в практической деятельности людей;
составлять простейшие математические модели задач, возникающих в практической деятельности людей;
выбирать наиболее рациональный метод и алгоритм решения задачи, а также оценивать сложность выбранного алгоритма;
разрабатывать алгоритмы для решения различных практических задач с применением математических методов.
В результате освоения дисциплины Вы должны знать:
основные понятия и принципы моделирования;
основные методологические подходы к решению математических задач, возникающих в ходе практической деятельности людей;
основные методы решения детерминированных задач и задач в условиях неопределенности, возникающих в практической деятельности.
В результате освоения дисциплины у Вас должны формироваться общие компетенции (ОК):
Название ОК
Результат, который Вы должны получить после изучения содержания дисциплины
ОК 1. Понимать сущность и социальную значимость своей будущей профессии, проявлять к ней устойчивый интерес.
Понимание роли математического аппарата программировании
ОК 2. Организовывать собственную деятельность, выбирать типовые методы и способы выполнения профессиональных задач, оценивать их эффективность и качество.
Умения применять математический аппарат в решении профессиональных задач, оценивать их эффективность и качество
ОК 3. Принимать решения в стандартных и нестандартных ситуациях и нести за них ответственность.
Развитие аналитического мышления.
ОК 4. Осуществлять поиск и использование информации, необходимой для эффективного выполнения профессиональных задач, профессионального и личностного развития.
Умение ориентироваться в многообразии моделей объектов естествознания и методов их решения
ОК 5. Использовать информационно-коммуникационные технологии в профессиональной деятельности.
Умение осуществлять поиск нужной информации различных источниках.
ОК 6. Работать в коллективе и команде, эффективно общаться с коллегами, руководством, потребителями.
Умение эффективно распределять объём работы между участниками решения конкретной задачи.
ОК 7. Брать на себя ответственность за работу членов команды (подчиненных), результат выполнения заданий.
Навыки доводить решение поставленной задачи до получения нужного результата и его интерпретация.
ОК 8. Самостоятельно определять задачи профессионального и личностного развития, заниматься самообразованием, осознанно планировать повышение квалификации.
Расширение круга представлений о возможности применения математического аппарата для решения общепрофессиональных задач.
ОК 9. Ориентироваться в условиях частой смены технологий в профессиональной деятельности.
Умение составлять математические модели содержательных задач и применять для их решения численные методы.
Содержание дисциплины поможет Вам подготовиться к последующему освоению профессиональных компетенций в рамках профессионального МДК 01.02 Прикладное программирование, входящего в ПМ.01 Разработка программных модулей программного обеспечения компьютерных систем.
В таблице приведены профессиональные компетенции, к освоению которых готовит содержание дисциплины.
Название ПК
Результат, который Вы должны получить после изучения содержания дисциплины
ПК 1.1. Выполнять разработку спецификаций отдельных компонент.
Умение составлять математические модели оптимизационных задач
ПК.в Осуществлять разработку кода программного продукта для решения различных практических задач с применением математических методов.
Умение использовать алгоритмы на графах при составлении программ.
ПК.в Реализовывать основные методологические подходы к решению математических задач, возникающих в ходе практической деятельности людей при работе в базе данных;
Умение использовать алгоритмы математических методов при составлении программ.
Внимание! Если в ходе изучения дисциплины у Вас возникают трудности, то Вы всегда можете к преподавателю прийти на дополнительные занятия, которые проводятся согласно графику. Время проведения дополнительных занятий Вы сможете узнать у преподавателя, а также познакомившись с графиком их проведения, размещенном на двери кабинета преподавателя.
В случае, если Вы пропустили занятия, Вы также всегда можете прийти на консультацию к преподавателю в часы дополнительных
занятий.
ОБРАЗОВАТЕЛЬНЫЙ МАРШРУТ ПО ДИСЦИПЛИНЕ
Таблица 1
Формы отчетности, обязательные для сдачи
Количество
практические занятия
10
Итоговая аттестация (при наличии)
экзамен
Желаем Вам удачи!
СОДЕРЖАНИЕ ДИСЦИПЛИНЫ
Раздел 1. Основные понятия и принципы моделирования
Основные понятия и термины по теме: математическая модель, оптимизационная задача, множество возможных решений, оптимальное решение, показатель эффективности, многокритериальные задачи.
План изучения темы (перечень вопросов, обязательных к изучению):
Основные понятия и принципы моделирования. Основные понятия: решение, множество возможных решений, оптимальное решение, показатель эффективности.
Математическое моделирование задач коммерческой деятельности. Классические задачи математических методов: задача диеты (или задача о рационе); задача замены; задача о коммивояжере; распределительные задачи; задача о назначениях; задача о размещении складов; задача о раскрое; задачи поиска; задачи согласования; задачи упорядочения
Модели выбора решений в условиях неопределенности: выбор определенной модели товара или услуги на основе попарного сравнения их характеристик
Математические модели. Оптимальное решение. Показатель эффективности. Математические модели, основные принципы построения моделей, аналитические и статические модели.
Однокритериальные и многокритериальные задачи. Методы решения. Классификация задач, возникающих в практической деятельности и подходы к их решению: прямые и обратные задачи, детерминированные задачи и задачи в условиях неопределенности, однокритериальные и многокритериальные задачи, методы решения многокритериальных задач (выделение множества Парето, линейная свертка, наложение ограничений на показатели эффективности, метод последовательных уступок).
Теоретический материал
Введение
Сложный характер теоретических и практических задач современной рыночной экономики требует использования математических методов в экономических исследованиях. Проблемы, с которыми сталкиваются специалисты в различных областях экономики, зависят от множества различных, противоречивых факторов, меняющихся со временем и влияющих на другие проблемы и процессы.
В последнее время математическое моделирование является одним из важнейших методов изучения и анализа экономических объектов и процессов и прогнозирования их развития. Важность использования математических методов в анализе экономических проблем подчеркивается тем, что Нобелевские премии в области экономики получают в основном за успехи в экономико-математическом моделировании.
Экономико-математическое моделирование – это один из эффективных методов описания сложных социально-экономических систем и процессов.
Математические модели отображают экономические проблемы в абстрактной форме и позволяют учесть большое число различных характеристик исследуемых проблем.
Экономико-математическое моделирование призвано помочь руководителям различного ранга в выработке, обосновании и принятии эффективных, качественных решений в области экономики, организации производства и управления, в инвестиционном проектировании и в финансовой сфере. Это должно повысить надежность функционирования производственно-экономических систем.
Квалифицированные специалисты в различных областях экономической деятельности должны обладать обширными познаниями в сфере экономико-математического моделирования для решения задач оптимального распределения органических ресурсов; выработки эффективных решений в условиях неопределенности, противоречивости ограничений; анализа производственно-экономической информации и прогнозирования развития исследуемых процессов на основе современных компьютерных технологий.
Тема лекции «Основные понятия и принципы моделирования»
План лекции
Понятие о моделях и моделировании.
Алгоритм моделирования в задачах коммерческой деятельности.
Понятие о моделях и моделировании
Моделирование - это замещение одного объекта (оригинала) другим (моделью) и фиксация и изучение свойств модели. Замещение производится с целью упрощения, удешевления, ускорения изучения свойств оригинала.
Модель (лат. modulus мера) это объект-заместитель объекта-оригинала, обеспечивающий изучение некоторых свойств оригинала.
Компьютерная модель это программная реализация математической модели, дополненная различными служебными программами (например, рисующими и изменяющими графические образы во времени). Компьютерная модель имеет две составляющие программную и аппаратную. Программная составляющая так же является абстрактной знаковой моделью. Это лишь другая форма абстрактной модели, которая, однако, может интерпретироваться не только математиками и программистами, но и техническим устройством процессором компьютера.
Таким образом, моделирование может быть определено как представление объекта моделью для получения информации об этом объекте путем проведения экспериментов с его моделью. Теория замещения одних объектов (оригиналов) другими объектами (моделями) и исследования свойств объектов на их моделях называется теорией моделирования.
Теория моделирования взаимосвязанная совокупность положений, определений, методов и средств создания моделей. Сами модели являются предметом теории моделирования.
Теория моделирования является основной составляющей общей теории систем - системологии, где в качестве главного принципа постулируются осуществимые модели: система представима конечным множеством моделей, каждая из которых отражает определённую грань её сущности.
Роль и место моделирования в исследовании систем
Познание любой системы (S) сводится по существу к созданию её модели. Перед изготовлением каждого устройства или сооружения разрабатывается его модель - проект. Любое произведение искусства является моделью, фиксирующее действительность.
Достижения математики привели к распространению математических моделей различных объектов и процессов. Подмечено, что динамика функционирования разных по физической природе систем однотипными зависимостями, что позволяет моделировать их на ЭВМ.
На качественно новую ступень поднялась моделирование в результате разработки методологии имитационного моделирования на ЭВМ.
Сейчас трудно указать область человеческой деятельности, где бы применялось моделирование. Разработаны модели производства автомобилей, выращивания пшеницы, функционирования отдельных органов человека, жизнедеятельности Азовского моря, атомного взрыва, последствий атомной войны.
Специалисты считают, что моделирование становится основной функцией ВС. На практике широко используются АСУ технологическими процессами организационно-экономическими комплексами, процессами проектирования, банки данных и знаний. Но любая из этих систем нуждается в информации об управляемом объекте и модели управляемой объектом, в моделировании тех или иных управляющих решений.
Сами ВС как сложные и дорогостоящие технические системы могут являться объектами моделирования.
Обычно процесс разработки сложной системы осуществляется итерационно с использованием моделирования проектных решений. Если характеристики не удовлетворяют предъявленным требованиям, то по результатам анализа производят корректировку проекта, затем снова проводят моделирование.
При анализе действующих систем с помощью моделирования определяют границы работоспособности системы, выполняют имитацию экспериментальных условий, которые могут возникнуть в процессе функционирования системы. Искусственное создание таких условий на действительной системе затруднено и может привести к катастрофическим последствиям.
Применение моделирования может быть полезным при разработке стратегии развития ВС, её усовершенствования при создании сетей ЭВМ.
В настоящее время при анализе и синтезе сложных (больших) систем получил развитие системный подход, который отличается от классического (или индуктивного - путем перехода от частного к общему и синтезирует (конструирует) систему путем слияния ее компонент, разрабатываемых раздельно) подхода. В отличие от этого системный подход предполагает последовательный переход от общего к частному, когда в основе рассмотрения лежит цель, причем исследуемый объект выделяется из окружающей среды.
Понятие системы и элемента системы
Специалисты по проектированию и эксплуатации сложных систем имеют дело с системами управления различных уровней, обладающими общим свойством - стремлением достичь некоторой цели. Эту особенность учтем в следующих определениях системы.
Система S целенаправленное множество взаимосвязанных элементов любой природы.
Внешняя среда Е множество существующих вне системы элементов любой природы, оказывающих влияние на систему или находящихся под ее воздействием.
Понятие модели
Модель представление объекта, системы или понятия, в некоторой форме, отличного от их реального существования.
Моделирование во-первых, построение модели, во-вторых, изучение модели, в-третьих, анализ системы на основе данной модели.
При системном подходе к моделированию систем необходимо прежде всего четко определить цель моделирования. Применительно к вопросам моделирования цель возникает из требуемых задач моделирования, что позволяет подойти к выбору критерия и оценить, какие элементы войдут в создаваемую модель М. Поэтому необходимо иметь критерий отбора отдельных элементов в создаваемую модель.
Цели моделирования:
1) оценка оценить действительные характеристики проектируемой или существующей системы, определить насколько система предлагаемой структуры будут соответствовать предъявляемым требованиям.
2) сравнение произвести сравнение конкурирующих систем одного функционального назначения или сопоставить несколько вариантов построения одной и той же системы.
3) прогноз оценить поведение системы при некотором предполагаемом сочетании рабочих условий.
4) анализ чувствительности выявить из большого числа факторов, действующих на систему тем, которое в большей степени влияют на ее поведение и определяют ее показатели эффективности.
5) оптимизация найти или установить такое сочетание действующих факторов и их величин, которое обеспечивает наилучшие показатели эффективности системы в целом.
1-4 задачи анализа, 5 - задача синтеза.
Подходы к исследованию систем. Важным для системного подхода является определение структуры системы совокупности связей между элементами системы, отражающих их взаимодействие.
При структурном подходе выявляются состав выделенных элементов системы S и связи между ними. Совокупность элементов и связей между ними позволяет судить о структуре системы. Последняя в зависимости от цели исследования может быть описана на разных уровнях рассмотрения. Наиболее общее описание структуры это топологическое описание, позволяющее определить в самых общих понятиях составные части системы и хорошо формализуемое на базе теории графов.
Менее общим является функциональное описание, когда рассматриваются отдельные функции, т. е. алгоритмы поведения системы, и реализуется функциональный подход, оценивающий функции, которые выполняет система, причем под функцией понимается свойство, приводящее к достижению цели.
Независимо от типа используемой модели М при ее построении необходимо руководствоваться рядом принципов системного подхода:
1) пропорционально-последовательное продвижение по этапам и направлениям создания модели;
2) согласование информационных, ресурсных, надежностных и других характеристик;
3) правильное соотношение отдельных уровней иерархии в системе моделирования;
4) целостность отдельных обособленных стадий построения модели.
Классификация моделей
Физические модели. В основу классификации положена степень абстрагирования модели от оригинала. Предварительно все модели можно подразделить на 2 группы физические и абстрактные (математические).
Ф.М. обычно называют систему, эквивалентную или подобную оригиналу, но возможно имеющую другую физическую природу. Виды Ф.М.:
- натуральные - это реальные исследуемые системы (макеты, опытные образцы). Имеют полную адекватность (соответствия) с системой оригиналом, но дороги;
- квазинатуральные совокупность натуральных и математических моделей. Этот вид используется тогда, когда модель части системы не может быть математической из-за сложности её описания (модель человека оператора) или когда часть системы должна быть исследована во взаимодействии с другими частями, но их ещё не существует или их включение очень дорого (вычислительные полигоны, АСУ);
- масштабные это система той же физической природы, что и оригинал, но отличается от него масштабами. Методологической основой масштабного моделирования является теория подобия. При проектировании ВС масштабные модели могут использоваться для анализа вариантов компоновочных решений;
- аналоговые - системы, имеющие физическую природу, отличающуюся от оригинала, но сходные с оригиналом процессы функционирования. Для создания аналоговой модели требуется наличие математического описания изучаемой системы. В качестве аналоговых моделей используются механические, гидравлические, пневматические и электрические системы. Аналоговое моделирование использует при исследовании средства ВТ на уровне логических элементов и электрических цепей, а так же на системном уровне, когда функционирование системы описывается, например, дифференциальными или алгебраическими уравнениями;
Математические модели. Математические модели представляют собой формализованное представление системы с помощью абстрактного языка, с помощью математических соотношений, отражающих процесс функционирования системы. Для составления математических моделей можно использовать любые математические средства алгебраическое, дифференциальное, интегральное исчисления, теорию множеств, теорию алгоритмов и т.д. По существу вся математика создана для составления и исследования моделей объектов и процессов.
К средствам абстрактного описания систем относятся также языки химических формул, схем, чертежей, карт, диаграмм и т.п. Выбор вида модели определяется особенностями изучаемой системы и целями моделирования, т.к. исследование модели позволяет получить ответы на определённую группу вопросов. Для получения другой информации может потребоваться модель другого вида. Математические модели можно классифицировать как детерминированные и вероятностные, аналитические, численные и имитационные.
Детерминированное моделирование отображает процессы, в которых предполагается отсутствие всяких случайных воздействий; стохастическое моделирование отображает вероятностные процессы и события. В этом случае анализируется ряд реализаций случайного процесса и оцениваются средние характеристики, т. е. набор однородных реализаций.
Аналитической моделью называется такое формализованное описание системы, которое позволяет получить решение уравнения в явном виде, используя известный математический аппарат.
Численная модель характеризуется зависимостью такого вида, который допускает только частные решения для конкретных начальных условий и количественных параметров моделей.
Имитационная модель это совокупность описания системы и внешних воздействий, алгоритмов функционирования системы или правил изменения состояния системы под влиянием внешних и внутренних возмущений. Эти алгоритмы и правила не дают возможности использования имеющихся математических методов аналитического и численного решения, но позволяют имитировать процесс функционирования системы и производить вычисления интересующих характеристик. Имитационные модели могут быть созданы для гораздо более широкого класса объектов и процессов, чем аналитические и численные. Поскольку для реализации имитационных моделей служат ВС, средствами формализованного описания ИМ служат универсальные и специальные алгоритмические языки. ИМ в наибольшей степени подходят для исследования ВС на системном уровне.
Алгоритм моделирования в задачах коммерческой деятельности
Вся совокупность действий, связанных с построением, анализом и другими операциями, проводимыми с моделями, называется моделированием, алгоритм которого представлен на рис.2.
Рис.2. Алгоритм моделирования
Последовательность моделирования представляет собой ите ративную (пошаговую) процедуру, которая предусматривает и позволяет про вести коррекцию после каждого этапа и вернуться к любому из предшествующих, а затем продолжить анализ.
Можно выделить несколько основных этапов алгоритма экономико-математического моделирования. Все начинается с замысла. Затем на первом этапе выявляется проблема, формулиру ются цели и задачи исследования, проводится качественное опи сание экономического процесса или объекта. На втором этапе определяются методы решения, строится математическая модель изучаемого объекта, выбираются или разрабатываются методы исследования, программируются модели на компьютере, подго тавливается исходная информация. Далее проверяется пригод ность машинной модели на основе правильности получаемых с ее помощью результатов и оценивается их устойчивость. На тре тьем, основном, этапе экономико-математического моделирова ния проводится исследование по модели, реализованной в виде компьютерных программ, проводятся расчеты, обрабатываются и анализируются полученные результаты и, наконец, принима ется оптимальное решение.
Вопросы для самоконтроля:
Что такое математическое моделирование?
Что такое модель?
Дайте определение компьютерной модели.
Дайте определение теории моделирования.
Опишите роль и место моделирования в исследовании систем.
Опишите цели моделирования.
Опишите классификацию моделей.
Что такое математическое моделирование. На какие типы оно делится.
Сформулируйте алгоритм моделирования в задачах коммерческой деятельности. Опишите каждый его этап.
Тема лекции «Математическое моделирование задач коммерческой деятельности»
План лекции:
Классические задачи математических методов
Классические задачи исследования операций
Рассмотрим некоторые классические задачи, традиционно относящиеся к проблематике исследования операций.
Задача диеты (или задача о рационе) – задача ЛП, состоящая в определении такого рациона, который удовлетворял бы потребности человека или животного в питательных веществах при минимальной общей стоимости используемых продуктов. Это наиболее распространенный случай более общей задачи об оптимальном составе смеси.
Задача замены заключается в прогнозе затрат, связанных с обновлением оборудования, и в выработке наиболее экономичной стратегии проведения этой работы. В этих задачах широко используются математико-статистические методы, так как выход из строя оборудования всегда имеет нерегулярный, вероятностный характер.
Задача о коммивояжере состоит в отыскании наилучшего маршрута для коммивояжера (бродячего торговца), который должен объехать все порученные ему города и вернуться назад за кратчайший срок или с наименьшими затратами на проезд. Это одна из типичных задач, решаемых методом динамического программирования. О сложности ее говорит такой факт: если городов – 4, то число возможных маршрутов равно 6, а уже при 11 городах существует более 3,5 млн. допустимых маршрутов.
Распределительные задачи – класс экономико-математических задач, связанных с распределением ресурсов по работам, которые необходимо выполнить. Распределительная задача заключается в отыскании наилучшего распределения ресурсов, при котором либо максимизируется общий доход или результат, выраженный в какой-либо форме, либо минимизируются затраты.
Задача о назначениях – вид задачи ЛП, с помощью которой решаются вопросы типа: как распределить рабочих по станкам, чтобы общая выработка была наибольшей или затраты на заработную плату наименьшими, как наилучшим образом распределить экипажи самолетов, как назначить людей на различные должности.
Задача о размещении складов – одна из задач исследования операций, обычно решаемая методом НП (но при некоторых условиях она может сводиться и к обычной транспортной задаче ЛП). Заключается в минимизации общей суммы транспортных и складских расходах при следующих ограничениях: с каждого завода должна быть отгружена вся продукция, емкость любого склада не должна быть превышена, потребности всех покупателей должны быть удовлетворены.
Задача о раскрое – частный случай задач о комплексном использовании сырья, обычно сводящихся к методу ЛП. Выбранный математиками метод решения задачи о раскрое помогает с наименьшими отходами использовать листы металла, листы стекла, картона и других материалов при раскрое их на заданное количество деталей различных размеров.
Задачи поиска – класс задач, состоящих в отыскании наилучшего способа получения такой информации, которая однозначно определила бы решение. Критерием такой задачи является минимум затрат двух видов: стоимости получения информации и цены ошибки, обусловленной ее использованием.
Задачи согласования – класс задач, связанных с согласованием совокупности отдельных работ и частных операций во времени для получения оптимального общего результата. Это обычно задачи сетевого планирования и управления.
Задачи упорядочения – класс задач, в которых производится выбор дисциплины обслуживания. Выбор порядка обслуживания называется упорядочением.
Вопросы для самоконтроля:
Классические задачи математических методов.
Тема лекции «Модели выбора решений в условиях неопределенности»
План лекции:
Выбор определенной модели товара или услуги на основе попарного сравнения их характеристик
Выбор определенной модели товара или услуги на основе попарного сравнения их характеристик
В практической деятельности приходится рассматривать сложные объекты, которые невозможно целостно сопоставить. В таких случаях выделяют существенные показатели этих объектов, а затем проводят сравнение их значений. При этом первичная информация задаётся в виде таблицы значений показателей, где представлены множество сравниваемых объектов a1, a2, a3,, ai, ,am, все наименования показателей P1, P2, P3, , Pi, , Pn и значение этих показателей по каждому объекту p1(ai), p2(a2), p3(a3), , pj(ai), , pn(am).
Для выявления предпочтения необходимо ввести систему решающих правил. Например, если по каждому показателю pj(ai) можно вычислить Mj, определяющую его значимость, то взвешенную сумму этих показателей можно рассматривать как суммарную оценку объекта ai :
13 EMBED Equation.3 1415
Тогда можно ввести решающее правило: ai предпочтительнее aj, если F(ai)>F(aj).
По указанной системе решающих правил отношение, выражающее доминирование, определяется построением матрицы попарного сравнения В, элемент которой определяется таким образом:
13 EMBED Equation.3 1415
Пример:Рассмотрим задачу выбора ноутбука на основе следующих данных:
Характеристики моделей ноутбуков
Модель
Процессор
ОЗУ
Жесткий диск
Экран
Цена
Lenovo B570
1500 МГц
2048 МБ
250 ГБ
15,6 дюйм
11500 руб
ASUS Eee PC 1225B
1650 МГц
4096 МБ
500 ГБ
11,6 дюйм
15000 руб
Toshiba SATELLITE C850-C1K
1700 МГц
2048 МБ
500 ГБ
15,6 дюйм
11600 руб
Acer ASPIRE V5-171-53314G50as
1700 МГц
4096МБ
500 ГБ
11,6 дюйм
20000 руб
Сопоставим показатели с помощью метода парных сравнений.
Результаты запишем в таблицу.
Процессор
ОЗУ
Жесткий диск
Экран
Цена
Si
Mi
Ri
Процессор
1
2
2
2
2
9
0,36
1
ОЗУ
0
1
2
2
2
7
0,28
2
Жесткий диск
0
0
1
2
0
3
0,12
4
Экран
0
0
0
1
0
1
0,04
5
Цена
0
0
2
2
1
5
0,2
3
25
После заполнения матрицы элементами сравнения находим по строкам суммы баллов по каждому показателю:
13 EMBED Equation.3 1415
где n- количество показателей, n=5.
Правильность заполнения матрицы определяется равенством
13 EMBED Equation.3 1415
Затем определяем коэффициент весомости по формуле
13 EMBED Equation.3 1415
Приоритет показателей распределяется по рангу, который пропорционален значению коэффициента весомости: чем больше его значение, тем выше ранг, причем наибольшему значению Mi cсоответствует Ri=1.
Построим следующую матрицу бальных оценок показателей, выбрав наиболее важные показатели, имеющие ранг R=1.2.3.
Модель
Процессор
ОЗУ
Цена
Lenovo B570
3
4
5
ASUS Eee PC 1225B
4
5
3
Toshiba SATELLITE C850-C1K
5
4
4
Acer ASPIRE V5-171-53314G50as
5
5
2
Mi
0.36
0.28
0.2
На основании данных таблицы можно определить значения интегральных оценок для этих моделей ноутбуков:
F (Lenovo B570) = 0,36*3+0,28*4+0,2*5= 3.2
F (ASUS Eee PC 1225B) =0,36*4+0,28*5+0,2*3= 3.44
F (Toshiba SATELLITE C850-C1K) =0,36*5+0,28*4+0,2*5=3.92
F (Acer ASPIRE V5-171-53314G50as) = 0,36*5+0,28*5+0,2*2=3.6
Вывод: Так как F (Toshiba SATELLITE C850-C1K) больше остальных значений функции, то мы выбираем модель Toshiba SATELLITE C850-C1K..
Тема лекции «Математические модели. Оптимальное решение. Показатель эффективности»
План лекции
Введение.
Оптимальное решение.
Основные понятия и определения оптимизации.
Постановка задачи оптимизации в общей форме.
Выбор решения в условиях неопределенности.
Математическая модель дачи линейного программирования
Введение
Человек всегда принимал решения, и всегда хотелось, чтобы они были правильными, оптимальными.
Предмет математические методы тесно переплетается с математическим моделированием, исследованием операций, так как в исследовании операций и математическое моделирование практически всегда используются математические методы решения задач, моделирования систем и анализа их характеристик.
Исследование операций – это использование математических и количественных методов для обоснования решения.
Исследование операций решает типичные экономические задачи:
План снабжения предприятия сырьем.
Задача. Имеется n предприятий, m баз с ресурсами, запасы каждой базы ограничены. Требуется разработать план снабжения предприятия сырьем при минимальных расходах при перевозке.
Закладка дороги.
Задача. Имеется заданное количество рабочих, машин, транспорта. Требуется спланировать строительство дороги в минимально возможные сроки.
Продажа сезонных товаров.
Задача. Для реализации сезонных товаров создается сеть временных торговых точек. Требуется определить их число, размещение, запасы, количество персонала для получения максимальной прибыли.
Контроль продукции.
Задача. Выпускается определенный вид продукции. Для контроля качества организуется выборочная проверка. Требуется определить размер партии и правила проверки при минимальных расходах на контроль.
Другие задачи мы сформулировали на прошлом занятии.
Оптимальное решение
Оптимизация – это выбор наилучшего решения. Математическая теория оптимизации включает в себя фундаментальные результаты и численные методы, позволяющие находить наилучший вариант из множества возможных альтернатив без их полного перебора и сравнения.
Принятие оптимальных решений базируется на «трех китах»:
Математической модели;
Решение задачи на компьютере;
Исходных данных.
Математическое моделирование имеет два существенных преимущества: дает быстрый ответ на поставленный вопрос, предоставляет возможность широкого экспериментирования, осуществить которое на реальном объекте зачастую невозможно. Для решения оптимизационных задач используются количественные методы решения. Применяют математический аппарат разной степени сложности: простые алгебраические уравнения, обыкновенные дифференциальные уравнения, дифференциальные уравнения в частных производных.
Алгоритмы задач принятия решений настолько сложны, что без компьютера решить их невозможно.
Исходные данные определяют успех дела в целом.
Основные понятия и определения оптимизации
Операция – это мероприятие, направленное на достижение какой-то цели.
РЕШЕНИЕ – это определенный набор зависящих от нас параметров и действий.
ОПТИМАЛЬНОЕ РЕШЕНИЕ – это решение более предпочтительное перед другими по некоторому критерию.
ЭЛЕМЕНТЫ РЕШЕНИЯ – это те параметры, которые образуют решение задачи.
ПОКАЗАТЕЛЬ ЭФФЕКТИВНОСТИ (целевая функция) – это некоторые количественные критерии, по которым сравнивают решения между собой, его называют целевой функцией. Обозначается W.
Примеры выбора показателя эффективности.
Задача 1: если Р – суммарные расходы на перевозку сырья, то показатель эффективности Р min.
Задача 2: среднее ожидаемое время окончания стройки Т, тогда показатель эффективности Т min.
Задача 3: П – прибыль от реализации продукции, критерий эффективности Т max.
В большинстве задач на практике критерий эффективности выбрать очень сложно, так как эффективность в реальной жизни определяется не одним критерием, а нескольким.
Все задачи можно разделить на прямы и обратные.
ПРЯМЫЕ задачи отвечают на вопрос: что будет, если в заданных условиях выбрать некоторое решение Х.
ОБРАТНЫЕ задачи отвечают на вопрос: какое решение Х надо выбрать, чтобы показатель эффективности W был max или min.
Постановка задачи оптимизации в общей форме
Пусть имеется некоторая операция О, на успех которой можно влиять, выбирая некоторым способом, решение Х, эффективность операции характеризуется одним показателем W max. Когда все условия операции О определены заранее, то все факторы, от которых зависит успех операции делятся на две категории: заданные, заранее известные факторы
·; зависящие от нас элементы решения, которые образуют решения х.
Показатель эффективности зависит от обеих групп факторов и выражается формулой:
W = W(
·, x), (*)
в общем случае
·, x – векторы (совокупность чисел). Если зависимость (*) известна, то прямая задача решена.
Обратная задача формулируется так: при заданном комплексе условий
· требуется найти такое решение х = х*, которое обращает показатель эффективности W в max.
W* = max{W(
·, x)}, где W*- мах. W* - это максимальное значение эффективности при найденном оптимальном решении х*.
Решение задачи оптимизации.
Метод поиска экстремума и оптимального решения х* ведется, исходя из особенностей функции W и вида ограничений, накладываемых на решение. Если W и ограничения линейные, то имеем задачу линейного программирования, которая решается стандартным методом (симплекс методом). Если W – выпукла функция, то применяют метод выпуклого программирования. Для многоэтажных задач используют метод динамического программирования. Для решения многомерных задач применяют численные методы.
Выбор решения в условиях неопределенности
Реальные задачи чаще всего создают неизвестные факторы е. В этом случае показатель эффективности зависит от трех групп факторов: W = W(
·, x, е). Наличие неопределенных факторов е превращает задачу оптимизации в задачу о выборе решения в условиях неопределенности.
Задача 1. планируется ассортимент товаров для распродажи на ярмарке. Требуется получить максимальную прибыль. Неизвестно количество покупателей, их потребности.
Задача 2. проектируется система сооружений от паводков. Неизвестны моменты наступления и размеры.
Виды неопределенности.
неизвестный фактор е – случайная величина, статистические характеристики которой известны или могут быть получены, тогда имеем стохастическую задачу со стохастической неопределенностью.
Например: организуется работа магазина с целью повысить количество обслуживаемых покупателей, но неизвестны их количество, время посещения, требуемые товары, время обслуживания. Однако, все эти характеристики можно получить.
неизвестный фактор е не может быть получен и описан статистическим методами, тогда имеем не стохастическую неопределенность.
Например: проектируется информационно-вычислительная система для обслуживания случайных потоков запросов. Время существования запросов, их количество неизвестны, а получить вероятностные характеристики невозможно, так как система еще не создана.
В ситуациях с не стохастической неопределенностью полезно проводить предварительные расчеты. Кроме этого используют метод экспертных оценок, который используется в задачах прогнозирования. Его суть состоит в том, что вероятность события предлагают оценить экспертам, ответы обрабатывают как статистический материал. Полученные данные позволяют свести неопределенность к стохастической.
Математическая модель дачи линейного программирования
Математическая модель любой задачи линейного программирования включает в себя:
максимум или минимум целевой функции (критерий оптимальности);
систему ограничений в форме линейных уравнений и неравенств;
требование неотрицательности переменных.
Таким образом, экономико-математическая формулировка и модель общей задачи линейного программирования имеют следующий вид:
найти максимальное (минимальное) значение линейной целевой функции
13 EMBED Equation.3 1415
при условиях-ограничениях:
13 EMBED Equation.3 141513 EMBED Equation.3 141513 EMBED Equation.3 1415
где aij, bi, cj – заданные постоянные величины.
Пример. Фирма выпускает 2 вида мороженного: сливочное и шоколадное. Для изготовления используются 2 исходных продукта: молоко и наполнители, расходы которых на 1 кг мороженного и суточные запасы исходных продуктов даны в таблице.
Исходный продукт
Расход исходных продуктов на 1 кг мороженного
Запас, кг
Сливочное
Шоколадное
Молоко
0.8
0.5
400
Наполнители
0.4
0.8
365
Изучение рынка сбыта показало, что суточный спрос на сливочное мороженное превышает спрос на шоколадное мороженное не более чем на 100 кг. Кроме того, установлено, что спрос на шоколадное мороженное не превышает 350 кг в сутки. Отпускная цена 1 кг сливочного мороженного 16 ден.ед., шоколадного - 14 ден.ед. Определить количество мороженого каждого вида, которое должна производить фирма, чтобы доход от реализации продукции был максимальным.
Решение задачи:
Составляем математическую модель задачи.
Вводим обозначения (переменные величины):
х 1 – суточный объем выпуска сливочного мороженного, кг;
х 2 - суточный объем выпуска шоколадного мороженного, кг
Целевая функция:
F = 16 х 1 + 14 х 2max
при ограничениях:
0.8 х 1 + 0.5 х 2
· 400 (ограничение по молоку);
0.4 х 1 + 0.8 х 2
· 365 (ограничение по наполнителям);
х 1 + х 2
· 100 (рыночное ограничение по спросу);
х 2
· 350 (рыночное ограничение по спросу);
х 1
· 0, х 2
· 0
Пример: На фабрике изготавливаются краски для внутренних (В) и наружных (Н) работ, которая поступает в продажу по цене 3 тыс. руб. и 2 тыс. руб. за 1 т. Для производства красок используют два вида сырья А и В, максимально возможные суточные запасы которых составляют 3 т и 4 т. Расходы сырья на производство 1 т красок приведены в табл.
Суточный спрос на краску для внутренних работ никогда не превышал спроса на краску для наружных работ более чем на 1,5 т, а спрос на краску для внутренних работ никогда не превышал 2 т в сутки. Какое количество краски каждого вида необходимо производить фабрике, чтобы доход от ее реализации был максимальным?
Сырье
Расход сырья на 1 т краски, т
Запасы сырья, т
Наружных работ, Н
Внутренних работ, В
А
0,5
1,0
3
В
1,0
0,5
4
Цена 1 т, тыс. руб.
2
3
Решение задачи:
Построим экономико-математической модель задачи.
Поскольку в задаче необходимо определить объемы производства для продажи краски, то суточные объемы производства красок для наружных и внутренних работ обозначим 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415 тонн соответственно.
Критерием, по которому определяется степень достижения поставленной цели, является доход от продажи краски, который должен быть максимально возможным. На этом основании целевую функцию можно записать таким образом:
13 EMBED Equation.3 1415
Решение любой задачи осуществляется в рамках ограниченных ресурсов. В данном случае необходимо учесть ограничения на расход сырья, запасы которого на фабрике не бесконечны, а также ограничения на спрос краски. Математически эти ограничения можно записать следующим образом:
13 EMBED Equation.3 1415
Объемы производства и соответственно продажи краски не могут принимать отрицательных значений. В связи с этим необходимо записать условие неотрицательности переменных: 13 EMBED Equation.3 1415.
Кроме того, известно, что план фабрики предусматривает обязательный выпуск красок указанных видов, производство которых за всю историю не опускалось ниже, чем 13 EMBED Equation.3 1415 т, 13 EMBED Equation.3 1415 т.
Таким образом, в целом экономико-математическую модель задачи можно представить таком виде.
Определить суточные объемы производства красок – вектор 13 EMBED Equation.3 1415, который при заданных условиях-ограничениях
13 EMBED Equation.3 1415
обеспечивает максимальный доход от продажи краски в соответствии с целевой функцией: 13 EMBED Equation.3 1415.
Вопросы для самоконтроля:
Что такое исследование операции?
Какие основные задачи решает исследование операции ?
Дайте определение оптимизации.
Каковы основы оптимизации.
Сформулируйте основные понятия оптимизации (РЕШЕНИЕ, ОПТИМАЛЬНОЕ РЕШЕНИЕ, ЭЛЕМЕНТЫ РЕШЕНИЯ, ПОКАЗАТЕЛЬ ЭФФЕКТИВНОСТИ).
Сформулируйте задачу оптимизации в общей форме.
Тема лекции «Однокритериальные и многокритериальные задачи. Методы решения»
План лекции
Многокритериальные задачи
Метод Парето
Сведение многокритериальной задачи к однокритериальной
Метод последовательных уступок
Многокритериальные задачи
Когда идет речь о крупномасштабных, сложных операциях, затрагивающих разнообразные интересы их организаторов и общества в целом, то их эффективность не может быть полностью охарактеризована с помощью одного-единственного показателя эффективности W. На помощь ему приходится привлекать другие, дополнительные. Такие задачи исследования операций называются многокритериальными. Т. е. для крупномасштабной задачи исследования операций является многокритериальность – наличие ряда количественных показателей W1, W2, ... одни из которых желательно обратить в максимум, другие в минимум.
Многокритериальная задача – это задача, у которой несколько показателей эффективности, которые желательно обратить в максимум или в минимум или и в максимум, и в минимум.
Можно ли найти решение, одновременно удовлетворяющее всем этим требованиям? Откровенно ответим: нет. Как же быть в случае, если все же приходится оценивать эффективность операции по нескольким показателям. Существует несколько способов, о них несколько ниже.
Метод Парето
Есть задача с двумя критериями W1 и W2, оба требуется максимизировать. Множество X состоит из конечного числа n возможных решений x1, x2, ..., xn. Каждому решению соответствует определенные значения показателей W1 и W2; будем изображать решение точкой на плоскости с координатами W1, W2 и занумеруем точки соответственно номеру решения.
[ Cкачайте файл, чтобы посмотреть картинку ]
Очевидно, из всего множества X, эффективными будут только решения x2, x5, x10, x11, лежащие на правой верхней границе области возможных решений. Для всякого другого решения существует хотя бы одно доминирующее решение, для которого либо W1, либо W2, либо оба больше, чем для данного. И только для решений, лежащих на правой верхней границе, доминирующих не существует.
Когда из множества возможных решений выделены эффективные, "переговоры" могут вестись уже в пределах этого "эффективного" множества. На данном рисунке его образуют четыре решения: x2, x5, x10, x11, из которых x11 – наилучшее по критерию W1, а x2 – по критерию W2. Дело лица, принимающего решение, выбрать тот вариант, который для него предпочтителен по обоим критериям.
Сведение многокритериальной задачи к однокритериальной
Существует часто принимаемый способ свести многокритериальную задачу к однокритериальной – это выделить один (главный) показатель W1 и стремиться обратить его в максимум, а на все остальные W2, W3, ... наложить только некоторые ограничения, потребовав, чтобы они были не меньше каких-то заданных W2, W3, ... .
Например, при оптимизации плана работы предприятия можно потребовать, чтобы прибыль была максимальна, план по ассортименту – выполнен, себестоимость продукции – не выше заданной. При таком подходе все показатели, кроме одного – главного, переводятся в разряд заданных условий
·. Известный произвол в назначении границ W2, W3, ... остается; поправки в эти границы тоже могут быть введены в "диалоговом режиме".
Метод последовательных уступок
Предположим, что показатели W1, W2, ... расположены в порядке убывающей важности. Сначала ищется решение, обращающее в максимум первый (важнейший) показатель W1 = W'1. Затем назначается, исходя из практических соображений, с учетом малой точности, с которой нам известны входные данные, некоторая "уступка"
·W1, которую мы согласны сделать для того, чтобы максимизировать второй показатель W2. Наложим на показатель W1 ограничение: потребуем, чтобы он был не меньше, чем W'1-
·W1 и при этом ограничении ищем решение, обращающее в максимум W2. Далее снова назначим уступку в W2, ценой которой можно максимизировать W3 и т. д. Такой способ построения компромиссного решения хорош тем, что здесь сразу видно, ценой какой уступки в одном показателе приобретается выигрыш в другом и какова величина этого выигрыша.
Вопросы для самоконтроля:
Дайте определение многокритериальной задачи.
Приведите несколько примеров многокритериальных задач.
Перечислите методы нахождения оптимального решения многокритериальных задач.
Какой из методов нахождения оптимального решения многокритериальных задач предпочтителен.
Практические занятия:
Практическое занятие №1 «Составление простейших математических моделей задач, возникающих в практической деятельности людей»
Практическое занятие №2 «Решение простейших однокритериальных задач»
Раздел 2. Основные методологические подходы к решению математических задач, возникающих в ходе практической деятельности людей
Тема 2.1 Линейное программирование
Основные понятия и термины по теме: целевая функция, условия-ограничения, область допустимых решений, оптимальное решение, свободные переменные, базисные переменные.
План изучения темы (перечень вопросов, обязательных к изучению):
Основная задача ЛП. Общий вид задач линейного программирования (ЛП). Основная задача линейного программирования (ОЗЛП) и сведение произвольной задачи линейного программирования к основной задаче линейного программирования.
Методы решения задач ЛП. Геометрический метод. Разработка алгоритма для решения различных практических задач ЛП с применением математических методов
Методы решения задач ЛП. Симплекс-метод. Разработка алгоритма для решения различных практических задач ЛП с применением математических методов
Транспортная задача. Метод потенциалов. Разработка алгоритма для решения различных практических задач ЛП с применением математических методов
Теоретический материал
Тема лекции «Основная задача ЛП»
План лекции
Линейное программирование.
Пример на составление математических моделей задач линейного программирования.
Линейное программирование
Линейное программирование – это направление математического программирования, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием.
Линейное программирование состоит в нахождении экстремального значения линейной функции многих переменных при наличии линейных ограничений, связывающих эти переменные.
Необходимым условием постановки задачи линейного программирования являются ограничения на наличие ресурсов, величину спроса, производственную мощность предприятия и другие производственные факторы.
Математическая модель любой задачи линейного программирования включает в себя:
максимум или минимум целевой функции (критерий оптимальности);
систему ограничений в форме линейных уравнений и неравенств;
требование неотрицательности переменных.
Таким образом, экономико-математическая формулировка и модель общей задачи линейного программирования имеют следующий вид:
найти максимальное (минимальное) значение линейной целевой функции
13 EMBED Equation.3 1415
при условиях-ограничениях:
13 EMBED Equation.3 141513 EMBED Equation.3 141513 EMBED Equation.3 1415
где aij, bi, cj – заданные постоянные величины.
Стандартной задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения целевой функции (1) при выполнении условий (2) и (4).
Канонической (или основной) задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения целевой функции (1) при выполнении условий (3) и (4).
Совокупность чисел 13 EMBED Equation.3 1415, удовлетворяющих ограничениями задачи, называется допустимым решением (или планом).
План 13 EMBED Equation.3 1415 при котором целевая функция задачи принимает максимальное (минимальное) значение, называется оптимальным.
В случае, когда требуется найти минимум функции 13 EMBED Equation.3 1415 можно перейти к нахождению максимума функции 13 EMBED Equation.3 1415 так как 13 EMBED Equation.3 1415
Ограничение-неравенство исходной задачи линейного программирования, имеющий вид 13 EMBED Equation.3 1415, преобразуется в ограничение-равенство с добавлением к левой части дополнительной неотрицательной переменной, а ограничение-неравенство вида 13 EMBED Equation.3 1415 - преобразуется в ограничение-равенство вычитанием из левой части дополнительной неотрицательной переменной.
Запишем в основной задаче линейного программирования ограничение в векторной форме
13 EMBED Equation.3 1415
где 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415 - m-мерные векторы-столбцы, составленные из коэффициентов при неизвестных и свободных членах системы уравнений задачи.
План 13 EMBED Equation.3 1415 называется опорным планом основной задачи линейного программирования, если система векторов 13 EMBED Equation.3 1415, входящих разложение (5) с положительными коэффициентами 13 EMBED Equation.3 1415, линейно независимо.
Так как векторы 13 EMBED Equation.3 1415 являются m-мерными, то из определения опорного плана следует, что число его положительных компонентов не может превышать m.
Опорный план называется невырожденным, если он содержит ровно m положительных компонент. Если в опорном плане число положительных компонент меньше m, то план является вырожденным.
Пример на составление математических моделей задач линейного программирования
Пример: Фирма производит две модели А и В сборных книжных полок. Их производство ограничено наличием сырья (высококачественных досок) и временем машинной обработки. Для каждого изделия модели А требуется 3 м2 досок, а для модели В – 4 м2. Фирма может получать от своих поставщиков до 1700 м2 досок в неделю. Для каждого изделия модели А требуется 12 мин. машинного времени, а для изделия модели В – 30 мин. В неделю можно использовать 160 часов машинного времени.
Сколько изделий каждой модели следует выпускать фирме в неделю для максимальной прибыли, если каждое изделие модели А приносит 2 дол. прибыли, а каждое изделие модели В – 4 дол. прибыли?
Построение математической модели
Пусть x1 – количество выпущенных за неделю полок модели А, а x2 – количество выпущенных полок модели В. Тогда:
3x1 – количество досок, требуемых на неделю для изготовления полок модели А;
4x2 – количество досок, требуемых на неделю для изготовления полок модели В;
3x1+4x2 – количество досок, требуемых на неделю для изготовления книжных полок двух моделей, а по условию задачи это число не должно превышать 1700 м2, следовательно, получаем первое ограничение:
3x1+4x2
· 1700 (1)
Найдем ограничение на использование машинного времени.
12 мин. составляют 0,2 часа, а 30 мин. – 0,5 часа, таким образом:
0,2x1 – количество времени, требуемое на неделю для обработки полок модели А;
0,5x2 – количество времени, требуемое на неделю для обработки полок модели В;
0,2x1+0,5x2 – количество времени, требуемое на неделю для обработки двух моделей, а по условию задачи это число не должно превышать 160 часов, следовательно, получаем второе ограничение:
0,2x1+0,5x2
· 160 или 2x1+5x2
· 1600 (2)
Кроме того, поскольку x1 и x2 выражают еженедельный объем выпускаемых изделий, то они не могут быть отрицательными, то есть:
x1
· 0, x2
· 0 (3)
Наша задача состоит в том, чтобы найти такие значения x1 и x2, при которых еженедельная прибыль будет максимальной. Составим выражение для еженедельной прибыли:
2x1 – еженедельная прибыль, получаемая от продажи полок модели А;
4x2 – еженедельная прибыль, получаемая от продажи полок модели В;
F = 2x1+4x2 – еженедельная прибыль, которая должна быть максимальной. Таким образом, имеем следующую математическую модель для данной задачи.
F = 2x1+4x2 max
[ Cкачайте файл, чтобы посмотреть картинку ]
Вопросы для самоконтроля по теме:
Дайте определение задаче линейного программирования.
Что такое целевая функция?
Почему накладывается условие неотрицательности?
В чем отличие допустимых решений от оптимальных?
Тема лекции «Методы решения задач ЛП. Геометрический метод»
План лекции
Методы решения задач ЛП. Геометрический (графический) метод решения двумерной задачи линейного программирования (максимизация целевой функции).
Алгоритм решения двумерной задачи линейного программирования геометрическим методом.
Пример решения задачи ЛП графическим методом.
Геометрический (графический)метод решения двумерной задачи линейного программирования (максимизация целевой функции)
Двумерная задача линейного программирования – задача линейного программирования, количество переменных которой равно 2.
В общем виде двумерную задачу линейного программирования можно представить следующим образом.
Определить значение переменных x1 и x2, при которых линейная целевая функция F достигает максимума (минимума).
F = c1x1+c2x2 max(min) при ограничениях на переменные
[ Cкачайте файл, чтобы посмотреть картинку ]
Среди ограничений могут одновременно встречаться знаки
·,
· и =. Коэффициенты aij, bi, cj (i = 1..m, j = 1,2) - любые действительные числа (возможно и 0).
Двумерные задачи линейного программирования обычно решаются графически и решение связано со свойствами выпуклых множеств.
Множество точек называется выпуклым, если оно вместе с любыми двумя точками содержит и их произвольную выпуклую комбинацию.
Геометрический смысл этого определения состоит в том, что множеству вместе с его произвольными точками полностью при надлежит и прямолинейный отрезок, их соединяющий. Приме рами выпуклых множеств являются прямолинейный отрезок, полуплоскость, круг, шар, куб, полупространство и др.
Множество планов основной задачи линейного программи рования является выпуклым (если оно не пусто). Непустое мно жество планов называется многогранником решений, а всякая угловая точка многогранника решений - вершиной.
Если основная задача линейного программирования имеет оптимальный план, то целевая функция задачи принимает мак симальное значение в одной из вершин многогранника решений. Если максимальное значение достигается более чем в одной вершине, то целевая функция принимает его во всякой точке, являющейся выпуклой линейной комбинацией этих вершин.
Алгоритм решения двумерной задачи линейного программирования графическим методом
Решение задачи линейного программирования графическим методом включает следующие этапы.
1. На плоскости Х1ОХ2 строят прямые, уравнения которых получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств.
2. Находят полуплоскости, определяемые каждым из огра ничений задачи.
3. Строят многоугольник решений.
4. Строят векторN(с1, c2), который указывает направление возрастания целевой функции.
5. Строят начальную прямую целевой функции с1х1 + с2х2 =0 и затем передвигают ее в направлении вектора N до крайней угловой точки многоугольника решений. В результате находят точку, в которой целевая функция принимает максимальное значение, либо множество точек с одинаковым максимальным значением целевой функции, если начальная прямая сливается с одной из сторон многоугольника решений, либо устанавливают неограниченность сверху функции на множестве планов.
6. Определяют координаты точки максимум функции и вычисляют значение целевой функции в этой точке.
Минимальное значение линейной функции цели находится путем передвижения начальной прямой с1х1 + с2х2 = 0 в направлении, противоположном вектору N(c1,c2).
Замечание 1: В алгоритме решения пункты 4-6 можно выполнять следующим образом:
4. Найти значение целевой функции в угловых точках многогранника решений.
5. Точка, в которой функция принимает наибольшее значение и является точкой максимума.
Замечание 2: При решении двумерных задач линейного программирования возможны следующие ситуации (ОДР – область допустимых решений):
[ Cкачайте файл, чтобы посмотреть картинку ]
Пример решения задачи ЛП графическим методом
Найдите максимум и минимум линейной функ ции
при условиях-ограничениях:
Решение. Построим на плоскости Х1ОХ2 многоугольник решений. Для этого в неравенствах системы ограничений и условиях неотрицательности переменных знаки неравенств заменим на знаки точных равенств.
Построив прямые системы, найдем соответствующие полуплоскости и их пересечение.
Многоугольником решений задачи является пятиугольник АВСДЕ, координаты точек которого удовлетворяют условию неотрицательности переменных и неравенствам системы ограничений задачи.
Для нахождения точек экстремума построим начальную прямую F(13 EMBED Equation.3 1415)=-2х1+4х2= 0 и вектор N(-2,4). Передвигая прямую F(13 EMBED Equation.3 1415)=0 в направлении вектора N, найдем точку С, в которой начальная прямая принимает положение опорной прямой. Следовательно, в точке С целевая функция имеет максимальное значение. Так как точка С получена в результате пересечения прямых 1 и 2, то ее координаты удовлетворяют уравнениям этих прямых:
Решив систему уравнений, получим: х1 =3,4; х2 = 4,2; откуда найдем максимальное значение целевой функции Fmax(13 EMBED Equation.3 1415) = - 2 3,4+ 4 4,2 =10.
По условию задачи начальная прямая параллельна прямой (2), так как коэффициенты при переменных x1, x2 пропорциональны: -2/-1 = 4/2 = 2. Следовательно, начальная прямая займет положение опорной прямой в точках В, С и в любой точке отрезка ВС, в которых F(13 EMBED Equation.3 1415) принимает одно и то же максимальное значение. Для определения координат точки В решим систему двух линейных уравнений:
Максимальное значение целевой функции в точке В равно:
F(13 EMBED Equation.3 1415) = -2 . 0 + 4 .2,5 =10.
Запишем множество оптимальных решений как линейную выпуклую комбинацию углов точек отрезка ВС:
Подставив координаты угловых точек, получим:
Подставляя любые значения а от 0 до 1, получим координаты множества точек отрезка ВС, в каждой из которых целевая функция принимает максимальное значение, равное 10.
Для нахождения минимального значения целевой функции задачи перемещаем начальную прямую в направлении, противоположном вектору N(c1, c2). Начальная прямая займет положение опорной прямой в вершине Д, где х1 = 2, хг = 0, а минимальное значение целевой функции равно:
.
Пример: Решить задачу ЛП графическим методом:
Фирма выпускает два вида продукции А и В. Суточные ресурсы фирмы следующие:
610- единиц производственного оборудования;
620 - единиц сырья;
720- единиц электроэнергии.
Расходы каждого вида ресурсов на единицу продукции каждого типа представлены в табл.1:
ресурсы
Тип продукции
Запасы ресурсов
А
В
Оборудование
2
4
610
Сырье
1
5
620
э/ресурсы
3
2
720
Цена единицы продукции первого вида равна 8 ден.ед., а второго вида – 6ден.ед.
Сколько единиц продукции каждого вида необходимо произвести в сутки, чтобы выручка от реализации готовой продукции была максимальной?
Решение: Математическая модель задачи:
Пусть х1 – количество продукции первого вида, производимой в сутки;
х2 – количество продукции второго вида, производимой в сутки.
Найти х1, х2, дающие максимум целевой функции 13 EMBED Equation.3 1415 при ограничениях:
13 EMBED Equation.3 1415
Геометрическое решение задачи
В системе координат Х1ОХ2 строим график линейной зависимости, полученной переходом от неравенств к равенствам:
13 EMBED Equation.3 1415 (1)
13 EMBED Equation.3 1415 (2)
(3)
(1)
х1
0
305
х2
152.5
0
(2)
х1
0
620
х2
124
0
(3)
х1
0
240
х2
360
0
Штриховкой выделяем область определения задачи.
Строим прямую, полученную с использованием целевой функции для F=0:
13 EMBED Equation.3 1415
х1
0
150
х2
0
-200
График данной линейной зависимости (F=0) перемещаем параллельно самому себе до вершины с максимальным значением целевой функции.
Получаем точку А, координаты которой и соответствуют оптимальному решению задачи.
Найдем координаты т.А. В ней пересекаются линии (1), (3)
13 EMBED Equation.3 1415
Таким образом, А(207,5; 48,75).
Подставляя значение переменных в целевую функцию, получим13 EMBED Equation.3 1415
Вывод: Продукции первого вида А должно быть произведено 207.5ед., второго вида – 148.75 ед. Максимальная выручка от реализации продукции составит 1952.5 ден.ед.
Пример: Решить задачу ЛП графическим методом:
Фабрика выпускает продукцию двух видов: П1 и П2. Продукция обоих видов поступает в оптовую продажу. Для производства этой продукции используются три исходных продукта - А, В, С. Максимально возможные суточные запасы этих продуктов составляют 6, 8 и 5 т соответственно. Расходы сырья А, В, С на 1 тыс. изделий П1 и П2 приведены в таблице.
Исходный продукт
Расход исходных продуктов на 1 тыс. изделий (т.) П1 П2
Максимально воз можный запас (т.)
А
1
2
6
В
2
1
8
С
1
0.8
5
Изучение рынка сбыта показало, что суточный спрос на изделия П2 никогда не превышает спроса изделия П1 более чем на 1 тыс. шт. Кроме того, установлено, что спрос на изделия П2 никогда не превышает 2 тыс. шт. в сутки.
Оптовые цены 1 тыс. шт. изделий П1 равны 3 тыс. руб., 1 тыс. шт. П2 - 2 тыс. шт.
Какое количество изделий (в тыс. шт.) каждого вида должна производить фабрика, чтобы доход от реализации продукции был максимальным?
Решение: Математическая модель задачи:
Определить суточные объемы производства (13 EMBED Equation.DSMT4 1415и 13 EMBED Equation.DSMT4 1415) изделий П1 и П2 в тыс. шт., при которых достигается
13 EMBED Equation.DSMT4 1415 - (целевая функция)
при
13 EMBED Equation.DSMT4 1415
ограничения
Графический метод решения ЗЛП
Графическим методом целесообразно решать ЗЛП, содержащие не более двух пе ременных.
Алгоритм графического метода рассмотрим применительно к задаче:
13 EMBED Equation.DSMT4 1415
при
13 EMBED Equation.DSMT4 1415
Шаг 1. Строим область допустимых решений - область Р, т.е. геометриче ское место точек, в котором одновременно удовлетворяются все ограничения ЗЛП. Каж дое из неравенств (а)-(д) системы ограничений задачи геометрически определяет полуплоскость соответственно с граничными прямыми:
13 EMBED Equation.DSMT4 1415
Условия неотрицательности переменных (е) ограничивают область допустимых решений первым квадратом. Области, в которых выполняются соответствующие ограни чения в виде неравенств, указываются стрелками, направленными в сторону допус тимых значений переменных (см. на рис.).
13 EMBED Equation.DSMT4 1415
откуда 13 EMBED Equation.DSMT4 1415 или 13 EMBED Equation.DSMT4 1415.
Подставляя значения 13 EMBED Equation.DSMT4 1415 и 13 EMBED Equation.DSMT4 1415 в функцию 13 EMBED Equation.DSMT4 1415, найдем
13 EMBED Equation.DSMT4 1415.
Тема лекции «Методы решения задач ЛП. Симплекс-метод»
План лекции
Симплекс-метод линейного программирования.
Алгоритм симплексного метода включает следующие этапы:
Пример решения задачи симплекс-методом.
Симплекс-метод линейного программирования
Для решения задач линейного программирования предложе но немало различных алгоритмов. Наиболее эффективным сре ди них является алгоритм, известный под названием симплексный метод, или метод последовательного улучшения плана.
Впервые симплексный метод был предложен американским ученым Дж. Данцингом в 1949 г., однако еще в 1939 г. идеи метода были разработаны российским математиком Л.В. Канто ровичем.
Симплексный метод - это итерационный процесс, который начинается с одного решения и в поисках лучшего варианта движется по угловым точкам области возможных решений до тех пор, пока не достигнет оптимального значения, в частности по угловым точкам многоугольника решений, полученного гео метрическим методом.
В тех случаях, когда модель содержит т уравнений, для построения пробных решений используются т переменных, принимающих некоторые положительные значения при нулевых значениях остальных переменных. Вначале допустим, что решение существует, причем оптимальное значение целевой функции конечно.
В этом случае вычислительная процедура может быть представлена в следующей последовательности.
1. Выберем т переменных, задающих допустимое пробное решение, и исключим эти переменные из целевой функции.
2. Проверим, нельзя ли за счет одной из переменных, при равненной вначале к нулю, улучшить значение целевой функ ции, придавая ей отличные от нуля (причем положительные) значения. Если это возможно, перейдем к третьему этапу, в противном случае прекратим вычисления.
3. Найдем предельное значение переменной, за счет которой можно улучшить значение целевой функции. Увеличение зна чения этой переменной допустимо до тех пор, пока одна из т переменных, вошедших в пробное решение, не обратится в нуль. Исключим из выражения для целевой функции только что упо мянутую переменную и введем в пробное решение ту перемен ную, за счет которой результат может быть улучшен.
4. Разрешим систему т уравнений относительно перемен ной, вошедшей в новое пробное решение. Исключим эту пере менную из выражения для целевой функции. Вернемся ко вто рому этапу.
Важно отметить, что при однозначном понимании данного предписания предложенный алгоритм действительно приводит к оптимальному решению для любой модели линейного програм мирования за конечное число итераций, если система ограниче ний задачи совместна.
Симплексный метод основан на последовательном переходе от одного опорного плана задачи линейного программирования к другому, при этом значение целевой функции изменяется. Рассмотрим алгоритм симплексного метода на примере задачи планирования товарооборота.
Коммерческое предприятие реализует п товарных групп, располагая т ограниченными материально-денежными ресурса ми bi > 0 (i = 1,,m). Известны расходы ресурсов каждого i-вида на реализацию единицы товара по каждой группе, представленной в виде матрицы А = (аij), и прибыль cj, получаемая предприятием от реализации единицы товара j группы. Надо определить объем и структуру товарооборота xj (j = 1,,n) при которых прибыль коммерческого предприятия была бы максимальной.
Математическую модель задачи запишем следующим образом.
Определить вектор 13 EMBED Equation.3 1415= (х1, х2,..., хn), который удовлетворя ет ограничениям вида
и обеспечивает максимальное значение целевой функции
Алгоритм симплексного метода
Алгоритм симплексного метода включает следующие этапы:
1. Составление первого опорного плана. Система ограниче ний задачи, решаемой симплексным методом, задана в виде системы неравенств смысла «<», правые части которых bi > 0. Перейдем от системы неравенств к системе уравнений путем введения неотрицательных дополнительных переменных. Век торы-столбцы при этих переменных представляют собой единич ные векторы и образуют базис, а соответствующие им перемен ные называются базисными:
Решим эту систему относительно базисных переменных:
а функцию цели перепишем в виде уравнения
Полагая, что основные переменные х1 =х2 = х3 =... хп =0, получим первый опорный план Х1 = (0, 0, ...,0, b1, b2, ..., bт); F(X1) = 0, который заносим в симплексную табл. Она со стоит из коэффициентов системы ограничений и свободных членов. Последняя строка таблицы называется индексной и за полняется коэффициентами функции цели, взятыми с противо положным знаком.
2. Проверка плана на оптимальность. Если все коэффици енты индексной строки симплексной таблицы при решении за дачи на максимум неотрицательны (> 0), то план является опти мальным. Если найдется хотя бы один коэффициент индексной строки меньше нуля, то план не оптимальный и его можно улуч шить. В этом случае переходим к следующему этапу алгоритма.
3. Определение ведущих столбца и строки. Из отрицатель ных коэффициентов индексной строки выбираем наибольший по абсолютной величине, что и определяет ведущий столбец, кото рый показывает, какая переменная на следующей итерации перейдет из свободных в базисные.
Затем элементы столбца свободных членов симплексной таблицы делим на элементы того же знака (+/+; "/-) ведущего столбца. Результаты заносим в отдельный столбец di, которые будут всегда положительные. Строка симплексной таблицы, соответствующая минимальному значению di, является ведущей. Она определяет переменную xi, которая на следующей итерации выйдет из базиса и станет свободной.
Элемент симплексной таблицы, находящийся на пересече нии ведущих столбца и строки, называют разрешающим и вы деляют кружком.
4. Построение нового опорного плана. Переход к новому плану осуществляется в результате пересчета симплексной таб лицы методом Жордана - Гаусса. Сначала заменим переменные в базисе, т. е. вместо хi , в базис войдет переменная хj, соответ ствующая ведущему столбцу.
Разделим все элементы ведущей строки предыдущей симплек сной таблицы на разрешающий элемент и результаты деления занесем в строку следующей симплексной таблицы, соответствую щую введенной в базис переменной xj. В результате этого на месте разрешающего элемента в следующей симплексной таблице будем иметь 1, а в остальных клетках j столбца, включая клетку столбца индексной строки, записываем нули. Остальные новые элементы нового плана находятся по правилу прямоугольника:
где СТЭ - элемент старого плана, РЭ - разрешающий элемент, А и В - элементы старого плана, образующие прямоугольник с эле ментами СТЭ и РЭ.
Далее возвращаемся ко второму этапу алгоритма провер ке плана на оптимальность.
При решении задачи линейного программирования на ми нимум целевой функции признаком оптимальности плана явля ются отрицательные значения всех коэффициентов индексной строки симплексной таблицы.
Если в ведущем столбце все коэффициенты aij
·0, то функ ция цели F(X) не ограничена на множестве допустимых планов, т. е. F(X) стремится к бесконечности и задача не имеет решения.
Если в столбце di симплексной таблицы содержатся два или несколько одинаковых наименьших значения, то новый опорный план будет вырожденным (одна или несколько базисных перемен ных станут равными нулю). Вырожденные планы могут привес ти к зацикливанию, т. е. к многократному повторению процесса вычислений, не позволяющему получить оптимальный план. С целью исключения этого для выбора ведущей строки используют метод Креко, который заключается в следующем. Элементы строк, имеющие одинаковые наименьшие значения di, делятся на предполагаемые разрешающие элементы, а результаты заносят ся в дополнительные строки. За ведущую строку выбирается та, в которой раньше встретится наименьшее частное при чтении таблицы слева направо по столбцам. Например, таблица, содер жащая три равных значения di = 2, имеет следующий вид:
Допустим, разрешающим столбцом является х7, который вво дится в новый план, тогда разрешающим элементом может быть: 2, 4 или 5. Следуя указанному правилу, получится таблица:
Сравниваем последовательно слева направо полученные ча стные по столбцам. В первом и втором столбцах все частные одинаковы, а в третьем столбце наименьшее частное 1,5 в пер вой строке, следовательно, эта строка и будет разрешающей с разрешающим элементом 2.
Если в оптимальный план вошла дополнительная перемен ная хп+1, то при реализации такого плана имеются недоисполь зованные ресурсы i-ro вида в количестве, полученном в столбце свободных членов симплексной таблицы.
Если в индексной строке симплексной таблицы оптималь ного плана находится нуль, принадлежащий свободной перемен ной, не вошедшей в базис, а в столбце, содержащем этот нуль, имеется хотя бы один положительный элемент, то задача имеет множество оптимальных планов. Свободную переменную, соот ветствующую указанному столбцу, можно внести в базис, вы полнив соответствующие этапы алгоритма. В результате будет получен второй оптимальный план с другим набором базисных переменных.
Пример решения задачи симплекс-методом
Коммерческое предприятие, располагающее материально-денежными ресурсами, реализует три группы товаров А, В, С. Плановые нормативы затрат ресурсов на 1 тыс. руб. товарооборота, а также объем ресурсов заданы в таблице.
Определите плановый объем продажи и структуру товарооборота так, чтобы доход торгового предприятия был максимальный.
Виды материально-денежных ресурсов
Норма затрат материально-денежных ресурсов на 1 тыс. руб. товарооборота
Объем ресурсов b1
Группа A
Группа B
Группа C
Рабочее время продавцов, Чел.-ч.
0,1
3
0.4
1100
Площадь торговых залов, м2
0,05
0.2
0.02
120
Площадь складских помещений, м
3
0.02
2
8000
Доход, тыс.руб.
3
1
4
Max
Решение: Запишем математическую модель задачи.
Определим вектор 13 EMBED Equation.3 1415, который удовлетворяет условиям
13 EMBED Equation.3 1415
и обеспечивает максимальное значение целевой функции
13 EMBED Equation.3 1415.
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных x4, x5, x6:
13 EMBED Equation.3 1415
Матрица коэффициентов A=(aij) этой системы у равнений имеет следующий вид:
13 EMBED Equation.3 1415
Векторы 13 EMBED Equation.3 1415 - линейно независимы, так как определитель, составленный из компонент этих векторов, отличен от нуля. Следовательно, соответствующие этим векторам переменные x4, x5, x6 являются базисными и в этой задаче определяют объемы неиспользованных ресурсов.
Решим систему уравнений относительно базисных переменных.
13 EMBED Equation.3 1415
Функцию цели запишем в виде уравнения:
13 EMBED Equation.3 1415
Полагая, что свободные переменные x1=0, x2=0, x3=0, получим первый опорный план 13 EMBED Equation.3 1415 13 EMBED Equation.3 1415, в котором базисные переменные x4=1100, x5=120, x6=8000. Следовательно, товары не продаются, доход равен нулю, а ресурсы не используются. Полученный первый опорный план запишем в симплексную таблицу.
План
Базисные переменные
Значения базисных переменных
Значение коэффициентов при
13 EMBED Equation.3 1415
X1
X2
X3
X4
X5
X6
I
x4
x5
x6
1100
120
8000
0,1
0,05
3
0,2
0,02
1
0,4
0,02
2
1
0
0
0
1
0
0
0
1
5500
6000
8000
Индексная строка
13 EMBED Equation.3 1415
0
-3
13 EMBED Equation.3 1415
-4
0
0
0
II
x2
x5
x6
5500
10
2500
0,5
0,04
2,5
1
0
0
2
-0,02
0
5
-0,1
-5
0
1
0
0
0
1
11000
250
1000
Индексная строка
13 EMBED Equation.3 1415
27500
13 EMBED Equation.3 1415
0
6
25
0
0
III
x2
x1
x6
5375
250
1875
0
1
0
1
0
0
2,25
-0,5
1,25
6,25
-2,5
1,25
-12,5
25
-62,5
0
0
1
Индексная строка
13 EMBED Equation.3 1415
27625
0
0
5,75
23,75
12,5
0
Первый опорный план неоптимальный, так как в индексной строке находятся отрицательные коэффициенты: -3, -5, -4.
За ведущий столбец выберем столбец, соответствующий переменной x2, так как, сравнивая по модулю, имеем: |-5|>{|-3|,|-4|}.
Вычислим значения di по строкам как частное от деления 13 EMBED Equation.3 1415 и из них выберем наименьшее:
13 EMBED Equation.3 1415
Следовательно, первая строка является ведущей.
Разрешающий элемент равен 0,2 и находится на пересечении ведущего столбца и ведущей строки и выделен в таблице.
Формируем следующую часть симплексной таблице. Вместо переменной x4 в план II войдет переменная x2. Строка, соответствующая переменной x2 в плане II, получена в результате деления всех элементов строки x4 плана I на разрешающий элемент РЭ=0,2. На месте разрешающего элемента в плане II получаем 1. В остальных клетках столба x2 плана II записываем нули.
Таким образом, в новом плане II заполнены строки x2 и столбец x2. Все остальные элементы нового плана II, включая элементы индексной строки, определяются по правилу прямоугольника. Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ=0,2. Во второй вершине по диагонали находится старое значение элемента, например, значение целевой функции F(K1)=0=СЭ, которое указывает на место расположения нового НЭ в новом плане II. Третий элемент А=1100 и четвертый элемент В=-5 завершают построение прямоугольника в недостающих двух вершинах и расположены по диагонали. Значение нового элемента в плане II находится из выражения:
13 EMBED Equation.3 1415
Элементы строки определяются аналогично:
13 EMBED Equation.3 1415 13 EMBED Equation.3 1415 13 EMBED Equation.3 1415 13 EMBED Equation.3 1415
Все элементы, расположенные на пересечении строк и столбцов, соответствующих одноименным базисным элементам, равны 1, остальные элементы столбца в базисах векторов, включая индексную строку, равны 0. Аналогично проводятся расчеты по всем строкам таблицы, включая индексную.
Выполняя последовательно все этапы алгоритма, формулируем план II.
На третьей итерации табл. получаем план III, который является оптимальным, так как все коэффициенты в индексной строке 13 EMBED Equation.3 1415 0.
Оптимальный план можно записать так:
13 EMBED Equation.3 1415
Следовательно, необходимо продавать товаров первой группы А 250 ед., а второй группы В – 5375 ед. При этом торговое предприятие получает максимальный доход в размере 27625 тыс. руб. Товары группы С не реализуются.
В оптимальном плане среди базисных переменных находится дополнительная переменная x6. Это указывает на то, что ресурсы третьего вида (площадь складских помещений) недоиспользована на 1875 м2, так как переменная x6 была введена в третье ограничение задачи, характеризующее собой использование складских помещений этого ресурса.
В индексной строке оптимального плана в столбцах переменных x3, x4, x5, не вошедших в состав базисных, получены ненулевые элементы, поэтому оптимальный план задачи линейного программирования является единственным.
Вопросы для самоконтроля по теме:
Какие задачи линейного программирования можно решать симплексным методом?
Каков признак оптимальности в симплексном методе?
Как строится опорный план?
Как определяется ведущий столбец и ведущая строка симплексной таблице?
Как осуществляется перерасчет элементов симплексной таблицы?
Каковы основные случаи при реализации симплексного метода?
Тема лекции «Транспортная задача. Метод потенциалов»
План лекции
Построение математической модели транспортной задачи.
Методы решения транспортных задач.
Метод потенциалов решения транспортных задач.
Вырожденность в транспортной задаче.
Построение математической модели транспортной задачи
Мы рассмотрели общие подходы к решению задач линейного программирования. Однако существуют частные типы задач линейного программирования, которые в силу своей структуры допускают решения более простыми методами. Мы остановимся только на одной из них – так называемой транспортной задаче.
Постановка транспортной задачи
Однородный груз, имеющийся в m пунктах отправления (производства) А1, А2, ..., Аm соответственно в количествах а1, а2, ..., аm единиц, требуется доставить в каждый из n пунктов назначения (потребления) В1, В2, ..., Вn соответственно в количествах b1, b2, ..., bn единиц. Стоимость перевозки (тариф) единицы продукции из Аi в Вj известна для всех маршрутов Ai, Bj и cij (i = 1, m; j = 1, n). Требуется составить такой план перевозок, при котором весь груз из пунктов отправления вывозится, и запросы всех пунктов потребления удовлетворяются (закрытая модель), т. е:
[ Cкачайте файл, чтобы посмотреть картинку ]
а суммарные транспортные расходы минимальны.
Математическая модель транспортной задачи
[ Cкачайте файл, чтобы посмотреть картинку ]
Будем называть любой план перевозок допустимым, если он удовлетворяет системам ограничений и требованиям неотрицательности.
Допустимый план, будем называть опорным, если в нем отличны от нуля не более m+n-1 базисных перевозок, а остальные перевозки равны 0.
План будет называться оптимальным, если он, среди всех допустимых планов, приводит к минимальной суммарной стоимости перевозок.
Методы решения транспортных задач
Так как транспортная задача является задачей линейного программирования, то её можно решать симплекс-методом, но в силу своей особенности её можно решить гораздо проще.
Условия задачи удобно располагать в таблице, вписывая в ячейки количество перевозимого груза из Аi в Bj груза Xij
· 0, а в маленькие клетки – соответствующие тарифы Cij.
[ Cкачайте файл, чтобы посмотреть картинку ]
Затем решение задачи разбивается на два этапа:
Определение опорного плана.
Нахождение оптимального решения путем последовательных операций.
Найдем вначале допустимое (опорное) решение транспортной задачи. Это решение можно найти, используя метод "северо-западного угла" или метод "минимального элемента".
Метод северо-западного угла (диагональный)
Сущность метода заключается в том, что на каждом шаге заполняется левая верхняя (северо-западная) клетка оставшейся части таблицы, причем максимально возможным числом: либо полностью выносится груз из Аi, либо полностью удовлетворяется потребность Вj. Процедура продолжается до тех пор, пока на каком-то шаге не исчерпаются запасы аi и не удовлетворятся все потребности bj. В заключении проверяют, удовлетворяют ли найденные компоненты плана Хij горизонтальным и вертикальным уравнениям.
Пример: Фирма должна отправить некоторое количество кроватей с трёх складов в пять магазинов. На складах имеется соответственно 15, 25 и 20 кроватей, а для пяти магазинов требуется соответственно 20, 12, 5, 8 и 15 кроватей. Стоимость перевозки одной кровати со склада в магазин приведены в таблице.
Склады
Магазины
B1
B2
B3
B4
B5
A1
1
0
3
4
2
A2
5
1
2
3
3
A3
4
8
1
4
3
Как следует спланировать перевозку, чтобы её стоимость была минимальной?
Решение: Построим опорный план.
Исходная транспортная таблица:
[ Cкачайте файл, чтобы посмотреть картинку ]
Построение второй транспортной таблицы
Магазин В1 подал заявку на 20 кроватей, но со склада А1 мы можем перевести 15 кроватей, ещё 5 кроватей мы перевезём со склада А2. Спрос для магазина В1 удовлетворён. Рассмотрим магазин В2. В него необходимо доставить 12 кроватей - доставим их со склада А2.
На складе А2 осталось 8 кроватей. Выделим из них пять для магазина В3. На складе А2 осталось 3 кровати. Выделим их на магазин В3, но потребности магазина ещё не удовлетворены, поэтому выделим ему со склада А3 ещё пять кроватей. Осталось 15 кроватей, столько, сколько требуется в магазин В5.
[ Cкачайте файл, чтобы посмотреть картинку ]
Построенный план является допустимым, так как все заявки удовлетворены, все запасы израсходованы.
Проверим, является ли полученный план опорным: количество ячеек с ненулевыми перевозками равно m+n-1 = 7.
Опорный план: Х11 = 15, Х21 = 5, Х22 = 12, Х23 = 5, Х24 = 3, Х34 = 5, Х35 = 15. Все остальные Xij = 0.
F = 1*15+5*5+1*12+2*5+3*3+4*5+3*15 = 136
Метод наименьшего элемента
Сущность метода в том, что на каждом шаге заполняется та клетка оставшейся части таблицы, которая имеет наименьший тариф; в случае наличия нескольких таких равных тарифов заполняется любая из них. В остальном действуют аналогично предыдущему способу.
Пример: см. предыдущий пример
Решение: Построим опорный план.
Исходная транспортная таблица:
[ Cкачайте файл, чтобы посмотреть картинку ]
Построение второй транспортной таблицы
Находим в таблице наименьшую стоимость перевозки – это 0 в клетке A1B2. Записываем в этой клетке значение 12 (наименьшее из сумм по строке и столбцу).
[ Cкачайте файл, чтобы посмотреть картинку ]
Теперь вычеркиваем второй столбец, уменьшив сумму в первой строке на 12.
[ Cкачайте файл, чтобы посмотреть картинку ]
Находим следующую наименьшую по стоимости ячейку – их несколько, например, A1B1. Присваиваем ей значение 3, а сумму по столбцу заменяем на 17.
[ Cкачайте файл, чтобы посмотреть картинку ]
Вычеркиваем первую строку.
[ Cкачайте файл, чтобы посмотреть картинку ]
Выбираем ячейку A3B3, присваиваем ей значение 5. Вычеркиваем третий столбец. Сумму по третьей строке заменяем на 15.
[ Cкачайте файл, чтобы посмотреть картинку ]
Выбираем ячейку A2B5, записываем в ней 15, уменьшаем вторую строку на 15 и вычеркиваем пятый столбец.
[ Cкачайте файл, чтобы посмотреть картинку ]
Выбираем ячейку A3B1, присваиваем ей 15. Уменьшаем первый столбец на 15 и вычеркиваем третью строку.
[ Cкачайте файл, чтобы посмотреть картинку ]
Ячейке A2B1 присваиваем 2 и вычеркиваем первый столбец. Сумму по второй строке заменяем на 8.
[ Cкачайте файл, чтобы посмотреть картинку ]
Ячейке A2B4 присваиваем 8 и вычеркиваем четвертый столбец.
[ Cкачайте файл, чтобы посмотреть картинку ]
Опорный план построен.
Х11 = 3, Х12 = 12, Х21 = 2, Х24 = 8, Х25 = 15, Х31 = 15, Х33 = 5.
Все остальные Хij = 0.
F = 3*1+0*12+5*2+3*8+3*15+5*1 = 147
2. Найдём теперь оптимальный план для данной задачи.
Для этого воспользуемся методом потенциалов.
Метод потенциалов решения транспортных задач
[ Cкачайте файл, чтобы посмотреть картинку ] (1)
Соотношения (1) определяют систему из m+n-1 линейных уравнений с m+n известными, имеющую бесчисленное множество решений; для её определённости одному неизвестному присваивают произвольное значение (обычно альфа равное 0), тогда все остальные неизвестные определяются однозначно.
Метод потенциалов:
Введем строку потенциалов ui и столбец потенциалов vj. Полагая, что u1=0, а остальные ui и vj найдем так, чтобы
а) для заполненных ячеек выполнялись равенства 13 EMBED Equation.3 1415;
б) для незаполненных ячеек выполнялись равенства 13 EMBED Equation.3 1415
Критерий оптимальности
Если известны потенциалы решения Х0 транспортной задачи и для всех незаполненных ячеек выполняются условия 13 EMBED Equation.3 1415то Х0 является оптимальным планом транспортной задачи.
Если план не оптимален, то необходимо перейти к следующему плану (таблице) так, чтобы транспортные расходы не увеличивались.
Цикл перерасчёта таблицы – это последовательность ячеек, удовлетворяющая условиям:
Одна ячейка пустая, все остальные занятые.
Любые две соседние ячейки находятся в одной строке или в одном столбце.
Пустой ячейке присваивают знак "+", остальным – поочерёдно знаки "–" и "+".
Для перераспределения плана перевозок с помощью цикла перерасчёта сначала находят незаполненную ячейку (r, s), в которой
·r+
·s > Crs, и строят соответствующий цикл; затем в минусовых клетках находят число X = min(Xij). Далее составляют новую таблицу по следующему правилу:
В плюсовых клетках добавляем Х.
Из минусовых клеток вычитаем Х.
Все остальные клетки вне цикла остаются без изменения.
Получим новую таблицу, дающую новое решение Х, такое, что F (X1)
· F (X0); оно снова проверяется на оптимальность через конечное число шагов, обязательно найдем оптимальный план транспортной задачи, ибо он всегда существует.
Найдём оптимальный план для рассмотренной выше задачи. В качестве опорного плана возьмем план, полученный с помощью метода "минимального элемента" Х11 = 3, Х12 = 12, Х21 = 2, Х24 = 8, Х25 = 15, Х31 = 15, Х33 = 5. Все остальные элементы равны 0.
Так как у нас получились отрицательные значения, то полученный план не является оптимальным. Выберем ячейку для пересчета A2B2. Получим:
[ Cкачайте файл, чтобы посмотреть картинку ]
X = min(2, 12) = 2
Строим следующую транспортную таблицу.
[ Cкачайте файл, чтобы посмотреть картинку ]
Проверим полученный план на оптимальность с помощью метода потенциалов.
Т.к. есть отрицательные оценки пустых ячеек, то построенный план не является оптимальным, следовательно, производим пересчет. Выберем ячейку A3B5.
X = min(15, 10, 15) = 10, значит вычитать и прибавлять в ячейках, будем 10.
Строим следующую транспортную таблицу.
[ Cкачайте файл, чтобы посмотреть картинку ]
Проверим построенный план на оптимальность.
Т.к. отрицательных оценок пустых ячеек нет, то полученный план является оптимальным. Х11 = 15, Х22 = 12, Х24 = 8, Х25 = 5, Х31 = 5, Х33 = 5, Х35 = 10. Все остальные Хij = 0.
F = 1*15+1*12+3*8+3*5+4*5+1*5+3*10 = 121.
Вырожденность в транспортной задаче
Вырожденность в транспортной задаче возникает, когда одна или более базисных переменных обращаются в 0.
При построении первого базисного решения могут возникать трудности, если суммы по строкам и столбцам равны между собой и обратились в 0. В этом случае из дальнейшего рассмотрения следует исключить только одну из них. Другая сумма будет ликвидирована при присвоении базисной переменной значения 0. Поскольку на каждом шаге удаляется только одна строка или только один столбец, то в результате количество базисных переменных не меняется (даже если некоторые базисные переменные обратились в нуль).
Трудности могут возникать и при улучшении базисного допустимого плана. Применение правил может обратить в нуль более одной базисной переменной. В этом случае, важно помнить, что только одна из них должна стать не базисной, остальные следует сохранить базисными, но с нулевыми значениями.
Вопросы для самоконтроля по теме:
Приведите пример транспортной задачи.
Когда транспортная задача называется вырожденной?
В чем суть метода потенциалов?
Что находится изначально: опорный план перевозок или оптимальный план перевозок?
Практические занятия
Практическое занятие №3 «Выбор и обоснование наиболее рационального метода и алгоритма решения задачи, а также оценка сложности выбранного алгоритма: геометрический метод, симплекс метод»
Практическое занятие №4 «Выбор и обоснование наиболее рационального метода и алгоритма решения транспортной задачи, а также оценка сложности выбранного алгоритма: метод потенциалов»
Тема 2.2 Нелинейное программирование
Основные понятия и термины по теме: целевая функция, условия-ограничения, область допустимых решений, оптимальное решение.
План изучения темы (перечень вопросов, обязательных к изучению):
Общий вид задач НП. Метод множителей Лагранжа. Разработка алгоритма для решения различных практических задач НП с применением математических методов. Общий вид задач нелинейного программирования. Графический метод решения задач нелинейного программирования.
Условный экстремум. Функция Лагранж. Метод множителей Лагранжа
Теоретический материал
Тема лекции «Общий вид задач НП. Метод множителей Лагранжа»
План лекции
Нелинейное программирование.
Задачи безусловной однопараметрической оптимизации.
Экстремумы функции двух переменных.
Нелинейное программирование
Задачами нелинейного программирования называются задачи математического программирования, в которых нелинейными являются и (или) целевая функция, и (или) ограничения в виде неравенств или равенств.
Задачи нелинейного программирования можно классифицировать в соответствии с видом функции F(x), функциями ограничений и размерностью вектора х (вектора решений).
В самом общем виде классификация представлена в таблице.
Вид F(x)
Вид функции ограничений
Число переменных
Название задачи
Нелинейная
Отсутствуют
1
Безусловная однопараметрическая оптимизация
Нелинейная
Отсутствуют
Более 1
Безусловная многопараметрическая оптимизация
Нелинейная или линейная
Нелинейные или линейные
Более 1
Условная нелинейная оптимизация
Общих способов решения, аналогичных симплекс-методу линейного программирования, для нелинейного программирования не существует.
В каждом конкретном случае способ выбирается в зависимости от вида функции F(x).
Задачи нелинейного программирования на практике возникают довольно часто, когда, например, затраты растут непропорционально количеству закупленных или произведённых товаров.
Многие задачи нелинейного программирования могут быть приближены к задачам линейного программирования, и найдено близкое к оптимальному решению. Встречаются задачи квадратичного программирования, когда функция есть F(x) полином 2-ой степени относительно переменных, а ограничения линейны. В ряде случаев может быть применён метод штрафных функций, сводящий задачу поиска экстремума при наличии ограничений к аналогичной задаче, которая при отсутствии ограничений обычно решается проще.
Но в целом задачи нелинейного программирования относятся к трудным вычислительным задачам. При их решении часто приходится прибегать к приближенным методам оптимизации. Мощным средством для решения задач нелинейного программирования являются численные методы. Они позволяют найти решение задачи с заданной степенью точности.
Задачи безусловной однопараметрической оптимизации
Для нахождения максимума и минимума функции F(x) строится её график. Для построения графика необходимо исследовать функцию. Ниже приведена схема исследования графика:
Нахождение области значения функции.
Нахождение области определения.
Исследование на четность и нечетность.
Исследование на периодичность.
Нахождение точек пересечения с осями, нахождение интервалов знакопостоянства функции (отрицательна, положительна).
Нахождение критических точек (точек подозрительных на экстремум) и локальных точек максимума и минимума, промежутки возрастания и убывания функции.
Нахождение второй производной и промежутков выпуклости и вогнутости.
Нахождение точек разрыва и асимптот (если такие есть).
Несколько точек для контроля.
Пример
Построить график функции у = х2+2х-3.
Решение
Функция определена на интервале от минус бесконечности до плюс бесконечности. Точек разрыва нет.
Имеем f(-x) = (-x)2+2(-x)-3 = x2-2x-3. Функция не является ни четной, ни нечетной, так как f(-x) не равно f(x) и f(x) не равно -f(x).
Найдем точки пересечения графика функции с осями координат. Если у = 0, то х2+2х-3 = 0, откуда х1 = -3, х2 = 1. Значит, кривая пересекает ось абсцисс в точках (-3, 0) и (1, 0). При х = 0, у = -3 (из равенства у = х2+2х-3), т. е. кривая пересекает ось ординат в точке (0, -3).
Найдем критические точки функции. Имеем у' = 2х+2, 2х+2 = 0, 2(х+1) = 0, х = -1.
Находим интервалы знакопостоянства функции.
[ Cкачайте файл, чтобы посмотреть картинку ]
f(-1) = fmin = -4.
Находим вторую производную: у" = 2, т. е. f" > 0. Следовательно, кривая вогнута на всей области определения и не имеет точек перегиба.
Построение графика.
[ Cкачайте файл, чтобы посмотреть картинку ]
Численный метод решения задачи – это определенная последовательность операций над числами.
Численные методы, позволяющие решить задачу в точной постановке, не вносят погрешностей в вычисления.
При исследовании функции делаем вывод: рассматриваемая функция должна быть дифференцируема.
Но на практике такие функции встречаются довольно редко, поэтому для решения задач нелинейного программирования применяются приближенные методы.
Бывает так, что решить задачу в точной постановке трудно или невозможно. Тогда её заменяют близкой по результатам приближенной задачей. Численный метод, реализующий такую приближённую задачу, называют приближённым методом. Такие методы вносят погрешности в вычисления.
Экстремумы функции двух переменных
Максимумом (минимумом) функции 13 EMBED Equation.3 1415 называется такое ее значение 13 EMBED Equation.3 1415, которое больше (меньше) всех других значений, принимаемых ею в точках, достаточно близких к точке 13 EMBED Equation.3 1415 и отличных от нее.
Максимум или минимум функции называется ее экстремумом. Точка, в которой достигается экстремум, называется точкой экстремума.
Точки экстремума функции двух переменных 13 EMBED Equation.3 1415 надо искать среди тех точек, лежащих внутри области ее определения, координаты которых удовлетворяют системе
13 EMBED Equation.3 1415 (1.2)
Точки, удовлетворяющие такой системе уравнений, называются стационарными.
Но не всякая такая точка действительно будет точкой максимума или минимума. Каждую стационарную точку надо специальным образом проверить. Для функции двух переменных проверка стационарной точки 13 EMBED Equation.3 1415 требует:
1) нахождения в этой точке значений вторых производных:
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415,
которые обозначим буквами 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415 соответственно;
2) определения знака 13 EMBED Equation.3 1415:
если 13 EMBED Equation.3 1415, то в стационарной точке 13 EMBED Equation.3 1415 нет экстремума;
если 13 EMBED Equation.3 1415, то экстремум есть, причем 13 EMBED Equation.3 1415, если 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415, если 13 EMBED Equation.3 1415;
если 13 EMBED Equation.3 1415, то ничего сказать нельзя – требуется дополнительное исследование.
Пример. Найти для функции 13 EMBED Equation.3 1415, точки максимума и минимума (если они существуют).
Решение.
1) Ищем частные производные:
13 EMBED Equation.3 1415 13 EMBED Equation.3 1415.
2) Для нахождения стационарных точек функции составим и решим систему (1.2). В нашем случае система имеет вид
13 EMBED Equation.3 1415
Первое уравнение выполняется в двух случаях: либо когда 13 EMBED Equation.3 1415, либо когда 13 EMBED Equation.3 1415 или 13 EMBED Equation.3 1415. В первом случае второе уравнение после подстановки нуля вместо 13 EMBED Equation.3 1415 приобретает вид 13 EMBED Equation.3 1415 и имеет решения 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415. Таким образом, в данном случае решениями системы будут пары чисел: 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, а стационарными точками функции 13 EMBED Equation.3 1415 – точки 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415.
Во втором случае, после замены 13 EMBED Equation.3 1415 на 13 EMBED Equation.3 1415 второе уравнение приобретает вид 13 EMBED Equation.3 1415. Оно имеет решения 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415. Так как 13 EMBED Equation.3 1415, то отсюда следует, что решениями системы будут пары чисел 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, а стационарными точками функции 13 EMBED Equation.3 1415 будут также точки 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415.
3) Следующий шаг – проверка каждой стационарной точки на экстремум. Найдем сначала формулы, выражающие вторые производные функции 13 EMBED Equation.3 1415:
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415 13 EMBED Equation.3 1415.
Приступим теперь к проверке точки 13 EMBED Equation.3 1415, для чего найдем соответствующие ей числа A, B, C:
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415.
13 EMBED Equation.3 1415 и, значит, в 13 EMBED Equation.3 1415 экстремума нет.
Аналогично проверяем точку 13 EMBED Equation.3 1415:
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415,13 EMBED Equation.3 1415.
13 EMBED Equation.3 1415 и, значит, в 13 EMBED Equation.3 1415 экстремума нет.
Точно также нет экстремума и в точке 13 EMBED Equation.3 1415, так как в ней 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415.
Наконец, для точки 13 EMBED Equation.3 1415 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415. Следовательно, в точке 13 EMBED Equation.3 1415 экстремум есть и, согласно теории, это максимум, так как 13 EMBED Equation.3 1415. При этом значение функции в точке максимума равно 13 EMBED Equation.3 1415.
Вопросы для самоконтроля:
Дайте определение задачам нелинейного программирования.
Существуют ли общие методы решения задач нелинейного программирования?
Приведите примеры задач безусловной однопараметрической оптимизации.
Что такое численный метод решения задачи?
Тема лекции «Условный экстремум. Функция Лагранжа»
План лекции:
Условный экстремум. Функция Лагранжа
Условный экстремум. Функция Лагранжа
Условным экстремумом функции 13 EMBED Equation.3 1415 называется экстремум этой функции, достигнутый при условии, что переменные х и у связаны уравнением 13 EMBED Equation.3 1415 (уравнение связи).
Отыскание условного экстремума можно свести к исследованию на обычный экстремум так называемой функции Лагранжа 13 EMBED Equation.3 1415, где 13 EMBED Equation.3 1415- неопределенный постоянный множитель.
Необходимые условия экстремума функции Лагранжа имеют вид
13 EMBED Equation.3 1415
Из этой системы трех уравнений можно найти неизвестные х, у, 13 EMBED Equation.3 1415.
Геометрический метод:
Для того, чтобы найти наибольшее и наименьшее значения функции в замкнутой области, надо:
1) найти стационарные точки, расположенные в данной области, и вычислить значение функции в этих точках;
2) найти наибольшее и наименьшее значения функции на линиях, образующих границу области;
3) из всех найденных значений выбрать наибольшее и наименьшее значения.
Пример:
Найти экстремум функции 13 EMBED Equation.3 1415 при условии, что х и у связаны уравнением 13 EMBED Equation.3 1415.
Решение: Рассмотрим функцию Лагранжа 13 EMBED Equation.3 1415. Имеем 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415.
Из системы уравнений (необходимые условия экстремума)
13 EMBED Equation.3 1415 находим 13 EMBED Equation.3 1415
Нетрудно видеть, что в точке (5/4, 5/6) функция 13 EMBED Equation.3 1415 достигает наибольшего значения 13 EMBED Equation.3 1415.
Практические занятия
Практическое занятие №5 «Решение задач НП графическим методом и методом Лагранжа. Разработка алгоритма для решения различных практических задач с применением математических методов»
Тема 2.3 Динамическое программирование
Основные понятия и термины по теме: шаговое управление, управление операцией в целом, оптимальное управление, выигрыш на данном шаге, выигрыш за всю операцию, аддитивный и мультипликативный критерии.
План изучения темы (перечень вопросов, обязательных к изучению):
Основные понятия ДП. Основные понятия динамического программирования: шаговое управление, управление операцией в целом, оптимальное управление, выигрыш на данном шаге, выигрыш за всю операцию, аддитивный критерий, мультипликативный критерий.
Модели ДП. Идея метода динамического программирования. Простейшие задачи, решаемые методом динамического программирования
Разработка алгоритма для решения различных практических задач ДП с применением математических методов. Оптимальное распределение ресурсов
Разработка алгоритма для решения различных практических задач ДП с применением математических методов. Выбор оптимального маршрута перевозки грузов
Теоретический материал
Тема лекции: «Основные понятия ДП»
Понятие задачи динамического программирования
Рассматриваемые ранее задачи характеризуются тем, что в них не учитываются изменения оптимизируемых параметров во времени – процессы считаются статичными. Выбирается некоторый период времени, и для него определяются проектируемые или планируемые значения показателей. При этом предполагается, что управляемые или неуправляемые параметры системы в течение всего планового времени не будут изменяться или, по крайней мере, не претерпят серьёзных изменений, требующих пересмотра принятых решений.
Однако в реальной жизни есть задачи, в которых необходимо учитывать изменения параметров систем во времени. Эти параметры могут меняться непрерывно или дискретно – от этапа к этапу. Например, из года в год меняется возраст машин и оборудования, изменяется производственная мощность и производительность труда на предприятиях. Очевидно, что необходимо принимать оптимальные решения на год (или другой срок) и одновременно на весь рассматриваемый период в целом с учётом возможных изменений параметров. Для решения такого вида задач, которые получили название многошаговые, разработан соответствующий математический аппарат, который получил название динамическое программирование.
Рассмотрим задачу, состоящую из m шагов. Например, деятельность предприятия в течение нескольких месяцев, эксплуатация трактора в течение нескольких лет и т. д. В других случаях разбивку на шаги приходится проводить искусственно, например, прокладка трассы, дороги и т. д.
На каждом шаге с целью улучшения результата операции в целом осуществляется распределение и перераспределение ресурсов, т. е. управление u. Эффективность операции в целом характеризуется показателем W, который зависит от всей совокупности управлений u и на каждом шаге операций.
W = W(u) = W(u1, u2, ,um) (1)
Управление, при котором показатель W достигает максимума (минимума), называется оптимальным управлением u*, которое состоит из совокупности оптимальных шагов управлений.
U* = (u1*, u2*, , um*) (2)
Метод динамического программирования был предложен и развит Р. Беллманом и его учениками в начале 50-х годов и состоит в нахождении максимума (минимума) целевой функции при ограничении общего вида на изменяемые параметры.
Задача может быть сформулирована следующим образом:
Задача динамического программирования – определить ui* (ui* не только число, а может быть вектором, функцией) на каждом шаге, i = 1, 2 , m, и тем самым u* всей операции в целом.
Рассмотрим подход к решению данной задачи. Характерным для динамического программирования является то, что переменные рассматриваются вместе, а не последовательно – одна за другой. При этом вычислительная тема строится таким образом, что вместо одной задачи с n переменными решается серия задач с небольшим числом, а чаще с одной переменной. Сам же вычислительный процесс производится на основе метода последовательных приближений в два круга:
От последнего шага к первому.
От первого шага к последнему или же наоборот, в зависимости от исходных данных.
На первом круге ищется так называемое условное оптимальное решение. Оно выбирается так, чтобы все предыдущие шаги обеспечили максимальную эффективность последующего. Основу такого подхода составляет принцип оптимальности Беллмана, который формулируется следующим образом:
Нельзя получить оптимальное значение целевой функции i-шагового процесса, если для любого ui, выбранного на шаге i, значение целевой функции для оставшихся i-1 шагов не является оптимальным при этом выбранном на i-шаге значении ui.
Такой процесс продолжается до тех пор, пока решение не потеряет свой условный характер, т. е. до первого шага или последнего. Для него решение просто оптимально. Поэтому второй круг начинают именно с этого шага и последовательно переходят от условных к оптимальным решениям, тем самым обеспечивается оптимальность операции в целом.
Другими словами, управление на i-шаге выбирается не так, чтобы выигрыш именно на данном шаге был максимален (минимален), а так, чтобы была оптимальна сумма выигрышей на всех оставшихся до конца шагах плюс данный. Исключение – последний шаг. Поэтому процесс динамического программирования обычно разворачивается от конца к началу – прежде всего, планируется последний шаг. А как его спланировать, если неизвестен последний? Необходимо сделать разные предположения о том, чем завершится m-1 шаг и для каждого из этих предположений найти условное оптимальное управление и соответствующий ему условный оптимальный выигрыш на m шаге. Далее, двигаясь назад, оптимизируем управление на m-2 шаге и т. д., пока не дойдем до первого. После можно построить не условно-оптимальное, а искомое оптимальное управление u* и найти искомый оптимальный выигрыш W*. Для этого достаточно, двигаясь от начала к концу, прочитать уже готовые рекомендации и найти u*, состоящие из u1*, u2*, um*. Что касается оптимального выигрыша W* за всю операцию, то он нам уже известен – именно на его оптимальности выбрано управление на первом шаге.
Вопросы для самоконтроля:
Какие задачи называются многошаговыми?
При помощи какого математического аппарата решаются многошаговые задачи?
Что такое оптимальное управление u*?
Каков алгоритм метода последовательных приближений в два круга?
Тема лекции «Разработка алгоритма для решения различных практических задач ДП с применением математических методов. Оптимальное распределение ресурсов»
План лекции:
Классические задачи динамического программирования
Оптимальное распределение ресурсов
Пример решения задачи оптимального распределения ресурсов
Классические задачи динамического программирования
Задача о наибольшей общей подпоследовательности: даны две последовательности, требуется найти самую длинную общую подпоследовательность.
Задача поиска наибольшей увеличивающейся подпоследовательности: дана последовательность, требуется найти самую длинную возрастающую подпоследовательность.
Задача о редакционном расстоянии (расстояние Левенштейна): даны две строки, требуется найти минимальное количество стираний, замен и добавлений символов, преобразующих одну строку в другую.
Задача о вычислении чисел Фибоначчи
Задача о порядке перемножения матриц: даны матрицы , , , требуется минимизировать количество скалярных операций для их перемножения.
Задача о выборе траектории
Задача последовательного принятия решения
Задача об использовании рабочей силы
Задача управления запасами
Задача о ранце: из неограниченного множества предметов со свойствами «стоимость» и «вес» требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при ограниченном суммарном весе.
Алгоритм Флойда Уоршелла: найти кратчайшие расстояния между всеми вершинами взвешенного ориентированного графа.
Алгоритм Беллмана Форда: найти кратчайший путь во взвешенном графе между двумя заданными вершинами.
Максимальное независимое множество вершин в дереве: дано дерево, найти максимальное множество вершин, никакие две из которых не связаны ребром.
Оптимальное распределение инвестиций
Требуется распределить имеющиеся В единиц средств среди n предприятий, доход 13 EMBED Equation.3 1415 от которых в зависимости от количества вложенных средств 13 EMBED Equation.3 1415 определяется матрицей (n(n) приведенной в таблице , так, чтобы суммарный доход со всех предприятий был бы максимальным.
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
Запишем математическую модель задачи.
Определить 13 EMBED Equation.3 1415, удовлетворяющий условиям
13 EMBED Equation.3 1415
и обеспечивающий максимум целевой функции
13 EMBED Equation.3 1415
Очевидно, эта задача может быть решена простым перебором всех возможных вариантов распределения В единиц средств по n предприятиям, например на сетевой модели. Однако решим ее более эффективным методом, который заключается в замене сложной многовариантной задачи многократным решением простых задач с малым количеством исследуемых вариантов.
С этой целью разобьем процесс оптимизации на n шагов и будем на каждом k-м шаге оптимизировать инвестирование не всех предприятий, а только предприятий с k -го по n -е. При этом естественно считать, что в остальные предприятия (с первого по k- 1)-е тоже вкладываются средства, и поэтому на инвестирование предприятий с k -го по n -е остаются не все средства, а некоторая меньшая сумма 13 EMBED Equation.3 1415. Эта величина и будет являться переменной состояния системы. Переменной управления на k -м шаге назовем величину 13 EMBED Equation.3 1415, средств, вкладываемых в k -е предприятие. В качестве функции Беллмана 13 EMBED Equation.3 1415 на k -м шаге можно выбрать макcимально возможный доход, который можно получить с предприятий с k -го по n -е при условии, что на их инвестирование осталось средств. Очевидно, что при вложении в k -е предприятие 13 EMBED Equation.3 1415, средств будет получена прибыль 13 EMBED Equation.3 1415, а система к (k+1)-му шагу перейдет в состояние 13 EMBED Equation.3 1415, и, следовательно, на инвестирование предприятий с (k+1)-го до n -го останется 13 EMBED Equation.3 1415 средств.
Таким образом, на первом шаге условной оптимизации при k= n функция Беллмана представляет собой прибыль только с n -го предприятия. При этом на его инвестирование может остаться количество средств 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415. Чтобы получить максимум прибыли с этого предприятия, можно вложить в него все эти средства, т.е. 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415.
На каждом последующем шаге для вычисления функции Беллмана необходимо использовать результаты предыдущего шага. Пусть на k -м шаге для инвестирования предприятий с k -го по n -е осталось 13 EMBED Equation.3 1415, средств (13 EMBED Equation.3 1415). Тогда от вложения в k -е предприятие 13 EMBED Equation.3 1415, средств будет получена прибыль 13 EMBED Equation.3 1415, а на инвестирование остальных предприятий (с k -го по n -е) останется 13 EMBED Equation.3 1415 средств. Максимально возможный доход, который может быть получен с предприятий (с k -го по n -е), будет равен:
13 EMBED Equation.3 1415
Максимум этого выражения достигается на некотором значении 13 EMBED Equation.3 1415, которое является оптимальным управлением на k -м шаге для состояния системы 13 EMBED Equation.3 1415, действуя таким образом, можно определить функции Беллмана и оптимальные управления до шага k = 1.
Значение функции Беллмана 13 EMBED Equation.3 1415представляет собой максимально возможный доход со всех предприятий, а значение на котором достигается максимум дохода, является оптимальным количеством средств, вложенных в первое предприятие. Далее на этапе безусловной оптимизации для всех последующих шагов вычисляется величина 13 EMBED Equation.3 1415 и оптимальным управлением на k -м шаге является то значение 13 EMBED Equation.3 1415, которое обеспечивает максимум дохода при соответствующем состоянии системы 13 EMBED Equation.3 1415.
Пример решения задачи оптимального распределения ресурсов
Капитал 40 млн.руб. инвестор должен вложить в четыре инвестиционных проекта так, чтобы получить максимальный доход. Доходность проектов дана в таблице (вложения кратны 8 млн. руб.)
u
Прибыль от внедрения
f4(u)
f3(u)
f2(u)
f1(u)
8
55
39
35
32
16
58
53
76
68
24
90
80
120
115
32
100
120
135
134
40
140
145
158
147
Решение:
Это задача динамического программирования. Решение состоит из двух этапов. На первом этапе (от конца к началу) ищем условное оптимальное решение, на втором (от начала к концу) – ищем оптимальное решение задачи.
1 этап.
Распределяем капитал между четырьмя проектами и считаем получаемую прибыль L(i), i=8,16,24,32,40.
1 шаг: Денежные средства вкладываются в четвертый проект.
L(8)=55
L(16)=58
L(24)=90
L(32)=100
L(40)=140
2 шаг: Денежные средства вкладываются в четвертый и третий проекты.
u
Прибыль от внедрения
1 шаг
f3(u)
8
55
39
16
58
53
24
90
80
32
100
120
40
140
145
13 EMBED Equation.3 1415
3 шаг: Денежные средства вкладываются в четвертый, третий (2 шаг) и второй проекты.
u
Прибыль от внедрения
2 шаг
f2(u)
8
55
35
16
94
76
24
108
120
32
135
135
40
175
158
13 EMBED Equation.3 1415
4 шаг: Денежные средства вкладываются в четвертый, третий, второй (3 шаг) и первый проекты.
u
Прибыль от внедрения
3 шаг
f1(u)
8
55
32
16
94
68
24
131
115
32
175
134
40
214
147
13 EMBED Equation.3 1415
2 этап:
На четвертом шаге выбираем максимальное из полученных значений прибыли L(40)=214.
И возвращаясь в обратном порядке от таблицы к таблице (от 4 шага к 1) выбираем такие значения доходов, при которых и получено значение 214.
Вывод: Максимальный доход 214 млн. руб. от вложенных средств может быть получен при следующем распределении средств:
1 проект – 0 млн. руб.
2 проект – 24 млн. руб.
3 проект – 8 млн. руб.
4 проект – 8 млн. руб.
Тема лекции «Разработка алгоритма для решения различных практических за
·дач ДП с применением математических методов. Выбор оптимального маршрута перевозки грузов»
Выбор оптимального маршрута перевозки грузов
Математический аппарат ДП, основанный на методологии пошаговой оптимизации, может быть использован при нахождении кратчайших расстояний, например, на географической карте, представленной в виде сети. Решение задачи по определению кратчайших расстояний между пунктами отправления и пунктами получения продукции по существующей транспортной сети является исходным этапом при решении таких экономических задач, как оптимальное прикрепление потребителей за поставщиками, повышение производительности транспорта за счет сокращения непроизводительного пробега и др.
Пусть транспортная сеть состоит из 10 узлов, часть из которых соединены магистралями. На рис. 1 показана сеть дорог и стоимости перевозки единицы груза между отдельными пунктами сети, которые проставлены у соответствующих ребер. Необходимо определить маршрут доставки груза из пункта 1 в пункт 10, обеспечивающий наименьшие транспортные расходы.
13 SHAPE \* MERGEFORMAT 1415
Рис. 1. Модель транспортной сети.
В задаче имеется ограничение – двигаться по изображенным на схеме маршрутом можно только слева на право, т.е. попав, например, в пункт 7, мы имеем право переместиться только в пункт 10 и не можем возвратиться обратно в 5 или 6. Это особенность транспортной сети дает право отнести каждый из 10 пунктов к одному из поясов. Будем считать, что пункт принадлежит k-му поясу, если из него попасть в конечный пункт ровно за k шагов, т.е. заездом ровно в (k-1) – й промежуточный пункт. Таким образом, пункты 7, 8 и 9 принадлежат к первому поясу, 5 и 6 ко второму, 2, 3 и 4 к третьему и 1– к четвертому. Тогда на k-м шаге будем находить оптимальные маршруты перевозки груза из пунктов в k-го пояса до конечного пункта. Оптимизацию будем производить с конца процесса, и потому, дойдя до k-го шага, неизвестно, в каком из пунктов k-го пояса окажется груз, перевозимый из первого пункта.
Введем обозначения:
k – номер шага (13 EMBED Equation.3 1415)
i – пункт, из которого осуществляются перевозки(13 EMBED Equation.3 1415)
j – пункт, в который доставляется груз(13 EMBED Equation.3 1415)
13 EMBED Equation.3 1415 – стоимость перевозки груза из пункта i в пункт j.
13 EMBED Equation.3 1415 – минимальные затраты на перевозку груза на k-м шаге решения задачи из пункта i до конечного пункта.
Очевидно, что минимум затрат на перевозку груза из пунктов k-го пояса до пункта 10 будет зависеть от того, в каком месте этого пояса мы оказались. Номер i пункта, принадлежащего k-му поясу будет являться переменной состояния системы на k-м шаге. Поскольку оптимизация осуществляется с конца процесса, то, находясь в некотором пункте i k-го пояса, принимается решение о перемещении груза в один из пунктов (k – 1)-го пояса, а направление дальнейшего движения известно из предыдущих шагов. Номер j пункта (k-1)-го пояса будет переменной управления на k-м шаге.
Для первого шага управления (k=1) функция Беллмана представляет собой минимальные затраты на перевозку груза из пунктов 1-го пояса в конечный пункт, т.е. 13 EMBED Equation.3 1415. Для последующих шагов затраты складываются из двух слагаемых – стоимость перевозки груза 13 EMBED Equation.3 1415 из пункта i k-го пояса в пункт j (k–1)-го пояса и минимально возможных затрат на перевозку из пункта j до конечного пункта, т.е. 13 EMBED Equation.3 1415.
Таким образом, функциональное уравнение Беллмана будет иметь вид
13 EMBED Equation.3 1415
Минимум затрат достигается на некотором значении 13 EMBED Equation.3 1415, которое является оптимальным направлением движением из пункта i в конечный пункт.
На четвертом шаге попадаем на 4-ый пояс и состояние системы становится определенным i=1. Функция 13 EMBED Equation.3 1415 представляет собой минимально возможные затраты по перемещению груза из пункта 1 в 10. Оптимальный маршрут определяется в результате анализа всех шагов в обратном порядке, а выбор некоторого управления j на k-м шаге приводит к тому, что состояние системы на (k-1)-м шаге становится определенным.
Пример. Решим сформулированную задачу, исходные данные которой приведены на рис. 1.
Решение:
I этап. Условная оптимизация.
1-й шаг. k=1 13 EMBED Equation.3 1415.
На первом шаге в пункт 10 груз может быть доставлен из пунктов 7, 8 или 9.
Таблица 1.
i j
10
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
7
7
7
10
8
9
9
10
9
11
11
10
2-й шаг. k=2. Функциональное уравнение на втором шаге принимает вид
13 EMBED Equation.3 1415
Все возможные перемещения груза на втором шаге и результаты расчета приведены в следующей таблице 2.
Таблица 2.
i j
7
8
9
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
5
8+7
6+9
–
15
7; 8
6
5+7
–
4+11
12
7
3-й шаг. k=3. 13 EMBED Equation.3 1415
Таблица 3.
i j
5
6
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
2
4+15
–
19
5
3
–
3+12
15
6
4
–
9+12
21
6
4-й шаг. k=4.
13 EMBED Equation.3 1415
Таблица 4.
i j
2
3
4
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
1
7+19
5+15
6+21
20
3
II этап. Безусловная оптимизация.
На этапе условной оптимизации получено, что минимальные затраты на перевозку груза из пункта 1 в пункт 10 составляют 13 EMBED Equation.3 1415. Данный результат достигается при движении груза их пункта 1 в пункт 3. По данным таблицы 3, из пункта 3 необходимо двигаться в пункт 6, затем – в пункт 7 и из него – в конечный пункт. Таким образом, оптимальный маршрут доставки груза: 13 EMBED Equation.3 1415 (на рис. Он показан двойными стрелками).
13 SHAPE \* MERGEFORMAT 1415
Рис. 2. Транспортная сеть с оптимальным маршрутом.
Вопросы для самоконтроля:
Как формулируется задача динамического программирования и в чем ее отличие от задач линейного программирования?
В чем заключаются особенности математической модели ДП?
Что лежит в основе метода ДП?
Сформулируйте задачу определения кратчайших расстояний по заданной сети. На сколько этапов разбивается задача? Сколько шагов содержится в каждом этапе и в чем суть этапа и шага?
Практические занятия:
Практическое занятие №6 «Решение задач о распределении средств между предприятиями и замене оборудования»
Тема 2.4 Алгоритмы на графах
Основные понятия и термины по теме: граф, вершины, ребра, неориентированные ребра, ориентированные ребра, метрические характеристики графа.
План изучения темы (перечень вопросов, обязательных к изучению):
Метрические характеристики графов. Матрица смежности, матрица инцидентности, матрица достижимости (расстояний), эксцентриситет, передаточное число, медиана, радиус, центр графа.
Задача о нахождении кратчайших путей в графе. Задача о нахождении кратчайшего пути. Алгоритм Дейкстры решения задачи. Пример решения задачи
Теоретический материал
Тема лекции: «Основные понятия теории графов .Метрические характеристики графов»
План лекции:
Основные термины теории графов.
Пути, маршруты, цепи и циклы.
Подграфы.
Деревья.
Метрические характеристики графов.
Структурная схема терминов
[ Cкачайте файл, чтобы посмотреть картинку ]
Основные термины теории графов
Граф – это множество точек или вершин и множество линий или ребер, соединяющих между собой все или часть этих точек.
Вершины, прилегающие к одному и тому же ребру, называются смежными.
Если ребра ориентированны, что обычно показывают стрелками, то они называются дугами, и граф с такими ребрами называется ориентированным графом. Если ребра не имеют ориентации, граф называется неориентированным.
Графы обычно изображаются в виде геометрических фигур, так что вершины графа изображаются точками, а ребра – линиями, соединяющими точки.
Пример 1 (граф)
[ Cкачайте файл, чтобы посмотреть картинку ]
Петля – это дуга, начальная и конечная вершина которой совпадают.
Простой граф – граф без кратных ребер и петель.
Степень вершины – это удвоенное количество петель, находящихся у этой вершины плюс количество остальных прилегающих к ней ребер.
Пустым называется граф без ребер. Полным называется граф, в котором каждые две вершины смежные
Пути, маршруты, цепи и циклы
Путь в ориентированном графе – это последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.
Вершины v0, vn называются связанными данным путем (или просто связанными). Вершину v0 называют началом, vn – концом пути. Если v0 = vn, то путь называют замкнутым. Число n называется длиной пути.
Маршрут в графе – путь, ориентацией дуг которого можно пренебречь.
Цепь – маршрут, в котором все ребра попарно различны.
Цикл – замкнутый маршрут, являющийся цепью.
Маршрут, в котором все вершины попарно различны, называют простой цепью. Цикл, в котором все вершины, кроме первой и последней, попарно различны, называются простым циклом.
Пример 2 (граф отношения делимости)
Построим граф, изображающий отношение делимости на множестве {1,2,3,4,5,6,7,8,9,10}. Принцип такой: если от одного числа до другого есть цепь, ведущая вверх, тогда второе число делится на первое.
[ Cкачайте файл, чтобы посмотреть картинку ]
Подграфы
Подграф графа – это граф, являющийся подмоделью исходного графа. Т. е. подграф содержит некоторые вершины исходного графа и некоторые ребра (только те, оба конца которых входят в подграф).
Подграф, порожденный множеством вершин U – это подграф, множество вершин которого – U, содержащий те и только те ребра, оба конца которых входят в U.
Подграф называется остовным подграфом, если множество его вершин совпадает с множеством вершин самого графа.
Связность графа
Граф называется связным, если любая пара его вершин связана.
Связными компонентами графа называются подграфы данного графа, вершины которых связаны.
Деревья
Дерево – это связный граф без циклов.
Деревья особенно часто возникают на практике при изображении различных иерархий. Например, популярны генеалогические деревья.
Пример 3 (генеалогическое дерево)
На рисунке показано библейское генеалогическое дерево.
[ Cкачайте файл, чтобы посмотреть картинку ]
Граф без цикла называется лесом. Вершины степени 1 в дереве называются листьями.
Деревья – очень удобный инструмент представления информации самого разного вида.
Деревья отличаются от простых графов тем, что при обходе дерева невозможны циклы. Это делает графы очень удобной формой организации данных для различных алгоритмов. Таким образом, понятие дерева активно используется в информатике и программировании.
Очевидно, что графический способ представления графов непригоден для ПК. Поэтому существуют другие способы представления графов.
Метрические характеристики графов
В теории графов применяются:
Матрица инцинденций. Это матрица А с n строками, соответствующими вершинам, и m столбцами, соответствующими рёбрам. Для ориентированного графа столбец, соответствующий дуге (х,y) содержит -1 в строке, соответствующей вершине х и 1 в строке, соответствующей вершине у. Во всех остальных – 0. Петлю, т. е. дугу (х,х) можно представлять иным значением в строке х, например, 2. Если граф неориентированный, то столбец, соответствующий ребру (х,у) содержит 1, соответствующие х и у – нули во всех остальных строках.
Матрица смежности. Это матрица n*n где n – число вершин, где bij = 1, если существует ребро, идущее из вершины х в вершину у и bij = 0 в противном случае.
Пусть G=(X,U) - связный граф, а 13 EMBED Equation 1415 - две его несовпадающие вершины. Длина кратчайшего маршрута, соединяющего вершины 13 EMBED Equation 1415 (пути из 13 EMBED Equation 1415) называется расстоянием между вершинами 13 EMBED Equation 1415 и обозначается 13 EMBED Equation 1415. Положим 13 EMBED Equation 1415, если вершины 13 EMBED Equation 1415 не соединены маршрутом (путем). Расстояние 13 EMBED Equation 1415 удовлетворяет следующим аксиомам:
1) 13 EMBED Equation 1415;
2) 13 EMBED Equation 1415;
3) 13 EMBED Equation 1415 тогда и только тогда, когда 13 EMBED Equation 1415;
4) 13 EMBED Equation 1415 для симметрических графов;
5) 13 EMBED Equation 1415 (неравенство треугольника).
Расстояние для графа G удобно задавать матрицей расстояний. Матрицей расстояний графа с n вершинами называется квадратная матрица D порядка n, элементы которой определяются следующим образом:
13 EMBED Equation 1415
Матрицу расстояний можно определить
Для фиксированной вершины 13 EMBED Equation 1415 величина
13 EMBED Equation 1415
называется эксцентриситетом (отклоненностью) вершины 13 EMBED Equation 1415.
Максимальный среди эксцентриситетов вершин называется диаметром графа G и обозначается diam (G):
13 EMBED Equation 1415
Минимальный из эксцентриситетов вершин связного графа называется его радиусом и обозначается через r(G):
13 EMBED Equation 1415
Вершина, имеющая минимальный эксцентриситет, называется центром графа.
Для вершины 13 EMBED Equation 1415 число 13 EMBED Equation 1415 называется передаточным числом. Вершина графа, которой соответствует минимальное передаточное число
13 EMBED Equation 1415
называется медианой графа. Центров и медиан в графе может быть несколько.
Рис. 1
Пример. Для графа, изображенного на рис.1 метрические характеристики определяются следующим образом:
13 EMBED Equation 1415
Радиус графа равен 1, диаметр равен 2. Центр графа - вершина 13 EMBED Equation 1415; Медиана графа - вершина 13 EMBED Equation 1415.
Вопросы для самоконтроля:
Что такое граф?
Приведите разновидности графов.
Может ли пустой граф быть ориентированным?
Нарисуйте полный граф.
Что такое подграф?
Каким образом понятие дерева активно используется в информатике и программировании?
Метрические характеристики графов.
Тема лекции: «Задача о нахождении кратчайших путей в графе и методы их решения»
План лекции:
Задача о нахождении кратчайшего пути.
Алгоритм Дейкстры решения задачи.
Пример решения задачи.
1. Задача о нахождении кратчайшего пути
Пусть дан граф, каждой дуге которого приписан вес. Задача о нахождении кратчайшего пути состоит в нахождении кратчайшего пути от заданной начальной вершины до заданной конечной вершины, при условии, что такой путь существует.
Можно дать много практических интерпретаций задачи о кратчайших путях. Например, вершины могут соответствовать городам и каждая дуга – некоторому пути, длина которого представлена весом дуги. Мы ищем кратчайшие пути между городами. Вес дуги может соответствовать стоимости (или времени) передачи информации между вершинами. В этом случае мы ищем самый дешевый (или самый скорый) путь.
Данная задача может быть разбита на две:
для начальной заданной вершины найти все кратчайшие пути от этой вершины к другим;
найти кратчайшие пути между всеми парами вершин.
2. Алгоритм Дейкстры решения задачи
Алгоритм Дейкстры ( алгоритм поиска кратчайшего пути во взвешенном графе между двумя заданными вершинами s и t при неотрицательных весах всех дуг.
Пусть s - начальная вершина пути, t - конечная.
На каждой итерации алгоритма каждая вершина xi графа имеет метку l(xi), которая может быть постоянной или временной. В первом случае l(xi) является длиной кратчайшего (s, xi)-пути; во втором случае l(xi) - длина кратчайшего (s, xi)-пути, проходящего через вершину xi и вершины с постоянными метками. Таким образом временная метка l(xi), является оценкой сверху для длины кратчайшего (s, xi)-пути, и, став на некоторой итерации постоянной, она остается такой до конца работы алгоритма.
Кроме l(xi), с вершинами графа связывается еще одна метка Q(xi).На каждой итерации Q(xi) является номером вершины, предшествующей хi в кратчайшем (s, xi)-пути.
После того, как последняя вершина t получила постоянную метку, с помощью меток Q(x) легко указать последовательность вершин, составляющих кратчайший (S,t)-путь:
(s..., Qn(t)..., Q(Q(t)), Q(t),t),
Qn(t)= Q(Q(...Q(t)) (n раз).
Перед началом работы алгоритма начальная вершина s имеет постоянную метку l(s)=0, а метки всех остальных вершин равны бесконечности (() и являются временными. Обозначим через p последнюю из вершин, получивших постоянную метку.
Алгоритм Дейкстры включает следующие шаги:
1. Положить l(s)=0 и считать эту метку постоянной. Положить l(xi)= ( для всех xi ( s, и считать эти метки временными. p = s.
2. Обновление пометок. Для всех вершин xi ( Г(p), пометки которых временные, изменить пометки в соответствии с правилом:
l(xi)=min { l(xi), l(p) +w(p, xi) }.
Если l(xi)> l(p) +w(p, xi), то Q(xi) = p.
3. Если l(xi)= ( для всех вершин xi, пометки которых временные, то в исходном графе отсутствуют пути из вершины s в вершины с временными метками. Останов алгоритма. В противном случае переход к шагу 4.
4. Превращение пометок в постоянные. Среди всех вершин с временными метками найти такую вершину xi* , для которой l(xi*) = minl(xi) (метка минимальная) и считать эту пометку постоянной. Положить p=xi*. Пометку Q(xi*) также считать постоянной.
5. Если p ( t, перейти к шагу 2, а если p = t, то l(p) - длина кратчайшего пути из s в t.
После определения длины кратчайшего пути сам кратчайший путь восстанавливается по постоянным меткам Q(xi).
3.Пример решения задачи
Для взвешенного орграфа найти кратчайший путь из вершины s в вершину t.
13 EMBED PBrush 1415
1. Помечаем в соответствии с алгоритмом вершины графа:
l(s) = 0 ,
l(a) = ( ,
l(b) = ( ,
l(c) = ( ,
l(d) = ( ,
l(t) = ( .
Вершине s приписываем постоянную пометку, т.е. p = s.
2. Из вершины s помечаем остальные вершины:
l(a) = min {(, 0 + 4} = 4,
l(b) = min {(, 0 + 7} = 7,
l(c) = min {(, 0 + 3} = 3,
l(d) = ( ,
l(t) = ( .
У вершин a, b, с уменьшились пометки, следовательно Q(a) = s, Q(b) = s, Q(c) = s.
Вершине c приписываем постоянную пометку, т.е. p = c. Пометка Q(с)=s также становится постоянной.
3. Из вершины c помечаем остальные вершины:
l(a) = min {4, 3 + (} = 4,
l(b) = min {7, 3 + (} = 7,
l(d) = min {(, 3 + 3} = 6,
l(t) = ( .
У вершины d уменьшилась пометка, следовательно Q(d) = c.
Вершине a приписываем постоянную пометку, т.е. p = a. Пометка Q(a)=s становится постоянной.
4. Из вершины а помечаем остальные вершины:
l(b) = min {7, 4 + 4} = 7,
l(d) = min {6, 4 + 3} = 6,
l(t) = ( .
Вершине d приписываем постоянную пометку, т.е. p = d.. Пометка Q(d)=c становится постоянной.
5. Из вершины d помечаем остальные вершины:
l(b) = min {7, 6 + (} = 7,
l(t) = min {(, 6 + 2} = 8,
У вершины t уменьшилась пометка, следовательно Q(t) = d.
Вершине b приписываем постоянную пометку, т.е. p=b. Пометка Q(b)=s становится постоянной.
6. Из вершины b помечаем вершину t:
l(t) = min {8, 7 + 2} = 8.
Метки l(t) и Q(t)=d становятся постоянными.
7. Восстанавливаем по меткам Q кратчайший путь из s в t:
Путь scdt длиной 8.
Работу алгоритма можно проиллюстрировать таблицей:
Вершина
1
2
3
4
5
6
s
0
-
-
-
-
-
a
(
4
4
-
-
-
b
(
7
7
7
7
-
c
(
3
-
-
-
-
d
(
(
6
6
-
-
t
(
(
(
(
8
8
Вопросы для самоконтроля:
Дайте интерпретацию задаче о кратчайших путях.
Каков алгоритм для нахождения решения задач?
Практические занятия:
Практическое занятие №7 «Нахождение кратчайшего пути в графе. Разработка алгоритма для решения различных практических задач с применением математических методов»
Раздел 3. Основные методы решения детерминированных задач и задач в условиях неопределенности, возникающих в практической деятельности
Тема 3.1 Системы массового обслуживания
Основные понятия и термины по теме: случайный процесс, граф состояний, поток событий, вероятность состояния.
План изучения темы (перечень вопросов, обязательных к изучению):
Основные понятия теории марковских процессов. Случайный процесс, марковский процесс, граф состояний, поток событий,
Уравнение Колмогорова А.Н. Вероятность состояния, уравнения Колмогорова, финальные вероятности состояний. Схема гибели и размножения.
Понятие СМО. классификация систем массового обслуживания. Простейшие системы массового обслуживания и их параметры
Теоретический материал
Тема лекции: «Основные понятия теории марковских процесов»
План лекции:
Марковский случайный процесс
Марковский случайный процесс
Построение математических моделей в условиях неопределенности - очень сложная или невыполнимая задача. Лишь для некоторых упрощенных случаев можно построить математическую модель.
Следует различать два вида неопределенности:
вероятностные характеристики либо известны, либо могут быть получены в результате эксперимента. Такая неопределенность называется стохастической, и для большинства объектов, содержащих такую неопределенность, можно построить математическую модель, например выход из строя оборудования, приход нового клиента и т. д.
вероятностные характеристики определить невозможно. В этом случае задачу можно попытаться решить с помощью экспертных оценок, но результат будет весьма приблизительным, например, каковы будут модели женской одежды через пять лет?
Строгую математическую модель с аналитическим вычислением всех интересующих величин можно построить только в том случае, если случайный процесс носит марковский характер.
Случайный процесс будет марковским, если вероятностные характеристики процесса в момент времени t зависят только от текущего (настоящего) состояния процесса в этот момент времени t и не зависят от того, как (каким способом и когда) рассматриваемый процесс перешел в текущее состояние.
Если за процессом проводилось наблюдение, известны все предыдущие состояния и известно текущее состояние, то для процесса можно указать вероятность наступления следующего состояния достаточно легко. Причем, если процесс марковский, то достаточно знать текущее состояние процесса, чтобы делать прогноз будущего состояния процесса, но очевидно, что текущее состояние процесса достигнуто благодаря ряду предшествующих событий.
Большинство процессов, наблюдаемых в технике, экономике и других областях, можно свести к марковским процессам, если параметры, управляющие одновременно предшествующими событиями и одновременно влияющие на прогнозируемые события, включить в описание текущего события. Однако следует иметь в виду, что включение слишком большого количества параметров, описывающих состояние процесса (размерность задачи), может привести к тому, что математическое описание будет слишком громоздким и трудно поддаваться решению. Из всего многообразия марковских процессов хорошо изучены и представляют большой практический интерес марковские случайные процессы с дискретными состояниями и непрерывным временем.
Под дискретным состоянием будем понимать, что процесс переходит из одного состояния в другое скачкообразно за очень короткое время (практически мгновенно), и количество этих состояний известно (фиксировано).
Под непрерывным временем будем понимать такое, при котором переход из одного допустимого состояния в другое допустимое состояние происходит в произвольные моменты времени, т. е. заранее не определенные.
Потоки событий. Однородные события, следующие друг за другом в произвольные моменты времени (случайно), называются потоком событий (или входным потоком заявок). Примерами потоков событий могут быть: поток пассажиров в авиакассе, поток посетителей парикмахерской, поток отказов технического устройства и т.д. Здесь под событием понимается факт поступления заявок на обработку (приход покупателя, наличие отказа технического средства, поступление телефонного вызова и т.д.), а не результат его обработки (как это рассматривается в теории вероятностей). Поэтому в системах массового обслуживания вероятностными характеристиками будет обладать не отдельное событие, а интервал времени.
Интенсивностью 13 EMBED Equation.3 1415 потока событий называется среднее число событий за единицу времени. Интенсивность 13 EMBED Equation.3 1415 может быть как числом постоянным (константой), так и величиной, зависящей от времени t. Например, количество пассажиров в городском транспорте в «часы пик» резко увеличивается по сравнению с другим временем суток.
Все многообразие потоков можно разделить на два больших класса.
1. Регулярные потоки. События внутри потока следуют один за другим, через равные промежутки времени.
2. Стационарные (нерегулярные) потоки. События внутри потока следуют одно за другим хаотично (нерегулярно) и независимо друг от друга. Важно отметить одну особенность стационарного потока интенсивность13 EMBED Equation.3 1415 есть величина постоянная, В разные моменты времени, но в равные интервалы времени 13 EMBED Equation.3 1415Т попадает разное количество событий, но среднее количество событий для интервала времени 13 EMBED Equation.3 1415Т остается постоянным.
Большинство процессов, характерных для техники, транспорта, экономики и т. д. не стационарны, т. е. имеют ярко выраженные повторения группы событий. Но в отдельные ограниченные отрезки времени (например, внутри суток) эти процессы можно рассматривать как стационарные.
Для каждого потока событий можно указать следующие характеристики:
1. Поток без последствия. Если для потока можно указать два непересекающихся интервала времени и внутри одного интервала времени появление событий не зависит от появления событий внутри другого интервала времени, то такой поток называется потоком без последствия. Примерами потоков без последствия могут быть: приход клиентов в банк (у каждого клиента могут быть собственные причины посещения банка), поступление звонков в справочную службу и т. д.
2. Ординарный поток. Если события внутри потока следуют одно за другим и запрещено наступление двух и более событий, то такой поток называется ординарным.
Вопросы для самоконтроля:
Дайте определение марковскому процессу.
Какие типы неопределенностей встречаются.
Дайте определение потоку событий.
Тема лекции: «Уравнения Колмогорова А.Н.»
План лекции:
Финальные вероятности.
Решение системы уравнений Колмогорова.
1.Финальные вероятности состояний
Будем рассматривать марковские процессы с дискретными состояниями и непрерывным временем.
Пример 1 : Техническое устройство состоит из трёх узлов и в любой момент времени может находиться в одном из восьми состояний (рис. 1).
Возможные состояния устройства таковы:
S0 все три узла исправны;
S1 первый узел неисправен, второй и третий исправны;
S2 второй узел неисправен, первый и третий исправны;
S3 третий узел неисправен, первый и второй исправны;
S4 первый и третий узлы неисправны, второй исправен;
S5 второй и третий узлы неисправны, первый исправен;
S6 первый и второй узлы неисправны, третий исправен;
S7 все три узла неисправны.
Размеченным графом будем считать такой граф, у которого стрелками указаны переходы из одного состояния в другое, а рядом со стрелкой указана интенсивность перехода. Будем различать две интенсивности прямую 13 EMBED Equation.3 1415, и обратную 13 EMBED Equation.3 1415.
Тогда 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415 интенсивности потоков отказов соответственно первого, второго и третьего узлов, а 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415 соответственно интенсивности потоков возвратов (ремонтов) узлов.
Если для ремонта каждого узла имеется отдельный специалист, то среднее время ремонта каждого узла есть величина постоянная и не имеет значения, один или несколько узлов вышли из строя.
На основе построенного размеченного графа (см. рис. 1) создадим математическую модель.
Наше техническое устройство в соответствии с построенным графом в любой момент времени будет находиться в одном из восьми возможных состояний. Обозначим вероятность каждого i-го состояния как pi(t), тогда
13 EMBED Equation.3 1415 (1)
Для определения вероятности каждого состояния технического устройства составим соответствующие дифференциальные уравнения. Вероятность того, что техническое устройство будет находиться в состоянии S1 (первый узел неисправен, а второй и третий узлы исправны), обозначим p1(t). Дадим малое приращение по времени 13 EMBED Equation.3 1415t. За это малое время 13 EMBED Equation.3 1415t техническое устройство либо остается в прежнем состоянии S0 , либо перейдет в состояние S1 и з состояний S0 , S4 или S6.
Определим вероятность первого случая устройство остается в состоянии S1. В момент времени t устройство было в состоянии S1 с вероятностью p1(t). За время 13 EMBED Equation.3 1415t устройство не перейдет в любое из состояний S0, S4 или S6. Суммарный поток событий, который может вывести устройство из состояния S1, будет равен (2 +(3+(1. Каждый из этих потоков событий простейший, поэтому и суммарный поток также будет простейшим (все три свойства стационарности, ординарности и отсутствие последействия сохраняются).
Вероятность того, что устройство выйдет из состояния S1 будет равна p1(t) ((2 +(3+(1 ) 13 EMBED Equation.3 1415t, а вероятность того, что останется в состоянии S1 p1(t) [1 ((2 +(3+(1) 13 EMBED Equation.3 1415t].
Теперь определим вероятность перехода устройства за время в 13 EMBED Equation.3 1415t состояние S1 из состояний S0, S4 или S6.
Для S4 p4(t) 13 EMBED Equation.3 1415t(3;
Для S4 p6(t) 13 EMBED Equation.3 1415t(2;
Для S4 p0(t) 13 EMBED Equation.3 1415t(1.;
Таким образом, вероятность нахождения устройства в состоянии S> будет равна:
p1(t+13 EMBED Equation.3 1415t)= p1(t) [1-((1+(2 +(3 )13 EMBED Equation.3 1415t]+ p0(t)(113 EMBED Equation.3 1415t+ p4(t) (313 EMBED Equation.3 1415t + p6(t) (2 13 EMBED Equation.3 1415t.
Выполним преобразования:
p1(t+13 EMBED Equation.3 1415t)= p1(t) ((1+(2 +(3 )13 EMBED Equation.3 1415t+ p0(t)(113 EMBED Equation.3 1415t+ p4(t) (313 EMBED Equation.3 1415t + p6(t) (2 13 EMBED Equation.3 1415t;
p1(t+13 EMBED Equation.3 1415t)- p1(t) = p0(t)(113 EMBED Equation.3 1415t+ p4(t)(313 EMBED Equation.3 1415t+ p6(t)(213 EMBED Equation.3 1415t-((1+(2 +(3) p1(t) 13 EMBED Equation.3 1415t;
13 EMBED Equation.3 1415(1 p0(t)+ (3 p4(t) +(2 p6(t)-((1+(2 +(3) p1(t) .
Устремив 13 EMBED Equation.3 1415t к нулю, получим:
13 EMBED Equation.3 1415(1 p0(t)+ (3 p4(t) +(2 p6(t)-((1+(2 +(3) p1(t)
или 13 EMBED Equation.3 1415(1 p0+ (3 p4(t) +(2 p6-((1+(2 +(3) p1. (8.2)
Выполнив аналогичные действия, получим семь дифференциальных уравнений:
13 EMBED Equation.3 1415
Эта система дифференциальных уравнений называется системой уравнений Колмогорова. Имеем систему из восьми линейных дифференциальных уравнений с восемью неизвестными. Известно, что сумма всех вероятностей равна единице, т. е.
p0 +pl +p2 +p3 +p4 +p5+p6 +p7 =1. (4)
Таким образом, любое из уравнений, входящее в систему уравнений (3), можно записать, используя уравнение (4), и найти значения вероятностей для каждого события.
Для облегчения процесса составления дифференциальных уравнений можно применить следующее правило:
В левой части каждого уравнения следует записать производную вероятности г-го состояния устройства.
В правой части сумма произведений потока событий, входящих в текущее состояние, умноженная на вероятность состояния, из которого исходит поток, минус суммарная интенсивность исходящих потоков событий из текущего состояния, умноженная на вероятность текущего состояния.
Когда определены вероятности событий, то встаёт вопрос: «Что будет с техническим устройством в установившемся режиме?» В каком состоянии режиме) будет находиться техническое устройство по прошествии большого периода времени, т. е. при 13 EMBED Equation.3 1415. Если существуют пределы вероятностей pi(t) состояний устройства и они не зависят от текущего состояния устройства, то эти пределы называются финальными вероятностями состояний.
Если число состояний некоторого устройства равно и (конечное число состояний) и из каждого состояния можно перейти в другое состояние, то финальные вероятности существуют. Это положение доказывается в теории случайных процессов.
Если финальные вероятности существуют:
13 EMBED Equation.3 1415 при i = 1, 2, 3, ..., n, (5)
то их сумма будет равна единице:
13 EMBED Equation.3 1415 (6)
Финальные вероятности показывают, какое среднее время устройство будет находиться в каждом состоянии. Финальные вероятности находятся из системы дифференциальных уравнений, если их правые части приравнять нулю.
2.Решение системы уравнений Колмогорова
Зададим численные значения интенсивности потоков событий для примера 1:
(1=1; (2=2; (3=1; (1=2; (2=4; (3=2.
Приравняем левые части уравнений системы (3) нулю и заменим одно из уравнений (седьмое) выражением (4)
13 EMBED Equation.3 1415
Второй (отрицательный) член каждого выражения перенесем в левую часть
13 EMBED Equation.3 1415
Подставим конкретные значения (указанные выше) прямых и обратных интенсивностей
13 EMBED Equation.3 1415
После выполнения арифметических действий получим:
13 EMBED Equation.3 1415
Из первого уравнения выразим 13 EMBED Equation.3 1415 и подставим его в остальные уравнения:
13 EMBED Equation.3 1415
Аналогично выражаем 13 EMBED Equation.3 1415 и подставляем в оставшиеся уравнения и получаем:
13 EMBED Equation.3 1415
Выражаем 13 EMBED Equation.3 1415 и подставляем в оставшиеся уравнения и получаем:
13 EMBED Equation.3 1415
Из первого выражения выразим 13 EMBED Equation.3 1415 и подставим в оставшиеся уравнения. После выполнения преобразований получим:
13 EMBED Equation.3 1415
Из первого уравнения выразим13 EMBED Equation.3 1415 и подставим в оставшиеся уравнения:
13 EMBED Equation.3 1415
Из первого уравнения13 EMBED Equation.3 1415 в оставшиеся уравнения:
13 EMBED Equation.3 1415
Из первого уравнения p0 подставим в оставшиеся уравнения:
13 EMBED Equation.3 1415 13 EMBED Equation.3 1415
Определим остальные вероятности, подставляя полученные результаты в обратном порядке
P0= 0,46940 *0,21146=0,1007;
P6 =0,06678 *0,107 +0,1731 *0,2146=0,04387;
P5= 0,1608*0,1007+0,09232*0,04387+0,2801*0,2146=0,08035;
P4=0,07692*0,1007+0,1538*0,08035+0,1538*0,04387+0,7692*0,2146=0,08035;
P3=0,2*0,1007+0,8*0,080035+0,4*0,1853=0,1585;
P2=0,3333*0,1007+0,3333*0,08035+0,3333*0,04387=0,07498;
P1=0,2*0,1007+0,4*0,1853+0,8*0,04387=0,1294.
Выполним проверку. Сумма вероятностей всех событий должна быть равна единице.
p0+p1+p2+p3+p4+p5+p6+p7=1
0,1294+0,07498+0,1585+0,1853+0,08035+0,043870+0,04387+0,1007+0,2146=0,9877.
Полученный результат меньше единицы, так как значение каждой вероятности было округленно.
Вопросы для самоконтроля:
Как составить уравнения Колмогорова.
Тема лекции: «Понятие СМО»
План лекции:
СМО. Основные понятия.
Одноканальные СМО с отказами.
Одноканальные СМО с ожиданием.
Многоканальные СМО с отказами.
Многоканальные СМО с ожиданием.
СМО – системы массового обслуживания.
Структурная схема терминов
[ Cкачайте файл, чтобы посмотреть картинку ]
СМО. Основные понятия
С системами массового обслуживания (CMO) приходится сталкиваться очень часто. Это и работа телефонной станции, и различные очереди (на автозаправке, в поликлинике, в билетной кассе и т.д.), работа некоторых организаций (магазины, мастерские, парикмахерские и т. д.).
Каждая СМО имеет как минимум три элемента: обслуживающий инструмент (станок, касса, канал связи и т. д.), который в дальнейшем будем называть каналом обслуживания или просто каналом; входной поток, т.е. поток заявок, поступающих на обслуживание; выходной поток, т.е. заявки, выполненные СМО (обеспеченные услугой).
Каждая поступившая заявка и принятая на обслуживание внутри СМО обрабатывается некоторое время, называемое временем обслуживания tоб. Все заявки поступают случайным образом и независимо друг от друга. Будем рассматривать простейший случай: в каждый момент времени может поступить только одна заявка. Случаи поступления двух и более заявок в один и тот же момент времени не рассматриваются. Таким образом, в некоторые моменты времени поступившие заявки будут скапливаться на входе СМО и ожидать своей обработки либо покидать СМО необслуженными. В другие моменты времени СМО может простаивать, т. е. не иметь заявок на обслуживание.
График работы СМО представляет собой ступенчатую функцию, т. е. состояние СМО изменяется скачкообразно.
При моделировании работы СМО ставится задача связать технические характеристики СМО, такие, как количество каналов, производительность каждого канала, характер входного потока и т. д., с показателями работы СМО (различные средние величины - среднее время обслуживания одной заявки, среднее время ожидания обслуживания, среднее количество заявок, обслуживаемых за единицу времени и т.д.). Системы массового обслуживания можно классифицировать по разным признакам, например по способу обработки входного потока заявок. (рис. 8.2).
По способу функционирования СМО могут быть:
открытыми, т. е. поток заявок не зависит от внутреннего состояния СМО;
закрытыми, т.е. входной поток зависит от состояния СМО (один ремонтный рабочий обслуживает все каналы по мере их выхода из строя).
2. Одноканальные СМО с отказами
При изучении СМО используем следующие предположения:
Входной поток является пуассоновским с параметром
·.
Время обслуживания подчиняется экспоненциальному закону с параметром
·:
[ Cкачайте файл, чтобы посмотреть картинку ]
Время обслуживания требования не зависит от количества требований, поступивших в систему.
Такая система в любой момент времени t может находиться в одном из двух состояний:
Е0 – в системе 0 требований (система свободна);
Е1 – в системе 1 требование (система занята).
Далее мы будем находить вероятности:
Р0 – система находится в состоянии Е0;
Р1 – система находится в состоянии Е1.
Начиная с некоторого момента времени, вероятность Р0(t) перестает зависеть от времени и становится постоянной; постоянной будет и Р1(t). Эти величины равны соответственно
P0 =
·/
·+
·, P1 = 1-P0 =
·/
·+
·.
В таких случаях говорят, что в системе установился стационарный режим работы. Будем находить коэффициент загрузки системы по формуле
· = P1/P0 =
·/
·.
Напомним, что
· – среднее число требований, прибывающих в систему за единицу времени,
· – среднее число обслуженных требований.
Вероятности застать систему свободной и застать её занятой, соответственно равны теперь
P0 =
·/(
·+
·) = 1/(
·/
·-1) = 1/(
·+1), P1 =
·/(
·+1).
Ясно, что чем больше коэффициент загрузки, тем больше вероятность отказа системы. Это не выгодно потребителю (но выгодно организатору системы, ибо мала вероятность простоя Р0). Если уменьшить коэффициент загрузки, то уменьшится вероятность отказа СМО (это выгодно потребителю), но увеличится вероятность простоя (что не выгодно организаторам системы). Мы имеем дело с противоположными тенденциями и, следовательно, необходимо решать задачи оптимизации режима работы СМО.
3. Одноканальные СМО с ожиданием
Такие системы при условии, что нет ограничений на длину очереди, имеют бесчисленное множество состояний:
Е0, Е1, Е2, Е3, ...
Е0 – в системе 0 требований (система свободна);
Е1 – в системе 1 требование (система занята);
Е2 – в системе 1 требование, и одно требование ожидает в очереди;
Е3 – в системе 1 требование, и два требования ожидают в очереди и т. д.
Для нахождения вероятностей используется следующая формула:
P0 = 1-
·,
· =
·/
·.
Следовательно,
Pk = (1-
·)
·k, k = 1, 2, .
Условие
· > 0 является необходимым и достаточным для наличия стационарного режима работы системы.
Интересно знать, почему стационарный режим существует только при этом условии?
Это условие означает, что среднее число требований, поступивших в СМО, меньше, чем интенсивность самого обслуживания; поэтому система успевает ритмично работать. Теперь ясно, почему система не может работать при условии, когда коэффициент загрузки больше 1. Но почему нет установившегося режима, когда коэффициент загрузки равен 1? Ведь в этом случае, сколько в среднем требований поступает в СМО, столько в среднем и обслуживается. Однако требования поступают в систему неравномерно, и время их обслуживания тоже колеблется, так что могут быть и простои, и перегрузки. Вот поэтому при таком условии не поддерживается стационарный режим.
Подсчет средних характеристик
При изучении СМО важнейшими являются средние значения (математические ожидания) таких случайных величин:
n – количество требований, находящихся в системе;
v – длина очереди;
w – время ожидания в очереди.
Ниже их формулы:
n =
·/(1-
·);
v =
·2/(1-
·);
w = [
·/(1-
·)]*[1/
·].
Пример
Интенсивность потока автомобилей, поступающих на моечную станцию (одноканальная СМО) – 4 автомобиля в час, а интенсивность обслуживания – 5 автомобилей в час. Предполагая, что станция работает в стационарном режиме, найти среднее число автомобилей, находящихся на станции, среднюю длину очереди и среднее время ожидания обслуживания.
Решение
Определяем коэффициент загрузки системы:
· =
·/
· = 0,8.
Далее, используя изученные выше формулы, вычисляем все требуемые характеристики:
n = 0,8/(1-0,8) = 4;
v = 4*0,8 = 3,2;
w = 4/5 = 0,8.
4. Многоканальные СМО с отказами
Сделаем следующие предположения относительно таких систем:
входной поток пуассоновский;
время обслуживания распределено по экспоненциальному закону;
время обслуживания не зависит от входного потока;
все линии обслуживания работают независимо.
Будем считать, что система содержит некоторое количество линий обслуживания s. Она может находиться в состояниях Е0, Е1, Е2, Е3, ... ЕS. Расчёт переходных вероятностей показывает, что из каждого из свободных состояний система может переходить в соседнее состояние, либо в такое же, в каком была.
Для нахождения вероятностей используется следующая формула:
Pk =
·k/k!*P0,
· =
·/
·, где k = 1, 2, ...
Так как сумма всех вероятностей составляет 1, то
[ Cкачайте файл, чтобы посмотреть картинку ]
Отсюда следуют формулы:
[ Cкачайте файл, чтобы посмотреть картинку ]
[ Cкачайте файл, чтобы посмотреть картинку ]
Увеличение коэффициента загрузки системы ведет к увеличению вероятности отказа системы. Это не устраивает потребителей. Уменьшение вероятности отказа системы может быть достигнуто за счёт увеличения количества линий обслуживания.
Однако резкое увеличение количества линий не устраивает организатора, потому что ведёт к дополнительным затратам на приобретение новых линий обслуживания, и увеличивает вероятность простоя линий. Расчет показывает, что среднее число свободных линий обслуживания
· = s-
·(1-Ps).
Теперь ясно, что при сильном увеличении количества линий обслуживания, увеличится среднее число простаивающих линий.
Таким образом, мы имеем дело с двумя противоположными тенденциями. Задача сводится к выбору оптимального варианта. С этой целью будем минимизировать функцию стоимости СМО – С(s). Если через с1 мы обозначим стоимость одного отказа (организатор системы платит штраф за каждый отказ), а через с2 – стоимость простоя одной линии за единицу времени, то функция стоимости будет иметь следующий вид:
C(s) = c1
·Ps+c2
·.
Или в развернутом виде:
[ Cкачайте файл, чтобы посмотреть картинку ]
Сначала с увеличением s она убывает, а затем растёт. Наша задача состоит в том, чтобы найти её минимум.
Пример
Какое оптимальное число линий обслуживания должна иметь СМО, если известно, что
· = 2,
· = 1, c1 = 5, c2 = 1.
Решение
· =
·/
· = 2,
C(s) = 5*2*2s/s!(1+2+4/2!++2s/s!)+1*(s-2(1-Ps)),
P1 =
·/(1+
·) =2/3,
C(1) = 5*2*2/1(1+2)+1(1-2(1-2/3)) = 7.
Аналогично имеем:
C(2) = 4,8;
C(3) = 3,5;
C(4) = 3,1;
C(5) = 3,44.
Таким образом, минимум функции стоимости достигается при s = 4, т. е. оптимальное число линий обслуживания – 4.
5.Многоканальные СМО с ожиданием
Предположения относительно систем, введенные ранее, остаются в силе. Изучение системы ведется по обычной схеме:
Выясняются возможные состояния системы (здесь их бесконечное множество).
Находятся переменные вероятности.
Составляется система уравнений для нахождения Рk – вероятностей пребывания системы в каждом из своих состояний.
Изучаем стационарный режим работы СМО.
Находятся все вероятности, через Р0. Результат таков:
[ Cкачайте файл, чтобы посмотреть картинку ]
Ведётся подсчет средних характеристик: j – среднее количество занятых линий; q – среднее число свободных линий; Р(w > 0) – вероятность ожидания; v – средняя длина очереди.
j =
·;
q = s-
·;
P(w > 0) =
·s*P0/s!(1-
·/s);
v =
·s+1P0/(s-1)!(s-
·)2.
Пример
Определить число взлетно-посадочных полос для самолётов с учетом требования, что вероятность ожидания Р(w > 0) должна быть меньше, чем 0,05. Интенсивность потока равна 27 требований в сутки и интенсивность линий обслуживания – 30 самолётов в сутки.
Решение
· =
·/
· = 0,9.
Используя приведенные выше формулы, имеем:
s = 1: P0 = (1+0,9+0,81/(1(1-0,9)))-1 = 0,1, P(w > 0) = 0,9*0,1/(1-0,9) = 0,9;
s = 2: P0 = 0,380, P(w > 0) = 0,276;
s = 3: P0 = 0,403, P(w > 0) = 0,07;
s = 4: P0 = 0,456, P(w > 0) = 0,015.
Таким образом, надо устраивать 4 взлетно-посадочные полосы.
Вопросы для самоконтроля:
Какие виды СМО Вы знаете?
При каких предположениях изучаются одноканальные СМО с отказами?
Почему стационарный режим в одноканальных СМО с ожиданием существует только при условии
· > 0?
Какие средние характеристики можно рассчитать в одноканальных СМО с ожиданием?
Дана формула C(s) = c1
·Ps+c2
·. Объясните, что означают буквенные обозначения в этой формуле.
Практические занятия:
Практическое занятие №8 «Составление систем уравнений Колмогорова. Нахождение финальных вероятностей. Выбор и обоснование наиболее рационального метода и алгоритма решения задачи, а также оценка сложности выбранного алгоритма»
Тема 3.2. Имитационное моделирование
Основные понятия и термины по теме: имитационная модель, единичный жребий.
План изучения темы (перечень вопросов, обязательных к изучению):
Идея метода имитационного моделирования. Единичный жребий и формы его организации. Простейшие задачи, решаемые методом имитационного моделирования
Получение случайных величин. Таблица случайных чисел. Генераторы случайных чисел. Псевдослучайные числа. Метод середины квадратов.
Разработка алгоритма для решения различных практических задач имитационного моделирования с применением математических методов. Оценка надежности простейших систем методом Монте-Карло
Разработка алгоритма для решения различных практических задач имитационного моделирования с применением математических методов. Расчет СМО с отказами методом Монте-Карло
Теоретический материал
Тема лекции: «Идея метода имитационного моделирования»
План лекции:
Суть имитационного моделирования.
Метод Монте-Карло.
Получение случайных величин.
Суть имитационного моделирования
Имитационное моделирование – получение экспериментальной информации о сложном объекте, которая не может быть получена иным путем, как экспериментируя с его моделью на ПЭВМ.
Как остроумно подметил Ю. Адлер, сочетание слов имитация и моделирование недопустимо и является тавтологией. Но, рассматривая исторический процесс формирования этого термина, пришли к выводу, что это словосочетание определяет в моделировании такую область, которая относится к получению экспериментальной информации о сложном объекте, которая не может быть получена иным путем, как экспериментируя с его моделью на ПЭВМ.
Имитационный объект имеет вероятностный характер функционирования. Для исследователя представляют интерес выводы, носящие характер статистических показателей, оформленных, может быть, даже в виде графиков или таблиц, в которых каждому варианту исследуемых параметров поставлены в соответствие определенные средние значения с набором характеристик их распределения, без получения зависимости в аналитическом виде.
Эта особенность является и достоинством, и одновременно, недостатком имитационным моделей. Достоинство в том, что резко расширяется класс изучаемых объектов, а недостаток – в отсутствии простого управляющего выражения, позволяющего прогнозировать результат повторного эксперимента. Но в реальной жизни также невозможно для сколько-нибудь сложного объекта получить точное значение экономического показателя, а только лишь его ожидаемое значение с возможными отклонениями.
Главной функцией имитационной модели является воспроизведение с заданной степенью точности прогнозируемых параметров её функционирования, представляющих исследовательский интерес. Как объект, так и его модель, должны обладать системными признаками.
Функционирование объекта характеризуется значительным числом параметров. Особое место среди них занимает временной фактор. В большинстве моделей имеется возможность масштабирования или введения машинного времени, т. е. интервала, в котором остальные параметры системы сохраняют свои значения или заменяются некоторыми обобщенными величинами. Таким образом, за счет этих двух процессов – укрупнения единицы временного интервала и расчета событий этого интервала за зависящий от мощности ПЭВМ временной промежуток – и создается возможность прогноза и расчета вариантов управленческих действий.
2. Метод Монте-Карло
Неопределённость в предыдущих темах была стохастической. Поэтому строили аналитическую математическую модель и требовали, чтобы в данных задачах, рассматриваемые процессы были марковскими. На практике это не всегда выполняется и тогда требуется использовать методы имитационного моделирования. Что это такое рассказывалось в предыдущем параграфе, а теперь поговорим о самих методах имитационного моделирования.
Метод Монте-Карло является методом статистического моделирования или имитационного моделирования.
Метод Монте-Карло – это численный метод решения задач при помощи моделирования случайных величин.
Датой рождения метода Монте-Карло принято считать 1948 г. Создателями метода считают математиков Дж. Неймана и С. Улама.
Теоретическая основа метода была известна давно. Однако до появления ЭВМ этот метод не мог найти широкого применения.
Само название метода происходит от названия города Монте-Карло в княжестве Монако, знаменитого своими игорными домами. Дело в том, что одним из простейших механических приборов для получения случайных величин является рулетка. Возникает вопрос: помогает ли метод Монте-Карло выигрывать в рулетку? Нет, не помогает. И даже не занимается этим.
Идея метода чрезвычайно проста и состоит в следующем.
Вместо того чтобы описывать процесс с помощью аналитического аппарата, проводится розыгрыш случайного явления с помощью специально организованной процедуры, включающей в себя случайность и дающей случайный результат. Реализация случайного процесса каждый раз складывается по-разному, т. е. мы получаем различные исходы рассматриваемого процесса. Это множество реализаций можно использовать как некий искусственно полученный статистический материал, который может быть обработан обычными методами математической статистики. После такой обработки можно получить: вероятность события, математическое ожидание и т. д.
При помощи метода Монте-Карло может быть решена любая вероятностная задача, но оправданным он является тогда, когда процедура розыгрыша проще, а не сложнее аналитического расчета.
Пример
По цели производится 3 независимых выстрела, из которых каждый попадает в цель с вероятностью 1/2. Требуется найти вероятность хотя бы одного попадания.
Р(k >= 1) = P(1)+P(2)+P(3) = 1-P(k < 1)
P(0) = 1/2*1/2*1/2 = 1/8
P(k >= 1) = 1-1/8 = 7/8
Эту задачу можно решить розыгрышем – статистическим моделированием. Вместо 3 выстрелов будем бросать 3 монеты, считая, что герб – попадание, решка – промах. Опыт считается удачным, если на одной из монет выпадет герб. Проведем множество опытов, подсчитаем общее количество удач и разделим на число – N (количество проведённых опытов). Таким образом, они получили частоту события, а она при большом числе опытов близка к вероятности.
Метод Монте-Карло применяется: при моделировании случайных процессов, где присутствует множество случайных факторов.
3. Получение случайных величин
Таблица случайных чисел
Выбирается случайная величина, распределенная по следующему закону:
0
1
2
3
4
5
6
7
8
9
0,1
0,1
0,1
0,1
0,1
0,1
0,1
0,1
0,1
0,1
Монтируется диск (рулетка). Диск вращается и резко останавливается, затем выбирается та цифра, на которую указывает неподвижная стрелка.
[ Cкачайте файл, чтобы посмотреть картинку ]
Ряд цифр 20389320
Составляется таблица случайных чисел, выбирается определённое их количество (400).
Составить хорошую таблицу случайных чисел не так-то просто: любой реальный физический прибор вырабатывает случайные величины с распределением, несколько отличающимся от реального распределения.
Генераторы случайных чисел
Любой механический прибор будет слишком медленным для ЭВМ. Поэтому в качестве генераторов случайных чисел чаще всего используют шумы в электронных лампах: если за некоторый промежуток времени уровень шума превысил заданный порог чётное число раз, то записывается единица.
На первый взгляд это очень удобный способ. Пусть m таких генераторов работают параллельно, работают всё время и засылают случайные нули и единицы во все двоичные разряды специальной ячейки. Каждый такт – одно m-разрядное число. В любой момент счёта можно обратиться к этой ячейке и взять оттуда значение случайной величины, равномерно распределённой в интервале (0,1). Конечно, это значение приближенное, записанное в форме m-разрядной двоичной дроби
[ Cкачайте файл, чтобы посмотреть картинку ]
0, а1, а2, аm, где каждая из величин ai имитирует случайную величину с распределением:
0
1
1/2
1/2
Однако и этот метод не свободен от недостатков. Во-первых, трудно проверить "качество" вырабатываемых чисел. Проверки приходится делать периодически, так как из-за каких-либо неисправностей может возникнуть так называемый дрейф распределения (т. е. нули и единицы в каком-либо из разрядов станут появляться неодинаково часто). Во-вторых, обычно все расчёты на ЭВМ проводят дважды, чтобы исключить возможность случайного сбоя. Но воспроизвести те же случайные числа невозможно, если их по ходу счёта не запоминать. А если их запоминать, то мы снова приходим к случаю таблиц.
Датчики такого типа, несомненно, окажутся полезными тогда, когда будут производиться специализированные ЭВМ для решения задач методом Монте-Карло. А для универсальных ЭВМ, на которых расчёты с помощью случайных чисел проводятся лишь изредка, содержать и эксплуатировать специальное устройство просто неэкономично. Лучше использовать так называемые псевдослучайные числа.
Псевдослучайные числа
Поскольку "качество" используемых случайных чисел проверяется с помощью специальных тестов, можно не интересоваться тем, как эти числа получены, лишь бы они удовлетворяли принятой системе тестов. Можно даже попытаться вычислять их по заданной формуле. Но, конечно, это должна быть весьма хитрая формула.
Числа, получаемые по какой-либо формуле и имитирующие значения случайной величины, называются псевдослучайными числами. Под словом "имитирующие" подразумевается, что эти числа удовлетворяют ряду тестов так, как если бы они были значениями этой случайной величины.
Первый алгоритм для получения псевдослучайных чисел был предложен Дж. Нейманом. Он называется методом середины квадратов. Поясним его на примере.
Пример
Пусть задано 4-значное число у0 = 0,9876. Возведём его в квадрат. Получим 8-значное число 0,97535376. Выберем четыре средние цифры этого числа и положим у1 = 0,5353. Затем возведём у1 в квадрат (0,28654609) и снова извлечём четыре средние цифры. Получим у2 = 0,6546. Далее, у2 в квадрате – 0,42850116, у3 = 0,8501; у3 в квадрате – 0,72267001, у4 = 0,2670; у4 в квадрате – 0,07128900, у5 = 0,1289 и т. д.
Но этот алгоритм не оправдал себя: получалось больше чем нужно малых значений. Поэтому разработаны другие алгоритмы.
Достоинства метода псевдослучайных чисел довольно очевидны. Во-первых, на получение каждого числа затрачивается несколько простых операций. Во-вторых, программа занимает всего несколько ячеек накопителя. В-третьих, любое из чисел может быть легко воспроизведено и т. д.
Единственный недостаток – ограниченность количества псевдослучайных чисел.
Подавляющее большинство расчетов по методу Монте-Карло осуществляется c использованием псевдослучайных чисел.
Большинство алгоритмов для получения псевдослучайных чисел имеют вид
·k+1 = F(yk)
Если случайное число задано, то все последующие числа вычисляются по одной и той же формуле при k = 1, 2, 3,
Метод сравнений (метод вычетов)
Наиболее распространенный алгоритм для получения псевдослучайных чисел был предложен Д. Лемером. В основе этого алгоритма лежит функция у = {gx}, однако, для удобства реализации на ЭВМ алгоритм строится несколько иначе.
Определяется последовательность целых чисел mk, в которой начальное число m0 = 1 задано, а все последующие числа m1, m2, вычисляются по одной и той же формуле
mk+1 = 517* mk(mod 240), (1)
при k = 0, 1, 2, По числам mk вычисляются псевдослучайные числа
·k = 2-40mk.
Формула ([ Cкачайте файл, чтобы посмотреть ссылку ]) означает, что число mk+1 равно остатку, полученному при делении.
Отсюда происходят оба названия метода.
Вопросы для самоконтроля:
В чем заключается суть имитационного моделирования?
В чем заключаются достоинства и недостатки такого типа моделирования?
Как применяется метод Монте-Карло? Приведите пример такой задачи.
Какие способы получения случайных величин Вы знаете?
Что такое псевдослучайные числа? Расскажите о двух основных способах их получения.
Тема лекции: «Решение различных практических задач имитационного моделирования с применением математических методов.»
План лекции:
Оценка надежности простейших систем методом Монте-Карло.
Расчет СМО с отказами методом Монте-Карло.
1. Оценка надежности простейших систем методом Монте-Карло
Пример: Система состоит из двух блоков, соединенных последовательно. Система оказывает при отказе хотя бы одного блока. Первый блок содержит два элемента: А, В (они соединены параллельно) и оказывает при одновременном отказе обоих элементов. Второй содержит один элемент С и отказывает при отказе этого элемента.
а) Найти методом Монте-Карло оценку Р* надежности (вероятности безотказной работы) системы, зная вероятности безотказной работы элементов: Р (А)=0,8, Р (В)=0,85, Р (С)=0,6; б) найти абсолютную погрешность (Р-Р* (, где Р- надежность системы, вычисленная аналитически. Произвести 50 испытаний.
Решение. а) Выбираем из таблицы приложения (равномерно распределенные числа) три случайных числа: 0,10, 0,09 и 0,73; по правилу *) (если случайное число меньше вероятности события, то событие наступило; если случайное число больше или равно вероятности события, то событие не наступило) разыграем события А, В, С, состоящие в безотказной работе соответственно элементов А, В, С. Результаты испытания будем записывать в расчетную таблицу .
Поскольку Р (А)=0,8 и 0,10 <0,8, то событие наступило, т.е. элемент А в этом испытании работает безотказно. Так как Р (В)=0,85 и 0,09< 0,85, то событие В наступило, т.е. элемент В работает безотказно.
Таким образом, оба элемента первого блока работают; следовательно, работает и сам первый блок. В соответствующих клетках табл. ставим знак плюс.
Таблица
Номер
испытания
Блок
Случайные числа,
моделирующие элементы
Заключение о работе
элементов
блоков
системы
А
В
С
А
В
С
1
Первый
Второй
0,10
0,09
0,73
+
+
-
+
-
-
2
Первый
Второй
0,25
0,33
0,76
+
+
-
+
-
-
3
Первый
Второй
0,52
0,01
0,35
+
+
+
+
+
+
4
Первый
Второй
0,86
0,34
0,67
-
+
-
+
-
-
Так как Р (С)=0,6 и 0,73< 0,6, то событие С не наступило, т.е. элемент с получает отказ; Другими словами, второй блок, а значит и вся система, получают отказ. В соответствующих клетках табл. 57 ставим минус.
Аналогично разыгрываются и остальные испытания. В табл. приведены результаты четырех испытаний.
Произведя 50 испытаний, получим, что в 28 из них система работала безотказно. В качестве оценки искомой надежности Р примем относительную частоту Р * =28/50=0,56.
б) Найдем надежность системы Р аналитически. Вероятности безотказной работы первого и второго блоков соответственно равны:
13 EMBED Equation.3 1415
Вероятность безотказной работы системы
P=P1*P2=0,97*0,6=0,582
Искомая абсолютная погрешность (Р-Р*(=0,582-0,56=0,022.
2. Расчет СМО с отказами методом Монте-Карло
Пример: В трехканальную систему массового обслуживания с отказом поступает пуассоновский поток заявок. Время между поступлениями двух последовательных заявок распределено по показательному закону f(()=5e-5( . Длительность обслуживания каждой заявки равна 0,5 мин. Найти методом Монте-Карло математическое ожидание а числа обслуженных заявок за время Т=4 мин.
Решение:
Пусть Т1=0- момент поступления первой заявки. Заявка поступит в первый канал и будет им обслужена. Момент окончания обслуживания первой заявки Т1+0,5=0+0,5=0,5. В счетчик обслуженных заявок записываем единицу.
Моменты поступления последующих заявок найдем по формуле
Т(= Т(-1+ (( ,
где (( - длительность времени между двумя последовательными заявками с номерами (-1 и (.
Возможные (( = - (1/() ln ri = = (1/()(- ln ri ).
Учитывая, что, по условию, (=5, получим (( =0,2 (- ln ri ).
Случайные числа ri берем из таблицы приложения, начиная с первой строки сверху. Для нахождения времени между поступлениями первой и второй заявок возьмем случайное число r=0,10.
Тогда (2=0,2*(-ln 0,10)=0,2*2,30=0,460. Первая заявка поступила в момент T1=0.
Следовательно, вторая заявка поступила в момент T2= T1+0,4600+0,460=0,460. В этот момент первый канал еще занят обслуживанием первой заявки, поэтому вторая заявка поступит во второй и будет им обслужена. Момент окончания обслуживания второй заявки T2+05=0,460+0.5=0.960 . В счетчик обслуженных заявок добавляем единицу.
По очередному случайному числу r=0.09 разыграем время (3 между поступлениями второй и третьей заявок:
(3=0,2(-ln 0,09)=0,2*2,41=0,482.
Вторая заявка поступила в момент T2= 0,460 . Поэтому третья заявка поступила в момент T3= T2+0,482=0,460+0,482=0,942. В этот момент первый канал уже свободен и третья заявка поступит в первый канал. Момент окончания обслуживания третьей заявки
T3+0,5=0,942+0,5=1,442.В счетчик обслуженных заявок добавляем единицу.
Дальнейший расчет производят аналогично (табл. 59), причем если момент поступления заявки все каналы заняты (момент поступления заявки меньше каждого из моментов окончания обслуживания), то в счетчик отказов добавляют единицу.
Заметим, что обслуживание 20-й заявки закончится в момент 4 148,>4, поэтому эта заявка получает отказ.
Испытание прекращают (в таблице записывают «стоп»), если момент поступления заявки T>4.
Таблица
номер заявки
i
Случайное числоri
-ln ri
Время между двумя последовательными заявками
(i=0,2(-ln ri)
Момент поступления заявки
Ti= Ti-1+(i
Момент
Ti+0,5
окончания обслуживания заявки каналом
Счетчик
1
2
3
Обслуженных заявок
отказов
1
0
0,500
1
2
0,10
2,30
0,460
0,460
0,960
1
3
0,09
2,41
0,482
0,942
1,442
1
4
0,73
0,32
0,064
1,006
1,506
1
5
0,25
1,39
0,278
1,284
1,784
1
6
0,33
1,11
0,222
1,506
2,006
1
7
0,76
0,27
0,054
1,560
2,060
1
8
0,52
0,65
0,130
1,690
1
9
0,01
4,60
0,920
2,610
3,110
1
10
0,35
1,05
0,210
2,820
3,320
1
11
0,86
0,15
0,030
2,850
3,350
1
12
0,34
1,08
0,216
3,066
1
13
0,67
0,40
0,080
3,146
3,646
1
14
0,35
1,05
0,210
3,356
3,856
1
15
0,48
0,73
0,146
3,502
4,002
1
16
0,76
0,27
0,054
3,556
1
17
0,80
0,22
0,044
3,600
1
18
0,95
0,05
0,010
3,610
1
19
0,90
00,10
0,020
3,630
1
20
0,91
0,09
0,018
3,648
4,148
1
21
0,17
1,77
0,354
4,002
(стоп)
итого
Х1=12
8
Из таблицы находим, что за 4 мин всего поступило 20 заявок; обслужено x1=12.
Выполним аналогично еще пять испытаний, получим x2=15, x3=14, x4=12, x5=13, x6=15.
В качестве оценки искомого математического ожидания а числа обслуженных заявок примем выборочную среднюю
a *=13 EMBED Equation.3 1415=(2*12+13+14+2*15)/6=13,5.
Практические занятия:
Практическое занятие №9 «Решение задачи управления запасами и задачи теории СМО, используя имитационное моделирование»
Тема 3.3. Прогнозирование
Основные понятия и термины по теме: прогноз, скользящее среднее, линейное сглаживание.
План изучения темы (перечень вопросов, обязательных к изучению):
Понятие прогноза. Количественные и качественные методы прогноза
Метод наименьших квадратов
Теоретический материал
Тема лекции: «Понятие прогноза. Количественные и качественные методы прогноза. Метод наименьших квадратов»
План лекции:
Классификация прогнозирования.
Формализованные методы прогнозирования.
Эвристические методы прогнозирования.
Комплексные методы прогнозирования.
Линейное сглаживание функции.
Структурная схема терминов
[ Cкачайте файл, чтобы посмотреть картинку ]
Классификация прогнозирования
Прогнозирование – предсказание на основе каких-то методов как будет себя вести объект в определенный момент времени в будущем.
Прогнозы подразделяются на формализованные, эвристические и комплексные. Каждому классу прогноза присущи свои достоинства и ограничения.
Формализованные методы позволяют получать количественные показатели. При разработке таких прогнозов исходят из предположения об инерционности системы, т. е. предполагают, что в будущем система будет развиваться по тем же закономерностям, которые были у неё в прошлом и есть в настоящем. Недостатком формализованных методов является ограниченная глубина упреждения, находящаяся в пределах эволюционного цикла развития системы, за пределами которого надёжность прогнозов падает. К формализованным методам относятся экстраполяционные и регрессивные методы, метод группового учёта аргументов (МГУА), факторный анализ и др.
Эвристические методы основаны на использовании интеллекта человека, который на основании своих знаний и практического опыта способен предсказать качественные изменения в поведении прогнозируемого объекта, определять силу и продолжительность скачков его развития. Эвристические методы применяются там, где существует вероятность скачкообразных процессов в развитии системы, подразделяются на методы индивидуальных и коллективных экспертных оценок.
Комплексное прогнозирование объединяет в единую систему формализованные и эвристические методы, что позволяет повысить качество прогнозов.
В зависимости от глубины упреждения прогнозы подразделяются на оперативные, среднесрочные и перспективные:
Оперативные прогнозы – ограничены по срокам от долей секунды до года.
Среднесрочные – от года до пяти лет.
Перспективные – более пяти лет.
Если формализованные методы в силу присущих им ограничений используются для оперативных и краткосрочных прогнозов, то эвристические методы чаще используются для среднесрочных и перспективных прогнозов.
Формализованные методы прогнозирования
Методы экстраполяции
Методы экстраполяции в математическом смысле представляют собой распространение характера изменения функции из области её наблюдения в область, лежащую вне этого интервала.
Задача экстраполяции формируется так: пусть в интервале (t0, t) известны значения функции f(x), требуется определить значения этой функции в точке t+1, лежащей вне этого интервала.
Предположение об эволюционном характере развития прогнозируемых объектов ограничивает применение метода экстраполяции только теми периодами времени, в течение которых в развитии объектов не предлагается скачкообразных изменений. Оценка и экстраполяция тенденций получила широкое применение в нормативном прогнозировании. С помощью этого метода пытаются получить ответы на вопрос о наличии разумных шансов на решение поставленной задачи при помощи того же самого механизма, который существовал ранее.
Несмотря на многообразие явлений, технологическое и экономическое прогнозирование с помощью метода экстраполяции можно проводить ограниченным числом функций, которые подразделяются на четыре класса:
Класс 1: линейный рост функции на большей части интервала с уменьшением темпов в его конце. Такие кривые характерны для роста производительности труда, когда исчерпаны ресурсы данной технологии и рост производительности труда начинает замедляться. Для дальнейшего его возрастания необходим переход на новую технологию.
Класс 2а: на всём интервале развития наблюдаются экспоненциальный рост. Уравнение кривой для функции этого класса имеет вид y = Aeat, где А – значение процесса при t = 0; а – параметр процесса. Необходимо отметить, что этот процесс является линейным для логарифма рассматриваемой функции lnA = lnA+at.
Класс 2б: S-образные кривые, характеризующие начальным экспоненциальным или почти экспоненциальным ростом. Такие кривые часто используются для прогнозирования плотности телефонов в целом по стране или большому району. Примером функции класса 2б служит кривая логического роста (кривая Перла) y = L/(l+a0e-alt), где L – предел развития объекта; a0, a1 – константы; t – время.
Класс 3: функция с дважды экспоненциальным ростом или даже ещё более крутым подъёмом с последующим переходом в более пологую кривую. Эти функции характеризуются ростом технических систем в условиях интенсивности исследований и разработок.
Класс 4: функция с медленным экспоненциальным ростом в начале развития, который сменяется внезапным, более быстрым ростом и, наконец, замедлением в конце развития.
Регрессивный анализ
Уравнения множественной регрессии являются одним из наиболее распространённых методов многофакторного прогнозирования. Для линейного случая модель множественной регрессии записывается в виде
[ Cкачайте файл, чтобы посмотреть картинку ]
при j = 1m, где ai – коэффициент модели, i = 0n; uij – значения i-й функции независимой переменной; n – число независимых переменных в модели,
·i – случайная ошибка.
К недостаткам регрессивного анализа следует отнести необходимость субъективного определения исследователем структуры модели. Кроме того, регрессионный анализ позволяет строить модели только в области, где число коэффициентов модели меньше или равно числу точек опытных данных.
Метод группового учета аргументов (МГУА)
Метод группового учета аргументов (МГУА) свободен от недостатков, присущих моделям, которые получены методом классического анализа. В основу положен принцип самоорганизации, основанный на применении внешних критериев выбора.
Критерий называется внешним, если его определение основано на новой информации, неиспользованной при синтезе модели.
Суть принципа самоорганизации моделей оптимальной сложности состоит в том, что при постепенном усложнении математической модели отдельные её элементы проверяются в соответствии с внешними критериями, после этого часть модели допускается для дальнейшего усложнения. МГУА направлен на уменьшение необходимой априорной информации, вводимой в ЭВМ. В память ЭВМ вводят небольшую таблицу (например, 10-20 точек) и указывают критерий выбора модели, по которому машина находит объективную единственную модель оптимальной сложности.
Для малого числа переменных (до 20) используется комбинаторный алгоритм МГУА, который производит выбор модели из некоторого полного полинома с помощью приравнивания к нулю его слагаемых. В результате получают множество укороченных полиномов с постепенным усложнением структуры, каждый из которых оценивается по избранному критерию. Полином с наилучшим значением критерия является моделью оптимальной сложности.
Алгоритм МГУА с последовательным выделением трендов позволяет создавать модели множественной регрессии, основу которых составляет сумма уравнений регрессии по одному аргументу. По этому алгоритму расчет ведется следующим образом: первоначально определяется первый тренд и рассчитывается соответствующее отклонение истинных значений функции от тренда. Затем полученные отклонения аппроксимируются вторым трендом и определяется второй остаток. Число выделяемых трендов зависит от размерности функции. Их может быть два, три, четыре и более. Полученные значения трендов складываются. Окончательное выражение множественной регрессии:
y =
·a0j+a1f(x1)+a2f(x2)++anf(xn),
где a0j – свободный член j-го тренда.
Обобщенный алгоритм МГУА обеспечивает получение оптимальных моделей при использовании в качестве опорной функции аддитивной и мультипликативной моделей трендов. Для сокращения числа входных аргументов в этом алгоритме используется алгоритм последовательного выделения трендов для выбора оптимальной опорной модели. Затем осуществляется перебор всех возможных комбинаций выделенных трендов либо в классе сумм, либо в классе произведений.
Результат перебора – оптимальная комбинация, дающая наиболее регулярные решения.
При проведении расчётов по алгоритму МГУА таблица исходных данных делится на две части: обучающая (A) и проверяющая (B). Деление исходных данных проводят в отношении:
NA = 0,7N и NB = 0,3N или NA = 0,5N и NB = 0,5N, где N – общее число данных.
В качестве критерия получения оптимальной модели МГУА используется минимум среднеквадратичной ошибки на проверочной последовательности данных: первая разность прогнозных и реальных значений
·(1) или минимум среднеквадратичной ошибки приращений; вторая разность прогнозных и реальных значений
·(2).
Первый критерий рассчитывается по формуле:
[ Cкачайте файл, чтобы посмотреть картинку ]
где y*(k) – данные прогноза; y(k) – реальные данные части В.
Второй критерий рассчитывается по формуле:
[ Cкачайте файл, чтобы посмотреть картинку ]
где
·y*(k) – разности между данными прогноза;
·y(k) – разности между реальными данными.
Эвристические методы прогнозирования
Методы эвристических оценок основываются на выявлении мнений экспертов о перспективах развития объекта прогнозирования. Из подобных методов наиболее известен метод Дельфы, характерными особенностями которого является анонимный опрос экспертов, проводящийся в несколько туров; статистическая обработка результатов опроса каждого тура с последующим ознакомлением экспертов с её результатами. Перед каждым новым туром опроса эксперты имеют право изменять высказанное ими ранее мнение. Анонимность ответов необходима для того, чтобы исключать ряд нежелательных психологических факторов, которые наблюдаются в группах специалистов, проводящих очный обмен мнениями. К таким факторам относится склонность группы к компромиссу, принятие группой мнения "авторитетов", приспособление её к мнению большинства.
Процедура проведения экспертизы может быть различной. Однако в ней всегда можно выделить три этапа.
На первом этапе эксперты привлекаются к работе по уточнению модели объекта прогнозирования.
На втором – дают ответы на поставленные в анкете вопросы. При этом структурно-организованный набор вопросов должен быть логически связан с основной целью экспертизы, а формулировка вопросов должна исключать всякую смысловую неопределённость.
На третьем этапе, после статистической обработки результатов опроса тура, эксперты привлекаются для консультации по недостающей информации, необходимой для формирования окончательного прогноза.
При статистической обработке содержащихся в анкетных результатах экспертных оценок определяются статистические параметры прогнозируемых характеристик, их доверительные интервалы, статические оценки согласованности мнений экспертов.
Среднее значение прогнозируемой величины определяется по формуле
[ Cкачайте файл, чтобы посмотреть картинку ]
где Bj – значение прогнозируемой величины, данной j-м экспертом; n – число экспертов в группе.
Приближенное значение доверительного интервала ±b-tX*(D/(n-1)), t – параметр, определенный из таблиц Стьюдента для заданного уровня доверительной вероятности и числа степеней свободы l = (n-2).
Доверительные границы значений прогнозируемой величины вычисляются по формулам:
Для верхней границы: Ав = В+b.
Для нижней границы: Ан = В-b.
Коэффициент вариаций оценок экспертов определяется из зависимости:
V =
·/B,
где
· – среднеквадратичное отклонение.
Проведение опроса в несколько туров и обязательное ознакомление экспертов с результатами каждого тура обеспечивает сходимость данных прогноза к медианному значению.
Морфологический метод позволяет не только получить технические характеристики прогнозируемого объекта, но и определить его структуру. Для этого исследуемый объект (проблема) разбивается на относительно независимые части (элементы). Затем для каждой из частей разрабатывается многовариантное решение, в основу которого берутся её конструктивные, технологические, функциональные или другие особенности. Общее решение о структуре и свойствах объекта или процесса получают, взяв одно решение от каждой части, руководствуясь при этом возможными ограничениями. Морфологический метод связан с системным подходом к изучаемому объекту, так как предусматривает использование всей совокупности знаний об объекте. Благодаря упорядоченному подходу к рассмотрению проблемы, он дает систематизированную информацию по всем возможным решениям изучаемой проблемы. Метод включает этапы исследования: точную формулировку подлежащей решению проблемы; тщательный анализ всех параметров, важных с точки зрения решения проблемы: построение морфологического ящика; выбор оптимального решения.
Комплексные методы прогнозирования
Каждый метод прогнозирования обладает своими достоинствами и недостатками, поэтому их объединение повышает достоверность прогнозов. Общий алгоритм комплексных методов прогнозирования предусматривает объединение формализованных и эвристических методов в одной системе. Эти методы могут находиться в следующих соотношениях:
Данные обоих прогнозов не противоречат друг другу, их можно совместно обрабатывать и получать комбинированный прогноз.
Данные этих прогнозов противоречивы, здесь требуется ввести обратные связи, раскрывающие причины расхождения данных прогнозов и произвести измерения условий прогнозирования.
Выбор комплексных методов в значительной степени зависит от сроков, на которые делается прогноз и от объема имеющейся информации. В общем, комплексные методы наиболее приемлемы для долгосрочных прогнозов.
5.Линейное сглаживание функции
Метод наименьших квадратов один из методов [ Cкачайте файл, чтобы посмотреть ссылку ] для оценки неизвестных величин по результатам измерений, содержащим случайные ошибки.
Метод наименьших квадратов применяется также для приближённого представления заданной функции другими (более простыми) функциями и часто оказывается полезным при обработке наблюдений.
Метод наименьших квадратов предусматривает нахождение параметров функциональной зависимости из условия минимума суммы квадратов отклонений.
1. Если 13 EMBED Equation.3 1415 - линейная функция, т.е. 13 EMBED Equation.3 1415, то 13 EMBED Equation.3 1415, неизвестные параметры 13 EMBED Equation.3 1415определяются из системы
13 EMBED Equation.3 1415 (1)
Формулы, служащие для аналитического представления опытных данных, получили название эмпирических формул.
Система (1) называется системой нормальных уравнений.
2. Если 13 EMBED Equation.3 1415 - квадратичная функция, т.е. 13 EMBED Equation.3 1415, то 13 EMBED Equation.3 1415, неизвестные параметры 13 EMBED Equation.3 1415определяются из системы нормальных уравнений:
13 EMBED Equation.3 1415 (2)
Пример 1. Имеются следующие данные о величине пробега автомобиля 13 EMBED Equation.3 1415 (тыс. км) и 13 EMBED Equation.3 1415 – расходе масла (л/тыс. км):
13 EMBED Equation.3 1415
50
70
90
110
130
13 EMBED Equation.3 1415
0,2
0,5
0,8
1,1
1,3
Полагая, что между переменными 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415 существует линейная зависимость, найти эмпирическую формулу 13 EMBED Equation.3 1415 методом наименьших квадратов.
Решение:
Перепишем таблицу в виде столбцов и проведем необходимые вычисления:
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
1
2
3
4
5
50
70
90
110
130
0,2
0,5
0,8
1,1
1,3
2500
4900
8100
12100
16900
10
35
72
121
169
13 EMBED Equation.3 1415
450
3,9
44500
407
Система линейных уравнений (1) для определения величин 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415 примет вид
13 EMBED Equation.3 1415
Ее решение 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415.
Таким образом, линейная зависимость имеет вид 13 EMBED Equation.3 1415.
Строим полученную прямую и исходные точки в одной системе координат.
Пример: 2) Аппроксимируем таблично заданную функцию у= 13 EMBED Equation.3 1415 - квадратичной 13 EMBED Equation.3 1415.
Составим систему для определения 13 EMBED Equation.3 1415:
13 EMBED Equation.3 1415
Перепишем таблицу в виде столбцов и проведем необходимые вычисления:
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
0
5
0,707
25
125
625
3,535
17,675
1
5,5
0,79
30,25
166,375
915,0625
4,345
23,8975
2
6
1,11
36
216
1296
6,66
39,96
3
6,5
0,674
42,25
274,625
1785,0625
4,381
28,4765
4
7
0,948
49
343
2401
6,636
46,452
5
7,5
0,516
56,25
421,875
3164,0625
3,87
29,025
13 EMBED Equation.3 1415
37,5
4,745
238,75
1546,875
10186,1875
29,427
185,486
Система линейных уравнений для определения величин 13 EMBED Equation.3 1415 примет вид
13 EMBED Equation.3 1415
Решим систему методом Крамера:
6
37,5
238,75
37,5
238,75
1546,875
=61,25
238,75
1546,875
10186,19
4,745
37,5
238,75
29,427
238,75
1546,875
=-394,209
185,486
1546,875
10186,19
6
4,745
238,75
37,5
29,427
1546,875
=147,6733
238,75
185,486
10186,19
6
37,5
4,745
37,5
238,75
29,427
=-12,0706
238,75
1546,875
185,486
А0=-394,209/61,25=-6,44
А1= 147,6733/61,25= 2,41
А2=-12,0706/61,25= -0,20
Искомый многочлен:
13 EMBED Equation.3 1415
Вопросы для самоконтроля:
Как подразделяются прогнозы в зависимости от глубины упреждения?
Что такое метод экстраполяции?
Относится ли метод регрессивного анализа к комплексным методам?
Какова характерная особенность метода Дельфы?
В чем особенность морфологического метода?
Практические занятия
Практическое занятие №10 «Построение прогнозов количественными и качественными методами. Выбор и обоснование наиболее рационального метода и алгоритма решения задачи, а также оценка сложности выбранного алгоритма»
Тема 3.4. Теория игр
Основные понятия и термины по теме: игра, игроки, партия, выигрыш, ход, личные и случайные ходы, стратегические игры, стратегия.
План изучения темы (перечень вопросов, обязательных к изучению):
Предмет и задачи теории игр. Основные понятия. Классификация игр: в зависимости от количества игроков ; по количеству стратегий; по характеру взаимодействия ; по характеру выигрышей ; по виду функций выигрыша; матричная игра ;биматричная игр; непрерывной. Стратегия игрока. Оптимальная стратегия игрока
Матричные игры: чистые и смешанные стратегии
Теоретический материал
Тема лекции: «Предмет и задачи теории игр. Основные понятия»
План лекции
Предмет и задачи теории игр.
Классификация игр.
Игра – это модель конфликтной ситуации, т. е. ситуации в которых сталкиваются интересы двух (и более) сторон, преследующих разные (иногда противоположные) цели, причем выигрыш каждой стороны зависит от того, как поведут себя другие.
Структурная схема терминов
[ Cкачайте файл, чтобы посмотреть картинку ]
1. Предмет и задачи теории игр
В этом параграфе рассмотрим более неудобный вид неопределенности, чем в предыдущих темах. Если ранее мы рассматривали задачи, которые содержали стохастическую неопределенность, то теперь рассмотрим задачи, в которых некоторые параметры, от которых зависит успех операции, неизвестны, и нет никаких данных, позволяющих судить о том, какие значения более, а какие менее вероятны. Такого рода задачами и занимается теория игр. В некоторых случаях разработанные в ней методы дают возможность фактически найти оптимальное решение. Гораздо чаще эти методы позволяют попросту глубже разобраться в ситуации и оценить каждое решение с различных (иногда противоречивых) точек зрения.
Наиболее простыми из ситуаций, содержащих неудобную неопределенность, являются, так называемые конфликтные ситуации, т. е. ситуации в которых сталкиваются интересы двух (и более) сторон, преследующих разные (иногда противоположные) цели, причем выигрыш каждой стороны зависит от того, как поведут себя другие. К ним принадлежит любая ситуация, складывающаяся в ходе боевых действий, ряд ситуаций в области экономики и т. д. Модель конфликтной ситуации будем называть игрой.
В некотором смысле "конфликтной" можно считать ситуацию с несколькими критериями: каждый из них предъявляет к управлению свои требования, как правило, противоречивые.
Теория игр представляет собой математическую теорию конфликтных ситуаций. Ее цель – выработка рекомендаций по разумному поведению участников конфликта.
От реального конфликта игра отличается тем, что ведется по определенным правилам.
2.Классификация игр
Классификацию игр можно проводить: по количеству игроков, количеству стратегий, характеру взаимодействия игроков, характеру выигрыша, количеству ходов, состоянию информации и т. д.
В зависимости от количества игроков различают игры двух и n игроков. Первые из них наиболее изучены. Игры трёх и более игроков менее исследованы из-за возникающих принципиальных трудностей и технических возможностей получения решения. Чем больше игроков – тем больше проблем.
По количеству стратегий игры делятся на конечные и бесконечные. Если в игре все игроки имеют конечное число возможных стратегий, то она называется конечной. Если же хотя бы один из игроков имеет бесконечное количество возможных стратегий, игра называется бесконечной.
По характеру взаимодействия игры делятся на:
Бескоалиционные: игроки не имеют права вступать в соглашения, образовывать коалиции.
Коалиционные (кооперативные) – игроки могут вступать в коалиции.
В кооперативных играх коалиции наперёд определены.
По характеру выигрышей игры делятся на:
Игры с нулевой суммой (общий капитал всех игроков не меняется, а перераспределяется между игроками; сумма выигрыша всех игроков равна нулю).
Игры с ненулевой суммой.
По виду функций выигрыша игры делятся на:
Матричные.
Биматричные.
Непрерывные.
Выпуклые и т. д.
Матричная игра – это конечная игра двух игроков с нулевой суммой, в которой задаётся выигрыш игрока 1 в виде матрицы (строка матрицы соответствует номеру применяемой стратегии игрока 1, столбец – номеру применяемой стратегии игрока 2; на пересечении строки и столбца находится выигрыш игрока 1, соответствующий применяемым стратегиям).
Для матричных игр доказано, что любая из них имеет решение, и оно может быть найдено путём сведения игры к задаче линейного программирования.
Биматричная игра – это конечная игра двух игроков с ненулевой суммой, в которой выигрыши каждого игрока задаются матрицами отдельно для соответствующего игрока (в каждой матрице строка соответствует стратегии игрока 1, столбец – стратегии игрока 2, на пересечении строки и столбца в первой матрице находится выигрыш игрока 1, во второй – выигрыш игрока 2).
Для биматричных игр также разработана теория оптимального поведения игроков, однако, решать такие игры сложнее, чем обычные матричные.
Непрерывной считается игра, в которой функция выигрышей каждого игрока является непрерывной в зависимости от стратегий. Доказано, что игры этого класса имеют решения, однако, не разработано практически приемлемых методов их нахождения.
Если функция выигрышей является выпуклой, то такая игра называется выпуклой. Для них разработаны приемлемые методы решения, состоящие в отыскивании чистой оптимальной стратегии (определённого числа) для одного игрока и вероятностей применения чистых стратегий другого игрока. Такая задача решается сравнительно легко.
Стратегия игрока – совокупность правил, определяющих выбор варианта действий при каждом ходе в зависимости от сложившейся ситуации.
Оптимальная стратегия игрока – такая стратегия, которая обеспечивает ему наилучшее положение в данной игре, т. е. максимальный выигрыш.
Задача теории игр – выявление оптимальных стратегий игроков.
Вопросы для самопроверки:
Что такое игра?
Приведите примеры конфликтных ситуаций.
Какова цель теории игр?
Какие основные типы игр Вы знаете?
Приведите примеры игр с нулевой суммой
Практические занятия – не предусмотрено.
Тема 3.5 Теория принятия решений
Основные понятия и термины по теме: решение, условия определённости, неопределённости, риска.
План изучения темы (перечень вопросов, обязательных к изучению):
Область применения теории принятия решений. Принятие решений в условиях определенности, риска и неопределенности. Общие положения теории принятия решений. Основные понятия системного анализа. Основные понятия исследования операций
Критерий принятия решений. Дерево решений
Теоретический материал
Тема лекции: «Основные понятия ТПР»
План лекции:
Основные понятия и методы теории принятия решений.
Основные этапы решения задач ТПР.
Основные понятия и методы теории принятия решений
При проектировании сложных технических систем, создании сложных промышленных комплексов и управлении ими анализе экологических ситуаций, в других сферах деятельности человека возникают задачи принятия наилучших решений. Для решения этих прикладных задач были созданы и в настоящее время разрабатываются специальные математические модели и методы, которые принято объединять под названием «Теория принятия решений». Таким образом, ТПР – это наука, изучающая методы принятия оптимальных решений в различных областях целенаправленной деятельности человека.
В настоящее время большое место в ТПР отводится изучению методов автоматизации производства и управления различными видами деятельности на базе современной вычислительной техники.
ТПР, как любая научная дисциплина, оперирует определенными понятиями и определениями.
Операцией (О) называется совокупность взаимосогласованных действий, направленных на достижение определенных целей.
До тех пор, пока цель не установлена, нет смысла говорить об операции.
Оперирующей стороной (ОС) называются отдельные лица или коллективы, а также автоматы, стремящиеся в данной операции к достижению цели.
Активными средствами проведения операции (АС) называется совокупность материальных, энергетических, трудовых, финансовых и др. средств, используемых оперирующей стороной для успешного хода операции и достижения цели.
Очевидно, ОС должна обладать определенной свободой выбора АС и их расходования, тем самым обладая возможностью влиять на ход О. В противном случае О перестает быть управляемой, а ОС становится пассивным наблюдателем.
Стратегиями оперирующей стороны в данной операции называются допустимые способы расходования ею имеющихся АС.
Оценка приемлемости, сравнение стратегий и выбор наилучшей из них (оптимальной) в смысле принятой цели составляет основную задачу ТПР.
Действующими факторами операции называются объективные условия и обстоятельства, определяющие ее особенности и непосредственно влияющие на ее (О) исход.
Различают факторы определенные (точно известные) и неопределенные (имеющие вероятностную природу, или проявляющиеся беспорядочно). Все они подразделяются на контролируемые и неконтролируемые, причем неконтролируемыми бывают обычно неопределенные факторы. Наличие контролируемых факторов указывает на возможность управления ходом О оперирующей стороной.
Критерием эффективности (КЭ) операции называется показатель достигнутого соответствия между результатом предпринимаемых действий и целью операции.
Важнейшая особенность КЭ в сравнительной оценке различных стратегий до начала их реализации, а также использование на завершающем этапе для характеристики полученных результатов. как правило, интерес представляют стратегии, позволяющие достичь максимального или минимального значения КЭ.
Состоянием операции (СО) в некоторый момент времени t называется совокупность ее характеристик, проявляющихся в этот момент о объективно отражающих положение О.
Всякая операция представляет процесс во времени, проходящий различные этапы развития. Обычно этот процесс как-то проявляет себя, обнаруживает некоторые свои свойства, которые измеримы и допускают количественную оценку. Эти параметры формально отображают ход операции и называются фазовыми переменными.
Математической моделью (ММ) операции называются формальные соотношения, устанавливающие связь принятого КЭ с действующими факторами О и связи контролируемых и неконтролируемых факторов между собой.
Чтобы построить ММ, необходимо количественно оценить проявления рассматриваемых факторов и указать группы изменяемых параметров, формально представляющих эти факторы. Процесс создания ММ требует четкого осознания цели операции, проникновение в сущность моделируемых явлений, умение отделять главное от второстепенного.
Решением (Р), связанным с выбранной моделью, называется конкретный набор значений контролируемых параметров.
Решение можно получить различными методами с различной степенью точности, в различных предположениях о свойствах неконтролируемых факторов.
Исследователем операции называется специалист, который проводит исследования по отысканию наилучших решений для оперирующей стороны. Исследователь входит в состав оперирующей стороны, но его роль ограничивается рекомендацией, вытекающей из результатов исследования модели операции. Право окончательного принятия решения остается за руководящим органом, ответственным за проведение О и владеющим дополнительной неформализуемой информацией относительно допустимых стратегий.
Важное значение для исследователя О при выработке решения имеет его информированность о неконтролируемых факторах. В зависимости от этого последние могут быть разделены на три группы. Каждой групе соответствует свой тип задач ТПР.
Фиксированные факторы, значения которых известны исследователю. Им соответствуют детерминированные задачи, характеризующиеся тем, что каждой стратегии, выбираемой ОС, отвечает единственный результат.
Случайные фиксированные факторы, значения которых могут быть описаны с помощью известных законов распределения вероятности. Им соответствуют вероятностные, или стохастические, задачи (задачи с риском). Их характерной особенностью является то, что наряду со случайными факторами они могут содержать и фиксированные. Каждой стратегии соответствует некоторое множество результатов, вероятности наступления которых либо известны, либо могут быть оценены.
Неопределенные факторы, значения которых неизвестны и не могут быть оценены. Для них в лучшем случае известна область возможных значений, либо область возможных значений закона распределения. Им соответствуют задачи в условиях неопределенности и игровые задачи.
В свою очередь неопределенные факторы могут быть распределены на три подгруппы в соответствии с причиной их появления:
НФ, появляющиеся за счет наличия действующих от оп. стороны лиц или автоматов, цели которых не соответствуют или противоположны целям опер. стороны. (Игровые модели- военное дело, бизнес, спорт и др.)
Природные факторы, значения которых заранее не известны, как правило, из-за недостаточной изученности протекающих процессов. Эти факторы относятся безразлично к цели опер. стороны, но оказывают на ее достижение существенное влияние.
Неоп. ф., отражающие нечеткость знания цели операции, критерия эффективности. Обычно это задачи многокритериальной (векторной) оптимизации, когда цель операции описывается совокупностью критериев эффективности F1, F2, Fn. Чтобы выбрать единственное решение в этом случае приходится либо ранжировать критерии, либо отдавать предпочтение одному из них, добиваясь приемлемого компромисса.
Основные этапы решения задач ТПР
Несмотря на большое разнообразие задач ТПР, им всем присущи следующие основные этапы:
Постановка задачи.
Построение мат. модели.
Нахождение метода решения.
Проверка и корректировка модели.
Реализация найденного решения на практике.
Постановка задачи – чрезвычайно ответственный этап ТПР. Первоначально задача формулируется заказчиком- оперирующей стороной. Такая постановка задачи обычно не бывает окончательной. Во время анализа исследуемой операции задача уточняется. Здесь роль исследователя состоит в проведении тщательного обследования объекта, формулировании цели операции, изучении множества факторов, влияющих на результаты. Исследователь операции совместно с заказчиком выделяет совокупность существенных факторов, и уточняет окончательную содержательную постановку задачи.
Построение математической модели. Представляет процесс формализации содержательной постановки задачи. В общем случае модели принятия решений сводятся к моделям задач математического программирования вида:
Нахождение метода решения. Для нахождения оптимального решения 13 EMBED Equation.3 1415опт задачи (1) в зависимости от структуры целевой функции F и ограничений применяют те или иные методы теории мат. программирования:
Линейное программирование. 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415- линейные функции относительно своих переменных 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415.
Нелинейное программирование, если хотя бы одна из 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415- - нелинейная.
Динамическое программирование, если 13 EMBED Equation.3 1415 явл. аддитивной (сепарабельной) или мультипликативной функцией своих аргументов.
13 EMBED Equation.3 1415
Дискретное (целочисленное) программирование, если на переменные 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415 наложено условие дискретности или целочисленности.
Геометрическое программирование, если целевая функция выражается соотношениями 13 EMBED Equation.3 1415, или 13 EMBED Equation.3 1415, а ограничения 13 EMBED Equation.3 1415. Здесь коэффициенты Сi и показатели степени аij являются произвольными константами, а независимые переменные хj>0, j=1,m. Функции приведенного вида называются сигналами, а в случае хj>0– позиномами.
Проверка и корректировка модели. В сложных системах ММ лишь частично отражает реальный процесс. Поэтому необходима проверка степени соответствия, или адекватности, между моделью и реальным объектом (процессом). Проверку производят сравнением предсказанного поведения на модели с фактическим (измеренным). Если их разница в пределах допустимого, то модель считается адекватной, в противном случае необходимо скорректировать модель. Корректировка может потребовать дополнительных исследований объекта, уточнения структуры модели. Четыре названных выше этапа повторяют многократно до тех пор, пока будет достигнуто удовлетворительное соответствие между выходом объекта и модели.
Реализация найденного решения на практике. Является важнейшим этапом, завершающим операционное исследование. Полученное решение в виде отчетов, инструкций и рекомендаций представляется заказчику. Опер. сторона принимает окончательное решение с учетом неформализуемой информации.
Вопросы для самопроверки:
Дайте определения понятиям:
ТПР
Операцией (О)
Оперирующей стороной (ОС)
Активными средствами проведения операции (АС)
Стратегиями
Действующими факторами
Критерием эффективности (КЭ)
Состоянием операции (СО)
Математической моделью (ММ)
Решением (Р),
Исследователем операции
Опишите типы задач ТПР
Опишите основные этапы решения задач ТПР с пояснением всех этапов.
Тема лекции: «Решение задачи в условиях полной неопределенности.»
ПРИНЯТИЕ РЕШЕНИЙ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ И РИСКА (ИГРЫ С ПРИРОДОЙ)
ПОНЯТИЕ ИГРЫ С ПРИРОДОЙ
Ситуации, описываемые рассмотренными в гл. 2 моделями в виде стратегических игр, в экономической практике могут не в полной мере оказаться адекватными действительности, посколь ку реализация модели предполагает многократность повторения действий (решений), предпринимаемых в похожих условиях. В реальности количество принимаемых экономических решений в неизменных условиях жестко ограничено. Нередко экономичес кая ситуация является уникальной, и решение в условиях нео пределенности должно приниматься однократно. Это порождает необходимость развития методов моделирования принятия реше ний в условиях неопределенности и риска.
Традиционно следующим этапом такого развития являются игры с природой. Формально изучение игр с природой, так же как и стратегических, должно начинаться с построения платежной мат рицы, что является, по существу, наиболее трудоемким этапом под готовки принятия решения. Ошибки в платежной матрице не могут быть компенсированы никакими вычислительными методами и приведут к неверному итоговому результату.
Отличительная особенность игры с природой состоит в том, что в ней сознательно действует только один из участников, в большинстве случаев называемый игроком 1. Игрок 2 (природа) сознательно против игрока 1 не действует, а выступает как не имеющий конкретной цели и случайным образом выбирающий очередные «ходы» партнер по игре. Поэтому термин «природа» характеризует некую объективную действительность, которую не следует понимать буквально, хотя вполне могут встретиться ситуации, в которых «игроком» 2 действительно может быть природа (например, обстоятельства, связанные с погодными ус ловиями или с природными стихийными силами).
На примере игры с природой рассмотрим проблему заготов ки угля на зиму.
Задача 1. Необходимо закупить уголь для обогрева дома. Количество хранимого угля ограничено и в течение холодного периода должно быть полностью израсходовано. Предполагается, что неизрасходованный зимой уголь в лето пропадает. Покупать уголь можно в любое время, однако летом он дешевле, чем зимой.
Неопределенность состоит в том, что не известно, какой будет зима: суровой, тогда придется докупать уголь, или мягкой, тогда часть угля может остаться неиспользованной. Очевидно, что у природы нет злого умысла и она ничего против человека «не имеет». С другой стороны, долгосрочные прогнозы, составляемые метеорологическими службами, неточны и поэтому мо гут использоваться в практической деятельности только как ори ентировочные при принятии решений.
Методы принятия решений в играх с природой зависят от характера неопределенности, точнее от того, известны или нет вероятности состояний (стратегий) природы, т.е. имеет ли место ситуация риска или неопределенности. Ниже будут описаны методы, применяемые в обоих случаях.
Рассмотрим организацию и аналитическое представление игры с природой. Пусть игрок 1 имеет т возможных стратегий: А1, A2 , ... , Аm, а у природы имеется п возможных состояний (стра тегий): П1, П2, ..., Пn, тогда условия игры с природой задаются матрицей А выигрышей игрока 1:
Платит, естественно, не природа, а некая третья сторона (или совокупность сторон, влияющих на принятие решений игроком 1 и объединенных в понятие «природа»).
Возможен и другой способ задания матрицы игры с приро дой: не в виде матрицы выигрышей, а в виде так называемой матрицы рисков R = ||rij||m,n или матрицы упущенных возможно стей. Величина риска - это размер платы за отсутствие инфор мации о состоянии среды. Матрица R может быть построена не посредственно из условий задачи или на основе матрицы выиг рышей А.
Риском rij игрока при использовании им стратегии Аi и при состоянии среды Пj будем называть разность между выигрышем, который игрок получил бы, если бы он знал, что состоянием среды будет Пj, и выигрышем, который игрок получит, не имея этой информации.
Зная состояние природы (стратегию) Пj, игрок выбирает ту стратегию, при которой его выигрыш максимальный, т.е. rij = (j – aij при заданном j. Например, для мат рицы выигрышей
Согласно введенным определениям rij и (j получаем матрицу рисков
Независимо от вида матрицы игры требуется выбрать такую стратегию игрока (чистую или смешанную, если последняя име ет смысл), которая была бы наиболее выгодной по сравнению с другими. Необходимо отметить, что в игре с природой понятие смешанной стратегии игрока не всегда правомерно, поскольку его действия могут быть альтернативными, т.е. выбор одной из стратегий отвергает все другие стратегии (например, выбор аль тернативных проектов). Прежде всего следует проверить, нет ли среди стратегий игрока мажорируемых, и, если таковые имеют ся, исключить их.
ПРИНЯТИЕ РЕШЕНИЙ В УСЛОВИЯХ ПОЛНОЙ НЕОПРЕДЕЛЕННОСТИ
Неопределенность, связанную с отсутствием информации о вероятностях состоянии среды (природы), называют «безнадежной» или «дурной».
В таких случаях для определения наилучших решении ис пользуются следующие критерии: максимакса, Вальда, Сэвиджа, Гурвица. Альтернативные подходы, в частности принципы Байеса - Лапласа, рассматриваются в разд. 6.2.1.
Применение каждого из перечисленных критериев проиллю стрируем на примере матрицы выигрышей (3.1) или связанной с ней матрицы рисков (3.2).
Критерий максимакса. С его помощью определяется страте гия, максимизирующая максимальные выигрыши для каждого состояния природы. Это критерий крайнего оптимизма. Наилучшим признается решение, при котором достигается максималь ный выигрыш, равный 13 EMBED Equation.3 1415.
Нетрудно увидеть, что для матрицы А наилучшим решением будет А1, при котором достигается максимальный выигрыш - 9.
Следует отметить, что ситуации, требующие применения такого критерия, в экономике в общем нередки, и пользуются им не только безоглядные оптимисты, но и игроки, поставленные в безвыходное положение, когда они вынуждены руководствовать ся принципом «или пан, или пропал».
Максиминный критерий Вальда. С позиций данного критерия природа рассматривается как агрессивно настроенный и сознательно действующий противник типа тех, которые проти водействуют в стратегических играх.
Выбирается ре шение, для которого достигается значение 13 EMBED Equation.3 1415.
Для платежной матрицы А (3.1) нетрудно рассчитать:
для первой стратегии (i = 1) 13 EMBED Equation.3 1415;
для второй стратегии (i=2) 13 EMBED Equation.3 1415;
для третьей стратегии (i=3) 13 EMBED Equation.3 1415.
Тогда 13 EMBED Equation.3 1415, что соответствует второй стратегии A2 игрока 1.
В соответствии с критерием Вальда из всех самых неудачных результатов выбирается лучший (W = 3). Это перестрахо вочная позиция крайнего пессимизма, рассчитанная на худший случай. Такая стратегия приемлема, например, когда игрок не столь заинтересован в крупной удаче, но хочет себя застраховать от неожиданных проигрышей. Выбор такой стратегии определя ется отношением игрока к риску.
Критерий минимаксного риска Сэвиджа. Выбор стратегии аналогичен выбору стратегии по принципу Вальда с тем отличием, что игрок руководствуется не матрицей выигрышей А (3.1), а матрицей рисков R (3.2):
13 EMBED Equation.3 1415
Для матрицы R (3.2) нетрудно рассчитать:
для первой стратегии (i=1) 13 EMBED Equation.3 1415;
для второй стратегии (i=2) 13 EMBED Equation.3 1415;
для третьей стратегии (i=3) 13 EMBED Equation.3 1415.
Минимально возможный из самых крупных рисков, равный 4, достигается при использовании первой стратегии А1.
Критерий пессимизма-оптимизма Гурвица. Этот критерий при выборе решения рекомендует руководствоваться некоторым средним результатом, характеризующим состояние между крайним пессимизмом и безудержным оптимизмом. Согласно этому критерию стратегия в матрице А выбирается в соответствии со значением
При p = 0 критерий Гурвица совпадает с максимаксным кри ерием, а при р = 1 - с критерием Вальда. Покажем процедуру применения данного критерия для матрицы А (3.1) при р = 0,5:
для первой стратегии
для второй стратегии
для третьей стратегии
Тогда 13 EMBED Equation.3 1415, т.е. оптимальной является вторая стратегия А2.
Применительно к матрице рисков R критерий пессимизма-оптимизма Гурвица имеет вид:
При р = 0 выбор стратегии игрока 1 осуществляется по ус ловию наименьшего из всех возможных рисков (13 EMBED Equation.3 1415); при р = 1 - по критерию минимаксного риска Сэвиджа.
В случае, когда по принятому критерию рекомендуется к использованию несколько стратегий, выбор между ними может делаться по дополнительному критерию, например в расчет могут приниматься средние квадратичные отклонения от средних выигрышей при каждой стратегии. Еще раз подчеркнем, что здесь стандартного подхода нет. Выбор может зависеть от склонности к риску ЛПР.
Пример:
В заключение приведем результаты применения рассмотренных выше критериев на примере следующей матрицы выигрышей:
Для игрока 1 лучшими являются стратегии:
по критерию Вальда – А3,
по критерию Сэвиджа – А2 и А3,
по критерию Гурвица (при р = 0,6) – А3;
по критерию максимакса – А4.
Поскольку стратегия А3, фигурирует в качестве оптимальной по трем критериям выбора из четырех испытанных, степень ее надежности можно признать достаточно высокой для того, что бы рекомендовать эту стратегию к практическому применению.
Таким образом, в случае отсутствия информации о вероят ностях состоянии среды теория не дает однозначных и матема тически строгих рекомендации по выбору критериев принятия решений. Это объясняется в большей мере не слабостью тео рии, а неопределенностью самой ситуации. Единственный ра зумный выход в подобных случаях - попытаться получить до полнительную информацию, например, путем проведения ис следований или экспериментов. В отсутствие дополнительной информации принимаемые решения теоретически недостаточ но обоснованы и в значительной мере субъективны. Хотя при менение математических методов в играх с природой не дает абсолютно достоверного результата и последний в определен ной степени является субъективным (вследствие произвольно сти выбора критерия принятия решения), оно тем не менее создает некоторое упорядочение имеющихся в распоряжении ЛПР данных: задаются множество состояний природы, альтер нативные решения, выигрыши и потери при различных сочета ниях состояния «среда - решение». Такое упорядочение пред ставлений о проблеме само по себе способствует повышению качества принимаемых решений.
Пример:
Имеются четыре варианта (проекта) оснащения предприятия современным техническим оборудованием 13 EMBED Equation.3 1415. Четырьмя рабочими группами 13 EMBED Equation.3 1415 проведена экспертиза этих проектов и определена производственная эффективность 13 EMBED Equation.3 1415 каждого варианта. Требуется выбрать лучший проект, используя критерии Вальда, Сэвиджа, Гурвица.
Варианты оснащения
Состояние «природы»
S1
S2
S3
S4
R1
16
29
16
26
R2
15
12
22
12
R3
27
14
28
12
R4
27
30
15
26
Решение:
Матрица рисков дает возможность непосредственно оценить качество различных решений и установить, насколько полно реализуются в них существующие возможности достижения успеха при наличии риска.
Для выбора наилучшего проекта существуют различные критерии, среди которых можно назвать критерии: Вальда, Сэвиджа, Гурвица. Нет никаких оснований считать априори один из критериев лучше, чем другие, однако вернее будет выбрать тот проект, который будет предпочтительнее по нескольким критериям.
В теории статистических игр вводится специальный показатель, который называется риском. Риск показывает, насколько выгоден проект в данной конкретной обстановке с учетом его неопределенности. Риск рассчитывается как разность между ожидаемым результатом действий при наличии точных данных об обстановке и результатом, который может быть достигнут, если эти данные точно не известны.
Величины риска определяются следующими выражениями:
rij = 13 EMBED Equation.3 1415аij - аij = (j - aij,
где аij – размер «выигрыша» при выборе i–й стратегии при j–м состоянии «природы»; (j - максимальный «выигрыш» для j–й обстановки; rij - величина риска при выборе i–й стратегии при j–й обстановке. Составим матрицу рисков:
S1
S2
S3
S4
R1
11
1
12
0
R2
12
18
6
14
R3
0
16
0
14
R4
0
0
13
0
Матрица рисков дает возможность непосредственно оценить качество различных решений и установить, насколько полно реализуются в них существующие возможности достижения успеха при наличии риска.
Критерий Вальда – это максиминный критерий крайнего пессимизма, или наибольшей осторожности, перестраховки. Такой подход характерен для того, кто очень боится проиграть и считает природу разумным, вредным и агрессивным конкурентом, назло мешающим нам достигнуть успеха. В этом случае оптимальной стратегией для игрока Ri будет чистая стратегия R, при которой наименьший «выигрыш» будет максимальным, т.е. при которой гарантируется выигрыш, в любом случае не меньший, чем нижняя цена игры с природой:
V = 13 EMBED Equation.3 141513 EMBED Equation.3 1415аij.
Используя матрицу игры, определяем минимальный выигрыш для всех стратегий
(1 = 16; (2 = 12; (3 =12; (4 = 15.
Наилучший проект R1, дает максимальный (из минимальных) «выигрыш» в размере 16.
Критерий Сэвиджа сводится к тому, чтобы любыми путями избежать большого риска при принятии решения. Оптимальным будет проект Ri, при которой минимизируется величина максимального риска в наихудших условиях:
S = 13 EMBED Equation.3 141513 EMBED Equation.3 1415rij.
Используя матрицу рисков, находим максимальные риски для всех стратегий
r1 = 12, r2 = 18, r3 = 16, r4 = 13.
Наилучший проект R1 допускает минимальный риск (из максимальных) в размере 12.
Критерий Гурвица является линейной комбинацией пессимистической и оптимистической позиций. Стратегия выбирается из условия
G = 13 EMBED Equation.3 1415{k ( 13 EMBED Equation.3 1415аij + (1 - k) ( 13 EMBED Equation.3 1415аij},
где k – коэффициент «пессимизма».
Коэффициент k меняется от 0 до 1, не принимая этих граничных значений (0 < k < 1). Коэффициент k выбирается на основании опыта или из субъективных соображений. Чем опаснее ситуация, тем менее мы склонны к риску, тем больше мы хотим подстраховаться, а значит, тем ближе к единице выбирается k. При k = 1 критерий Гурвица превращается в критерий Вальда, а при k = 0 – в критерий «крайнего оптимизма».
По условию k =
·= 0,45, тогда
0,45 ( 16 + 0,55 ( 12 = 23,05
0,45 ( 12 + 0,55 (18 =22,35
0,45( 12 + 0,55 ( 16 =21,25
0,45 ( 15+ 0,55 ( 13 =22,6
Наилучший проект R4 дает «выигрыш» в размере 22,6.
Вывод: По большинству критериев наилучшим проектом является R4.
Вопросы для самопроверки:
Дайте определение «игры с природой»
Какими метолами решаются задачи в условиях неопределенности?
Опишите критерии Вальда, Сэвиджа, Гурвица.
Практические занятия – не предусмотрено.
КОНТРОЛЬ И ОЦЕНКА РЕЗУЛЬТАТОВ ОСВОЕНИЯ ДИСЦИПЛИНЫ
Вопросы к экзамену
ПРИМЕРНЫЙ ПЕРЕЧЕНЬ ВОПРОСОВ ДЛЯ ПОДГОТОВКИ
К СДАЧЕ ЭКЗАМЕНА ПО ДИСЦИПЛИНЕ «МАТЕМАТИЧЕСКИЕ МЕТОДЫ»
Раздел 1. Основы моделирования
Основные понятия и принципы моделирования.
Классификация моделей.
Алгоритм моделирования. Характеристики каждого этапа.
Классические задачи моделирования
Математические модели. Классификация.
Построение экономико-математической модели задачи. Оптимальное решение.
Математическое моделирование задач коммерческой деятельности.
Однокритериальные и многокритериальные задачи. Методы решения.
Алгоритм решения однокритериальных задач.
Раздел 2. Детерминированные задачи
Тема 2.1 Линейное программирование
Линейное программирование. Основные понятия линейного программирования.
Математическая модель задач линейного программирования.
Геометрический метод решения задач линейного программирования. Описание метода.
Алгоритм решения задач линейного программирования геометрическим методом.
Симплекс- метод решения задач линейного программирования. Описание метода.
Алгоритм решения задач линейного программирования симплекс- методом.
Транспортная задача. Построение экономико-математической модели транспортной задачи.
Транспортная задача. Методы построение опорного плана
Транспортная задача. Метод потенциалов.
Транспортная задача. Построение цикла перерасчета таблицы.
Тема 2.2. Нелинейное программирование
Нелинейное программирование. Основные понятия.
Нелинейное программирование. Экстремум функции одной переменной.
Нелинейное программирование. Экстремум функции двух переменных.
Нелинейное программирование. Условный экстремум. Функция Лагранжа.
Нелинейное программирование. Графический метод нахождения экстремумов функции.
Тема 2.3. Динамическое программирование
Динамическое программирование. Понятие задачи динамического программирования.
Модели динамического программирования.
Динамическое программирование. Выбор оптимального маршрута перевозки грузов.
Динамическое программирование. Оптимальное распределение ресурсов.
Тема 2.4. Алгоритмы на графах
Методы представления и хранения графов в памяти ЭВМ.
Метрические характеристики графов.
Задача о нахождении кратчайших путей в графе. Постановка задачи и алгоритм решения.
Раздел 3. Основные методы решения детерминированных задач и задач в условиях неопределенности, возникающих в практической деятельности
Тема 3.1. Системы массового обслуживания
Основные понятия теории Марковских процессов
Уравнение Колмогорова А.Н.
Системы массового обслуживания. Основные понятия.
Одноканальные СМО с отказами.
Одноканальные СМО с ожиданием.
Многоканальные СМО с отказами.
Многоканальные СМО с ожиданием.
Тема 3.2. Имитационное моделирование
Идея метода имитационного моделирования е
Получение случайных величин
Оценка надежности простейших систем методом Монте-Карло
Расчет СМО с отказами методом Монте-Карло
Тема 3.3. Прогнозирование
Прогнозирование. Классификация прогнозирования.
Формализованные методы прогнозирования.
Метод наименьших квадратов. Линейное сглаживание.
Метод наименьших квадратов. Квадратическая функция.
Тема 3.4. Теория игр
Предмет и задачи теории игр. Основные понятия.
Матричные игры: чистые стратегии.
Матричные игры: смешанные стратегии.
Тема 3.5. Теория принятия решений
Область применения теории принятия решений. Принятие решений в условиях определенности, риска и неопределенности.
Критерий принятия решений. Дерево решений.
ИНФОРМАЦИОННОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ
Основные источники
Партыка Т.Л., Попов И.И. Математические методы. – М.: ФОРУМ : ИНФРА-М, 2012.
Агальцов В.П., Волдайская И.В.. Математические методы в программировании: Учебник.- М.: ФОРУМ: ИНФРА-М, 2008.
Дополнительные источники
Фомин Г.П. Математические методы и модели в коммерческой деятельности: Учебник. – М.: Финансы и статистика, 2008.
Попов А.М. Экономико-математические методы и модели :учебник.-М.: Юрайт, 2012
Интернет-ресурсы
Единое информационно-образовательное пространство колледжа NetSchool. Форма доступа: http://sgtek.ru
Информационно-справочная система «В помощь студентам». Форма доступа: http://window.edu.ru
Информационно-справочная система. Форма доступа: [ Cкачайте файл, чтобы посмотреть ссылку ].
Информационно-справочная система. Форма доступа: [ Cкачайте файл, чтобы посмотреть ссылку ]
13PAGE 15
13 PAGE \* MERGEFORMAT 1412715
13 EMBED Equation.3 1415
4
4
1
9
7
5
8
6
9
3
11
6
5
7
10
9
8
7
5
6
4
3
2
2
3
4
6
5
7
8
9
10
1
x4
x1
x2
x3
x5
$
&
·
·
·
·
·
·
·
·
·
·ФРисунок 1Root EntryEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeРисунок 1Рисунок 2Рисунок 3Рисунок 4Equation NativeEquation NativeEquation NativeEquation NativeEquation NativeРисунок 14Equation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation Native;Equation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation Native