90934

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

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

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

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

Русский

2015-07-10

81 KB

28 чел.

ЛАБОРАТОРНАЯ РАБОТА № 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)!


 

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

65662. ОСОБЛИВОСТІ ПОШИРЕННЯ СОСНОВИХ ПИЛЬЩИКІВ ТА НАСЛІДКИ ЇХ ВПЛИВУ НА ДЕРЕВОСТАНИ ЦЕНТРАЛЬНОГО ПОЛІССЯ 267.5 KB
  Мета і завдання дослідження. Метою досліджень є визначення особливостей поширення соснових пильщиків у насадженнях Центрального Полісся та впливу пошкодження крон личинками на стан і приріст дерев сосни в осередках.
65663. ВІЙСЬКОВО-МОРСЬКА ТЕРМІНОЛОГІЯ УКРАЇНСЬКОЇ МОВИ: ЕТАПИ ФОРМУВАННЯ ТА СЕМАНТИКА 180.5 KB
  Україна морська держава тому закономірно що українська мова має розгалужену систему військовоморської лексики яка потребує докладного вивчення. Актуальність дослідження визначається необхідністю простежити формування розвиток а також сучасний стан української військовоморської терміносистеми.
65664. Інформаційна технологія формування стеганографічних систем для цифрових графічних середовищ на основі використання багатопараметричної адаптації 1.29 MB
  Проблема захисту інформації в цифрових комп’ютерних системах являє собою важливий напрямок досліджень в галузі інформатики, що досить інтенсивно розвивається. Це обумовлюється необхідністю захисту користувачів інформації від втрат, до яких може призвести неуповноважене використання даних...
65665. МЕХАНІЗМ ФОРМУВАННЯ ТА ПІДТРИМКИ КОНКУРЕНТНОГО СЕРЕДОВИЩА НА РИНКУ ЖИТЛОВО-КОМУНАЛЬНИХ ПОСЛУГ 230.5 KB
  Однією з основних передумов якісно нових перетворень в житлово-комунальному господарстві України є формування конкурентного середовища на ринку житлово-комунальних послуг ЖКП як дієвого механізму виходу галузі з кризи.
65666. Регулювання зайнятості населення в умовах міжнародної трудової міграції 786.5 KB
  Формування зайнятості з метою забезпечення населення місцями праці в умовах добровільного вибору різноманітних видів діяльності для задоволення власних потреб є одним з найважливіших завдань у кожній державі світу. В значній мірі це пояснюється тим що на зламі ХХ і ХХІ століть в багатьох країнах...
65667. Технологія навчання техніки вправ з обручем на основі спеціальної фізичної підготовки юних гімнасток 4.6 MB
  Обовязковою умовою цього процесу є необхідність удосконалення методики підготовки юних гімнасток. Зокрема у вітчизняній науковометодичній літературі дослідження у сфері предметної підготовки й розвитку спеціальних здібностей гімнасток у вправах з обручем відсутні що...
65668. МИРНЕ ВИРІШЕННЯ МІЖНАРОДНИХ ТЕРИТОРІАЛЬНИХ СПОРІВ: ПРАКТИКА МІЖНАРОДНИХ СУДОВИХ ОРГАНІВ 158 KB
  В основі сучасної системи міжнародних відносин лежить міжнародний правопорядок який базується на основоположних принципах міжнародного права що забезпечують належне підґрунтя для міжнародного співробітництва держав. Попри це в усіх сферах міжнародних відносин постійно виникають міжнародні спори.
65669. Структурні зміни легень при тяжкій черепно-мозковій травмі (клініко-експериментальне дослідження) 592 KB
  Значна кількість публікацій присвячених питанням патології легень при ураженні центральної нервової системи вказує на увагу до проблеми як клініцистів так і патоморфологів В. Проведений нами аналіз наукової літератури показав що динаміка морфологічних змін легень при переживанні травми...
65670. ОРГАНІЗАЦІЙНО-ЕКОНОМІЧНІ ЗАСАДИ ВОДОЗАБЕЗПЕЧЕННЯ МІСЬКОГО НАСЕЛЕННЯ 293 KB
  Тому великого значення в галузі економіки природокористування та охорони навколишнього середовища набуває розробка та реалізація організаційноекономічних засад підвищення ефективності водозабезпечення міського населення.