«С.С. Смородинский, Н.В. Батин ОПТИМИЗАЦИЯ РЕШЕНИЙ НА ОСНОВЕ МЕТОДОВ И МОДЕЛЕЙ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ Учебное пособие по курсу Системный анализ и исследование операций для студентов специальности ...»

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

Как отмечено выше, объемы производства изделий A и B обозначены через переменные X1 и X2.

Составим целевую функцию задачи, выражающую прибыль от производства изделий. Будем считать, что прибыль от продажи одного изделия представляет собой разность его цены и себестоимости. Прибыль от продажи одного изделия A можно выразить следующей формулой: 12 – (7 + 0,2X1) = 5 – 0,2X1. Аналогично выразим прибыль от продажи одного изделия B: 10 – (8 + 0,2X2) = = 2 – 0,2X2. Таким образом, целевая функция задачи (прибыль от продажи всех изделий A и B) имеет следующий вид:

E = (5 – 0,2X1)X1 + (2 – 0,2X2)X2 = 5X1 – 0,2 X 13X1 + 6X 8X1 + 11X X1, X2 – целые E = 5X1 – 0,2 X Здесь ограничения устанавливают предельный расход платины и палладия.

В этой задаче система ограничений линейная, а целевая функция – нелинейная (квадратичная). Таким образом, данная задача представляет собой задачу нелинейного квадратичного программирования.

6.3. Решение задач нелинейного программирования. Градиентные Наиболее универсальными из методов нелинейного программирования являются градиентные методы. Эти методы основаны на использовании градиента целевой функции.

Напомним, что градиент любой функции нескольких переменных F(X1, X2,..., Xn) – это вектор, координаты которого представляют собой частные производные этой функции:

grad F = Из высшей математики известно важное свойство градиента: он указывает направление наискорейшего возрастания функции. Вектор –grad F называется антиградиентом функции F и указывает направление ее наискорейшего убывания.

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

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

2. Выполняется переход от текущего решения к новому решению в направлении градиента (или антиградиента). Величина этого перехода определяется по-разному в зависимости от условий задачи и используемого метода.

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

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

Решим задачу из примера 6.3, используя метод Франка–Вульфа.

grad E = Найдем также начальное допустимое решение. В качестве такого решения можно использовать любой набор значений X1 и X2, удовлетворяющий системе ограничений. Начальное допустимое решение можно найти, например, следующим образом: исключить из целевой функции все нелинейные элементы и решить симплексметодом полученную задачу линейного программирования. Для рассматриваемого примера такая задача будет следующей:

13X1 + 6X 8X1 + 11X E = 5X1 + 2X2 max.

Решив эту задачу, получим начальное допустимое решение: = 6,923, = 0. Найдем значение целевой функции для этого решения: E = 5·6,923 – – 0,2·6,923 + 2·0 – 0,2·0 = 25,03.

Необходимо также задать требуемую точность решения задачи (). Зададим ее равной 500 ден. ед., т.е. будем считать, что решение найдено, если переход к новому решению приводит к увеличению целевой функции не более чем на 500 ден. ед. В данной задаче целевая функция выражается в тысячах ден. ед., поэтому = 0,5.

Решим задачу, используя итерационный алгоритм на основе метода Франка–Вульфа.

Итерация 1. Определяется градиент целевой функции в точке ОДР, соответствующей текущему решению:

grad E (X ) = (5 – 0,4·6,923; 2 – 0,4·0) = (2,2; 2).

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

13X1 + 6X 8X1 + 11X W = 2,2X1 + 2X2 max.

Решение этой задачи следующее: = 4,863, = 4,463. Это означает, что поиск нового решения будет выполняться в направлении от точки X = = (6,923; 0) к точке X = (4,863; 4,463).

3. Составляются уравнения для перехода к новому решению:

где – коэффициент, задающий величину перемещения от текущего решения к новому решению в направлении точки X. Этот коэффициент определяется на следующем шаге.

Для рассматриваемого примера эти уравнения имеют следующий вид:

4. Определяется коэффициент. Этот коэффициент находится таким образом, чтобы переход к новому решению обеспечивал максимальное значение целевой функции. С этой целью уравнения для перехода к новому решению, построенные на шаге 3, подставляются в целевую функцию E. В результате целевая функция представляется как функция от коэффициента :

E = 5(6,923 – 2,06) – 0,2(6,923 – 2,06) + 2·4,463 – 0,2(4,463) = Значение находится из условия экстремума целевой функции, т.е. из условия dE/d = 0:

dE/d = – 9,6 + 4,3 = 0.

Примечания:

1. Если значение, найденное из уравнения dE/d = 0, оказывается больше единицы, то принимается = 1. Это означает, что экстремум целевой функции в направлении, задаваемом градиентом, находится за пределами ОДР. В этом случае новое решение должно находиться на границе ОДР (т.е. в точке X*), но не выходить за нее.

2. Если уравнение dE/d = 0 не имеет решений (например, не зависит от ), то также принимается = 1.

5. Из уравнений, составленных на шаге 3, определяется новое решение:

Определяется значение целевой функции для полученного решения: E = 5·6 – 0,2·6 + 2·2 – 0,2·2 = 26.

6. Проверяется условие окончания поиска решения. Для этого определяется разность значений целевой функции для нового и предыдущего решения:

E = E (1) E (0) = 26 25,03 = 0,97. Эта величина сравнивается с заданной точностью. Если E, то текущее решение принимается в качестве оптимального. В данном случае E = 0,97, = 0,5. Таким образом, условие окончания поиска решения не выполняется. Требуется следующая итерация.

Итерация 1. Определяется градиент целевой функции в точке ОДР, соответствующей текущему решению:

grad E (X )= (5 – 0,4·6; 2 – 0,4·2) = (2,6; 1,2).

2. Определяется угловая точка ОДР, соответствующая предельно допустимому перемещению от текущего решения в направлении градиента. Для этого решается следующая задача линейного программирования:

13X1 + 6X 8X1 + 11X W = 2,6X1 + 1,2X2 max.

3. Составляются уравнения для перехода к новому решению:

4. Определяется коэффициент из условия экстремума целевой функции:

E = 5(6 – 1,137) – 0,2(6 – 1,137) + 2(2 + 2,463) – 0,2(2 + 2,463) = dE/d = –3 = 0.

5. Из уравнений, составленных на шаге 3, определяется новое решение:

Определяется значение целевой функции для полученного решения: E = 5·6 – 0,2·6 + 2·2 – 0,2·2 = 26.

6. Проверяется условие окончания поиска решения. Определяется разность значений целевой функции для нового и предыдущего решения:

E = E ( 2) E (1) = 0. Так как E, оптимальное решение найдено: X1 = 6, X2 = 2. Оптимальное значение целевой функции E = 26.

Таким образом, предприятию следует выпустить 6 изделий типа A и 2 изделия типа B. Такой план производства обеспечит предприятию максимальную прибыль в размере 26 тыс. ден. ед.

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

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

Единственное отличие состоит в том, что целевая функция W в задаче, решаемой на шаге 2, также подлежит минимизации.

6.4. Решение задач нелинейного программирования средствами табличного процессора Excel Решение задач нелинейного программирования в Excel в основном аналогично решению задач линейного программирования (см. подраздел 2.5).

Рассмотрим решение примера 6.3 средствами Excel.

Предположим, что желательно получить результаты (значения переменных X1 и X2) в ячейках B2 и C2. В ячейке B3 введем формулу целевой функции:

= 5·B2 – 0,2·B2^2 + 2·C2 – 0,2·C2^ В ячейке B4 введем формулу первого ограничения (на расход платины):

= 13·B2 + 6·C В ячейке D4 введем правую часть этого ограничения: 90.

Аналогично в ячейке B5 введем формулу ограничения на расход палладия (= 8·B2 + 11·C2), в ячейке D5 – правую часть этого ограничения (88).

Укажем также некоторые поясняющие надписи и обозначения (хотя это и необязательно). Рабочий лист будет иметь примерно такой вид, как показано на рис. 6.1.

Примечание. Значения 0 в ячейках B3 - B5 получены автоматически для начальных значений переменных, равных нулю.

Для решения задачи из меню «Сервис» выберем элемент «Поиск решения». В поле «Установить целевую ячейку» указывается ячейка B3, где находится формула целевой функции. Используя переключатели, необходимо указать, что требуется установить ячейку B3 «равной максимальному значению» (так как целевая функция в этой задаче подлежит максимизации). В поле «Изменяя ячейки» указываются ячейки, в которых должны находиться значения переменных: B2:C2.

В области «Ограничения» указываются ограничения, как показано в подразделе 2.5. Необходимо ввести ограничения на расход платины и палладия, заданные на рабочем листе, а также ограничение на неотрицательность всех переменных (B2:C2>=0) и ограничение на их целочисленность (в поле «Ссылка на ячейку» указать B2:C2, а в поле знака ограничения выбрать отметку «цел»).

Для решения задачи следует нажать кнопку «Выполнить». Рабочий лист с результатами решения показан на рис. 6.2.

В ячейках B2 и C2 получены оптимальные значения переменных, в ячейке B3 – оптимальное значение целевой функции. Эти величины совпадают с результатами, полученными по методу Франка–Вульфа.

В ячейках B4 и B5 находятся значения левых частей ограничений. Видно, что на выпуск изделий будет израсходовано 90 г платины и 70 г палладия.

Примечания:

1. В табличном процессоре Excel для решения задач оптимизации (элемент меню «Поиск решения») используются именно градиентные методы.

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

7. РЕШЕНИЕ ЗАДАЧ ОПТИМИЗАЦИИ НА ОСНОВЕ МЕТОДА

ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

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

К числу задач, для которых может применяться метод динамического программирования, относится большинство задач планирования на несколько периодов времени (например, на несколько лет). Шагом в таких задачах является один плановый период (например, один год). Метод динамического программирования применяется также для многих задач, в которых имеется возможность искусственно представить процесс принятия решения как последовательность из нескольких однотипных Общая постановка задачи, решаемой методом динамического программирования, следующая. Имеется некоторая операция, находящаяся в начальном состоянии S0. Операция реализуется за N шагов. На каждом шаге принимается некоторое решение Uk, где k – номер шага (k = 1,..., N). Выбор каждого решения Uk вызывает переход операции из состояния Sk-1 в новое состояние Sk, а также обеспечивает некоторое значение критерия эффективности Zk. Требуется определить последовательность решений U1, U2,..., Uk, обеспечивающих экстремальное (максимальное или минимальное) значение общего критерия эффективности E, зависящего от значений критерия эффективности на отдельных шагах Z1, Z2,..., Zk.

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

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

Задача, представленная в виде многошаговой операции, может быть решена методом динамического программирования, если она удовлетворяет следующим • отсутствие последействия: состояние операции по окончании каждого шага (Sk) и критерий эффективности на каждом шаге (Zk) зависят только от решения, принятого на данном шаге (Uk), и от состояния операции в начале данного шага (Sk-1), и не зависят от того, каким образом операция перешла в состояние Skаддитивность или мультипликативность критерия эффективности:

общий критерий эффективности представляет собой сумму критериев эффективности на отдельных шагах (E = Z1 + Z2 +... + ZN) или их произведение (E = = Z1·Z2·...·ZN).

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

В цикле условной оптимизации для каждого шага находится множество возможных состояний операции в начале данного шага. Для каждого из этих состояний находится условно оптимальное решение, т.е. решение, оптимальное для данного состояния. Поиск условно оптимальных решений начинается с последнего (N-го) шага, так как на этом шаге имеется возможность выбирать решение только с учетом эффективности на данном шаге (последующих шагов нет). Затем на других шагах (N–1-м, N–2-м,..., первом) условно оптимальные решения выбираются согласно принципу оптимальности, т.е. с учетом эффективности на данном шаге и на последующих шагах. На всех шагах от N-го до второго определяется несколько условно оптимальных решений – по одному для каждого возможного состояния. Для первого шага начальное состояние (S0) обычно известно точно, поэтому для этого шага находится только одно (безусловно оптимальное) решение В цикле безусловной оптимизации для каждого шага определяется безусловно оптимальное решение. Поиск безусловно оптимальных решений начинается с первого шага, так как для него известно начальное состояние S0, поэтому можно определить единственное (безусловно оптимальное) решение U 1. Определяется состояние S1, в которое переходит операция из состояния S0 в результате решения шага. Для него в цикле условной оптимизации уже найдено оптимальное решение U 2. Определяется состояние операции в начале третьего шага – состояние S2, в которое операция переходит в результате решения U 2.

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

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

7.2. Примеры решения задач на основе метода динамического При рассмотрении примеров будем использовать следующие обозначения: Sk – состояние в конце k-го шага (или, другими словами, состояние в начале k+1-го шага); Uk – любое возможное (допустимое) решение на k-м шаге; U k – оптимальное решение на k-м шаге; Zk – критерий эффективности на k-м шаге; Ek – суммарный критерий эффективности на всех шагах, начиная с k-го (т.е. на шагах от k-го до N-го); – оптимальный (в рассматриваемых примерах – максимальный) суммарный критерий эффективности на всех шагах, начиная с kго.

Пример 7.1. Денежные средства в размере 60 млн ден. ед. распределяются между четырьмя предприятиями (П1, П2, П3, П4), принадлежащими одной крупной фирме. Денежные средства выделяются в размерах, кратных 20 млн ден. ед. Каждым предприятием разработаны планы использования денежных средств на развитие производства. Определена прибыль, которую получит каждое предприятие в результате использования выделенных средств (табл. 7.1).

Например, если предприятию П1 не будут выделены средства, то оно не получит никакой прибыли. Если этому предприятию будет выделено 20 млн ден. ед., то его прибыль от использования этих средств составит 9 млн ден. ед. Если будет выделено 40 млн ден. ед., то прибыль составит 16 млн ден. ед., а при выделении 60 млн – Требуется распределить имеющиеся средства (60 млн ден. ед.) между предприятиями таким образом, чтобы общая прибыль фирмы была максимальной.

В данной задаче в качестве шагов будем рассматривать выделение средств предприятиям: первый шаг – выделение средств предприятию П1, второй – П2, и т.д. (всего 4 шага). Таким образом, распределение средств между предприятиями можно рассматривать как многошаговую операцию. В качестве состояния этой операции будем использовать величину имеющихся средств, которые требуется распределить. Начальное состояние S0 = 60. Решение на каждом шаге – это денежные средства, выделяемые предприятию (Uk, k = 1,..., 4). Критерий эффективности для каждого шага – прибыль, полученная предприятием (Zk, k = 1,..., 4). Общий критерий эффективности – это прибыль фирмы, т.е. сумма прибылей всех предприятий: E = Z1 + Z2 + Z3 + Z4.

