Найденные значения клеток позволяют провести исследование свободных мест. Его  целью является выявление отрицательных  свободных мест. Если U_i + V_j меньше соответствующего значения расстояния (в клетке на пересечении i-й строки и j-го столбца), взятого с обратным знаком, то свободное место (i, j) отрицательно и решение может быть улучшено.

А3: 0-1>-6

Б2: 7-5>-2

Б3: 7-1>-1

Б4: 7-4>-4

В1: 6-4>-6

В2: 6-5>-7

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

Задача 2.

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

Выполнение.

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

       Для определения основных показателей  работы АТС необходимо рассчитать  значение поступающей нагрузки в Эрлангах Ψ и вероятности, что из n-линий k будет занято

     Для расчета используются формулы: 

 

     Далее следует определить вероятность  отказа Р_отказа , среднее число занятых и среднее число свободных линий, коэффициенты занятости и простоя линий и сделать вывод о качестве обслуживания абонентов и эффективности использования линий связи.

     Определим значение нагрузки:

= 2·1=2

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

Вероятность того, что все линии будут свободны, составляет 13,7%

Теперь рассчитаем вероятность занятости k линий из n, применив формулу:

Рассчитаем:

k=1,

k=2,

k=3, =0,184

k=4,

k=5,

То есть, соответственно, 28%, снова 28%, 18,4%, 9,4%, 3,9%.

Найдем вероятность  того, что все линии связи будут  заняты (то есть, DoS), применив формулу 

Вероятность отказа в обслуживании  3,6%. Вероятность DoS, как видно из структуры формулы, катастрофически падает при увеличении числа каналов.

Рассчитаем среднее  число занятых линий по формуле 

Среднее число  занятых линий равно 1,98

Коэффициент занятости 

Определим теперь число свободных линий:

Среднее число  свободных линий 3,299, коэффициент  простоя   

Либо  можно определить логически, сумма  коэффициента простоя и коэффициента занятости должна быть равна 1, то есть 1-0,396=0,604.

Вывод:

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

Задача 3.

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

Решение.

Данная  задача относится к «задаче коммивояжера». Коммивояжеру необходимо пройти через все точки замкнутого графа и вернуться в исходную точку маршрута.

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

      Обозначим за Г множество всех обходов почтальона (т. е. всех простых ориентированных остовных циклов). Поскольку граф – полный, это множество заведомо не пусто. Сопоставим ему число φ(Г), которое будет играть роль значения на этом множестве оценочной функции: это число равно сумме констант приведения данной матрицы весов дуг графа и является оценкой снизу для стоимости минимального тура коммивояжёра. Приведённую матрицу весов данного графа следует запомнить, обозначим ее через С₁.

     Подсчитаем  φ(Г). Для этого выполним приведение матрицы весов.

Сначала – по строкам:

Обнуляем и вычитаем:

По столбцам:

Обнулим:

Сумма констант приведения 4+9+5+4+7+8+2=39

     Обозначим полученную матрицу через С₁ и найдём в ней самый тяжёлый нуль. Заметим, что замена нулевого элемента на ¥ приводит к изменению лишь двух слагаемых суммы констант приведения φ(Г) – по одному при приведении строк и столбцов. Поэтому вес нуля можно определить суммированием наименьших элементов его строки и столбца.

     Итак, запишем приведённую матрицу  еще раз, указывая рядом с каждым нулем его вес: