МЕТОДИЧЕСКИЕ УКАЗАНИЯ по выполнению самостоятельной внеаудиторной работы по дисциплине «Математические методы» для студентов 3 курса (специальность Программирование в компьютерных системах)
ДЕПАРТАМЕНТ ОБРАЗОВАНИЯ, НАУКИ И МОЛОДЕЖНОЙ ПОЛИТИКИ ВОРОНЕЖСКОЙ ОБЛАСТИ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ САМОСТОЯТЕЛЬНАЯ РАБОТА №ЕДНЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ВОРОНЕЖСКОЙ ОБЛАСТИ
«СЕМИЛУКСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИКО-ЭКОНОМИЧЕСКИЙ КОЛЛЕДЖ»
методические указания
по выполнению самостоятельной внеаудиторной работы
по дисциплине «Математические методы»
для студентов 3 курса
(специальность 230115 Программирование в компьютерных системах)
Семилуки , 2014
Одобрено методическим советом ГОБУ СПО ВО «СГТЭК»
Автор-составитель: Евдокимова М.Д., преподаватель ГОБУ СПО ВО «СГТЭК»
Учебное пособие содержит указания по выполнению внеаудиторных самостоятельных работ по «Математические методы», являющейся естественно-научной дисциплиной. Методические указания составлены в соответствии с рабочей программой по дисциплине «Математические методы» и предназначены для студентов 3-го курса, обучающихся по специальности 230115 Программирование в компьютерных системах.
© Евдокимова М.Д., 2014
©ГОБУ СПО ВО «СГТЭК» Оглавление
стр.
Введение
5
Самостоятельная работа №1: Подготовка сообщений «Основные понятия моделирования»
8
Самостоятельная работа №2: Собрать характеристики моделей
8
Самостоятельная работа №3: Подготовка сообщений «Метод анализа иерархий»
8
Самостоятельная работа №4: Построение простейших математических и статистических моделей
8
Самостоятельная работа №5: Решение простейших однокритериальных задач
11
Самостоятельная работа №6: Подготовка сообщений: «Линейное программирование – возникновение и развитие»
13
Самостоятельная работа №7: Решение задач линейного программирования геометрическим методом
13
Самостоятельная работа №8: Формирование и усвоение содержания теоретического материала, используя информационные образовательные ресурсы (онлайн-решение)
20
Самостоятельная работа №9: Решение задач линейного программирования симплекс–методом
20
Самостоятельная работа №10: Формирование и усвоение содержания теоретического материала, используя информационные образовательные ресурсы (онлайн-решение)
27
Самостоятельная работа №11: Решение транспортной задачи методом потенциалов
27
Самостоятельная работа №12: Формирование и усвоение содержания теоретического материала, используя информационные образовательные ресурсы (онлайн-решение)
38
Самостоятельная работа №13: Формирование и усвоение содержания теоретического материала
38
Самостоятельная работа №14: Подготовка сообщения на тему «Лагранж»
38
Самостоятельная работа №15: Решение задач нелинейного программирования графическим методом и методом множителей Лагранжа
38
Самостоятельная работа №16: Подготовка сообщения «Динамическое программирование»
44
Самостоятельная работа №17: Формирование и усвоение содержания теоретического материала
44
Самостоятельная работа №18: Решение задач о распределении средств между предприятиями
47
Самостоятельная работа №19: Выбор оптимального маршрута перевозки грузов
50
Самостоятельная работа №20: Подготовка сообщения на тему «Графы. Практическое приложения графов»
54
Самостоятельная работа №21: Нахождение кратчайших путей в графе. Решение задачи о максимальном потоке
54
Самостоятельная работа №22: Решение задач на графах
63
Самостоятельная работа №23: Подготовка сообщения «Колмогоров А.Н»
66
Самостоятельная работа №24: Подготовка сообщения «СМО»
66
Самостоятельная работа №25: Составление систем уравнений Колмогорова
66
Самостоятельная работа №26: Нахождение финальных вероятностей
70
Самостоятельная работа №27: Подготовка сообщения на тему «Имитационное моделирование»
74
Самостоятельная работа №28: Решение задачи управления запасами и задачи теории массового обслуживания, используя имитационное моделирование
74
Самостоятельная работа №29: Формирование и усвоение содержания теоретического материала, используя информационные образовательные ресурсы
79
Самостоятельная работа №30: Работа над учебным материалом по первоисточникам
79
Самостоятельная работа №31: Построение прогнозов количественными и качественными методами
79
Самостоятельная работа №32: Работа над учебным материалом по первоисточникам
87
Самостоятельная работа №33: Антагонистические матричные игры: чистые и смешанные стратегии
87
Самостоятельная работа №34: Область применимости теории принятия решений
101
Самостоятельная работа №35: Работа над учебным материалом по первоисточникам
101
Методические указания к самостоятельной работе студента
102
Литература
109
Введение
Методические указания по выполнению внеаудиторной самостоятельной работы по естественно - научной дисциплине «Математические методы» предназначены для студентов, обучающихся по специальности 230115 Программирование в компьютерных системах.
Объем самостоятельной работы студентов определяется государственным образовательным стандартом среднего профессионального образования (ФГОС СПО) по специальности 230115 Программирование в компьютерных системах базовой подготовки.
Выполнение внеаудиторной самостоятельной работы является обязательной для каждого студента, её объём в часах определяется действующим рабочим учебным планом Семилукского государственного технико-экономического колледжа по данной специальности.
Самостоятельная внеаудиторная работа проводится с целью:
- систематизации и закрепления полученных теоретических знаний студентов;
- углубления и расширения теоретических знаний;
- развития познавательных способностей и активности студентов, самостоятельности, ответственности и организованности;
- формирования самостоятельности мышления, способностей к саморазвитию, самосовершенствованию и самореализации.
Внеаудиторная самостоятельная работа выполняется студентом по заданию преподавателя, но без его непосредственного участия. По математике используются следующие виды заданий для внеаудиторной самостоятельной работы:
для овладения знаниями: чтение текста (учебника, дополнительной литературы), работа со словарями и справочниками, учебно-исследовательская работа, использование аудио- и видеозаписей, компьютерной техники и Интернета;
для закрепления и систематизации знаний: повторная работа над учебным материалом (учебника, дополнительной литературы, аудио- и видеозаписей), составление плана и алгоритма решения, составление таблиц для систематизации учебного материала, ответы на контрольные вопросы, подготовка сообщений к выступлению на уроке, конференции, подготовка сообщений, докладов, рефератов, тематических кроссвордов;
для формирования умений: выполнение схем, анализ карт, подготовка к деловым играм.
Содержание заданий самостоятельной работы ориентировано на подготовку студентов к освоению профессиональных модулей ОПОП по специальности 230115 Программирование в компьютерных системах, и овладению профессиональными компетенциями (ПК):
ПК 1.1. Выполнять разработку спецификаций отдельных компонент.
ПК 1.7.в Осуществлять разработку кода программного продукта для решения различных практических задач с применением математических методов.
ПК 2.5.в Реализовывать основные методологические подходы к решению математических задач, возникающих в ходе практической деятельности людей при работе в базе данных;
В процессе выполнения работы у студентов должны формироваться общие компетенции (ОК):
ОК 1. Понимать сущность и социальную значимость своей будущей профессии, проявлять к ней устойчивый интерес.
ОК 2. Организовывать собственную деятельность, выбирать типовые методы и способы выполнения профессиональных задач, оценивать их эффективность и качество.
ОК 3. Принимать решения в стандартных и нестандартных ситуациях и нести за них ответственность.
ОК 4. Осуществлять поиск и использование информации, необходимой для эффективного выполнения профессиональных задач, профессионального и личностного развития.
ОК 5. Использовать информационно-коммуникационные технологии в профессиональной деятельности.
ОК 6. Работать в коллективе и команде, эффективно общаться с коллегами, руководством, потребителями.
ОК 7. Брать на себя ответственность за работу членов команды (подчиненных), результат выполнения заданий.
ОК 8. Самостоятельно определять задачи профессионального и личностного развития, заниматься самообразованием, осознанно планировать повышение квалификации.
ОК 9. Ориентироваться в условиях частой смены технологий в профессиональной деятельности.
ОК 10. Исполнять воинскую обязанность, в том числе с применением полученных профессиональных знаний (для юношей).
В результате освоения учебной дисциплины обучающийся должен уметь:
составлять простейшие математические модели задач, возникающих в практической деятельности людей;
выбирать наиболее рациональный метод и алгоритм решения задачи, а также оценивать сложность выбранного алгоритма;
разрабатывать алгоритмы для решения различных практических задач с применением математических методов.
В результате освоения учебной дисциплины обучающийся должен знать:
основные понятия и принципы моделирования;
основные методологические подходы к решению математических задач, возникающих в ходе практической деятельности людей;
основные методы решения детерминированных задач и задач в условиях неопределенности, возникающих в практической деятельности.
Перед выполнением внеаудиторной самостоятельной работы студент должен внимательно выслушать инструктаж преподавателя по выполнению задания, который включает определение цели задания, его содержание, сроки выполнения, ориентировочный объем работы, основные требования к результатам работы, критерии оценки. В процессе инструктажа преподаватель предупреждает студентов о возможных типичных ошибках, встречающихся при выполнении задания.
В пособии представлены как индивидуальные, так и групповые задания в зависимости от цели, объема, конкретной тематики самостоятельной работы, уровня сложности. В качестве форм и методов контроля внеаудиторной самостоятельной работы студентов используются аудиторные занятия, зачеты, тестирование, самоотчеты, контрольные работы.
Критериями оценки результатов внеаудиторной самостоятельной работы студента являются:
- уровень освоения студентом учебного материала;
- умение студента использовать теоретические знания при выполнении практических задач;
- сформированность общеучебных умений;
- обоснованность и четкость изложения ответа;
- оформление материала в соответствии с требованиями.
В методических указаниях приведены теоретический (справочный) материал в соответствии с темой работы, обращение к которому поможет выполнить задания самостоятельной работы; вопросы для самоконтроля, подготавливающие к выполнению заданий и сами задания.
Раздел 1. Основные понятия и принципы моделирования
Самостоятельная работа №1: Подготовка сообщения «Основные понятия моделирования»
Цель: получить представление о моделировании и моделях
Самостоятельная работа: работа с литературой
Форма контроля: сообщение на уроке
Самостоятельная работа №2: Собрать характеристики моделей
Цель: научиться обобщать данных, работать с большим количеством информации.
Самостоятельная работа: индивидуальная домашняя работа
Форма контроля: проверка работы (таблицы с характеристиками моделей)
Виды заданий:
Сбор информации
Систематизация информации
Пример:
Характеристики моделей ноутбуков
Модель
Процессор
ОЗУ
Жесткий диск
Экран
Цена
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 руб
Самостоятельная работа №3: Подготовка сообщения «Метод анализа иерархий»
Цель: получить представление о методе анализа иерархий
Самостоятельная работа: работа с литературой
Форма контроля: сообщение на уроке
Самостоятельная работа №4 Построение простейших математических и статистических моделей
Цель: получить и закрепить навыки построения простейших математических и статистических моделей
Самостоятельная работа: индивидуальная домашняя работа
Форма контроля: проверка работы
Теоретический материал и методические указания к выполнению заданий
Математическая модель любой задачи линейного программирования включает в себя:
максимум или минимум целевой функции (критерий оптимальности);
систему ограничений в форме линейных уравнений и неравенств;
требование неотрицательности переменных.
Таким образом, экономико-математическая формулировка и модель общей задачи линейного программирования имеют следующий вид:
найти максимальное (минимальное) значение линейной целевой функции
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
при ограничениях:
13 EMBED Equation.3 1415
Варианты заданий:
Малое предприятие арендовало минипекарню для произ водства чебуреков и беляшей. Мощность пекарни позволяет вы пускать в день не более 50 кг продукции. Ежедневный спрос на чебуреки не превышает 260 штук, а на беляши 240 штук. Суточные запасы теста и мяса и расходы на производство каж дой единицы продукции приведены в таблице. Определить оп тимальный план ежедневного производства чебуреков и беля шей, обеспечивающих максимальную выручку от продажи.
Расход на производство, кг/шт.
Суточные запасы сырья, кг
чебурека
беляша
Мясо
0,35
0,6
21
Тесто
0,65
0,3
22
Цена, руб-/кг
50,0
80,0
Фирма производит два безалкогольных широко популяр ных напитка «Колокольчик» и «Буратино». Для производства 1 л. «Колокольчика» требуется 0,02 ч работы оборудования, а для «Буратино» - 0,04 ч, а расход специального ингредиента на них составляет 0,01 кг и 0,04 кг на 1 л соответственно. Ежедневно в распоряжении фирмы 16 кг специального ингредиента и 24 ч работы оборудования. Доход от продажи 1 л «Колокольчика» составляет 0,25 руб., а «Буратино» - 0,35 руб.Определите ежедневный план производства напитков каждо го вида, обеспечивающий максимальный доход от их продажи.
Фирма производит для автомобилей запасные части типа А и В. Фонд рабочего времени составляет 5000 чел.-ч в неделю. Для производства одной детали типа А требуется 1 чел.-ч, а для производства одной детали типа В - 2 чел.-ч. Производственная мощность позволяет выпускать максимум 2500 деталей типа А и 2000 деталей типа В в неделю. Для производства детали типа А уходит 2 кг полимерного материала и 5 кг листового материала, а для производства одной детали типа В 4 кг полимерного ма териала и 3 кг листового металла. Еженедельные запасы каждо го материала - по 10 000 кг. Общее число производимых деталей в течение одной недели должно составлять не менее 1500 штук. Определите, сколько деталей каждого вида следует произ водить, чтобы обеспечить максимальный доход от продажи за неделю, если доход от продаж одной детали типа А и В состав ляет соответственно 1,1 руб. и 1,5 руб.
Фирма производит и продает столы и шкафы из древеси ны хвойных и лиственных пород. Расход каждого вида в кубо метрах на каждое изделие задан в таблице.
Расход древесины, м3
Цена изделия, тыс. руб.
хвойные
лиственные
Стол
0,2
0,3
0,8
Шкаф
0,1
0,05
1.6
Запасы древесины, м3
40
25
Определите оптимальное количество столов и шкафов, которое следует поставлять на продажу для получения максималь ного дохода фирмы.
Самостоятельная работа №5: Решение простейших однокритериальных задач
Цель: научиться решать простейшие однокритериальные задачи
Самостоятельная работа: Используя данные самостоятельной работы №2, решите задачи выбора оптимальной модели.
Форма контроля: проверка работы
Теоретический материал и методические указания к выполнению заданий
Решение простейших однокритериальных задач
В практической деятельности приходится рассматривать сложные объекты, которые невозможно целостно сопоставить. В таких случаях выделяют существенные показатели этих объектов, а затем проводят Самостоятельная работа №авнение их значений. При этом первичная информация задаётся в виде таблицы значений показателей, где представлены множество Самостоятельная работа №авниваемых объектов 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..
Самостоятельная работа №6: Подготовка сообщения «Линейное программирование – возникновение и развитие»
Цель: получить представление о линейном программировании
Самостоятельная работа: работа с литературой
Форма контроля: сообщение на уроке
Самостоятельная работа №7: Решение задач линейного программирования геометрическим методом
Цель: научиться решать задачи линейного программирования геометрическим методом
Самостоятельная работа: индивидуальная домашняя работа
Форма контроля: проверка работы
Теоретический материал и методические указания к выполнению заданий
Геометрический (графический)метод решения двумерной задачи линейного программирования (максимизация целевой функции)
Двумерная задача линейного программирования – задача линейного программирования, количество переменных которой равно 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. Решить графическим методом следующую ЗЛП:
Z = 3x1 + 5x2 min
x1 + x2
· 5
3x1 - x2
· 3
x1
·0, x2
·0
Задача 2. Решить графическим методом следующую ЗЛП:
Z = 3x1 + 5x2 max
x1 + x2
· 5
3x1 - x2
· 3
x1
·0, x2
·0
Задача 3. Решить графическим методом следующую ЗЛП:
Z = 2x1 + 2x2 min
x1 + 3x2
· 3
-2x1 + x2
· 2
x1 + x2
· 5
x1
·0, x2
·0
Задача 4. Решить графическим методом следующую ЗЛП:
Z = 2x1 + 2x2 max
x1 + 3x2
· 3
-2x1 + x2
· 2
x1 + x2
· 5
x1
·0, x2
·0
Самостоятельная работа №8: Формирование и усвоение содержания теоретического материала, используя информационные образовательные ресурсы (онлайн-решение)
Цель: научиться использовать информационные образовательные ресурсы для самоконтроля по изучаемой теме
Самостоятельная работа: работа с Internet- ресурсами
Форма контроля: проверка работы
Самостоятельная работа №9: Решение задач линейного программирования симплекс–методом
Цель: научиться решать задачи линейного программирования симплекс–методом
Самостоятельная работа: индивидуальная домашняя работа
Форма контроля: проверка работы
Теоретический материал и методические указания к выполнению заданий
Симплекс-метод линейного программирования
Для решения задач линейного программирования предложе но немало различных алгоритмов. Наиболее эффективным Самостоятельная работа №е ди них является алгоритм, известный под названием симплек сный метод, или метод последовательного улучшения плана.
Впервые симплексный метод был предложен американским ученым Дж. Данцингом в 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, не вошедших в состав базисных, получены ненулевые элементы, поэтому оптимальный план задачи линейного программирования является единственным.
Варианты заданий
Задача 2. Решить ЗЛП симплексным методом.
Z = 4x1 + 3x2 max
-x1 + 3x2
· 9
2x1 + 3x2
· 18
2x1 - x2
· 10
x1
·0, x2
·0
Задача 2. Решить ЗЛП симплексным методом.
Z = 2x1 + x2 + 2x3 max
3x1 + 2x2 + x3
· 6
x1 + x2 + 2 x3
· 4
x1
·0, x2
·0, x3
·0
Задача 2. Решить ЗЛП симплексным методом.
Z = 5x1 + 4x2 - x3 max
x1 - 2x2 + 2x3
· 20
x1 + 4x2 - x3
· 16
x1
·0, x2
·0, x3
·0
Задача 2. Решить ЗЛП симплексным методом.
Z = 4x1 - x2 + x3 max
x1 + 2x2 + x3
· 20
2x1 - x2 + 2 x3
· 10
x1
·0, x2
·0, x3
·0
Самостоятельная работа №10: формирование и усвоение содержания теоретического материала, используя информационные образовательные ресурсы (онлайн-решение)
Цель: научиться использовать информационные образовательные ресурсы для самоконтроля по изучаемой теме
Самостоятельная работа: работа с Internet- ресурсами
Форма контроля: проверка работы
Самостоятельная работа №11: Решение транспортной задачи методом потенциалов
Цель: научиться решать транспортную задачу методом потенциалов
Самостоятельная работа: индивидуальная домашняя работа
Форма контроля: проверка работы
Теоретический материал и методические указания к выполнению заданий
1. Построение математической модели транспортной задачи
Мы рассмотрели общие подходы к решению задач линейного программирования. Однако существуют частные типы задач линейного программирования, которые в силу своей структуры допускают решения более простыми методами. Мы остановимся только на одной из них – так называемой транспортной задаче.
Постановка транспортной задачи
Однородный груз, имеющийся в 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.
План будет называться оптимальным, если он, Самостоятельная работа №еди всех допустимых планов, приводит к минимальной суммарной стоимости перевозок.
2.Методы решения транспортных задач
Так как транспортная задача является задачей линейного программирования, то её можно решать симплекс-методом, но в силу своей особенности её можно решить гораздо проще.
Условия задачи удобно располагать в таблице, вписывая в ячейки количество перевозимого груза из А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. Найдём теперь оптимальный план для данной задачи.
Для этого воспользуемся методом потенциалов.
3.Метод потенциалов решения транспортных задач
[ 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.
Варианты заданий:
Вариант 1
Решить транспортную ЗЛП методом потенциалов, построив исходный опорный план способом минимального элемента.
ai bj
80
60
170
80
110
8
1
9
7
190
4
6
2
12
90
6
5
8
9
Вариант 2
Решить транспортную ЗЛП методом потенциалов, построив исходный опорный план способом минимального элемента.
ai bj
30
70
90
110
50
3
8
10
5
150
1
4
6
2
100
3
1
9
7
Вариант 3
Решить транспортную ЗЛП методом потенциалов, построив исходный опорный план способом минимального элемента.
ai bj
15
7
14
62
51
24
19
23
15
19
14
21
15
16
28
10
9
6
11
Вариант 4
Решить транспортную ЗЛП методом потенциалов, построив исходный опорный план способом минимального элемента.
ai bj
25
135
40
100
100
5
2
1
1
110
3
7
5
5
90
6
5
4
4
Вариант 5
Решить транспортную ЗЛП методом потенциалов, построив исходный опорный план способом минимального элемента.
ai bj
115
65
75
40
125
21
14
27
15
145
7
20
13
11
25
10
11
14
12
Вариант 6
Решить транспортную ЗЛП методом потенциалов, построив исходный опорный план способом минимального элемента.
ai bj
270
140
200
110
510
1
4
7
3
90
5
6
8
9
120
7
2
4
8
Вариант 7
Решить транспортную ЗЛП методом потенциалов, построив исходный опорный план способом минимального элемента.
ai bj
225
325
250
100
250
5
8
7
3
200
4
2
5
6
450
7
3
9
2
Вариант 8
Решить транспортную ЗЛП методом потенциалов, построив исходный опорный план способом минимального элемента.
ai bj
310
200
195
145
350
1
4
6
8
200
9
7
1
2
300
2
3
2
9
Вариант 9
Решить транспортную ЗЛП методом потенциалов, построив исходный опорный план способом минимального элемента.
ai bj
40
50
90
60
60
1
2
1
4
80
4
3
5
3
100
6
2
2
3
Вариант 10
Решить транспортную ЗЛП методом потенциалов, построив исходный опорный план способом минимального элемента.
ai bj
290
120
110
130
200
1
7
8
4
250
8
6
1
2
200
7
2
3
1
Самостоятельная работа №12: Формирование и усвоение содержания теоретического материала, используя информационные образовательные ресурсы (онлайн-решение)
Цель: научиться использовать информационные образовательные ресурсы для самоконтроля по изучаемой теме
Самостоятельная работа: работа с Internet- ресурсами
Форма контроля: проверка работы
Самостоятельная работа №13: Формирование и усвоение содержания теоретического материала по теме «Линейное программирование»
Цель: расширить теоретические знания о линейном программировании
Самостоятельная работа: работа с литературой
Форма контроля: ответ на уроке
Самостоятельная работа №14: Подготовка сообщения на тему «Лагранж»
Цель: получить представление о вкладе Лагранжа в развитие математических методов
Самостоятельная работа: работа с литературой
Форма контроля: сообщение на уроке
Самостоятельная работа №15: Решение задач нелинейного программирования графическим методом и методом множителей Лагранжа
Цель: научиться решать задачи нелинейного программирования графическим методом и методом множителей Лагранжа
Самостоятельная работа: индивидуальное домашнее задание
Форма контроля: проверка работы
Теоретический материал и методические указания к выполнению заданий
Нелинейное программирование
Задачами нелинейного программирования называются задачи математического программирования, в которых нелинейными являются и (или) целевая функция, и (или) ограничения в виде неравенств или равенств.
Задачи нелинейного программирования можно классифицировать в соответствии с видом функции 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.
Варианты заданий
Задание 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
Задание 2. Найдите точки экстремума заданной функции:
13 EMBED Equation.3 1415.
5. 13 EMBED Equation.3 1415.
6. 13 EMBED Equation.3 1415.
7. 13 EMBED Equation.3 1415.
8.13 EMBED Equation.3 1415
Задание 3. Используя метод Лагранжа, найти переменные х, у, дающие минимум целевой функции 13 EMBED Equation.3 1415, при ограничении 13 EMBED Equation.3 1415.
Вариант
1
2
3
4
5
a
1
2
3
4
5
b
1
2
4
6
8
Задание 4. Используя графический метод решения, найти переменные х, у, дающие минимум целевой функции 13 EMBED Equation.3 1415, при ограничениях 13 EMBED Equation.3 1415.
Вариант
1
2
3
4
5
a
3
3
3
3
3
b
1
2
4
6
8
Самостоятельная работа №16: Подготовка сообщения «Динамическое программирование»
Цель: получить представление о динамическом программировании
Самостоятельная работа: работа с литературой
Форма контроля: сообщение на уроке
Самостоятельная работа №17: формирование и усвоение содержания теоретического материала по теме Динамическое программирование»
Цель: расширить теоретические знания о динамическом программировании
Самостоятельная работа: работа с литературой
Форма контроля: ответ на уроке
Теоретический материал и методические указания к выполнению заданий
Понятие задачи динамического программирования
Рассматриваемые ранее задачи характеризуются тем, что в них не учитываются изменения оптимизируемых параметров во времени – процессы считаются статичными. Выбирается некоторый период времени, и для него определяются проектируемые или планируемые значения показателей. При этом предполагается, что управляемые или неуправляемые параметры системы в течение всего планового времени не будут изменяться или, по крайней мере, не претерпят серьёзных изменений, требующих пересмотра принятых решений.
Однако в реальной жизни есть задачи, в которых необходимо учитывать изменения параметров систем во времени. Эти параметры могут меняться непрерывно или дискретно – от этапа к этапу. Например, из года в год меняется возраст машин и оборудования, изменяется производственная мощность и производительность труда на предприятиях. Очевидно, что необходимо принимать оптимальные решения на год (или другой Самостоятельная работа №ок) и одновременно на весь рассматриваемый период в целом с учётом возможных изменений параметров. Для решения такого вида задач, которые получили название многошаговые, разработан соответствующий математический аппарат, который получил название динамическое программирование.
Рассмотрим задачу, состоящую из 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* за всю операцию, то он нам уже известен – именно на его оптимальности выбрано управление на первом шаге.
Классические задачи динамического программирования
Задача о наибольшей общей подпоследовательности: даны две последовательности, требуется найти самую длинную общую подпоследовательность.
Задача поиска наибольшей увеличивающейся подпоследовательности: дана последовательность, требуется найти самую длинную возрастающую подпоследовательность.
Задача о редакционном расстоянии (расстояние Левенштейна): даны две строки, требуется найти минимальное количество стираний, замен и добавлений символов, преобразующих одну строку в другую.
Задача о вычислении чисел Фибоначчи
Задача о порядке перемножения матриц: даны матрицы , , , требуется минимизировать количество скалярных операций для их перемножения.
Задача о выборе траектории
Задача последовательного принятия решения
Задача об использовании рабочей силы
Задача управления запасами
Задача о ранце: из неограниченного множества предметов со свойствами «стоимость» и «вес» требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при ограниченном суммарном весе.
Алгоритм Флойда Уоршелла: найти кратчайшие расстояния между всеми вершинами взвешенного ориентированного графа.
Алгоритм Беллмана Форда: найти кратчайший путь во взвешенном графе между двумя заданными вершинами.
Максимальное независимое множество вершин в дереве: дано дерево, найти максимальное множество вершин, никакие две из которых не связаны ребром.
Самостоятельная работа №18: Решение задач о распределении средств между предприятиями
Цель: научиться решать задачи динамического программирования: задач о распределении средств между предприятиями
Самостоятельная работа: индивидуальное домашнее задание
Форма контроля: проверка работы
Теоретический материал и методические указания к выполнению заданий
Пример: Оптимальное распределение ресурсов
Капитал 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 млн. руб.
Варианты заданий:
Распределите оптимальным образом денежные средства инвестора величиной 5 у.е. между четырьмя предприятиями. Доход каждого предприятия от вложения в него и у.е.определяется функцией дохода f(u). Эти функции приведены в таблице.
u
Прибыль от внедрения по предприятиям
f4(u)
f3(u)
f2(u)
f1(u)
1
f4(1)
6
3
4
2
10
f3(2)
4
6
3
11
11
f2(3)
8
4
12
13
11
f1(4)
5
18
15
18
16
Вариант
1
2
3
4
f4(1)
9
8
6
9
f3(2)
10
11
10
11
f2(3)
9
8
9
8
f1(4)
7
9
7
9
Самостоятельная работа №19: Выбор оптимального маршрута перевозки грузов
Цель: научиться решать задачи динамического программирования: выбор оптимального маршрута перевозки грузов
Самостоятельная работа: индивидуальное домашнее задание
Форма контроля: проверка работы
Теоретический материал и методические указания к выполнению заданий
Выбор оптимального маршрута перевозки грузов
Математический аппарат ДП, основанный на методологии пошаговой оптимизации, может быть использован при нахождении кратчайших расстояний, например, на географической карте, представленной в виде сети. Решение задачи по определению кратчайших расстояний между пунктами отправления и пунктами получения продукции по существующей транспортной сети является исходным этапом при решении таких экономических задач, как оптимальное прикрепление потребителей за поставщиками, повышение производительности транспорта за счет сокращения непроизводительного пробега и др.
Пусть транспортная сеть состоит из 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. Транспортная сеть с оптимальным маршрутом.
Варианты заданий:
Задача. На данной сети дорог имеется несколько маршрутов, по которым можно доставить груз из пункта 1 в пункт 10.
Известны стоимости 13 EMBED Equation.3 1415 перевозки единицы груза между пунктами сети (данные приведены в таблице). Требуется:
методом динамического программирования найти на сети наиболее экономный маршрут доставки груза из пункта 1 в пункт 10 и соответствующие ему затраты;
выписать оптимальные маршруты перевозки груза из всех остальных пунктов сети в пункт 10 и указать отвечающие им минимальные затраты на доставку.
№
Тариф
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
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·Самостоятельная работа №20: Подготовка сообщения на тему «Графы. Практическое приложения графов»
Цель: получить представление о графах, их практических приложениях Самостоятельная работа: работа с литературой
Форма контроля: сообщение на уроке
Самостоятельная работа №21: Нахождение кратчайших путей в графе. Решение задачи о максимальном потоке
Цель: научиться решать задачи динамического программирования: Нахождение кратчайших путей в графе. Решение задачи о максимальном потоке
Самостоятельная работа: индивидуальное домашнее задание
Форма контроля: проверка работы
Теоретический материал и методические указания к выполнению заданий
Задача о нахождении кратчайшего пути
Пусть дан граф, каждой дуге которого приписан вес. Задача о нахождении кратчайшего пути состоит в нахождении кратчайшего пути от заданной начальной вершины до заданной конечной вершины, при условии, что такой путь существует.
Можно дать много практических интерпретаций задачи о кратчайших путях. Например, вершины могут соответствовать городам и каждая дуга – некоторому пути, длина которого представлена весом дуги. Мы ищем кратчайшие пути между городами. Вес дуги может соответствовать стоимости (или времени) передачи информации между вершинами. В этом случае мы ищем самый дешевый (или самый скорый) путь.
Данная задача может быть разбита на две:
для начальной заданной вершины найти все кратчайшие пути от этой вершины к другим;
найти кратчайшие пути между всеми парами вершин.
Алгоритм Дейкстры решения задачи
Алгоритм Дейкстры ( алгоритм поиска кратчайшего пути во взвешенном графе между двумя заданными вершинами 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).
Пример решения задачи
Для взвешенного орграфа найти кратчайший путь из вершины 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.
Задача о максимальном потоке
Основные понятия
Рассмотрим граф G=(X,U), называемый в дальнейшем сетью. Пусть каждой дуге (xi, xj) сопоставлено положительное число cij , называемое пропускной способностью дуги. В сети выделяют два специальных узла, один из них называют источником (обозначим его через s), другой – стоком (обозначим его через t). Множество неотрицательных чисел fij , определенных на дугах (xi,xj), называют потоками в дугах, если выполняются следующие условия:
13 EMBED Equation.3 1415
Линейные ограничения отражают тот факт, что поток, втекающий в вершину, равен потоку, вытекающему из нее, за исключением вершин, являющихся источником и стоком. При этом поток в каждой дуге не должен превышать ее пропускной способности. Величина v, равная сумме потоков по всем дугам, исходящим из источника s, или сумме потоков по всем дугам, заходящим в вершину t, называется величиной потока в сети:
13 EMBED Equation.3 1415
Задача о максимальном потоке состоит в нахождении такого множества потоков по дугам, чтобы величина потокаv в сети была максимальной при условии отсутствия превышения пропускных способностей дуг.
Задача об определении максимального потока
Рассмотрим задачу об определении максимального потока, протекающего от некоторой вершины S графа (источника) к некоторой вершине t (стоку).
Рассмотрим граф, состоящий из восьми узлов. Взаимная связь узлов и пропускные способности отдельных звеньев в единицу времени представлены ниже.
[ Cкачайте файл, чтобы посмотреть картинку ]
Требуется определить максимальный поток из Р0 в Р7, используя для этого все возможные дуги.
Заносим данные в таблицу. В ячейки таблицы записываем пропускную способность звеньев из Рi пункта в Рj элементом (i, j), а (j, i) – пропускная способность звена в обратном направлении. Если элемент (i, j) > 0, а (j, i) = 0, то на месте элемента (j, i) следует записать 0.
P0
P1
P2
P3
P4
P5
P6
P7
P0
3
4
3
2
P1
2
3
2
2
P2
3
2
3
4
3
P3
3
1
1
4
P4
5
0
2
P5
3
3
0
4
P6
2
4
1
2
4
P7
3
5
4
Выберем произвольно один из возможных путей из Р0 в Р7, например, Р0, Р2, Р6, Р7. Элементы (0,2), (2,6), (6,7) отмечаем знаком "-", а (2,0), (6,2), (7,6) – знаком "+".
P0
P1
P2
P3
P4
P5
P6
P7
P0
3
4-
3
2
P1
2
3
2
2
P2
3+
2
3
4-
3
P3
3
1
4
P4
5
0
2
P5
3
3
0
4
P6
2
4+
1
2
4-
P7
3
5
4+
Определяем пропускную способность выбранного пути:
Х1 = min{(0,2); (2,6); (6,7)} = min{4,4,4} = 4.
Вычитаем Х1 из ячеек со знаком "-" и прибавляем в ячейки со знаком "+".
Выбираем новый путь из Р0 к Р7. Например, Р0, Р1, Р6, Р7. Отмечаем элементы (0,1), (1,5) и (5,7) знаком "-". (1,0), (5,1) и (7,5) – знаком "+".
P0
P1
P2
P3
P4
P5
P6
P7
P0
3-
0
3
2
P1
2+
3
2-
2
P2
7
2
3
0
3
P3
3
1
4
P4
5
0
2
P5
3+
3
0
4-
P6
2
8
1
2
0
P7
3
5+
8
Определяем пропускную способность пути:
Х2 = min{(0,1); (1,5); (5,7)} = min{3,2,4} = 2.
Вычитаем Х2 из элементов таблицы, отмеченных знаком "-", и прибавляем к элементам со знаком "+".
Выбираем новый путь – Р0, Р3, Р5, Р7. Отмечаем плюсы и минусы.
Х3 = min{(0,3); (3,5); (5,7)} = min{3,4,2} = 2.
Составляем новую таблицу:
P0
P1
P2
P3
P4
P5
P6
P7
P0
1
0
3-
2
P1
4
3
0
2
P2
7
2
3
0
3
P3
3+
1
4-
P4
5
1
2
P5
5
3
0+
0
2-
P6
2
8
1
2
0
P7
3
7+
8
Рассматриваем путь Р0, Р1, Р2, Р7.
P0
P1
P2
P3
P4
P5
P6
P7
P0
1-
0
1
2
P1
4+
3-
0
2
P2
7
2+
3
0
3-
P3
5
1
2
P4
5
1
2
P5
5
3
2
0
0
P6
2
8
1
2
0
P7
3+
9
8
Х4 = min{(0,1); (1,2); (2,7)} = min{1,1,3} = 1.
Выбираем путь Р0, Р3, Р5, Р2, Р7.
P0
P1
P2
P3
P4
P5
P6
P7
P0
0
0-
0
2-
P1
5
2
0
2
P2
7
3
4
0+
1-
P3
6
1
1
P4
5+
1
2-
P5
5
2
3
0
0
P6
2
8-
1+
2
0
P7
5+
9
8
Х5 = min{(0,3); (3,5); (5,2); (2,7)} = min{1,2,3,2} = 1.
Выбираем путь Р0, Р4, Р6, Р2, Р7.
P0
P1
P2
P3
P4
P5
P6
P7
P0
0
0
0
2-
P1
5
2
0
2
P2
7
3
4
0+
1-
P3
6
1
1
P4
5+
1
2-
P5
5
2
3
0
0
P6
2
8-
1+
2
0
P7
5+
9
8
Х6 = min{(0,4); (4,6); (6,2); (2,7)} = min{2,2,8,1} = 1.
P0
P1
P2
P3
P4
P5
P6
P7
P0
0
0
0
1
P1
5
2
0
2
P2
7
3
4
1
0
P3
6
1
1
P4
6
1
1
P5
5
2
3
0
0
P6
2
7
2
2
0
P7
6
9
8
В столбце Р7 имеются только 0. Вычитая из элементов первой таблицы элементы последней, получаем итоговую таблицу со значениями (i, j), определяющими максимально возможный поток.
P0
P1
P2
P3
P4
P5
P6
P7
P0
3
4
3
1
P1
1
2
P2
3
3
P3
3
P4
1
P5
1
4
P6
4
P7
Максимальный поток равен (0,1)+(0,2)+(0,3)+(0,4) = 3+4+3+1 = 11 (из строки Р0).
Или (2,7)+(5,7)+(6,7) = 3+4+4 = 11 (из столбца Р7).
Величина потока, исходящая из начального узла Р0, совпадает с величиной потока, поступающего в конечный узел Р7. Для любого другого узла поступающий поток численно равен исходящему потоку из того же узла. Схема приведена ниже.
[ Cкачайте файл, чтобы посмотреть картинку ]
Варианты заданий:
Определить кратчайший путь от вершины s до вершины t с использованием алгоритма Дейкстры.
Определить максимальный поток в сети с использованием алгоритма Форда-Фалкерсона.
Самостоятельная работа №22: Решение задач на графах
Цель: научиться решать задачи на графах
Самостоятельная работа: индивидуальное домашнее задание
Форма контроля: проверка работы
Теоретический материал и методические указания к выполнению заданий
Метрические характеристики графов
В теории графов применяются:
Матрица инцинденций. Это матрица А с 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.Определить метрические характеристики графа.
Самостоятельная работа №23: Подготовка сообщения «Колмогоров А.Н»
Цель: получить представление о математике А.н.Колмогорове, познакомиться с его математическими трудами
Самостоятельная работа: работа с литературой
Форма контроля: сообщение на уроке
Самостоятельная работа №24: Подготовка сообщения «СМО»
Цель: получить представление о СМО, их видах и основных характеристиках
Самостоятельная работа: работа с литературой
Форма контроля: сообщение на уроке
Самостоятельная работа №25: Составление систем уравнений Колмогорова
Цель: научиться составлять системы уравнений Колмогорова
Самостоятельная работа: индивидуальное домашнее задание
Форма контроля: проверка работы
Теоретический материал и методические указания к выполнению заданий
Уравнения Колмогорова А.Н.»
Финальные вероятности состояний
Будем рассматривать марковские процессы с дискретными состояниями и непрерывным временем.
Пример 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)
Финальные вероятности показывают, какое Самостоятельная работа №еднее время устройство будет находиться в каждом состоянии. Финальные вероятности находятся из системы дифференциальных уравнений, если их правые части приравнять нулю.
Варианты заданий:
Составьте систему уравнений по схеме:
Самостоятельная работа №26: Нахождение финальных вероятностей
Цель: научиться находить финальные вероятности событий
Самостоятельная работа: индивидуальное домашнее задание
Форма контроля: проверка работы
Теоретический материал и методические указания к выполнению заданий
Если финальные вероятности существуют:
13 EMBED Equation.3 1415 при i = 1, 2, 3, ..., n, (5)
то их сумма будет равна единице:
13 EMBED Equation.3 1415 (6)
Финальные вероятности показывают, какое Самостоятельная работа №еднее время устройство будет находиться в каждом состоянии. Финальные вероятности находятся из системы дифференциальных уравнений, если их правые части приравнять нулю.
Решение системы уравнений Колмогорова
Зададим численные значения интенсивности потоков событий для примера 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
Полученный результат меньше единицы, так как значение каждой вероятности было округленно.
Варианты заданий:
Решить систему уравнений примера 1 с данными:
(1=2; (2=1; (3=3; (1=4; (2=2; (3=4.
Самостоятельная работа №27: Подготовка сообщения на тему «Имитационное моделирование»
Цель: получить представление о имитационном моделировании
Самостоятельная работа: работа с литературой
Форма контроля: сообщение на уроке
Самостоятельная работа №28: Решение задачи управления запасами и задачи теории массового обслуживания, используя имитационное моделирование
Цель: научиться решать задачи управления запасами и задачи теории массового обслуживания, используя имитационное моделирование
Самостоятельная работа: индивидуальное домашнее задание
Форма контроля: проверка работы
Теоретический материал и методические указания к выполнению заданий
Суть имитационного моделирования
Имитационное моделирование – получение экспериментальной информации о сложном объекте, которая не может быть получена иным путем, как экспериментируя с его моделью на ПЭВМ.
Рассматривая исторический процесс формирования этого термина, пришли к выводу, что это словосочетание определяет в моделировании такую область, которая относится к получению экспериментальной информации о сложном объекте, которая не может быть получена иным путем, как экспериментируя с его моделью на ПЭВМ.
Имитационный объект имеет вероятностный характер функционирования. Для исследователя представляют интерес выводы, носящие характер статистических показателей, оформленных, может быть, даже в виде графиков или таблиц, в которых каждому варианту исследуемых параметров поставлены в соответствие определенные Самостоятельная работа №едние значения с набором характеристик их распределения, без получения зависимости в аналитическом виде.
Эта особенность является и достоинством, и одновременно, недостатком имитационным моделей. Достоинство в том, что резко расширяется класс изучаемых объектов, а недостаток – в отсутствии простого управляющего выражения, позволяющего прогнозировать результат повторного эксперимента. Но в реальной жизни также невозможно для сколько-нибудь сложного объекта получить точное значение экономического показателя, а только лишь его ожидаемое значение с возможными отклонениями.
Главной функцией имитационной модели является воспроизведение с заданной степенью точности прогнозируемых параметров её функционирования, представляющих исследовательский интерес. Как объект, так и его модель, должны обладать системными признаками.
Функционирование объекта характеризуется значительным числом параметров. Особое место Самостоятельная работа №еди них занимает временной фактор. В большинстве моделей имеется возможность масштабирования или введения машинного времени, т. е. интервала, в котором остальные параметры системы сохраняют свои значения или заменяются некоторыми обобщенными величинами. Таким образом, за счет этих двух процессов – укрупнения единицы временного интервала и расчета событий этого интервала за зависящий от мощности ПЭВМ временной промежуток – и создается возможность прогноза и расчета вариантов управленческих действий.
Метод Монте-Карло
Неопределённость в предыдущих темах была стохастической. Поэтому строили аналитическую математическую модель и требовали, чтобы в данных задачах, рассматриваемые процессы были марковскими. На практике это не всегда выполняется и тогда требуется использовать методы имитационного моделирования. Что это такое рассказывалось в предыдущем параграфе, а теперь поговорим о самих методах имитационного моделирования. Метод Монте-Карло является методом статистического моделирования или имитационного моделирования.
Метод Монте-Карло – это численный метод решения задач при помощи моделирования случайных величин. Создателями метода считают математиков Дж. Неймана и С. Улама.
Теоретическая основа метода была известна давно. Однако до появления ЭВМ этот метод не мог найти широкого применения.
Идея метода состоит в следующем: Вместо того чтобы описывать процесс с помощью аналитического аппарата, проводится розыгрыш случайного явления с помощью специально организованной процедуры, включающей в себя случайность и дающей случайный результат. Реализация случайного процесса каждый раз складывается по-разному, т. е. мы получаем различные исходы рассматриваемого процесса. Это множество реализаций можно использовать как некий искусственно полученный статистический материал, который может быть обработан обычными методами математической статистики. После такой обработки можно получить: вероятность события, математическое ожидание и т. д.
При помощи метода Монте-Карло может быть решена любая вероятностная задача, но оправданным он является тогда, когда процедура розыгрыша проще, а не сложнее аналитического расчета.
Пример: По цели производится 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 (количество проведённых опытов). Таким образом, они получили частоту события, а она при большом числе опытов близка к вероятности.
Метод Монте-Карло применяется: при моделировании случайных процессов, где присутствует множество случайных факторов.
Оценка надежности простейших систем методом Монте-Карло
Пример: Система состоит из двух блоков, соединенных последовательно. Система оказывает при отказе хотя бы одного блока. Первый блок содержит два элемента: А, В (они соединены параллельно) и оказывает при одновременном отказе обоих элементов. Второй содержит один элемент С и отказывает при отказе этого элемента.
а) Найти методом Монте-Карло оценку Р* надежности (вероятности безотказной работы) системы, зная вероятности безотказной работы элементов: Р (А)=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.
Расчет СМО с отказами методом Монте-Карло
Пример: В трехканальную систему массового обслуживания с отказом поступает пуассоновский поток заявок. Время между поступлениями двух последовательных заявок распределено по показательному закону 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.
Варианты заданий:
Система состоит из двух блоков, соединенных последовательно. Первый блок содержит три элемента: А, В, С, а второй- два элемента: D, E. Элементы каждого блока соединены параллельно.
а) Найти методом Монте-Карло оценку Р* надежности системы, зная вероятности безотказной работы элементов: Р(А)=0,8; Р(В)=0,7; Р(С)=0,9; Р(D)=0,8; P(E)=0,7;
б) найти абсолютную погрешность (Р-Р*(, где Р- надежность системы, вычисленная аналитически. Произвести 15 испытаний.
Система состоит из двух блоков, соединенных последовательно. Первый блок содержит два элемента: А, В, второй- три элемента: С, D, E. Элементы первого и второго блоков соединены параллельно.
а) Найти методом Монте-Карло оценку Р* надежности системы, зная вероятности безотказной работы элементов: Р(А)=0,9; Р(В)=0,6; Р(С)=0,7; Р(D)=0,75; P(E)=0,6;
б) найти абсолютную погрешность (Р-Р*(, где Р - надежность системы, вычисленная аналитически. Произвести 15 испытаний.
В двухканальную систему массового обслуживания с отказом поступает пуассоновский поток заявок. Время между поступлениями двух последовательных заявок распределено по показательному закону f(()=5e-5( . Длительность обслуживания каждой заявки равна 0,5 мин. Найти методом Монте-Карло математическое ожидание а числа обслуженных заявок за время Т=10 мин.
В трехканальную СМО с отказами поступает пуассоновский поток заявок. Время между моментами поступления двух последовательных заявок распределено по закону f(()=8 e-8(; время обслуживания заявок 1мин. Найти методом Монте-Карло математическое ожидание а числа обслуженных заявок за время Т=10 мин.
Самостоятельная работа №29: Формирование и усвоение содержания теоретического материала, используя информационные образовательные ресурсы
Цель: научиться использовать информационные образовательные ресурсы для самоконтроля по изучаемой теме
Самостоятельная работа: работа с Internet- ресурсами
Форма контроля: проверка работы
Самостоятельная работа №30: Работа над учебным материалом по первоисточникам
Цель: расширить теоретические знания по изучаемой теме
Самостоятельная работа: работа с литературой
Форма контроля: ответ на уроке
Самостоятельная работа №31: Построение прогнозов количественными и качественными методами
Цель: научиться решать задачи на применение метода наименьших квадратов
Самостоятельная работа: индивидуальное домашнее задание
Форма контроля: проверка работы
Теоретический материал и методические указания к выполнению заданий
Классификация прогнозирования
Прогнозирование – предсказание на основе каких-то методов как будет себя вести объект в определенный момент времени в будущем.
Прогнозы подразделяются на формализованные, эвристические и комплексные. Каждому классу прогноза присущи свои достоинства и ограничения.
Формализованные методы позволяют получать количественные показатели. При разработке таких прогнозов исходят из предположения об инерционности системы, т. е. предполагают, что в будущем система будет развиваться по тем же закономерностям, которые были у неё в прошлом и есть в настоящем. Недостатком формализованных методов является ограниченная глубина упреждения, находящаяся в пределах эволюционного цикла развития системы, за пределами которого надёжность прогнозов падает. К формализованным методам относятся экстраполяционные и регрессивные методы, метод группового учёта аргументов (МГУА), факторный анализ и др.
Эвристические методы основаны на использовании интеллекта человека, который на основании своих знаний и практического опыта способен предсказать качественные изменения в поведении прогнозируемого объекта, определять силу и продолжительность скачков его развития. Эвристические методы применяются там, где существует вероятность скачкообразных процессов в развитии системы, подразделяются на методы индивидуальных и коллективных экспертных оценок.
Комплексное прогнозирование объединяет в единую систему формализованные и эвристические методы, что позволяет повысить качество прогнозов.
В зависимости от глубины упреждения прогнозы подразделяются на оперативные, Самостоятельная работа №еднеСамостоятельная работа №очные и перспективные:
Оперативные прогнозы – ограничены по Самостоятельная работа №окам от долей секунды до года.
Самостоятельная работа №еднеСамостоятельная работа №очные – от года до пяти лет.
Перспективные – более пяти лет.
Если формализованные методы в силу присущих им ограничений используются для оперативных и краткоСамостоятельная работа №очных прогнозов, то эвристические методы чаще используются для Самостоятельная работа №еднеСамостоятельная работа №очных и перспективных прогнозов.
Формализованные методы прогнозирования
Методы экстраполяции
Методы экстраполяции в математическом смысле представляют собой распространение характера изменения функции из области её наблюдения в область, лежащую вне этого интервала.
Задача экстраполяции формируется так: пусть в интервале (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,
где
· – Самостоятельная работа №еднеквадратичное отклонение.
Проведение опроса в несколько туров и обязательное ознакомление экспертов с результатами каждого тура обеспечивает сходимость данных прогноза к медианному значению.
Морфологический метод позволяет не только получить технические характеристики прогнозируемого объекта, но и определить его структуру. Для этого исследуемый объект (проблема) разбивается на относительно независимые части (элементы). Затем для каждой из частей разрабатывается многовариантное решение, в основу которого берутся её конструктивные, технологические, функциональные или другие особенности. Общее решение о структуре и свойствах объекта или процесса получают, взяв одно решение от каждой части, руководствуясь при этом возможными ограничениями. Морфологический метод связан с системным подходом к изучаемому объекту, так как предусматривает использование всей совокупности знаний об объекте. Благодаря упорядоченному подходу к рассмотрению проблемы, он дает систематизированную информацию по всем возможным решениям изучаемой проблемы. Метод включает этапы исследования: точную формулировку подлежащей решению проблемы; тщательный анализ всех параметров, важных с точки зрения решения проблемы: построение морфологического ящика; выбор оптимального решения.
Комплексные методы прогнозирования
Каждый метод прогнозирования обладает своими достоинствами и недостатками, поэтому их объединение повышает достоверность прогнозов. Общий алгоритм комплексных методов прогнозирования предусматривает объединение формализованных и эвристических методов в одной системе. Эти методы могут находиться в следующих соотношениях:
Данные обоих прогнозов не противоречат друг другу, их можно совместно обрабатывать и получать комбинированный прогноз.
Данные этих прогнозов противоречивы, здесь требуется ввести обратные связи, раскрывающие причины расхождения данных прогнозов и произвести измерения условий прогнозирования.
Выбор комплексных методов в значительной степени зависит от Самостоятельная работа №оков, на которые делается прогноз и от объема имеющейся информации. В общем, комплексные методы наиболее приемлемы для долгоСамостоятельная работа №очных прогнозов.
Линейное сглаживание функции
Метод наименьших квадратов один из методов [ 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
Самостоятельная работа №32: Работа над учебным материалом по первоисточникам
Цель: расширить теоретические знания по изучаемой теме
Самостоятельная работа: работа с литературой
Форма контроля: ответ на уроке
Самостоятельная работа №33: Антагонистические матричные игры: чистые и смешанные стратегии
Цель: расширить теоретические знания, получить умения по решению задач по изучаемой теме
Самостоятельная работа: работа с литературой, индивидуальное домашнее задание
Форма контроля: проверка работы
Теоретический материал и методические указания к выполнению заданий
Элементы и теория игр
Основные понятия теории игр
При решении задач в области экономики и управления производством в условиях неполноты и неточности информации возможны ситуации, когда необходимо принятие решений в условиях риска и неопределенности.
Предметом изучения теории игр являются ситуации, когда отсутствует полнота информации, а аппарат теории игр предназначен для выбора оптимальных решений в условиях неопределенности. Методы теории игр разработаны применительно к специфическим конфликтным ситуациям, которые обладают свойством многократной повторяемости. Целью теории игр является выработка рекомендаций по рациональному образу действия участников многократно повторяющегося конфликта. Под конфликтными ситуациями понимается положение, когда сталкиваются интересы двух и более сторон, причем выигрыш зависит от того, как поведут себя другие стороны. Математический анализ конфликта возможен при построении математической модели конфликта. Такая модель называется игрой. От реального конфликта игра отличается тем, что ведется по определенным правилам, которые участникам конфликта известны и строго выполняются. Игра называется парной, если в ней участвуют две стороны. Если в парной игре выигрыш одного из игроков равен проигрышу другого, то такая парная игра называется игрой с нулевой суммой. Конечной игрой называется игра с конечным числом стратегий. Стратегией называется совокупность правил, определяющих выбор варианта действия при каждом ходе в зависимости от сложившейся ситуации. Ходы бывают личные и случайные. При случайном ходе – выбор стратегии случайный. Стратегия игрока называется оптимальной, если при многократном повторении игры она обеспечивает ему максимальный Самостоятельная работа №едний выигрыш или минимальный Самостоятельная работа №едний проигрыш.
Матричные игры
Пусть игрок А имеет m чистых стратегий А1, А2, Аi,Аm, а игрок В имеет n чистых стратегий B1, B2, Bj,Bn. Такая игра называется игрой m х n. Если игрок А пользуется стратегией Аi, а игрок В пользуется стратегией Вj, то обозначим через аij выигрыш игрока А, если аij > 0, или проигрыш игрока А, если аij < 0. Очевидно, что – это одновременно проигрыш игрока В, если аij > 0, и выигрыш игрока В, если аij < 0.
Тогда мы можем привести игру к матричной форме, т.е. составить матрицу, которая называется платежной матрицей, или матрицей игры:
В1
В2
Вj
Вn
А1
а11
а12
а 1j
а 1n
А2
а21
а 22
а 2j
а 2n
Аi
аi1
а i2
а ij
а in
Аm
аm1
а m2
а mj
а mn
Каждая строка этой матрицы соответствует некоторой стратегии игрока А, а каждый столбец – некоторой стратегии игрока В.
Пример игры. Два игрока выкидывают на пальцах числа, причем четное число пальцев – это выигрыш игрока А, нечетное – проигрыш игрока А. Для простоты введем ограничение – игроки выкидывают от 1 до 3 пальцев.
Составим платежную таблицу:
В1
В2
В3
Вn
А1
2
-3
4
-3
А2
-3
4
-5
-5
А3
4
-5
6
-5
max
i
4
4
6
13 EMBED Equation.3 1415
Проанализируем матрицу игры: для каждой чистой стратегии игрока А определим минимальный выигрыш, т.е. определим
(i = 13 EMBED Equation.3 1415аij.
В нашем примере (1 = -3; (2 = -5; (3 = -5. Далее, Самостоятельная работа №еди полученных значений (i-х определим максимальное
( =13 EMBED Equation.3 1415(i = 13 EMBED Equation.3 141513 EMBED Equation.3 1415аij.
В нашем примере ( = -3, т.е. игрок А проигрывает 3 очка. Это число ( называется нижней ценой игры, а соответствующая ему стратегия называется максиминной. В нашем примере стратегия А1 максиминная, т.е. из всех наихудших ситуаций выбирают наилучшую. Эта величина (() – гарантированный «выигрыш» игрока А, какую бы стратегию ни выбрал игрок В.
Меньше нижней цены игры игрок А никогда не «выиграет».
Игрок В старается максимально уменьшить свой проигрыш. Для этого определяется верхняя цена игры
( =13 EMBED Equation.3 1415(j = 13 EMBED Equation.3 141513 EMBED Equation.3 1415аij.
Соответствующая стратегия называется минимаксной. В нашем примере будет две минимаксных стратегии В1 и В2. При этом игрок В проигрывает 4 очка.
Теорема 1. В любой матричной игре справедливо неравенство ( ( (, т.е. нижняя цена игры никогда не превосходит верхнюю.
Игра с седловой точкой
Если в матричной игре нижняя и верхняя цены игры совпадают, то такая игра имеет «седловую точку» в чистых стратегиях, а число ( = ( = ( называют ценой игры. В этом случае решением игры, т.е. оптимальным поведением для обоих игроков являются их максиминная для игрока А и минимаксная для игрока В стратегии игры. Любое отклонение игроков от своих оптимальных стратегий не может оказаться им выгодным. Элемент платежной матрицы, отвечающий оптимальным стратегиям, называется седловой точкой.
Пример. Пусть игра задана следующей платежной матрицей:
В1
В2
В3
В4
(i
А1
9
3
8
2
2
А2
4
2
7
3
2
А3
6
4
7
8
4
А4
5
3
4
7
3
(j
9
4
8
8
цена игры ( = ( = ( = 4
min max - лучшая стратегия для игрока В – (В2)
Игра в смешанных стратегиях
Если платежная матрица не имеет седловой точки, то если игрок будет пользоваться смешанными стратегиями, т.е. при каждом ходе менять стратегию случайным образом, то игрок А выигрывает больше, чем (, а игрок В проигрывает больше, чем (.
Рассмотрим платежную матрицу (1). Пусть игрок А использует чистые стратегии А1, А2, Аi,Аm с вероятностями p1, p2, pi,pm, причем 13 EMBED Equation.3 1415=1, а игрок В использует свои чистые стратегии В1, В2, Вj,Bn с вероятностями q1, q2, qj, qn, причем 13 EMBED Equation.3 1415= 1.
Тогда набор SA = (p1, p2, pi,pm) называется смешанной стратегией игрока А, а набор SB = (q1, q2, qj, qn) - смешанной стратегией игрока В.
Поскольку игроки выбирают свои стратегии случайным образом, то вероятность выбрать комбинацию АiВj по теории вероятности равна (Pi ( qj). При использовании смешанных стратегий игра становится случайной, тогда говорят о Самостоятельная работа №еднем значении выигрыша, который определяется платежной функцией
f(SA, SB) = 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 141513 EMBED Equation.3 1415) и 13 EMBED Equation.3 1415= (13 EMBED Equation.3 1415,13 EMBED Equation.3 1415,13 EMBED Equation.3 141513 EMBED Equation.3 1415) называются оптимальными, т.е. дающими каждой стороне максимальный возможный для нее Самостоятельная работа №едний выигрыш (для А) или минимальный Самостоятельная работа №едний проигрыш (для В), если они образуют седловую точку для платежной функции (2), т.е. если выполняется следующее условие:
f(SA, 13 EMBED Equation.3 1415) ( f(13 EMBED Equation.3 1415,13 EMBED Equation.3 1415) ( f(13 EMBED Equation.3 1415, SB).
Величина ( = f(13 EMBED Equation.3 1415, SB) называется ценой игры.
Теорема 2. В смешанных стратегиях любая матричная игра имеет седловую точку, или каждая матричная игра с нулевой суммой имеет решение в смешанных стратегиях.
Решение игры в смешанных стратегиях
Теорема 3. Для того чтобы смешанные стратегии 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415 были оптимальными в игре с матрицей (1) и ценой игры (, необходимо и достаточно, чтобы выполнялись следующие неравенства:
13 EMBED Equation.3 1415( (; j = 13 EMBED Equation.3 1415, причем 13 EMBED Equation.3 1415= 1; (3)
13 EMBED Equation.3 1415( (; i = 13 EMBED Equation.3 1415, причем 13 EMBED Equation.3 1415= 1. (4)
Нахождение оптимальной стратегии можно свести к решению задачи линейного программирования.
Пусть требуется найти оптимальные стратегии для игры с заданной платежной матрицей (1), для которой aij строго больше нуля (аij >0, i=13 EMBED Equation.3 1415,j = 13 EMBED Equation.3 1415), тогда цена игры ( > 0. Найдем оптимальную стратегию игрока А – (13 EMBED Equation.3 1415).
Разделим левую и правую части в выражении (3) на положительную величину (:
13 EMBED Equation.3 141513 EMBED Equation.3 1415( 1; 13 EMBED Equation.3 1415= 13 EMBED Equation.3 1415.
Введем обозначение 13 EMBED Equation.3 1415 = Хi, тогда
13 EMBED Equation.3 1415Хi ( 1; j = 13 EMBED Equation.3 1415; 13 EMBED Equation.3 1415= 13 EMBED Equation.3 1415.
Поскольку игрок А стремится сделать свой гарантированный выигрыш (() как можно большим (( ( max), то величина 13 EMBED Equation.3 1415 должна быть как можно меньше (( ( min), тогда имеем следующую задачу линейного программирования:
f(x) = 13 EMBED Equation.3 1415( min, (5)
13 EMBED Equation.3 1415Хi ( 1; j = 13 EMBED Equation.3 1415, (6)
Хi ( 0; i = 13 EMBED Equation.3 1415. (7)
Если Х* = (13 EMBED Equation.3 1415,13 EMBED Equation.3 1415,13 EMBED Equation.3 141513 EMBED Equation.3 1415) – оптимальный план задачи (5) – (7), а минимум функции f(x) = f(x*) = f*, то цена игры ( при этом составит ( = 13 EMBED Equation.3 1415, а т.к. 13 EMBED Equation.3 1415= Хi, тогда 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) – оптимальная смешанная стратегия игрока А.
Для игрока В используя выражение (4), получим
g(y) = 13 EMBED Equation.3 1415( max.
13 EMBED Equation.3 1415yj ( 1, i = 13 EMBED Equation.3 1415.
yj ( 0; j = 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,
т.е. ( ( ( – седловой точки нет.
А1
1
10
3
А2
8
4
5
Сведем данную задачу к задаче линейного программирования.
Найдем оптимальную стратегию игрока А – (13 EMBED Equation.3 1415):
f(x) = X1 + X2 ( min.
X1 + 8X2 ( 1,
10X1 + 4X2 ( 1,
3X1 + 5X2 ( 1,
X1 , X2 ( 0.
f(x) = 0,21; X1 = 0,026; X2 = 0,184,
отсюда
( = 13 EMBED Equation.3 1415= 4,76; P1 = 4,76 ( 0,026 = 0,124; P2 = 4,76 ( 0,184 = 0,876.
Найдем оптимальную стратегию игрока В – (13 EMBED Equation.3 1415):
g(y) = y1 + y2 + y3 ( max.
y1 + 10y2 + 3y3 ( 1,
8y1 + 4y2 + 5y3 ( 1,
y1 , y2 , y3 ( 0.
g(y) = 0,21; y1 = 0; y2 = 0,0526; y3 = 0,158,
отсюда
q1 = 0; q2 = 4,76 ( 0,0526 = 0,25; q3 = 4,76 ( 0,158 = 0,75.
Таким образом, применяя свою первую чистую стратегию с вероятностью 0,124 и вторую – с вероятностью 0,876, игрок А выигрывает величину 4,76. Игрок В, применяя свою вторую чистую стратегию с вероятностью 0,25 и третью – с вероятностью 0,75, проигрывает величину 4,76, иначе он проигрывает больше.
Игра два на два (2 х 2)
Рассмотрим игру, в которой у игроков А и В по две стратегии. Платежная матрица имеет вид
В1
В2
(8)
А1
a11
a12
А2
a21
a22
Рассмотрим случай, когда игра не имеет седловой точки.
Теорема 4. Пусть 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415 – оптимальные смешанные стратегии игры с платежной матрицей (1) и ценой игры (, тогда для любого i, при котором выполняется строгое неравенство
13 EMBED Equation.3 1415qj < (,
имеет место равенство pi = 0. А если pi > 0, то
13 EMBED Equation.3 1415qj = (.
Аналогично, если для некоторых j
13 EMBED Equation.3 1415( pi > (,
то для этих j qj = 0. А если qj > 0, то
13 EMBED Equation.3 1415( pi = (.
Определим оптимальную смешанную стратегию 13 EMBED Equation.3 1415 игрока А, а для этого решим систему трех уравнений с тремя неизвестными
а11 ( p1 + а21 ( p2 = (,
а12 ( p1 + а22 ( p2 = (,
p1 + p2 = 1.
Решив следующую систему, найдем оптимальную стратегию 13 EMBED Equation.3 1415 игрока В:
а11 ( q1 + а12 ( q2 = (,
а21 ( q1 + а22 ( q2 = (,
q1 + q2 = 1.
Рассмотрим первую систему. Вычитая из первого равенства второе, получая
(а11 - а12) ( p1 + (а21 - а22) ( p2 = 0.
Подставим P2 = 1 - P1, тогда
(а11 - а12) ( p1 + (а21 - а22) (1- p1 ) = 0,
отсюда оптимальная смешанная стратегия для игрока А – А*( p1, p2)
P1 = (а22 - а21)/( а11 - а12 + а22 - а21),
P2 = 1- P1 = (а11 - а12)/( а11 - а12 + а22 - а21).
цена игры
( = ( а11 ( а22 - а21 ( а12)/ ( а11 - а12 + а22 - а21).
Рассуждая аналогично, для определения оптимальной стратегии игрока В получая
q1 = (а22 - а12)/( а11 - а12 + а22 - а21),
q2 = (а11 - а21)/( а11 - а12 + а22 - а21).
Пример. Имеются две конкурирующие фирмы А и В, выпускающие изделия двух модификаций. Изучение спроса покупателей показало, что если выпускаются изделия первой модификации обеими фирмами, А1 и В1, то 40 % покупателей предпочитают изделия фирмы А и 60 % - фирмы В. Если выпускаются изделия А1 и В2, то 90 % покупателей приобретают изделия А. Если изготавливаются изделия А2 и В1, будет продано 70 % изделий фирмы А. Наконец, если выпускаются изделия второй модификации А2 и В2 обеими фирмами, то 20 % покупателей предпочитают изделия фирмы А.
Решение. Представим выигрыш фирмы А в табличной форме
а11 = 40 % - 60 % = -20 %; а12 = 90 % - 10 % = 80 %;
а21 = 70 % - 30 % = 40 %; а22 = 20 % - 80 % = -60 %.
В1
В2
(i
А1
-20
80
-20
А2
40
-60
-60
(j
40
80
Нижняя цена игры составляет (-20), верхняя равна 40. Игра не имеет седловой точки. Найдем оптимальные смешанные стратегии
13 SHAPE \* MERGEFORMAT 1415
p1 = (-60 - 40)/(-20 –80-60-40) = 13 EMBED Equation.3 1415; p2 = 13 EMBED Equation.3 1415;
( = [-20 ( (-60)- 40 ( 80]/ (-20 –80-60-40) = 10;
q1 = (-60 - 80)/(-20 –80-60-40) = 13 EMBED Equation.3 1415; q2 = 13 EMBED Equation.3 1415.
Выигрыш фирмы А в соответствии с ценой игры составит 10 %. Следовательно, А – В = 10 %, но А + В = 100 %, тогда А = 55 %; В = 45 %. Следовательно, при таких оптимальных стратегиях изделия фирмы А будут покупать 55 % потребителей, а фирма В – 45 % покупателей.
Геометрическое решение игры
Пусть игра 2 х 2 имеет платежную матрицу (8). Изобразим на оси абсцисс отрезок горизонтальной линии единичной длины и обозначим концы отрезка через нуль и единицу. Из точек 0 и 1 по осям ординат восстановим перпендикулярные линии и изобразим на них выигрыши игрока А при использовании им соответственно чистых стратегий А1 и А2. Все промежуточные точки отрезка (13 EMBED Equation.3 1415) будут изображать смешанные стратегии:
13 SHAPE \* MERGEFORMAT 1415
При оптимальной смешанной стратегии 13 EMBED Equation.3 1415выигрыш игрока А будет составлять величину ( и отмечен точкой М. Произведем аналогичные построения для игрока В:
13 SHAPE \* MERGEFORMAT 1415
13 SHAPE \* MERGEFORMAT 1415
При графическом решении игр возможны и другие ситуации:
Пример. Найдем графическое и аналитическое решение игры:
В1
В2
( = 4, ( = 5, ( ( ( -
следовательно, седловой точки нет.
А1
2
5
А2
6
4
Найдем оптимальную смешанную стратегию игрока А
13 SHAPE \* MERGEFORMAT 1415
Найдем оптимальную смешанную стратегию игрока В:
13 SHAPE \* MERGEFORMAT 1415
Игры 2 х n и m х 2
Допустим, платежная матрица задана и имеет вид 2 х n:
В1
В2
Вn
Игрок А имеет две стратегии, а игрок В – неограниченное число стратегий.
А1
a11
a12
a1n
А2
a21
a22
a2n
13 SHAPE \* MERGEFORMAT 1415
Допустим, платежная матрица имеет вид m х 2:
13 SHAPE \* MERGEFORMAT 1415
Минимум М находится на пересечении стратегий А1 и Аm, остальные отбрасываются, далее игра решается как задача 2 х 2.
Пример. Пусть игра задана в виде платежной матрицы
В1
В2
В3
Игра (2 х 3) не имеет седловой точки ( = 4, ( = 5, ( ( (, имеем игру в смешанных стратегиях.
А1
1
10
3
А2
8
4
5
Решим задачу графически и аналитически. Для игрока А: получаем игру 2 х 2, используя стратегии В2 и В3 игрока В:
Для игрока В:
13 SHAPE \* MERGEFORMAT 1415
Самостоятельная работа №34: Область применимости теории принятия решений
Цель: получить знания о применении теории принятия решений
Самостоятельная работа: работа с литературой
Форма контроля: ответ на уроке
Самостоятельная работа №35: Работа над учебным материалом по первоисточникам
Цель: расширить теоретические знания по изучаемой теме
Самостоятельная работа: работа с литературой
Форма контроля: ответ на уроке
Методические указания к самостоятельной работе студента
Целевые направления самостоятельной работы студентов
1.Для овладения и углубления знаний:
- составление различных видов планов и тезисов пот тексту;
- конспектирование текста;
- создание презентации.
2. Для закрепления знаний:
- работа с конспектом лекции;
- повторная работа с учебным материалом;
- составление плана ответа;
- составление различных таблиц.
3. Для систематизации учебного материала:
- подготовка ответов на контрольные вопросы;
- аналитическая обработка текста;
- подготовка сообщения, доклада;
- тестирование;
- составление кроссворда;
- формирование плаката;
- составление памятки.
4 .Для формирования практических и профессиональных умений.
-решение задач и упражнений по образцу;
-решение ситуативных и профессиональных задач;
Приёмы самостоятельной работы студентов.
1. Работа с учебником.
Для обеспечения максимально возможного усвоения материала и с учётом индивидуальных особенностей студенов, можно предложить им следующие приёмы обработки информации учебника:
- конспектирование;
- составление плана учебного текста;
- тезирование;
- аннотирование;
- выделение проблемы и нахождение путей её решения;
- самостоятельная постановка проблемы и нахождение в тексте путей её решения;
- определение алгоритма практических действий (план, схема).
2. Опорный конспект.
Опорный конспект необходимо давать на этапе изучения нового материала, а потом использовать его при повторении.
Опорный конспект позволяет не только обобщать, повторять необходимый теоретический материал, но и даёт педагогу огромный выигрыш во времени при прохождении материала.
3. Тесты
Основное достоинство тестовой формы контроля – это простота и скорость, с которой осуществляется первая оценка уровня обученности по конкретной теме, позволяющая, к тому же, реально оценить готовность к итоговому контролю в иных формах и, в случае необходимости, откорректировать те или иные элементы темы.
4.Семинар
Форма проведения семинара очень гибкая.
На семинарах решаются следующие задачи:
- углубление, конкретизация и систематизация знаний, полученных студентами на предшествующих этапах учёбы;
- развитие навыков самостоятельной работы
- ознакомление со спецификой работы с литературой;
- профессиональное использование знаний в учебных условиях.
Типы проведения семинарских занятий:
- вопросно-ответный семинар;
- развёрнутая беседа на основе заранее данного студентам плана, обсуждение письменных рефератов;
- заслушивание устных докладов студентов с последующим их обсуждением;
- семинар – диспут;
- теоретическая конференция;
- семинар – имитационная игра;
- комментированное чтение первоисточников.
5. Задачное обучение.
- практико-ориентированные задачи: выступают средством формирования у студентов системы интегрированных умений и навыков, необходимых для освоения профессиональных компетенций. Это могут быть ситуации, требующие применения умений и навыков, специфичных для профессии педагога (знания содержания предмета), ситуации, требующие организации деятельности, выбора её оптимальной структуры (организация детского коллектива, принципы организации занятий с детьми и т.п), личностно-ориентированных ситуаций (нахождение нестандартного способа решения).
- профессиональные задачи: выступают средством формирования у студентов умений определять, разрабатывать и применять оптимальные методы решения профессиональных задач. Они строятся на основе ситуаций, возникающих на различных уровнях осуществления практики и формулируются в виде производственных поручений (заданий).
Задачное обучение способно обеспечить целенаправленное, поэтапное формирование и контроль сформированности необходимых профессиональных компетенций.
Правила работы с книгой
При работе с книгой необходимо подобрать литературу, научиться правильно ее читать, вести записи. Для подбора литературы в библиотеке используются алфавитный и систематический каталоги.
Важно помнить, что рациональные навыки работы с книгой - это всегда большая экономия времени и сил.
Правильный подбор учебников рекомендуется преподавателем, читающим лекционный курс. Необходимая литература может быть также указана в методических разработках по данному курсу.
Изучая материал по учебнику, следует переходить к следующему вопросу только после правильного уяснения предыдущего, описывая на бумаге все выкладки и вычисления (в том числе те, которые в учебнике опущены или на лекции даны для самостоятельного вывода).
При изучении любой дисциплины большую и важную роль играет самостоятельная индивидуальная работа.
Особое внимание следует обратить на определение основных понятий курса. Студент должен подробно разбирать примеры, которые поясняют такие определения, и уметь строить аналогичные примеры самостоятельно. Нужно добиваться точного представления о том, что изучаешь. Полезно составлять опорные конспекты. При изучении материала по учебнику полезно в тетради (на специально отведенных полях) дополнять конспект лекций. Там же следует отмечать вопросы, выделенные студентом для консультации с преподавателем.
Выводы, полученные в результате изучения, рекомендуется в конспекте выделять, чтобы они при перечитывании записей лучше запоминались.
Опыт показывает, что помогает составление листа опорных сигналов, содержащего важнейшие и наиболее часто употребляемые формулы и понятия. Такой лист помогает запомнить формулы, основные положения лекции, а также может служить постоянным справочником для студента.
Различают два вида чтения; первичное и вторичное. Первичное - эти внимательное, неторопливое чтение, при котором можно остановиться на трудных местах. После него не должно остаться ни одного непонятного олова. Содержание не всегда может быть понятно после первичного чтения.
Задача вторичного чтения полное усвоение смысла целого (по счету это чтение может быть и не вторым, а третьим или четвертым).
Основные виды систематизированной записи прочитанного:
Аннотирование – предельно краткое связное описание просмотренной или прочитанной книги (статьи), ее содержания, источников, характера и назначения;
Планирование – краткая логическая организация текста, раскрывающая содержание и структуру изучаемого материала;
Тезирование – лаконичное воспроизведение основных утверждений автора без привлечения фактического материала;
Цитирование – дословное выписывание из текста выдержек, извлечений, наиболее существенно отражающих ту или иную мысль автора;
Конспектирование – краткое и последовательное изложение содержания прочитанного.
Конспект – сложный способ изложения содержания книги или статьи в логической последовательности. Конспект аккумулирует в себе предыдущие виды записи, позволяет всесторонне охватить содержание книги, статьи. Поэтому умение составлять план, тезисы, делать выписки и другие записи определяет и технологию составления конспекта
Методические рекомендации по составлению конспекта:
Внимательно прочитайте текст. Уточните в справочной литературе непонятные слова. При записи не забудьте вынести справочные данные на поля конспекта;
Выделите главное, составьте план;
Кратко сформулируйте основные положения текста, отметьте аргументацию автора;
Законспектируйте материал, четко следуя пунктам плана. При конспектировании старайтесь выразить мысль своими словами. Записи следует вести четко, ясно.
Грамотно записывайте цитаты. Цитируя, учитывайте лаконичность, значимость мысли.
В тексте конспекта желательно приводить не только тезисные положения, но и их доказательства. При оформлении конспекта необходимо стремиться к емкости каждого предложения. Мысли автора книги следует излагать кратко, заботясь о стиле и выразительности написанного. Число дополнительных элементов конспекта должно быть логически обоснованным, записи должны распределяться в определенной последовательности, отвечающей логической структуре произведения. Для уточнения и дополнения необходимо оставлять поля.
Овладение навыками конспектирования требует от студента целеустремленности, повседневной самостоятельной работы.
ТРЕБОВАНИЯ К ОФОРМЛЕНИЮ СООБЩЕНИЙ
Текст сообщения распечатать на бумаге формата А4.
По всем сторонам листа оставить поля от края листа. Размеры: левого поля - 20 мм; правого поля - 10 мм; верхнего поля - 15 мм; нижнего поля - 15 мм.
Использовать шрифт Times New Roman. Цвет шрифта должен быть чёрным, кегль – 12 пт. Можно использовать компьютерные возможности акцентирования внимания на определённых терминах, применяя различные способы начертания.
Заголовки следует располагать в середине строки без точки в конце и печатать прописными буквами, не подчеркивая.
Для абзацев, не являющихся заголовками, установить отступ первой строки на 12,5 мм и выравнивание – по ширине. Расстояние между абзацами – 3 пт.
Если в сообщении более одной страницы, то страницы следует нумеровать арабскими цифрами.
Обязательно напечатать список использованных источников (название статей, сайтов, или др. и адреса Web-страниц). В сообщении должны быть ссылки на используемую литературу.
Не забудьте подписать сообщение (указать фамилию, имя учащегося, подготовившего сообщение).
Основное требование к содержанию: сообщение должно быть информативно и интересно для большинства студентов.
Требования к докладам и докладчикам
Доклады, с которыми студенты выступают на семинарских занятиях, дают возможность разнообразить формы и содержание занятий, учитывая особые интересы студентов и не ограничиваясь тематическими рамками, установленными программой учебной дисциплины. Доклады позволяют студентам реализовать свои способности к самостоятельным научным исследованиям и творчеству.
Доклады представляют собой устные сообщения продолжительностью до 10 минут.
Доклад готовится по собственной инициативе студента, т.е. никто не обязывается к выступлению с докладом, но всякий имеет право предложить своё выступление вниманию студенческой группы и преподавателя.
Тему доклада студент определяет сам, исходя из собственных научно-исследовательских интересов. Разумеется, тема должна соответствовать изучаемой дисциплине.
При подготовке доклада следует ознакомиться с литературой по избранной теме. Основными источниками должны служить научные статьи и монографии, написанные компетентными авторами и опубликованные в научных и научно-популярных изданиях. Могут быть использованы также статьи из словарей и энциклопедий. Не рекомендуется воспроизводить в докладах тексты из учебных пособий (учебники служат для подготовки обычных уроков, а не исследовательских работ).
Недопустимо использование для доклада чужих рефератов, которых в Интернете имеется великое множество. Нельзя также составлять доклад из фрагментов чужих статей и монографий.
Умение студента прочитать вслух перед аудиторией чужие тексты, скачанные из Интернета или отсканированные, не заслуживает положительной оценки. На такие «доклады» не стоит тратить учебное время.
Во избежание плагиатов, выдаваемых за самостоятельно подготовленные доклады, тексты докладов или их аннотации будут подвергаться предварительному просмотру преподавателем. ,
Автор доклада должен показать актуальность избранной темы, сформулировать цель и задачи своего исследования, т.е. кратко объяснить, что и зачем он, собственно, хочет сказать, а в завершение своей речи он должен сделать выводы и обобщения. К тексту доклада следует приложить список использованной литературы. Автор доклада должен позаботиться о том, чтобы его слушатели могли понять, в чём заключается его самостоятельная работа.
Успех и оценка доклада в немалой степени зависят от того, насколько он окажется интересным для аудитории, сможет ли он вызвать живую дискуссию.
Требования к оформлению мультимедийных презентаций
Создавая презентацию, всегда думайте о тех, для кого она создается.
Каждый слайд должен иметь простую, понятную структуру и содержать текстовые или графические элементы, несущие в себе зрительный образ как основную идею слайда.
Цепочка образов должна полностью соответствовать логике. Такой подход способствует хорошему восприятию материала и воспроизведению в памяти представленного содержания посредством ассоциаций.
Используйте короткие слова и предложения. Минимизируйте количество предлогов, наречий, прилагательных.
Заголовки должны привлекать внимание (но не занимать все место и не отвлекать).
Текст, таблицы, диаграммы, схемы в презентациях
Для того чтобы ваша презентация имела успех, следует соблюдать ряд требований по ее оформлению.
Предпочтительно горизонтальное расположение материала.
Наиболее важная информация должна располагаться в центре экрана.
При выборе цветового оформления слайдов презентации следует учитывать тот факт, что мультимедийные проекторы проецируют изображение на экран по-разному: светлее, чем оно есть на самом деле или темнее.
На одном слайде рекомендуется использовать не более четырех цветов: один для фона, один-два для заголовков и один-два для текста. Достигайте сочетаемости цветов.
Для фона лучше использовать светлые тона. Цвет и размер шрифта, оформление шаблона должны быть подобраны так, чтобы все надписи читались.
Выбор размера шрифта на слайде определяется, исходя из нескольких условий:
размера помещения и максимальной удаленностью зрителей от экрана;
освещенности помещения и качества проекционной аппаратуры.
Текст должен читаться из самой дальней точки помещения, где происходит демонстрация.
Примерные рекомендуемые размеры шрифтов (с учетом демонстрации презентации в маленьком учебном классе):
заголовок – 22-28 pt;
подзаголовок – 20 -24 pt;
текст – 18 - 22 pt;
подписи данных в диаграммах – 18 - 22 pt;
шрифт легенды – 16 - 22 pt;
информация в таблицах – 18 -22 pt.
Помните, чем больше помещение и удаленнее зрители (ученики) от экрана, тем крупнее должен быть шрифт.
Наименьшую высоту буквы (h), проецируемой на экран, можно рассчитать по формуле: h = 0, 003D, где D – расстояние от учащихся, сидящих за последними столами кабинета, до экрана.
Не рекомендуется смешивать разные типы шрифтов. Нельзя злоупотреблять прописными буквами, т.к. они читаются хуже.
Количество текста на слайде регулируется с учетом назначения самой презентации и категории людей, на которых она рассчитана. (Чем младше дети, тем меньше информации на слайде должно быть).
С точки зрения эффективного восприятия текстовой информации, один слайд в среднем должен содержать 7 - 13 строк. На слайде следует располагать список не более чем из 5-6 пунктов, в каждом из которых – не более 5-6 слов.
Текстовая информация на слайде отражает цель и содержание урока (лекции, воспитательного мероприятия). С точки зрения содержания, текст на слайде - это определения, выводы, формулы, перечень объектов и пр. Как правило, один слайд – одна идея.
Если вы используете таблицы на слайдах, то текстовая информация в ней должна хорошо читаться. Поэтому размер шрифта определяется в соответствии с требованиями к тексту, представленными выше. Следует отметить, что шрифт таблицы, может быть на 1-2 пункта меньше, чем основной текст на слайде.
Одну таблицу можно разместить на нескольких слайдах (с сохранением заголовков) во избежание мелкого шрифта
Таблица в презентации может стать более наглядной, если использовать приемы выделения цветом отдельных областей таблицы.
Размер и вид используемой диаграммы на слайде определяется в соответствии с требованиями эффективного восприятия наглядной и текстовой информации.
С точки зрения восприятия графических объектов, на одном слайде рекомендуется размещать не более 3-х круговых диаграмм.
Тип диаграммы должен соответствовать типу отображаемых данных.
Данные и подписи не должны накладываться друг на друга и сливаться с графическими элементами диаграммы.
Если при форматировании слайда есть необходимость пропорционально уменьшить размер диаграммы, то размер шрифтов должен быть увеличен с таким расчетом, чтобы текстовая информация читалась.
Таблицы и диаграммы лучше размещать на светлом или белом фоне.
При демонстрации таблиц и диаграмм уместно последовательное появление текстовой информации, что достигается с помощью настроек анимационных эффектов. При этом следует придерживаться следующих правил: единство стиля подачи материала; удобство восприятия текстовой и наглядной информации.
Если вы используете схемы, то на одном слайде рекомендуется размещать не более одной схемы.
Схема располагается в центре слайда, заполняя всю его площадь.
Количество элементов на схеме определяется, с одной стороны, ее назначением, а с дугой – элементарным правилом «разумности» с точки зрения зрительного восприятия.
Текстовая информация в схеме должна хорошо читаться. Поэтому размер шрифта определяется в соответствии с требованиями к тексту, представленными выше.
При выборе цветовой гаммы и конфигурации объектов схемы помните, что схема – это наглядный образ содержания. Внешний вид схемы должен гармонично сочетаться с другими слайдами презентации.
Рисунки, фотографии
Общие требования к использованию рисунков и фотографий на слайдах:
разумное дозирование количества фотографий и рисунков в презентации и на одном слайде (как правило, это 3-5 изображений для иллюстрации одной идеи);
размещение фотографий и рисунков на слайде должно отвечать общим дизайн-эргономическим требованиям экранного представления информации;
для облегчения «веса презентации», т.е уменьшения объема файла фотографии рекомендуется представлять в сжатом виде;
все рисунки должны быть подписаны; подпись располагается снизу.
Анимации и эффекты
Одна из самых привлекательных особенностей презентации – конечно, интерактивность, что обеспечивается различными анимационными эффектами.
При создании презентации педагогу важно помнить:
· Увиденное сначала предстает перед нами как образ – мы реагируем на поведение объекта (движение, изменение формы и цвета), выделяем размер, цвет, форму, а затем обращаем внимание на содержание.
· Понимание закономерностей восприятия, грамотное, планомерное использование приемов анимации – это залог повышения эффективности восприятия материала, представленного в презентации.
· С помощью анимации создается модель какого-либо процесса, явления, наглядного решения задачи, последовательности выполнения каких-либо действий, ответов на вопросы и т.д.
· Не следует увлекаться анимациями, помня о том, что важен не внешний эффект, а содержание информации.
Планируя и оценивая презентацию, помните: анимации и эффекты – только к месту.
Литература
Основные источники
Партыка Т.Л., Попов И.И. Математические методы. – М.: ФОРУМ : ИНФРА-М, 2012.
Агальцов В.П., Волдайская И.В.. Математические методы в программировании: Учебник.- М.: ФОРУМ: ИНФРА-М, 2008.
Дополнительные источники
Фомин Г.П. Математические методы и модели в коммерческой деятельности: Учебник. – М.: Финансы и статистика, 2008.
Попов А.М. Экономико-математические методы и модели :учебник.-М.: Юрайт, 2012
Интернет-ресурсы
Единое информационно-образовательное пространство колледжа NetSchool. Форма доступа: http://sgtek.ru
Информационно-справочная система «В помощь студентам». Форма доступа: http://window.edu.ru
Информационно-справочная система. Форма доступа: [ Cкачайте файл, чтобы посмотреть ссылку ].
Информационно-справочная система. Форма доступа: [ Cкачайте файл, чтобы посмотреть ссылку ]
13PAGE 14715
13PAGE 14415
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
2
3
4
6
5
9
10
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
7
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
8
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
x4
x1
x2
x3
x5
X1
X2
X3
X4
X5
X6
X7
X1
X2
X3
X4
X5
X6
X7
X1
X2
X3
X4
X5
X6
X7
X1
X2
X3
X4
X5
X6
X7
(1)
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415- лучшая стратегия для игрока А – (А3)
(
(
(
(
(
(
(
(
A1
A2
B2
а12
а22
(
М
А1
А2
В1
а11
0
q2
q1
13 EMBED Equation.3 1415
верхняя граница игры - сколько может
самое меньшее проиграть игрок В.
q1 - вероятность выбора стратегии B1.
q2 - вероятность выбора стратегии B2.
а21
1
1
а12
выигрыш первого игрока, т.е. самое лучшее, как может поступить игрок А в наихудшей для него ситуации.
( - цена игры при максиминной стратегии игрока А.
p1 - вероятность выбора стратегии А1.
p2 - вероятность выбора стратегии А2.
нижняя граница игры - гарантированный
13 EMBED Equation.3 1415
Р1
Р2
0
а11
А1
В2
В1
М
(
а22
а21
А2
В2
В1
(
(
(
(
(
(
(
(
(
(
(
(
(
В1
A2
B2
(
В2
В1
0
Р2
Максимальное из минимальных значений ( соответствует чистым стратегиям А2 и В2:
13 EMBED Equation.3 1415 = (0;1), т.е. p1 = 0, p2 = 1.
1
А1
А1
1
В этом случае стратегия В2 – доминирующая и ее отбрасывают. Оптимальное решение игры – в чистых стратегиях
13 EMBED Equation.3 1415 = (0;1), т.е. p1 = 0, p2 = 1.
Р2
0
В1
В2
(
B1
A2
В2
(
(
(
(
(
13 EMBED Equation.3 1415
М
p1 = 0,4
(
(
А1
1
2p1 + 6p2 = (,
5p1 + 4p2 = (,
p1 + p2 = 1.
2p1 + 6p2 – 5p1 – 4p2 = 0:
2p2 – 3p1 = 0, p1 = 1 - p2:
5p2 = 3; p2 = 13 EMBED Equation.3 1415; p1 = 13 EMBED Equation.3 1415;
13 EMBED Equation.3 1415= (13 EMBED Equation.3 1415) = (0,4; 0,6);
( = 2p1 + 6p2 = 4,4.
13 EMBED Equation.3 1415 = (0;1), т.е. Р1 = 0, Р2 = 1.
p2 = 0,6
0
В1
В2
( = 4,4
B2
A2
В1
(
(
(
(
(
(
(
(
(
(
A1
B2
A2
(
A2
A1
0
q2 = 13 EMBED Equation.3 1415
2q1 + 5q2 = (,
6q1 + 4q2 = (,
q1 + q2 = 1.
13 EMBED Equation.3 1415= (13 EMBED Equation.3 1415) = (13 EMBED Equation.3 1415,13 EMBED Equation.3 1415).
1
B1
(
(
q1 = 1/5
М
13 EMBED Equation.3 1415
(
(
(
(
(
B1
Bn
B2
(
Bn
B2
0
Точка максимума М находится на пересечении стратегий В1 и В2, остальные отбрасываются, далее игра решается как задача 2 х 2.
1
B1
(
13 EMBED Equation.3 1415
(
(
A1
(
M
A2
p2
p1
(
(
(
(
(
A1
Am
A2
(
Am
A2
0
1
A1
(
13 EMBED Equation.3 1415
(
(
B1
(
M
B2
q2
q1
В1
В2
А1
a11
a12
А2
a21
a22
Am
аm1
аm2
(
(
(
(
(
В1
В3
A2
(
В2
10
0
1
A1
(
13 EMBED Equation.3 1415
(
B1
(
M
B2
p2
p1
В3
5
10p1 + 4p2 = (,
3p1 + 5p2 = (,
p1 + p2 = 1.
p1 = 13 EMBED Equation.3 1415; p2 = 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;1), т.е. Р1 = 0, Р2 = 1.
10q1 + 3q3 = (,
4q2 + 5q2 = (,
q2 + q3 = 1.
q2 = 13 EMBED Equation.3 1415; q3 = 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;1), т.е. Р1 = 0, Р2 = 1.
5
А2
q2
q3
A1
M
(
B2
(
13 EMBED Equation.3 1415
(
1
0
10
А1
(
B3
A2
(
(
(