Задача удовлетворяет свойству отсутствия последействия. Состояние по окончании каждого шага (т.е. имеющаяся сумма средств, подлежащая распределению, Sk) зависит только от суммы, имевшейся в начале шага (Skи от решения, принятого на данном шаге (т.е. от выделенной на данном шаге денежной суммы Uk): Sk = Sk- – Uk. Критерий эффективности на каждом шаге (т.е. прибыль предприятия Zk) зависит только от решения на данном шаге, т.е. от выделенной предприятию суммы Uk, и не зависит от того, сколько средств выделено другим предприятиям.

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

Задача решается в два цикла.

Цикл условной оптимизации Шаг 4 (выделение средств предприятию П4) Определяются все возможные состояния S3 к началу шага 4 (или к концу шага 3), т.е. все возможные значения остатка денежных средств после их выделения предприятиям П1, П2 и П3. Этот остаток может составлять ден. ед. (если все средства выделяются предприятиям П1, П2 и П3), 20 млн ден. ед. (если предприятиям П1, П2, П3 выделяется 40 млн ден. ед.), 40 млн ден. ед. (если предприятиям П1, П2, П3 выделяется 20 млн ден. ед.) или 60 млн ден. ед. (если предприятиям П1, П2, П3 средства вообще не выделяются).

Для каждого из возможных состояний определяется условно оптимальное решение, т.е. решение, оптимальное при условии, что остаток денежных средств равен S3. Так как предприятие П4 – последнее (предполагается, что другим предприятиям средства уже выделены), оптимальное решение состоит в выделении предприятию П всех оставшихся средств.

Возможные состояния в начале четвертого шага S3, соответствующие им условно оптимальные решения U и значения критерия эффективности (прибыль предприятия П4) приведены в табл. 7.2.

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

Шаг 3 (выделение средств предприятиям П3 и П4) Все расчеты для шага 3 приведены в табл. 7.3.

В таблице использованы следующие обозначения: S2 – возможные суммы денежных средств, распределяемые между предприятиями П3 и П4 (т.е. оставшиеся после выделения средств предприятиям П1 и П2); U3 – возможные варианты выделения средств предприятию П3; Z3 – прибыль предприятия П3 от выделения средств в размере U3; S3 – остаток денежных средств после их выделения предприятиям П1, П2 и П3 (т.е. средства, выделяемые предприятию П4);

E * – прибыль предприятия П4 от выделенных ему средств в размере S3; E3 – суммарная прибыль предприятий П3 и П4 (сумма величин из столбцов Z3 и E * ); U 3 – условно оптимальное решение для состояния S2 (денежные средства, которые следует выделить предприятию П3 при наличии суммы S2); E 3 – условно оптимальный критерий эффективности для предприятий П3 и П4, т.е.

прибыль, получаемая этими предприятиями в результате решения U 3.

Определяются все возможные состояния S2 к началу шага 3 (или к концу шага 2), т.е. все возможные значения денежных средств, распределяемых между предприятиями П3 и П4. Этот остаток может составлять 0 ден. ед.

(если все средства выделяются предприятиям П1 и П2), 20 млн ден. ед. (если предприятиям П1 и П2 выделено 40 млн ден. ед.), 40 млн ден. ед. (если предприятиям П1 и П2 выделено 20 млн ден. ед.) или 60 млн ден. ед. (если предприятиям П1 и П2 средства вообще не выделяются).

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

Предположим, что денежные средства, распределяемые между предприятиями П3 и П4, составляют 20 млн ден.

ед. (S2 = 20). Эти средства можно оставить для предприятия П4 (тогда предприятию П3 средства не выделяются, U3 = 0) или выделить их предприятию П3 (U3 = 20). Если U3 = 0, то предприятие П3 не получит прибыли (Z3 = 0). В этом случае остаток средств (состояние) в конце третьего шага составит S3 = 20 млн ден. ед. Эти средства будут выделены предприятию П4, и его прибыль составит = 12 млн ден. ед. Суммарная прибыль предприятий П3 и П4 составит E3 = 0 + 12 = 12 млн ден. ед. Если U3 = 20, то предприятие П3 получит прибыль Z3 = 6 млн ден. ед. Остаток средств (состояние) в конце третьего шага составит S3 = 0. Предприятию П4 не будет выделено никаких средств, и оно не получит прибыли ( E 4 = 0). Суммарная прибыль предприятий П3 и П составит E3 = 6 + 0 = 6 млн ден. ед. Таким образом, если между предприятиями П3 и П4 распределяется сумма в размере 20 млн ден. ед., то эти средства не следует выделять предприятию П3; их следует выделить предприятию П4, так как общая прибыль в этом случае будет максимальной. Другими словами, для состояния S2 = условно оптимальное решение Предположим, что денежные средства, распределяемые между предприятиями П3 и П4, составляют 40 млн ден. ед. (S2 = 40). Предприятию П3 можно выделить 0, 20 или 40 млн ден. ед. (U3 = 0, 20 или 40). Если U3 = 0, то предприятие П3 не получит прибыли (Z3 = 0). В этом случае остаток средств (состояние) в конце третьего шага составит S3 = 40 млн ден. ед. Эти средства будут выделены предприятию П4, и его прибыль составит E * = 17 млн ден. ед. Суммарная прибыль предприятий П3 и П4 составит E3 = 0 + 17 = 17 млн ден. ед.

Аналогично можно определить, что при выделении предприятию П3 суммы в размере 20 млн ден. ед. (т.е. при U3 = 20) суммарная прибыль предприятий П3 и П4 составит E3 = 6 + 12 = 18 млн ден. ед. При U3 = 40 суммарная прибыль предприятий П3 и П4 составит E3 = 12 + 0 = 12 млн ден. ед. Таким образом, для состояния S2 = 40 условно оптимальное решение U 3 = 20, условно оптимальный критерий эффективности E 3 = 18 млн ден. ед. Это означает, что при распределении между предприятиями П3 и П4 средств в размере 40 млн ден. ед. предприятию П3 следует выделить 20 млн ден. ед.

Аналогично можно определить, что при распределении между предприятиями П3 и П4 средств в размере 60 млн ден. ед. предприятию П3 следует выделить все 60 млн ден. ед. (для состояния S2 = 60 условно оптимальное решение U 3 = 60, условно оптимальный критерий эффективности E 3 = 25 млн ден. ед.).

Шаг 2 (выделение средств предприятиям П2, П3 и П4) Все расчеты для шага 2 приведены в табл. 7.4.

Обозначения в таблице: S1 – возможные суммы денежных средств, распределяемые между предприятиями П2, П3 и П4 (т.е. оставшиеся после выделения средств предприятию П1); U2 – возможные варианты выделения средств предприятию П2; Z2 – прибыль предприятия П2 от выделения средств в размере U2; S2 – остаток денежных средств после их выделения предприятиям П1 и П (т.е. средства, выделяемые предприятиям П3 и П4); E3 – максимальная суммарная прибыль предприятий П3 и П4 от выделенных им средств в размере S (определяется из табл. 7.3); E2 – суммарная прибыль предприятий П2, П3 и П (сумма величин из столбцов Z2 и E 3 ); U * – условно оптимальное решение для состояния S1 (денежные средства, которые следует выделить предприятию П при наличии суммы S1); E * – условно оптимальный критерий эффективности для предприятий П2, П3 и П4, т.е. прибыль, получаемая этими предприятиями в результате решения U *. Рассмотрим порядок решения для шага 2.

Определяются все возможные состояния S1 к началу шага 2, т.е. все возможные значения денежных средств, распределяемых между предприятиями П2, П3 и П4. Этот остаток может составлять 0; 20; 40 или 60 млн ден.

ед. (в зависимости от того, сколько средств выделяется предприятию П1).

Для каждого из возможных состояний S1 определяется условно оптимальное решение, т.е. оптимальная денежная сумма, выделяемая предприятию П2 при условии, что имеются денежные средства в размере S1. Средства для предприятия П2 должны выделяться таким образом, чтобы обеспечить максимальную суммарную прибыль предприятий П2, П3 и П4.

Предположим, что денежные средства, распределяемые между предприятиями П2, П3 и П4, составляют 20 млн ден. ед. (S1 = 20). Предприятию П можно выделить 0 или 20 млн ден. ед. (U2 = 0 или U2 = 20). Если U2 = 0, то предприятие П2 не получит прибыли (Z2 = 0). В этом случае остаток средств (состояние) в конце второго шага составит S2 = 20 млн ден. ед. Эти средства будут распределены между предприятиями П3 и П4. Из табл. 7.3 видно, что при оптимальном распределении таких средств между предприятиями П3 и П4 максимальная суммарная прибыль этих предприятий составит E3 = 12 млн ден. ед.

Суммарная прибыль предприятий П2, П3 и П4 составит E2 = 0 + 12 = 12 млн ден. ед. Если U2 = 20, то предприятие П2 получит прибыль Z2 = 10 млн ден. ед.

Остаток средств (состояние) в конце третьего шага составит S3 = 0. Предприятиям П3 и П4 не будет выделено никаких средств, и они не получат прибыли ( E3 = 0), а суммарная прибыль предприятий П2, П3 и П4 составит E2 = 10 + 0 = = 10 млн ден. ед. Таким образом, для состояния S1 = 20 условно оптимальное решение U * = 0, условно оптимальный критерий эффективности E * = 12 млн ден. ед. Это означает, что при распределении средств в размере 20 млн ден. ед.

между предприятиями П2, П3 и П4, предприятию П2 не следует выделять средства; все имеющиеся средства следует распределить между предприятиями П и П4.

Предположим, что денежные средства, распределяемые между предприятиями П2, П3 и П4, составляют 40 млн ден. ед. (S1 = 40). Предприятию П можно выделить 0, 20 или 40 млн ден. ед. (U2 = 0, 20 или 40). Если U2 = 0, то предприятие П2 не получит прибыли (Z2 = 0). Остаток средств в конце второго шага составит S2 = 40 млн ден. ед. Эти средства будут распределены между предприятиями П3 и П4. Из табл. 7.3 видно, что максимальная прибыль этих предприятий от использования таких средств составит E 3 = 18 млн ден. ед.

Суммарная прибыль предприятий П2, П3 и П4 составит E2 = 0 + 18 = 18 млн ден. ед. Аналогично можно определить, что при U2 = 20 суммарная прибыль предприятий П2, П3 и П4 составит E2 = 10 + 12 = 22 млн ден. ед. При U2 = суммарная прибыль предприятий П2, П3 и П4 составит E2 = 18 + 0 = 18 млн ден. ед. Таким образом, для состояния S1 = 40 условно оптимальное решение U * = 20, условно оптимальный критерий эффективности E * = 22 млн ден. ед.

Это означает, что при распределении средств в размере 40 млн ден. ед. между предприятиями П2, П3 и П4, предприятию П2 следует выделить 20 млн ден. ед.

Аналогично можно определить, что при распределении между предприятиями П2, П3 и П4 средств в размере 60 млн ден. ед. предприятию П2 следует выделить 40 млн ден. ед.

Шаг 1 (выделение средств предприятиям П1, П2, П3 и П4) Все расчеты для шага 1 приведены в табл. 7.5. Обозначения в таблице:

S0 – начальная сумма денежных средств, распределяемых между всеми предприятиями; U1 – возможные варианты выделения средств предприятию П1;

Z1 – прибыль предприятия П1 от выделения средств в размере U1; S1 – остаток денежных средств после их выделения предприятию П1 (т.е. средства, выделяемые предприятиям П2, П3 и П4); E * – максимальная суммарная прибыль предприятий П2, П3 и П4 от выделенных им средств в размере S1 (определяется из табл. 7.4); E1 – суммарная прибыль предприятий П1, П2, П3 и П4, т.е.

всех предприятий (сумма величин из столбцов Z1 и E 2 ); U 1 – безусловно оптимальное решение для состояния S0 (денежные средства, которые следует выделить предприятию П1 при наличии суммы S0); E1 – безусловно оптимальный критерий эффективности для предприятий П1, П2, П3 и П4, т.е. прибыль, получаемая всеми предприятиями в результате решения U 1.

Начальная сумма денежных средств (состояние S0) известна: S0 = 60. Требуется определить, сколько средств необходимо выделить предприятию П1, чтобы обеспечить максимальную суммарную прибыль предприятий П1, П2, П3 и П4, т.е. всех предприятий. Так как начальное состояние на этом шаге известно точно (в отличие от других шагов), будет найдено безусловно оптимальное решение.

Предприятию П1 можно выделить 0, 20, 40 или 60 млн ден. ед. (U1 = 0, 20, 40 или 60). В зависимости от выделенных средств прибыль предприятия П (Z1) может составлять 0, 9, 16 или 22 млн ден. ед. Остаток средств в конце первого шага S1 (сумма, выделяемая предприятиям П2, П3 и П4) может составлять 60, 40, 20 или 0 млн ден. ед. Из табл. 7.4 определяется максимальная прибыль предприятий П2, П3 и П4 ( E * ) от использования средств в размере S1: она может составлять 30, 22, 12 или 0 млн ден. ед. Для всех случаев определяется сумсуммарная прибыль предприятий П1, П2, П3 и П4 (E1): она может составлять 30, 31, 28 или 22 млн ден. ед. Таким образом, максимальная прибыль предприятий П1, П2, П3 и П4 (т.е. всех предприятий) достигается, если выделить предприятию П1 20 млн ден. ед. (при условии, что для остальных предприятий средства также будут распределяться оптимальным образом). Это означает, что оптимальным решением является выделение предприятию П1 средств в размере 20 млн ден. ед.: U 1 = 20. Прибыль всех предприятий в этом случае составит 31 млн ден. ед.

Цикл безусловной оптимизации Для первого шага (выделение средств предприятию П1) получено безусловно оптимальное решение: U 1 = млн ден. ед. Для предприятий П2, П3 и П4 остается 40 млн ден. ед. Таким образом, состояние в начале второго шага S1 = 40. Из табл. 7.4 для этого состояния определяется оптимальное решение: U 2 = 20 (предприятию П выделяется 20 млн ден. ед.). Для предприятий П3 и П4 остается 20 млн ден. ед. (состояние в начале третьего шага S2 = 20). Из табл. 7.3 для этого состояния определяется оптимальное решение: U 3 = 0 (предприятию П средства не выделяются). Для предприятия П4 остается 20 млн ден. ед. (S3 = 20). Поэтому U 4 = 20.

Таким образом, оптимальное решение задачи следующее. Предприятию П1 следует выделить 20 млн ден. ед., предприятию П2 – также 20 млн ден. ед., предприятию П3 – не выделять средства, предприятию П4 – выделить 20 млн ден. ед. Общая прибыль составит 31 млн ден. ед., в том числе прибыль предприятия П1 – 9 млн ден. ед., П2 – 10 млн ден. ед., П3 – 0, П4 – 12 млн ден. ед.

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

В конце каждого квартала выручка каждого предприятия распределяется следующим образом: 20% выплачивается акционерам фирмы, 80% – перераспределяется между предприятиями.

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

Величины в таблице обозначают следующее: если, например, предприятию П в начале января будет выделен 1 млн ден. ед., то прибыль предприятия к концу марта составит 800 тыс. ден. ед. (80% от выделенной суммы). Таким образом, выручка предприятия за квартал составит 1 млн 800 тыс. ден. ед.

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

В качестве состояния операции будем использовать величину имеющихся средств, которые требуется распределить. Начальное состояние S0 = 5. Состояние в начале k-го шага будем обозначать как Sk-1. Решение на каждом шаге – это денежные средства, выделяемые каждому из предприятий. Будем обозначать средства, выделяемые предприятию П1, как Uk, а средства, выделяемые предприятию П2 – как Sk-1 – Uk, k = 1,..., 4. Критерий эффективности для каждого шага – сумма выплат акционерам (Zk, k = 1,..., 4). Общий критерий эффективности – это выплаты акционерам в течение года: E = Z1 + Z2 + Z3 + Z4.

Цикл условной оптимизации Шаг 4 (распределение средств в четвертом квартале) Пусть в конце третьего квартала между предприятиями распределяется сумма в размере S3. Пусть предприятию П1 выделяется сумма в размере U4, а предприятию П2 – S3 – U4. Тогда выручка предприятий к концу четвертого квартала составит 1,7U4 + 1,4(S3 – U4). Из этой суммы акционерам будет выплачено 20%. Таким образом, выплаты акционерам в конце четвертого квартала определяются следующим образом:

E4 = Z4 = 0,2(1,7U4 + 1,4(S3 – U4)) = 0,06U4 + 0,28S3.

Видно, что максимальные выплаты акционерам обеспечиваются при максимальном значении U4. Это означает, что предприятию П1 в четвертом квартале следует выделить всю имеющуюся сумму:

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

Шаг 3 (распределение средств в третьем и четвертом кварталах) Пусть в конце второго квартала между предприятиями распределяется сумма в размере S2. Пусть предприятию П1 выделяется сумма в размере U3, а предприятию П2 – S2 – U3. Тогда выручка предприятий к концу третьего квартала составит 1,5U3 + 1,8(S2 – U3). Из этой суммы 20% будет выплачено акционерам, а 80% – распределено между предприятиями. Выплаты акционерам за третий и четвертый кварталы определяются следующим образом:

E3 = Z3 + мых между предприятиями в начале четвертого квартала. Эта сумма составляет 80% от выручки предприятий в третьем квартале: S3 = 0,8(1,5U3 + 1,8(S2 – U3)). Таким образом, + 1,8(S2 – U3)) = 0,49S2 – 0,08U3.

