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

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

Рубрика Экономико-математическое моделирование
Вид лабораторная работа
Язык русский
Дата добавления 17.02.2012
Размер файла 869,0 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru/

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

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

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

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

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

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

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

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

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

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

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

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

Студент

Норма выпитого

Запасы

(в литрах)

"Русич"

"Премьер"

Иванов

2

2

1.5

Петров

3,5

1

1,5

Сидоров

10

4

4,5

Васильев

-

1

0,7

Крепость напитка

16 %

10 %

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

2.1 Управляемые параметры

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

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

- решение.

2.2 Ограничения

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

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

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

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

(л).

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

(л).

(л).

(л).

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

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

4. Решение.

при:

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

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

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

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

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

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

=>

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

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

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

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

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

16

10

0

0

0

0

Св

Б.П.

X1

X2

X3

X4

X5

X6

в

0

X3

2

2

1

0

0

0

1,5

0

X4

3,5

1

0

1

0

0

1,5

0

X5

10

4

0

0

1

0

4,5

0

X6

0

1

0

0

0

1

0,7

F

-16

-10

0

0

0

0

0

;

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

16

10

0

0

0

0

Св

Б.П.

X1

X2

X3

X4

X5

X6

В

0

X3

0

1,428

1

-0,572

0

0

0,642

16

X1

1

0,286

0

0,286

0

0

0,428

0

X5

0

1,14

0

-2,86

1

0

0,214

0

X6

0

1

0

0

0

1

0,7

F

0

-5,424

0

4,576

0

0

6,857

;

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

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

;

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

=>

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

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

16

10

0

0

0

0

Св

Б.П.

X1

X2

X3

X4

X5

X6

В

0

X3

0

0

1

3

-1,25

0

0,375

16

X1

1

0

0

1

-0,25

0

0,375

10

X2

0

1

0

-2,5

0,875

0

0,1875

0

X6

0

0

0

2,5

-0,875

1

0,5125

F

0

0

0

-9

4,75

0

7,875

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

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

;

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

=>

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

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

. Тогда:

;

16

10

0

0

0

0

Св

Б.П.

X1

X2

X3

X4

X5

X6

в

0

X4

0

0

0,333

1

-0,416

0

0,125

16

X1

1

0

-0,333

0

0,166

0

0,25

10

X2

0

1

1,833

0

-0,166

0

0,5

0

X6

0

0

-0,833

0

0,166

1

0,2

F

0

0

3

0

1

0

9

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

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

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

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

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

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

4. При подкормке посевов необходимо внести на 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

Морской

Солнечный

Слава

Уютный

1

2

3

4

Железнодо-рожный вокзал

1

10

0

20

11

Аэропорт

2

12

7

9

20

Морской вокзал

3

0

14

16

18

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

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

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

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

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

Число туристов в исходном пункте

1

2

3

4

10

0

20

11

1

X11

X12

X13

X14

15

12

7

9

20

2

X21

X22

X23

X24

25

0

14

16

18

3

X31

X32

X33

X34

5

Число мест в отеле

5

15

15

10

????????????????????

?????????????????????????

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

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

Таблица 3

Исход-ный пункт, i

Пункт назначения (отели),j

Число турис-тов в исход. пункте

1

2

3

4

5

10

0

20

11

0

1

X11

X12

X13

X14

X15

15

12

7

9

20

0

2

X21

X22

X23

X24

X25

25

0

14

16

18

0

3

X31

X32

X33

X34

X35

10

Число мест в отеле

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) Ввод данных. Вводим данные таблицы 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

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

целевая функция: 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

аi

30

30

30

20

1

4

5

30

5

1

4

40

4

5

1

8.

b

iаi

120

80

50

130

1

7

6

70

6

1

1

50

7

6

1

9.

bi

аi

150

150

100

200

1

3

4

150

4

3

1

50

3

1

4

10.

bi

аi

70

70

70

110

1

3

0

70

3

1

3

30

3

3

1

11.

bi

аi

70

50

50

50

8

6

1

60

1

8

6

60

6

8

1

12.

bi

аi

120

90

70

100

2

5

3

90

3

2

5

90

5

3

2

13.

bi

аi

80

80

80

160

2

7

9

40

3

3

6

40

4

2

7

14.

bi

аi

130

60

40

20

1

3

2

150

2

1

3

60

3

1

2

15.

bi

аi

20

30

30

10

30

2

3

2

4

40

3

2

5

1

20

4

3

2

6

16.

bi

аi

30

25

35

20

50

3

2

4

1

40

2

3

1

5

20

3

2

4

4

17.

bi

аi

70

90

110

150

120

2

5

4

6

130

3

11

3

2

150

3

10

3

2

18.

bi

аi

250

300

350

300

350

2

3

4

3

300

2

3

1

2

550

3

1

3

4

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

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

Управление.

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

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

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

1. Школа

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

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

4. Детский сад

5. Лицей

6. Колледж

7. Больница

8. Банк

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

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

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

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

Задание:

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

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

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

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

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

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

1

2

j

n

А

a1

a2

aj

an

B

b1

b2

bj

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

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

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

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

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

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

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

1

2

3

4

5

6

7

8

9

10

А

20

13

17

8

11

25

10

11

7

6

B

17

6

21

14

4

18

19

21

16

15

Оптимальный

план

8

9

6

3

10

7

4

5

2

1

Рис 2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.

j

i

1

2

3

4

5

6

7

8

9

10

A

2

5

4

6

10

8

12

15

3

0

В

1

8

6

5

2

4

4

18

4

9

2.

j

i

1

2

3

4

5

6

7

8

9

10

A

13

12

5

6

8

4

21

1

16

