90934

ПРИМЕНЕНИЕ МЕТОДОВ МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ ДЛЯ РЕШЕНИЯ ЗАДАЧИ ОРГАНИЗАЦИИ ОЧЕРЕДИ

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

Экономическая теория и математическое моделирование

Цель работы – освоение основных понятий математического моделирования на примере задачи организации очереди и экспериментальная проверка (на основе вычислительного эксперимента) теоретических положений.

Русский

2015-07-10

81 KB

25 чел.

ЛАБОРАТОРНАЯ РАБОТА № 1

ПРИМЕНЕНИЕ МЕТОДОВ МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ ДЛЯ РЕШЕНИЯ ЗАДАЧИ ОРГАНИЗАЦИИ ОЧЕРЕДИ.

  1.  Цель и задачи работы.

Цель работы – освоение основных понятий математического моделирования на примере задачи организации очереди и экспериментальная проверка (на основе вычислительного эксперимента) теоретических положений.

Задачи работы:

построение и исследование математической модели последовательности действий;

применение комбинаторных методов для решения задачи организации очереди.  

  1.  Краткие теоретические сведения.

Задача организации очереди имеет следующую формулировку:

Имеется n посетителей, ожидающих приема (деталей, подлежащих обработке). Время беседы с каждым из них (время обработки) заранее известно и равно t1, t2,…, tn.

Требуется найти такой порядок приема посетителей (обработки деталей), чтобы суммарное время ожидания было минимальным.     

Управление U=(u1,u2,…,un) (возможные варианты порядка приема) соответствует множеству перестановок из n элементов. Рассмотрим  множество S, состоящее из n элементов.

 

Перестановка - это упорядоченная совокупность всех элементов S. Определим количество  перестановок Pn.  Например, для S={1,2,3} все перестановки можно сформировать так:

Выбор 1-го элемента

Выбор 2-го элемента

Выбор 3-го
элемента

Перестановка

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

Эти рассуждения очевидным образом обобщаются на множество, состоящее из n элементов: 1-й элемент выбирается n способами, 2-й элемент выбирается n-1 способами,….

Таким образом, количество перестановок на множестве, состоящем из n  элементов

Pn=n(n-1)(n-2)1=n!,

где произведение n(n-1)(n-2)1 обозначается как n!=n(n-1)(n-2)1

По определению полагают  0!=1

можно доказать методом математической индукции.

  1.  Для n=1 очевидно P1=1=1!
  2.  Пусть количество всех перестановок множества, состоящего из n=k элементовPk=k!. Рассмотрим теперь множество из k+1-го элемента. Из k элементов этого множества по индуктивному предположению можно сформировать k! перестановок. Из каждой такой перестановки добавлением k+1-го элемента можно получить k+1 перестановку, поскольку его номер в новой перестановке может быть от 1 до k+1. Таким образом, всех перестановок множества из k+1-го элемента Pk+1=k!(k+1)=(k+1)!

Формирование перестановок

Пусть список приема определяется перестановкой номеров посетителей (u1,u2,…,un):

Тогда время ожидания первого по списку посетителя 1=0.

Время ожидания второго по списку посетителя 2=tu1.

Время ожидания третьего по списку посетителя 3=tu1+ tu2

……….

Время ожидания n-го по списку посетителя n=tu1+ tu2+…+tun-1

Таким образом, общее время ожидания  

=1+2+3…+n=(n-1)tu1+(n-2)tu2+…+ tun-1

Минимальное время ожидания реализуется в случае, когда величины t1, t2,…, tn упорядочены по возрастанию.   

1.3. Выполнение лабораторной работы

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

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

3. Подготовить отчет.  

 

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

Вариант 1.

t1

t2

t3

t4

2

4

12

7

Дополнительное условие: второй клиент должен быть последним в списке

Вариант 2.

t1

t2

t3

t4

8

4

5

7

Дополнительное условие: второй клиент должен быть в списке сразу после четвертого.

Вариант 3.

t1

t2

t3

t4

4

4

5

1

Дополнительное условие: четвертый клиент должен быть вторым в списке

Вариант 4.

t1

t2

t3

t4

11

15

12

6

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

Вариант 5.

t1

t2

t3

t4

8

3

5

3

Дополнительное условие: второй клиент не должен быть последним в списке

Вариант 6.

t1

t2

t3

t4

5

6

7

3

Дополнительное условие: первый клиент должен быть в списке раньше четвертого.

Вариант 7.

t1

t2

t3

t4

9

7

8

4

Дополнительное условие: третий клиент не должен быть в списке ни последним, ни предпоследним.

Вариант 8.

t1

t2

t3

t4

4

5

7

8

Дополнительное условие: третий клиент должен быть в списке позже четвертого, но не должен быть последним.

Вариант 9.

t1

t2

t3

t4

4

3

7

12

Дополнительное условие: второй клиент должен быть в списке перед третьим и после первого.

Вариант 10.

t1

t2

t3

t4

3

2

4

7

Дополнительное условие: третий клиент должен быть в списке сразу перед  четвертым.

Вариант 11.

t1

t2

t3

t4

7

2

5

1

Дополнительное условие: четвертый клиент не должен быть в списке сразу после второго.