Подставляя эту величину в уравнение для E3, получим:

E3 = 0,2(1,5U3 + 1,8(S2 – U3)) + 0,49S2 – 0,08U3 = 0,85S2 – 0,14U3.

Видно, что максимальные выплаты акционерам обеспечиваются при минимальном значении U3 (так как коэффициент при U3 отрицательный). Таким образом, условно оптимальное решение для третьего квартала состоит в том, чтобы не выделять средства предприятию П1: U 3 = 0. Подставляя U3 = 0, получим выражение для усE 3 = 0,85S2.

ловно оптимального значения критерия эффективности на третьем и четвертом шагах:

Шаг 2 (распределение средств во втором – четвертом кварталах) Пусть в конце первого квартала между предприятиями распределяется сумма в размере S1. Пусть предприятию П1 выделяется сумма в размере U2, а предприятию П2 – сумма в размере S1 – U2. Тогда выручка предприятий к концу второго квартала составит 1,5U2 + 2,2(S1 – U2). Из этой суммы 20% будет выплачено акционерам, а 80% – распределено между предприятиями. Выплаты акционерам за второй – четвертый кварталы определяются следующим образом:

E2 = Z2 + Выполнив расчеты, аналогичные приведенным на шаге 3, выразим величину E2 через U2 и S1:

E2 = 0,2(1,5U2 + 2,2(S1–U2)) + = 0,2(1,5U2 + 2,2(S1–U2)) + 0,850,8(1,5U2 + 2,2(S1 – U2)) = Видно, что максимальные выплаты акционерам обеспечиваются при минимальном значении U2 (так как коэффициент при U2 отрицательный). Таким образом, условно оптимальное решение для второго квартала состоит в том, чтобы не выделять средства предприятию П1: U 2 = 0. Подставляя U2 = 0 в выражение для E2, получим выражение для условно оптимального значения критерия эффективности на втором – четвертом шагах:

E2 = 1,94S1.

Шаг 1 (распределение средств в первом – четвертом кварталах) В начале первого квартала между предприятиями распределяется сумма в размере S0 = 5. Пусть предприятию П1 выделяется сумма в размере U1, а предприятию П2 – сумма в размере S0 – U1. Выручка предприятий к концу первого квартала составит 1,8U1 + 1,4(S0 – U1). Как и в другие кварталы, 20% из этой суммы будет выплачено акционерам, а 80% – распределено между предприятиями. Выплаты акционерам за первый – четвертый кварталы определяются следующим образом:

Выполнив расчеты, аналогичные приведенным на предыдущих шагах, выразим величину E1 через U1 и S0:

E1 = 0,2(1,8U1 + 1,4(S0 – U1)) + = 0,2(1,8U1 + 1,4(S0 – U1)) + 1,94S1 = = 0,2(1,8U1 + 1,4(S0 – U1)) + 1,940,8(1,8U1 + 1,4(S0 – U1)) = 2,45S0 + 0,7U1.

Видно, что максимальные выплаты акционерам за весь год обеспечиваются при максимальном значении U1. Таким образом, безусловно оптимальное решение для первого квартала состоит в том, чтобы выделить чальное состояние известно: S0 = 5 млн ден. ед. Итак, в первом квартале предприятию П1 следует выделить млн ден. ед.

Цикл безусловной оптимизации Шаг 1 (распределение средств в первом квартале) Безусловно оптимальное решение для первого квартала найдено выше:

U 1 = 5 (все имеющиеся средства выделяются предприятию П1).

Выручка предприятия П1 к концу первого квартала составит 1,85 = = 9 млн ден. ед. Найдем сумму выплат акционерам в первом квартале: Z1 = 0,29 = = 1,8 млн ден. ед. Найдем состояние в конце первого квартала, т.е. сумму средств, распределяемых между предприятиями в начале второго квартала:

S1 = 0,89 = 7,2 млн ден. ед.

Шаг 2 (распределение средств во втором квартале) Состояние в начале второго шага S1 = 7,2 млн ден. ед. В ходе условной оптимизации выяснено, что все эти средства следует выделить предприятию П ( U 2 = 0).

Выручка предприятия П2 к концу второго квартала составит 2,27,2 = = 15,84 млн ден. ед. Выплаты акционерам во втором квартале составят Z2 = 0,215,84 = 3,17 млн ден. ед. Состояние в конце второго шага (т.е. сумма средств, распределяемых между предприятиями в начале третьего квартала) следующее: S2 = 0,815,84 = 12,67 млн ден. ед.

Шаг 3 (распределение средств в третьем квартале) Состояние в начале третьего шага S2 = 12,67 млн ден. ед. В ходе условной оптимизации выяснено, что все эти средства следует выделить предприятию П ( U 3 = 0).

Выручка предприятия П2 к концу третьего квартала составит 1,812,67 = = 22,81 млн ден. ед. Выплаты акционерам в третьем квартале составят Z3 = 0,222,81 = 4,56 млн ден. ед. Состояние в конце третьего шага (т.е. сумма средств, распределяемых между предприятиями в начале четвертого квартала) следующее: S3 = 0,822,81 = 18,25 млн ден. ед.

Шаг 4 (распределение средств в четвертом квартале) Состояние в начале четвертого шага S3 = 18,25 млн ден. ед. В ходе условной оптимизации выяснено, что все эти средства следует выделить предприятию П1 ( U 3 = S3 = 18,25).

Выручка предприятия П1 к концу четвертого квартала составит 1,718,25 = 31,03 млн ден. ед. Выплаты акционерам в четвертом квартале составят Z4 = 0,231,03 = 6,21 млн ден. ед.

Таким образом, оптимальное решение задачи следующее. В первом квартале следует выделить предприятию П1 5 млн ден.ед, во втором квартале выделить предприятию П2 7,2 млн ден. ед., в третьем квартале выделить предприятию П2 12,67 млн ден. ед., в четвертом квартале выделить предприятию П1 18,25 млн ден. ед. Выплаты акционерам в первом квартале составят 1,8 млн ден. ед., во втором – 3,17, в третьем – 4,56, в четвертом – 6,21 млн ден. ед. Таким образом, выплаты акционерам в течение года составят 15,74 млн ден. ед.

8. АНАЛИЗ И ОПТИМИЗАЦИЯ РЕШЕНИЙ

НА ОСНОВЕ МОДЕЛЕЙ МАССОВОГО ОБСЛУЖИВАНИЯ

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

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

Заявки, поступающие на обслуживание в СМО (заказы, детали, задачи, покупатели и т.д.), образуют поток заявок. Элементы СМО, обслуживающие заявки, называются каналами обслуживания.

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

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

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

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

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

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

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

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

