Лекция 7. ВЕКТОРНО-СЕТЕВЫЕ И ДРУГИЕ МЕТОДЫ РЕШЕНИЯ ИНЖЕНЕРНЫХ ЗАДАЧ

 С О Д Е Р Ж А Н И Е
Введение
1. Основы сетевого планирования
Пример 1. Установить электродвигатель на фундаментной плите.
2. Анализ сети.
3. Типовые процедуры расчета сетевого графика на ЭВМ
Пример 2. Найти оптимальный путь судна из порта р1 в порт р2.
Пример 3. Задача Богданова-Вентцель. Найти маршрут движения объекта из А в Б такой, чтобы расход топлива  был минимальным.
4. Метод безусловной оптимизации Белмана.
5. Решение задач сетевых графиков
Пример 4. Найти критический путь в предложенной сети. 
6. Упражнения
Л и т е р а т у р а


Введение

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

1. Основы сетевого планирования

Деятельность коллектива исполнителей, направленная на достижение поставленной цели, называют операцией.

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

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

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

Каждой вершине графа приписывают число - ее номер.

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

Рис. 1. Конечный ориентированный графСетевая модель представляет  конечномерный ориентированный граф без контуров.

Контур - это путь, в котором начальная вершина совпадает с конечной.

Граф, приведенный на рис.1, содержит контур 1-3-4-1 и, согласно определению, не является сетью.

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

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

Пример 1. Требуется установить электродвигатель на фундаментной плите.

В операцию входят следующие работы:

1) оформление заказа на фундаментальную плиту;
2) изготовление фундаментальной плиты;
3) перевозка плиты;
4) подготовка основания под фундамент;
5) устройство опалубки для фундамента;
6) бетонирование фундамента;
7) твердение бетона;
8) монтаж фундаментной плиты;
9) заказ и получение со склада двигателя;
10) перевозка двигателя;
11) монтаж двигателя.

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

На рис.2 приведена сетевая модель с временными характеристиками работ. Ожидаемая длительность каждой работы указана в днях над каждым ребром сети.
 
Рис. 2 Сетевой график с временными характеристиками работ для установки электродвигателя

2. Анализ сети

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

Наступлением i-го события считается момент, когда завершены все работы, входящие в i-й узел сети. Поэтому событие не наступает до тех пор, пока не завершается последняя из входящих в данный узел работ. Если к рассматриваемому событию ведут несколько путей, то срок наступления события будет определяться продолжительностью пути наибольшей длительности. Так, например, к событию 6 сети (рис.2), ведут два пути: 0,1,2,6 и 0,3,4,5,6. Длительность этих путей равна: 18 и 16 дням.

Очевидно, что событие 6 не может наступить ранее 18 дней и Тe6=18 дней. Находя таким образом значение Тe для каждого, в том числе и для конечного k-го события, можно определить значение Тk - срок завершения операции. Время Тk есть время самого продолжительного пути, ведущего от начального события к конечному. Этот путь называется критическим путем.

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

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

3. Типовые процедуры расчета параметров сетевого графика на ЭВМ

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

Структуру критического пути можно определить, анализируя результаты расчета сети:
1) события, имеющие нулевой резерв времени, лежат на критическом пути;
2) работы, имеющие нулевой полный и свободный резерв времени, лежат на критическом пути;

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

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

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

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

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

Пример 2. Пусть дан сетевой график (рис.3) движений судна из порта p1 в порт p21 через порты p11, p12, p13. Расход топлива и прибыль в зависимости от прохождения того или иного маршрута показаны на ребрах. Вершины графа обозначим как вектора, составляющими (координатами) которых являются: расход топлива, прибыль, номер маршрута.

Возможны три маршрута движения:
1) p1-p11-p21,
2) p1-p12-p21,
3) p1-p13-p21

Выделим каждый маршрут своими номерами точек (начала и концы всех маршрутов совпадают)
Зададим расход, прибыль и номер маршрута в точках-векторах

: p1=0.,0.,    0.    p2=x1, y1,  1.     p3=x1,y1,    2.
: p11=90.,300.,0.   p12=70.,400.,1.   p13=110.,200.,2.
: p21=30.,500.,0.   p22=x21,y21, 1.   p23=x21,y21,  2.

где
х - определяется расход топлива,
y- определяется прибыль,
z - определяет номер маршрута

Выполним расчеты расхода топлива и прибыли по каждому из трех маршрутов
Расход топлива на маршрутах

s1=x1+x11+x21= 120
s2=x2+x12+x22= 90
s3=x3+x13+x23= 110

Выполним сравнения всех трех значений (сначала с эталоном, задаваемым заведомо большим числом (s99=1000.))

s1 < s99 ? s99=s1
s2 < s99 ? s99=s2
s3 < s99 ? s99=s3

Получим наименьший расход топлива по маршрутам равный s99=90.

Аналогично определяем прибыль на маршрутах

s11=y1+y11+y21= 500
s12=y2+y12+y22=700
s13=y3+y13+y23=650

Выполнив сравнения всех трех значений с эталоном (задаваемое сначало заведомо меньшим числом, чем оно может быть (s98=0.)

s11 > s98 ? s98=s11
s12 > s98 ? s98=s12
s13 > s98 ? s98=s13
получим что наибольшая прибыль в s98 и равна  700

Для контроля и наглядности строим графики расхода топлива от варианта движения
 
 
Рис. 4. Графики а) расхода топлива и б) прибыли от номера маршрута судна
 

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

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

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

