Инфоурок Математика Другие методич. материалыМЕТОДИЧЕСКИЕ УКАЗАНИЯ по выполнению самостоятельной внеаудиторной работы по дисциплине «Математические методы» для студентов 3 курса (специальность Программирование в компьютерных системах)

МЕТОДИЧЕСКИЕ УКАЗАНИЯ по выполнению самостоятельной внеаудиторной работы по дисциплине «Математические методы» для студентов 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: Собрать характеристики моделей

 

Цель: научиться обобщать данных, работать с большим количеством информации.

Самостоятельная работа: индивидуальная домашняя работа

Форма контроля: проверка работы (таблицы с характеристиками моделей)

Виды заданий:

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 Построение простейших математических и статистических моделей

 

Цель: получить и закрепить навыки построения простейших математических и статистических моделей

Самостоятельная работа: индивидуальная домашняя работа

Форма контроля: проверка работы

 

Теоретический материал и методические указания к выполнению заданий

 

Математическая модель любой задачи линейного программирования включает в себя:

·         максимум или минимум целевой функции (критерий оптимальности);

·         систему ограничений в форме линейных уравнений и неравенств;

·         требование неотрицательности переменных.

Таким образом, экономико-математическая формулировка и модель общей задачи линейного программирования имеют следующий вид:

найти максимальное (минимальное) значение линейной целевой функции

при условиях-ограничениях:

где 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

при ограничениях:

 

 

Варианты заданий: 

 

1.     Малое предприятие арендовало минипекарню для произ­водства чебуреков и беляшей. Мощность пекарни позволяет вы­пускать в день не более 50 кг продукции. Ежедневный спрос на чебуреки не превышает 260 штук, а на беляши — 240 штук. Суточные запасы теста и мяса и расходы на производство каж­дой единицы продукции приведены в таблице. Определить оп­тимальный план ежедневного производства чебуреков и беля­шей, обеспечивающих максимальную выручку от продажи.

 

 

 

Расход на производство, кг/шт.

Суточные запасы сырья, кг

чебурека

беляша

Мясо

0,35

0,6

21

Тесто

0,65

0,3

22

Цена, руб-/кг

50,0

80,0

 

 

2.     Фирма производит два безалкогольных широко популяр­ных напитка «Колокольчик» и «Буратино». Для производства 1 л. «Колокольчика» требуется 0,02 ч работы оборудования, а для «Буратино» - 0,04 ч, а расход специального ингредиента на них составляет 0,01 кг и 0,04 кг на 1 л соответственно. Ежедневно в распоряжении фирмы 16 кг специального ингредиента и 24 ч работы оборудования. Доход от продажи 1 л «Колокольчика» составляет 0,25 руб., а «Буратино» - 0,35 руб.Определите ежедневный план производства напитков каждо­го вида, обеспечивающий максимальный доход от их продажи.

3.     Фирма производит для автомобилей запасные части типа А и В. Фонд рабочего времени составляет 5000 чел.-ч в неделю. Для производства одной детали типа А требуется 1 чел.-ч, а для производства одной детали типа В - 2 чел.-ч. Производственная мощность позволяет выпускать максимум 2500 деталей типа А и 2000 деталей типа В в неделю. Для производства детали типа А уходит 2 кг полимерного материала и 5 кг листового материала, а для производства одной детали типа В — 4 кг полимерного ма­териала и 3 кг листового металла. Еженедельные запасы каждо­го материала - по 10 000 кг. Общее число производимых деталей в течение одной недели должно составлять не менее 1500 штук. Определите, сколько деталей каждого вида следует произ­водить, чтобы обеспечить максимальный доход от продажи за неделю, если доход от продаж одной детали типа А и В состав­ляет соответственно 1,1 руб. и 1,5 руб.

4.     Фирма производит и продает столы и шкафы из древеси­ны хвойных и лиственных пород. Расход каждого вида в кубо­метрах на каждое изделие задан в таблице.

 

 

 

Расход древесины, м3

Цена изделия, тыс. руб.

хвойные

лиственные

Стол

0,2

0,3

0,8

Шкаф

0,1

0,05

1.6

Запасы древесины, м3

40

25

 

 

Определите оптимальное количество столов и шкафов, которое следует поставлять на продажу для получения максималь­ного дохода фирмы.

 

 

Самостоятельная работа №5: Решение простейших однокритериальных задач

 

Цель: научиться решать  простейшие однокритериальные задачи

Самостоятельная работа: Используя данные самостоятельной работы №2, решите задачи выбора оптимальной модели.

Форма контроля: проверка работы

 

Теоретический материал и методические указания к выполнению заданий

 

1.                   Решение простейших однокритериальных задач

В практической деятельности приходится рассматривать сложные объекты,  которые невозможно целостно сопоставить. В таких случаях выделяют существенные показатели этих объектов, а затем проводят Самостоятельная работа №авнение их значений. При этом первичная информация задаётся в виде таблицы значений показателей, где представлены множество Самостоятельная работа №авниваемых объектов a1, a2, a3,…, ai, …,am,  все наименования показателей P1, P2, P3, …, Pi, …, Pn  и значение этих показателей по каждому объекту p1(ai), p2(a2), p3(a3), …, pj(ai), …, pn(am).

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

Тогда можно ввести решающее правило: ai предпочтительнее aj, если F(ai)>F(aj).

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

 

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

 

Характеристики моделей ноутбуков

 

Модель

Процессор

ОЗУ

Жесткий диск

Экран

Цена

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

 

 

 

   После заполнения матрицы элементами Самостоятельная работа №авнения находим по строкам суммы баллов по каждому показателю:

где n- количество показателей, n=5.

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

   Затем определяем коэффициент весомости по формуле

Приоритет показателей распределяется по рангу, который пропорционален значению коэффициента весомости: чем больше его значение, тем выше ранг, причем наибольшему значению 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: Решение задач линейного программирования геометрическим методом

 

Цель: научиться решать  задачи линейного программирования геометрическим методом

Самостоятельная работа: индивидуальная домашняя работа

Форма контроля: проверка работы

 

Теоретический материал и методические указания к выполнению заданий

 

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

 

Двумерная задача линейного программирования – задача линейного программирования, количество переменных которой равно 2.

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

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

F = c1x1+c2x2 → max(min) при ограничениях на переменные

Самостоятельная работа №еди ограничений могут одновременно встречаться знаки ≥, ≤ и =. Коэффициенты aij, bi, cj (i = 1..m, j = 1,2) - любые действительные числа (возможно и 0).

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

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

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

 

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

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

 

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

Решение задачи линейного программирования графическим методом включает следующие этапы.

1. На плоскости Х1ОХ2 строят прямые, уравнения которых получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств.

2.  Находят полуплоскости, определяемые каждым из огра­ничений задачи.

3.  Строят многоугольник решений.

4. Строят векторN1, c2), который указывает направление возрастания целевой функции.

5. Строят начальную прямую целевой функции с1х1 + с2х2 =0 и затем передвигают ее в направлении вектора N до крайней угловой точки многоугольника решений. В результате находят точку, в которой целевая функция принимает максимальное значение, либо множество точек с одинаковым максимальным значением целевой функции, если начальная  прямая сливается с одной из сторон многоугольника решений, либо устанавливают неограниченность сверху функции на множестве планов.

6.  Определяют координаты точки максимум функции и вычисляют значение целевой функции в этой точке.

Минимальное значение линейной функции цели находится путем передвижения начальной прямой с1х1 + с2х2 = 0 в направлении, противоположном вектору N(c1,c2).

Замечание 1: В алгоритме решения пункты 4-6 можно выполнять следующим образом:

4.  Найти значение целевой функции в угловых точках многогранника решений.

5.  Точка, в которой функция принимает наибольшее значение и является точкой максимума.

 

Замечание 2: При решении двумерных задач линейного программирования возможны следующие ситуации (ОДР – область допустимых решений):

 

3.      Пример решения задачи ЛП графическим методом

Найдите максимум и минимум линейной функ­ции   

при условиях-ограничениях:

Решение. Построим на плоскости Х1ОХ2 многоугольник решений. Для этого в неравенствах системы ограничений и условиях неотрицательности переменных знаки неравенств заменим на знаки точных равенств.

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

Многоугольником решений задачи является пятиугольник АВСДЕ, координаты точек которого удовлетворяют условию неотрицательности переменных и неравенствам системы ограничений задачи.

Для нахождения точек экстремума построим начальную прямую F()=-2х1+4х2= 0 и вектор N(-2,4). Передвигая прямую F()=0 в направлении вектора N, найдем точку С, в которой начальная прямая принимает положение опорной прямой. Следовательно, в точке С целевая функция имеет максимальное значение. Так как точка С получена в результате пересечения прямых 1 и 2, то ее координаты удовлетворяют уравнениям этих прямых:

Решив систему уравнений, получим: х1 =3,4; х2 = 4,2; откуда найдем максимальное значение целевой функции Fmax() = -  2 • 3,4+ 4 • 4,2 =10.

По условию задачи начальная прямая параллельна прямой (2), так как коэффициенты при переменных x1, x2 пропорциональны: -2/-1 = 4/2 = 2. Следовательно, начальная прямая займет положение опорной прямой в точках В, С и в любой точке отрезка ВС, в которых F() принимает одно и то же максимальное значение. Для определения координат точки В решим систему двух линейных уравнений:

Максимальное значение целевой функции в точке В равно:

F() = -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, дающие максимум целевой функции  при ограничениях:

 

Геометрическое решение задачи