Вариант 12.

t1

t2

t3

t4

2

4

12

7

Дополнительное условие: второй клиент не должен быть в списке должен быть в списке ни первым ни последним.

PAGE  2


1

2

2

3

1 2 3

1 3 2

2

1

3

1

3

2 1 3

2 3 1

3

1

2

1

2

3 1 2

3 2 1

k!

■■■...■

■■■...■

■■■...■

...

добавляется k+1-й элемент

■■■...■

■■...■

■■■...■

...

k+1

■■■...■

■■...■

■■■...■

...

k+1

...

k!(k+1)==(k+1)!


 

А также другие работы, которые могут Вас заинтересовать

34644. Личность. Методы принятия решений 22.49 KB
  ЯОбраз какими мы видим себя Идеальное Я какими нам хотелось бы быть Зеркальное Я какими по нашему мнению нас видят другие Реальное Я каковы мы в действительности Методы принятия решений При принятии решений вне зависимости от применяемых моделей существует правило принятия решений. Соответственно существуют следующие методы принятия решений: Платежная матрица оказывает помощь руководителю в выборе одного из нескольких вариантов решений. Методы прогнозирования в них используется как накопленный опыт так и текущие допущения на...
34645. Понятие алгоритма. Свойства, способы описания 90 KB
  Понятие алгоритма и способы его описания; Типы алгоритмов; Блоксхемы; Базовые структуры применяемые при создании алгоритмов. Иначе говоря блоксхема служит для графического изображения структуры алгоритма. Последовательность действий в соответствии с блоксхемой указывается с помощью стрелок соединяющих отдельные блоки и показывающих какой блок и вслед за каким должен выполняться. В ходе изучения данной дисциплины будут рассматриваться алгоритмы описанные при помощи языка программирования и при помощи специальных схем...
34646. Процедуры и функции 85.5 KB
  Пользовательские функции. В Паскале имеется два вида подпрограмм: процедуры PROCEDURE и функции FUNCTION. В программе процедуры и функции описываются после раздела описания переменных программы но до начала ее основной части то есть до оператора Begin начинающего эту часть.
34647. Рекурентные выражения. Рекурсия 73.5 KB
  При первом вызове функции fib5 определяется через fib4fib3; вычисление fib4 осуществляется через fib3 fib2 fib3 через fib2 fibl fib2 через fib1 fib0. Согласно условию прекращения рекурсии fibl и fib0 равно 1. Соответствующий рекурсивный процесс должен быть осуществлен и для fib4 и т. Решение: Vr n:byte; function fibk:byte :longint; begin if k = 1 then fib : = 1 else fib: =fibk l fibk 2 {рекурсивный вызов} end; BEGIN redlnn; writelnn 'e число Фибоначчи'...
34648. Сортировка. Усовершенствованные алгоритмы сортировки 142.5 KB
  Усовершенствованные алгоритмы сортировки. Имеется два вида алгоритмов сортировки. Изза этих отличий методы сортировки существенно отличаются для этих двух видов сортировки. В общем случае при сортировке данных только часть информации используется в качестве ключа сортировки который используется в сравнениях.
34649. Страница Dialogs 227.84 KB
  Пусть ваше приложение включает окно редактирования Memo1 в которое по команде меню Открыть вы хотите загружать текстовый файл а после какихто изменений сделанных пользователем сохранять по команде Сохранить текст в том же файле а по команде Сохранить как.FileNme; Memo1.FileNme сохраняется в переменной FNme и файл загружается в текст Memo1 методом LodFromFile. Обработка команды Сохранить выполняется оператором Memo1.
34650. Страница System 215.58 KB
  Пиктограмма Имя Назначение Timer Таймер. Timer Компонент DelphiTimer очень простой компонент который не виден на экране но тем не менее TimerDelphi выполняет очень важные функции в программе. DelphiTimer позволяет вводить необходимые задержки между выполнением тех или иных действий.
34651. Символьные переменные и строки. Множества. Записи 92 KB
  Символьные переменные Строки Множества Записи Символьные переменные Значением символьного типа Chr является множество всех символов ПК. PRED X возвращает предыдущее значение порядкового типа значение которое соответствует порядковому номеру ORDX 1 т. ORDPREDX = ORDX 1; SUCC X возвращает следующее значение порядкового типа которое соответствует порядковому номеру ORDX 1 т. 10 Перевод строки; при выводе его на экран все последующие символы будут выводиться начиная с той же позиции но на следующей...
34652. Структура программного модуля. Состав интегрированной программной среды 154 KB
  В ТурбоПаскале применяются следующие условные знаки и служебные слова для описания различных операций: Приоритет операции Условный знак Выражение Название операции Тип переменных в выражении Тип результата выполнения опрации ЛОГИЧЕСКИЕ ОПЕРАЦИИ 1 not not Логическое не Логический целый Логический целый 2 nd nd b Логическое и Логический целый Логический целый 3 or or B Логическое или Логический целый Логический целый 3 xor xor B Логическое исключающее или Логический целый Логический целый МАТЕМАТИЧЕСКИЕ ОПЕРАЦИИ 2 xy Умножение Целый Целый...