Рис. 5Пример. 3. Судно из порта р0 в  p55 может двигаться через промежуточные порты (рис. 5) по горизонтальным, вертикальным или диагональным отрезкам. Однозначно перебрать различные варианты маршрутов (особенно когда промежуточных портов десятки и сотни) сложно. Можно двигаться по методу случайных чисел от 1 до 3. Выпало - 1  двигаемся по горизонтали, выпало - 2, по вертикали, 3 - по диагонали. Итак, из одного порта в другой до тех пор, пока судно не придет в конечный порт. По варианту пути следования можно просчитать: пройденный путь, расход топлива, прибыль и т.п. Вначале путь, наверняка, окажется не самым оптимальным. Однако, повторяя движения судно много раз по методу случайных чисел, можно получить маршрут близкий к оптимальному или оптимальный.
 
Рис. 6,а
Рис. 6.б
Рис. 6.с
Рис. 6. а) варианты движения судна и график ЦФ (зависимости расхода топлива от варианта движения), б) фиксация номера варианта движений при минимальном расходе топлива, с) оптимальный путь полученный за 50 итераций (вариантов движения). Рисунки получены при решении задачи в системе "Вектор".

Пусть требуется найти маршрут (рис. 5) движения объекта из точки р0 в точку р55, причем так, чтобы маршрут был самым коротким. Движение точки по клеткам можно задать:

p=(1-v)*((1-u)*p1+u*p2)+v ((1-u)*p3+u*p4)

Изменения переменные u  и v можно фиксировать точки по узлам сетки. Если изменяется параметр u, то перемещение происходит по горизонтали, если изменяется параметр v — по вертикали, а если сразу по u и v, то по диагонали.

Последовательность изменения значений u и v определяется случайным числом (в данном случае из трех): если случайное число равно единице, то меняется параметр u, если равно 2, то - v, если 3 - то одновременно u и v.

При движении объекта из точки А в точку В определяем и длину маршрута. Далее, организовав какое-либо число проходов по маршруту, можно выбрать из них минимальный. Так за 50 итераций в системе “Вектор” получен маршрут (рис. 7,б). Он не оптимален.
 
Рис. 7,а
Рис. 7,б
Рис. 7. Оптимальный маршрут движения объекта из точки А в точку В полученный за 50 итераций.

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



4. Метод безусловной оптимизации Белмана.

На основе метода Белмана вышепоставленная  задача имеет однозначное решение. Метод сводится к процедуре поэтапной оптимизации от конца процесса к его началу. Предполагается, что конечная цель достигнута и ищется оптимальная стратегия на последнем участке, далее ищется оптимальная стратегия на всех предпоследнем (цифры оптимального расхода топлива ставятся в окружности узловых точек) и и т.д. - до начальной точки. Метод удобнее понять на рис. 8,а,б,с. Оптимальная стратегия будет равна 12 единиц.
 
 
 
Рис. 1
 
Рис. 2
 
Рис. 3
 
По методу Богданова- Белмана предлагается оптимизировать путь от конца к началу.
Вопрос. А не измениться ли ситуация, если проводить безусловную оптимизацию не с конца к началу, а от начало к концу? Проверьте это предположение.

Примечание. Метод Белмана и постановка задачи были предложены профессором В.И.Богдановым

5. Решение задач сетевых графиков

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

Пример 4. Дан сетевой график. График содержит 11 событий и 14 работ. Начальное событие (н.с) имеет номер 1, конечное событие (к.с.) - 11. Длительность работ  дана в табл. Найти критический путь.
 
 
 
 
 
 
Таблица 
N работ 
 Код 
начальное
событие
Код
конечное
событие
Длительность работ
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
1
1
1
2
3
4
5
6
7
7
8
9
10
5
2
3
4
6
6
7
8
9
9
10
11
11
9
1
2
3
4
5
6
0
8
4
3
2
1
1
1
 
 Решение задачи

1. Вершины графов (события) обозначим через вектора, в которые в качестве координат будут виды работ. Вектора могут оказаться включающие одну, две и три (вершина 9) работ. Вектора обозначим как pij , где i -номер уровня по горизонтальному направлению, а j - их перечень по вертикали.
2. Осуществляя перебор всевозможных движений по методу случайных чисел, учитывая что движение из одной точки в другую может быть по трем, одному или двум направлениям, а также производя вычисления в зависимости от того по какому пути участку пути было движение, можно найти наиболее оптимальный путь по тому или иному критерию.

Построения графика зависимости того или иного параметра оптимизации от номера маршрута здесь желателен. По нему видно сколько раз достигался max/min и  по количеству сколько раз он достигается можно заключить, что оптимум найден или почти найден.



Упражнения
Упражнение 1. Найти критический путь в сети. Рассчитать резервы времени для событий 4 и 5.  
Рис. 9
Ответ.
а) Критический путь проходит через события: 1,2,3,6,8, его длительность равна 37 дням.
б) Полный резерв времени для события 4 равен 8 дням, для события 5 - равен нулю (событие лежит на критическом пути).

6. Упражнение 2. Определить, изменится ли длительность (см. на рис. 9) выполнения операции, если в  сети:
а) длительность работы 2-5 возрастет до 18 дней;
б) длительность работы 6-8 снизится до 3 дней.
Ответ. а) длительность операции увеличится на 1 день.

Вопрос.
Можно ли решать задачи сетевого планирования по методу Белмана? Проверьте.


Л и т е р а т у р а

Седых В.И., Болотов В.П., Зволинский Н.Т. Векторно-сетевые методы решения инженерных задач. Методическое пособие /электронный справочник/. Владивосток: Двгма, 1994. 40 с.
Лернер А.Я. Начала кибернетики. М., 1967г., 400 с.
Зуховицкий С.И., Радчик А.И. Математические методы сетевого планирования, "Наука", 1965.
Бурков В.Н. и др. Сетевые модели и задачи управления, "Советское радио", 1067.
Райветт П., Акофф Р.Л. Исследование операций, "Мир", 1966.
 

..........................................