В системе координат Х1ОХ2 строим график линейной зависимости, полученной переходом от неравенств к равенствам:

  (1)

       (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:

х1

0

150

х2

0

-200

 

График данной линейной зависимости (F=0) перемещаем параллельно самому себе до вершины с максимальным значением целевой функции.

Получаем точку А, координаты которой и соответствуют оптимальному решению задачи.

Найдем координаты т.А. В ней пересекаются линии (1), (3)

Таким образом, А(207,5; 48,75).

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

 

Вывод:Продукции первого вида А должно быть произведено  207.5ед., второго вида – 148.75 ед.  Максимальная выручка от реализации продукции составит 1952.5 ден.ед.

 

 

Варианты заданий

 

Задача 1. Решить графическим методом следующую ЗЛП:

Z  =  3x1 + 5x→  min

x1 + x2 ≤ 5

3x1 - x2 ≤ 3

x1 ≥0,  x2 ≥0

Задача 2. Решить графическим методом следующую ЗЛП:

Z  =  3x1 + 5x→  max

x1 + x2 ≤ 5

3x1 - x2 ≤ 3

x1 ≥0,  x2 ≥0

Задача 3. Решить графическим методом следующую ЗЛП:

Z  =  2x1 + 2x→  min

x1 + 3x2 ≥ 3

-2x1 + x2 ≤ 2

x1 + x2 ≤ 5

x1 ≥0,  x2 ≥0

Задача 4. Решить графическим методом следующую ЗЛП:

Z  =  2x1 + 2x→  max

x1 + 3x2 ≥ 3

-2x1 + x2 ≤ 2

x1 + x2 ≤ 5

x1 ≥0,  x2 ≥0

 

 

Самостоятельная работа №8: Формирование и усвоение содержания теоретического материала, используя информационные образовательные ресурсы (онлайн-решение)

 

Цель: научиться использовать информационные образовательные ресурсы для самоконтроля по изучаемой теме

Самостоятельная работа: работа с Internet- ресурсами

Форма контроля: проверка работы

 

 

Самостоятельная работа №9: Решение задач линейного программирования симплекс–методом

 

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

Самостоятельная работа: индивидуальная домашняя работа

Форма контроля: проверка работы

 

Теоретический материал и методические указания к выполнению заданий

 

1.      Симплекс-метод линейного программирования

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

Впервые симплексный метод был предложен американским ученым Дж. Данцингом в 1949 г., однако еще в 1939 г. идеи метода были разработаны российским математиком Л.В. Канто­ровичем.

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

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

В этом случае вычислительная процедура может быть представлена в следующей последовательности.

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

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

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

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

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

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

Коммерческое предприятие реализует п товарных групп, располагая т ограниченными материально-денежными ресурса­ми bi > 0 (i = 1,…,m). Известны расходы ресурсов каждого i-вида на реализацию единицы товара по каждой группе, представленной в виде матрицы А = (аij), и прибыль cj, получаемая предприятием от реализации единицы товара j группы. Надо определить объем и структуру товарооборота xj (j = 1,…,n) при которых прибыль коммерческого предприятия была бы максимальной.

Математическую модель задачи запишем следующим образом.

Определить вектор = 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 вида в количестве, полученном в столбце свободных членов симплексной таблицы.

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

 

2.      Пример решения задачи симплекс-методом

 

Коммерческое предприятие, располагающее материально-денежными ресурсами, реализует три группы товаров А, В, С. Плановые нормативы затрат ресурсов на 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

 

Решение: Запишем математическую модель задачи.

Определим вектор , который удовлетворяет условиям

и обеспечивает максимальное значение целевой функции

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных x4, x5, x6:

Матрица коэффициентов A=(aij) этой системы у равнений имеет следующий вид:

Векторы  - линейно независимы, так как определитель, составленный из компонент этих векторов, отличен от нуля. Следовательно, соответствующие этим векторам переменные x4, x5, x6 являются базисными и в этой задаче определяют объемы неиспользованных ресурсов.

Решим систему уравнений относительно базисных переменных.

Функцию цели запишем в виде уравнения:

Полагая, что свободные переменные x1=0, x2=0, x3=0, получим первый опорный план  , в котором базисные переменные x4=1100, x5=120, x6=8000. Следовательно, товары не продаются, доход равен нулю, а ресурсы не используются. Полученный первый опорный план запишем в симплексную таблицу.

План

Базисные переменные

Значения базисных переменных

Значение коэффициентов при

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

Индексная строка

0

-3

-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

Индексная строка

27500

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

 

Индексная строка

27625

0

0

5,75

23,75

12,5

0

 

 

Первый опорный план неоптимальный, так как в индексной строке находятся отрицательные коэффициенты: -3, -5, -4.

За ведущий столбец выберем столбец, соответствующий переменной x2, так как, Самостоятельная работа №авнивая по модулю, имеем: |-5|>{|-3|,|-4|}.

Вычислим значения di по строкам как частное от деления  и из них выберем наименьшее:

Следовательно, первая строка является ведущей.

Разрешающий элемент равен 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 находится из выражения:

Элементы строки определяются аналогично:

                   

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

Выполняя последовательно все этапы алгоритма, формулируем план II.

На третьей итерации табл. получаем план III, который является оптимальным, так как все коэффициенты в индексной строке  0.

Оптимальный план можно записать так:

Следовательно, необходимо продавать товаров первой группы А 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 + x+ 2x3 →  max

3x1 + 2x2 + x3 ≤ 6

x1 + x2 + 2 x3 ≤ 4

x1 ≥0,  x2 ≥0, x3 ≥0

Задача 2. Решить ЗЛП симплексным методом.

 Z  =  5x1 + 4x- x3 →  max

x1 - 2x2 + 2x3  20

x1 + 4x2 -  x3 ≤ 16

x1 ≥0,  x2 ≥0, x3 ≥0

Задача 2. Решить ЗЛП симплексным методом.

Z  =  4x1 - x+ 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). Требуется составить такой план перевозок, при котором весь груз из пунктов отправления вывозится, и запросы всех пунктов потребления удовлетворяются (закрытая модель), т. е:

а суммарные транспортные расходы минимальны.

 

Математическая модель транспортной задачи

 

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

Допустимый план, будем называть опорным, если в нем отличны от нуля не более m+n-1 базисных перевозок, а остальные перевозки равны 0.

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

 

2.Методы решения транспортных задач

 

Так как транспортная задача является задачей линейного программирования, то её можно решать симплекс-методом, но в силу своей особенности её можно решить гораздо проще.

Условия задачи удобно располагать в таблице, вписывая в ячейки количество перевозимого груза из Аi в Bj груза Xij ≥ 0, а в маленькие клетки – соответствующие тарифы Cij.

Затем решение задачи разбивается на два этапа:

 

1.      Определение опорного плана.

2.      Нахождение оптимального решения путем последовательных операций.

 

1.                       Найдем вначале допустимое (опорное) решение транспортной задачи. Это решение можно найти, используя метод "северо-западного угла" или метод "минимального элемента".

 

Метод северо-западного угла (диагональный)

 

Сущность метода заключается в том, что на каждом шаге заполняется левая верхняя (северо-западная) клетка оставшейся части таблицы, причем максимально возможным числом: либо полностью выносится груз из А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

Как следует спланировать перевозку, чтобы её стоимость была минимальной?

 

Решение: Построим опорный план.

Исходная транспортная таблица:

 

Построение второй транспортной таблицы

 

Магазин В1 подал заявку на 20 кроватей, но со склада А1 мы можем перевести 15 кроватей, ещё 5 кроватей мы перевезём со склада А2. Спрос для магазина В1 удовлетворён. Рассмотрим магазин В2. В него необходимо доставить 12 кроватей - доставим их со склада А2.

На складе А2 осталось 8 кроватей. Выделим из них пять для магазина В3. На складе А2 осталось 3 кровати. Выделим их на магазин В3, но потребности магазина ещё не удовлетворены, поэтому выделим ему со склада А3 ещё пять кроватей. Осталось 15 кроватей, столько, сколько требуется в магазин В5.

Построенный план является допустимым, так как все заявки удовлетворены, все запасы израсходованы.

 

Проверим, является ли полученный план опорным: количество ячеек с ненулевыми перевозками равно 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

 

Метод наименьшего элемента

 

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

 

Пример: см.  предыдущий пример

Решение: Построим опорный план.

Исходная транспортная таблица:

 

Построение второй транспортной таблицы

 

Находим в таблице наименьшую стоимость перевозки – это 0 в клетке A1B2. Записываем в этой клетке значение 12 (наименьшее из сумм по строке и столбцу).

Теперь вычеркиваем второй столбец, уменьшив сумму в первой строке на 12.

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

Вычеркиваем первую строку.

Выбираем ячейку A3B3, присваиваем ей значение 5. Вычеркиваем третий столбец. Сумму по третьей строке заменяем на 15.

Выбираем ячейку A2B5, записываем в ней 15, уменьшаем вторую строку на 15 и вычеркиваем пятый столбец.

Выбираем ячейку A3B1, присваиваем ей 15. Уменьшаем первый столбец на 15 и вычеркиваем третью строку.

Ячейке A2B1 присваиваем 2 и вычеркиваем первый столбец. Сумму по второй строке заменяем на 8.

Ячейке A2B4 присваиваем 8 и вычеркиваем четвертый столбец.

Опорный план построен.

Х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.Метод потенциалов решения транспортных задач

                             (1)

Соотношения (1) определяют систему из m+n-1 линейных уравнений с m+n известными, имеющую бесчисленное множество решений; для её определённости одному неизвестному присваивают произвольное значение (обычно альфа равное 0), тогда все остальные неизвестные определяются однозначно.

 

Метод потенциалов:

 

Введем строку потенциалов ui и столбец потенциалов vj. Полагая, что u1=0, а остальные ui и vj найдем так, чтобы

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

б) для незаполненных ячеек выполнялись равенства

Критерий оптимальности

 

Если известны потенциалы решения Х0 транспортной задачи и для всех незаполненных ячеек выполняются условия то Х0 является оптимальным планом транспортной задачи.

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

 