Количество заявок в пуассоновском потоке, поступающих на обслуживание за некоторый интервал времени, представляет собой пуассоновскую случайную величину. Это означает, что вероятность поступления ровно k заявок за некоторый интервал времени t определяется по формуле где – интенсивность потока заявок, т.е. среднее количество заявок, поступающих в единицу времени.

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

Законы распределения интервалов времени между заявками и времени обслуживания в СМО. Интервалы времени между моментами поступления заявок и времена обслуживания заявок в СМО обычно представляют собой случайные величины. Во многих случаях эти величины описываются следующими законами распределения:

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

• равномерный закон – если интервал времени между заявками или время их обслуживания всегда принимает значение в пределах некоторого диапазона;

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

• закон Эрланга k-го порядка – если интервал времени между заявками или время их обслуживания представляет собой сумму k случайных величин, распределенных по экспоненциальному закону.

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

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

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

X – математическое ожидание (среднее значение) случайной величины.

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

В табл. 8.1 приведены коэффициенты вариации для некоторых величин, часто применяемых для описания СМО.

В дальнейшем будем обозначать коэффициент вариации интервалов времени между заявками как, а коэффициент вариации времени обслуживания – как.

8.3. Типовой узел СМО. Классификация СМО Любая СМО может быть представлена в виде одного или нескольких типовых узлов. Типовой узел СМО показан на рис.8.1.

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

Имеется несколько вариантов классификации СМО (табл. 8.2).

Для описания СМО может использоваться обозначение A/B/m – d, где A – обозначение закона распределения интервалов времени между заявками; B – обозначение закона распределения времени обслуживания заявок; m – количество каналов; d – обозначение дисциплины обслуживания. В качестве A и B обычно используются следующие обозначения: M – экспоненциальное распределение, G – любое другое. Для некоторых распределений используются специальные обозначения, например, D – детерминированная величина, Ek – распределение Эрланга k-го порядка, и т.д. Примеры таких обозначений будут приведены ниже.

Признак сификации ограниче- очереди и/или время их пребывания в очереди.

ниями на Если заявка поступает на обслуживание в моочередь мент, когда в очереди уже имеется предельное количество заявок, или время пребывания заявки в очереди превышает допустимое, то она Без оче- Если заявка поступает на обслуживание в мореди мент, когда все каналы заняты, то она покидает Коли- Замкну- Имеется фиксированное количество заявок, печество тые риодически требующих обслуживания.

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

СМО Количество узлов, в которых требуется обслуживание, и порядок их прохождения могут Дисци- FIFO «Первым пришел – первым обслужен» (обслуплина живание в порядке поступления) обслу- LIFO «Первым пришел – последним обслужен»

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

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

Основные параметры каналов обслуживания – количество каналов (m), среднее время обслуживания заявки в канале ( x ). В расчетах вместо величины x часто используется интенсивность обслуживания заявок µ = 1 / x. Эта величина представляет собой среднее количество заявок, которое может быть обслужено одним каналом СМО в единицу времени. Другими словами, интенсивность обслуживания – это количество заявок, обслуживаемых каналом в единицу времени при условии, что канал никогда не простаивает из-за отсутствия заявок.

Параметром СМО с ограничением на количество заявок в очереди является также максимальное (предельно допустимое) количество заявок в очереди (n).

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

P0 – вероятность простоя СМО. Эта величина показывает, какую часть от общего времени работы СМО все ее каналы свободны, т.е. простаивают из-за отсутствия заявок;

Pотк – вероятность отказа. Эта величина показывает, какая доля всех поступающих заявок не обслуживается системой из-за занятости ее каналов или большого количества заявок в очереди. Для СМО без ограничений на очередь Pотк = 0;

Pобсл – вероятность обслуживания. Эта величина показывает, какая доля всех поступающих заявок обслуживается системой. Очевидно, что Pобсл = = 1 – Pотк. Для СМО без отказов Pобсл = 1;

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

q – среднее число заявок в очереди (средняя длина очереди);

S – среднее число заявок на обслуживании (в каналах), или среднее число занятых каналов;

k – среднее число заявок в СМО, т.е. на обслуживании и в очереди;

w – среднее время пребывания заявки в очереди (среднее время ожидания обслуживания);

t – среднее время пребывания заявки в СМО, т.е. в очереди и на обслуживании;

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

Величины P0, U и S характеризуют степень загрузки СМО. Эти величины представляют интерес с точки зрения стороны, осуществляющей эксплуатацию СМО.

Например, если в качестве СМО рассматривается предприятие, выполняющее некоторые заказы, то эти величины представляют интерес для владельцев предприятия.

Обычно желательно, чтобы коэффициент загрузки СМО имел значение на уровне 0, – 0,85. Значения U < 0,75 указывают, что СМО простаивает значительную часть времени, т.е. используется нерационально. Значения U > 0,85 указывают на перегрузку СМО.

Величины Pотк, Pобсл, w и t характеризуют качество обслуживания заявок.

Они представляют интерес с точки зрения пользователей СМО. Желательна минимизация значений Pотк, w, t и максимизация Pобсл.

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

Величины q и k обычно используются в качестве вспомогательных для расчета других характеристик СМО.

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

Величина представляет собой отношение интенсивности потока заявок к интенсивности, с которой СМО может их обслуживать. Любая СМО без ограничений на очередь может нормально работать (т.е. обслуживать все поступающие заявки) только при условии, что < 1. Величина > 1 означает, что количество заявок, поступающих в СМО в единицу времени (), превышает количество заявок, которые СМО может обслужить в единицу времени (mµ). В таких условиях в СМО без ограничений на очередь количество заявок, ожидающих обслуживания, будет постоянно возрастать, так как заявки будут поступать в СМО быстрее, чем она может их обслуживать. Для СМО с ограничениями на очередь и без очереди возможны любые значения, так как в таких СМО часть заявок получает отказ, т.е. не допускается в СМО.

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

Коэффициент загрузки:

Среднее число заявок на обслуживании (среднее число занятых каналов):

Среднее число заявок в СМО:

Пропускная способность СМО:

или Среднее время пребывания заявки в очереди (формула Литтла):

Среднее время пребывания заявки в СМО:

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

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

• коэффициент загрузки: U = ;

• пропускная способность: =.

Эти формулы представляют собой частные случаи формул (8.4) и (8.8) для Pотк = 0.

Вероятность простоя (P0), вероятность отказа (Pотк) и средняя длина очереди ( q ) рассчитываются по-разному в зависимости от типа СМО.

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

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

8.5. Вероятности состояний СМО Вероятности состояний СМО – это вероятности пребывания в СМО определенного количества заявок. Обычно при вычислении вероятностей состояний требуется определять величины Pj – вероятности пребывания в СМО ровно j заявок. Например, P2 – вероятность того, что в СМО (т.е. на обслуживании и в очереди) находятся ровно две заявки. Если, например, P2 = 0,15, это означает, что в течение 15% времени (от всего времени работы СМО) в ней находятся ровно две заявки. В течение остального времени (85%) количество заявок в СМО составляет менее двух (одну или ни одной) или более двух (три или больше).

Величины Pj вычисляются по-разному для разных типов СМО. Точный расчет Pj возможен только для марковских СМО, т.е. СМО типа M/M/m.

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

• вероятность пребывания в СМО не более R заявок:

• вероятность пребывания в СМО более R заявок:

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

8.6. Экономические характеристики СМО Под экономическими характеристиками будем понимать величины, выражающие прибыль от работы СМО, затраты на обслуживание заявок и т.д. Расчет таких характеристик зависит от постановки задачи. Приведем несколько общих формул, применимых в большинстве задач.

Выручка от обслуживания заявок в СМО в течение времени T:

где – пропускная способность СМО;

C – выручка от обслуживания одной заявки.

Затраты, связанные с обслуживанием заявок в СМО в течение времени T:

где Cобс – затраты, связанные с обслуживанием одной заявки.

Затраты, связанные с эксплуатацией СМО в течение времени T:

где m – количество каналов в СМО;

S – среднее число заявок на обслуживании (в каналах), или среднее число занятых каналов;

Cраб – затраты, связанные с работой одного канала в течение единицы времени;

Cпр – затраты, связанные с простоем одного канала в течение единицы времени.

Убытки, связанные с отказами в обслуживании за время T:

где – интенсивность потока заявок;

Cотк – убытки, связанные с отказом в обслуживании одной заявки;

Pотк – вероятность отказа.

Убытки за время T, связанные с пребыванием заявок в СМО (как в очереди, так и на обслуживании):

где k – среднее число заявок в СМО;

Cпр – убытки, связанные с пребыванием заявки в СМО в течение единицы времени.

8.7. Одноканальные СМО без ограничений на очередь Для расчета характеристик таких СМО применяются следующие формулы.

Вероятность простоя:

Средняя длина очереди:

где – коэффициент вариации интервалов времени между заявками;

– коэффициент вариации времени обслуживания.

Формула (8.20) позволяет точно рассчитать среднюю длину очереди только для СМО типа M/M/1, т.е. для марковских СМО. Для других СМО величина q, найденная по формуле (8.20), является приближенной.

Для СМО типа M/M/1 можно также определить следующие величины.

Вероятности пребывания в СМО j заявок:

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

Пример 8.1. В небольшой мастерской имеется один стенд для ремонта и наладки некоторых приборов. В течение рабочего дня в мастерскую в среднем поступает 10 заявок на ремонт приборов; поток заявок можно считать пуассоновским. За рабочий день на стенде можно отремонтировать 12 приборов. Время ремонта одного прибора – случайная величина, которую можно приближенно считать экспоненциальной. Приборы, ожидающие ремонта, размещаются на специальных стеллажах, составляемых из стандартных секций. Одна секция вмещает 6 приборов. Если на стеллажах нет места, то прибор приходится размещать на полу, что нежелательно.