12

В

10

14

4

8

7

5

6

2

1

3

3.

j

i

1

2

3

4

5

6

7

8

9

10

A

6

8

6

9

7

2

1

2

3

2

В

5

4

6

4

6

52

3

14

12

5

4.

j

i

1

2

3

4

5

6

7

8

9

10

A

4

5

7

8

2

6

14

15

22

25

В

5

8

4

17

5

16

2

3

8

9

5.

j

i

1

2

3

4

5

6

7

8

9

10

A

14

5

2

6

23

5

4

9

8

17

В

6.

j i

1

2

3

4

5

6

7

8

9

10

A

15

2

18

16

5

7

6

8

4

9

В

4

9

5

6

7

8

18

16

14

8

7.

j

i

1

2

3

4

5

6

7

8

9

10

A

4

6

1

16

7

18

12

14

5

3

В

8

6

7

5

9

15

4

18

10

11

8.

j

i

1

2

3

4

5

6

7

8

9

10

A

12

14

5

6

8

2

4

18

17

9

В

4

5

8

10

13

1

5

3

7

0

9.

j

i

1

2

3

4

5

6

7

8

9

10

A

0

5

6

8

1

9

16

4

9

5

В

15

4

8

6

2

7

5

9

8

7

10.

j

i

1

2

3

4

5

6

7

8

9

10

A

4

8

15

13

11

12

20

25

6

10

В

20

10

4

9

7

18

12

11

7

1

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

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

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

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

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

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

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

i

1

2

3

4

5

6

7

8

9

10

Y (i)

5

10

20

50

60

80

100

130

170

250

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

х1

1

x2

1

хn

1

Х п =

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

Хi = y + Ei

Xi = kx i+ b + Ei

( Ei2/n) 1/2 min

F (k,b) = (yi - yi mod) 2= (yi - kxi - b) 2

(xT * x) = xi2 xi

xi 1

k = k/

b = b/

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

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

k

b

se

24,51515

-47,3333

25,44751

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

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

Xi= axi2+bxi+c+Ei

( Ei2/n) 1/2 min

F (a,b,c) = (yi - axi2 - bxi-c) 2

DF/DA=0 Df/DA= (yi - axi2 - bxi-c) * (-xi2) =0

DF/DB=0 DF/DB= (yi - axi2 - bxi-c) * (-xi) =0

DF/DC=0DF/DC= (yi - axi2 - bxi-c) * (-1) =0

-yixi2+axi4+bxi3+cxi2=0

yixi+axi3+bxi2+cxi=0

yi+axi2+bxi+c1=0

a=a/, b=b/, c=c/

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

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

a

b

c

se

0,393262

3,290903

0,0059

90,32221

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

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

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

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

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

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

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

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

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

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

=

Но а

Поэтому

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

; ;

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

;

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

, где

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

;

.

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

По выведенным ранее формулам найдем , и 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. Порядок присвоения приоритета прямой, т. е самой короткой по времени выполнения программе присваивается наивысший приоритет.

Решение:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ответ:

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

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

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

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

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

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

Вариант

ЗАДАЧА

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

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

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

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

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

Решение:

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

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

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

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

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

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

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

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

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

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

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

Литература

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

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

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

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

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

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

Размещено на Allbest.ru


Подобные документы

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

    курсовая работа [268,0 K], добавлен 17.02.2010

  • Основные методы решения задач линейного программирования. Графический метод, симплекс-метод. Двойственная задача, метод потенциалов. Моделирование и особенности решения транспортной задачи методом потенциалов с использованием возможностей Мicrosoft Excel.

    контрольная работа [1,1 M], добавлен 14.03.2014

  • Формулировка проблемы в практической области. Построение моделей и особенности экономико-математической модели транспортной задачи. Задачи линейного программирования. Анализ постановки задач и обоснования метода решения. Реализация алгоритма программы.

    курсовая работа [56,9 K], добавлен 04.05.2011

  • Геометрический способ решения стандартных задач линейного программирования с двумя переменными. Универсальный метод решения канонической задачи. Основная идея симплекс-метода, реализация на примере. Табличная реализация простого симплекс-метода.

    реферат [583,3 K], добавлен 15.06.2010

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

    курсовая работа [54,1 K], добавлен 05.03.2010

  • Применение линейного программирования для решения транспортной задачи. Свойство системы ограничений, опорное решение задачи. Методы построения начального опорного решения. Распределительный метод, алгоритм решения транспортной задачи методом потенциалов.

    реферат [4,1 M], добавлен 09.03.2011

  • Математическая формализация оптимизационной проблемы. Геометрическая интерпретация стандартной задачи линейного программирования, планирование товарооборота. Сущность и алгоритм симплекс-метода. Постановка транспортной задачи, последовательность решения.

    учебное пособие [126,0 K], добавлен 07.10.2014

  • Математическая формулировка задачи линейного программирования. Применение симплекс-метода решения задач. Геометрическая интерпретация задачи линейного программирования. Применение методов линейного программирования к экстремальным задачам экономики.

    курсовая работа [106,0 K], добавлен 05.10.2014

  • Понятие классической транспортной задачи, классификация задач по критерию стоимости и времени. Методы решения задач: симплекс, северо-западного угла (диагональный), наименьшего элемента, потенциалов решения, теория графов. Определение и применение графов.

    курсовая работа [912,1 K], добавлен 22.06.2015

  • Решение задачи линейного программирования графическим и симплекс-методом. Решение задачи двойственной к исходной. Определение оптимального плана закрепления потребителей за поставщиками однородного груза при условии минимизации общего пробега автомобилей.

    контрольная работа [398,2 K], добавлен 15.08.2012

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.