Цикл перерасчёта таблицы – это последовательность ячеек, удовлетворяющая условиям:

1.      Одна ячейка пустая, все остальные занятые.

2.      Любые две соседние ячейки находятся в одной строке или в одном столбце.

 

Пустой ячейке присваивают знак "+", остальным – поочерёдно знаки "–" и "+".

Для перераспределения плана перевозок с помощью цикла перерасчёта сначала находят незаполненную ячейку (r, s), в которой αr+βs > Crs, и строят соответствующий цикл; затем в минусовых клетках находят число X = min(Xij). Далее составляют новую таблицу по следующему правилу:

3.      В плюсовых клетках добавляем Х.

4.      Из минусовых клеток вычитаем Х.

5.      Все остальные клетки вне цикла остаются без изменения.

 

Получим новую таблицу, дающую новое решение Х, такое, что F (X1) ≤ F (X0); оно снова проверяется на оптимальность через конечное число шагов, обязательно найдем оптимальный план транспортной задачи, ибо он всегда существует.

 

Найдём оптимальный план для рассмотренной выше задачи. В качестве опорного плана возьмем план, полученный с помощью метода  "минимального элемента" Х11 = 3, Х12 = 12, Х21 = 2, Х24 = 8, Х25 = 15, Х31 = 15, Х33 = 5. Все остальные элементы равны 0.

 

Так как у нас получились отрицательные значения, то полученный план не является оптимальным. Выберем ячейку для пересчета A2B2. Получим:

X = min(2, 12) = 2

Строим следующую транспортную таблицу.

Проверим полученный план на оптимальность с помощью метода потенциалов.

Т.к. есть отрицательные оценки пустых ячеек, то построенный план не является оптимальным, следовательно, производим пересчет. Выберем ячейку A3B5.

 

X = min(15, 10, 15) = 10, значит вычитать и прибавлять в ячейках, будем 10.

Строим следующую транспортную таблицу.

 

Проверим построенный план на оптимальность.

Т.к. отрицательных оценок пустых ячеек нет, то полученный план является оптимальным. Х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: Решение задач нелинейного программирования графическим методом и методом множителей Лагранжа

 

Цель: научиться решать задачи нелинейного программирования графическим методом и методом множителей Лагранжа

Самостоятельная работа: индивидуальное домашнее задание

Форма контроля: проверка работы

 

Теоретический материал и методические указания к выполнению заданий

 

1.      Нелинейное программирование

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

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

В самом общем виде классификация представлена в таблице.

 

Вид F(x)

Вид функции ограничений

Число переменных

Название задачи

Нелинейная

Отсутствуют

1

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

Нелинейная

Отсутствуют

Более 1

Безусловная многопараметрическая оптимизация

Нелинейная или линейная

Нелинейные или линейные

Более 1

Условная нелинейная оптимизация

 

Общих способов решения, аналогичных симплекс-методу линейного программирования, для нелинейного программирования не существует.

В каждом конкретном случае способ выбирается в зависимости от вида функции F(x).

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

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

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

2.        Задачи безусловной однопараметрической оптимизации

Для нахождения максимума и минимума функции F(x) строится её график. Для построения графика необходимо исследовать функцию. Ниже приведена схема исследования графика:

1.      Нахождение области значения функции.

2.      Нахождение области определения.

3.      Исследование на четность и нечетность.

4.      Исследование на периодичность.

5.      Нахождение точек пересечения с осями, нахождение интервалов знакопостоянства функции (отрицательна, положительна).

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

7.      Нахождение второй производной и промежутков выпуклости и вогнутости.

8.      Нахождение точек разрыва и асимптот (если такие есть).

9.      Несколько точек для контроля.

 

Пример

Построить график функции у = х2+2х-3.

Решение

1.      Функция определена на интервале от минус бесконечности до плюс бесконечности. Точек разрыва нет.

2.      Имеем f(-x) = (-x)2+2(-x)-3 = x2-2x-3. Функция не является ни четной, ни нечетной, так как f(-x) не равно f(x) и f(x) не равно -f(x).

3.      Найдем точки пересечения графика функции с осями координат. Если у = 0, то х2+2х-3 = 0, откуда х1 = -3, х2 = 1. Значит, кривая пересекает ось абсцисс в точках (-3, 0) и (1, 0). При х = 0, у = -3 (из равенства у = х2+2х-3), т. е. кривая пересекает ось ординат в точке (0, -3).

4.      Найдем критические точки функции. Имеем у' = 2х+2, 2х+2 = 0, 2(х+1) = 0, х = -1.

5.      Находим интервалы знакопостоянства функции.

f(-1) = fmin = -4.

6.      Находим вторую производную: у" = 2, т. е. f" > 0. Следовательно, кривая вогнута на всей области определения и не имеет точек перегиба.

7.      Построение графика.

Численный метод решения задачи – это определенная последовательность операций над числами.

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

При исследовании функции делаем вывод: рассматриваемая функция должна быть дифференцируема.

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

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

 

3.      Экстремумы функции двух переменных

 

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

Максимум или минимум функции называется ее экстремумом. Точка, в которой достигается экстремум, называется точкой экстремума.

Точки экстремума функции двух переменных  надо искать Самостоятельная работа №еди тех точек, лежащих внутри области ее определения, координаты которых удовлетворяют системе

                                             (1.2)

Точки, удовлетворяющие такой системе уравнений, называются стационарными.

Но не всякая такая точка действительно будет точкой максимума или минимума. Каждую стационарную точку надо специальным образом проверить. Для функции двух переменных проверка стационарной точки  требует:

1) нахождения в этой точке значений вторых производных:

,

которые обозначим буквами , ,  соответственно;

2) определения знака :

если , то в стационарной точке  нет экстремума;

если , то экстремум есть, причем , если  и , если ;

если , то ничего сказать нельзя – требуется дополнительное исследование.

 

Пример. Найти для функции , точки максимума и минимума (если они существуют).

Решение.

1) Ищем частные производные:

   .

2) Для нахождения стационарных точек функции составим и решим систему (1.2). В нашем случае система имеет вид

Первое уравнение выполняется в двух случаях: либо когда , либо когда  или . В первом случае второе уравнение после подстановки нуля вместо  приобретает вид  и имеет решения  и . Таким образом, в данном случае решениями системы будут пары чисел: ,  и , , а стационарными точками функции  – точки  и .

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

3) Следующий шаг – проверка каждой стационарной точки на экстремум. Найдем сначала формулы, выражающие вторые производные функции :

 .

Приступим теперь к проверке  точки , для чего найдем соответствующие ей числа A, B, C:

, , .

 и, значит, в  экстремума нет.

Аналогично проверяем точку :

, ,.

 и, значит, в  экстремума нет.

Точно также нет экстремума и в точке , так как в ней , ,  и .

Наконец, для точки  , ,  и . Следовательно, в точке  экстремум есть и, согласно теории, это максимум, так как . При этом значение функции в точке максимума равно .

 

4.      Условный экстремум. Функция Лагранжа

 

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

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

Необходимые условия экстремума функции Лагранжа имеют вид

Из этой системы трех уравнений можно найти неизвестные х, у, .

Геометрический метод:

Для того, чтобы найти наибольшее и наименьшее значения функции в замкнутой области, надо:

1) найти стационарные точки, расположенные в данной области, и вычислить значение функции в этих точках;

2) найти наибольшее и наименьшее значения функции на линиях, образующих границу области;

3) из всех найденных значений выбрать наибольшее и наименьшее значения.

Пример:

Найти экстремум функции  при условии, что х и у связаны уравнением .

Решение: Рассмотрим функцию Лагранжа . Имеем ,    .

Из системы уравнений (необходимые условия экстремума)

         находим

Нетрудно видеть, что в точке (5/4, 5/6) функция  достигает наибольшего значения .

 

Варианты заданий

 

Задание 1. Найдите точки экстремума заданной функции:

1.    

2.    

3.    

4.    

5.    

 

Задание 2. Найдите точки экстремума заданной функции:

1.     .

2.     5. .

3.     6. .

4.     7. .

5.     8.

 

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

Вариант

1

2

3

4

5

a

1

2

3

4

5

b

1

2

4

6

8

 

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

Вариант

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 переменными решается серия задач с небольшим числом, а чаще с одной переменной. Сам же вычислительный процесс производится на основе метода последовательных приближений в два круга:

1.                 От последнего шага к первому.

2.                 От первого шага к последнему или же наоборот, в зависимости от исходных данных.

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

Нельзя получить оптимальное значение целевой функции 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

 

3 шаг: Денежные средства вкладываются в четвертый, третий (2 шаг) и второй  проекты.

u

Прибыль от внедрения

2 шаг

f2(u)

8

55

35

16

94

76

24

108

120

32

135

135

40

175

158

 

4 шаг: Денежные средства вкладываются в четвертый, третий, второй (3 шаг) и первый  проекты.

u

Прибыль от внедрения

3 шаг

f1(u)

8

55

32

16

94

68

24

131

115

32

175

134

40

214

147

 

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, обеспечивающий наименьшие транспортные расходы.

Рис. 1. Модель транспортной сети.

 

В задаче имеется ограничение – двигаться по изображенным на схеме маршрутом можно только слева на право, т.е. попав, например, в пункт 7, мы имеем право переместиться только в пункт 10 и не можем возвратиться обратно в 5 или 6. Это особенность транспортной сети дает право отнести каждый из 10 пунктов к одному из поясов. Будем считать, что пункт принадлежит k-му поясу, если из него попасть в конечный пункт ровно за k шагов, т.е. заездом ровно в (k-1) – й промежуточный пункт. Таким образом, пункты 7, 8 и 9 принадлежат к первому поясу, 5 и 6 ко второму, 2, 3 и 4 к третьему и 1– к четвертому. Тогда на k-м шаге будем находить оптимальные маршруты перевозки груза из пунктов в k-го пояса до конечного пункта. Оптимизацию будем производить с конца процесса, и потому, дойдя до k-го шага, неизвестно, в каком из пунктов k-го пояса окажется груз, перевозимый из первого пункта.

