Разработка математических моделей решения задач

МИНИСТЕРСТВО ВЫСШЕГО И СРЕДНЕГО СПЕЦИАЛЬНОГО

ОБРАЗОВАНИЯ РЕСПУБЛИКИ УЗБЕКИСТАН

Кафедра "Информатика и математика"

Лабораторная работа

По дисциплине "МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ"

для студентов направления "Информатика и информационные технологии"

Составитель: Сапаев У.

Лабораторная работа № 1,2

Тема: Разработка математической модели. Решение задач линейного программирования симплекс-методом.

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

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

1. Четыре студента: Иванов, Петров, Сидоров и Васильев пошли на концерт группы "Чайф", захватив пиво 2 сортов: "Русич" и "Премьер". Определить план распития напитков для получения максимального суммарного опьянения (в ). Исходные данные даны в таблице:

СтудентНорма выпитогоЗапасы (в литрах) "Русич""Премьер"Иванов221.5Петров3,511,5Сидоров1044,5Васильев-10,7Крепость напитка16 %10 %

. Математическая модель.

.1 Управляемые параметры

x1 [л] - количество выпитого пива "Русич".

x2 [л] - количество выпитого пива "Премьер".

- решение.

.2 Ограничения

- количество пива "Русич", выпитого Ивановым.

- количество пива "Премьер", выпитого Ивановым.

- общее количество пива, выпитого Ивановым.

Общее количество пива, выпитого Ивановым, не превосходит имеющихся у него запасов пива, поэтому:

(л).

Аналогично строим другие ограничения:

(л).

(л).

(л).

. Постановка задачи.

Найти *, где достигается максимальное значение функции цели:

. Решение.

при:

Приведем задачу к каноническому виду:

Определим начальный опорный план: .

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

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

Предположим, что , тогда:

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

=>

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

Из ограничения (2) имеем: .

Подставляя в функцию цели: получаем:

Оформим данный этап задачи в виде симплекс-таблицы:

Начальная симплекс-таблица:

16100000СвБ.П. X1X2X3X4X5X6в0X32210001,50X43,5101001,50X510400104,50X60100010,7F-16-1000000

;

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

16100000СвБ.П. X1X2X3X4X5X6В0X301,4281-0,572000,64216X110,28600,286000,4280X501,140-2,86100,2140X60100010,7F0-5,42404,576006,857

;

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

откуда получаем:

;

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

=>

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

, а из ограничений (2) и (3): . Тогда: ;

16100000СвБ.П. X1X2X3X4X5X6В0X30013-1,2500,37516X11001-0,2500,37510X2010-2,50,87500,18750X60002,5-0,87510,5125F000-94,7507,875

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

откуда получаем:

;

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

=>

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

, а из ограничений (1) и (2):

. Тогда:

;

16100000СвБ.П. X1X2X3X4X5X6в0X4000,3331-0,41600,12516X110-0,33300,16600,2510X2011,8330-0,16600,50X600-0,83300,16610,2F0030109

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

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

Задание лаборатория

. Найдите максимум функции z = 4xl + 3х2 (xi ? 0) при условии

x1-x2? - 2,5x1+3x2?15,x2? 2,5,2x1-x2? - 2,x1-2x2? 2.

. Для откорма крупного рогатого скота используется два вида кормов b1и b2, в которые входят питательные вещества а1, а2, а3 и a4. Содержание количеств единиц питательных веществ в одном килограмме каждого корма, стоимость одного килограмма корма и норма содержания питательных веществ в дневном рационе животного представлены в таблице. Составьте рацион при условии минимальной стоимости.

Питательные вещества Вид кормов Норма содержания питательного вещества B1 B2 A1 3 4 24 A2 1 2 18 A3 4 0 20 A4 0 1 6 Стоимость 1 кг корма, руб. 2 1

3. Трикотажная фабрика использует для производства свитеров и кофточек чистую шерсть, силон и нитрон, запасы которых составляют, соответственно, 800, 400 и 300 кг.

