Практика 7. ВЕКТОРНО-ГРАФИЧЕСКИЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ СЕТЕВОГО  ПЛАНИРОВАНИЯ

Содержание
Теоретические положения.
Упражнение 1.  Определить критический путь (наименьших трудозатрат) в предлагаемом графе.
Контрольные вопросы.
Упражнение 2.   Найти оптимальный путь судна из порта р1 в порт р2.  Судно имеет возможность зайти в порты р11-р13.
Контрольные вопросы.
Упражнение 3. Транспортная задача. Найти оптмальный маршрут судна. Решаем в три этапа.
Упражнение 3.1.  Сформировать сетку (точки в портах захода).
Упражнение 3.2.  Создать алгоритм движение точек  по сетке по методу случайных чисел.
Упражнение 3.3.  Задать движение точек  по сетке по методу случайных чисел.
Упражнение 3.4.  И наконец, найти маршрут такого движения объекта такой, чтобы расход топлива для двигателей был минимальным (см. постановку задачи).
Контрольные вопросы.
Упражнение 4. Решить задачу упр. 3 на основе безусловной оптимизации Белмана.


 

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

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

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

Для формализовать перебор возможных решений можно воспользоваться просто перебором всех путей или методом случайных чисел.

Упражнение 1. Определить критический путь (наименьших трудозатрат) в предлагаемом графе
 

gsd.mac  - МК формализации и задания данных
print$on  $ включить печать
$ формализуем нулевой путь, третья координата трудозатраты (в часах)
: p1=50.,50.,0. p2=100.0,0.,5.  p3=150.,0.,23.
: p4=200.,0.,18. p5=200.,50.,5. p6=250.,50.,30.
$ первый путь (трудозатраты также в z), совпадающие точки берем из предыдущего пути
: p11=p1         p12=p2          p13=p3
: p14=x3,y3,0.   p15=x5,y5,1.0  p16=p6
$ второй путь
: p21=p1           p22=100.,50.,24.    p23=150.,50.,2.
: p24=x23,y23,0.   p25=200.,50.,18.     p26=p6
$ третий путь
: p31=p1          p32=x2,100.,20. p33=x3,y32,11.
: p34=x3,y32,0.   p35=x5,y32,10.  p36=x6,y6,27.
$ четвертый путь
: p41=p1         p42=p32  p43=x3,50.,4.
: p44=x43,y43,0.   p45=150.,50.,18.0  p46=x6,y6,30.
uzli: n1=1 n2=2 n3=3 n4=4 n5=5 n6=6 $ к МК построение вершин  графа
s99 =1000.0   $ начальное значение эталона при поиске минимума
s98=0.            $ начальное значение при поиске максимума
p103=x1,s99   $ нач.точка графика зависимости затрат времени от маршрута
gseti: n9=1       $ к программе вычислений
exit  $ выход (для тех, кто забывает ввести последнюю строчку)

gseti.mac - вычисление трудозатрат по путям и выбор пути наименьших трудозатрат
n9 > 5 ? exit  $ вычисление трудозатрат в зависисмости от пути
uzli                            $ к МК построение вершин графа
otrezok: p101=pn1 p102=pn2 $ построения первого участка пути
otrezok: p101= pn3                 $ второго (p102 уже задана выше)
otrezok: p102=pn4                  $ третьего
otrezok: p101=pn5                  $ четвертого
otrezok: p102=pn6                  $ пятого
s1=zn1+zn2+zn3+zn4+zn5+zn6  $ вычисляем суммарные трудозатраты
s1 < s99 ? s99=s1   $ выбрать наименьшие трудозатраты в s99
s1 >  s98 ? s98=s1  $ наибольшие в s98
otrezok: p101=p103 x102=n9*50  y102=s1 $ построение графика ЦФ
p103=p102         $ конец текущего отрезка в начало следующего
n50=s99              $ минимум трудозатрат переводим в целое
$ n50 < 59 ? exit $ условие выхода при достижении минимума
pauser    $ пауза, чтобы продолжить работу МК, нажать на enter
27  $  удалить предыдущий вид пути.
:n1=n1+10 n2=n2+10 n3=n3+10 n4=n4+10 n5=n5+10 n6=n6+10 $ счет-чики
gseti: n9=n9+1  $ рекурсия
 
uzli.mac  $ вспомогательная МК для построения узловых точек в графе
okr: p100=pn1 s100=5.0
okr: p100=pn2
okr: p100=pn3
okr: p100=pn4
okr: p100=pn5
okr: p100=pn6

Перебор путей в МК происходит снизу, поэтому по ЦФ видно, что второй путь самый критический.



Контрольные вопросы.
1. Скажите чему будут равны трудозатраты по первому, второму пути?
2. В какой переменной идет расчет трудозатрат?
3. В какой переменной будет минимум трудозатрат?
4. Что является аргументом  ЦФ?
5. В какой переменной вычисляется  ЦФ?


 Упражнение 2. Найти оптимальный путь судна из порта р1 в порт р21.  Судно имеет возможность зайти в порты р11-р13. Известен расход топлива при переходе из одного порта в другой. Известна и прибыль, которую бы судно получило при обеспечении перевозки груза из одного порта в другой.
 
Решение. Необходимо через вектора задать расход топлива, прибыль и номер варианта маршрута. В вектора (в их регистры х,y,z) поместим: в х- расход топлива, в y -прибыль, в z -номер маршрута.

date.mac
: 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.

Задача двухкритериальная: один параметр (расход топлива) стремится к мin, другой (прибыль)- к мах. Оба параметра зависят от одной переменной - номера маршрута. Решение задачи возможно через МК <tesgr1>

tesgr1.mac - МК  о расходе топлива и прибыли.
$ расход определяется координатой  х,
$ прибыль определяется координатой y,
$ номер маршрута - координатой z:
: p1= 0.,0.,    0.    p2=0., 0.,   1.    p3= 0.,0.,  2.
: p11=90.,300., 0.   p12=70.,400., 1.   p13=40.,200., 2.
: p21=30.,200., 0.   p22=20.,300., 1.   p23=70.,450., 2.
$ Производим начальные расчеты (для построения графика ЦФ)
:  p99=0., (x1+x11+x21)/10.       p98=0.,(y1+y11+y21)/10.
$  зададим сначала в s91 заведомо большее число, где
$ в дальнейшем будет находится  наименьший расход топлива
:s91=1000.
$ зададим s92 заведомо меньшее число, где будет находится наибольша прибыль
:s92=0.
$ n9-счетчик маршрутов, n1,n11,n21-номера портов
tesgr2:  n9=0  n1=1 n11=11 n21=21   $ расчет по различным маршрутам
tesgr2.mac
n9 2 ? exit              $ условие выхода из рекурсии
s1=xn1+xn11+xn21           $ расход топлива по маршрутам
s1 < s91 ? s91=s1          $ минимум расхода топлива в s91
s=n9*50                    $ перевод n9 в вещественное число и масштабирование
otrezok: p101=p99 p102=s,s1/10.  $ график расхода т. от номера движения
p99=p102                   $ запомнить конец отрезка
s11=yn1+yn11+yn21          $ прибыль по маршрутам
s11 s92 ? s92=s11        $ максимум прибыли в s92
s=n9*50                    $ перевод n9 в вещественное число и мастабирование
otrezok: p101=p98 p102=s,s11/10. $ график прибыли от номера движения
p98=p102                   $ запомнить конец отрезка
tesgr2: n1=n1+1 n11=n11+1 n21=n21+1 n9=n9+1   $ рекурсия
 
 
Графики ЦФ.

Контрольные вопросы.
1. Скажите чему будут равны трудозатраты по первому, второму пути?
2. В какой переменной идет расчет трудозатрат?
3. В какой переменной будет минимум трудозатрат?
4. Что является аргументом  ЦФ?
5. В какой переменной вычисляется  ЦФ?


Упражнение 3. Задача Богданов-Вентцель. Необходимо найти маршрут такого движения объекта из точки А (нижняя слева) в точку В (верхняя справа), чтобы расход топлива для двигателей был минимальным. Движение возможно в каждой клетке по вертикали, горизонтали или диагонали. Расход топлива в условных единицах дан на ребрах графа.
 

Решим задачу в три этапа: 1) задание сетки, 2) задание движения точки по сетке и 3) при движении точки по узлам сетки, выполнить расчет расхода топлива в зависимости от ребра по которому движемся.

Упражнение 3. 1. Формирование сетки (точек в узлах).
Задача решается с помощью задания исходных данных date.mac и двух циклов tset1.mac и tset2.mac

date.mac - тест
: p181=50.,15. p182=270.,15.
: p183=50.,150. p184=270.,150.
tet1.mac
tset1.mac
s101 1.001 ? exit
p185=(1.-s101)*p181+s101*p183
p186=(1.-s101)*p182+s101*p184
tset2: s102=0.
tset1: s101=s101+0.2
tset2.mac
s102 1.001 ? exit
p180=(1.0-s102)*p185+s102*p186
okr: p100=p180 s100=2.0
tset2: s102=s102+0.2



Упражнение 3. 2. Алгоритм движение точек  по сетке по методу случайных чисел
 

testb.mac - тест движения точки по методу случайных чисел
: p=50., 50.   p1=100.,50. p10=50.,100. p11=100.,100.
_Случайное_число_(в_n191)_от_ 00001 00004
n191 < 1 ? p100=p1
n191 < 2 ? p100=p10
n191 < 3 ? p100=p11
otrezok : p101=p p102=p100



 
Упражнение 3. 3. Формирование движение точек  по сетке по методу случайных чисел.  
 

bset0.mac МК движения точек по сетке (горизонтали, вертикали,
$ диагонали) по методу случайных чисел
: p181=50.,15.       p184=270.,150.
: p182=x184, y181  p183=x181, y184
bset1: s1=0. s2=0. p111=p181
tset1: s101=0. s102=0. $  построение точек в узлах сетки

bset1.mac
$ различныке варианты движения точек от р181 к р184
n1 > 5 ? exit
27            $ удаление визуализации
bset2: n2=0 s1=0. s2=0. p111=p181
pauser
bset1: n1=n1+1