Введем обозначения:

k – номер шага ()

i – пункт, из которого осуществляются перевозки()

j – пункт, в который доставляется груз()

 – стоимость перевозки груза из пункта i в пункт j.

 – минимальные затраты на перевозку груза на k-м шаге решения задачи из пункта i до конечного пункта.

Очевидно, что минимум затрат на перевозку груза из пунктов k-го пояса до пункта 10 будет зависеть от того, в каком месте этого пояса мы оказались. Номер i пункта, принадлежащего k-му поясу будет являться переменной состояния системы на k-м шаге. Поскольку оптимизация осуществляется с конца процесса, то, находясь в некотором пункте i k-го пояса, принимается решение о перемещении груза в один из пунктов (k – 1)-го пояса, а направление дальнейшего движения известно из предыдущих шагов. Номер j пункта (k-1)-го пояса будет переменной управления на k-м шаге.

Для первого шага управления (k=1) функция Беллмана представляет собой минимальные затраты на перевозку груза из пунктов 1-го пояса в конечный пункт, т.е. . Для последующих шагов затраты складываются из двух слагаемых – стоимость перевозки груза  из пункта i k-го пояса в пункт j (k–1)-го пояса и минимально возможных затрат на перевозку из пункта j до конечного пункта, т.е. .

Таким образом, функциональное уравнение Беллмана будет иметь вид

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

На четвертом шаге попадаем на 4-ый пояс и состояние системы становится определенным i=1. Функция  представляет собой минимально возможные затраты по перемещению груза из пункта 1 в 10. Оптимальный маршрут определяется в результате анализа всех шагов в обратном порядке, а выбор некоторого управления j на k-м шаге приводит к тому, что состояние системы на (k-1)-м шаге становится определенным.

Пример. Решим сформулированную задачу, исходные данные которой приведены на рис. 1.

I этап. Условная оптимизация.

1-й шаг. k=1 .

На первом шаге в пункт 10 груз может быть доставлен из пунктов 7, 8 или 9.

Таблица 1.

i                           j

10

7

7

7

10

8

9

9

10

9

11

11

10

 

2-й шаг. k=2.  Функциональное уравнение на втором шаге принимает вид

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

Таблица 2.

i                           j

7

8

9

5

8+7

6+9

15

7; 8

6

5+7

4+11

12

7

 

3-й шаг. k=3. 

Таблица 3.

i                     j

5

6

2

4+15

19

5

3

3+12

15

6

4

9+12

21

6

 

4-й шаг. k=4.

Таблица 4.

i                           j

2

3

4

1

7+19

5+15

6+21

20

3

 

II этап. Безусловная оптимизация.

На этапе условной оптимизации получено, что минимальные затраты на перевозку груза из пункта 1 в пункт 10 составляют . Данный результат достигается при движении груза их пункта 1 в пункт 3. По данным таблицы 3, из пункта 3 необходимо двигаться в пункт 6, затем – в пункт 7 и из него – в конечный пункт. Таким образом, оптимальный маршрут доставки груза:  (на рис. Он показан двойными стрелками).

 

Рис. 2. Транспортная сеть с оптимальным маршрутом.

 

Варианты заданий: 

 

Задача. На данной сети дорог имеется несколько маршрутов, по которым можно доставить груз из пункта 1 в пункт 10.


 

Известны стоимости  перевозки единицы груза между пунктами сети (данные приведены в таблице). Требуется:

1.      методом динамического программирования найти на сети наиболее экономный маршрут доставки груза из пункта 1 в пункт 10 и соответствующие ему затраты;

2.      выписать оптимальные маршруты перевозки груза из всех остальных пунктов сети в пункт 10 и указать отвечающие им минимальные затраты на доставку.

 

Тариф

 

1.                   

7

3

5

2

7

9

3

1

8

4

5

2

6

1

9

4

3

8

2.                   

4

8

4

6

1

9

3

5

4

8

2

7

4

9

6

1

7

2

3.                   

9

2

5

3

7

4

6

8

1

3

5

8

7

1

4

5

9

5

4.                   

1

6

2

5

3

6

8

4

7

2

9

5

3

6

1

4

6

1

 

 

Самостоятельная работа №20: Подготовка сообщения на тему «Графы. Практическое приложения графов»

 

Цель: получить представление о графах, их практических приложениях Самостоятельная работа: работа с литературой

Форма контроля: сообщение на уроке

 

 

Самостоятельная работа №21: Нахождение кратчайших путей в графе. Решение задачи о максимальном потоке

 

Цель: научиться решать задачи динамического программирования: Нахождение кратчайших путей в графе. Решение задачи о максимальном потоке

Самостоятельная работа: индивидуальное домашнее задание

Форма контроля: проверка работы

 

Теоретический материал и методические указания к выполнению заданий

 

1.      Задача о нахождении кратчайшего пути

 

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

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

Данная задача может быть разбита на две:

·         для начальной заданной вершины найти все кратчайшие пути от этой вершины к другим;

·         найти кратчайшие пути между всеми парами вершин.

·          

2.      Алгоритм Дейкстры решения задачи

 

Алгоритм Дейкстрыалгоритм поиска кратчайшего пути во взвешенном графе между двумя заданными вершинами s и t  при неотрицательных весах всех дуг.

Пусть  s - начальная вершина пути,  t - конечная.

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

 Кроме l(xi), с вершинами графа связывается еще одна метка Q(xi).На каждой итерации Q(xi) является номером вершины, предшествующей хi в кратчайшем   (s, xi)-пути.

После того, как последняя вершина  t получила постоянную метку, с помощью меток Q(x) легко указать последовательность вершин, составляющих кратчайший (S,t)-путь:

                                          (s..., Qn(t)..., Q(Q(t)), Q(t),t),

                                           Qn(t)= Q(Q(...Q(t))   (n раз).

Перед началом работы алгоритма начальная вершина s имеет постоянную метку l(s)=0, а метки всех остальных вершин равны бесконечности ()  и являются временными. Обозначим через p последнюю из вершин, получивших постоянную метку.

 

Алгоритм Дейкстры включает следующие шаги:

1. Положить l(s)=0 и считать эту метку постоянной. Положить l(xi)= для всех  xi ¹ s, и считать эти метки временными.  p = s.

2. Обновление пометок.  Для всех вершин xi Î Г(p), пометки которых временные, изменить пометки в соответствии с правилом:

                                         l(xi)=min { l(xi), l(p) +w(p, xi) }.

Если l(xi)> l(p) +w(p, xi), то  Q(xi) = p.

3. Если l(xi)=   для всех вершин xi, пометки которых временные, то в исходном графе отсутствуют пути из вершины s в вершины с временными метками. Останов алгоритма. В противном случае переход к шагу 4.

4. Превращение пометок в постоянные.  Самостоятельная работа №еди всех вершин с временными метками найти такую вершину xi* , для которой l(xi*) = minl(xi) (метка минимальная) и считать эту пометку постоянной. Положить p=xi*.  Пометку Q(xi*) также считать постоянной.

5. Если p ¹ t, перейти к шагу 2, а если p = t, то l(p) - длина кратчайшего пути из s в t.

После определения длины кратчайшего пути сам кратчайший путь восстанавливается по постоянным меткам Q(xi).

 

3.      Пример решения задачи

 

Для взвешенного орграфа найти кратчайший путь из вершины s в вершину t.

 

1. Помечаем в соответствии с алгоритмом вершины графа:

l(s) = 0 ,

l(a) = ,

l(b) = ,

l(c) = ,

l(d) = ,

l(t) = .

Вершине s приписываем постоянную пометку, т.е. p = s.

 

2. Из вершины s помечаем остальные вершины:

l(a) = min {, 0 + 4} = 4,

l(b) = min {, 0 + 7} = 7, 

l(c) = min {, 0 + 3} = 3,

l(d) = ,

l(t) = .

У вершин a, b, с уменьшились пометки, следовательно Q(a) = s, Q(b) = s, Q(c) = s.

Вершине c приписываем постоянную пометку, т.е. p = c. Пометка Q(с)=s также становится постоянной.

 

3. Из вершины c помечаем остальные вершины:

l(a) = min {4,  3 + } = 4,

l(b) = min {7,  3 + } = 7,

l(d) = min {,  3 + 3} = 6,

l(t) = .

У вершины d уменьшилась пометка, следовательно Q(d) = c.

Вершине a приписываем постоянную пометку, т.е. p = a. Пометка Q(a)=s становится постоянной.

 

4. Из вершины а помечаем остальные вершины:

l(b) = min {7,  4 + 4} = 7,

l(d) = min {6,  4 + 3} = 6,

l(t) = .

Вершине d приписываем постоянную пометку, т.е. p = d.. Пометка Q(d)=c становится постоянной.

 

5. Из вершины d помечаем остальные вершины:

l(b) = min {7,  6 + } = 7,

l(t) = min {,  6 + 2} = 8,

У вершины t уменьшилась пометка, следовательно Q(t) = d.

Вершине b приписываем постоянную пометку, т.е. p=b. Пометка Q(b)=s становится постоянной.

 

6. Из вершины b помечаем вершину t:

l(t) = min {8, 7 + 2} = 8.

Метки l(t) и Q(t)=d становятся постоянными.

 

7. Восстанавливаем по меткам Q  кратчайший путь из s в t:

Путь scdt  длиной 8.                                                                    

 

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

 

1.      Основные понятия

 

Рассмотрим граф G=(X,U), называемый в дальнейшем сетью. Пусть каждой дуге (xi, xj) сопоставлено положительное число cij , называемое пропускной способностью дуги. В сети выделяют два специальных узла, один из них называют источником (обозначим его через s), другой – стоком (обозначим его через t). Множество неотрицательных чисел fij , определенных на дугах (xi,xj), называют потоками в дугах, если выполняются следующие условия: 

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

                               

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

 

2.      Задача об определении максимального потока

 

Рассмотрим задачу об определении максимального потока, протекающего от некоторой вершины S графа (источника) к некоторой вершине t (стоку).

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

 

Требуется определить максимальный поток из Р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. Для любого другого узла поступающий поток численно равен исходящему потоку из того же узла. Схема приведена ниже.

 

 

Варианты заданий:

 

  1. Определить кратчайший путь от вершины s до вершины t с использованием алгоритма Дейкстры.

  1. Определить максимальный поток в сети с использованием алгоритма Форда-Фалкерсона.

 

 

Самостоятельная работа №22: Решение задач на графах

 

Цель: научиться решать задачи на графах

Самостоятельная работа: индивидуальное домашнее задание

Форма контроля: проверка работы

 

Теоретический материал и методические указания к выполнению заданий

 

Метрические характеристики графов

 

В теории графов применяются:

 

1.                 Матрица инцинденций. Это матрица А с n строками, соответствующими вершинам, и m столбцами, соответствующими рёбрам. Для ориентированного графа столбец, соответствующий дуге (х,y) содержит -1 в строке, соответствующей вершине х и 1 в строке, соответствующей вершине у. Во всех остальных – 0. Петлю, т. е. дугу (х,х) можно представлять иным значением в строке х, например, 2. Если граф неориентированный, то столбец, соответствующий ребру (х,у) содержит 1, соответствующие х и у – нули во всех остальных строках.

 

2.                 Матрица смежности. Это матрица n*n где n – число вершин, где bij = 1, если существует ребро, идущее из вершины х в вершину у и bij = 0 в противном случае.

3.                 Пусть G=(X,U) - связный граф, а  - две его несовпадающие вершины. Длина кратчайшего  маршрута, соединяющего вершины  (пути из ) называется расстоянием между вершинами  и обозначается . Положим , если вершины  не соединены маршрутом (путем). Расстояние  удовлетворяет следующим аксиомам:

1) ;