Вид сырья в пряже Затраты пряжи на 10 шт., Свитер Кофточка Шерсть 4 2 Силон 2 I Нитрон 1 1 Прибыль, руб. 6 5

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

. При подкормке посевов необходимо внести на 1 га почвы не менее 8 единиц химического вещества А, не менее 21 единиц химического вещества В и не менее 16 единиц химического вещества С. Фермер закупает комбинированные удобрения двух видов I и П. В таблице указано содержание количества единиц химического вещества в 1 кг каждого вида удобрений и цена 1 кг удобрений. Определите потребность фермера в удобрениях I и II вида на 1 га посевной площади при минимальных затратах на их приобретение.

Химические вещества Содержание химических веществ в I кг удобрения I II А 1 5 В 12 3 С 4 4 Цена 1 кг удобрения, руб 5 2

Лабораторная работа №3

ТЕМА: Транспортная задача.

Цель работы: Изучить метод потенциалов.

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

Пример 2. Фирма обслуживающая туристов прибывающих на отдых, должна разместить их в 4 отелях: Морской, Солнечный, Слава и Уютный, в которых забронировано соответственно 5, 15, 15 и 10 мест. Пятнадцать туристов прибывают по железной дороге, двадцать пять прилетают очередным рейсом в аэропорт, а пять человек прибудут на теплоходе на морской вокзал. Транспортные расходы при перевозке из пунктов прибытия в отели приведены в таблице 1.

Таблица 1

Исходный пункт, iПункт назначения (отели), jМорскойСолнечныйСлаваУютный1234Железнодо-рожный вокзал 1 10 0 20 11Аэропорт2127920Морской вокзал30141618

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

I. Математическая модель задачи.

) Переменные задачи. Обозначим количество туристов, которые будут перевозиться из пункта i в отель j как Xij (i=1,2,3; j=1,2,3,4). Это переменные задачи, значения которых должны быть определены в процессе решения. Например, X23 - это число туристов, которое должно быть перевезено из аэропорта (пункт 2) в отель Слава (пункт 3). В задаче содержится 3*4=12 переменных.

) Ограничения на переменные задачи. Очевидно, что все переменные задачи не отрицательные и целые числа, т.е.

Xij 0, (1)

Xij - целые числа, (2)

где i=1, 2, 3; j=1, 2, 3, 4.

Кроме этого, должны быть удовлетворяться следующие условия. Число туристов, вывозимых с железнодорожного вокзала (пункт 1) равно 15, поэтому:

X11 + X12 + X13 + X14 = = 15 (3)

Аналогично для аэропорта (пункт 2):

X21 + X22 + X23 + X24 = = 25 (4)

И для морского вокзала (пункт 3):

X31 + X32 + X33 + X34 = = 5 (5)

По условию задачи в отеле Морской (пункт 1) забронировано 5 мест, поэтому:

X11 + X21 + X31 = = 5 (6)

Аналогично, для отеля Солнечный (пункт 2):

X12 + X22 + X32 = = 15 (7)

Для отеля Слава (пункт 3):

X13 + X23 + X33 = = 15 (8)

Для отеля Уютный" (пункт 4):

X14 + X24 + X34 = = 10 (9)

Обычно транспортная задача представляется в виде таблицы, где в ячейках помещаются переменные задачи (Xij), а в правом верхнем углу ячейки стоят стоимости перевозки из пункта i в пункт j (Cij). В крайнем правом столбце и нижней строке таблицы записываются числа определяющие ограничения задачи (в данном примере - это число туристов в исходных пунктах и число мест в пунктах назначения - отелях).

Для примера 2 таблица имеет вид (таблица 2):

Таблица 2

Исходный пункт, iПункт назначения (отели),jЧисло туристов в исходном пункте123410020111X11X12X13X14151279202X21X22X23X242501416183X31X32X33X345Число мест в отеле 5 15 15 10???????????????????? ?????????????????????????