За ремонт одного прибора мастерская берет плату в размере 40 ден. ед., если заказ на ремонт выполняется в течение одного дня, и 30 ден. ед. – если выполнение заказа занимает более одного дня. Затраты, связанные с ремонтом одного прибора, составляют 25 ден. ед.

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

Поток заявок (приборов) является пуассоновским, время обслуживания распределено по экспоненциальному закону, и имеется один канал обслуживания. Поэтому мастерскую можно представить как СМО типа M/M/1. В этой СМО = 10 заявок/день, µ = 12 заявок/день, x = 1/12 = 0,083 дня. Число каналов m = 1.

Найдем нагрузку на СМО: = /(mµ) = 0,83.

Найдем вероятность простоя по формуле (8.19): P0 = 0,17.

Найдем среднюю длину очереди по формуле (8.20). Из табл. 8.1 найдем коэффициенты вариации. Так как поток заявок пуассоновский, интервалы времени между заявками – экспоненциальные случайные величины. Поэтому = 1. Время обслуживания заявок (т.е. ремонта приборов) – также экспоненциальная случайная величина, поэтому = 1. По формуле (8.20) получим: q = 4,17 приборов.

Мастерская принимает на обслуживание все поступающие приборы (отказов в обслуживании нет). Поэтому Pотк = 0, Pобсл = 1.

Найдем остальные характеристики СМО по формулам (8.4)–(8.11): U = 0,83;

S = 0,83 прибора; k = 5 приборов; = 10 приборов/день; w = 0,417 дня; t = 0,5 дня.

Проанализируем полученные характеристики СМО.

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

В среднем в очереди находится 4,17 прибора, а в мастерской (т.е. в очереди и на обслуживании) – 5 приборов. Мастерская обслуживает в среднем 10 приборов в день, т.е. все поступающие приборы. Время от поступления прибора в мастерскую до начала его ремонта (т.е. время пребывания прибора в очереди) составляет в среднем 0,417 дня. Время от поступления прибора в мастерскую до окончания его ремонта (время пребывания прибора в мастерской) составляет в среднем 0,5 дня.

Найдем прибыль от работы мастерской за один рабочий день. При этом необходимо учесть, что выручка мастерской от ремонта одного прибора может быть разной. Она составляет 40 ден. ед., если заказ на ремонт выполняется в течение одного дня, и 30 ден. ед. – в противном случае. По формуле (8.22) найдем долю заказов, время выполнения которых превышает один день: P(t > T) = –12·(1–0,83)· =e = 0,13. Значит, в 13% случаев выручка от ремонта одного прибора составляет 30 ден. ед., в остальных случаях – 40 ден. ед. Можно считать, что средняя выручка от ремонта одного прибора составляет 30·0,13 + 40·0,87 = = 38,7 ден. ед. Мастерская ремонтирует в среднем 10 приборов в день, затрачивая на ремонт каждого прибора 25 ден. ед. Таким образом, прибыль мастерской за один день составит в среднем (38,7 – 25)·10 = 127 ден. ед.

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

Предположим, что стеллажи состоят из одной стандартной секции, т.е. вмещают приборов. Найдем вероятность их переполнения. Стеллажи будут переполнены, если в мастерской будет находиться более семи приборов, так как в этом случае один прибор будет находиться на обслуживании (на стенде), шесть – на стеллажах, остальные – на полу. Таким образом, вероятность переполнения стеллажей, вмещающих шесть приборов, равна вероятности пребывания в мастерской восьми и более приборов. Эта вероятность определяется по формуле (8.13): P(j > 7) = 1 – P0 – P1 – P2 – P3 – P4 – P – P6 – P7. Величина P0 найдена выше: P0 = 0,17. Остальные вероятности найдем по формуле (8.21): P1 = 0,141, P2 = 0,117, P3 = 0,097, P4 = 0,081, P5 = 0,067, P6 = 0,056, P7 = 0,046. Здесь P0 – вероятность простоя (вероятность того, что в СМО нет ни одной заявки); P1 – вероятность пребывания в СМО ровно одной заявки (вероятность того, что на обслуживании в СМО находится заявка, но в очереди заявок нет); P2 – вероятность пребывания в СМО ровно двух заявок (вероятность того, что на обслуживании в СМО находится заявка, и еще одна заявка находится в очереди), и т.д. Вероятность переполнения стеллажей следующая:

P(j > 7) = 1 – 0,17 – 0,141 – 0,117 – 0,097 – 0,081 – 0,067 – 0,056 – 0,046 = 0,225.

Эта вероятность превышает 5%, поэтому одной секции недостаточно.

Найдем вероятности переполнения стеллажей большей емкости:

• из двух секций: P(j > 13) = 0,074;

• из трех секций: P(j > 19) = 0,024.

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

Пример 8.2. Станок-автомат используется для выпуска некоторых деталей.

Интервалы между моментами поступления деталей на обработку составляют от 3 до минут. Время обработки детали на станке-автомате – случайная величина, распределенная по гауссовскому закону со средним значением 4 мин и стандартным отклонением 30 с. Затраты на один час работы станка-автомата составляют 40 ден. ед., на один час простоя – 15 ден. ед. Материал, необходимый для изготовления детали, стоит 1,5 ден. ед. Готовые детали продаются по цене 10 ден. ед.

Найти характеристики работы станка и среднюю прибыль от его работы за одну рабочую смену (8 часов).

Интервалы времени между моментами поступления заявок (деталей) представляют собой случайные величины, распределенные по равномерному закону. Время обработки детали – гауссовская случайная величина. Имеется один канал обслуживания. Поэтому станок можно представить как СМО типа G/G/1. Интервал между деталями составляет в среднем 5,5 мин, поэтому = = 1/5,5 = 0,182 детали/мин. Обработка одной детали занимает в среднем 4 мин, поэтому x = 4 мин, µ = 0,25 детали/мин. Число каналов m = 1.

Найдем нагрузку на СМО: = /(mµ) = 0,728.

Найдем вероятность простоя по формуле (8.19): P0 = 0,272.

Найдем среднюю длину очереди по формуле (8.20). Коэффициент вариации для интервалов между моментами поступления деталей найдем из табл. 8.1 (для равномерного закона): = (8 – 3)/((8 + 3) 3 ) = 0,262. Коэффициент вариации для времени обработки деталей найдем по формуле (8.2): = 0,5/4 = 0,125. По формуле (8.20) получим: q = 0,082 деталей.

Станок обрабатывает все поступающие детали. Поэтому Pотк = 0, Pобсл = 1.

Найдем остальные характеристики СМО по формулам (8.4)–(8.11): U = 0,728, S = 0,728 детали, k = 0,81 детали, = 0,182 детали/мин, w = 0,45 мин, t = 4,45 мин.

Найдем прибыль от работы станка за рабочую смену. По формуле (8.14) найдем выручку от продажи деталей, выпускаемых за смену: V = 0,182·10·480 = 873,6 ден.

ед. (здесь 480 – продолжительность рабочей смены в минутах). По формуле (8.15) найдем затраты на материал для изготовления деталей: Zобс = 0,182·1,5·480 = 131, ден. ед. По формуле (8.16) найдем затраты, связанные с эксплуатацией станка в течение + (1 – 0,728)·15)·8 = 265,6 ден. ед. (здесь 8 – продолжительность рабочей смены в часах, так как в формуле используются величины затрат за один час работы и простоя станка). Найдем прибыль от работы станка: 873,6 – 131,04 – 265,6 = = 476,96 ден. ед.

8.8. Многоканальные СМО без ограничений на очередь Для многоканальных СМО точный расчет характеристик возможен только при условии, что СМО является марковской, т.е. для СМО типа M/M/m. Для расчета характеристик таких СМО применяются следующие формулы.

где m – количество каналов (т.е. количество заявок, которые могут обслуживаться в СМО Вероятности пребывания в СМО j заявок:

Формула (8.25) позволяет найти вероятности состояний СМО, при которых очередь отсутствует (количество заявок, обслуживаемых в СМО, не превышает количества каналов), а формула (8.26) – вероятности состояний при наличии очереди.

Примечание. Приведенные формулы могут применяться и для приближенного расчета характеристик немарковских многоканальных СМО (т.е. СМО типа M/G/m, G/M/m или G/G/m).

Пример 8.3. В ремонтной службе предприятия выполняется наладка некоторых механизмов. На наладку поступает в среднем 10 механизмов в час (поток механизмов можно считать пуассоновским). Наладка одного механизма занимает в среднем 15 мин (время наладки инструмента можно считать экспоненциальной случайной величиной). В ремонтной службе работают три наладчика. Заработная плата наладчика составляет 30 ден. ед. в день.

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

Найти: а) характеристики работы ремонтной службы; б) потери предприятия в течение рабочей смены (8 часов), связанные с наладкой инструментов, включая затраты на содержание ремонтной службы и убытки от простоя механизмов; в) вероятность того, что наладка механизма начнется сразу же после его поступления (без ожидания в очереди); г) вероятность того, что количество механизмов, ожидающих наладки, окажется свыше пяти; д) определить, целесообразно ли уменьшить количество наладчиков до двух; е) определить, целесообразно ли увеличить количество наладчиков до а) Ремонтную службу можно рассматривать как СМО типа M/M/3 без ограничений на очередь. В этой СМО = 10 механизмов/час = 0,167 механизма/мин, x = мин, µ = 0,067 механизма/мин.

Найдем нагрузку на СМО: = /(mµ) = 0,833.

Найдем вероятность простоя по формуле (8.23):

По формуле (8.24) определяем среднюю длину очереди (т.е. среднее количество механизмов, ожидающих наладки): q = 3,43 механизма.