2) ;

3)  тогда и только тогда, когда ;

4)  для симметрических графов;

5)  (неравенство треугольника).

Расстояние для графа G удобно задавать матрицей расстояний. Матрицей расстояний графа с n вершинами называется квадратная матрица D порядка n, элементы которой определяются следующим образом:

Матрицу расстояний можно определить

4.      Для фиксированной вершины  величина

называется эксцентриситетом (отклоненностью) вершины .

5.      Максимальный Самостоятельная работа №еди эксцентриситетов вершин называется диаметром графа G и обозначается  diam (G):

6.      Минимальный из эксцентриситетов вершин связного графа называется его радиусом и обозначается через r(G):

7.      Вершина, имеющая минимальный эксцентриситет, называется центром графа.

8.      Для вершины  число  называется передаточным числом.

9.      Вершина графа, которой соответствует минимальное передаточное число

  

называется медианой графа. Центров и медиан в графе может быть несколько.

 

 

 

 

 

 

 

 


Рис. 1

 

Пример. Для графа, изображенного на рис.1 метрические характеристики определяются следующим образом:

 

Радиус графа равен 1, диаметр равен 2. Центр графа - вершина ; Медиана графа - вершина .

 

Варианты заданий:

 

Задание 1.Определить метрические характеристики графа.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Самостоятельная работа №23: Подготовка сообщения «Колмогоров А.Н»

 

Цель: получить представление о математике А.н.Колмогорове, познакомиться с его математическими трудами

 Самостоятельная работа: работа с литературой

Форма контроля: сообщение на уроке

 

 

Самостоятельная работа №24: Подготовка сообщения «СМО»

 

Цель: получить представление о СМО, их видах и основных характеристиках

Самостоятельная работа: работа с литературой

Форма контроля: сообщение на уроке

 

Самостоятельная работа №25: Составление систем уравнений Колмогорова

 

Цель: научиться составлять системы уравнений Колмогорова

Самостоятельная работа: индивидуальное домашнее задание

Форма контроля: проверка работы

 

Теоретический материал и методические указания к выполнению заданий

 

Уравнения Колмогорова А.Н.»

 

1.     Финальные вероятности состояний

 

Будем рассматривать марковские процессы с дискретными состояниями и непрерывным временем.

 

Пример 1 : Техническое устройство состоит из трёх узлов и в любой момент времени может находиться в одном из восьми состояний (рис. 1).

 

Возможные состояния устройства таковы:

S0 — все три узла исправны;

S1— первый узел неисправен, второй и третий исправны;

S2 — второй узел неисправен, первый и третий исправны;

S3 — третий узел неисправен, первый и второй исправны;

S4 — первый и третий узлы неисправны, второй исправен;

S5 — второй и третий узлы неисправны, первый исправен;

S6 — первый и второй узлы неисправны, третий исправен;

S7 —  все три узла неисправны.

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

Тогда  и   — интенсивности потоков отказов соответственно первого, второго и третьего узлов, а  и  — соответственно интенсивности потоков возвратов (ремонтов) узлов.

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

На основе построенного размеченного графа (см. рис. 1) создадим математическую модель.

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

                                       (1)

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

Определим вероятность первого случая — устройство остается в состоянии S1. В момент времени t устройство было в состоянии S1 с вероятностью p1(t). За время t устройство не перейдет в любое из состояний S0, S4  или S6. Суммарный поток событий, который может вывести устройство из состояния  S1, будет равен l2 +l3+m1. Каждый из этих потоков событий простейший, поэтому и суммарный поток также будет простейшим (все три свойства стационарности, ординарности и отсутствие последействия сохраняются).

Вероятность того, что устройство выйдет из состояния S1  будет равна p1(t) (l2 +l3+m1 ) t, а вероятность того, что останется в состоянии  S1p1(t) [1 — (l2 +l3+m1) t].

Теперь определим вероятность перехода устройства за время в t состояние S1 из состояний S0, S4 или S6.

Для S4 — p4(t) tm3;

Для  S4 — p6(t) tm2;

Для S4 p0(t) tl1.;

Таким образом, вероятность нахождения устройства в состоянии S> будет равна:

p1(t+t)= p1(t) [1-(m1+l2 +l3 )t]+ p0(t)l1t+ p4(t) m3t + p6(t) m2 t.

Выполним преобразования:

p1(t+t)= p1(t) (m1+l2 +l3 )t+ p0(t)l1t+ p4(t) m3t + p6(t) m2 t;

p1(t+t)- p1(t) = p0(t)l1t+ p4(t)m3t+ p6(t)m2t-(m1+l2 +l3) p1(t) t;

l1 p0(t)+ m3 p4(t) +m2 p6(t)-(m1+l2 +l3) p1(t) .

Устремив t  к нулю, получим:

l1 p0(t)+ m3 p4(t) +m2 p6(t)-(m1+l2 +l3) p1(t)

или l1 p0+ m3 p4(t) +m2 p6-(m1+l2 +l3) p1. (8.2)

Выполнив аналогичные действия, получим семь дифференциальных уравнений:

 

Эта система дифференциальных уравнений называется системой уравнений Колмогорова. Имеем систему из восьми линейных дифференциальных уравнений с восемью неизвестными. Известно, что сумма всех вероятностей равна единице, т. е.

p0 +pl +p2 +p3 +p4 +p5+p6 +p7 =1.                                      (4)

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

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

 

В левой части каждого уравнения следует записать производную вероятности г-го состояния устройства.

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

 

Когда определены вероятности событий, то встаёт вопрос: «Что будет с техническим устройством в установившемся режиме?» В каком состоянии режиме) будет находиться техническое устройство по прошествии большого периода времени, т. е. при . Если существуют пределы вероятностей pi(t) состояний устройства и они не зависят от текущего состояния устройства, то эти пределы называются финальными вероятностями состояний.

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

Если финальные вероятности существуют:

 при i = 1, 2, 3, ..., n,                              (5)

то их сумма будет равна единице:

                       (6)

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

 

Варианты заданий:

Составьте систему уравнений по схеме:

 

 

 

Самостоятельная работа №26: Нахождение финальных вероятностей

 

Цель: научиться находить финальные вероятности событий

Самостоятельная работа: индивидуальное домашнее задание

Форма контроля: проверка работы

 

Теоретический материал и методические указания к выполнению заданий

 

Если финальные вероятности существуют:

 при i = 1, 2, 3, ..., n,                              (5)

то их сумма будет равна единице:

                       (6)

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

 

1.     Решение системы уравнений Колмогорова

 

Зададим численные значения интенсивности потоков событий для примера 1:

l1=1; l2=2; l3=1; m1=2; m2=4; m3=2.

Приравняем левые части уравнений системы (3) нулю и заменим одно из уравнений (седьмое) выражением (4)

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

Подставим конкретные значения (указанные выше) прямых и обратных интенсивностей

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

Из первого уравнения выразим  и подставим его в остальные уравнения:

Аналогично выражаем  и подставляем в оставшиеся уравнения и получаем:

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

Из первого выражения выразим  и подставим в оставшиеся уравнения. После выполнения преобразований получим:

Из первого уравнения выразим и подставим в оставшиеся уравнения:

Из первого уравнения в оставшиеся уравнения:

Из первого уравнения p0 подставим в оставшиеся уравнения:

    

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

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 с данными:

 

l1=2; l2=1; l3=3; m1=4; m2=2; m3=4.

 

 

Самостоятельная работа №27: Подготовка сообщения на тему «Имитационное моделирование»

 

Цель: получить представление о имитационном моделировании