bset2.mac - расчет точек и ее изображения в прямоугольнике в зависимости от s1 и s2
n2 > 25 ? exit
p185=(1.-s1)*p181+s1*p183
p186=(1.-s1)*p182+s1*p184
p190=(1.0-s2)*p185+s2*p186
okr: p100=p190 s100=4.0
otrezok: p101=p111 p102=p190
p111=p102
_Случайное_число_(в_n191)_от_ 1  4  $ команда
n191 <> 1 ? s1=s1+0.2
n191 <> 2 ? s2=s2+0.2
n191 <> 3 ? s1=s1+0.2
n191 <> 3 ? s2=s2+0.2
s1 > 1.01 ? s1=1.
s2 > 1.01 ? s2=1.
bset2: n2=n2+1


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

bgd0.mac - расчет оптимального маршрута, минимизируя расход топлива.
$  print$on
$ msg$off - выключить вывод расчетов
:p0 =0.,0.,0. p1 =2.,0.,0. p2=6.,0.,0.   p3 =6.,0.,0.   p4 =1.,0.,0.   p5=5.,0.,0.
:p10=0.,9.,0. p11=2.,3.,1. p12=7.,9.,8. p13=3.,5.,4. p14=14.,3.,2.     p15=1.,4.,3.
:p20=0.,8.,0. p21=6.,4.,5. p22=1.,6.,12. p23=10.,2.,11.  p24=12.,2.,13. p25=8.,5.,6.
:p30=0.,2.,0. p31=10.,3.,2. p32=7.,2.,3.  p33=6.,9.,8.   p34=1.,10.,9.   p35=9.,7.,10.
:p40=0.,4.,0. p41=6.,9.,8. p42=4.,3.,5.  p43=4.,7.,5.   p44=1.,7.,5.   p45=7.,8.,6.
:p50=0.,3.,0. p51=4.,7.,5. p52=3.,1.,2.  p53=6.,2.,7.  p54=2.,4.,3.   p55=3.,5.,12.
: p71=50.,10. p72=250.,10. p73=50.,150. p74=250.,150. p111=p71
bgd1: n=0 s99=1000.1  n1=0  p112=0.,90. n2=1 n3=10
tset1: s101=0. s102=0. p181=p71 p182=p72 p183=p73 p184=p74  - узлы сетки

bgd1.mac
n6 > 25 ? exit
27
bgd2: n5=0 p111=p71  s1=0. s2=0. s7=0. n1=0 s8=0.n2=1 n3=10
pauser   $ пауза, чтоб продолжить работу МК нажать на любую клавишу
s8 < s99 ? s99=s8    $ минимальный расход топлива (s8 - рассчитывается в bgd2.mac)
s21=n6     $  номер маршрута переводится в вещественное для абсциссы ЦФ
otrezok: p101=p112 p102=s21*5.,s8    $ график ЦФ
p112=p102          $ конец в начало
n50=s99               $ минимум в целое
$ n50 <> 19 ? exit   $     - условие выхода при достижении минимума
bgd1: n6=n6+1
 

bgd2.mac
n5 > 15 ? exit
s1 > 1.-0.001 ? n2=0
s2 > 1.-0.001 ? n3=0
p91=(1.-s1)*p71+s1*p73
p92=(1.-s1)*p72+s1*p74
p90=(1.-s2)*p91+s2*p92
otrezok: p101=p111 p102=p90
p111=p90
_Случайное_число_(в_n191)_от_ 1  4
n191 <> 1 ? s1=s1+0.2
n191 <> 2 ? s2=s2+0.2
n191 <> 3 ? s1=s1+0.2
n191 <> 3 ? s2=s2+0.2

n191 <> 1  ? n1=n1+n2
n191 <> 2  ? n1=n1+n3
n191 <> 3  ? n1=n1+n2+n3

n2 <> 0 ! n3 <> 0 ? goto met
n191 <> 1 ? s8=s8+xn1
n191 <> 2 ? s8=s8+yn1
n191 <> 3 ? s8=s8+zn1
goto vet
$met
n2 <> 0 & ^(n3 <> 0) ? s8=s8+yn1
n3 <> 0 & ^(n2 <> 0) ? s8=s8+xn1
$vet
s1 > 1.0-0.01  ? s1=1.0
s2 > 1.0-0.01  ? s2=1.0
bgd2: n5=n5+1
 
Из 50 вариантов движения найден путь, который по расходу топлива минимальный. Однако однозначно сказать, что он самый минимальный нельзя (расчет шел по методу случайных чисел).



Контрольные вопросы.
1. Скажите чему будут равны трудозатраты по первому, второму пути?
2. В какой переменной идет расчет трудозатрат?
3. В какой переменной будет минимум трудозатрат?
4. Что является аргументом  ЦФ?
5. В какой переменной вычисляется  ЦФ?



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

Рис. 1

Рис. 2

Рис. 3
 

Решение поставленной задачи в упр. 3 в системе “Вектор” по методу Богданов-Белман см. в уроке 7.