Транспортная задача, для которой суммы чисел в последнем столбце и нижней строке равны, называется сбалансированной: 15 + 25 + 5 = 45, 5 + 15 + 15 + 10 = 45. Если транспортная задача не сбалансирована, то в таблицу добавляется еще одна строка или столбец. Причем стоимости перевозки в добавленных ячейках принимаются равными нулю.

Для нашего примера предположим, что в аэропорт прибыло не пять, а десять туристов. Сумма чисел в последнем столбце будет равна: 15 + 25 + 10 + 50. Чтобы сбалансировать задачу вводим пятый столбец (фиктивный отель) с пятью местами. Таблица в этом случае будет иметь вид (таблица 3):

Таблица 3

Исход-ный пункт, iПункт назначения (отели),jЧисло турис-тов в исход. пункте12345100201101X11X12X13X14X151512792002X21X22X23X24X2525014161803X31X32X33X34X3510Число мест в отеле 5 15 15 10 5???????????????? ?????????????????????????

3) Целевая функция. Транспортные расходы на перевозку туристов в отели вычисляются по формуле:

Z = CijXij = 10X11 + 0X12 + 20X13 +. +18X34 (10)

Окончательно транспортная задача имеет вид (таблица 2). Нужно найти такие значения переменных Xij (i=1,2,3; j=1,2,3,4) при которых целевая функция, определяемая формулой (10), будет иметь минимальное значение и будут выполнены ограничения (1) ¸ (9):

Xij 0, где Xij - целые числа (i=1,2,3; j=1,2,3,4)

?;

?;

?;

Как и в рассмотренной выше задаче распределения ресурсов (пример 1) транспортная задача является задачей линейного программирования и может быть решена симплекс-методом. В виду специфики транспортной задачи для нее был разработан специальный метод решения - метод потенциалов (см. Л1).

II. Решение транспортной задачи в процедуре EXCEL Поиск решения

) Ввод данных. Вводим данные таблицы 1 и 2 в ячейки EXCEL (рис.17).

В ячейках B3: E5 введены стоимости перевозок (табл.1).

В ячейках F3: F5 находится число прибывающих туристов. А в ячейках B6: E6 находится число мест в отелях. Ячейки B8: E10 - рабочие (изменяемые) ячейки, в которых будут вычисляться значения переменных задачи Xij.

В ячейках F8: F10 нужно записать формулы для вычисления левых частей ограничений (3) ¸ (5):

в F8 должна быть сумма ячеек B8: E8;

в F9 должна быть сумма ячеек B9: E9;

в F10 должна быть сумма ячеек B10: E10.

Формулы для вычисления левых частей ограничений (6) ? (9) введем в ячейки B11: E11:

в B11 должна быть сумма ячеек B8: B10;

в C11 должна быть сумма ячеек C8: C10;

в D11 должна быть сумма ячеек D8: D10;

в E11 должна быть сумма ячеек E8: E10;

Целевую функцию поместим в ячейку G3:

G3: СУММПРОИЗВ (B3: E5; B8: E10).

Таблица исходных данных имеет вид (Рис.17):

Рис.17

) Заполнение окна процедуры "Поиск решения".

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

значение целевой функции: min;

изменяемые ячейки: B8: E10;

ограничения задачи:

F8: F10 = F3: F5 (формулы (3) ¸ (5))

B11: E11 = B6: E6 (формулы (6) ¸ (9))

B8: E10 0 (1) и B8: E10 - целые числа (2)

В окне "Параметры" установить "Линейная модель", что соответствует решению задачи симплекс-методом. Результаты заполнения окна показаны на рис.18:

Рис.18

Выполнив процедуру "Поиск решения" получим следующие результаты (рис. 19):

Рис. 19