Ремонтная служба выполняет наладку всех поступающих механизмов. Поэтому Pотк = 0, Pобсл = 1. Найдем остальные характеристики по формулам (8.4)–(8.11):

U = 0,833, S = 2,49 механизма, k = 5,92 механизма, = 0,167 механизма/мин, w = 20,5 мин, t = 35,5 мин.

б) Затраты на содержание ремонтной службы составляют 30·3 = 90 ден. ед.

Убытки предприятия, связанные с простоем механизмов, найдем по формуле (8.18):

Zпр = 5,92·6·8 = 284,16 ден. ед. за смену. Таким образом, полные потери предприятия, = 374,16 ден. ед. за смену.

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

Вероятность такого состояния находится по формуле (8.12): P(j 2) = P0 + P1 + P2.

= 0,305. Это значит, что примерно в 30,5% случаев механизм, доставленный в ремонтную службу, сразу же поступит к наладчику.

г) Найдем вероятность того, что количество механизмов, ожидающих наладки, окажется свыше пяти. Такое состояние означает, что количество механизмов, находящихся в ремонтной службе, превышает восемь (три из них – на наладке, остальные – в очереди). Вероятность такого состояния находится по формуле (8.13): P(j > 8) = – (P0 + P1 + … + P8). Вероятности P1, P2, P3 найдем по формуле (8.25): P1 = 0,115, P2 = 0,144, P3 = 0,12. Вероятности P4, P5, …, P8 найдем по формуле (8.26): P4 = 0,1, P5 = 0,083, P6 = 0,069, P7 = 0,058, P8 = 0,048. Таким образом, P(j > 8) = 0,218.

д) Найдем нагрузку на СМО при m = 2: = /(mµ) = 1,25. Величина > 1 означает, что механизмы поступают в ремонтную службу с большей интенсивностью, чем она может их обслуживать. Таким образом, два наладчика «не справятся» с потоком заявок.

Уменьшить количество наладчиков до двух нельзя.

е) Найдем характеристики СМО при m = 4: = 0,623, P0 = 0,074, q = 0,53 механизма, Pотк = 0, Pобсл = 1, U = 0,623, S = 2,49 механизма, k = 3,02 механизма, w = 3,14 мин, t = 18,14 мин, = 0,167 механизма/мин.

Затраты на содержание ремонтной службы составляют 30·4 = 120 ден. ед. По формуле (8.18) найдем убытки предприятия, связанные с простоем механизмов:

Zпр = 3,02·6·8 = 144,96 ден. ед. за смену. Таким образом, полные потери предприятия, = 264,96 ден. ед. за смену. Эти потери меньше, чем для трех наладчиков. Поэтому увеличение количества наладчиков до четырех следует признать выгодным.

8.9. СМО с ограничением на длину очереди В СМО такого типа в очереди может находиться не более n заявок. Если заявка поступает в СМО в момент, когда в очереди уже находятся n заявок, то она не обслуживается (не допускается в очередь). Для расчета характеристик таких СМО применяются следующие формулы.

где m – количество каналов СМО;

n – максимально допустимое количество заявок в очереди.

Формула (8.30) позволяет найти вероятности состояний СМО, при которых очередь отсутствует (количество заявок, обслуживаемых в СМО, не превышает количества каналов), а формула (8.31) – вероятности состояний при наличии очереди.

При = 1 расчет вероятности простоя и средней длины очереди выполняется по следующим формулам:

Пример 8.4. Предприятие выполняет заказы на переводы с иностранных языков. В среднем на предприятие поступает 8 заказов в день (поток заказов можно считать пуассоновским). Средний размер перевода – 5 страниц (размер перевода можно считать случайной величиной, распределенной по экспоненциальному закону). На предприятии работают 4 переводчика. Норма для переводчика – 7 страниц в день.

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

Переводчику выплачивается 2 ден. ед. за каждую переведенную страницу, плюс 100 ден. ед. в месяц. Заказчик платит предприятию 4 ден. ед. за каждую переведенную страницу.

Найти а) характеристики работы предприятия; б) среднюю заработную плату переводчика за месяц (25 рабочих дней); в) среднюю прибыль предприятия за месяц;

г) определить, выгодно ли предприятию принять на работу еще одного переводчика.

а) На предприятии работают 4 переводчика (m = 4). Поток заказов – пуассоновский, время их выполнения – экспоненциальная случайная величина. Поэтому предприятие можно рассматривать как СМО типа M/M/4 с ограничением на длину очереди (n = 6). В этой СМО = 8 заказов/день. Так как переводчик может перевести в среднем 7 страниц в день, а средний размер перевода – 5 страниц, значит, производительность переводчика (интенсивность обслуживания заявок) составляет µ = 7/5 = 1,4 заказа/день. Среднее время работы переводчика над заказом x = 1/µ = 0,71 дня.

Найдем нагрузку на СМО: = /(mµ) = 1,43.

Найдем вероятность простоя по формуле (8.27):

(4 1,43)0 (4 1,43)1 (4 1,43)2 (4 1,43)3 (4 1,43)4 (4 1,43)5 11, По формуле (8.28) определяем вероятность отказа в обслуживании:

Pотк = 0,31. Это означает, что примерно 31% заказчиков, обращающихся на предприятие, получают отказ из-за перегруженности переводчиков. Вероятность обслуживания составляет Pобсл = 1 – Pотк = 0,69.

По формуле (8.29) найдем среднюю длину очереди (т.е. среднее количество заказов, ожидающих выполнения): q = 4,1 заказа.

Найдем остальные характеристики по формулам (8.4)–(8.11): U = 0,982, S = 3,93 заказа, k = 8,03 заказа, = 5,5 заказа/день, w = 0,75 дня, t = 1,46 дня.

б) Найдем заработную плату переводчика за месяц (25 рабочих дней). Переводчики, работающие на предприятии, выполняют в среднем 5,5 заказа в день ( = 5,5).

Средний размер заказа – 5 страниц; за каждую страницу переводчику выплачивается ден. ед. Таким образом, сумма, выплачиваемая всем переводчикам за выполнение заказов в течение месяца, составляет в среднем 5,5·5·2·25 = 1375 ден. ед. Заработная плата каждого из переводчиков составляет в среднем 1375/4 + 100 = 443,75 ден. ед. в месяц.

в) Найдем среднюю прибыль предприятия за месяц. Выручка предприятия от выполнения переводов за месяц составляет в среднем 5,5·5·4·25 = 2750 ден. ед. Переводчикам выплачивается 4·443,75 = 1775 ден. ед. Таким образом, прибыль предприятия составляет 2750 – 1775 = 975 ден. ед. в месяц.

г) Определим, выгодно ли предприятию принять на работу еще одного переводчика. Найдем характеристики работы предприятия для m = 5: = 1,14, P0 = 0,00154, Pотк = 0,175, Pобсл = 0,825, q = 2,99 заказа, U = 0,943, S = 4,72 заказа, k = 7,71 заказа, = 6,6 заказа/день, w = 0,45 дня, t = 1,16 дня. Выполнив расчеты, как показано выше, найдем, что выручка предприятия за месяц составит 6,6·5·4·25 = 3300 ден. ед., + 100 = 430 ден. ед., прибыль предприятия – 3300 – 5·430 = 1150 ден. ед.

Таким образом, прием на работу еще одного переводчика приведет к росту прибыли предприятия с 975 до 1150 ден. ед., т.е. на 175 ден. ед. в месяц. Рост прибыли достигнут за счет уменьшения количества отказов, в результате чего увеличивается пропускная способность предприятия. Снижение количества отказов также является положительным результатом, так как улучшает репутацию предприятия. Еще одним положительным результатом является сокращение среднего срока выполнения заказа (с 1,46 до 1,16 дня). Отрицательным результатом является некоторое снижение заработной платы переводчика (с 443,75 до 430 ден. ед. в месяц). Однако предприятие имеет возможность избежать этого, использовав часть дополнительной прибыли на повышение заработной платы переводчиков. Например, если предприятие будет выплачивать переводчикам дополнительно по 15 ден. ед., то заработная плата переводчиков не снизится (и даже увеличится с 443,75 до 445 ден. ед.), а дополнительная прибыль предприятия составит 175 – 5·15 = 100 ден. ед. Таким образом, прием на работу еще одного переводчика следует признать выгодным.

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

Вероятность простоя:

Вероятность отказа в обслуживании:

Вероятности пребывания в СМО j заявок:

Пример 8.5. В телефонную справочную службу поступает в среднем два запроса в минуту (поток запросов можно считать пуассоновским). Длительность разговора можно считать экспоненциальной случайной величиной; в среднем разговор занимает 1,5 минуты. Если в момент звонка в справочную службу все телефоны оказываются занятыми, то клиент вынужден отказаться от разговора (положить трубку).

Найти, сколько телефонов должна иметь справочная служба, чтобы обслуживать не менее 85% клиентов. Для выбранного количества телефонов найти характеристики справочной службы.

Справочную службу можно рассматривать как СМО типа M/M/m без очереди.

Величину m (количество каналов) требуется определить. В данной СМО = 2 звонка/мин, x = 1,5 мин, µ = 0,67 звонка/мин.

Предположим, что в справочной службе имеется только один телефон (m = 1).

Тогда = /(mµ) = 3. По формуле (8.32) найдем вероятность простоя СМО:

По формуле (8.33) найдем вероятность отказа: Pотк = 0,75. Таким образом, 75% клиентов, обратившихся в справочную службу, не будут обслужены из-за ее загруженности. Такой вариант справочной службы явно неприемлем.

Будем увеличивать количество телефонов (т.е. число каналов m) до тех пор, пока вероятность отказа не примет значение, не превышающее 0,15. Значения вероятности отказа для различного количества телефонов приведены в табл. 8.3.

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