Самостоятельная работа: работа с литературой

Форма контроля: сообщение на уроке

 

 

Самостоятельная работа №28: Решение задачи управления запасами и задачи теории массового обслуживания, используя имитационное моделирование

 

Цель: научиться решать задачи управления запасами и задачи теории массового обслуживания, используя имитационное моделирование

Самостоятельная работа: индивидуальное домашнее задание

Форма контроля: проверка работы

 

Теоретический материал и методические указания к выполнению заданий

 

1.      Суть имитационного моделирования

 

Имитационное моделирование – получение экспериментальной информации о сложном объекте, которая не может быть получена иным путем, как экспериментируя с его моделью на ПЭВМ.

Рассматривая исторический процесс формирования этого термина, пришли к выводу, что это словосочетание определяет в моделировании такую область, которая относится к получению экспериментальной информации о сложном объекте, которая не может быть получена иным путем, как экспериментируя с его моделью на ПЭВМ.

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

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

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

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

 

2.      Метод Монте-Карло

 

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

Метод Монте-Карло – это численный метод решения задач при помощи моделирования случайных величин. Создателями метода считают математиков Дж. Неймана и С. Улама.

Теоретическая основа метода была известна давно. Однако до появления ЭВМ этот метод не мог найти широкого применения.

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

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

Пример:   По цели производится 3 независимых выстрела, из которых каждый попадает в цель с вероятностью 1/2. Требуется найти вероятность хотя бы одного попадания.

Р(k >= 1) = P(1)+P(2)+P(3) = 1-P(k < 1)             P(0) = 1/2*1/2*1/2 = 1/8          P(k >= 1) = 1-1/8 = 7/8

Эту задачу можно решить розыгрышем – статистическим моделированием. Вместо 3 выстрелов будем бросать 3 монеты, считая, что герб – попадание, решка – промах. Опыт считается удачным, если на одной из монет выпадет герб. Проведем множество опытов, подсчитаем общее количество удач и разделим на число – N (количество проведённых опытов). Таким образом, они получили частоту события, а она при большом числе опытов близка к вероятности.

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

 

3.      Оценка надежности простейших систем методом Монте-Карло

 

Пример: Система состоит из двух блоков, соединенных последовательно. Система оказывает при отказе хотя бы  одного блока. Первый блок содержит два элемента: А, В (они соединены параллельно) и оказывает при одновременном отказе обоих элементов. Второй содержит один элемент С и отказывает при отказе этого элемента.

а) Найти методом Монте-Карло оценку Р* надежности (вероятности безотказной работы) системы, зная вероятности безотказной работы элементов: Р (А)=0,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.

б)   Найдем надежность системы Р аналитически. Вероятности безотказной работы первого и второго блоков соответственно равны:

Вероятность безотказной работы системы

P=P1*P2=0,97*0,6=0,582

Искомая абсолютная погрешность êР-Р*ê=0,582-0,56=0,022.

 

2.     Расчет СМО с отказами методом Монте-Карло

 

Пример: В трехканальную систему массового обслуживания с отказом поступает пуассоновский поток заявок. Время между поступлениями двух последовательных заявок распределено по показательному закону f(t)=5e-5t . Длительность обслуживания каждой заявки равна 0,5 мин. Найти методом Монте-Карло математическое ожидание а числа обслуженных заявок за время Т=4 мин.

Решение:

Пусть Т1=0- момент поступления первой заявки. Заявка поступит в первый канал и будет им обслужена. Момент окончания обслуживания первой заявки  Т1+0,5=0+0,5=0,5. В счетчик обслуженных заявок записываем единицу.

Моменты поступления последующих заявок найдем по формуле

Тi= Тi-1+ ti ,

где  ti - длительность времени между двумя последовательными заявками с номерами i-1 и i.

Возможные ti = - (1/l) ln ri = =  (1/l)(- ln ri  ).

Учитывая, что, по условию, l=5, получим  ti =0,2 (- ln ri  ).

Случайные числа ri берем из таблицы приложения, начиная с первой строки сверху. Для нахождения времени между поступлениями первой и второй заявок возьмем случайное число r=0,10.

Тогда t2=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 разыграем время t3 между поступлениями второй и третьей заявок:

t3=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

Время между двумя последовательными заявками

ti=0,2(-ln ri)

Момент поступления заявки

Ti= Ti-1+ti

Момент

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 *==(2*12+13+14+2*15)/6=13,5.

 

Варианты заданий:

 

  1. Система состоит из двух блоков, соединенных последовательно. Первый блок содержит три элемента: А, В, С, а второй- два элемента: D, E. Элементы каждого блока соединены параллельно.

а)  Найти методом Монте-Карло оценку Р* надежности системы, зная вероятности безотказной работы элементов: Р(А)=0,8; Р(В)=0,7; Р(С)=0,9; Р(D)=0,8; P(E)=0,7;

б) найти абсолютную погрешность  êР-Р*ê, где Р- надежность системы, вычисленная аналитически. Произвести 15 испытаний.

 

  1. Система состоит из двух блоков, соединенных последовательно. Первый блок содержит два элемента: А, В,  второй- три элемента: С, D, E. Элементы первого и второго блоков соединены параллельно.

а)  Найти методом Монте-Карло оценку Р* надежности системы, зная вероятности безотказной работы элементов: Р(А)=0,9; Р(В)=0,6; Р(С)=0,7; Р(D)=0,75; P(E)=0,6;

б) найти абсолютную погрешность  êР-Р*ê, где Р - надежность системы, вычисленная аналитически. Произвести 15 испытаний.

 

  1. В двухканальную систему массового обслуживания с отказом поступает пуассоновский поток заявок. Время между поступлениями двух последовательных заявок распределено по показательному закону f(t)=5e-5t . Длительность обслуживания каждой заявки равна 0,5 мин. Найти методом Монте-Карло математическое ожидание а числа обслуженных заявок за время Т=10 мин.

 

  1. В трехканальную СМО с отказами поступает пуассоновский поток заявок. Время между моментами поступления двух последовательных заявок распределено по закону f(t)=8 e-8t; время обслуживания заявок 1мин. Найти методом Монте-Карло математическое ожидание а числа обслуженных заявок за время Т=10 мин.

 

 

Самостоятельная работа №29: Формирование и усвоение содержания теоретического материала, используя информационные образовательные ресурсы

 

Цель: научиться использовать информационные образовательные ресурсы для самоконтроля по изучаемой теме

Самостоятельная работа: работа с Internet- ресурсами

Форма контроля: проверка работы

 

 

Самостоятельная работа №30: Работа над учебным материалом по первоисточникам

 

Цель: расширить теоретические знания по изучаемой теме

Самостоятельная работа: работа с литературой

Форма контроля: ответ на уроке

 

 

Самостоятельная работа №31: Построение прогнозов количественными и качественными методами

 

Цель: научиться решать задачи на применение метода наименьших квадратов

Самостоятельная работа: индивидуальное домашнее задание

Форма контроля: проверка работы

 

Теоретический материал и методические указания к выполнению заданий

 

1.                 Классификация прогнозирования

 

Прогнозирование – предсказание на основе каких-то методов как будет себя вести объект в определенный момент времени в будущем.

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

 

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

 

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

 

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

В зависимости от глубины упреждения прогнозы подразделяются на оперативные, Самостоятельная работа №еднеСамостоятельная работа №очные и перспективные:

Оперативные прогнозы – ограничены по Самостоятельная работа №окам от долей секунды до года.

Самостоятельная работа №еднеСамостоятельная работа №очные – от года до пяти лет.

Перспективные – более пяти лет.

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

 

2.      Формализованные методы прогнозирования

 

Методы экстраполяции

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

Задача экстраполяции формируется так: пусть в интервале (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: функция с медленным экспоненциальным ростом в начале развития, который сменяется внезапным, более быстрым ростом и, наконец, замедлением в конце развития.

 

Регрессивный анализ

Уравнения множественной регрессии являются одним из наиболее распространённых методов многофакторного прогнозирования. Для линейного случая модель множественной регрессии записывается в виде

при j = 1…m, где ai – коэффициент модели, i = 0…n; 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).

Первый критерий рассчитывается по формуле:

где y*(k) – данные прогноза; y(k) – реальные данные части В.

Второй критерий рассчитывается по формуле:

где Δy*(k) – разности между данными прогноза; Δy(k) – разности между реальными данными.

 

3.      Эвристические методы прогнозирования

 

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

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

На первом этапе эксперты привлекаются к работе по уточнению модели объекта прогнозирования.

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

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

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

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

где Bj – значение прогнозируемой величины, данной j-м экспертом; n – число экспертов в группе.

Приближенное значение доверительного интервала ±b-tX*(D/(n-1)), t – параметр, определенный из таблиц Стьюдента для заданного уровня доверительной вероятности и числа степеней свободы l = (n-2).

Доверительные границы значений прогнозируемой величины вычисляются по формулам:

Для верхней границы: Ав = В+b.

Для нижней границы: Ан = В-b.

Коэффициент вариаций оценок экспертов определяется из зависимости:

V = σ/B,

где σ – Самостоятельная работа №еднеквадратичное отклонение.

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

 

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

 

4.      Комплексные методы прогнозирования

 

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

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

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

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

 

5.      Линейное сглаживание функции

 

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

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

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

1. Если  - линейная функция, т.е. , то , неизвестные параметры определяются из системы

                                (1)

Формулы, служащие для аналитического представления опытных данных, получили название эмпирических формул.

Система (1) называется системой нормальных уравнений.

 

2. Если  - квадратичная функция, т.е. , то , неизвестные параметры определяются из системы нормальных уравнений:

                                (2)

 

Пример 1. Имеются следующие данные о величине пробега автомобиля  (тыс. км) и  – расходе масла (л/тыс. км):