Таким образом с железнодорожного вокзала (исходный пункт 1) следует 10 туристов отвезти в отель "Уютный" (пункт 4) и 5 туристов в отель "Солнечный" (пункт назначения 2); из аэропорта (исходный пункт 2) 10 туристов отвезти в отель "Солнечный" (пункт назначения 2) и 15 туристов в отель "Слава" (пункт назначения 3); туристов прибывающих на морской вокзал (исходный пункт 3) нужно отправить в отель "Морской" (пункт назначения 1). Все эти результаты видны в конечной таблице (рис. 19) При этом суммарная стоимость транспортных расходов составит 315 рублей (ячейка G3).

bi аi303030201453051440451

.

b iаi12080501301767061150761

.

bi аi15015010020013415043150314

.

bi аi7070701101307031330331

.

bi аi705050508616018660681

12.

bi аi12090701002539032590532

.

bi аi8080801602794033640427

.

bi аi13060402013215021360312

.

bi аi20303010302324403251204326

16.

bi аi30253520503241402315203244

17.

bi аi709011015012025461303113215031032

.

bi аi250300350300350234330023125503134

Лабораторная работа №4

ТЕМА: Создание концептуальной модели

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

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

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

Рис.1. Отображение оригинала So и модели Sm в сознании исследователя

Первоначально концептуальная модель системы So возникает в сознании исследователя j (рис.1). Модель ориентируется на выявление определенных свойств системы в соответствии с целями моделирования. Для этого исследователь делает как бы мысленный срез системы в "плоскости" той метасистемы М, в качестве элемента которой представляет интерес система So, т.е. выполняет M-ориентацию. Затем исследователь выявляет основные признаки ориентированной модели и может добавить некоторые признаки и условия, которые облегчат исследование модели или позволят представить ее в виде некоторого среза моделирующей системы Sm. Концептуальная модель - это субстрат системы с позиций достижения целей моделирования.

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

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

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

Рис.2. Уровни модели

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

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

Уровни детализации иногда называются стратами, а процесс выделения уровней - стратификацией. Выбор страт зависит от целей моделирования и степени предварительного знания свойств элементов. Для одной и той же системы могут быть использованы различные страты. Обычно в модель включаются элементы одного уровня детализации - K-страта. Однако может представлять интерес построение модели из элементов разных страт. В том случае, когда общесистемные (функциональные) свойства отдельных элементов мало известны или вызывает затруднение их описание, можно для каждого такого элемента включить в модель его детализированное описание из нижестоящего (К - 1) - страта. Некоторые элементы и этого уровня можно расчленить, т.е. использовать их описание из следующего уровня - (К - 2) - страта.

При построении ориентированной и стратифицированной концептуальной модели необходимо руководствоваться следующим. В модель должны войти все те параметры системы Sok и, в первую очередь, параметры {soj}, допускающие варьирование в процессе моделирования, которые обеспечивают определение интересующих исследователя характеристик Yok при конкретных внешних воздействиях {xon} на заданном временном интервале Т функционирования системы. Остальные параметры должны быть, по возможности, исключены из модели.

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

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

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

Локализация. Последующий шаг создания концептуальной модели - ее локализация, которая осуществляется путем представления внешней среды в виде генераторов внешних воздействий, включаемых в состав модели в качестве элементов. При необходимости они дифференцируются на генераторы рабочей нагрузки, поставляющие на вход системы основные исходные объекты - вещество (сырье, полуфабрикаты, комплектующие), энергию для энергетических систем или данные для информационных систем, в том числе для ВС; генераторы дополнительных обеспечивающих объектов и энергии; генераторы управляющих и возмущающих воздействий. Генераторы возмущающих воздействий нарушают процесс функционирования системы (рис.3).

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

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

Структуризация.

Управление.

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

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

Задание: Построить концептуальную модель следующих объектов:

. Школа

. Швейная фабрика

. Университет

. Детский сад

. Лицей

. Колледж

. Больница

. Банк

