Экономико-математические методы и модели

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Системы массового обслуживания с ожиданием делятся на системы  с ограниченным ожиданием и системы  с неограниченным ожиданием.

В системах с ограниченным ожиданием может ограничиваться: длина очереди, время пребывания в очереди.

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

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

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

5. Динамическое программирование

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

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

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

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

Задачи динамического  программирования имеют ряд особенностей.

1. В них рассматривается процесс поведения системы во времени.
2. Состояние системы в каждый момент времени однозначно определяется численными значениями небольшого набора параметров.
3. Операция выбора решения состоит в преобразовании этого набора параметров в такой же набор с другими числовыми значениями.
4. Если система в рассматриваемый момент времени находится в некотором состоянии, то ее поведение в дальнейшем определяется этим состоянием и выбираемым управлением, но не зависит от предыстории (т.е. от того, в каких состояниях находилась система до этого момента).

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

В некоторых задачах, решаемых методом динамического программирования, процесс управления разбивается  на шаги. При распределении на несколько  лет ресурсов деятельности предприятия  шагом целесообразно считать  временной период; при распределении  средств между предприятиями  – номер очередного предприятия. В других задачах разбиение на шаги вводится искусственно. Например, непрерывный управляемый процесс  можно рассматривать как дискретный, условно разбив его на временные  отрезки (шаги). Исходя из условий каждой конкретной задачи, длину шага выбирают таким образом, чтобы на каждом шаге получить простую задачу оптимизации  и обеспечить требуемую точность вычислений [4, стр. 486 – 487].

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

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

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

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

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

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

Итак, методология динамического  программирования состоит в расчленении  задачи на этапы и поэтапном построении оптимального управления на каждом шаге [1, стр. 366 – 368].

6. Сетевое планирование и управление