Модели задач математического программирования.

· Литература

1. Острейковский В.А. Теория систем. – М.: Высшая школа, 1997. – 240 с.

2. Спицнадель В.Н. Основы системного анализа. – СПб.: Бизнесс-пресс, 2000. – 326 с.

3. Шарапов О.Д. и др. Системный анализ. – К.: Вища школа, 1993. – 303 с.

4. Системный анализ в экономике и организации производства/ Под ред. С.А. Валуева и др. – Л.: Политехника, 1991. – 398 с.

5. Дабагян А.В. Проектирование технических систем. – М.: Машиностроение, 1986. – 256 с.

6. Ершова Н.М. Теория систем и системный анализ: Конспект лекций. – Днепропетровск: ПГАСА, 2005. – 112 с.

7. Ершова Н.М. Теория систем и системный анализ: Краткий конспект лекций. – Днепропетровск: ПГАСА, 2006. – 70 с.

8. Ершова Н.М. Методы и способы компьютерных информационных технологий: Конспект лекций. – Днепропетровск: ПГАСА, 2005. – 169 с.

9. Ершова Н.М. Основы системного анализа. Методические указания и задания. – Днепропетровск: ПГАСА, 2007. – 62 с.

10. Ершова Н.М. Компьютерные технологии реализации математических методов управления производством: Конспект лекций. – Днепропетровск: ПГАСА, 2001. – 93 с.

11. Ершова Н.М. Реализация в среде электронных таблиц математических методов и моделей управления производством. Методические указания и задания.–Днепропетровск: ПГАСА, 2001.–42с.

12. Ершова Н.М., Цыбрий Л.В. Математические методы и модели управления производством. Модуль 4 дистанционного курса по дисциплине «Математическое моделирование экономических задач». – Днепропетровск: ПГАСА, 2004. –44 с.

13. Математика для экономистов: В 6 т./ Под ред. А.Ф. Тарасюка. – М.: ИНФРА-М, 2000. – (серия «Высшее образование»). Т.6: Чернов В.П., Ивановский В.Б. Теория массового обслуживания. – 158 с.

14. Нужина Т.С. Элементы теории массового обслуживания. Учебное пособие. – Казань: КАИ, 1971. – 117 с.

15. Кузнецов А.В., Сакович В.А., Холод Н.И. Высшая математика. Математическое программирование. - Минск: Вышэйшая школа, 1994. – 286 с.

Введение в тему

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

4.1. Задачи систем массового обслуживания

Важная задача моделирования систем – обеспечение синхронной и сбалансированной работы всех ее элементов. Для моделирования реальных систем обслуживания используется теория массового обслуживания (ТМО).

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

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

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

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

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

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

4.2. Основные понятия теории массового обслуживания

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

СМО можно представить в виде физической системы дискретного типа или с конечным множеством состояний Переход системы из одного состояния в другое осуществляется скачком в тот момент времени, когда происходит одно из событий:

· приход заявки;

· освобождение канала;

· уход заявки из очереди;

· и др.

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

Рассмотрим канальную СМО, в которой поступившая заявка при занятости каналов, покидает систему не обслуженной. Это система с возможными состояниями:

· - все каналы свободны;

· - один канал занят;

·

· - каналов заняты;

·

· - все каналы заняты.

Изобразим схему возможных переходов из состояния в состояние (рис.4.1).

Рис.4.1. Схема возможных переходов

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

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

4.3. Простейший поток и его свойства

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

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

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

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

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

Случайная величина , равная числу поступивших заявок за время , имеет закон распределения Пуассона.

где - плотность потока. Плотность полностью определяет простейший поток, т.е. среднее число заявок, поступивших за время , равно .

Простейший поток заявок одновременно обладает свойствами стационарности, ординарности и отсутствия последействия. Рассмотрим на оси простейший поток заявок как последовательность случайных точек (рис.4.2).

Рис.4.2. Схема простейшего потока заявок

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

В соответствии с законом Пуассона:

· вероятность того, что за время поступит ровно заявок, равна

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

· вероятность того, что на участок попадет хотя бы одна заявка, равна

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

Четвертое свойствопростейшего потока – вероятность поступления в течение промежутка времени длительности ровно заявок принимает наибольшее значение в момент времени При максимумы будут в моменты времени 0, 1, 2, … (рис.4.3).

Рис.4.3. Иллюстрация 4-го свойства простейшего потока

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

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

Основные формулы простейшего потока:

· Параметр потока равен плотности

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

· Вероятность того, что на интервал времени не поступит ни одной заявки

· Вероятность того, что на интервал времени поступит по крайней мере одна заявка

· Среднее число заявок, поступивших на интервал времени

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

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

· не поступит ни одного вызова;

· поступит хотя бы один вызов;

· поступит ровно два вызова;

· поступит ровно три вызова;

· поступит ровно четыре вызова;

· поступит один или два вызова;

· поступит более двух вызовов.

Кроме того, проверить четвертое свойство простейшего потока вызовов.

Решениевыполняем в следующей последовательности:

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

2. Определяем среднее число заявок

3. Последовательно рассчитываем в среде электронных таблиц (ЭТ) требуемые вероятности по формулам:

· вероятность того, что за 15 часов будут поступать один или два вызова, равна сумме

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

Расчет при =15 является контрольным.

4. Определяем время достижения вероятностью своего максимального значения в соответствии с 4-м свойством простейшего потока заявок -