. Поликлиника

Лабораторная работа №5

Тема: Задача Джонсона для двух станков.

Цель работы: Изучения составления расписания работы технологической линии.

Задание:

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

Составить блок - схему алгоритма Джонсона.

Составить программу на алгоритмическом языке паскаль.

Теоретическая часть

Имеется два станка и n деталей, каждая из которых должна пройти обработку с начала на первой, а затем на второй машине. Время операции j - й детали на первом станке обозначим через aj, на втором - через bj. Требуется дать расписания которое минимизирует общее время обработки всех деталей.

Алгоритм Джонсона для получения оптимального расписания. Идея его состоит в стремление максимально сократит простой второй машины полном исключении прерываний и искусственных простоев первой. Запиваем числа aj и bj в табл.1

12…j…nАa1a2…aj…anBb1b2…bj…

Просматриваем продолжительности работ aj и bj, j=1,n и находим среди них наименьшую.

Если она относится к первому станку, то соответствующая деталь для обработки располагается первой.

Если она относится ко второму стану, то соответствующая деталь для обработки располагается последней.

Вычеркиваем столбец соответствующий этой детали.

Процесс повторяется в отношении оставшихся деталей.

Если попадаются равные числа, то для определенности деталь с меньшим индексом располагается первой. В случае же равенства aj и bj парядок деталей устанавливается по первой машине.

Пример. Найти оптимальное расписание для двух машин. (Табл.2)

12345678910А20131781125101176B176211441819211615Оптимальный план 89631074521

Рис 2

Наименьший элемент матрицы (4). Он находится во второй строке, поэтому процесс надо закончить обработкой детали (5).

Подставим над столбцом 5 "птичку" или вычеркнем его.

В оставшейся матрице ищем минимальные элемент (6). Согласно пункту (6) алгоритма, деталь с меньшим индексом следует располагать первой.

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

Точно так же устанавливается порядок обработки остальных. На рис.2 представлен линейный график оптимального расписания (график Ганта).

Таким образом, время простоя (на графике заштрихованная часть) второй равно a10=6 (единиц). Общее время прохождения всех работ:

a10+ (b1+b2+…+b10) =6+151=157 (единиц)

Содержания отчёта

Исходные данные

Алгоритм расчёта. (блок - схема)

Листинг программы и результата вычислений

Контрольные вопросы.

Для каких случаев решена задача Джонсона

Описание задача Джонсона

1.

j i 12345678910A2546108121530В18652441849

.

j i 12345678910A131256842111612В101448756213

.

j i 12345678910A6869721232В5464652314125

.

j i 12345678910A45782614152225В584175162389

.

j i 12345678910A1452623549817В

.

j i 12345678910A1521816576849В4956781816148

.

j i 12345678910A46116718121453В86759154181011

.

j i 12345678910A12145682418179В458101315370

.

j i 12345678910A05681916495В15486275987

.

j i 12345678910A48151311122025610В201049718121171

Лабораторная работа №6

Тема: Метод наименьших квадратов

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

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

Содержание работы:

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

Таблица 1. Исходные данные

i12345678910Y (i) 51020506080100130170250

Составим матрицу плана

х11x21хn1

Х п =

Найдем определитель

Хi = y + Eii = kx i+ b + Ei

(S Ei2/n) 1/2 ®min(k,b) = å (yi - yi mod) 2= å (yi - kxi - b) 2

(xT * x) = åxi2 åxi

åxi å1= Dk/D = Db/D

Подставим в формулы табличные значения.

Табл. результатов

kbse24,51515 -47,333325,44751

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

Матрица плана

i= axi2+bxi+c+Ei

(S Ei2/n) 1/2 ®min(a,b,c) = S (yi - axi2 - bxi-c) 2

DF/DA=0 Df/DA= S (yi - axi2 - bxi-c) * (-xi2) =0/DB=0 DF/DB=S (yi - axi2 - bxi-c) * (-xi) =0/DC=0DF/DC=S (yi - axi2 - bxi-c) * (-1) =0