Для выбранного варианта справочной службы вероятность простоя составляет P0 = 0,06 (эта величина была необходима для вычисления Pотк). По формулам (8.4)– (8.11) найдем остальные характеристики: U = 0,53, Pобсл = 0,89, q = 0 (так как очередь не образуется), S = 2,66 звонка, k = 2,66 звонка, = 1,78 звонка/мин, w = 0, t = 1,5 мин. Таким образом, справочная служба обслуживает 89% клиентов. Недостатком выбранного варианта является низкая загрузка. Однако уменьшить количество телефонов для устранения этого недостатка нельзя, так как при этом увеличится количество отказов.

8.11. СМО с заявками с разным временем обслуживания В таких СМО обслуживаются заявки нескольких типов, различающихся по времени обслуживания. Пусть в СМО обслуживается R типов заявок. Обозначим долю заявок i-го типа в потоке заявок как Pi, i = 1, …, R, P1 + P2 +... + + PR = 1. Времена обслуживания заявок разных типов представляют собой случайные (или детерминированные) величины; для расчета характеристик СМО законы распределения этих величин должны быть известны. Среднее время обслуживания заявки iго типа обозначим как xi, i = 1, …, R.

Для расчета характеристик таких СМО необходимо определить среднее время обслуживания и коэффициент вариации времени обслуживания всех заявок в СМО.

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

1. Находятся дисперсии времени обслуживания заявок каждого типа: Di, i = 1, …, R.

Для этого должны быть известны законы распределения времени обслуживания заявок.

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

Примечание. Второй начальный момент случайной величины – это математическое ожидание (т.е. среднее значение) квадрата этой величины.

3. Находится второй начальный момент времени обслуживания всех заявок:

4. Находится дисперсия времени обслуживания всех заявок:

5. Находится коэффициент вариации времени обслуживания всех заявок:

Дальнейший расчет характеристик СМО выполняется точно так же, как для любой СМО типа M/G/1, G/G/1, M/G/m или G/G/m (см. подразделы 8.7, 8.8).

Пример 8.6. Детали, при изготовлении которых допущен дефект, направляются для устранения дефекта на специальный станок. При изготовлении деталей возможны дефекты трех видов (обозначим их как A, B и C). Детали, имеющие несколько дефектов (два или три) одновременно, не подлежат ремонту; поэтому каждая деталь, поступающая на станок, имеет только один дефект. Детали, имеющие дефект A, поступают на станок в среднем через каждые 20 мин, с дефектом B – через каждые мин, с дефектом C – через каждые 25 мин. Потоки деталей с дефектами каждого вида можно считать пуассоновскими. Устранение дефекта A занимает от 2 до 5 мин, устранение дефекта B – ровно 5 мин; время устранения дефекта C представляет собой гауссовскую случайную величину со средним значением 7 мин и стандартным отклонением 1,5 мин.

Требуется найти характеристики работы станка.

Так как потоки деталей с дефектами каждого вида можно считать пуассоновскими, поток всех деталей также можно считать пуассоновским (подробнее об этом см. в подразделе 8.13). Найдем интенсивности потоков деталей с дефектами каждого вида: A = 1/20 = 0,05 детали/мин, B = 1/10 = 0,1 детали/мин, C = 1/25 = 0,04 детали/мин. Интенсивность потока всех деталей представляет собой сумму интенсивностей отдельных потоков: = A + B + C = 0,19 детали/мин.

Найдем доли деталей каждого вида в общем потоке деталей: PA = = 0,05/0,19 = 0,26; PB = 0,1/0,19 = 0,53; PC = 0,04/0,19 = 0,21.

Найдем среднее время обработки деталей всех видов. Средние времена обработки деталей каждого вида следующие: x A = (2 + 5)/2 = 3,5 мин, x B = = 5 мин, xC = 7 мин. Среднее время обработки деталей всех видов: x = = 0,26·3,5 + 0,53·5 + 0,21·7 = 5,03 мин.

Найдем коэффициент вариации времени обработки всех деталей. Для этого необходимо определить дисперсии времен обработки деталей каждого вида.

Время обработки деталей с дефектом A – случайная величина, распределенная по равномерному закону. Из теории вероятностей известно, что дисперсия такой величины определяется по формуле: D = (b a ) /( 2 3 ), где a и b – границы диапазона значений случайной величины. Таким образом, D A = (5 2) /( 2 3 ) = 0,87.

Время обработки деталей с дефектом B – детерминированная (точно известная) величина. Для таких величин дисперсия равна нулю: DB = 0.

Время обработки деталей с дефектом С – случайная величина, распределенная по гауссовскому закону. Для нее известно стандартное отклонение: = 1,5 мин. Так как дисперсия любой случайной величины представляет собой квадрат ее стандартного отклонения, DC = 1,5 = 2,25.

Найдем коэффициент вариации времени обслуживания всех заявок по формулам (8.36)–(8.39).

Вторые начальные моменты времен обработки деталей каждого вида:

A = DA + x A = 0,87 + 3,5 = 13,12; B = 25; C = 51,25.

Второй начальный момент времени обслуживания всех заявок:

= 0,26·13,12 + 0,53·25 + 0,21·51,25 = 27,42.

Дисперсия времени обслуживания всех заявок: D = 27,42 – 5,03 = 2,12.

= 2,12 / 5,03 = 0,29.

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

В этой СМО = 0,19 детали/мин, x = 5,03 мин, µ = 1/5,03 = 0,2 детали/мин, = 1, = 0,29.

Найдем характеристики СМО, как показано в подразделе 8.7: = 0,95;

P0 = 0,05; q = 9,78 детали; Pотк = 0; Pобсл = 1; U = 0,95; S = 0,95 детали; k = = 10,73 детали; = 0,19 детали/мин; w = 51,5 мин; t = 56,5 мин.

Из полученных характеристик видно, что станок явно перегружен: коэффициент загрузки U = 0,95. Это приводит к скоплению большого количества деталей, ожидающих обработки: в среднем ожидают обработки 9,78 детали. Среднее время пребывания деталей в очереди (т.е. время ожидания обработки) очень велико: оно составляет 51,5 мин, что более чем в 10 раз превышает время самой обработки. Для устранения этих недостатков можно рекомендовать установить еще один станок для ремонта дефектных деталей.

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

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

СМО является одноканальной; нет ограничений на очередь. Другими словами, тип СМО – M/M/1 или M/G/1 без ограничений на очередь.

Приоритеты заявок могут быть относительными или абсолютными.

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

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

Пусть в СМО имеется R значений (уровней) приоритета. Будем обозначать номером 1 высший приоритет, а номером R – низший. Будем обозначать характеристики СМО для заявок с i-м уровнем приоритета индексом, обозначающим приоритет (например, t1 – среднее время пребывания в СМО заявок с первым уровнем приоритета).

Средние характеристики СМО для заявок всех уровней приоритета будем указывать без индексов (например, t – среднее время пребывания в СМО всех заявок).

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

где i – интенсивность потока заявок с i-м уровнем приоритета;

µ i – интенсивность обслуживания заявок с i-м уровнем приоритета, определяемая как µ i = 1 / xi, где xi – среднее время обслуживания заявок с i-м уровнем приоритета.

Нагрузка на СМО, создаваемая всеми заявками, определяется следующим образом:

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

• для заявок с высшим приоритетом (с приоритетом 1):

где j – коэффициент вариации времени обслуживания заявок с j-м уровнем приоритета;

• для заявок с приоритетами 2, 3, …, R:

Для СМО с абсолютными приоритетами средние времена пребывания заявок в очереди рассчитываются по следующим формулам:

• для заявок с высшим приоритетом (с приоритетом 1):

• для заявок с приоритетами 2, 3, …, R:

8.45) Другие характеристики СМО определяются по следующим формулам (для СМО как с относительными, так и с абсолютными приоритетами).

Среднее время пребывания заявки в очереди:

где – интенсивность потока всех заявок в СМО: = 1 + 2 +... + R.

Pi – доля заявок с i-м уровнем приоритета в потоке заявок, поступающих в СМО, Среднее время пребывания заявки в СМО:

Среднее число заявок в СМО:

Среднее число заявок на обслуживании (среднее число занятых каналов):

Среднее число заявок в очереди:

Пропускная способность СМО:

Вероятность простоя СМО:

Коэффициент загрузки СМО:

Пример 8.7. В автоматизированной системе управления технологическим процессом (АСУТП) обрабатываются сигналы трех типов (сигналы A,B,C), поступающие от производственного оборудования. Сигналы типа A поступают в среднем через каждые 2 секунды. Сигналы типа B поступают со средней интенсивностью 3 сигнала в секунду, сигналы типа C – 6 сигналов в секунду. Обработка одного сигнала типа A занимает в среднем 20 мс, сигнала типа B – 50 мс, сигнала типа C – 100 мс. Интервалы времени между сигналами и время обработки сигналов можно считать случайными величинами, распределенными по экспоненциальному закону.

Предлагаются три варианта дисциплины обслуживания сигналов: а) в порядке поступления (дисциплина FIFO); б) с относительными приоритетами;

в) с абсолютными приоритетами. При обслуживании с приоритетами более высокий приоритет должны иметь сигналы, требующие меньшего времени обработки (поэтому высший приоритет будут иметь сигналы A, менее высокий – сигналы B, самый низкий – сигналы C).

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

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

Интенсивности потоков сигналов каждого типа известны: A = 0,5 сигнала/с, B = сигнала/с, C = 6 сигналов/с. Вычислим интенсивность потока всех сигналов:

= A + B + C = 9,5 сигнала/с. Найдем доли сигналов каждого типа в общем потоке = 0,63.

Выполним расчет характеристик АСУТП для различных дисциплин обслуживания.