Боярская Татьяна Александровна.
Математические Методы.
03.09.2012
Математическая модель – это приближенное описание какого либо класса явлений или объектов реального мира на языке математики.
Основные этапы мат. Моделирования:
Построение модели. (Формулирование задачи)
Решение математической задачи, к которой приводит модель
Интерпретация полученных результатов
Проверка адекватности модели
Модификация модели
05.09.2012
Способы построения мат. Моделей
Определение целей моделирования
Модель нужна, чтобы понять как устроен объект
Модель нужна, чтобы научиться управлять объектом
Модель нужна, чтобы прогнозировать прямые и косвенные последствия реализации заданных способов и форм воздействия на объект
Поиск математического описания
Классификация мат. Моделей:
По отраслям науки
По применяемому математическому аппарату
Детерминированные и стохастические
По целям моделирования
07.09.2012
Виды моделей:
Дескриптивные (описательные). Траектория полета, например.
Оптимизационные модели. Модели, в которых необходимо найти максимумы.
Многокритериальные. Задача, которая зависит от многих критериев.
Игровые модели
Имитационные модели
Классификация задачей характеризующихся практической деятельностью
Класс снабжения предприятия
Постройка участка магистрали
Продажа сезонных товаров
Снегозащита дорог
Противолодочные рейды
Выборочный контроль продукции
Медицинское обследование
Библиотечное обслуживание
Задача о ранце, задача о коммивояжер, транспортная задача, задача об упаковке, составление расписания
Графическое решение задач линейного программирования
Метод применяется для решения задач линейного программирования с двумя переменными заданными в не канонической форме и многими переменными в канонической форме, при условии, что они содержат не более двух свободных переменных.
10.09.2012
С геометрической точки зрения задача линейного программирования ищется такая угловая точка или набор точек из допустимого множества решений, на котором достигается самая верхняя/нижняя линия уровня расположенная дальше остальных в направлении наискорейшего роста.
gradL(X ̅ )=oL/(oX_1 ) e_1+oL/(oX_2 ) e_2=C ̅
Алгоритм решения задач
Находим область допустимых значений
Строим вектор C
Проводим линию уровня перпендикулярно вектору С
Для задач на максимум линию уровня перемещаем в направление роста вектора С, для задач на минимум – наоборот
Находим координаты точки экстремума и значение целевой функции в ней
Пример. Выбор оптимального варианта выпуска изделия.
Фирма выпускает два вида мороженного: сливочное и шоколадное. Для изготовления используются два основных компонента: молоко и наполнители.
Исходн. Прод. Расход прод. На 1кг. Запасы
Сливочное Шоколадное
Молоко 0.8 0.5 400
Наполнители 0.4 0.8 365
Суточный спрос на сливочное мороженное превышает спрос на шоколадное не более чем на 100кг. Спрос на шоколадное не превышает 350кг. Розничная цена сливочного – 16р, шоколадное – 14р за 1кг. Какое количество мороженного каждого вида фирма должна произвести что бы прибыль от реализации была максимальна.
X1-суточное производство сливочного мороженного, кг
X2 – шоколадного, кг
L(X)=16*X_1+14*X_2→max
{█(0,8*X_1+0,5*X_2≤400@0,4*X_1+0,8*X_2≤365@X_1-X_2≤100@X_2≤350)┤
{█(0,8*X_1+0,5*X_2=400@0,4*X_1+0,8*X_2=365)┤
X_1=((365-0,8*300))/0,4
L=16*312,5+14*300=9200
Симплекс метод решения задач линейного программирования
Опорным решением называется базисное неотрицательное решение
Алгоритм решения:
Математическая модель задачи должна быть канонической (только равенства)
Находится опорное решение и проверяется на оптимальность. Для этого все строки, за исключением индексной, заполняются по данным системы ограничений и целевой функции. Индексная строка заполняется следующим образом: ∆i=∑_(j=1)^m▒〖C_i h_ij 〗-C_j
Если все дельта житые больше или равны нуля то найденное решение оптимально
Если хотя бы одна дельта житая меньше нуля, но при соответствующей переменной нет ни одного положительного коэффициента решение прекращается так как целевая функция не ограничена в области допустимых значений
Если хотя бы одна оценка отрицательна и при соответствующей переменной есть хотя бы один положительный коэффициент то вводится новое опорное решение
Если отрицательных оценок несколько то в столбец базисной переменной вводят ту переменную которой соответствует наибольшая по абсолютной величене отрицательная оценка
Заполняется следящий этап. Заполняется симплексная таблица 2го этапа.
11.09.2012
Пример. Анализ эффективности использования производственного потенциала предприятия.
Предприятие располагает тремя производственными ресурсами: сырье, оборудование и электроэнергия. И может организовать производство двумя различными способами
Ресурсы Расход ресурсов на 1 мес. Общий ресурс
1 способ 2 способ
Сырье 1 2 4
Оборудование 1 1 3
Электроэнергия 2 1 8
При первом способе производства предприятие выпускает за месяц 300 ед. продукции, при втором 4000 ед. Сколько месяцев должно работать предприятие каждым из этих способов, что бы при наличных ресурсах обеспечить максимальный выпуск продукции.
X_1-I,X_2-II
L(X)=3X_1=4X_2→max
{█(X_1+2X_2≤4@X_1+X_2≤3@〖2X〗_1+X_2≤8@X_1≥0,X_2≥0)┤
Доведение мат.модели к каноническому виду
(L(X)=3X_1=4X_2→max)¦{█(█(X_1+2X_2+X_3=4@X_1+X_2+X_4=3@2X_1+X_2+X_5=8@X1,X2,X3,X4,X5≥0)@)┤
Ci БП 3 4 0 0 0 L(X)
X1 X2 X3 X4 X5 Bi
0 X3 1
2
1 0 0 4
0 X4 1 1 0 1 0 3
0 X5 2 1 0 0 1 8
∆i -3 -4 0 0 0 0
4 X2 1/2 1 ½ 0 0 2
0 X4 1/2 0 -1/2 1 0 1
0 X5 3/2 0 -1/2 0 1 6
∆i -1 0 2 0 0 8
4 X2 0 1 1 -1 0 1
3 X1 1 0 -1 2 0 2
0 X5 0 0 1 -3 1 3
∆i 0 0 1 2 0 10
4/2=2; 3/1=3; 8/1=8
2/1/2=4; 1/1/2=2; 6/3/2=4
Xопт.=(2,1,0,0,0)
L=3*2+4*1
Транспортная задача
В Am пунктах производства имеется однородный груз в количестве am. Этот груз необходимо доставить в Bn пунктах назначения в количествах bn. Стоимость перевозки единицы груза из пункта Ai в пункт Bj обозначается Cij. Требуется составить план перевозок позволяющий вывести все грузы и имеющий минимальную стоимость.
Транспортные задачи бывают нескольких типов:
∑_(i=1)^m▒ai=∑_(j=1)^n▒bj-закрытая.
∑_(i=1)^m▒ai≠∑_(j=1)^n▒bj-открытая.
Математическая модель транспортной задачи имеет следующий вид:
L(X)=∑_(i=1)^m▒∑_(j=1)^m▒〖C_ij X_ij→min〗
{█(∑_(j=1)^m▒〖X_ij=a_i 〗@∑_(i=1)^m▒〖X_ij=b_j 〗@X_ij≥0)┤
Оптимальным решением является матрица. Хопт.=(Xij)mxn
На складах A1, A2 и A3имеются запасы продукции 90, 400 и 100 соответственно. Потребители B1, B2, B3 должны получить эту продукцию в количестве 140, 300, 160 соответственно. Стоимость перевозки представлена матрицей
■(2&5&2@4&1&5@3&6&8)
B1 B2 B3 ∑▒
A1 902 5 2 90
A2 4 2401 1605 400
A3 503 606 8 110
∑▒ 140 300 160 600
∑▒〖90*2+240*1+160*5+50*3+60*6=1730〗 стоимость перевозки груза
Проверку решения на оптимальность проводят методом потенциалов.
Решение транспортной задачи является оптимальным, если ему соответствует система из m+n действительных чисел Ui и Vj
Ui + Vj=Cij – зан
Ui + Vj-Cij <0 –своб
(u_1+v_1=2)¦█(u_2+v_2=1@u_2+v_3=5@u_3+v_1=3@u_3+v_2=6@------@u_1=0@u_2=-4@u_3=1@v_1=2@v_2=5@v_3=9)
∆_12=u1+v2-C12=0+2-5=-3
∆_13=u1+v3-C13=0+9-2=730
∆_21=u2+v1-C21=-4+2-4=-6
∆_33=u3+v3-C33=1+9-8=270
∑▒〖90*2+90*4+240*1+70*5+50*3+60*6=1640〗
u1+v3=2
u1+v1=4
u2+v2=1
u2+v3=5
u3+v1=3
u3+v2=6
22.10.2012
Для выпуска конкурентно способно продукции надо:
Подготовка ТЗ на переоборудование участка (30 дней)
Заказ и поставка нового оборудования (60 дней)
Заказ и поставка нового электрооборудования (50 дней)
Демонтаж старого и установка нового оборудования (90 дней)
Демонтаж старого и установка нового электрооборудования (80 дней)
Переобучение персонала (30 дней)
Испытание и сдача в эксплуатацию оборудования на производство (20 дней)
Ожидается, что производительность после ввода линии в эксплуатацию составит 20 тонн мороженного в день. Прибыль от реализации 1 тонны составляет 0,5 тысяч в сутки.
Деньги на покупку и переоборудование участка в размере 2 миллиона руб. взяты в банке под 20% годовых. Из расчета 1,5 миллиона на покупку, 500 тыс на демонтаж и установку.
Затраты
Работа Нормальный режим Экстремальный режим
Продолжительность работы, дней Затраты, тыс. рублей Продолжительность работы, дней Затраты, тыс. рублей
1 30 20 25 30
2 60 40 45 60
3 50 30 40 40
4 90 70 70 100
5 80 60 65 70
6 30 25 20 25
7 20 20 17 25
Итог 360 265 282 350
Определить через какое время можно будет отдать кредит.
Нормальный путь
Через 200 дней после начала работ предприятие изтратит 1,5 миллиона на приобритение оборудование и 266 тысяч на его установку и сдачу в экспуатацию.
Построим график изменения кредита в зависимости от времени получения прибыли.
Составим уравнение прямой проходящей через две точки
Через 360 дней после получения кредита долг предприятия составит 2400 тыс. руб.
((y-y_A ))/(y_B-y_A )=(x-x_A)/(x_B-x_A )
(y-2000)/(2400-2000)=(x-Q)/(360-0)
10x-9y+18000=0
Найдем уравнение прибыли
Известно, что через 200 дней у нас остается 235 тыс рублей. Через 100 дней посне начала выпуска продукции предприятие получит прибыль 1 миллион руб.
(y-235)/(1000-235)=(x-200)/(300-200)
10x-y-1765=0
{█(10x-9y+18000=0@10x-y-1765=0)┤
y=2471 т.р.
x=423 дня
График выполнения работ может быть сжат, за счет выполнения некоторых операций в кратчайшие сроки.
*Граф с зачеркнутыми*
В ускоренном режиме тратим дополнительно 70 тыс.
{█(10x-9y+18000=0@10x-y-1410=0)┤
2000-1500-265=0
257-1160т.р.
(x-157)/(257-157)=(y-160)/(1160-160)
y=2426 т.р.
x=383,6=384 дней
Задача минимизация сети состоит в отыскании ребер, соединяющих все узлы сети и имеющих минимальную суммарную длину.
Телевизионная фирма планирует создание кабельной сети для обслуживания 5ти районов новостроек.
Нахождение кратчайшего пути
Задача состоит в нахождении дорог находящихся на транспортном пути, которые имеют минимальную длинну.
d_ij i→j
U_j=〖min〗_j {U_
U1=0
U2=U1+d1,2=0+2=2
U3=U1+d1,3=0+4=4
U4=min(U1+d1,4; U2+2,4; U3+d3,4)=min(0+10; 2+11; 4+3)=7
U5=min(U2+d2,5; U4+d4,5)=7
U6=min(U3+d3,6; U4+d4,6)=5
U7=min(U5+d5,7; U6+d6,7)=13
Задача замены автопарка
Фирма по прокату автомобилей планирует замену автопарка на очередные 5 лет. Автомобиль должен проработать не менее 1 года, прежде чем будет поставлен вопрос о его замене.
30.10.2012
Система массого обслуживания (СМО)
Ситуации связанные с ожиданием потребности в обслуживании называют системами массового обслуживания. Цель изучения СМО контроль характеристик системы и установление зависимости между числом обслуживаемых единиц и качества обслуживания.
Основные элементы СМО:
Источник заявок: входящий поток, каналы обслуживания, выходящий поток. В зависимости от характера формирования очереди различают:
СМО с отказами
СМО без отказов (с неограниченным ожиданием)
Входящий поток – это поток заявок обладающих свойствами: стационарности, ординарности и отсутствием последействия.
Вероятность того, что число заявок поступивших за время t в количестве k определяется
P_k (t)=((t))/k!
Лямбда – среднее число заявок
f(t)=μe^(-μt)
μ=1/t_оч
f(t_обс )=me^(-mt)
m=1/t_обс
p=λ/m
…….
B1=1 B2=2 B3=3
A1=1 0 -1 -2
A2=2 1 0 -1
A3=3 2 1 0
Задача первого игрока максимизировать выйгрышь, задача второго – минимизировать пройгрышь.
Для данной игры платежная матрица выглядит следущим образом: (■(0&-1&-2@1&0&-1@2&1&0))
Найдем наилучшую стратегию первого игрока (A).
ai=min(ai). Зная минимальные выйгреши при каждой стратегии первый игрок выберет максимальный из них. α=max(min(a_ij )) – это гарантираванный выйгрешь первого игрока.
α=0
β=min(max(a_ij ) )
β=0
α≤β
если α=β то игра называется игрой с силовой точкой
есди платежная матрица не имеет силовой точки то игра идет в смешанных стратегиях.
x_i ∑_(i=1)^n▒〖x_i=1〗
∑_(j=1)^m▒〖y_j=1〗
Выйгрышь второго игрока при использовании первыйм игроком смешанных стратегий определяют как математическое ожидание выйгреша. ∑_(i=1)^n▒∑_(j=1)^m▒〖a_j x_i y_i 〗
Применение оптимальной стратегии позволяет получить выйгрышь равной цены игры. Применение первыйм игроком оптимальной стратегии позволяет получить выйгрышь не менее цены игры. Оптимальная стратегия второго игрока позволяет получить выйгрешь не более цены игры.
α≤μ≤β
■(7&6&5@5&4&3@5&6&6) ■(4&2@2&3@3&5)
■(2&3&3) ■(2&4)
■(4&2@3&5)
α=max(2,3)=3
β=min(4,5)=4