Syixi2+aSxi4+bSxi3+cSxi2=0

Syixi+aSxi3+bSxi2+cSxi=0

Syi+aSxi2+bSxi+cS1=0

=Da/D, b=Db/D, c=Dc/D

Подставим табличные значения.

Таблица 4 Результаты

abcse0,393262 3,2909030,005990,32221

Вывод: Сравнивая две модели, линейный и квадратичный графики, видно, что линейная модель лучше, у нее меньше остаточная сумма квадратов.

ВЗАИМОСВЯЗЬ МЕЖДУ СЛУЧАЙНЫМИ ВЕЛИЧИНАМИ

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

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

В математическом анализе зависимость между двумя величинами выражается понятием функции y=f (x), где каждому допустимому значению одной переменной соответствует одно и только одно значение другой переменной. Такая зависимость носит название функциональной; она обнаруживается с помощью строгих логических доказательств и не нуждается в опытной проверке. Если y=const при изменении х, то говорят что у не зависит от х. Так например, угол правильного многоугольника зависит от числа сторон, но не зависит от их длины.

Гораздо сложнее обстоит дело с понятием зависимости случайных величин: Если при изменении х изменилось у, мы не можем сразу сказать, является ли это изменение результатом зависимости от х или оно обязано лишь влиянию случайных факторов. Правда и между случайными величинами может существовать строгая функциональная зависимость, устанавливаемая логическим путем. Например, число мужчин x и число женщин h на 100 человек населения являются случайными величинами, однако всегда x+h=1000. Подобного рода зависимость между случайными величинами обычно известна из теоретических соображений заранее, до всяких наблюдений. На практике она проявляется в том случае, когда для вычисления двух случайных величин используются одни и те же наблюдения. Если же для вычисления каждой из случайных величин используются свои наблюдения, то на эти случайные величины действуют разные случайные факторы, и функциональная зависимость между ними уже невозможна. Попробуйте, например, отдельно измерять сторону а и площадь S квадрата и вы сами убедитесь, что не всегда S = a2.

