МЕТОДИЧЕСКИЕ УКАЗАНИЯ для практических занятий по дисциплине «Математические методы» для студентов 3 курса (специальность Программирование в компьютерных системах)
ДЕПАРТАМЕНТ ОБРАЗОВАНИЯ, НАУКИ И МОЛОДЕЖНОЙ ПОЛИТИКИ ВОРОНЕЖСКОЙ ОБЛАСТИ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ СРЕДНЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ВОРОНЕЖСКОЙ ОБЛАСТИ
«СЕМИЛУКСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИКО-ЭКОНОМИЧЕСКИЙ КОЛЛЕДЖ»
методические указания
для практических занятий
по дисциплине «Математические методы»
для студентов 3 курса
(специальность 230115 Программирование в компьютерных системах)
Семилуки , 2014
Одобрено методическим советом ГОБУ СПО ВО «СГТЭК»
Автор-составитель: Евдокимова М.Д., преподаватель ГОБУ СПО ВО «СГТЭК»
Учебное пособие содержит указания для практических занятий по «Математические методы», являющейся естественно-научной дисциплиной. Методические указания составлены в соответствии с рабочей программой по дисциплине «Математические методы» и предназначены для студентов 3-го курса, обучающихся по специальности 230115 Программирование в компьютерных системах
© Евдокимова М.Д., 2014
©ГОБУ СПО ВО «СГТЭК»
Оглавление
стр
Введение
4
Оценка практических занятий обучающихся
6
Общая классификация ошибок
6
Раздел 1. Основные понятия и принципы моделирования
8
Практическое занятие №1 «Составление простейших математических моделей задач, возникающих в практической деятельности людей»
8
Практическое занятие №2 «Решение простейших однокритериальных задач»
13
Раздел 2. Основные методологические подходы к решению математических задач, возникающих в ходе практической деятельности людей
17
Практическое занятие №3 «Выбор и обоснование наиболее рационального метода и алгоритма решения задачи, а также оценка сложности выбранного алгоритма: геометрический метод, симплекс метод»
17
Практическое занятие №4 «Выбор и обоснование наиболее рационального метода и алгоритма решения транспортной задачи, а также оценка сложности выбранного алгоритма: метод потенциалов»
28
Практическое занятие №5 «Решение задач НП графическим методом и методом Лагранжа. Разработка алгоритма для решения различных практических задач с применением математических методов»
35
Практическое занятие №6 «Решение задач о распределении средств между предприятиями и замене оборудования»
40
Практическое занятие №7 «Нахождение кратчайшего пути в графе. Разработка алгоритма для решения различных практических задач с применением математических методов»
46
Раздел 3. Основные методы решения детерминированных задач и задач в условиях неопределенности, возникающих в практической деятельности
53
Практическое занятие №8 «Составление систем уравнений Колмогорова. Нахождение финальных вероятностей. Выбор и обоснование наиболее рационального метода и алгоритма решения задачи, а также оценка сложности выбранного алгоритма»
53
Практическое занятие №9 «Решение задачи управления запасами и задачи теории СМО, используя имитационное моделирование»
66
Практическое занятие №10 «Построение прогнозов количественными и качественными методами. Выбор и обоснование наиболее рационального метода и алгоритма решения задачи, а также оценка сложности выбранного алгоритма»
72
Литература
77
Введение
Методические указания к выполнению практических занятий по дисциплине «Математические методы» предназначены для закрепления теоретических знаний, полученных на лекциях, а также для овладения студентами умений и навыков применять эти знания при самостоятельной работе.
Перечень практических занятий соответствует рабочей программе по дисциплине «Математические методы»
Выполнение студентами практических занятий по дисциплине проводится с целью:
- закрепления полученных теоретических знаний по дисциплине;
- углубления теоретических знаний в соответствии с заданной темой;
- формирования умений решать практические задачи;
- развития самостоятельности, ответственности и организованности;
- формирования активных умственных действий студентов, связанных с поисками рациональных способов выполнения заданий;
- подготовки к экзамену.
Методические указания выполняют функцию управления самостоятельной работой студента, поэтому каждое занятие имеет унифицированную структуру, включающую определение целей занятия, оснащения занятия, порядок выполнения работы, а также задания и контрольные вопросы для закрепления темы.
Содержание заданий практического занятия ориентировано на подготовку студентов к освоению профессиональных модулей ОПОП по специальности 230115 Программирование в компьютерных системах и овладению профессиональными компетенциями:
ПК 1.1. Выполнять разработку спецификаций отдельных компонент.
ПК 1.7.в Осуществлять разработку кода программного продукта для решения различных практических задач с применением математических методов.
ПК 2.5.в Реализовывать основные методологические подходы к решению математических задач, возникающих в ходе практической деятельности людей при работе в базе данных.
В процессе освоения дисциплины у студентов должны формироваться общие компетенции:
ОК 1. Понимать сущность и социальную значимость своей будущей профессии, проявлять к ней устойчивый интерес.
ОК 2. Организовывать собственную деятельность, выбирать типовые методы и способы выполнения профессиональных задач, оценивать их эффективность и качество.
ОКЗ. Принимать решения в стандартных и нестандартных ситуациях и нести за них ответственность.
ОК 4. Осуществлять поиск и использование информации, необходимой для эффективного выполнения профессиональных задач, профессионального и личностного развития.
ОК 5. Использовать информационно-коммуникационные технологии в профессиональной деятельности.
ОК 6. Работать в коллективе и команде, эффективно общаться с коллегами, руководством, потребителями.
ОК 7. Брать на себя ответственность за работу членов команды (подчиненных), результат выполнения заданий.
ОК 8. Самостоятельно определять задачи профессионального и личностного развития, заниматься самообразованием, осознанно планировать повышение квалификации.
ОК 9. Ориентироваться в условиях частой смены технологий в профессиональной деятельности.
ОК 10. Исполнять воинскую обязанность, в том числе с применением полученных профессиональных знаний (для юношей).
В результате освоения учебной дисциплины обучающийся должен уметь:
составлять простейшие математические модели задач, возникающих в практической деятельности людей;
выбирать наиболее рациональный метод и алгоритм решения задачи, а также оценивать сложность выбранного алгоритма;
разрабатывать алгоритмы для решения различных практических задач с применением математических методов.
В результате освоения учебной дисциплины обучающийся должен знать:
основные понятия и принципы моделирования;
основные методологические подходы к решению математических задач, возникающих в ходе практической деятельности людей;
основные методы решения детерминированных задач и задач в условиях неопределенности, возникающих в практической деятельности.
В методических указаниях приведены теоретический (справочный) материал в соответствии с темой занятия, обращение к которому поможет выполнить задания.
Организация выполнения и контроля практических занятий по дисциплине «Математические методы» является подготовительным этапом к сдаче экзамена по данной дисциплине.
Нормы оценки знаний, умений и навыков обучающихся по дисциплине
Оценка практических занятий обучающихся
Ответ оценивается отметкой «5», если:
работа выполнена полностью;
в логических рассуждениях и обосновании решения нет пробелов и ошибок;
в решении нет математических ошибок (возможна одна неточность, описка, которая не является следствием незнания или непонимания учебного материала).
Отметка «4» ставится в следующих случаях:
работа выполнена полностью, но обоснования шагов решения недостаточны (если умение обосновывать рассуждения не являлось специальным объектом проверки);
допущены одна ошибка или есть два – три недочёта в выкладках, рисунках, чертежах или графиках (если эти виды работ не являлись специальным объектом проверки).
Отметка «3» ставится, если:
допущено более одной ошибки или более двух – трех недочетов в выкладках, чертежах или графиках, но обучающийся обладает обязательными умениями по проверяемой теме.
Отметка «2» ставится, если:
допущены существенные ошибки, показавшие, что обучающийся не обладает обязательными умениями по данной теме в полной мере.
Отметка «1» ставится, если:
работа показала полное отсутствие у обучающегося обязательных знаний и умений по проверяемой теме или значительная часть работы выполнена не самостоятельно.
Учитель может повысить отметку за оригинальный ответ на вопрос или оригинальное решение задачи, которые свидетельствуют о высоком математическом развитии обучающегося; за решение более сложной задачи или ответ на более сложный вопрос, предложенные обучающемуся дополнительно после выполнения им каких-либо других заданий
Общая классификация ошибок
При оценке знаний, умений и навыков учащихся следует учитывать все ошибки (грубые и негрубые) и недочёты.
Грубыми считаются ошибки:
незнание определения основных понятий, законов, правил, основных положений теории, незнание формул, общепринятых символов обозначений величин, единиц их измерения;
незнание наименований единиц измерения;
неумение выделить в ответе главное;
неумение применять знания, алгоритмы для решения задач;
неумение делать выводы и обобщения;
неумение читать и строить графики;
неумение пользоваться первоисточниками, учебником и справочниками;
потеря корня или сохранение постороннего корня;
отбрасывание без объяснений одного из них;
равнозначные им ошибки;
вычислительные ошибки, если они не являются опиской;
логические ошибки.
К негрубым ошибкам следует отнести:
неточность формулировок, определений, понятий, теорий, вызванная неполнотой охвата основных признаков определяемого понятия или заменой одного - двух из этих признаков второстепенными;
неточность графика;
нерациональный метод решения задачи или недостаточно продуманный план ответа (нарушение логики, подмена отдельных основных вопросов второстепенными);
нерациональные методы работы со справочной и другой литературой;
неумение решать задачи, выполнять задания в общем виде.
Недочетами являются:
нерациональные приемы вычислений и преобразований;
небрежное выполнение записей, чертежей, схем, графиков.
Раздел 1. Основные понятия и принципы моделирования
Практическое занятие №1
«Составление простейших математических моделей задач, возникающих в практической деятельности людей»
Цели занятия:
1. Отработать и закрепить умения записывать условие задачи в виде математических формул.
2. Отработать и закрепить умения записывать взаимосвязь показателей задачи в виде математической модели.
Методические указания к выполнению заданий практического занятия
Математическая модель любой задачи линейного программирования включает в себя:
максимум или минимум целевой функции (критерий оптимальности);
систему ограничений в форме линейных уравнений и неравенств;
требование неотрицательности переменных.
Таким образом, экономико-математическая формулировка и модель общей задачи линейного программирования имеют следующий вид:
найти максимальное (минимальное) значение линейной целевой функции
13 EMBED Equation.3 1415
при условиях-ограничениях:
13 EMBED Equation.3 141513 EMBED Equation.3 141513 EMBED Equation.3 1415
где aij, bi, cj – заданные постоянные величины.
Пример. Фирма выпускает 2 вида мороженного: сливочное и шоколадное. Для изготовления используются 2 исходных продукта: молоко и наполнители, расходы которых на 1 кг мороженного и суточные запасы исходных продуктов даны в таблице.
Исходный продукт
Расход исходных продуктов на 1 кг мороженного
Запас, кг
Сливочное
Шоколадное
Молоко
0.8
0.5
400
Наполнители
0.4
0.8
365
Изучение рынка сбыта показало, что суточный спрос на сливочное мороженное превышает спрос на шоколадное мороженное не более чем на 100 кг. Кроме того, установлено, что спрос на шоколадное мороженное не превышает 350 кг в сутки. Отпускная цена 1 кг сливочного мороженного 16 ден.ед., шоколадного - 14 ден.ед. Определить количество мороженого каждого вида, которое должна производить фирма, чтобы доход от реализации продукции был максимальным.
Решение:
Составляем математическую модель задачи.
Вводим обозначения (переменные величины):
х 1 – суточный объем выпуска сливочного мороженного, кг;
х 2 - суточный объем выпуска шоколадного мороженного, кг
Целевая функция:
f = 16 х 1 + 14 х 2max
при ограничениях:
0.8 х 1 + 0.5 х 2
· 400 (ограничение по молоку);
0.4 х 1 + 0.8 х 2
· 365 (ограничение по наполнителям);
х 1 + х 2
· 100 (рыночное ограничение по спросу);
х 2
· 350 (рыночное ограничение по спросу);
х 1
· 0, х 2
· 0
Вариант 1
Задание: построить математическую модель к задаче, пояснить условные обозначения.
1. Рацион кормления коров на ферме состоит из 3х продуктов, содержащих белки, кальций и витамины. Потребность одной коровы в сутки – не менее 2000 г белков и 210 г кальция. Потребность в витаминах строго дозирована и составляет 0,087 г в сутки.
Содержание питательных веществ
Белки г/кг
Кальций г/кг
Витамины г/кг
Сено
50
10
2
Силос
70
6
3
Концентраты
180
3
1
Составить самый дешевый рацион, если цена 1 кг сена, силоса и концентратов составляет соответственно 1,5 2,0 6,0 у.е.
2. Завод производит продукцию 3х типов: П1, П2, П3. Для производства каждого изделия необходимо 3 технологические операции: О1, О2, О3. В день можно производить не более 170 единиц продукции. Найти наиболее прибыльный план производства.
Операции
Объем работ на 1 изделие (чел.-час)
Дневной фонд времени, час
П1
П2
П3
О1
2
3
2
360
О2
1
2
3
240
О3
1
1
2
180
Прибыль от 1-го изделия, $
15
22
19
В какой операции наиболее целесообразны сверхурочные работы, максимально увеличивающие фонд рабочего времени, если их стоимость $4 (чел.-час)?
3. Фирма производит для автомобилей запасные части типа А и В. Фонд рабочего времени составляет 5000 чел.-ч в неделю. Для производства одной детали типа А требуется 1 чел.-ч, а для производства одной детали типа В - 2 чел.-ч. Производственная мощность позволяет выпускать максимум 2500 деталей типа А и 2000 деталей типа В в неделю. Для производства детали типа А уходит 2 кг полимерного материала и 5 кг листового материала, а для производства одной детали типа В 4 кг полимерного ма териала и 3 кг листового металла. Еженедельные запасы каждо го материала - по 10 000 кг. Общее число производимых деталей в течение одной недели должно составлять не менее 1500 штук. Определите, сколько деталей каждого вида следует произ водить, чтобы обеспечить максимальный доход от продажи за неделю, если доход от продаж одной детали типа А и В состав ляет соответственно 1,1 руб. и 1,5 руб.
Вариант 2
Задание: построить математическую модель к задаче, пояснить условные обозначения.
1. Туристская фирма в летний сезон обслуживает в среднем 7500 туристов и располагает флотилией из двух типов судов, характеристики которых представлены в таблице.
В месяц выделяется 60 000 т горючего. Потребность в рабочей силе не превышает 700 человек.
Определите количество судов I и II типа, чтобы обеспечить максимальный доход, который составляет от эксплуатации судов I типа 20 млн руб., а II типа - 10 млн руб. в месяц.
2. Для сохранения здоровья и работоспособности человек должен употреблять в сутки некоторое количество белков, жиров, углеводов и витаминов. Имеются два вида пищи: I и II. Содержание питательных веществ в I кг пищи, суточная норма и стоимость одного кг пищи каждого вида даны в таблице.
Питательные вещества
Вид пищи
Суточная норма
I
II
Жиры
Белки
Углеводы
Витамины
1
4
2
0
10/3
2
2/8
1
10
12
14
1
Стоимость 1 кг
20 коп.
24 коп.
Как нужно организовать питание, чтобы пища содержала необходимое количество питательных веществ, а стоимость была бы минимальной?
3. Обработка деталей А и В может производиться на трех станках. Причем каждая деталь при ее изготовлении должна последовательно обрабатываться на каждом из станков. Прибыль от реализации детали А – 100 ден. ед., детали В – 160 ден. ед. Исходные данные приведены в таблице. Определить производственную программу, максимизирующую прибыль при условии: спрос на деталь А не менее 300 шт., на деталь В - не более 200 шт.
Станок
Норма времени на обработку одной детали, ч
Время работы станка, ч
А
В
1
0,2
0,1
100
2
0,2
0,5
180
3
0,1
0,2
100
Вариант 3
Задание: построить математическую модель к задаче, пояснить условные обозначения.
В процессе производства два изделия А и В должны пройти обработку на станках I, II и III. Время обработки каждого изделия на каждом из этих станков задано таблицей
Станки
Изделия
I
II
III
А В
1 1/4
4 2
1 4
Станки можно использовать соответственно в течение 45, 100 и 60 часов. Продажная цена изделия А–6 рублей, а изделия В–4 рубля. В каком соотношении следует производить изделия А и В, чтобы получить максимальную прибыль?
Малое предприятие арендовало минипекарню для произ водства чебуреков и беляшей. Мощность пекарни позволяет вы пускать в день не более 50 кг продукции. Ежедневный спрос на чебуреки не превышает 260 штук, а на беляши 240 штук. Суточные запасы теста и мяса и расходы на производство каж дой единицы продукции приведены в таблице. Определить оп тимальный план ежедневного производства чебуреков и беля шей, обеспечивающих максимальную выручку от продажи.
Расход на производство, кг/шт.
Суточные запасы сырья, кг
чебурека
беляша
Мясо
0,35
0,6
21
Тесто
0,65
0,3
22
Цена, руб-/кг
50,0
80,0
3. АО «Механический завод» при изготовлении двух типов деталей использует токарное, фрезерное и сварочное оборудование. При этом обработку каждой детали можно вести двумя различными технологическими способами. Необходимые исходные данные приведены в таблице. Составить оптимальный план загрузки оборудования, обеспечивающий заводу максимальную прибыль.
Оборудование
Деталь
Полезный фонд времени, станко-ч
1
2
Технологический способ
1
2
1
2
Фрезерное
2
2
3
0
20
Токарное
3
1
1
2
37
Сварочное
0
1
1
4
30
Прибыль, ден.ед
11
6
9
6
Вариант 4
Задание: построить математическую модель к задаче, пояснить условные обозначения.
Фирма производит и продает столы и шкафы из древеси ны хвойных и лиственных пород. Расход каждого вида в кубо метрах на каждое изделие задан в таблице.
Расход древесины, м3
Цена изделия, тыс. руб.
хвойные
лиственные
Стол
0,15
0,2
0,8
Шкаф
0,3
0,1
1.6
Запасы древесины, м3
80
40
Определите оптимальное количество столов и шкафов, которое следует поставлять на продажу для получения максималь ного дохода фирмы.
2. Фирма решила открыть на основе технологии производ ства чешского стекла, фарфора и хрусталя линию по изготовлению ваз и графинов и их декорирование. Затраты сырья на производство этой продукции представлены в таблице.
Сырье
Расход сырья на производство
Поставки сырья в неделю, кг
ваза
графин
Кобальт
20
18
30
Сусальное 24-каратное золото
13
10
12
Оптовая цена, руб./шт.
700
560
Определите оптимальный объем выпуска продукции, обес печивающий максимальный доход от продаж, если спрос на вазы не превышает 200 шт. в неделю.
3. Фирма производит два безалкогольных широко популяр ных напитка «Колокольчик» и «Буратино». Для производства 1 л. «Колокольчика» требуется 0,02 ч работы оборудования, а для «Буратино» - 0,04 ч, а расход специального ингредиента на них составляет 0,01 кг и 0,04 кг на 1 л соответственно. Ежедневно в распоряжении фирмы 16 кг специального ингредиента и 24 ч работы оборудования. Доход от продажи 1 л «Колокольчика» составляет 0,25 руб., а «Буратино» - 0,35 руб. Определите ежедневный план производства напитков каждо го вида, обеспечивающий максимальный доход от их продажи.
Контрольные вопросы:
Что такое математическое моделирование?
Что такое модель?
Классификация моделей.
Алгоритм моделирования в задачах коммерческой деятельности.
Классификация математических моделей.
Практическое занятие №2
«Решение простейших однокритериальных задач»
Цели занятия:
1. Отработать и закрепить умения графически решать системы неравенств с двумя переменными.
2. Отработать и закрепить умения записывать взаимосвязь показателей задачи в виде математической модели.
Методические указания к выполнению заданий практического занятия
Решение системы неравенств с двумя переменными графическим методом включает следующие этапы.
1. На плоскости Х1ОХ2 строят прямые, уравнения которых получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств.
2. Находят полуплоскости, определяемые каждым из неравенств.
3. Строят многоугольник решений.
Пример:
Решить систему неравенств графическим способом.13 EMBED Equation.3 1415
13 EMBED Equation.DSMT4 1415
Решение:
Шаг 1. Строим область допустимых решений - область Р, т.е. геометрическое место точек, в котором одновременно удовлетворяются все ограничения ЗЛП. Каждое из неравенств (а)-(д) системы ограничений задачи геометрически определяет полуплоскость соответственно с граничными прямыми:
13 EMBED Equation.DSMT4 1415
Условия неотрицательности переменных (е) ограничивают область допустимых решений первым квадратом. Области, в которых выполняются соответствующие ограничения в виде неравенств, указываются стрелками, направленными в сторону допустимых значений переменных
Решение системы – многоугольник ABCDEF.
Вариант 1
Решить графически систему неравенств:
а) x1 + x2
· 5
3x1 - x2
· 3
x1
·0, x2
·0
б) x1 + x2
· 4
6x1 + 2x2
· 6
x1 + 5x2
· 5
x1
·0, x2
·0
Составить математическую модель задачи и найти решение системы ограничений:
Чулочно-носочная фирма производит и продает два вида товаров: мужские носки и женские чулки. Фирма получает прибыль в размере 10 руб. от производства и продажи одной пары чулок и в размере 4 руб. от производства и продажи одной пары носков. Производство каждого изделия осуществляется на трех участках. Затраты труда (в часах) на производство одной пары указаны в следующей таблице для каждого участка:
Участок производства
Чулки
Носки
1
0,02
0,01
2
0,03
0,01
3
0,03
0,02
Руководство рассчитало, что в следующем месяце фирма ежедневно будет располагать следующими ресурсами рабочего времени на каждом из участков: 60 ч на участке 1; 70 ч на участке 2 и 100 ч на участке 3. Сколько пар носков и чулок следует производить ежедневно, если фирма хочет максимизировать прибыль?
Вариант 2
Решить графически систему неравенств:
а) x1 + x2
· 5
3x1 - x2
· 3
x1
·0, x2
·0
б) x1 - x2
· 3
x1 + x2
· 9
-x1 + x2
· 3
x1 + x2
· 3/2
x1
·0, x2
·0
Составить математическую модель задачи и найти решение системы ограничений:
После предпринятой рекламной компании фирма «Отдых» испытывает рост спроса на два типа мангалов для приготовления шашлыков на открытом воздухе – газовые и угольные. Фирма заключила контракт на ежемесячную поставку в магазины 300 угольных и 300 газовых мангалов. Производство мангалов ограничивается мощностью следующих трех участков: производства деталей, сборки и упаковки. В таблице показано, сколько человекочасов затрачивается на каждом участке на каждую единицу продукции, а также приведен допустимый ежемесячный объем трудозатрат:
Участок
Трудозатраты на производство одного мангала, ч
Фонд времени, человекочасы
угольного
газового
Производство
5
8
2600
Сборка
0,8
1,2
400
Упаковка
0,5
0,5
200
Вариант 3
Решить графически систему неравенств:
а) x1 + 3x2
· 3
-2x1 + x2
· 2
x1 + x2
· 5
x1
·0, x2
·0
б) -x1 + 3x2
· 9
2x1 + 3x2
· 18
2x1 - x2
· 10
x1
·0, x2
·0
Составить математическую модель задачи и найти решение системы ограничений:
Предприятие располагает ресурсами сырья, рабочей силы и оборудованием, необходимыми для производства любого из четырех видов производимых товаров. Затраты ресурсов на изготовление единицы каждого вида товара и прибыль, получаемая предприятием, а также объем ресурсов указаны в таблице. Составить план выпуска товаров, дающий максимальную прибыль.
Ресурсы
Затраты ресурсов на 1 ед. товара
Объем ресурсов
1
2
3
4
Сырье, кг
3
5
2
4
60
Рабочая сила, чел.
22
14
18
30
400
Оборудование, станко-ч
10
14
8
16
130
Прибыль на 1 ед.товара, руб.
30
25
56
48
Вариант 4
Решить графически систему неравенств:
а) x1 + 3x2
· 3
-2x1 + x2
· 2
x1 + x2
· 5
x1
·0, x2
·0
б) x1 - x2
· 3
2x1 + x2
· 3
x1 - 3x2
· 1
x1
·0, x2
·0
Составить математическую модель задачи и найти решение системы ограничений:
Обработка деталей А и В может производиться на трех станках. Причем каждая деталь при ее изготовлении должна последовательно обрабатываться на каждом из станков. Прибыль от реализации детали А – 100 ден. ед., детали В – 160 ден. ед. Исходные данные приведены в таблице. Определить производственную программу, максимизирующую прибыль при условии: спрос на деталь А не менее 300 шт., на деталь В - не более 200 шт.
Станок
Норма времени на обработку одной детали, ч
Время работы станка, ч
А
В
1
0,2
0,1
100
2
0,2
0,5
180
3
0,1
0,2
100
Раздел 2. Основные методологические подходы к решению математических задач, возникающих в ходе практической деятельности людей
Практическое занятие №3
«Выбор и обоснование наиболее рационального метода и алгоритма решения задачи, а также оценка сложности выбранного алгоритма: геометрический метод, симплекс метод»
Цели занятия:
1. Научиться решать задачи геометрическим методом.
2. Научиться решать задачи симплексным методом.
3. Закрепить навыки записи взаимосвязи показателей задачи в виде математической модели.
Методические указания к выполнению заданий практического занятия
Линейное программирование
Линейное программирование – это направление математического программирования, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием.
Линейное программирование состоит в нахождении экстремального значения линейной функции многих переменных при наличии линейных ограничений, связывающих эти переменные.
Необходимым условием постановки задачи линейного программирования являются ограничения на наличие ресурсов, величину спроса, производственную мощность предприятия и другие производственные факторы.
Математическая модель любой задачи линейного программирования включает в себя:
максимум или минимум целевой функции (критерий оптимальности);
систему ограничений в форме линейных уравнений и неравенств;
требование неотрицательности переменных.
Таким образом, экономико-математическая формулировка и модель общей задачи линейного программирования имеют следующий вид:
найти максимальное (минимальное) значение линейной целевой функции
13 EMBED Equation.3 1415
при условиях-ограничениях:
13 EMBED Equation.3 141513 EMBED Equation.3 141513 EMBED Equation.3 1415
где aij, bi, cj – заданные постоянные величины.
Стандартной задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения целевой функции (1) при выполнении условий (2) и (4).
Канонической (или основной) задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения целевой функции (1) при выполнении условий (3) и (4).
Графический метод решения двумерной задачи линейного программирования (максимизация целевой функции)
Двумерная задача линейного программирования – задача линейного программирования, количество переменных которой равно 2.
В общем виде двумерную задачу линейного программирования можно представить следующим образом.
Определить значение переменных x1 и x2, при которых линейная целевая функция F достигает максимума (минимума).
F = c1x1+c2x2 max(min) при ограничениях на переменные
[ Cкачайте файл, чтобы посмотреть картинку ]
Среди ограничений могут одновременно встречаться знаки
·,
· и =. Коэффициенты aij, bi, cj (i = 1..m, j = 1,2) - любые действительные числа (возможно и 0).
Двумерные задачи линейного программирования обычно решаются графически и решение связано со свойствами выпуклых множеств.
Множество точек называется выпуклым, если оно вместе с любыми двумя точками содержит и их произвольную выпуклую комбинацию.
Геометрический смысл этого определения состоит в том, что множеству вместе с его произвольными точками полностью при надлежит и прямолинейный отрезок, их соединяющий. Приме рами выпуклых множеств являются прямолинейный отрезок, полуплоскость, круг, шар, куб, полупространство и др.
Множество планов основной задачи линейного программи рования является выпуклым (если оно не пусто). Непустое мно жество планов называется многогранником решений, а всякая угловая точка многогранника решений - вершиной.
Если основная задача линейного программирования имеет оптимальный план, то целевая функция задачи принимает мак симальное значение в одной из вершин многогранника решений. Если максимальное значение достигается более чем в одной вершине, то целевая функция принимает его во всякой точке, являющейся выпуклой линейной комбинацией этих вершин.
Алгоритм решения двумерной задачи линейного программирования графическим методом
Решение задачи линейного программирования графическим методом включает следующие этапы.
1. На плоскости Х1ОХ2 строят прямые, уравнения которых получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств.
2. Находят полуплоскости, определяемые каждым из огра ничений задачи.
3. Строят многоугольник решений.
4. Строят векторN(с1, c2), который указывает направление возрастания целевой функции.
5. Строят начальную прямую целевой функции с1х1 + с2х2 =0 и затем передвигают ее в направлении вектора N до крайней угловой точки многоугольника решений. В результате находят точку, в которой целевая функция принимает максимальное значение, либо множество точек с одинаковым максимальным значением целевой функции, если начальная прямая сливается с одной из сторон многоугольника решений, либо устанавливают неограниченность сверху функции на множестве планов.
6. Определяют координаты точки максимум функции и вычисляют значение целевой функции в этой точке.
Минимальное значение линейной функции цели находится путем передвижения начальной прямой с1х1 + с2х2 = 0 в направлении, противоположном вектору N(c1,c2).
Замечание 1: В алгоритме решения пункты 4-6 можно выполнять следующим образом:
4. Найти значение целевой функции в угловых точках многогранника решений.
5. Точка, в которой функция принимает наибольшее значение и является точкой максимума.
Пример 1
На предприятии имеется сырье видов I, II, III. Из него можно изготавливать изделия типов А и В. Пусть запасы видов сырья на предприятии составляют b1, b2 , b3 ед. соответственно, изделие типа А дает прибыль c1 ден. ед., а изделие типа В – c2 ден. ед. Расход сырья на изготовление одного изделия задан в условных единицах таблицей. Составить план выпуска изделий, при котором предприятие имеет наибольшую прибыль. Решить задачу графически и симплексным методом.
Изделие
Сырье
b1
b2
b3
c1
c2
I
II
III
150
260
300
6
3
А
3
4
3
В
1
3
4
Решение. Составим математическую модель задачи. Обозначим: x1 – количество выпускаемых изделий типа A, x2 - количество выпускаемых изделий типа B . Тогда с учетом расходов сырья на изготовление изделия каждого типа получим следующие ограничения на x1 и x2 , учитывающие запасы сырья каждого вида:
13 EMBED Equation.3 1415 (1)
По смыслу задачи
13 EMBED Equation.3 1415
Прибыль F предприятия при плане x1, x2 равна
13 EMBED Equation.3 1415. (3)
Итак, математическая модель задачи получена: необходимо найти значения x1, x2 , удовлетворяющие неравенствам (1), (2), для которых функция (3) достигает наибольшего значения. Полученная задача – стандартная задача линейного программирования.
Решим полученную задачу графически.
Для этого введем систему координат x1Ox2 и изобразим в ней множество решений систем неравенств (1), (2) (область допустимых решений - ОДР) в виде множества точек плоскости.
Условию (2) удовлетворяют точки первой четверти. Для получения полуплоскостей, соответствующих неравенствам системы (1), построим их границы, т.е. прямые линии:
Имя прямой
Уравнение прямой
Таблица для построения прямой
(а)
13 EMBED Equation.3 1415
х1
0
50
х2
150
0
(б)
13 EMBED Equation.3 1415
х1
0
65
х2
260/3
0
(в)
13 EMBED Equation.3 1415
х1
0
100
х2
75
0
Пересечение построенных полуплоскостей с первой четвертью – искомая ОДР (многоугольник OABCD, рис.1.1.).
Ищем координаты вершин ОДР и значения целевой функции F в этих вершинах:
O(0; 0): F(O)=6*0+3*0=0$
A(0;75): F(A)=6*0+3*75=225;
13 EMBED Equation.3 1415
F(B)=6*20+3*60=300
13 EMBED Equation.3 1415
F(C)=6*38+3*36=336
D(50;0)
F(D)=6*50+3*0=300.
Отсюда
Fmax= F(C)= F(38;36)=336.
Вывод: предприятию выгодно выпустить 38 изделий типа A(х1=38) и 36 изделия типа B (х2=36). При этом его прибыль будет наибольшая и составит 336 ден. ед.
Симплекс-метод метод решения задачи линейного программирования
Для решения задач линейного программирования предложе но немало различных алгоритмов. Наиболее эффективным сре ди них является алгоритм, известный под названием симплексный метод, или метод последовательного улучшения плана.
Впервые симплексный метод был предложен американским ученым Дж. Данцингом в 1949 г., однако еще в 1939 г. идеи метода были разработаны российским математиком Л.В. Канто ровичем.
Симплексный метод - это итерационный процесс, который начинается с одного решения и в поисках лучшего варианта движется по угловым точкам области возможных решений до тех пор, пока не достигнет оптимального значения, в частности по угловым точкам многоугольника решений, полученного гео метрическим методом.
Симплексный метод основан на последовательном переходе от одного опорного плана задачи линейного программирования к другому, при этом значение целевой функции изменяется.
Алгоритм симплексного метода включает следующие этапы:
1. Составление первого опорного плана. Система ограниче ний задачи, решаемой симплексным методом, задана в виде системы неравенств смысла «<», правые части которых bi > 0. Перейдем от системы неравенств к системе уравнений путем введения неотрицательных дополнительных переменных. Век торы-столбцы при этих переменных представляют собой единич ные векторы и образуют базис, а соответствующие им перемен ные называются базисными:
Решим эту систему относительно базисных переменных:
а функцию цели перепишем в виде уравнения
Полагая, что основные переменные х1 =... =хп =0, получим первый опорный план Х1 = (0, 0, ...,0, b1, b2, ..., bт); F(X1) = 0, который заносим в симплексную табл. Она со стоит из коэффициентов системы ограничений и свободных членов. Последняя строка таблицы называется индексной и за полняется коэффициентами функции цели, взятыми с противо положным знаком.
2. Проверка плана на оптимальность. Если все коэффици енты индексной строки симплексной таблицы при решении за дачи на максимум неотрицательны (> 0), то план является опти мальным. Если найдется хотя бы один коэффициент индексной строки меньше нуля, то план не оптимальный и его можно улуч шить. В этом случае переходим к следующему этапу алгоритма.
3. Определение ведущих столбца и строки. Из отрицатель ных коэффициентов индексной строки выбираем наибольший по абсолютной величине, что и определяет ведущий столбец, кото рый показывает, какая переменная на следующей итерации перейдет из свободных в базисные.
Затем элементы столбца свободных членов симплексной таблицы делим на элементы того же знака (+/+; "/-) ведущего столбца. Результаты заносим в отдельный столбец di, которые будут всегда положительные. Строка симплексной таблицы, соответствующая минимальному значению di, является ведущей. Она определяет переменную xi, которая на следующей итерации выйдет из базиса и станет свободной.
Элемент симплексной таблицы, находящийся на пересече нии ведущих столбца и строки, называют разрешающим и вы деляют кружком.
4. Построение нового опорного плана. Переход к новому плану осуществляется в результате пересчета симплексной таб лицы методом Жордана - Гаусса. Сначала заменим переменные в базисе, т. е. вместо хi , в базис войдет переменная хj, соответ ствующая ведущему столбцу.
Разделим все элементы ведущей строки предыдущей симплек сной таблицы на разрешающий элемент и результаты деления занесем в строку следующей симплексной таблицы, соответствую щую введенной в базис переменной xj. В результате этого на месте разрешающего элемента в следующей симплексной таблице будем иметь 1, а в остальных клетках j столбца, включая клетку столбца индексной строки, записываем нули. Остальные новые элементы нового плана находятся по правилу прямоугольника: НЭ=СТЭ-А. В/РЭ, где СТЭ - элемент старого плана, РЭ - разрешающий элемент, А и В - элементы старого плана, образующие прямоугольник с эле ментами СТЭ и РЭ.
Далее возвращаемся ко второму этапу алгоритма провер ке плана на оптимальность.
При решении задачи линейного программирования на ми нимум целевой функции признаком оптимальности плана явля ются отрицательные значения всех коэффициентов индексной строки симплексной таблицы.
Пример 2.
Предприятие выпускает три вида изделий (N1, N2, N3), используя три вида ресурсов (Р1, Р2, Р3). Запасы ресурсов (З) ограничены. Прибыль от реализации (П) единицы изделия и нормы расхода ресурсов представлены в таблице. Определить ассортимент и объемы выпуска продукции, получаемую прибыль, величину остатков. Найти решение задачи симплексным методом с представлением всех симплексных таблиц и проанализировать полученные результаты.
N1
N2
N3
З
Р1
1
3
4
42
Р2
4
2
2
54
Р3
3
2
2
80
П
2
1
3
Решение: Запишем математическую модель задачи.
Определим вектор 13 EMBED Equation.3 1415, который удовлетворяет условиям
13 EMBED Equation.3 1415
и обеспечивает максимальное значение целевой функции
13 EMBED Equation.3 1415
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных x4, x5, x6:
13 EMBED Equation.3 1415
Полагая, что свободные переменные x1=0, x2=0, x3=0, получим первый опорный план 13 EMBED Equation.3 1415 13 EMBED Equation.3 1415, в котором базисные переменные x4=39, x5=89, x6=59. Следовательно, изделия не производятся, доход равен нулю, а ресурсы не используются. Полученный первый опорный план запишем в симплексную таблицу.
План
СЗ
БП
ЗБП
Значение коэффициентов при
13 EMBED Equation.3 1415
X1
X2
X3
X4
X5
X6
I
0
0
0
x4
x5
x6
42
54
80
1
4
3
3
2
2
4
2
2
1
0
0
0
1
0
0
0
1
42/4=10,5
54/2=27
80/2=40
Индексная строка
13 EMBED Equation.3 1415=0
-2
-1
-3
0
0
0
Первый опорный план неоптимальный, так как в индексной строке находятся отрицательные коэффициенты: -2, -1, -3.
За ведущий столбец выберем столбец, соответствующий переменной x3, так как, сравнивая по модулю, имеем: |-3|>{|-1|,|-2|}.
Вычислим значения 13 EMBED Equation.3 1415 по строкам как частное от деления 13 EMBED Equation.3 1415 и из них выберем наименьшее:
13 EMBED Equation.3 1415
Следовательно, ведущая строка- х4.
Разрешающий элемент равен РЭ=4 и находится на пересечении ведущего столбца и ведущей строки и выделен в таблице.
Формируем следующую часть симплексной таблице. Вместо переменной x4 в план II войдет переменная x3. Строка, соответствующая переменной x3 в плане II, получена в результате деления всех элементов строки x4 плана I на разрешающий элемент РЭ=4. На месте разрешающего элемента в плане II получаем 1. В остальных клетках столба x3 плана II записываем нули.
Таким образом, в новом плане II заполнены строки x3 и столбец x3. Все остальные элементы нового плана II, включая элементы индексной строки, определяются по правилу прямоугольника. Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ=4.
Значение нового элемента в плане II находится из выражения:
13 EMBED Equation.3 1415
Все элементы, расположенные на пересечении строк и столбцов, соответствующих одноименным базисным элементам, равны 1, остальные элементы столбца в базисах векторов, включая индексную строку, равны 0. Аналогично проводятся расчеты по всем строкам таблицы, включая индексную.
Построим вторую симплекс-таблицу:
План
СЗ
БП
ЗБП
Значение коэффициентов при
13 EMBED Equation.3 1415
X1
X2
X3
X4
X5
X6
II
3
0
0
х3
x5
x6
10,5
33
59
0,25
3,5
0,5
0,75
0,5
0,5
1
0
0
0,25
-0,5
-0,5
0
1
0
0
0
1
42
9,43
118
Индексная строка
13 EMBED Equation.3 1415=3-10,5=31,5
-1,25
1,25
0
0,75
0
0
Второй опорный план неоптимальный, так как в индексной строке находятся отрицательные коэффициенты: -1,25.
За ведущий столбец выберем столбец, соответствующий переменной x1.
Вычислим значения 13 EMBED Equation.3 1415 по строкам как частное от деления 13 EMBED Equation.3 1415 и из них выберем наименьшее:
13 EMBED Equation.3 1415
Следовательно, ведущая строка- х5.
Разрешающий элемент равен РЭ=3,5 и находится на пересечении ведущего столбца и ведущей строки и выделен в таблице.
Формируем следующую часть симплексной таблице. Вместо переменной x5 в план III войдет переменная x1. Строка, соответствующая переменной x1 в плане III, получена в результате деления всех элементов строки x5 плана II на разрешающий элемент РЭ=3.5. На месте разрешающего элемента в плане III получаем 1. В остальных клетках столбца x1 плана III записываем нули.
Таким образом, в новом плане III заполнены строки x1 и столбец x1. Все остальные элементы нового плана III, включая элементы индексной строки, определяются по правилу прямоугольника.
Все элементы, расположенные на пересечении строк и столбцов, соответствующих одноименным базисным элементам, равны 1, остальные элементы столбца в базисах векторов, включая индексную строку, равны 0. Аналогично проводятся расчеты по всем строкам таблицы, включая индексную.
Построим третью симплекс-таблицу:
План
СЗ
БП
ЗБП
Значение коэффициентов при
13 EMBED Equation.3 1415
X1
X2
X3
X4
X5
X6
III
3
2
0
х3
x1
x6
8,143
9,429
35,429
1
0
0
0,714
0,143
0,143
1
0
0
0,286
-0,143
-0,143
-0,071
0,286
-0,714
0
0
1
Индексная строка
13 EMBED Equation.3 1415= 3*8,143+2*9,429=
=43,286
0
0,357
0
0,571
0,357
0
Получаем план III, который является оптимальным, так как все коэффициенты в индексной строке 13 EMBED Equation.3 1415 0.
Оптимальный план можно записать так:
13 EMBED Equation.3 1415
Вывод: Для получения максимального дохода 43,286 у.е. предприятию необходимо производить изделий первого вида 9,429 ед., третьего вида – 8,143 ед., изделия второго вида не производятся.
При этом ресурсы первого и второго видов расходуются полностью, ресурсы третьего остаются в количестве 35,429ед.
Задание 1
На предприятии имеется сырье видов I, II, III. Из него можно изготавливать изделия типов А и В. Пусть запасы видов сырья на предприятии составляют b1, b2, b3 ед. соответственно, изделие типа А дает прибыль с1 ден.ед., а изделие типа В - с2 ден.ед. Расход сырья на изготовление одного изделия задан в словных единицах таблицей.
Составить план выпуска изделий, при котором предприятие имеет наибольшую прибыль. Решить задачу графическим методом.
1 вариант
Изделие
Сырье
b1
b2
b3
с1
с2
I
II
III
102
91
105
5
9
А
6
3
2
В
3
4
5
2вариант
Изделие
Сырье
b1
b2
b3
с1
с2
I
II
III
20
36
40
2
5
А
1
1
3
В
3
2
1
3 вариант
Изделие
Сырье
b1
b2
b3
с1
с2
I
II
III
40
34
46
1
2
А
2
1
3
В
2
2
1
4 вариант
Изделие
Сырье
b1
b2
b3
с1
с2
I
II
III
300
520
600
6
3
А
3
4
3
В
1
3
4
Задание 2
Предприятие выпускает три вида изделий (N1, N2, N3), используя три вида ресурсов (Р1, Р2, Р3). Запасы ресурсов (З) ограничены. Прибыль от реализации (П) единицы изделия и нормы расхода ресурсов представлены в таблице. Определить ассортимент и объемы выпуска продукции, получаемую прибыль, величину остатков. Найти решение задачи симплексным методом с представлением всех симплексных таблиц и проанализировать полученные результаты.
Вариант 1
N1
N2
N3
З
Р1
1
8
5
43
Р2
4
1
6
74
Р3
5
2
2
35
П
5
7
6
Вариант 2
N1
N2
N3
З
Р1
3
5
4
81
Р2
6
1
3
74
Р3
1
5
2
33
П
4
8
7
Вариант 3
N1
N2
N3
З
Р1
6
7
2
57
Р2
6
6
1
97
Р3
3
7
8
63
П
5
6
8
Вариант 4
N1
N2
N3
З
Р1
7
8
3
81
Р2
4
1
6
68
Р3
5
1
7
54
П
2
5
6
Контрольные вопросы:
Какие задачи относятся к задачам линейного программирования?
Как определяется область допустимых решений (многоугольник решений)?
Как строится начальный вектор и что он показывает?
Какие задачи линейного программирования можно решать геометрическим методом?
Каков признак оптимальности в симплексном методе?
Как строится опорный план?
Как определяется ведущий столбец и ведущая строка симплексной таблице?
Как осуществляется перерасчет элементов симплексной таблицы?
Оцените по рациональности метода и сложности методы решения задач ЛП.
Практическое занятие №4
«Выбор и обоснование наиболее рационального метода и алгоритма решения транспортной задачи, а также оценка сложности выбранного алгоритма: метод потенциалов»
Цели занятия:
Научиться записывать математическую модель транспортной задачи.
Научиться строить опорный план транспортной задачи.
Научиться находить оптимальный план транспортной задачи.
Методические указания к выполнению заданий практического занятия
1. Построение математической модели транспортной задачи
Мы рассмотрели общие подходы к решению задач линейного программирования. Однако существуют частные типы задач линейного программирования, которые в силу своей структуры допускают решения более простыми методами. Мы остановимся только на одной из них – так называемой транспортной задаче.
Постановка транспортной задачи
Однородный груз, имеющийся в m пунктах отправления (производства) А1, А2, ..., Аm соответственно в количествах а1, а2, ..., аm единиц, требуется доставить в каждый из n пунктов назначения (потребления) В1, В2, ..., Вn соответственно в количествах b1, b2, ..., bn единиц. Стоимость перевозки (тариф) единицы продукции из Аi в Вj известна для всех маршрутов Ai, Bj и cij (i = 1, m; j = 1, n). Требуется составить такой план перевозок, при котором весь груз из пунктов отправления вывозится, и запросы всех пунктов потребления удовлетворяются (закрытая модель), т. е:
[ Cкачайте файл, чтобы посмотреть картинку ]
а суммарные транспортные расходы минимальны.
Математическая модель транспортной задачи
[ Cкачайте файл, чтобы посмотреть картинку ]
Будем называть любой план перевозок допустимым, если он удовлетворяет системам ограничений и требованиям неотрицательности.
Допустимый план, будем называть опорным, если в нем отличны от нуля не более m+n-1 базисных перевозок, а остальные перевозки равны 0.
План будет называться оптимальным, если он, среди всех допустимых планов, приводит к минимальной суммарной стоимости перевозок.
2.Методы решения транспортных задач
Так как транспортная задача является задачей линейного программирования, то её можно решать симплекс-методом, но в силу своей особенности её можно решить гораздо проще.
Условия задачи удобно располагать в таблице, вписывая в ячейки количество перевозимого груза из Аi в Bj груза Xij
· 0, а в маленькие клетки – соответствующие тарифы Cij.
[ Cкачайте файл, чтобы посмотреть картинку ]
Затем решение задачи разбивается на два этапа:
Определение опорного плана.
Нахождение оптимального решения путем последовательных операций.
Найдем вначале допустимое (опорное) решение транспортной задачи. Это решение можно найти, используя метод "северо-западного угла" или метод "минимального элемента".
Метод северо-западного угла (диагональный)
Сущность метода заключается в том, что на каждом шаге заполняется левая верхняя (северо-западная) клетка оставшейся части таблицы, причем максимально возможным числом: либо полностью выносится груз из Аi, либо полностью удовлетворяется потребность Вj. Процедура продолжается до тех пор, пока на каком-то шаге не исчерпаются запасы аi и не удовлетворятся все потребности bj. В заключении проверяют, удовлетворяют ли найденные компоненты плана Хij горизонтальным и вертикальным уравнениям.
Метод наименьшего элемента
Сущность метода в том, что на каждом шаге заполняется та клетка оставшейся части таблицы, которая имеет наименьший тариф; в случае наличия нескольких таких равных тарифов заполняется любая из них. В остальном действуют аналогично предыдущему способу.
3.Метод потенциалов решения транспортных задач
[ Cкачайте файл, чтобы посмотреть картинку ] (1)
Соотношения (1) определяют систему из m+n-1 линейных уравнений с m+n известными, имеющую бесчисленное множество решений; для её определённости одному неизвестному присваивают произвольное значение (обычно альфа равное 0), тогда все остальные неизвестные определяются однозначно.
Метод потенциалов:
Введем строку потенциалов ui и столбец потенциалов vj. Полагая, что u1=0, а остальные ui и vj найдем так, чтобы
а) для заполненных ячеек выполнялись равенства 13 EMBED Equation.3 1415;
б) для незаполненных ячеек выполнялись равенства 13 EMBED Equation.3 1415
Критерий оптимальности
Если известны потенциалы решения Х0 транспортной задачи и для всех незаполненных ячеек выполняются условия 13 EMBED Equation.3 1415то Х0 является оптимальным планом транспортной задачи.
Если план не оптимален, то необходимо перейти к следующему плану (таблице) так, чтобы транспортные расходы не увеличивались.
Цикл перерасчёта таблицы – это последовательность ячеек, удовлетворяющая условиям:
Одна ячейка пустая, все остальные занятые.
Любые две соседние ячейки находятся в одной строке или в одном столбце.
Пустой ячейке присваивают знак "+", остальным – поочерёдно знаки "–" и "+".
Для перераспределения плана перевозок с помощью цикла перерасчёта сначала находят незаполненную ячейку (r, s), в которой
·r+
·s > Crs, и строят соответствующий цикл; затем в минусовых клетках находят число X = min(Xij). Далее составляют новую таблицу по следующему правилу:
В плюсовых клетках добавляем Х.
Из минусовых клеток вычитаем Х.
Все остальные клетки вне цикла остаются без изменения.
Получим новую таблицу, дающую новое решение Х, такое, что F (X1)
· F (X0); оно снова проверяется на оптимальность через конечное число шагов, обязательно найдем оптимальный план транспортной задачи, ибо он всегда существует.
Различные виды циклов перерасчета таблицы
13 SHAPE \* MERGEFORMAT 1415
13 SHAPE \* MERGEFORMAT 1415
Пример.
Имеется три поставщика продукции с соответствующими предложениями а1, а2, а3 и три потребителя в1, в2, в3 соответственно. Стоимость перевозки единицы груза из каждого пункта отправления до каждого пункта назначения задается матрицей С.
Составить план перевозок всей продукции от поставщиков потребителям, при котором суммарные затраты на перевозки минимальны.
а1=50, а2=60, а3=90
в1=90, в2=70, в3=40
13 EMBED Equation.3 1415
Решение:
Эта задача является закрытой транспортной задачей, так как
13 EMBED Equation.3 1415
50+60+90=90+70+40.
200=200.
Для ее решения воспользуемся таблицей, в которой будем составлять последовательно планы перевозок.
Составим первый план перевозок. В этом плане отличными от нуля перевозками 13 EMBED Equation.3 1415 могут быть лишь (m+n-1) значений, где m – число поставщиков, n – число потребителей. Остальные переменные заведомо равны нулю. Будем их в таблице помечать прочерком.
В нашем примере m=3, n=3.
Значит число заполненных клеток: 3+3-1=5.
Для составления плана последовательно заполняем клетки таблицы так, чтобы на каждом шаге исчерпывалась или потребность какого-либо потребителя, или возможности какого-либо поставщика. В соответствующем столбе или строке ставим в остальных пустых клетках прочерки. Если при этом одновременно исчерпывается и потребность и возможность, то вычеркивается что-то одно (столбец или строка). При таком построении плана перевозок заполненными окажутся ровно (m+n-1) клетки, а остальные прочеркиваются.
При построении первого опорного плана воспользуемся методом наименьшего элемента. Начнем с клетки с наименьшими затратами 13 EMBED Equation.3 1415 и на каждом шаге будем выбирать такую клетку.
В каждой клетке таблицы значения 13 EMBED Equation.3 1415 будем записывать в правом верхнем углу таблицы. В центре будем проставлять значения 13 EMBED Equation.3 1415.
B1
B2
B3
vi
A1
1
3
3
2
50
2
-
10
40
A2
1
4
6
-1
1
60
1
60
-
-
A3
2
3
2
5
90
2
30
60
-
90
70
40
200
uj
0
1
1
Заполняем клетку (21), так как с21=1 – наименьшее, значением х21=60. При этом прочеркиваем вторую строку.
На втором шаге заполняем клетку (13), т.к. с13=2 - наименьшее, значением х13=40. При этом прочеркиваем третий столбец.
В оставшейся части таблицы наименьшее с31=2, значит, заполняем клетку (31) значением х31=30 (90-60=30). При этом прочеркиваем первый столбец.
Теперь остается наименьшее с12=3, значит, заполняем клетку (12) значением х12=10 (50-40=10). При этом прочеркиваем первая строка.
Наименьшее с32=3, значит заполняем клетку (32) значением х32=60 (70-10=60).
Число заполненных клеток равно 5.
Стоимость перевозок F при данном плане
13 EMBED Equation.3 1415.
Для проверки оптимальности полученного плана воспользуемся методом потенциалов.
Введем строку потенциалов uj и столбец потенциалов vi. Полагая, что u1=0, а остальные uj и vi найдем так, чтобы
а) для заполненных клеток выполнялись равенства 13 EMBED Equation.3 1415;
б) для незаполненных клеток выполнялись равенства 13 EMBED Equation.3 1415.
Оценки пустых клеток будем записывать в левых верхних углах клеток.
Для оптимальности плана должно выполняться условие 13 EMBED Equation.3 1415 для всех пустых клеток.
У нас 13 EMBED Equation.3 1415, значит, план не оптимален. Уменьшим стоимость перевозок, заполнив клетку (23).
Для этого построим цикл перерасчета таблицы - это последовательность клеток, удовлетворяющая условиям:
Одна ячейка пустая, все остальные занятые.
Любые две соседние ячейки находятся в одной строке или в одном столбце.
Пустой ячейке присваивают знак "+", остальным – поочерёдно знаки "–" и "+".
В минусовых клетках находят число X = min(Xij). Далее составляют новую таблицу по следующему правилу:
В плюсовых клетках добавляем Х.
Из минусовых клеток вычитаем Х.
Все остальные клетки вне цикла остаются без изменения.
По циклу в клетку (23) перемещаем 40 единиц из клетки (13).
Получаем новый опорный план.
B1
B2
B3
vi
A1
1
3
3
0
2
50
2
-
50
-
A2
1
4
6
0
1
60
1
20
-
40
A3
2
3
3
5
90
2
70
20
-
90
70
40
200
uj
0
1
0
Для проверки оптимальности полученного плана воспользуемся методом потенциалов.
Так как среди оценок пустых клеток нет отрицательных, то построенный план оптимальный.
13 EMBED Equation.3 1415.
При этом стоимость перевозок 13 EMBED Equation.3 141513 EMBED Equation.3 1415.
Вывод: Для того, чтобы транспортные расходы на перевозку продукции были минимальны и составляли 410 ден.ед., необходимо из пункта А1 перевозить 50 ед. в пункт В2, из А2 – 20 ед. в В1 и 40 ед. в В3, из А3 – 70 ед. в В1 и 20 ед. в В3.
Задание
Решить транспортную задачу.
Имеется три поставщика продукции с соответствующими предложениями а1, а2, а3 и три потребителя в1, в2, в3 соответственно. Стоимость перевозки единицы груза из каждого пункта отправления до каждого пункта назначения задается матрицей С.
Составить план перевозок всей продукции от поставщиков потребителям, при котором суммарные затраты на перевозки минимальны.
Вариант 1
а1=90, а2=40, а3=70
в1=50, в2=50, в3=100
13 EMBED Equation.3 1415
Вариант 2
а1=180, а2=80, а3=40
в1=100, в2=100, в3=200
13 EMBED Equation.3 1415
Вариант 3
а1=80, а2=70, а3=50
в1=45, в2=55, в3=100
13 EMBED Equation.3 1415
Вариант 4
а1=90, а2=40, а3=70
в1=85, в2=45, в3=70
13 EMBED Equation.3 1415
Контрольные вопросы:
Приведите пример транспортной задачи.
Когда транспортная задача называется вырожденной?
Укажите общий алгоритм решения транспортной задачи.
В чем суть метода потенциалов?
Что находится изначально: опорный план перевозок или оптимальный план перевозок?
Практическое занятие№5 «Решение задач НП»
Цели занятия:
1. Научиться решать задачи нелинейного программирования различными методами.
2. Научиться находить экстремумы функций.
Методические указания к выполнению заданий практического занятия
Нелинейное программирование
Задачами нелинейного программирования называются задачи математического программирования, в которых нелинейными являются и (или) целевая функция, и (или) ограничения в виде неравенств или равенств.
Задачи нелинейного программирования можно классифицировать в соответствии с видом функции F(x), функциями ограничений и размерностью вектора х (вектора решений).
Общих способов решения, аналогичных симплекс-методу линейного программирования, для нелинейного программирования не существует.
В каждом конкретном случае способ выбирается в зависимости от вида функции F(x).
Задачи нелинейного программирования на практике возникают довольно часто, когда, например, затраты растут непропорционально количеству закупленных или произведённых товаров.
Многие задачи нелинейного программирования могут быть приближены к задачам линейного программирования, и найдено близкое к оптимальному решению. Встречаются задачи квадратичного программирования, когда функция есть F(x) полином 2-ой степени относительно переменных, а ограничения линейны. В ряде случаев может быть применён метод штрафных функций, сводящий задачу поиска экстремума при наличии ограничений к аналогичной задаче, которая при отсутствии ограничений обычно решается проще.
Но в целом задачи нелинейного программирования относятся к трудным вычислительным задачам. При их решении часто приходится прибегать к приближенным методам оптимизации. Мощным средством для решения задач нелинейного программирования являются численные методы. Они позволяют найти решение задачи с заданной степенью точности.
Задачи безусловной однопараметрической оптимизации
Схема применения производной
для нахождения интервалов монотонности и экстремумов
Найти область определения функции и интервалы, на которых функция непрерывна.
Найти производную f’(x).
Найти критические точки.
В каждом из интервалов, на которые область определения разбивается критическими точками, определить знак производной и вид монотонности функции.
Относительно каждой критической точки определить, является ли она точкой максимума, минимума или не является точкой экстремума.
Пример: y=2x3-3x2-36x+5
Численный метод решения задачи – это определенная последовательность операций над числами.
Численные методы, позволяющие решить задачу в точной постановке, не вносят погрешностей в вычисления.
При исследовании функции делаем вывод: рассматриваемая функция должна быть дифференцируема.
Но на практике такие функции встречаются довольно редко, поэтому для решения задач нелинейного программирования применяются приближенные методы.
Бывает так, что решить задачу в точной постановке трудно или невозможно. Тогда её заменяют близкой по результатам приближенной задачей. Численный метод, реализующий такую приближённую задачу, называют приближённым методом. Такие методы вносят погрешности в вычисления.
Экстремумы функции двух переменных
Максимумом (минимумом) функции 13 EMBED Equation.3 1415 называется такое ее значение 13 EMBED Equation.3 1415, которое больше (меньше) всех других значений, принимаемых ею в точках, достаточно близких к точке 13 EMBED Equation.3 1415 и отличных от нее.
Максимум или минимум функции называется ее экстремумом. Точка, в которой достигается экстремум, называется точкой экстремума.
Точки экстремума функции двух переменных 13 EMBED Equation.3 1415 надо искать среди тех точек, лежащих внутри области ее определения, координаты которых удовлетворяют системе
13 EMBED Equation.3 1415 (1.2)
Точки, удовлетворяющие такой системе уравнений, называются стационарными.
Но не всякая такая точка действительно будет точкой максимума или минимума. Каждую стационарную точку надо специальным образом проверить. Для функции двух переменных проверка стационарной точки 13 EMBED Equation.3 1415 требует:
1) нахождения в этой точке значений вторых производных:
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415,
которые обозначим буквами 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415 соответственно;
2) определения знака 13 EMBED Equation.3 1415:
если 13 EMBED Equation.3 1415, то в стационарной точке 13 EMBED Equation.3 1415 нет экстремума;
если 13 EMBED Equation.3 1415, то экстремум есть, причем 13 EMBED Equation.3 1415, если 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415, если 13 EMBED Equation.3 1415;
если 13 EMBED Equation.3 1415, то ничего сказать нельзя – требуется дополнительное исследование.
Пример. Найти для функции 13 EMBED Equation.3 1415, точки максимума и минимума (если они существуют).
Решение.
1) Ищем частные производные:
13 EMBED Equation.3 1415 13 EMBED Equation.3 1415.
2) Для нахождения стационарных точек функции составим и решим систему (1.2). В нашем случае система имеет вид
13 EMBED Equation.3 1415
Первое уравнение выполняется в двух случаях: либо когда 13 EMBED Equation.3 1415, либо когда 13 EMBED Equation.3 1415 или 13 EMBED Equation.3 1415. В первом случае второе уравнение после подстановки нуля вместо 13 EMBED Equation.3 1415 приобретает вид 13 EMBED Equation.3 1415 и имеет решения 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415. Таким образом, в данном случае решениями системы будут пары чисел: 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, а стационарными точками функции 13 EMBED Equation.3 1415 – точки 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415.
Во втором случае, после замены 13 EMBED Equation.3 1415 на 13 EMBED Equation.3 1415 второе уравнение приобретает вид 13 EMBED Equation.3 1415. Оно имеет решения 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415. Так как 13 EMBED Equation.3 1415, то отсюда следует, что решениями системы будут пары чисел 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, а стационарными точками функции 13 EMBED Equation.3 1415 будут также точки 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415.
3) Следующий шаг – проверка каждой стационарной точки на экстремум. Найдем сначала формулы, выражающие вторые производные функции 13 EMBED Equation.3 1415:
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415 13
·EMBED Equation.3 1415.
Приступим теперь к проверке точки 13 EMBED Equation.3 1415, для чего найдем соответствующие ей числа A, B, C:
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415.
13 EMBED Equation.3 1415 и, значит, в 13 EMBED Equation.3 1415 экстремума нет.
Аналогично проверяем точку 13 EMBED Equation.3 1415:
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415,13 EMBED Equation.3 1415.
13 EMBED Equation.3 1415 и, значит, в 13 EMBED Equation.3 1415 экстремума нет.
Точно также нет экстремума и в точке 13 EMBED Equation.3 1415, так как в ней 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415.
Наконец, для точки 13 EMBED Equation.3 1415 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415. Следовательно, в точке 13 EMBED Equation.3 1415 экстремум есть и, согласно теории, это максимум, так как 13 EMBED Equation.3 1415. При этом значение функции в точке максимума равно 13 EMBED Equation.3 1415.
4.Условный экстремум. Функция Лагранжа
Условным экстремумом функции 13 EMBED Equation.3 1415 называется экстремум этой функции, достигнутый при условии, что переменные х и у связаны уравнением 13 EMBED Equation.3 1415 (уравнение связи).
Отыскание условного экстремума можно свести к исследованию на обычный экстремум так называемой функции Лагранжа 13 EMBED Equation.3 1415, где 13 EMBED Equation.3 1415- неопределенный постоянный множитель.
Необходимые условия экстремума функции Лагранжа имеют вид
13 EMBED Equation.3 1415
Из этой системы трех уравнений можно найти неизвестные х, у, 13 EMBED Equation.3 1415.
Пример:
Найти экстремум функции 13 EMBED Equation.3 1415 при условии, что х и у связаны уравнением 13 EMBED Equation.3 1415.
Решение: Рассмотрим функцию Лагранжа 13 EMBED Equation.3 1415. Имеем 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415.
Из системы уравнений (необходимые условия экстремума)
13 EMBED Equation.3 1415 находим 13 EMBED Equation.3 1415
Нетрудно видеть, что в точке (5/4, 5/6) функция 13 EMBED Equation.3 1415 достигает наибольшего значения 13 EMBED Equation.3 1415.
Геометрический метод
Для того, чтобы найти наибольшее и наименьшее значения функции в замкнутой области, надо:
1) найти стационарные точки, расположенные в данной области, и вычислить значение функции в этих точках;
2) найти наибольшее и наименьшее значения функции на линиях, образующих границу области;
3) из всех найденных значений выбрать наибольшее и наименьшее значения.
Задания практического занятия
Задание 1. Найдите точки экстремума заданной функции:
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
Задание 2. Найдите точки экстремума заданной функции.
1. 13 EMBED Equation.3 1415.
2. 13 EMBED Equation.3 1415.
3. 13 EMBED Equation.3 1415.
4. 13 EMBED Equation.3 1415.
Задание 3. Используя метод Лагранжа, найти переменные х, у, дающие минимум целевой функции 13 EMBED Equation.3 1415, при ограничении 13 EMBED Equation.3 1415.
Вариант
1
2
3
4
a
1
2
3
4
b
1
2
4
6
Задание 4. Используя графический метод решения, найти переменные х, у, дающие минимум целевой функции 13 EMBED Equation.3 1415, при ограничениях 13 EMBED Equation.3 1415
Вариант
1
2
3
4
a
3
3
3
3
b
1
2
4
6
Контрольные вопросы:
Дайте определение задачам нелинейного программирования.
Существуют ли общие методы решения задач нелинейного программирования?
Как находится экстремум функции одной переменной?
Как находится экстремум функции нескольких переменных?
Как находится условный экстремум функции?
Практическое занятие№6
«Решение задач о распределении средств между предприятиями и замене оборудования»
Цели занятия:
Научиться решать задачи динамического программирования.
Научиться разбивать весь процесс решения задачи на этапы.
Научиться выбирать оптимальную стратегию поведения.
Методические указания к выполнению заданий практического занятия
Динамическое программирование
1. Понятие задачи динамического программирования
Рассматриваемые ранее задачи характеризуются тем, что в них не учитываются изменения оптимизируемых параметров во времени – процессы считаются статичными. Выбирается некоторый период времени, и для него определяются проектируемые или планируемые значения показателей. При этом предполагается, что управляемые или неуправляемые параметры системы в течение всего планового времени не будут изменяться или, по крайней мере, не претерпят серьёзных изменений, требующих пересмотра принятых решений.
Однако в реальной жизни есть задачи, в которых необходимо учитывать изменения параметров систем во времени. Эти параметры могут меняться непрерывно или дискретно – от этапа к этапу. Например, из года в год меняется возраст машин и оборудования, изменяется производственная мощность и производительность труда на предприятиях. Очевидно, что необходимо принимать оптимальные решения на год (или другой срок) и одновременно на весь рассматриваемый период в целом с учётом возможных изменений параметров. Для решения такого вида задач, которые получили название многошаговые, разработан соответствующий математический аппарат, который получил название динамическое программирование.
Задача может быть сформулирована следующим образом:
Задача динамического программирования – определить ui* (ui* не только число, а может быть вектором, функцией) на каждом шаге, i = 1, 2 , m, и тем самым u* всей операции в целом.
Рассмотрим подход к решению данной задачи. Характерным для динамического программирования является то, что переменные рассматриваются вместе, а не последовательно – одна за другой. При этом вычислительная тема строится таким образом, что вместо одной задачи с n переменными решается серия задач с небольшим числом, а чаще с одной переменной. Сам же вычислительный процесс производится на основе метода последовательных приближений в два круга:
От последнего шага к первому.
От первого шага к последнему или же наоборот, в зависимости от исходных данных.
На первом круге ищется так называемое условное оптимальное решение. Оно выбирается так, чтобы все предыдущие шаги обеспечили максимальную эффективность последующего. Основу такого подхода составляет принцип оптимальности Беллмана, который формулируется следующим образом:
Нельзя получить оптимальное значение целевой функции i-шагового процесса, если для любого ui, выбранного на шаге i, значение целевой функции для оставшихся i-1 шагов не является оптимальным при этом выбранном на i-шаге значении ui.
Такой процесс продолжается до тех пор, пока решение не потеряет свой условный характер, т. е. до первого шага или последнего. Для него решение просто оптимально. Поэтому второй круг начинают именно с этого шага и последовательно переходят от условных к оптимальным решениям, тем самым обеспечивается оптимальность операции в целом.
Оптимальное распределение ресурсов
Пример:
Капитал 40 млн.руб. инвестор должен вложить в четыре инвестиционных проекта так, чтобы получить максимальный доход. Доходность проектов дана в таблице (вложения кратны 8 млн. руб.)
u
Прибыль от внедрения
f4(u)
f3(u)
f2(u)
f1(u)
8
55
39
35
32
16
58
53
76
68
24
90
80
120
115
32
100
120
135
134
40
140
145
158
147
Решение:
Это задача динамического программирования. Решение состоит из двух этапов. На первом этапе (от конца к началу) ищем условное оптимальное решение, на втором (от начала к концу) – ищем оптимальное решение задачи.
1 этап.
Распределяем капитал между четырьмя проектами и считаем получаемую прибыль L(i), i=8,16,24,32,40.
1 шаг: Денежные средства вкладываются в четвертый проект.
L(8)=55
L(16)=58
L(24)=90
L(32)=100
L(40)=140
2 шаг: Денежные средства вкладываются в четвертый и третий проекты.
u
Прибыль от внедрения
1 шаг
f3(u)
8
55
39
16
58
53
24
90
80
32
100
120
40
140
145
13 EMBED Equation.3 1415
3 шаг: Денежные средства вкладываются в четвертый, третий (2 шаг) и второй проекты.
u
Прибыль от внедрения
2 шаг
f2(u)
8
55
35
16
94
76
24
108
120
32
135
135
40
175
158
13 EMBED Equation.3 1415
4 шаг: Денежные средства вкладываются в четвертый, третий, второй (3 шаг) и первый проекты.
u
Прибыль от внедрения
3 шаг
f1(u)
8
55
32
16
94
68
24
131
115
32
175
134
40
214
147
13 EMBED Equation.3 1415
2 этап:
На четвертом шаге выбираем максимальное из полученных значений прибыли L(40)=214.
И возвращаясь в обратном порядке от таблицы к таблице (от 4 шага к 1) выбираем такие значения доходов, при которых и получено значение 214.
Максимальный доход 214 млн. руб. от вложенных средств может быть получен при следующем распределении средств:
1 проект – 0 млн. руб.
2 проект – 24 млн. руб.
3 проект – 8 млн. руб.
4 проект – 8 млн. руб.
Задание
Задание 1. Распределите оптимальным образом денежные средства инвестора величиной 5 у.е. между четырьмя предприятиями. Доход каждого предприятия от вложения в него и у.е.определяется функцией дохода f(u). Эти функции приведены в таблице.
u
Прибыль от внедрения по предприятиям
f4(u)
f3(u)
f2(u)
f1(u)
1
f4(1)
6
3
4
2
10
f3(2)
4
6
3
11
11
f2(3)
8
4
12
13
11
f1(4)
5
18
15
18
16
Вариант
1
2
3
4
f4(1)
9
5
6
8
f3(2)
10
10
7
7
f2(3)
7
5
8
9
f1(4)
10
9
13
15
Задание 2. Из пункта А в пункт В необходимо проложить автомобильную трассу по самому экономичному пути.
Вариант 1
Вариант 2
Вариант 3
Вариант 4
Контрольные вопросы:
Какие задачи можно решать методами динамического программирования?
В чем заключаются достоинства и недостатки динамического программирования?
Объясните алгоритм решения задач динамического программирования.
Укажите принцип выбора направления движения.
В чем заключается принцип оптимальности?
Каков алгоритм распределения ресурсов?
Практическое занятие№7
«Нахождение кратчайшего пути в графе. Разработка алгоритма для решения различных практических задач с применением математических методов»
Цель занятия:
Закрепить умения определять метрические характеристики графа.
Закрепить умения определять кратчайший путь от вершины s до вершины t с использованием алгоритма Дейкстры.
Методические указания к выполнению заданий практического занятия
Граф – это множество точек или вершин и множество линий или ребер, соединяющих между собой все или часть этих точек.
Метрические характеристики графов
В теории графов применяются:
Матрица инцинденций. Это матрица А с n строками, соответствующими вершинам, и m столбцами, соответствующими рёбрам. Для ориентированного графа столбец, соответствующий дуге (х,y) содержит (-1) в строке, соответствующей вершине х и 1 в строке, соответствующей вершине у. Во всех остальных – 0. Петлю, т. е. дугу (х,х) можно представлять иным значением в строке х, например, 2.
Если граф неориентированный, то столбец, соответствующий ребру (х,у) содержит 1, соответствующие х и у – нули во всех остальных строках.
Матрица смежности. Это матрица n*n где n – число вершин, где bij = 1, если существует ребро, идущее из вершины х в вершину у и bij = 0 в противном случае.
Пусть G=(X,U) - связный граф, а 13 EMBED Equation 1415 - две его несовпадающие вершины. Длина кратчайшего маршрута, соединяющего вершины 13 EMBED Equation 1415 (пути из 13 EMBED Equation 1415) называется расстоянием между вершинами 13 EMBED Equation 1415 и обозначается 13 EMBED Equation 1415. Положим 13 EMBED Equation 1415, если вершины 13 EMBED Equation 1415 не соединены маршрутом (путем). Расстояние 13 EMBED Equation 1415 удовлетворяет следующим аксиомам:
1) 13 EMBED Equation 1415;
2) 13 EMBED Equation 1415;
3)13 EMBED Equation 1415 тогда и только тогда, когда 13 EMBED Equation 1415;
4) 13 EMBED Equation 1415 для симметрических графов;
5) 13 EMBED Equation 1415
Расстояние для графа G удобно задавать матрицей расстояний. Матрицей расстояний графа с n вершинами называется квадратная матрица D порядка n, элементы которой определяются следующим образом:
13 EMBED Equation 1415
Для фиксированной вершины 13 EMBED Equation 1415 величина 13 EMBED Equation 1415называется эксцентриситетом (отклоненностью) вершины 13 EMBED Equation 1415.
Максимальный среди эксцентриситетов вершин называется диаметром графа G и обозначается diam (G):
13 EMBED Equation 1415
Минимальный из эксцентриситетов вершин связного графа называется его радиусом и обозначается через r(G):
13 EMBED Equation 1415
Вершина, имеющая минимальный эксцентриситет, называется центром графа.
Для вершины 13 EMBED Equation 1415 число 13 EMBED Equation 1415 называется передаточным числом. Вершина графа, которой соответствует минимальное передаточное число 13 EMBED Equation 1415
называется медианой графа. Центров и медиан в графе может быть несколько.
Рис. 1
Пример. Для графа, изображенного на рис.1 метрические характеристики определяются следующим образом:
13 EMBED Equation 1415
Радиус графа равен 1, диаметр равен 2. Центр графа - вершина 13 EMBED Equation 1415; Медиана графа - вершина 13 EMBED Equation 1415.
Задача о нахождении кратчайшего пути
Пусть дан граф, каждой дуге которого приписан вес. Задача о нахождении кратчайшего пути состоит в нахождении кратчайшего пути от заданной начальной вершины до заданной конечной вершины, при условии, что такой путь существует.
Можно дать много практических интерпретаций задачи о кратчайших путях. Например, вершины могут соответствовать городам и каждая дуга – некоторому пути, длина которого представлена весом дуги. Мы ищем кратчайшие пути между городами. Вес дуги может соответствовать стоимости (или времени) передачи информации между вершинами. В этом случае мы ищем самый дешевый (или самый скорый) путь.
Данная задача может быть разбита на две:
для начальной заданной вершины найти все кратчайшие пути от этой вершины к другим;
найти кратчайшие пути между всеми парами вершин.
Алгоритм Дейкстры решения задачи
Алгоритм Дейкстры ( алгоритм поиска кратчайшего пути во взвешенном графе между двумя заданными вершинами s и t при неотрицательных весах всех дуг.
Пусть s - начальная вершина пути, t - конечная.
На каждой итерации алгоритма каждая вершина xi графа имеет метку l(xi), которая может быть постоянной или временной. В первом случае l(xi) является длиной кратчайшего (s, xi)-пути; во втором случае l(xi) - длина кратчайшего (s, xi)-пути, проходящего через вершину xi и вершины с постоянными метками. Таким образом временная метка l(xi), является оценкой сверху для длины кратчайшего (s, xi)-пути, и, став на некоторой итерации постоянной, она остается такой до конца работы алгоритма.
Кроме l(xi), с вершинами графа связывается еще одна метка Q(xi).На каждой итерации Q(xi) является номером вершины, предшествующей хi в кратчайшем (s, xi)-пути.
После того, как последняя вершина t получила постоянную метку, с помощью меток Q(x) легко указать последовательность вершин, составляющих кратчайший (S,t)-путь:
(s..., Qn(t)..., Q(Q(t)), Q(t),t),
Qn(t)= Q(Q(...Q(t)) (n раз).
Перед началом работы алгоритма начальная вершина s имеет постоянную метку l(s)=0, а метки всех остальных вершин равны бесконечности (() и являются временными. Обозначим через p последнюю из вершин, получивших постоянную метку.
Алгоритм Дейкстры включает следующие шаги:
1. Положить l(s)=0 и считать эту метку постоянной. Положить l(xi)= ( для всех xi ( s, и считать эти метки временными. p = s.
2. Обновление пометок. Для всех вершин xi ( Г(p), пометки которых временные, изменить пометки в соответствии с правилом:
l(xi)=min { l(xi), l(p) +w(p, xi) }.
Если l(xi)> l(p) +w(p, xi), то Q(xi) = p.
3. Если l(xi)= ( для всех вершин xi, пометки которых временные, то в исходном графе отсутствуют пути из вершины s в вершины с временными метками. Останов алгоритма. В противном случае переход к шагу 4.
4. Превращение пометок в постоянные. Среди всех вершин с временными метками найти такую вершину xi* , для которой l(xi*) = minl(xi) (метка минимальная) и считать эту пометку постоянной. Положить p=xi*. Пометку Q(xi*) также считать постоянной.
5. Если p ( t, перейти к шагу 2, а если p = t, то l(p) - длина кратчайшего пути из s в t.
После определения длины кратчайшего пути сам кратчайший путь восстанавливается по постоянным меткам Q(xi).
Пример решения задачи
Для взвешенного орграфа найти кратчайший путь из вершины s в вершину t.
13 EMBED PBrush 1415
1. Помечаем в соответствии с алгоритмом вершины графа:
l(s) = 0 ,
l(a) = ( ,
l(b) = ( ,
l(c) = ( ,
l(d) = ( ,
l(t) = ( .
Вершине s приписываем постоянную пометку, т.е. p = s.
2. Из вершины s помечаем остальные вершины:
l(a) = min {(, 0 + 4} = 4,
l(b) = min {(, 0 + 7} = 7,
l(c) = min {(, 0 + 3} = 3,
l(d) = ( ,
l(t) = ( .
У вершин a, b, с уменьшились пометки, следовательно Q(a) = s, Q(b) = s, Q(c) = s.
Вершине c приписываем постоянную пометку, т.е. p = c. Пометка Q(с)=s также становится постоянной.
3. Из вершины c помечаем остальные вершины:
l(a) = min {4, 3 + (} = 4,
l(b) = min {7, 3 + (} = 7,
l(d) = min {(, 3 + 3} = 6,
l(t) = ( .
У вершины d уменьшилась пометка, следовательно Q(d) = c.
Вершине a приписываем постоянную пометку, т.е. p = a. Пометка Q(a)=s становится постоянной.
4. Из вершины а помечаем остальные вершины:
l(b) = min {7, 4 + 4} = 7,
l(d) = min {6, 4 + 3} = 6,
l(t) = ( .
Вершине d приписываем постоянную пометку, т.е. p = d.. Пометка Q(d)=c становится постоянной.
5. Из вершины d помечаем остальные вершины:
l(b) = min {7, 6 + (} = 7,
l(t) = min {(, 6 + 2} = 8,
У вершины t уменьшилась пометка, следовательно Q(t) = d.
Вершине b приписываем постоянную пометку, т.е. p=b. Пометка Q(b)=s становится постоянной.
6. Из вершины b помечаем вершину t:
l(t) = min {8, 7 + 2} = 8.
Метки l(t) и Q(t)=d становятся постоянными.
7. Восстанавливаем по меткам Q кратчайший путь из s в t:
Путь scdt длиной 8.
Вариант 1
Задание 1.Определить метрические характеристики графа.
Задание 2. Определить кратчайший путь от вершины s до вершины t с использованием алгоритма Дейкстры.
Вариант 2
Задание 1.Определить метрические характеристики графа.
Задание 2. Определить кратчайший путь от вершины s до вершины t с использованием алгоритма Дейкстры.
Вариант 3
Задание 1.Определить метрические характеристики графа.
Задание 2. Определить кратчайший путь от вершины s до вершины t с использованием алгоритма Дейкстры.
Вариант 4
Задание 1.Определить метрические характеристики графа.
Задание 2. Определить кратчайший путь от вершины s до вершины t с использованием алгоритма Дейкстры.
Контрольные вопросы:
Что такое граф?
Приведите разновидности графов.
Может ли пустой граф быть ориентированным?
Нарисуйте полный граф.
Каким образом понятие дерева активно используется в информатике и программировании?
Перечислите метрические характеристики графов.
Дайте интерпретацию задаче о кратчайших путях.
Раздел 3. Основные методы решения детерминированных задач и задач в условиях неопределенности, возникающих в практической деятельности
Практическое занятие№8
«Составление систем уравнений Колмогорова. Нахождение финальных вероятностей. Выбор и обоснование наиболее рационального метода и алгоритма решения задачи, а также оценка сложности выбранного алгоритма»
Цель занятия:
Отработать и закрепить умения составлять системы уравнений Колмогорова.
Отработать и закрепить умения находить финальные вероятности.
Отработать и закрепить умения определите основные показатели СМО.
Методические указания к выполнению заданий практического занятия
Марковский случайный процесс
Построение математических моделей в условиях неопределенности - очень сложная или невыполнимая задача. Лишь для некоторых упрощенных случаев можно построить математическую модель.
Следует различать два вида неопределенности:
вероятностные характеристики либо известны, либо могут быть получены в результате эксперимента. Такая неопределенность называется стохастической, и для большинства объектов, содержащих такую неопределенность, можно построить математическую модель, например выход из строя оборудования, приход нового клиента и т. д.
вероятностные характеристики определить невозможно. В этом случае задачу можно попытаться решить с помощью экспертных оценок, но результат будет весьма приблизительным, например, каковы будут модели женской одежды через пять лет?
Строгую математическую модель с аналитическим вычислением всех интересующих величин можно построить только в том случае, если случайный процесс носит марковский характер.
Случайный процесс будет марковским, если вероятностные характеристики процесса в момент времени t зависят только от текущего (настоящего) состояния процесса в этот момент времени t и не зависят от того, как (каким способом и когда) рассматриваемый процесс перешел в текущее состояние.
Из всего многообразия марковских процессов хорошо изучены и представляют большой практический интерес марковские случайные процессы с дискретными состояниями и непрерывным временем.
Под дискретным состоянием будем понимать, что процесс переходит из одного состояния в другое скачкообразно за очень короткое время (практически мгновенно), и количество этих состояний известно (фиксировано).
Под непрерывным временем будем понимать такое, при котором переход из одного допустимого состояния в другое допустимое состояние происходит в произвольные моменты времени, т. е. заранее не определенные.
Потоки событий. Однородные события, следующие друг за другом в произвольные моменты времени (случайно), называются потоком событий (или входным потоком заявок). Примерами потоков событий могут быть: поток пассажиров в авиакассе, поток посетителей парикмахерской, поток отказов технического устройства и т.д. Здесь под событием понимается факт поступления заявок на обработку (приход покупателя, наличие отказа технического средства, поступление телефонного вызова и т.д.), а не результат его обработки (как это рассматривается в теории вероятностей). Поэтому в системах массового обслуживания вероятностными характеристиками будет обладать не отдельное событие, а интервал времени.
Интенсивностью 13 EMBED Equation.3 1415 потока событий называется среднее число событий за единицу времени. Интенсивность 13 EMBED Equation.3 1415 может быть как числом постоянным (константой), так и величиной, зависящей от времени t. Например, количество пассажиров в городском транспорте в «часы пик» резко увеличивается по сравнению с другим временем суток.
Финальные вероятности состояний
Будем рассматривать марковские процессы с дискретными состояниями и непрерывным временем.
Пример 1 : Техническое устройство состоит из трёх узлов и в любой момент времени может находиться в одном из восьми состояний (рис. 1).
Возможные состояния устройства таковы:
S0 все три узла исправны;
S1 первый узел неисправен, второй и третий исправны;
S2 второй узел неисправен, первый и третий исправны;
S3 третий узел неисправен, первый и второй исправны;
S4 первый и третий узлы неисправны, второй исправен;
S5 второй и третий узлы неисправны, первый исправен;
S6 первый и второй узлы неисправны, третий исправен;
S7 все три узла неисправны.
Размеченным графом будем считать такой граф, у которого стрелками указаны переходы из одного состояния в другое, а рядом со стрелкой указана интенсивность перехода. Будем различать две интенсивности прямую 13 EMBED Equation.3 1415, и обратную 13 EMBED Equation.3 1415.
Тогда 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415 интенсивности потоков отказов соответственно первого, второго и третьего узлов, а 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415 соответственно интенсивности потоков возвратов (ремонтов) узлов.
Если для ремонта каждого узла имеется отдельный специалист, то среднее время ремонта каждого узла есть величина постоянная и не имеет значения, один или несколько узлов вышли из строя.
На основе построенного размеченного графа (см. рис. 1) создадим математическую модель.
Наше техническое устройство в соответствии с построенным графом в любой момент времени будет находиться в одном из восьми возможных состояний. Обозначим вероятность каждого i-го состояния как pi(t), тогда
13 EMBED Equation.3 1415
Для определения вероятности каждого состояния технического устройства составим соответствующие дифференциальные уравнения:
13 EMBED Equation.3 1415
Эта система дифференциальных уравнений называется системой уравнений Колмогорова. Имеем систему из восьми линейных дифференциальных уравнений с восемью неизвестными. Известно, что сумма всех вероятностей равна единице, т. е.
p0 +pl +p2 +p3 +p4 +p5+p6 +p7 =1
Таким образом, любое из уравнений, входящее в систему уравнений, можно записать, используя последнее уравнение, и найти значения вероятностей для каждого события.
Для облегчения процесса составления дифференциальных уравнений можно применить следующее правило:
В левой части каждого уравнения следует записать производную вероятности г-го состояния устройства.
В правой части сумма произведений потока событий, входящих в текущее состояние, умноженная на вероятность состояния, из которого исходит поток, минус суммарная интенсивность исходящих потоков событий из текущего состояния, умноженная на вероятность текущего состояния.
Если финальные вероятности существуют: 13 EMBED Equation.3 1415 при i = 1, 2, 3, ..., n,
то их сумма будет равна единице: 13 EMBED Equation.3 1415
Финальные вероятности показывают, какое среднее время устройство будет находиться в каждом состоянии. Финальные вероятности находятся из системы дифференциальных уравнений, если их правые части приравнять нулю.
Решение системы уравнений Колмогорова
Зададим численные значения интенсивности потоков событий для примера 1:
(1=1; (2=2; (3=1; (1=2; (2=4; (3=2.
Приравняем левые части уравнений системы нулю .
13 EMBED Equation.3 1415
Второй (отрицательный) член каждого выражения перенесем в левую часть
13 EMBED Equation.3 1415
Подставим конкретные значения (указанные выше) прямых и обратных интенсивностей
13 EMBED Equation.3 1415
После выполнения арифметических действий получим:
13 EMBED Equation.3 1415
Из первого уравнения выразим 13 EMBED Equation.3 1415 и подставим его в остальные уравнения:
13 EMBED Equation.3 1415
Аналогично выражаем 13 EMBED Equation.3 1415 и подставляем в оставшиеся уравнения и получаем:
13 EMBED Equation.3 1415
Выражаем 13 EMBED Equation.3 1415 и подставляем в оставшиеся уравнения и получаем:
13 EMBED Equation.3 1415
Из первого выражения выразим 13 EMBED Equation.3 1415 и подставим в оставшиеся уравнения. После выполнения преобразований получим:
13 EMBED Equation.3 1415
Из первого уравнения выразим13 EMBED Equation.3 1415 и подставим в оставшиеся уравнения:
13 EMBED Equation.3 1415
Из первого уравнения13 EMBED Equation.3 1415 в оставшиеся уравнения:
13 EMBED Equation.3 1415
Из первого уравнения p0 подставим в оставшиеся уравнения:
13 EMBED Equation.3 1415 13 EMBED Equation.3 1415
Определим остальные вероятности, подставляя полученные результаты в обратном порядке
P0= 0,46940 *0,21146=0,1007;
P6 =0,06678 *0,107 +0,1731 *0,2146=0,04387;
P5= 0,1608*0,1007+0,09232*0,04387+0,2801*0,2146=0,08035;
P4=0,07692*0,1007+0,1538*0,08035+0,1538*0,04387+0,7692*0,2146=0,08035;
P3=0,2*0,1007+0,8*0,080035+0,4*0,1853=0,1585;
P2=0,3333*0,1007+0,3333*0,08035+0,3333*0,04387=0,07498;
P1=0,2*0,1007+0,4*0,1853+0,8*0,04387=0,1294.
Выполним проверку. Сумма вероятностей всех событий должна быть равна единице.
p0+p1+p2+p3+p4+p5+p6+p7=1
0,1294+0,07498+0,1585+0,1853+0,08035+0,043870+0,04387+0,1007+0,2146=0,9877
Полученный результат меньше единицы, так как значение каждой вероятности было округленно.
СМО. Основные понятия.
С системами массового обслуживания (CMO) приходится сталкиваться очень часто. Это и работа телефонной станции, и различные очереди (на автозаправке, в поликлинике, в билетной кассе и т.д.), работа некоторых организаций (магазины, мастерские, парикмахерские и т. д.).
Каждая СМО имеет как минимум три элемента: обслуживающий инструмент (станок, касса, канал связи и т. д.), который в дальнейшем будем называть каналом обслуживания или просто каналом; входной поток, т.е. поток заявок, поступающих на обслуживание; выходной поток, т.е. заявки, выполненные СМО (обеспеченные услугой).
Каждая поступившая заявка и принятая на обслуживание внутри СМО обрабатывается некоторое время, называемое временем обслуживания tоб. Все заявки поступают случайным образом и независимо друг от друга. Будем рассматривать простейший случай: в каждый момент времени может поступить только одна заявка. Случаи поступления двух и более заявок в один и тот же момент времени не рассматриваются. Таким образом, в некоторые моменты времени поступившие заявки будут скапливаться на входе СМО и ожидать своей обработки либо покидать СМО необслуженными. В другие моменты времени СМО может простаивать, т. е. не иметь заявок на обслуживание.
График работы СМО представляет собой ступенчатую функцию, т. е. состояние СМО изменяется скачкообразно.
При моделировании работы СМО ставится задача связать технические характеристики СМО,
По способу функционирования СМО могут быть:
открытыми, т. е. поток заявок не зависит от внутреннего состояния СМО;
закрытыми, т.е. входной поток зависит от состояния СМО (один ремонтный рабочий обслуживает все каналы по мере их выхода из строя).
Одноканальные СМО с отказами
При изучении СМО используем следующие предположения:
Входной поток является пуассоновским с параметром
·.
Время обслуживания подчиняется экспоненциальному закону с параметром
·:
[ Cкачайте файл, чтобы посмотреть картинку ]
Время обслуживания требования не зависит от количества требований, поступивших в систему.
Такая система в любой момент времени t может находиться в одном из двух состояний:
Е0 – в системе 0 требований (система свободна);
Е1 – в системе 1 требование (система занята).
Далее мы будем находить вероятности:
Р0 – система находится в состоянии Е0;
Р1 – система находится в состоянии Е1.
Начиная с некоторого момента времени, вероятность Р0(t) перестает зависеть от времени и становится постоянной; постоянной будет и Р1(t). Эти величины равны соответственно
P0 =
·/
·+
·, P1 = 1-P0 =
·/
·+
·.
В таких случаях говорят, что в системе установился стационарный режим работы. Будем находить коэффициент загрузки системы по формуле
· = P1/P0 =
·/
·.
Напомним, что
· – среднее число требований, прибывающих в систему за единицу времени,
· – среднее число обслуженных требований.
Вероятности застать систему свободной и застать её занятой, соответственно равны теперь
P0 =
·/(
·+
·) = 1/(
·/
·-1) = 1/(
·+1), P1 =
·/(
·+1).
Ясно, что чем больше коэффициент загрузки, тем больше вероятность отказа системы. Это не выгодно потребителю (но выгодно организатору системы, ибо мала вероятность простоя Р0). Если уменьшить коэффициент загрузки, то уменьшится вероятность отказа СМО (это выгодно потребителю), но увеличится вероятность простоя (что не выгодно организаторам системы). Мы имеем дело с противоположными тенденциями и, следовательно, необходимо решать задачи оптимизации режима работы СМО.
Одноканальные СМО с ожиданием
Такие системы при условии, что нет ограничений на длину очереди, имеют бесчисленное множество состояний:
Е0, Е1, Е2, Е3, ...
Е0 – в системе 0 требований (система свободна);
Е1 – в системе 1 требование (система занята);
Е2 – в системе 1 требование, и одно требование ожидает в очереди;
Е3 – в системе 1 требование, и два требования ожидают в очереди и т. д.
Для нахождения вероятностей используется следующая формула:
P0 = 1-
·,
· =
·/
·.
Следовательно,
Pk = (1-
·)
·k, k = 1, 2, .
Условие
· > 0 является необходимым и достаточным для наличия стационарного режима работы системы.
Интересно знать, почему стационарный режим существует только при этом условии?
Это условие означает, что среднее число требований, поступивших в СМО, меньше, чем интенсивность самого обслуживания; поэтому система успевает ритмично работать. Теперь ясно, почему система не может работать при условии, когда коэффициент загрузки больше 1. Но почему нет установившегося режима, когда коэффициент загрузки равен 1? Ведь в этом случае, сколько в среднем требований поступает в СМО, столько в среднем и обслуживается. Однако требования поступают в систему неравномерно, и время их обслуживания тоже колеблется, так что могут быть и простои, и перегрузки. Вот поэтому при таком условии не поддерживается стационарный режим.
Подсчет средних характеристик
При изучении СМО важнейшими являются средние значения (математические ожидания) таких случайных величин:
n – количество требований, находящихся в системе;
v – длина очереди;
w – время ожидания в очереди.
Ниже их формулы:
n =
·/(1-
·);
v =
·2/(1-
·);
w = [
·/(1-
·)]*[1/
·].
Пример
Интенсивность потока автомобилей, поступающих на моечную станцию (одноканальная СМО) – 4 автомобиля в час, а интенсивность обслуживания – 5 автомобилей в час. Предполагая, что станция работает в стационарном режиме, найти среднее число автомобилей, находящихся на станции, среднюю длину очереди и среднее время ожидания обслуживания.
Решение
Определяем коэффициент загрузки системы:
· =
·/
· = 0,8.
Далее, используя изученные выше формулы, вычисляем все требуемые характеристики:
n = 0,8/(1-0,8) = 4;
v = 4*0,8 = 3,2;
w = 4/5 = 0,8.
Многоканальные СМО с отказами
Сделаем следующие предположения относительно таких систем:
входной поток пуассоновский;
время обслуживания распределено по экспоненциальному закону;
время обслуживания не зависит от входного потока;
все линии обслуживания работают независимо.
Будем считать, что система содержит некоторое количество линий обслуживания s. Она может находиться в состояниях Е0, Е1, Е2, Е3, ... ЕS. Расчёт переходных вероятностей показывает, что из каждого из свободных состояний система может переходить в соседнее состояние, либо в такое же, в каком была.
Для нахождения вероятностей используется следующая формула:
Pk =
·k/k!*P0,
· =
·/
·, где k = 1, 2, ...
Так как сумма всех вероятностей составляет 1, то [ Cкачайте файл, чтобы посмотреть картинку ]
Отсюда следуют формулы:
[ Cкачайте файл, чтобы посмотреть картинку ] [ Cкачайте файл, чтобы посмотреть картинку ]
Увеличение коэффициента загрузки системы ведет к увеличению вероятности отказа системы. Это не устраивает потребителей. Уменьшение вероятности отказа системы может быть достигнуто за счёт увеличения количества линий обслуживания.
Однако резкое увеличение количества линий не устраивает организатора, потому что ведёт к дополнительным затратам на приобретение новых линий обслуживания, и увеличивает вероятность простоя линий. Расчет показывает, что среднее число свободных линий обслуживания
· = s-
·(1-Ps).
Теперь ясно, что при сильном увеличении количества линий обслуживания, увеличится среднее число простаивающих линий.
Таким образом, мы имеем дело с двумя противоположными тенденциями. Задача сводится к выбору оптимального варианта. С этой целью будем минимизировать функцию стоимости СМО – С(s). Если через с1 мы обозначим стоимость одного отказа (организатор системы платит штраф за каждый отказ), а через с2 – стоимость простоя одной линии за единицу времени, то функция стоимости будет иметь следующий вид:
C(s) = c1
·Ps+c2
·.
Или в развернутом виде:
[ Cкачайте файл, чтобы посмотреть картинку ]
Сначала с увеличением s она убывает, а затем растёт. Наша задача состоит в том, чтобы найти её минимум.
Пример: Какое оптимальное число линий обслуживания должна иметь СМО, если известно, что
· = 2,
· = 1, c1 = 5, c2 = 1.
Решение
· =
·/
· = 2,
C(s) = 5*2*2s/s!(1+2+4/2!++2s/s!)+1*(s-2(1-Ps)),
P1 =
·/(1+
·) =2/3,
C(1) = 5*2*2/1(1+2)+1(1-2(1-2/3)) = 7.
Аналогично имеем:
C(2) = 4,8; C(3) = 3,5; C(4) = 3,1; C(5) = 3,44.
Таким образом, минимум функции стоимости достигается при s = 4, т. е. оптимальное число линий обслуживания – 4.
Многоканальные СМО с ожиданием
Предположения относительно систем, введенные ранее, остаются в силе. Изучение системы ведется по обычной схеме:
Выясняются возможные состояния системы (здесь их бесконечное множество).
Находятся переменные вероятности.
Составляется система уравнений для нахождения Рk – вероятностей пребывания системы в каждом из своих состояний.
Изучаем стационарный режим работы СМО.
Находятся все вероятности, через Р0. Результат таков:
[ Cкачайте файл, чтобы посмотреть картинку ]
Ведётся подсчет средних характеристик: j – среднее количество занятых линий; q – среднее число свободных линий; Р(w > 0) – вероятность ожидания; v – средняя длина очереди.
j =
·; q = s-
·;
P(w > 0) =
·s*P0/s!(1-
·/s); v =
·s+1P0/(s-1)!(s-
·)2.
Пример: Определить число взлетно-посадочных полос для самолётов с учетом требования, что вероятность ожидания Р(w > 0) должна быть меньше, чем 0,05. Интенсивность потока равна 27 требований в сутки и интенсивность линий обслуживания – 30 самолётов в сутки.
Решение
· =
·/
· = 0,9.
Используя приведенные выше формулы, имеем:
s = 1: P0 = (1+0,9+0,81/(1(1-0,9)))-1 = 0,1, P(w > 0) = 0,9*0,1/(1-0,9) = 0,9;
s = 2: P0 = 0,380, P(w > 0) = 0,276;
s = 3: P0 = 0,403, P(w > 0) = 0,07;
s = 4: P0 = 0,456, P(w > 0) = 0,015.
Таким образом, надо устраивать 4 взлетно-посадочные полосы.
Вариант 1
Техническое устройство состоит из трёх узлов и в любой момент времени может находиться в одном из восьми состояний (рис. 1).Численные значения интенсивности потоков событий: (1=2; (2=2; (3=1; (1=4; (2=4; (3=2. Найдите финальные вероятности сосотояний устройства.
Интенсивность потока автомобилей, поступающих на моечную станцию (одноканальная СМО) – 5 автомобиля в час, а интенсивность обслуживания – 6 автомобилей в час. Предполагая, что станция работает в стационарном режиме, найти среднее число автомобилей, находящихся на станции, среднюю длину очереди и среднее время ожидания обслуживания.
Какое оптимальное число линий обслуживания должна иметь СМО, если
· = 3,
· = 2, c1 = 4, c2 = 2.
Определить число взлетно-посадочных полос для самолётов с учетом требования, что вероятность ожидания Р(w > 0) должна быть меньше, чем 0,06. Интенсивность потока равна 28 требований в сутки и интенсивность линий обслуживания – 32 самолётов в сутки.
Вариант 2
Техническое устройство состоит из трёх узлов и в любой момент времени может находиться в одном из восьми состояний (рис. 1).Численные значения интенсивности потоков событий: (1=2; (2=1; (3=1; (1=4; (2=2; (3=2. Найдите финальные вероятности сосотояний устройства.
Интенсивность потока автомобилей, поступающих на моечную станцию (одноканальная СМО) – 6 автомобиля в час, а интенсивность обслуживания – 7 автомобилей в час. Предполагая, что станция работает в стационарном режиме, найти среднее число автомобилей, находящихся на станции, среднюю длину очереди и среднее время ожидания обслуживания.
Какое оптимальное число линий обслуживания должна иметь СМО, если
· = 4,
· = 2, c1 = 5, c2 = 2.
Определить число взлетно-посадочных полос для самолётов с учетом требования, что вероятность ожидания Р(w > 0) должна быть меньше, чем 0,06. Интенсивность потока равна 30 требований в сутки и интенсивность линий обслуживания – 34 самолётов в сутки.
Вариант 3
Техническое устройство состоит из трёх узлов и в любой момент времени может находиться в одном из восьми состояний (рис. 1).Численные значения интенсивности потоков событий: (1=1; (2=2; (3=2; (1=4; (2=4; (3=4. Найдите финальные вероятности сосотояний устройства.
Интенсивность потока автомобилей, поступающих на моечную станцию (одноканальная СМО) – 4 автомобиля в час, а интенсивность обслуживания – 5 автомобилей в час. Предполагая, что станция работает в стационарном режиме, найти среднее число автомобилей, находящихся на станции, среднюю длину очереди и среднее время ожидания обслуживания.
Какое оптимальное число линий обслуживания должна иметь СМО, если
· = 2,
· = 1, c1 = 3, c2 = 2.
Определить число взлетно-посадочных полос для самолётов с учетом требования, что вероятность ожидания Р(w > 0) должна быть меньше, чем 0,08. Интенсивность потока равна 28 требований в сутки и интенсивность линий обслуживания – 32 самолётов в сутки.
Вариант 4
Техническое устройство состоит из трёх узлов и в любой момент времени может находиться в одном из восьми состояний (рис. 1).Численные значения интенсивности потоков событий: (1=2; (2=2; (3=2; (1=2; (2=2; (3=4. Найдите финальные вероятности сосотояний устройства.
Интенсивность потока автомобилей, поступающих на моечную станцию (одноканальная СМО) – 8 автомобиля в час, а интенсивность обслуживания – 9 автомобилей в час. Предполагая, что станция работает в стационарном режиме, найти среднее число автомобилей, находящихся на станции, среднюю длину очереди и среднее время ожидания обслуживания.
Какое оптимальное число линий обслуживания должна иметь СМО, если
· = 7,
· = 8, c1 = 4, c2 = 2.
Определить число взлетно-посадочных полос для самолётов с учетом требования, что вероятность ожидания Р(w > 0) должна быть меньше, чем 0,06. Интенсивность потока равна 18 требований в сутки и интенсивность линий обслуживания – 22 самолётов в сутки.
Контрольные вопросы:
Дайте определение марковскому процессу.
Какие типы неопределенностей встречаются.
Дайте определение потоку событий.
Как составить уравнения Колмогорова.
Какие виды СМО Вы знаете?
При каких предположениях изучаются одноканальные СМО с отказами?
Почему стационарный режим в одноканальных СМО с ожиданием существует только при условии
· > 0?
Какие средние характеристики можно рассчитать в одноканальных СМО с ожиданием?
Практическое занятие№9
«Решение задачи управления запасами и задачи теории СМО, используя имитационное моделирование»
Цель занятия:
1.Научиться оценивать надежность простейших систем методом Монте-Карло;
2.Научиться рассчитывать СМО с отказами методом Монте-Карло.
Методические указания к выполнению заданий практического занятия
Суть имитационного моделирования
Имитационное моделирование – получение экспериментальной информации о сложном объекте, которая не может быть получена иным путем, как экспериментируя с его моделью на ПЭВМ.
Как остроумно подметил Ю. Адлер, сочетание слов имитация и моделирование недопустимо и является тавтологией. Но, рассматривая исторический процесс формирования этого термина, пришли к выводу, что это словосочетание определяет в моделировании такую область, которая относится к получению экспериментальной информации о сложном объекте, которая не может быть получена иным путем, как экспериментируя с его моделью на ПЭВМ.
Имитационный объект имеет вероятностный характер функционирования. Для исследователя представляют интерес выводы, носящие характер статистических показателей, оформленных, может быть, даже в виде графиков или таблиц, в которых каждому варианту исследуемых параметров поставлены в соответствие определенные средние значения с набором характеристик их распределения, без получения зависимости в аналитическом виде.
Эта особенность является и достоинством, и одновременно, недостатком имитационным моделей. Достоинство в том, что резко расширяется класс изучаемых объектов, а недостаток – в отсутствии простого управляющего выражения, позволяющего прогнозировать результат повторного эксперимента. Но в реальной жизни также невозможно для сколько-нибудь сложного объекта получить точное значение экономического показателя, а только лишь его ожидаемое значение с возможными отклонениями.
Главной функцией имитационной модели является воспроизведение с заданной степенью точности прогнозируемых параметров её функционирования, представляющих исследовательский интерес. Как объект, так и его модель, должны обладать системными признаками.
Функционирование объекта характеризуется значительным числом параметров. Особое место среди них занимает временной фактор. В большинстве моделей имеется возможность масштабирования или введения машинного времени, т. е. интервала, в котором остальные параметры системы сохраняют свои значения или заменяются некоторыми обобщенными величинами. Таким образом, за счет этих двух процессов – укрупнения единицы временного интервала и расчета событий этого интервала за зависящий от мощности ПЭВМ временной промежуток – и создается возможность прогноза и расчета вариантов управленческих действий.
Метод Монте-Карло
Неопределённость в предыдущих темах была стохастической. Поэтому строили аналитическую математическую модель и требовали, чтобы в данных задачах, рассматриваемые процессы были марковскими. На практике это не всегда выполняется и тогда требуется использовать методы имитационного моделирования. Что это такое рассказывалось в предыдущем параграфе, а теперь поговорим о самих методах имитационного моделирования.
Метод Монте-Карло является методом статистического моделирования или имитационного моделирования.
Метод Монте-Карло – это численный метод решения задач при помощи моделирования случайных величин.
Датой рождения метода Монте-Карло принято считать 1948 г. Создателями метода считают математиков Дж. Неймана и С. Улама.
Теоретическая основа метода была известна давно. Однако до появления ЭВМ этот метод не мог найти широкого применения.
Само название метода происходит от названия города Монте-Карло в княжестве Монако, знаменитого своими игорными домами. Дело в том, что одним из простейших механических приборов для получения случайных величин является рулетка. Возникает вопрос: помогает ли метод Монте-Карло выигрывать в рулетку? Нет, не помогает. И даже не занимается этим.
Идея метода чрезвычайно проста и состоит в следующем.
Вместо того чтобы описывать процесс с помощью аналитического аппарата, проводится розыгрыш случайного явления с помощью специально организованной процедуры, включающей в себя случайность и дающей случайный результат. Реализация случайного процесса каждый раз складывается по-разному, т. е. мы получаем различные исходы рассматриваемого процесса. Это множество реализаций можно использовать как некий искусственно полученный статистический материал, который может быть обработан обычными методами математической статистики. После такой обработки можно получить: вероятность события, математическое ожидание и т. д.
При помощи метода Монте-Карло может быть решена любая вероятностная задача, но оправданным он является тогда, когда процедура розыгрыша проще, а не сложнее аналитического расчета.
Оценка надежности простейших систем методом Монте-Карло
Пример: Система состоит из двух блоков, соединенных последовательно. Система оказывает при отказе хотя бы одного блока. Первый блок содержит два элемента: А, В (они соединены параллельно) и оказывает при одновременном отказе обоих элементов. Второй содержит один элемент С и отказывает при отказе этого элемента.
а) Найти методом Монте-Карло оценку Р* надежности (вероятности безотказной работы) системы, зная вероятности безотказной работы элементов: Р (А)=0,8, Р (В)=0,85, Р (С)=0,6; б) найти абсолютную погрешность (Р-Р* (, где Р- надежность системы, вычисленная аналитически. Произвести 50 испытаний.
Решение. а) Выбираем из таблицы приложения (равномерно распределенные числа) три случайных числа: 0,10, 0,09 и 0,73; по правилу *) (если случайное число меньше вероятности события, то событие наступило; если случайное число больше или равно вероятности события, то событие не наступило) разыграем события А, В, С, состоящие в безотказной работе соответственно элементов А, В, С. Результаты испытания будем записывать в расчетную таблицу .
Поскольку Р (А)=0,8 и 0,10 <0,8, то событие наступило, т.е. элемент А в этом испытании работает безотказно. Так как Р (В)=0,85 и 0,09< 0,85, то событие В наступило, т.е. элемент В работает безотказно.
Таким образом, оба элемента первого блока работают; следовательно, работает и сам первый блок. В соответствующих клетках табл. ставим знак плюс.
Таблица
Номер
испытания
Блок
Случайные числа,
моделирующие элементы
Заключение о работе
элементов
блоков
системы
А
В
С
А
В
С
1
Первый
Второй
0,10
0,09
0,73
+
+
-
+
-
-
2
Первый
Второй
0,25
0,33
0,76
+
+
-
+
-
-
3
Первый
Второй
0,52
0,01
0,35
+
+
+
+
+
+
4
Первый
Второй
0,86
0,34
0,67
-
+
-
+
-
-
Так как Р (С)=0,6 и 0,73< 0,6, то событие С не наступило, т.е. элемент с получает отказ; Другими словами, второй блок, а значит и вся система, получают отказ. В соответствующих клетках табл. 57 ставим минус.
Аналогично разыгрываются и остальные испытания. В табл. приведены результаты четырех испытаний.
Произведя 50 испытаний, получим, что в 28 из них система работала безотказно. В качестве оценки искомой надежности Р примем относительную частоту Р * =28/50=0,56.
б) Найдем надежность системы Р аналитически. Вероятности безотказной работы первого и второго блоков соответственно равны:
13 EMBED Equation.3 1415
Вероятность безотказной работы системы
P=P1*P2=0,97*0,6=0,582
Искомая абсолютная погрешность (Р-Р*(=0,582-0,56=0,022.
Расчет СМО с отказами методом Монте-Карло
Пример: В трехканальную систему массового обслуживания с отказом поступает пуассоновский поток заявок. Время между поступлениями двух последовательных заявок распределено по показательному закону f(()=5e-5( . Длительность обслуживания каждой заявки равна 0,5 мин. Найти методом Монте-Карло математическое ожидание а числа обслуженных заявок за время Т=4 мин.
Решение:
Пусть Т1=0- момент поступления первой заявки. Заявка поступит в первый канал и будет им обслужена. Момент окончания обслуживания первой заявки Т1+0,5=0+0,5=0,5. В счетчик обслуженных заявок записываем единицу.
Моменты поступления последующих заявок найдем по формуле
Т(= Т(-1+ (( ,
где (( - длительность времени между двумя последовательными заявками с номерами (-1 и (.
Возможные (( = - (1/() ln ri = = (1/()(- ln ri ).
Учитывая, что, по условию, (=5, получим (( =0,2 (- ln ri ).
Случайные числа ri берем из таблицы приложения, начиная с первой строки сверху. Для нахождения времени между поступлениями первой и второй заявок возьмем случайное число r=0,10.
Тогда (2=0,2*(-ln 0,10)=0,2*2,30=0,460. Первая заявка поступила в момент T1=0.
Следовательно, вторая заявка поступила в момент T2= T1+0,4600+0,460=0,460. В этот момент первый канал еще занят обслуживанием первой заявки, поэтому вторая заявка поступит во второй и будет им обслужена. Момент окончания обслуживания второй заявки T2+05=0,460+0.5=0.960 . В счетчик обслуженных заявок добавляем единицу.
По очередному случайному числу r=0.09 разыграем время (3 между поступлениями второй и третьей заявок:
(3=0,2(-ln 0,09)=0,2*2,41=0,482.
Вторая заявка поступила в момент T2= 0,460 . Поэтому третья заявка поступила в момент T3= T2+0,482=0,460+0,482=0,942. В этот момент первый канал уже свободен и третья заявка поступит в первый канал. Момент окончания обслуживания третьей заявки
T3+0,5=0,942+0,5=1,442.В счетчик обслуженных заявок добавляем единицу.
Дальнейший расчет производят аналогично (табл. 59), причем если момент поступления заявки все каналы заняты (момент поступления заявки меньше каждого из моментов окончания обслуживания), то в счетчик отказов добавляют единицу.
Заметим, что обслуживание 20-й заявки закончится в момент 4 148,>4, поэтому эта заявка получает отказ.
Испытание прекращают (в таблице записывают «стоп»), если момент поступления заявки T>4.
Таблица
номер заявки
i
Случайное числоri
-ln ri
Время между двумя последовательными заявками
(i=0,2(-ln ri)
Момент поступления заявки
Ti= Ti-1+(i
Момент
Ti+0,5
окончания обслуживания заявки каналом
Счетчик
1
2
3
Обслуженных заявок
отказов
1
0
0,500
1
2
0,10
2,30
0,460
0,460
0,960
1
3
0,09
2,41
0,482
0,942
1,442
1
4
0,73
0,32
0,064
1,006
1,506
1
5
0,25
1,39
0,278
1,284
1,784
1
6
0,33
1,11
0,222
1,506
2,006
1
7
0,76
0,27
0,054
1,560
2,060
1
8
0,52
0,65
0,130
1,690
1
9
0,01
4,60
0,920
2,610
3,110
1
10
0,35
1,05
0,210
2,820
3,320
1
11
0,86
0,15
0,030
2,850
3,350
1
12
0,34
1,08
0,216
3,066
1
13
0,67
0,40
0,080
3,146
3,646
1
14
0,35
1,05
0,210
3,356
3,856
1
15
0,48
0,73
0,146
3,502
4,002
1
16
0,76
0,27
0,054
3,556
1
17
0,80
0,22
0,044
3,600
1
18
0,95
0,05
0,010
3,610
1
19
0,90
00,10
0,020
3,630
1
20
0,91
0,09
0,018
3,648
4,148
1
21
0,17
1,77
0,354
4,002
(стоп)
итого
Х1=12
8
Из таблицы находим, что за 4 мин всего поступило 20 заявок; обслужено x1=12.
Выполним аналогично еще пять испытаний, получим x2=15, x3=14, x4=12, x5=13, x6=15.
В качестве оценки искомого математического ожидания а числа обслуженных заявок примем выборочную среднюю
a *=13 EMBED Equation.3 1415=(2*12+13+14+2*15)/6=13,5.
Задания
Вариант 1
Система состоит из двух блоков, соединенных последовательно. Первый блок содержит три элемента: А, В, С, а второй- два элемента: D, E. Элементы каждого блока соединены параллельно.
а) Найти методом Монте-Карло оценку Р* надежности системы, зная вероятности безотказной работы элементов: Р(А)=0,8; Р(В)=0,9; Р(С)=0,85; Р(D)=0,7; P(E)=0,6;
б) найти абсолютную погрешность (Р-Р*(, где Р- надежность системы, вычисленная аналитически. Произвести 15 испытаний.
В двухканальную систему массового обслуживания с отказом поступает пуассоновский поток заявок. Время между поступлениями двух последовательных заявок распределено по показательному закону f(()=4e-4( . Длительность обслуживания каждой заявки равна 1 мин. Найти методом Монте-Карло математическое ожидание а числа обслуженных заявок за время Т=8 мин.
Вариант 2
Система состоит из двух блоков, соединенных последовательно. Первый блок содержит два элемента: А, В, второй- три элемента: С, D, E. Элементы первого и второго блоков соединены параллельно.
а) Найти методом Монте-Карло оценку Р* надежности системы, зная вероятности безотказной работы элементов: Р(А)=0,8; Р(В)=0,9; Р(С)=0,7; Р(D)=0,75; P(E)=0,8;
б) найти абсолютную погрешность (Р-Р*(, где Р - надежность системы, вычисленная аналитически. Произвести 15 испытаний.
В трехканальную СМО с отказами поступает пуассоновский поток заявок. Время между моментами поступления двух последовательных заявок распределено по закону f(()=0,8e-0,8(; время обслуживания заявок 1,5 мин. Найти методом Монте-Карло математическое ожидание а числа обслуженных заявок за время Т=10мин.
Вариант 3
Система состоит из двух блоков, соединенных последовательно. Первый блок содержит три элемента: А, В, С, а второй- два элемента: D, E. Элементы каждого блока соединены параллельно.
а) Найти методом Монте-Карло оценку Р* надежности системы, зная вероятности безотказной работы элементов: Р(А)=0,9; Р(В)=0,5; Р(С)=0,95; Р(D)=0,8; P(E)=0,7;
б) найти абсолютную погрешность (Р-Р*(, где Р- надежность системы, вычисленная аналитически. Произвести 15 испытаний.
В двухканальную систему массового обслуживания с отказом поступает пуассоновский поток заявок. Время между поступлениями двух последовательных заявок распределено по показательному закону f(()=5e-5( . Длительность обслуживания каждой заявки равна 1,5 мин. Найти методом Монте-Карло математическое ожидание а числа обслуженных заявок за время Т=10 мин.
Вариант 4
Система состоит из двух блоков, соединенных последовательно. Первый блок содержит два элемента: А, В, второй- три элемента: С, D, E. Элементы первого и второго блоков соединены параллельно.
а) Найти методом Монте-Карло оценку Р* надежности системы, зная вероятности безотказной работы элементов: Р(А)=0,8; Р(В)=0,7; Р(С)=0,8; Р(D)=0,85; P(E)=0,6;
б) найти абсолютную погрешность (Р-Р*(, где Р - надежность системы, вычисленная аналитически. Произвести 15 испытаний.
В трехканальную СМО с отказами поступает пуассоновский поток заявок. Время между моментами поступления двух последовательных заявок распределено по закону f(()=8 e-8(; время обслуживания заявок 1мин. Найти методом Монте-Карло математическое ожидание а числа обслуженных заявок за время Т=8 мин.
Контрольные вопросы:
В чем заключается суть имитационного моделирования?
В чем заключаются достоинства и недостатки такого типа моделирования?
Как применяется метод Монте-Карло?
Какие способы получения случайных величин Вы знаете?
Практическое занятие№10
«Построение прогнозов количественными и качественными методами. Выбор и обоснование наиболее рационального метода и алгоритма решения задачи, а также оценка сложности выбранного алгоритма»
Цель занятия:
Научиться применять МНК для линейного сглаживания данные.
Научиться сглаживать данные с помощью квадратичной функции.
Методические указания к выполнению заданий практического занятия
Метод наименьших квадратов один из методов [ Cкачайте файл, чтобы посмотреть ссылку ] для оценки неизвестных величин по результатам измерений, содержащим случайные ошибки.
Метод наименьших квадратов применяется также для приближённого представления заданной функции другими (более простыми) функциями и часто оказывается полезным при обработке наблюдений.
Метод наименьших квадратов предусматривает нахождение параметров функциональной зависимости из условия минимума суммы квадратов отклонений.
1. Если 13 EMBED Equation.3 1415 - линейная функция, т.е. 13 EMBED Equation.3 1415, то 13 EMBED Equation.3 1415, неизвестные параметры 13 EMBED Equation.3 1415определяются из системы
13 EMBED Equation.3 1415 (1)
Формулы, служащие для аналитического представления опытных данных, получили название эмпирических формул.
Система (1) называется системой нормальных уравнений.
2. Если 13 EMBED Equation.3 1415 - квадратичная функция, т.е. 13 EMBED Equation.3 1415, то 13 EMBED Equation.3 1415, неизвестные параметры 13 EMBED Equation.3 1415определяются из системы нормальных уравнений:
13 EMBED Equation.3 1415 (2)
Пример 1.
С помощью МНК подобрать параметры a и b линейной функции 13 EMBED Equation.3 1415, приближенно описывающей следующие опытные данные.
Построить полученную прямую и исходные точки в одной системе координат.
13 EMBED Equation.3 1415
0
1
1,5
2,1
3
13 EMBED Equation.3 1415
2,9
6,3
7,9
10
13,2
Решение:
Параметры 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415 искомой функции найдем из системы нормальных уравнений. Для этого перепишем ее в следующем виде:
13 EMBED Equation.3 1415
Для решения задачи составим таблицу.
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
1
0
2,9
0
0
2
1,0
6,3
1
6,3
3
1,5
7,9
2,25
11,85
4
2,1
10,0
4,41
21
5
3,0
13,2
9,0
39,6
·
7,6
40,3
16,66
78,75
Тогда система нормальных уравнений примет вид:
13 EMBED Equation.3 1415.
Решим систему.
Для этого выразим 13 EMBED Equation.3 1415 из второго уравнения:
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
Подставим в первое уравнение:
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415.
Отсюда 13 EMBED Equation.3 1415.
Итак, 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, и, следовательно, искомая функция имеет вид:
13 EMBED Equation.3 1415.
Построим полученную прямую и исходные точки в одной системе координат.
Вывод:
Так как исходные данные и полученная прямая расположены близко друг к другу, то аппроксимирующая функция найдена правильно.
Задание
Задание 1. С помощью МНК подобрать параметры a и b линейной функции 13 EMBED Equation.3 1415, приближенно описывающей следующие опытные данные. Построить полученную прямую и исходные точки в одной системе координат.
вариант
1
13 EMBED Equation.3 1415
1
3
4
5
6
8
13 EMBED Equation.3 1415
6
4
4
2
3
2
2
13 EMBED Equation.3 1415
2
3
4
5
7
8
13 EMBED Equation.3 1415
1
3
4
6
6
9
3
13 EMBED Equation.3 1415
1
2
4
6
7
8
13 EMBED Equation.3 1415
7
6
4
5
3
3
4
13 EMBED Equation.3 1415
2
3
4
5
7
8
13 EMBED Equation.3 1415
2
6
6
7
8
10
Задание 2. С помощью МНК подобрать параметры a и b квадратичной функции 13 EMBED Equation.3 1415, приближенно описывающей следующие опытные данные. Построить полученную линию и исходные точки в одной системе координат.
вариант
1
13 EMBED Equation.3 1415
2
2,5
3
3,5
4
4,5
13 EMBED Equation.3 1415
4,2
2,5
6,2
7,5
2,6
1
2
13 EMBED Equation.3 1415
1
1,5
2
2,6
2,9
3,1
13 EMBED Equation.3 1415
2,6
5,6
4,3
1,6
2,6
3,4
3
13 EMBED Equation.3 1415
2
3
3,6
3,8
4,2
4,6
13 EMBED Equation.3 1415
0
2,3
2,5
2,9
1
4,5
4
13 EMBED Equation.3 1415
5
5,5
6
6,5
7
7,5
13 EMBED Equation.3 1415
4,5
4,6
8,5
2,6
4,5
6,7
Контрольные вопросы:
Какова общая постановка задачи нахождения эмпирических формул?
Каким образом можно оценивать качество приближения?
Каким образом графически можно интерпретировать постановку задачи нахождения эмпирических формул?
В чем сходство и различие постановки задачи метода наименьших квадратов и задачи интерполяции?
Какие виды приближающих функций обычно применяются?
В чем суть метода приближения таблично заданной функции по методу наименьших квадратов линейной функцией?
Как сводится задача построения различных эмпирических формул к задаче нахождения линейной функции?
Литература
Основные источники
Партыка Т.Л., Попов И.И. Математические методы. – М.: ФОРУМ : ИНФРА-М, 2012.
Агальцов В.П., Волдайская И.В.. Математические методы в программировании: Учебник.- М.: ФОРУМ: ИНФРА-М, 2008.
Дополнительные источники
Фомин Г.П. Математические методы и модели в коммерческой деятельности: Учебник. – М.: Финансы и статистика, 2008.
Попов А.М. Экономико-математические методы и модели :учебник.-М.: Юрайт, 2012
Интернет-ресурсы
Единое информационно-образовательное пространство колледжа NetSchool. Форма доступа: http://sgtek.ru
Информационно-справочная система «В помощь студентам». Форма доступа: http://window.edu.ru
Информационно-справочная система. Форма доступа: [ Cкачайте файл, чтобы посмотреть ссылку ].
Информационно-справочная система. Форма доступа: [ Cкачайте файл, чтобы посмотреть ссылку ]
13 PAGE \* MERGEFORMAT 14115
x5
x3
x2
x1
x4
Рисунок 4321Root EntryEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeРисунок 56Equation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation Native