50

70

90

110

130

0,2

0,5

0,8

1,1

1,3

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

Решение:

Перепишем таблицу в виде столбцов и проведем необходимые вычисления:

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

450

3,9

44500

407

Система линейных уравнений (1) для определения величин  и  примет вид

Ее решение , .

Таким образом, линейная зависимость имеет вид .

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

 

Пример: 2) Аппроксимируем таблично заданную функцию у=- квадратичной  .

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

Перепишем таблицу в виде столбцов и проведем необходимые вычисления:

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

37,5

4,745

238,75

1546,875

10186,1875

29,427

185,486

Система линейных уравнений для определения величин  примет вид

Решим систему методом Крамера:

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

 

Искомый многочлен:

 

 

Самостоятельная работа №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

(1)

 
А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

 

                      

 

Проанализируем матрицу игры: для каждой чистой стратегии игрока А определим минимальный выигрыш, т.е. определим

 

ai = аij.

В нашем примере a1 = -3; a2 = -5; a3 = -5. Далее, Самостоятельная работа №еди полученных значений li-х определим максимальное

 

a =ai = аij.

В нашем примере a = -3, т.е. игрок А проигрывает 3 очка. Это число a называется нижней ценой игры, а соответствующая ему стратегия называется максиминной. В нашем примере стратегия А1 максиминная, т.е. из всех наихудших ситуаций выбирают наилучшую. Эта величина (a) – гарантированный «выигрыш» игрока А, какую бы стратегию ни выбрал игрок В.

Меньше нижней цены игры игрок А никогда не «выиграет».

Игрок В старается максимально уменьшить свой проигрыш. Для этого определяется верхняя цена игры

 

b =bj = аij.

 

Соответствующая стратегия называется минимаксной. В нашем примере будет две минимаксных стратегии В1 и В2. При этом игрок В проигрывает 4 очка.

Теорема 1. В любой матричной игре справедливо неравенство a £ b, т.е. нижняя цена игры никогда не превосходит верхнюю.

 

Игра с седловой точкой

 

Если в матричной игре нижняя и верхняя цены игры совпадают, то такая игра имеет «седловую точку» в чистых стратегиях, а число u = a = b называют ценой игры. В этом случае решением игры, т.е. оптимальным поведением для обоих игроков являются их максиминная для игрока А и минимаксная  для игрока В стратегии игры. Любое отклонение игроков от своих оптимальных стратегий не может оказаться им выгодным. Элемент платежной матрицы, отвечающий оптимальным стратегиям, называется седловой точкой.

 

Пример. Пусть игра задана следующей платежной матрицей:

 

В1

В2

В3

В4

ai

- лучшая стратегия для игрока А – (А3)

 
А1

9

3

8

2

2

А2

4

2

7

3

2


А3

6

4

7

8

4

А4

5

3

4

7

3

bj

9

4

8

8

 

цена игры u = a = b = 4

min max - лучшая стратегия для игрока В – (В2)

 

 

 

Игра в смешанных стратегиях

 

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

Рассмотрим платежную матрицу (1). Пусть игрок А использует чистые стратегии А1, А2, … Аi,…Аm с вероятностями p1, p2, … pi,…pm, причем  =1, а игрок В использует свои чистые стратегии В1, В2, … Вj,…Bn с вероятностями q1, q2, … qj,… qn, причем = 1.

Тогда набор SA = (p1, p2, … pi,…pm) называется смешанной стратегией игрока А, а набор SB = (q1, q2, … qj,… qn) - смешанной стратегией игрока В.

Поскольку игроки выбирают свои стратегии случайным образом, то вероятность выбрать комбинацию АiВj по теории вероятности равна (Pi × qj). При использовании смешанных стратегий игра становится случайной, тогда говорят о Самостоятельная работа №еднем значении выигрыша, который определяется платежной функцией

 

f(SA, SB) = .                                                       (2)

 

Смешанные стратегии = (,,…) и = (,,…) называются оптимальными, т.е. дающими каждой стороне максимальный возможный для нее Самостоятельная работа №едний выигрыш (для А) или минимальный Самостоятельная работа №едний проигрыш (для В), если они образуют седловую точку для платежной функции (2), т.е. если выполняется следующее условие:

 

f(SA, ) £ f(,) £ f(, SB).

 

            Величина u = f(, SB) называется ценой игры.

            Теорема 2. В смешанных стратегиях  любая матричная игра имеет седловую точку, или каждая матричная игра с нулевой суммой имеет решение в смешанных стратегиях.

 

Решение игры в смешанных стратегиях

 

            Теорема 3. Для того чтобы смешанные стратегии  и  были оптимальными в игре с матрицей (1) и ценой игры u, необходимо и достаточно, чтобы выполнялись следующие неравенства:

 

³ u; j = , причем = 1;                          (3)

£ u; i = , причем = 1.                                     (4)

 

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

            Пусть требуется найти оптимальные стратегии для игры с заданной платежной матрицей (1), для которой aij строго больше нуля (аij >0, i=,j = ), тогда цена игры u > 0. Найдем оптимальную стратегию игрока А – ().

            Разделим левую и правую части в выражении (3) на положительную величину u:

³ 1;            = .

 

Введем обозначение  = Хi, тогда

 

Хi  ³ 1; j = ;          = .

 

            Поскольку игрок А стремится сделать свой гарантированный выигрыш (u) как можно большим (u ® max), то величина  должна быть как можно меньше (u ® min), тогда имеем следующую задачу линейного программирования:

f(x) = ® min,                                          (5)

Х³ 1; j = ,                                                     (6)

Х³ 0; i = .                                                         (7)

 

            Если Х* = (,,…) – оптимальный план задачи (5) – (7), а минимум функции f(x) = f(x*) = f*, то цена игры u при этом составит u = , а т.к. = Хi, тогда = (u × ,… u × ) = (,…) – оптимальная смешанная стратегия игрока А.

Для игрока В используя выражение (4), получим

 

g(y) = ® max.

 

yj £ 1, i = .

y³ 0; j = .

 

Решение игры u =  = (u × ,… u × ) = (,…).

 

Пример. Найти оптимальные смешанные стратегии игры, заданной следующей платежной матрицей:

 

 

В1

В2

В3

          нижняя цена игры a = 4,

верхняя цена игры b = 5,

          т.е. a ¹ b – седловой точки нет.

А1

1

10

3

А2

8

4

5

 

Сведем данную задачу к задаче линейного программирования.

 

Найдем оптимальную стратегию игрока А – ():

 

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,

 

отсюда

 

u = = 4,76;        P1 = 4,76 × 0,026 = 0,124;             P2 = 4,76 × 0,184 = 0,876.

Найдем оптимальную стратегию игрока В – ():

 

   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. Пусть  и   – оптимальные смешанные стратегии игры с платежной матрицей (1) и ценой игры u, тогда для любого i, при котором выполняется строгое неравенство

qj < u,

 

имеет место равенство pi = 0. А если pi > 0, то

 

qj = u.

 

Аналогично, если для некоторых j

 

× pi > u,

 

то для этих j                                    qj = 0. А если qj > 0, то

 

× pi = u.

 

            Определим оптимальную смешанную стратегию  игрока А, а для этого решим систему трех уравнений с тремя неизвестными

 

а11 × p1  + а21 × p2 = u,

а12 × p1  + а22 × p2 = u,

p1 + p2 = 1.

           

Решив следующую систему, найдем оптимальную стратегию   игрока В:

а11 × q1  + а12 × q2 = u,

а21 × q1  + а22 × q2 = u,

q1 + q2 = 1.

 

            Рассмотрим первую систему. Вычитая из первого равенства второе, получая

 

11 - а12) × p+ (а21 - а22) × p= 0.

 

            Подставим P= 1 - P1, тогда

 

11 - а12) × p+ (а21 - а22) (1- p1 ) = 0,

 

отсюда оптимальная смешанная стратегия для игрока А – А*( p1, p2)

 

P= (а22 - а21)/( а11 - а12 + а22 - а21),

 

P= 1- P1  = (а11 - а12)/( а11 - а12 + а22 - а21).

цена игры

u = ( а11 × а22 - а21 × а12)/ ( а11 - а12 + а22 - а21).

 

            Рассуждая аналогично, для определения оптимальной стратегии игрока В получая

q= (а22 - а12)/( а11 - а12 + а22 - а21),

 

q= (а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

ai

А1

-20

80

-20


А2

40

-60

-60

bj

40

80

 

        

Нижняя цена игры составляет (-20), верхняя равна 40. Игра не имеет седловой точки. Найдем оптимальные смешанные стратегии

 

 

 

p= (-60 - 40)/(-20 –80-60-40) = ; p= ;

 

u = [-20 × (-60)- 40 × 80]/ (-20 –80-60-40) = 10;

 

q= (-60 - 80)/(-20 –80-60-40) = ; q= .

 

            Выигрыш фирмы А в соответствии с ценой игры составит 10 %. Следовательно, А – В = 10 %, но А + В = 100 %, тогда А = 55 %; В = 45 %. Следовательно, при таких оптимальных стратегиях изделия фирмы А будут покупать 55 % потребителей, а фирма В – 45 % покупателей.

 

 

 

 

 

 

 

Геометрическое решение игры

 

            Пусть игра 2 х 2 имеет платежную матрицу (8). Изобразим на оси абсцисс отрезок горизонтальной линии единичной длины и обозначим концы отрезка через нуль и единицу. Из точек 0 и 1 по осям ординат восстановим перпендикулярные линии и изобразим на них выигрыши игрока А при использовании им соответственно чистых стратегий А1 и А2. Все промежуточные точки отрезка () будут изображать смешанные стратегии:

 

При оптимальной смешанной стратегии выигрыш игрока А будет составлять величину u и отмечен точкой М. Произведем аналогичные построения для игрока В:

 

 

При графическом решении игр возможны и другие ситуации:

 

            Пример. Найдем графическое и аналитическое решение игры:

           

 

В1

В2

                       a = 4, b = 5, a ¹ b -

          следовательно, седловой точки нет.

А1

2

5

А2

6

4

 

Найдем оптимальную смешанную стратегию игрока А

 

 

 

                        Найдем оптимальную смешанную стратегию игрока В:

 

Игры 2 х n  и m х 2

 

            Допустим, платежная матрица задана и имеет вид 2 х n:

 

 

В1

В2

Вn

      Игрок А имеет две стратегии, а игрок В – неограниченное число стратегий.

А1

a11

a12

a1n

А2

a21

a22

a2n

 

 

Допустим, платежная матрица имеет вид m х 2:

 

Надпись: 	В1	В2
А1	a11	a12
А2	a21	a22
…	…	…
Am	аm1	аm2

        

Минимум М находится на пересечении стратегий А1 и Аm, остальные отбрасываются, далее игра решается как задача 2 х 2.

           

Пример. Пусть игра задана в виде платежной матрицы

 

 

В1

В2

В3

    Игра (2 х 3) не имеет седловой точки a = 4, b = 5, a ¹ b, имеем игру в смешанных стратегиях.

А1

1

10

3

А2

8

4

5

 

 


            Решим задачу графически и аналитически. Для игрока А: получаем игру 2 х 2, используя стратегии В2 и В3 игрока В:

 

Для игрока В:

 

 

 

Самостоятельная работа №34: Область применимости теории принятия решений

 

Цель: получить знания о применении теории принятия решений

Самостоятельная работа: работа с литературой

Форма контроля: ответ на уроке

 

 

Самостоятельная работа №35: Работа над учебным материалом по первоисточникам

 

Цель: расширить теоретические знания по изучаемой теме

Самостоятельная работа: работа с литературой

Форма контроля: ответ на уроке


Методические указания к самостоятельной работе студента

 

 

Целевые направления  самостоятельной  работы студентов

 

1.Для овладения и углубления знаний:

- составление различных видов планов и тезисов пот тексту;

- конспектирование текста;

- создание презентации.

2. Для закрепления  знаний:

- работа с конспектом лекции;

- повторная работа с учебным материалом;

- составление плана ответа;

- составление различных таблиц.

3. Для систематизации учебного  материала:

- подготовка ответов на контрольные вопросы;

- аналитическая обработка текста;

- подготовка сообщения, доклада;

- тестирование;

- составление кроссворда;

- формирование плаката;

- составление памятки.

4 .Для формирования практических и профессиональных умений.

-решение задач и упражнений по образцу;

-решение ситуативных и профессиональных задач;

 

Приёмы самостоятельной работы студентов.

 

1. Работа с учебником.

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

- конспектирование;

- составление плана учебного текста;

- тезирование;

- аннотирование;

- выделение проблемы и нахождение путей её решения;

- самостоятельная постановка проблемы и нахождение в тексте путей её решения;

- определение алгоритма практических действий (план, схема).

2. Опорный конспект.

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

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

 

3. Тесты

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

4.Семинар

Форма проведения семинара очень гибкая.

На семинарах решаются следующие задачи:

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

- развитие навыков самостоятельной работы

- ознакомление со спецификой работы с литературой;

- профессиональное использование знаний в учебных условиях.

Типы проведения семинарских занятий:

- вопросно-ответный семинар;

- развёрнутая беседа на основе заранее данного студентам плана, обсуждение письменных рефератов;

- заслушивание устных докладов студентов с последующим их обсуждением;

- семинар – диспут;

- теоретическая конференция;

- семинар – имитационная игра;

- комментированное чтение первоисточников.

 

5. Задачное обучение.

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

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

Задачное обучение способно обеспечить целенаправленное, поэтапное формирование и контроль сформированности необходимых профессиональных компетенций.

 

Правила работы с книгой

 

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

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

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

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

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

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

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

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

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

Задача вторичного чтения  полное усвоение смысла целого (по счету это чтение может быть и не вторым, а третьим или четвертым).

 

Основные виды систематизированной записи прочитанного:

 

1.                  Аннотирование – предельно краткое связное описание просмотренной или прочитанной книги (статьи), ее содержания, источников, характера и назначения;

2.                  Планирование – краткая логическая организация текста, раскрывающая содержание и структуру изучаемого материала;

3.                  Тезирование – лаконичное воспроизведение основных утверждений автора без привлечения фактического материала;

4.                  Цитирование – дословное выписывание из текста выдержек, извлечений, наиболее существенно отражающих ту или иную мысль автора;

5.                  Конспектирование – краткое и последовательное изложение содержания прочитанного.

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

 

Методические рекомендации по составлению конспекта:

 

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 изображений для иллюстрации одной идеи);

• размещение фотографий и рисунков на слайде должно отвечать общим дизайн-эргономическим требованиям экранного представления информации;

• для облегчения «веса презентации», т.е уменьшения объема файла фотографии рекомендуется представлять в сжатом виде;

• все рисунки должны быть подписаны; подпись располагается снизу.

Анимации и эффекты

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

При создании презентации педагогу важно помнить:

· Увиденное сначала предстает перед нами как образ – мы реагируем на поведение объекта (движение, изменение формы и цвета), выделяем размер, цвет, форму, а затем обращаем внимание на содержание.

· Понимание закономерностей восприятия, грамотное, планомерное использование приемов анимации – это залог повышения эффективности восприятия материала, представленного в презентации.

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

· Не следует увлекаться анимациями, помня о том, что важен не внешний эффект, а содержание информации.

Планируя и оценивая презентацию, помните: анимации и эффекты – только к месту.

 

 


Литература

 

Основные источники

 

1.     Партыка Т.Л., Попов И.И. Математические методы. – М.: ФОРУМ       : ИНФРА-М, 2012.

2.     Агальцов В.П., Волдайская И.В.. Математические методы в программировании: Учебник.-  М.: ФОРУМ: ИНФРА-М, 2008.

 

Дополнительные источники

 

1.        Фомин Г.П. Математические методы и модели в коммерческой деятельности: Учебник. – М.: Финансы и статистика, 2008.

2.        Попов А.М. Экономико-математические методы и модели :учебник.-М.: Юрайт, 2012

 

Интернет-ресурсы

 

1.            Единое информационно-образовательное пространство колледжа NetSchool. Форма доступа: http://sgtek.ru

2.     Информационно-справочная система «В помощь студентам». Форма доступа: http://window.edu.ru

3.     Информационно-справочная система. Форма доступа:   http://dit.isuct.ru.

4.     Информационно-справочная система. Форма доступа: http://www.resolventa.ru

 

 

 

 

Просмотрено: 0%
Просмотрено: 0%
Скачать материал
Скачать материал "МЕТОДИЧЕСКИЕ УКАЗАНИЯ по выполнению самостоятельной внеаудиторной работы по дисциплине «Математические методы» для студентов 3 курса (специальность Программирование в компьютерных системах)"

Методические разработки к Вашему уроку:

Получите новую специальность за 3 месяца

Юрист

Получите профессию

Интернет-маркетолог

за 6 месяцев

Пройти курс

Рабочие листы
к вашим урокам

Скачать

Краткое описание документа:

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

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

Скачать материал

Найдите материал к любому уроку, указав свой предмет (категорию), класс, учебник и тему:

6 664 567 материалов в базе

Скачать материал

Другие материалы

Оставьте свой комментарий

Авторизуйтесь, чтобы задавать вопросы.

  • Скачать материал
    • 28.01.2015 613
    • DOCX 2.6 мбайт
    • Рейтинг: 5 из 5
    • Оцените материал:
  • Настоящий материал опубликован пользователем Евдокимова Марина Дмитриевна. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт

    Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.

    Удалить материал
  • Автор материала

    Евдокимова Марина Дмитриевна
    Евдокимова Марина Дмитриевна
    • На сайте: 9 лет и 5 месяцев
    • Подписчики: 6
    • Всего просмотров: 142833
    • Всего материалов: 57

Ваша скидка на курсы

40%
Скидка для нового слушателя. Войдите на сайт, чтобы применить скидку к любому курсу
Курсы со скидкой

Курс профессиональной переподготовки

Фитнес-тренер

Фитнес-тренер

500/1000 ч.

Подать заявку О курсе

Курс профессиональной переподготовки

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

Учитель математики и информатики

300 ч. — 1200 ч.

от 7900 руб. от 3650 руб.
Подать заявку О курсе
  • Сейчас обучается 36 человек из 17 регионов
  • Этот курс уже прошли 35 человек

Курс повышения квалификации

Развивающие математические задания для детей и взрослых

36 ч. — 180 ч.

от 1700 руб. от 850 руб.
Подать заявку О курсе
  • Сейчас обучается 66 человек из 26 регионов
  • Этот курс уже прошли 81 человек

Курс повышения квалификации

Особенности подготовки к проведению ВПР в рамках мониторинга качества образования обучающихся по учебному предмету "Математика" в условиях реализации ФГОС ООО

72 ч. — 180 ч.

от 2200 руб. от 1100 руб.
Подать заявку О курсе
  • Сейчас обучается 203 человека из 54 регионов
  • Этот курс уже прошли 1 515 человек

Мини-курс

Управление техническими ресурсами и экономикой предприятия

4 ч.

780 руб. 390 руб.
Подать заявку О курсе

Мини-курс

Детская нейропсихология: особенности, диагностика, исследования

6 ч.

780 руб. 390 руб.
Подать заявку О курсе
  • Сейчас обучается 119 человек из 43 регионов
  • Этот курс уже прошли 56 человек

Мини-курс

Карьера и развитие в современном мире

10 ч.

1180 руб. 590 руб.
Подать заявку О курсе