ДЕПАРТАМЕНТ ОБРАЗОВАНИЯ, НАУКИ И МОЛОДЕЖНОЙ ПОЛИТИКИ ВОРОНЕЖСКОЙ ОБЛАСТИ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ САМОСТОЯТЕЛЬНАЯ РАБОТА №ЕДНЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ВОРОНЕЖСКОЙ ОБЛАСТИ

«СЕМИЛУКСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИКО-ЭКОНОМИЧЕСКИЙ КОЛЛЕДЖ»

М.Д. Евдокимова

методические указания

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

по дисциплине «Математические методы и модели в экономике»

для студентов 2 курса

(специальность 080114 Экономика и бухгалтерский учет (по отраслям)

Семилуки , 2014

Одобрено методическим советом ГОБУ СПО ВО «СГТЭК»

Автор-составитель: Евдокимова М.Д., преподаватель ГОБУ СПО ВО «СГТЭК»

Учебное пособие содержит указания по выполнению внеаудиторных самостоятельных работ по «Математические методы и модели в экономике», являющейся профессиональной дисциплиной. Методические указания составлены в соответствии с рабочей программой по дисциплине «Математические методы и модели в экономике» и предназначены для студентов 2-го курса, обучающихся по специальности 080114 Экономика и бухгалтерский учет (по отраслям)

© Евдокимова М.Д., 2014

©ГОБУ СПО ВО «СГТЭК»

Оглавление

стр.

Введение

5

Раздел 1. Основные понятия и принципы моделирования

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

8

Самостоятельная работа №2 Построение простейших математических и статистических моделей

8

Самостоятельная работа №3: Собрать характеристики моделей

10

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

11

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

13

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

17

Самостоятельная работа №6: Подготовка сообщений: «Линейное программирование - возникновение и развитие»

17

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

17

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

23

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

31

Самостоятельная работа №10: Формирование и усвоение содержания теоретического материала по теме «Линейное программирование»

41

Самостоятельная работа №11: Подготовка сообщения «Динамическое программирование»

41

Самостоятельная работа №12: формирование и усвоение содержания теоретического материала по теме Динамическое программирование»

42

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

44

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

44

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

55

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

55

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

55

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

55

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

55

Самостоятельная работа №19: Подготовить сообщение «Область применимости теории принятия решений»

62

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

62

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

62

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

71

Литература

79

Введение

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

Объем самостоятельной работы студентов определяется государственным образовательным стандартом среднего профессионального образования (ФГОС СПО) по специальности 080114 Экономика и бухгалтерский учет (по отраслям).

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

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

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

- углубления и расширения теоретических знаний;

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

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

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

для овладения знаниями: чтение текста (учебника, дополнительной литературы), работа со словарями и справочниками, учебно-исследовательская работа, использование аудио- и видеозаписей, компьютерной техники и Интернета;

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

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

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

ПК 1.1. Обрабатывать первичные бухгалтерские документы.

ПК 1.3. Проводить учет денежных средств, оформлять денежные и кассовые документы.

ПК 2.2. Выполнять поручения руководства в составе комиссии по инвентаризации имущества в местах его хранения.

ПК 2.4. Проводить процедуры инвентаризации финансовых обязательств организации.

ПК 4.4. Проводить контроль и анализ информации об имуществе и финансовом положении организации, ее платежеспособности и доходности.

В процессе выполнения работы у студентов должны формироваться общие компетенции (ОК):

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

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

ОК 3. Принимать решения в стандартных и нестандартных ситуациях и нести за них ответственность.

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

ОК 5. Использовать информационно-коммуникационные технологии в профессиональной деятельности.

ОК 6. Работать в коллективе и команде, эффективно общаться с коллегами, руководством, потребителями.

ОК 7. Брать на себя ответственность за работу членов команды (подчиненных), результат выполнения заданий.

ОК 8. Самостоятельно определять задачи профессионального и личностного развития, заниматься самообразованием, осознанно планировать повышение квалификации.

ОК 9. Ориентироваться в условиях частой смены технологий в профессиональной деятельности.

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

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

уметь:

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

• выбирать и обосновывать наиболее рациональный метод и алгоритм решения задачи, а также оценивать сложность выбранного алгоритма;

• решать различные практические задачи с применением математических методов.

знать:

• основные понятия и принципы моделирования;

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

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

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

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

Критериями оценки результатов внеаудиторной самостоятельной работы студента являются:

- уровень освоения студентом учебного материала;

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

- сформированность общеучебных умений;

- обоснованность и четкость изложения ответа;

- оформление материала в соответствии с требованиями.

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

Раздел 1. Основные понятия и принципы моделирования

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

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

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

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

Самостоятельная работа №2 Построение простейших математических и статистических моделей

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

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

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

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

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

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

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

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

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

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

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

где a_ij, b_i, c_j - заданные постоянные величины.

Пример. Фирма выпускает 2 вида мороженного: сливочное и шоколадное. Для изготовления используются 2 исходных продукта: молоко и наполнители, расходы которых на 1 кг мороженного и суточные запасы исходных продуктов даны в таблице.

Изучение рынка сбыта показало, что суточный спрос на сливочное мороженное превышает спрос на шоколадное мороженное не более чем на 100 кг. Кроме того, установлено, что спрос на шоколадное мороженное не превышает 350 кг в сутки. Отпускная цена 1 кг сливочного мороженного 16 ден.ед., шоколадного - 14 ден.ед. Определить количество мороженого каждого вида, которое должна производить фирма, чтобы доход от реализации продукции был максимальным.

Решение:

Составляем математическую модель задачи.

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

х ₁ - суточный объем выпуска сливочного мороженного, кг;

х ₂ - суточный объем выпуска шоколадного мороженного, кг

Целевая функция:

f = 16 х ₁ + 14 х ₂→max

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

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

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

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: Собрать характеристики моделей

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

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

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

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

1. Сбор информации

2. Систематизация информации

Пример:

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

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

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

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

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

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

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

В практической деятельности приходится рассматривать сложные объекты, которые невозможно целостно сопоставить. В таких случаях выделяют существенные показатели этих объектов, а затем проводят Самостоятельная работа №авнение их значений. При этом первичная информация задаётся в виде таблицы значений показателей, где представлены множество Самостоятельная работа №авниваемых объектов a₁, a_2, a_3,…, a_i, …,a_m, все наименования показателей P₁, P₂, P₃, …, P_i, …, P_n и значение этих показателей по каждому объекту p₁(a_i), p₂(a₂), p₃(a₃), …, p_j(a_i), …, p_n(a_m).

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

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

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

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

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

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

Результаты запишем в таблицу.

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

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

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

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

Приоритет показателей распределяется по рангу, который пропорционален значению коэффициента весомости: чем больше его значение, тем выше ранг, причем наибольшему значению M_icсоответствует R_i=1.

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

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

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..

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

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

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

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

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

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

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

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

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

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

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

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

где a_ij, b_i, c_j - заданные постоянные величины.

Пример. Фирма выпускает 2 вида мороженного: сливочное и шоколадное. Для изготовления используются 2 исходных продукта: молоко и наполнители, расходы которых на 1 кг мороженного и суточные запасы исходных продуктов даны в таблице.

Изучение рынка сбыта показало, что суточный спрос на сливочное мороженное превышает спрос на шоколадное мороженное не более чем на 100 кг. Кроме того, установлено, что спрос на шоколадное мороженное не превышает 350 кг в сутки. Отпускная цена 1 кг сливочного мороженного 16 ден.ед., шоколадного - 14 ден.ед. Определить количество мороженого каждого вида, которое должна производить фирма, чтобы доход от реализации продукции был максимальным.

Решение:

Составляем математическую модель задачи.

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

х ₁ - суточный объем выпуска сливочного мороженного, кг;

х ₂ - суточный объем выпуска шоколадного мороженного, кг

Целевая функция:

f = 16 х ₁ + 14 х ₂→max

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

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

Постройте математическую модель задачи:

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. Фирма производит и продает столы и шкафы из древеси­ны хвойных и лиственных пород. Расход каждого вида в кубо­метрах на каждое изделие задан в таблице.

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

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

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

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

Самостоятельная работа №6: Подготовка сообщения «Линейное программирование - возникновение и развитие»

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

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

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

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

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

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

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

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

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

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

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

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

F = c₁x₁+c₂x₂ → max(min) при ограничениях на переменные

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

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

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

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

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

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

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

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

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

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

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

4. Строят векторN(с₁, c₂), который указывает направление возрастания целевой функции.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

F() = -2 ^. 0 + 4 ^.2,5 =10.

Запишем множество оптимальных решений как линейную выпуклую комбинацию углов точек отрезка ВС:

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

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

Для нахождения минимального значения целевой функции задачи перемещаем начальную прямую в направлении, противоположном вектору N(c_1,c₂). Начальная прямая займет положение опорной прямой в вершине Д, где х₁ = 2, х_г = 0, а минимальное значение целевой функции равно:

.

Пример: Решить задачу ЛП графическим методом:

Фирма выпускает два вида продукции А и В. Суточные ресурсы фирмы следующие:

610- единиц производственного оборудования;

620 - единиц сырья;

720- единиц электроэнергии.

Расходы каждого вида ресурсов на единицу продукции каждого типа представлены в табл.1:

Цена единицы продукции первого вида равна 8 ден.ед., а второго вида - 6ден.ед.

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

Решение: Математическая модель задачи:

Пусть х₁ - количество продукции первого вида, производимой в сутки;

х₂ - количество продукции второго вида, производимой в сутки.

Найти х₁, х₂, дающие максимум целевой функции при ограничениях:

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

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

(1)

(2)

(3)

(1)

х₁

0

305

х₂

152.5

0

(2)

х₁

0

620

х₂

124

0

(3)

х₁

0

240

х₂

360

0

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

Строим прямую, полученную с использованием целевой функции для F=0:

х₁

0

150

х₂

0

-200

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

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

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

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

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

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

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

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

Z = 3x₁ + 5x₂ → min

x₁ + x₂ ≤ 5

3x₁ - x₂ ≤ 3

x₁ ≥0, x₂ ≥0

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

Z = 3x₁ + 5x₂ → max

x₁ + x₂ ≤ 5

3x₁ - x₂ ≤ 3

x₁ ≥0, x₂ ≥0

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

Z = 2x₁ + 2x₂ → min

x₁ + 3x₂ ≥ 3

-2x₁ + x₂ ≤ 2

x₁ + x₂ ≤ 5

x₁ ≥0, x₂ ≥0

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

Z = 2x₁ + 2x₂ → max

x₁ + 3x₂ ≥ 3

-2x₁ + x₂ ≤ 2

x₁ + x₂ ≤ 5

x₁ ≥0, x₂ ≥0

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Определить вектор = (х₁, х₂,..., х_n), который удовлетворя­ет ограничениям вида

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

Алгоритм симплексного метода включает следующие этапы:

1. Составление первого опорного плана. Система ограниче­ний задачи, решаемой симплексным методом, задана в виде системы неравенств смысла «<», правые части которых b_i > 0. Перейдем от системы неравенств к системе уравнений путем введения неотрицательных дополнительных переменных. Век­торы-столбцы при этих переменных представляют собой единич­ные векторы и образуют базис, а соответствующие им перемен­ные называются базисными:

Решим эту систему относительно базисных переменных:

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

Полагая, что основные переменные х₁ =х₂ = х₃ =... х_п =0, получим первый опорный план Х₁ = (0, 0, ...,0, b₁, b₂, ..., b_т); F(X₁) = 0, который заносим в симплексную табл. Она со­стоит из коэффициентов системы ограничений и свободных членов. Последняя строка таблицы называется индексной и за­полняется коэффициентами функции цели, взятыми с противо­положным знаком.

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

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

Затем элементы столбца свободных членов симплексной таблицы делим на элементы того же знака (⁺/+; "/-) ведущего столбца. Результаты заносим в отдельный столбец di, которые будут всегда положительные. Строка симплексной таблицы, соответствующая минимальному значению d_i, является ведущей. Она определяет переменную x_i, которая на следующей итерации выйдет из базиса и станет свободной.

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

4. Построение нового опорного плана. Переход к новому плану осуществляется в результате пересчета симплексной таб­лицы методом Жордана - Гаусса. Сначала заменим переменные в базисе, т. е. вместо х_i , в базис войдет переменная х_j, соответ­ствующая ведущему столбцу.

Разделим все элементы ведущей строки предыдущей симплек­сной таблицы на разрешающий элемент и результаты деления занесем в строку следующей симплексной таблицы, соответствую­щую введенной в базис переменной x_j. В результате этого на месте разрешающего элемента в следующей симплексной таблице будем иметь 1, а в остальных клетках j столбца, включая клетку столбца индексной строки, записываем нули. Остальные новые элементы нового плана находятся по правилу прямоугольника:

где СТЭ - элемент старого плана, РЭ - разрешающий элемент, А и В - элементы старого плана, образующие прямоугольник с эле­ментами СТЭ и РЭ.

Далее возвращаемся ко второму этапу алгоритма - провер­ке плана на оптимальность.

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

Если в ведущем столбце все коэффициенты a_ij≤0, то функ­ция цели F(X) не ограничена на множестве допустимых планов, т. е. F(X) стремится к бесконечности и задача не имеет решения.

Если в столбце d_i симплексной таблицы содержатся два или несколько одинаковых наименьших значения, то новый опорный план будет вырожденным (одна или несколько базисных перемен­ных станут равными нулю). Вырожденные планы могут привес­ти к зацикливанию, т. е. к многократному повторению процесса вычислений, не позволяющему получить оптимальный план. С целью исключения этого для выбора ведущей строки используют метод Креко, который заключается в следующем. Элементы строк, имеющие одинаковые наименьшие значения d_i, делятся на предполагаемые разрешающие элементы, а результаты заносят­ся в дополнительные строки. За ведущую строку выбирается та, в которой раньше встретится наименьшее частное при чтении таблицы слева направо по столбцам. Например, таблица, содер­жащая три равных значения d_i = 2, имеет следующий вид:

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

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

Если в оптимальный план вошла дополнительная перемен­ная х_п+1, то при реализации такого плана имеются недоисполь­зованные ресурсы i-ro вида в количестве, полученном в столбце свободных членов симплексной таблицы.

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

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

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

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

Виды материально-денежных ресурсов

Норма затрат материально-денежных ресурсов на 1 тыс. руб. товарооборота

Объем ресурсов b₁

Группа A

Группа B

Группа C

Рабочее время продавцов, Чел.-ч.

0,1

3

0.4

1100

Площадь торговых залов, м²

0,05

0.2

0.02

120

Площадь складских помещений, м

3

0.02

2

8000

Доход, тыс.руб.

3

1

4

Max

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

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

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

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных x₄, x₅, x₆:

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

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

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

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

Полагая, что свободные переменные x₁=0, x₂=0, x₃=0, получим первый опорный план , в котором базисные переменные x₄=1100, x₅=120, x₆=8000. Следовательно, товары не продаются, доход равен нулю, а ресурсы не используются. Полученный первый опорный план запишем в симплексную таблицу.

План

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

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

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

X₁

X₂

X₃

X₄

X₅

X₆

I

→x₄

x₅

x₆

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

x₂

→x₅

x₆

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

x₂

x₁

x₆

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.

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

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

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

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

Формируем следующую часть симплексной таблице. Вместо переменной x₄ в план II войдет переменная x₂. Строка, соответствующая переменной x₂ в плане II, получена в результате деления всех элементов строки x₄ плана I на разрешающий элемент РЭ=0,2. На месте разрешающего элемента в плане II получаем 1. В остальных клетках столба x₂ плана II записываем нули.

Таким образом, в новом плане II заполнены строки x₂ и столбец x₂. Все остальные элементы нового плана II, включая элементы индексной строки, определяются по правилу прямоугольника. Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ=0,2. Во второй вершине по диагонали находится старое значение элемента, например, значение целевой функции F(K₁)=0=СЭ, которое указывает на место расположения нового НЭ в новом плане II. Третий элемент А=1100 и четвертый элемент В=-5 завершают построение прямоугольника в недостающих двух вершинах и расположены по диагонали. Значение нового элемента в плане II находится из выражения:

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

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

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

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

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

Следовательно, необходимо продавать товаров первой группы А 250 ед., а второй группы В - 5375 ед. При этом торговое предприятие получает максимальный доход в размере 27625 тыс. руб. Товары группы С не реализуются.

В оптимальном плане Самостоятельная работа №еди базисных переменных находится дополнительная переменная x₆. Это указывает на то, что ресурсы третьего вида (площадь складских помещений) недоиспользована на 1875 м², так как переменная x₆ была введена в третье ограничение задачи, характеризующее собой использование складских помещений этого ресурса.

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

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

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

Z = 4x₁ + 3x₂ → max

-x₁ + 3x₂ ≤ 9

2x₁ + 3x₂ ≤ 18

2x₁ - x₂ ≤ 10

x₁ ≥0, x₂ ≥0

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

Z = 2x₁ + x₂ + 2x₃ → max

3x₁ + 2x₂ + x₃ ≤ 6

x₁ + x₂ + 2x₃ ≤ 4

x₁ ≥0, x₂ ≥0, x₃ ≥0

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

Z = 5x₁ + 4x₂ - x₃ → max

x₁ - 2x₂ + 2x₃ ≤ 20

x₁ + 4x₂ - x₃ ≤ 16

x₁ ≥0, x₂ ≥0, x₃ ≥0

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

Z = 4x₁ - x₂ + x₃ → max

x₁ + 2x₂ + x₃ ≤ 20

2x₁ - x₂ + 2x₃ ≤ 10

x₁ ≥0, x₂ ≥0, x₃ ≥0

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

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

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

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

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

1. Построение математической модели транспортной задачи

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

Постановка транспортной задачи

Однородный груз, имеющийся в m пунктах отправления (производства) А1, А2, ..., Аm соответственно в количествах а1, а2, ..., аm единиц, требуется доставить в каждый из n пунктов назначения (потребления) В1, В2, ..., Вn соответственно в количествах b1, b2, ..., bn единиц. Стоимость перевозки (тариф) единицы продукции из Аi в Вj известна для всех маршрутов Ai, Bj и c_ij (i = 1, m; j = 1, n). Требуется составить такой план перевозок, при котором весь груз из пунктов отправления вывозится, и запросы всех пунктов потребления удовлетворяются (закрытая модель), т. е:

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

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

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

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

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

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

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

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

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

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.

Опорный план: Х₁₁ = 15, Х₂₁ = 5, Х₂₂ = 12, Х₂₃ = 5, Х₂₄ = 3, Х₃₄ = 5, Х₃₅ = 15. Все остальные X_ij = 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 и вычеркиваем четвертый столбец.

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

Х₁₁ = 3, Х₁₂ = 12, Х₂₁ = 2, Х₂₄ = 8, Х₂₅ = 15, Х₃₁ = 15, Х₃₃ = 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), тогда все остальные неизвестные определяются однозначно.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Найдём оптимальный план для рассмотренной выше задачи. В качестве опорного плана возьмем план, полученный с помощью метода "минимального элемента" Х₁₁ = 3, Х₁₂ = 12, Х₂₁ = 2, Х₂₄ = 8, Х₂₅ = 15, Х₃₁ = 15, Х₃₃ = 5. Все остальные элементы равны 0.

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

X = min(2, 12) = 2

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

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

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

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

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

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

Т.к. отрицательных оценок пустых ячеек нет, то полученный план является оптимальным. Х₁₁ = 15, Х₂₂ = 12, Х₂₄ = 8, Х₂₅ = 5, Х₃₁ = 5, Х₃₃ = 5, Х₃₅ = 10. Все остальные Х_ij = 0.

F = 1*15+1*12+3*8+3*5+4*5+1*5+3*10 = 121.

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

Вариант 1

Решить транспортную ЗЛП методом потенциалов, построив исходный опорный план способом минимального элемента.

a_i b_j

80

60

170

80

110

⁸

¹

⁹

⁷

190

⁴

⁶

²

¹²

90

⁶

⁵

⁸

⁹

Вариант 2

Решить транспортную ЗЛП методом потенциалов, построив исходный опорный план способом минимального элемента.

a_i b_j

30

70

90

110

50

³

⁸

¹⁰

⁵

150

¹

⁴

⁶

²

100

³

¹

⁹

⁷

Вариант 3

Решить транспортную ЗЛП методом потенциалов, построив исходный опорный план способом минимального элемента.

a_i b_j

15

7

14

62

51

²⁴

¹⁹

²³

¹⁵

19

¹⁴

²¹

¹⁵

¹⁶

28

¹⁰

⁹

⁶

¹¹

Вариант 4

Решить транспортную ЗЛП методом потенциалов, построив исходный опорный план способом минимального элемента.

a_i b_j

25

135

40

100

100

⁵

²

¹

¹

110

³

⁷

⁵

⁵

90

⁶

⁵

⁴

⁴

Вариант 5

Решить транспортную ЗЛП методом потенциалов, построив исходный опорный план способом минимального элемента.

a_i b_j

115

65

75

40

125

²¹

¹⁴

²⁷

¹⁵

145

⁷

²⁰

¹³

¹¹

25

¹⁰

¹¹

¹⁴

¹²

Вариант 6

Решить транспортную ЗЛП методом потенциалов, построив исходный опорный план способом минимального элемента.

a_i b_j

270

140

200

110

510

¹

⁴

⁷

³

90

⁵

⁶

⁸

⁹

120

⁷

²

⁴

⁸

Вариант 7

Решить транспортную ЗЛП методом потенциалов, построив исходный опорный план способом минимального элемента.

a_i b_j

225

325

250

100

250

⁵

⁸

⁷

³

200

⁴

²

⁵

⁶

450

⁷

³

⁹

²

Вариант 8

Решить транспортную ЗЛП методом потенциалов, построив исходный опорный план способом минимального элемента.

a_i b_j

310

200

195

145

350

¹

⁴

⁶

⁸

200

⁹

⁷

¹

²

300

²

³

²

⁹

Вариант 9

Решить транспортную ЗЛП методом потенциалов, построив исходный опорный план способом минимального элемента.

a_i b_j

40

50

90

60

60

¹

²

¹

⁴

80

⁴

³

⁵

³

100

⁶

²

²

³

Вариант 10

Решить транспортную ЗЛП методом потенциалов, построив исходный опорный план способом минимального элемента.

a_i b_j

290

120

110

130

200

¹

⁷

⁸

⁴

250

⁸

⁶

¹

²

200

⁷

²

³

¹

Самостоятельная работа №10: Формирование и усвоение содержания теоретического материала по теме «Линейное программирование»

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

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

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

Самостоятельная работа №11: Подготовка сообщения «Динамическое программирование»

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

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

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

Самостоятельная работа №12: формирование и усвоение содержания теоретического материала по теме Динамическое программирование»

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

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

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

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

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

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

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

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

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

W = W(u) = W(u₁, u₂, …,u_m) (1)

Управление, при котором показатель W достигает максимума (минимума), называется оптимальным управлением u*, которое состоит из совокупности оптимальных шагов управлений.

U* = (u₁*, u₂*, …, u_m*) (2)

Метод динамического программирования был предложен и развит Р. Беллманом и его учениками в начале 50-х годов и состоит в нахождении максимума (минимума) целевой функции при ограничении общего вида на изменяемые параметры.

Задача может быть сформулирована следующим образом:

Задача динамического программирования - определить u_i* (u_i* не только число, а может быть вектором, функцией) на каждом шаге, i = 1, 2 …, m, и тем самым u* всей операции в целом.

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

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

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

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

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

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

Другими словами, управление на i-шаге выбирается не так, чтобы выигрыш именно на данном шаге был максимален (минимален), а так, чтобы была оптимальна сумма выигрышей на всех оставшихся до конца шагах плюс данный. Исключение - последний шаг. Поэтому процесс динамического программирования обычно разворачивается от конца к началу - прежде всего, планируется последний шаг. А как его спланировать, если неизвестен последний? Необходимо сделать разные предположения о том, чем завершится m-1 шаг и для каждого из этих предположений найти условное оптимальное управление и соответствующий ему условный оптимальный выигрыш на m шаге. Далее, двигаясь назад, оптимизируем управление на m-2 шаге и т. д., пока не дойдем до первого. После можно построить не условно-оптимальное, а искомое оптимальное управление u* и найти искомый оптимальный выигрыш W*. Для этого достаточно, двигаясь от начала к концу, прочитать уже готовые рекомендации и найти u*, состоящие из u₁*, u₂*, … u_m*. Что касается оптимального выигрыша W* за всю операцию, то он нам уже известен - именно на его оптимальности выбрано управление на первом шаге.

Классические задачи динамического программирования

• Задача о наибольшей общей подпоследовательности: даны две последовательности, требуется найти самую длинную общую подпоследовательность.

• Задача поиска наибольшей увеличивающейся подпоследовательности: дана последовательность, требуется найти самую длинную возрастающую подпоследовательность.

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

• Задача о вычислении чисел Фибоначчи

• Задача о порядке перемножения матриц: даны матрицы , …, , требуется минимизировать количество скалярных операций для их перемножения.

• Задача о выборе траектории

• Задача последовательного принятия решения

• Задача об использовании рабочей силы

• Задача управления запасами

• Задача о ранце: из неограниченного множества предметов со свойствами «стоимость» и «вес» требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при ограниченном суммарном весе.

• Алгоритм Флойда - Уоршелла: найти кратчайшие расстояния между всеми вершинами взвешенного ориентированного графа.

• Алгоритм Беллмана - Форда: найти кратчайший путь во взвешенном графе между двумя заданными вершинами.

• Максимальное независимое множество вершин в дереве: дано дерево, найти максимальное множество вершин, никакие две из которых не связаны ребром.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(s..., Qⁿ(t)..., Q(Q(t)), Q(t),t),

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

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

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

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

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

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

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

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

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

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

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

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

Для взвешенного орграфа найти кратчайший путь из вершины 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. 1. Основные понятия

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

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

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

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

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

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

Требуется определить максимальный поток из Р₀ в Р₇, используя для этого все возможные дуги.

Заносим данные в таблицу. В ячейки таблицы записываем пропускную способность звеньев из Р_i пункта в Р_j элементом (i, j), а (j, i) - пропускная способность звена в обратном направлении. Если элемент (i, j) > 0, а (j, i) = 0, то на месте элемента (j, i) следует записать 0.

P₀

P₁

P₂

P₃

P₄

P₅

P₆

P₇

P₀

3

4

3

2

P₁

2

3

2

2

P₂

3

2

3

4

3

P₃

3

1

1

4

P₄

5

0

2

P₅

3

3

0

4

P₆

2

4

1

2

4

P₇

3

5

4

Выберем произвольно один из возможных путей из Р₀ в Р₇, например, Р₀, Р₂, Р₆, Р₇. Элементы (0,2), (2,6), (6,7) отмечаем знаком "-", а (2,0), (6,2), (7,6) - знаком "+".

P₀

P₁

P₂

P₃

P₄

P₅

P₆

P₇

P₀

3

4-

3

2

P₁

2

3

2

2

P₂

3+

2

3

4-

3

P₃

3

1

4

P₄

5

0

2

P₅

3

3

0

4

P₆

2

4+

1

2

4-

P₇

3

5

4+

Определяем пропускную способность выбранного пути:

Х₁ = min{(0,2); (2,6); (6,7)} = min{4,4,4} = 4.

Вычитаем Х₁ из ячеек со знаком "-" и прибавляем в ячейки со знаком "+".

Выбираем новый путь из Р₀ к Р₇. Например, Р₀, Р₁, Р₆, Р₇. Отмечаем элементы (0,1), (1,5) и (5,7) знаком "-". (1,0), (5,1) и (7,5) - знаком "+".

P₀

P₁

P₂

P₃

P₄

P₅

P₆

P₇

P₀

3-

0

3

2

P₁

2+

3

2-

2

P₂

7

2

3

0

3

P₃

3

1

4

P₄

5

0

2

P₅

3+

3

0

4-

P₆

2

8

1

2

0

P₇

3

5+

8

Определяем пропускную способность пути:

Х₂ = min{(0,1); (1,5); (5,7)} = min{3,2,4} = 2.

Вычитаем Х₂ из элементов таблицы, отмеченных знаком "-", и прибавляем к элементам со знаком "+".

Выбираем новый путь - Р₀, Р₃, Р₅, Р₇. Отмечаем плюсы и минусы.

Х₃ = min{(0,3); (3,5); (5,7)} = min{3,4,2} = 2.

Составляем новую таблицу:

P₀

P₁

P₂

P₃

P₄

P₅

P₆

P₇

P₀

1

0

3-

2

P₁

4

3

0

2

P₂

7

2

3

0

3

P₃

3+

1

4-

P₄

5

1

2

P₅

5

3

0+

0

2-

P₆

2

8

1

2

0

P₇

3

7+

8

Рассматриваем путь Р₀, Р₁, Р₂, Р₇.

P₀

P₁

P₂

P₃

P₄

P₅

P₆

P₇

P₀

1-

0

1

2

P₁

4+

3-

0

2

P₂

7

2+

3

0

3-

P₃

5

1

2

P₄

5

1

2

P₅

5

3

2

0

0

P₆

2

8

1

2

0

P₇

3+

9

8

Х₄ = min{(0,1); (1,2); (2,7)} = min{1,1,3} = 1.

Выбираем путь Р₀, Р₃, Р₅, Р₂, Р₇.

P₀

P₁

P₂

P₃

P₄

P₅

P₆

P₇

P₀

0

0-

0

2-

P₁

5

2

0

2

P₂

7

3

4

0+

1-

P₃

6

1

1

P₄

5+

1

2-

P₅

5

2

3

0

0

P₆

2

8-

1+

2

0

P₇

5+

9

8

Х₅ = min{(0,3); (3,5); (5,2); (2,7)} = min{1,2,3,2} = 1.

Выбираем путь Р₀, Р₄, Р₆, Р₂, Р₇.

P₀

P₁

P₂

P₃

P₄

P₅

P₆

P₇

P₀

0

0

0

2-

P₁

5

2

0

2

P₂

7

3

4

0+

1-

P₃

6

1

1

P₄

5+

1

2-

P₅

5

2

3

0

0

P₆

2

8-

1+

2

0

P₇

5+

9

8

Х₆ = min{(0,4); (4,6); (6,2); (2,7)} = min{2,2,8,1} = 1.

P₀

P₁

P₂

P₃

P₄

P₅

P₆

P₇

P₀

0

0

0

1

P₁

5

2

0

2

P₂

7

3

4

1

0

P₃

6

1

1

P₄

6

1

1

P₅

5

2

3

0

0

P₆

2

7

2

2

0

P₇

6

9

8

В столбце Р₇ имеются только 0. Вычитая из элементов первой таблицы элементы последней, получаем итоговую таблицу со значениями (i, j), определяющими максимально возможный поток.

P₀

P₁

P₂

P₃

P₄

P₅

P₆

P₇

P₀

3

4

3

1

P₁

1

2

P₂

3

3

P₃

3

P₄

1

P₅

1

4

P₆

4

P₇

Максимальный поток равен (0,1)+(0,2)+(0,3)+(0,4) = 3+4+3+1 = 11 (из строки Р₀).

Или (2,7)+(5,7)+(6,7) = 3+4+4 = 11 (из столбца Р₇).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

S₀ - все три узла исправны;

S₁- первый узел неисправен, второй и третий исправны;

S₂ - второй узел неисправен, первый и третий исправны;

S₃ - третий узел неисправен, первый и второй исправны;

S₄ - первый и третий узлы неисправны, второй исправен;

S₅ - второй и третий узлы неисправны, первый исправен;

S₆ - первый и второй узлы неисправны, третий исправен;

S₇ - все три узла неисправны.

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

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

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

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

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

(1)

Для определения вероятности каждого состояния технического устройства составим соответствующие дифференциальные уравнения. Вероятность того, что техническое устройство будет находиться в состоянии S₁ (первый узел неисправен, а второй и третий узлы исправны), обозначим p₁(t). Дадим малое приращение по времени t. За это малое время t техническое устройство либо остается в прежнем состоянии S₀ , либо перейдет в состояние S₁ и з состояний S₀ , S₄ или S_6.

Определим вероятность первого случая - устройство остается в состоянии S₁. В момент времени t устройство было в состоянии S₁ с вероятностью p₁(t). За время t устройство не перейдет в любое из состояний S₀, S₄ или S₆. Суммарный поток событий, который может вывести устройство из состояния S₁, будет равен ₂ +₃+₁. Каждый из этих потоков событий простейший, поэтому и суммарный поток также будет простейшим (все три свойства стационарности, ординарности и отсутствие последействия сохраняются).

Вероятность того, что устройство выйдет из состояния S₁ будет равна p₁(t) (₂ +₃+₁ ) t, а вероятность того, что останется в состоянии S₁- p₁(t) [1 - (₂ +₃+₁) t].

Теперь определим вероятность перехода устройства за время в t состояние S₁ из состояний S₀, S₄ или S₆.

Для S₄ - p₄(t) t_3;

Для S₄ - p₆(t) t_2;

Для S₄ - p₀(t) t_1.;

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

p₁(t+t)= p₁(t) [1-(₁+₂ +₃ )t]+ p₀(t)₁t+ p₄(t) ₃t+ p₆(t) ₂ t.

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

p₁(t+t)= p₁(t) (₁+₂ +₃ )t+ p₀(t)₁t+ p₄(t) ₃t+ p₆(t) ₂ t;

p₁(t+t)- p₁(t) = p₀(t)₁t+ p₄(t)₃t+ p₆(t)₂t-(₁+₂ +₃) p₁(t) t;

₁ p₀(t)+ ₃ p₄(t) +₂ p₆(t)-(₁+₂ +₃) p₁(t) _.

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

₁ p₀(t)+ ₃ p₄(t) +₂ p₆(t)-(₁+₂ +₃) p₁(t)

или ₁ p₀+ ₃ p₄(t) +₂ p₆-(₁+₂ +₃) p_1. (8.2)

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

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

p₀ +p_l +p₂ +p₃ +p₄ +p₅+p₆ +p₇ =1. (4)

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

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

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

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

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

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

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

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

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

(6)

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

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

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

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

(6)

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

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

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

₁=1; ₂=2; ₃=1; ₁=2; ₂=4; ₃=2.

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

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

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

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

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

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

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

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

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

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

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

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

P₀= 0,46940 *0,21146=0,1007;

P₆ =0,06678 *0,107 +0,1731 *0,2146=0,04387;

P₅= 0,1608*0,1007+0,09232*0,04387+0,2801*0,2146=0,08035;

P₄=0,07692*0,1007+0,1538*0,08035+0,1538*0,04387+0,7692*0,2146=0,08035;

P₃=0,2*0,1007+0,8*0,080035+0,4*0,1853=0,1585;

P₂=0,3333*0,1007+0,3333*0,08035+0,3333*0,04387=0,07498;

P₁=0,2*0,1007+0,4*0,1853+0,8*0,04387=0,1294.

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

p₀+p₁+p₂+p₃+p₄+p₅+p₆+p₇=1

0,1294+0,07498+0,1585+0,1853+0,08035+0,043870+0,04387+0,1007+0,2146=0,9877

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

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

Решить систему уравнений примера 1 с данными:

₁=2; ₂=1; ₃=3; ₁=4; ₂=2; ₃=4.

Самостоятельная работа №19: Подготовить сообщение «Область применимости теории принятия решений»

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача экстраполяции формируется так: пусть в интервале (t₀, t) известны значения функции f(x), требуется определить значения этой функции в точке t+1, лежащей вне этого интервала.

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

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

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

Класс 2а: на всём интервале развития наблюдаются экспоненциальный рост. Уравнение кривой для функции этого класса имеет вид y = Ae^at, где А - значение процесса при t = 0; а - параметр процесса. Необходимо отметить, что этот процесс является линейным для логарифма рассматриваемой функции lnA = lnA+at.

Класс 2б: S-образные кривые, характеризующие начальным экспоненциальным или почти экспоненциальным ростом. Такие кривые часто используются для прогнозирования плотности телефонов в целом по стране или большому району. Примером функции класса 2б служит кривая логического роста (кривая Перла) y = L/(l+a₀e^-alt), где L - предел развития объекта; a₀, a₁ - константы; t - время.

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

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

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

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

при j = 1…m, где a_i - коэффициент модели, i = 0…n; u_ij - значения i-й функции независимой переменной; n - число независимых переменных в модели, ξ_i - случайная ошибка.

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

Метод группового учета аргументов (МГУА)

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

Критерий называется внешним, если его определение основано на новой информации, неиспользованной при синтезе модели.

Суть принципа самоорганизации моделей оптимальной сложности состоит в том, что при постепенном усложнении математической модели отдельные её элементы проверяются в соответствии с внешними критериями, после этого часть модели допускается для дальнейшего усложнения. МГУА направлен на уменьшение необходимой априорной информации, вводимой в ЭВМ. В память ЭВМ вводят небольшую таблицу (например, 10-20 точек) и указывают критерий выбора модели, по которому машина находит объективную единственную модель оптимальной сложности.

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

Алгоритм МГУА с последовательным выделением трендов позволяет создавать модели множественной регрессии, основу которых составляет сумма уравнений регрессии по одному аргументу. По этому алгоритму расчет ведется следующим образом: первоначально определяется первый тренд и рассчитывается соответствующее отклонение истинных значений функции от тренда. Затем полученные отклонения аппроксимируются вторым трендом и определяется второй остаток. Число выделяемых трендов зависит от размерности функции. Их может быть два, три, четыре и более. Полученные значения трендов складываются. Окончательное выражение множественной регрессии:

y = Σa_0j+a₁f(x₁)+a₂f(x₂)+…+a_nf(x_n),

где a_0j - свободный член j-го тренда.

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

Результат перебора - оптимальная комбинация, дающая наиболее регулярные решения.

При проведении расчётов по алгоритму МГУА таблица исходных данных делится на две части: обучающая (A) и проверяющая (B). Деление исходных данных проводят в отношении:

N_A = 0,7N и N_B = 0,3N или N_A = 0,5N и N_B = 0,5N, где N - общее число данных.

В качестве критерия получения оптимальной модели МГУА используется минимум Самостоятельная работа №еднеквадратичной ошибки на проверочной последовательности данных: первая разность прогнозных и реальных значений Δ(1) или минимум Самостоятельная работа №еднеквадратичной ошибки приращений; вторая разность прогнозных и реальных значений Δ(2).

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

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

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

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

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

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

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

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

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

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

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

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

где B_j - значение прогнозируемой величины, данной 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. Имеются следующие данные о величине пробега автомобиля (тыс. км) и - расходе масла (л/тыс. км):

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

Решение:

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

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

Ее решение , .

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

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

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

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

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

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

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

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

А₀=394,209/61,25=-6,44

А₁= 147,6733/61,25= 2,41

А₂=12,0706/61,25= -0,20

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

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

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

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. Форма доступа: sgtek.ru

2. Информационно-справочная система «В помощь студентам». Форма доступа: window.edu.ru

3. Информационно-справочная система. Форма доступа: http://dit.isuct.ru.

4. Информационно-справочная система. Форма доступа: resolventa.ru