Как правило, между случайными величинами может существовать лишь связь особого рода, при которой с изменением одной величины меняется распределение другой - такая связь называется стохастической. Изменение случайной величины h, соответствующее изменению величины x, разбивается при этом на две компоненты: стохастическую (связанную с зависимостью h от x) и случайную (связанную с влиянием "собственных" случайных факторов величин. Если первая компонента отсутствует, то величины h и x независимы. Если же стохастическая компонента не равна нулю, то между h и x есть стохастическая связь. При этом соотношение между стохастической и случайной компонентами определяет силу связи. Наконец, отсутствие второй компоненты дает функциональную зависимость.

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

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

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

=

Но а

Поэтому

Следовательно, зависимость между x и h вытекает из неравенства:

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

которая называется коэффициентом корреляции.

Отметим некоторые наиболее важные свойства коэффициента корреляции.

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

Коэффициент корреляции может изменяться от - 1 до +1

Коэффициент корреляции не меняется от прибавления к h и x, каких - либо постоянных (неслучайных) слагаемых.

Коэффициент корреляции не меняется от умножения h и x, на положительные числа.

Если же одну из величин, не меняя другой умножить на - 1, то на - 1 умножится и коэффициент корреляции.

Если коэффициент корреляции > 0, то величины h и x, одновременно возрастают или убывают, если же < 0, то с возрастанием одной величины другая убывает.

Но коэффициент корреляции, как показатель зависимости обладает существенным недостатком. Это связано с тем, что крайние значения r=±1 не очень полезны, так как соответствуют не всякой функциональной зависимости, а только строго линейной связи между h и x,.

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

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

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

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

В практике в основном приходится применять выборочный коэффициент r корреляции, который вычисляется по тем же формулам что и генеральный коэффициент r. Только здесь берутся выборочные математические ожидания (средние) и дисперсии. Так для m пар выборочных значений (х1, у1), (х2, у2). (хm, ym) эти величины удобно вычислять по формулам:

выборочное математическое ожидание:

; ;

выборочный корреляционный момент

;

выборочный коэффициент корреляции

, где

При вычислениях удобно пользоваться формулами

;

.

Рассмотрим пример. При исследованиях зависимости растворимости тиосульфата натрия (в%) от температуры (в градусах) полученные данные приведенные в таблице в колонках обозначенных у и х соответственно. Уравнение регрессии будем искать в виде у=a + b х. Все вычисления произведем в табличной форме.

По выведенным ранее формулам найдем a, b и r

Видно, что коэффициент корреляции близок к единице. Следовательно зависимость между х и у практически линейна, и окончательным уравнением регрессии можно признать равенство у=32,6+0,44х

Контрольные вопросы

Что такое коэффициент корреляции?

Основные свойства коэффициента корреляции. Его преимущества и недостатки.

Лабораторная работа №7

Тема: Расчет временных характеристик ВС методами теории систем массового обслуживания

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

Задание. ВС реализует 3 прикладных программы со средними трудоемкостями ?1=104 оп, ?2=2.1*104 оп, ?3=3.1*104 оп. с интенсивностями инициирования соответственно ?1=15 с-1, ?2=10 с-1, ?3=5 с-1. Коэффициент загрузки системы ?=1-0.3=0.7. Дисциплина обслуживания с абсолютным приоритетом. Тип модели M/M/1. Порядок присвоения приоритета прямой, т. е самой короткой по времени выполнения программе присваивается наивысший приоритет.

Решение:

) Найдем быстродействие процессора.

) Назначение приоритетов:

Первый поток Р=3

Второй поток Р=2

Третий поток Р=1

) Найдем среднее время обслуживания задачи.

4) Проверка условий стационарности

) Найдем среднее время ожидания в очереди.

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

Первый поток:

Второй поток:

Третий поток:

Следовательно:

математическая модель стратификация локализация

) Найдем среднее время пребывания в системе.

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

Первый поток:

Второй поток:

Третий поток:

Следовательно:

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

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

Ответ:

Среднее время ожидания в очереди:

Среднее время пребывания в системе:

Лабораторная работа №8

Тема: Сетевые модели.

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

Теоретическая часть

Вариант

ЗАДАЧА

Построить сетевую модель ремонта Вашей квартиры

а) определить критический путь

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

в) рассчитать ранние сроки окончания и начала событий

г) рассчитать резервы событий

Решение:

Делаем ремонт двухкомнатной квартиры улучшенной планировки: жилая комната, детская, кухня, ванна, туалет и коридор.

. Необходимо сделать:

сменить обои во всех помещениях;

покрасить окна;

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

в остальных помещениях потолок покрывается краской КЧ

покрасить входную дверь;

постелить по всей квартире линолиум

. Строим таблицу ремонта и сетевой график

. "Четырехсекторным" методом рассчитываем параметры сетевого графика и определяем "критический путь".

. Рассчитываем параметры сетевого графика и резервы времени

Литература

1.Налимов В.В. Теория эксперимента. М., Наука, 1971. - 207 с.

2.Налимов В.В., Голикова Т.И. Логические основания планирования эксперимента М.: Металлургия, 1981. - 151 с.

.Федоров В.В. Теория оптимального эксперимента. М., Наука, 1971.

.Лотов А.В. Введение в экономико-математическое моделирование. - М.: Наука, 1984. - 392 с.

.Вознесенский В.А. Статистические методы планирования эксперимента в технико-экономических исследованиях. - М.: Финансы и статистика, 1981. - 263 с.

.Тихонов А.И., Уфимцев М.В. Статистическая обработка результатов экспериментов. - М.: Моск. Ун-т, 1988. - 174 с.