Дискретно-непрерывная математика (стр. 44 )

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

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

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

Рис. 5.16. Сетевой график с оценками продолжительностей отдельных работ и указанием критического пути.

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

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

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

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

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

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

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

Взаимозаменяемость и ограниченность увеличивают эту вариантность, делают труднее задачу составления наилучшего — оптимального расписания.

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

5.14. Экстремальные перестановки

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

Произвольную п-перестановоку будем обозначать символом

σn = i1, i2, …, ik,…, in ; (5.44)

таким образом, ik (или ik(σn)) - число, стоящее в перестановке σn на k-м (от начала) месте; k(i) (или k(i/σ)) - номер места, которое занимает в перестановке σ число i. В перестановке 2, 4, 1, 3 , например,

i 3= 1, k (3)=4.

Число Р(п) всех возможных различных п-перестановок равно произведению чисел от 1 дo n, называемому п-факториалом и обозначаемому п!= 1·2·3... п.

Действительно, легко доказать справедливость следующего рекурентного соотношения:

Р(п) = Р( п-1)·п, Р(1) = 1, (5.45)

(Рекурентними соотношениями называют формулы для общего члена ип последовательности, если ип можно выразить как функцию некоторого числа l предыдущих членов последовательности ип = f(un-1, un-2, ..., ип-l). Такие последовательности называют также обратными ) откуда и следует, что

Р(п) = п! (5.46)

Доказательство строится по индукции. Справедливость Р(1)= 1 очевидна. Различных п-перестановок с зафиксированным i1, очевидно, столько, сколько можно построить различных перестановок остальных п— 1 элементов в σп, т. е. Р(п— 1). Кроме того, очевидно, что i1 может принимать п значений. Отсюда и следует (5.45).

Число Р(п) быстро растет с возрастанием п (табл. 5.1) - быстрее, чем даже показательная функция ап при любом наперед заданном а (так что п! > ап начиная с какого-то п).

Порядок роста функции Р(п) устанавливает следующая формула

Стирлинга

(5.47)

Таблица 5.1

Значения п!, вычисленые непосредственно (т. е. по формуле (5.46) с последующим округлением) и по формуле Стирлинга (п! =S(n))

Многие практические задачи сводятся к определению некоторой перестановки. Например, как п-перестановка (5.44) может быть представлено распределение п претендентов по п местам: ik здесь — номер претендента, распределенного на k-е место. Как п-перестановка может рассматриваться также решение задачи об очередности последовательного выполнения п (перенумерованных предварительно) работ; ik здесь— номер той работы, которая, согласно решению, будет выполнена k-й по порядку.

2. Задача директора. В приемной в ожидании личной встречи с директором собралось п посетителей. Предварительный опрос позволил выяснить, сколько времени должен уделить директор рассмотрению вопроса каждого посетителя: для i-го посетителя (согласно тому, как мы их перенумеровали) это время обозначим через Тi. Директор, зная, что хотя общее (суммарное) время, которе он уделит всем посетителям, одно и тот же, (независимо от очередности их приема), хотел бы так организовать прием, чтобы посетители находились в приемной в целом как можно меньше. Иными слонами, он хотел бы минимизировать время ожидания посетителей в приемной.

Решением задачи директора, очевидно, будет некоторая п-перестановка чисел

σn = i1, i2, …, ik,…, in , (5.48)

соответствующая очередности приема посетителей.

Обозначим через τk(σn) время ожидания в приемной посетителя ik при очередности приема, который задается перестановкой σп.

Очевидно, что

(5.49)

причем, естественно, предполагается, что директор не делает заметных (не равных 0) перерывов между приемами двух посетителей.

Директор ставит задачу: найти такую перестановку σп, на которой величина

(5.50)

принимает наименьшее значение.

Другими словами, требуется среди всех возможных перестановок σп найти такую, которая минимизирует значение функции F(σn). Последняя фраза — уже почти «математическая» постановка задачи директора: здесь определено множество объектов, среди которых надо искать решение задачи — перестановки (о посетителях и директоре мы уже на время — до решения задачи — забыли). Здесь же указано свойство искомого решения (для него значение F(σn) является минимальным); ранее было определено, как вычислить F(σn) для каждой перестановки.

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

В задачах поиска экстремальной перестановки требуется найти п-перестановку σn, на которой некоторая функция F(σn) достигает экстремума (минимума или максимума в зависимости от постановки задачи, в нашем примере — минимума) и задан способ вычисления F(σn) на каждой перестановке σn.

Функцию, екстремум которой находится в некоторой задаче, называют функцией оптимизации или функцией-критерием.