Файл: Соловейчик, Р. Э. Программирование на АЛГОЛ-60 учеб. пособие.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.10.2024
Просмотров: 106
Скачиваний: 1
|
|
|
|
|
|
|
|
|
|
90 |
|
|
|
|
|
|
|
|
raaxj= |
|
|
+dij |
Гз] |
= |
0 + |
5 |
* |
5 |
|
ti[4] |
= |
О С 5 |
ti |
[4]. = 5 |
|||
шах»'»« Й |
+aij |
M |
= |
2 + 2 |
» |
4 |
|
ti[4] |
= |
5 7 4 |
|
|
|
|||||
raax»=tl[2] |
+dij |
[5] |
= |
2 + |
6 |
|
8 |
|
ti[6j |
= |
0 < 8 |
ti |
[6]: =8 |
|||||
oa3s=*i [2]t |
|
dij |
[б] |
= |
2 + 5 |
» |
7 |
|
ti[7] |
= |
0 < 7 |
ti |
[?b =7 |
|||||
masts ti [3]+ |
|
dij |
w |
= |
1 + 2 |
= |
3 |
|
ti[4l |
= |
5 7 3 |
|
|
|
||||
max: a ti[3]t |
|
« Ц |
и |
= |
1 + |
7 |
= |
8 |
|
ti[sl |
= |
0< 8 |
ti |
[5 J 5=8 |
||||
maxja ti [4]+ |
|
dij |
[9] |
= |
5 + |
6 = 11 |
|
« Й |
|
= |
В<11 |
ti |
0Ф |
=11 |
||||
maxt= ti [4 ]* |
|
dij [t o ] = |
5 + |
2 = |
|
|
|
|
|
|
|
|||||||
|
7 |
|
ti [б I = |
8 > 7 |
|
|
|
|||||||||||
mexi = ti [5]* |
|
dij [il] |
= 1 1 + 4 |
= 15 |
|
ti[a] |
= |
0<15 |
ti |
М » |
= 15 |
|||||||
maxja ti |
el* |
|
<3131I,] |
= ■ 8 + 2 |
= 10 |
|
ti[7] |
= |
7 < Ю |
ti |
li--= 10 |
|||||||
maxi =.ti |
6] 4 |
dij [13] |
= |
8 + |
7 |
= 15 |
|
ti[a] = |
15=15 |
|
|
|
||||||
maxi-.ti |
Vj4 |
|
a 13 [14] |
= 10 + |
4 = 14 |
|
ti[8] = |
15 >14 |
|
|
|
|||||||
/ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Третьим циклом Присваивается самой поздней дате оконча- |
|||||||||||||||||
ния последнего события самая ранняя дата его окончания |
|
|||||||||||||||||
|
|
|
|
te |
8] |
= ti |
fej |
= |
15 , |
|
|
|
|
|
|
|||
а затем определяются самые поздние даты окончания событий |
||||||||||||||||||
min»= |
tQ м |
|
-a 13 |
[14] |
= 15-4 |
= II |
|
te Й |
= |
и 7 II |
te |
[1> =11 |
||||||
min! = |
te |
и |
-dij |
N= 15-7 |
= |
8 |
|
te [б] |
= |
М > 8 |
te |
[6], |
3 В |
|||||
min:= |
te |
и |
-dij |
N |
= 11-2 = |
9 |
|
te [б] = Р< 9 |
|
|
|
|||||||
rain:= |
te М |
|
-dij |
Cxx] |
= 15-4 |
= II |
|
te [5] |
= |
М > II |
te |
[5] » =11 |
||||||
atn: = |
te [б] |
|
-dij |
N |
= |
8-2 |
= |
6 |
|
te [4] |
= |
м > 6 |
te |
w * |
= 6 |
|||
mins = |
te |
и |
|
|
|
|
|
|
|
|
|
|
|
|
te Г4]: = 5 |
|||
и |
-dij |
(?] |
= 11-6 |
= |
5 |
|
te [4] |
= |
б > 5 |
|||||||||
П)1П;= |
te |
-dij |
[ej |
= 11-7 |
= |
4 |
|
te Й |
= |
М > 4 |
te |
Й ! = 4 |
||||||
mins = |
te W |
|
-dij |
Ы |
= 5-2 = 3 |
|
te [Й |
= |
4 73 |
te |
[з]« = 3 |
|||||||
mint= |
te |
и |
-dij |
[el |
= 11-5 |
= |
6 |
|
te [21 = |
М > 6 |
te- [sj* |
s 6 |
||||||
min: = |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
te м |
|
-dij |
Й |
= |
8—6 |
= |
2 |
|
te й |
= |
6 >2 |
te |
[*h |
=» 2 |
||||
minj = |
te |
W |
w= |
5-2 |
= |
|
|
te |
С2) |
ч |
|
|
|
|
||||
|
|
“ dij |
3 |
|
|
- |
з |
|
|
|
||||||||
|
te |
М |
|
= |
5“5 |
= |
0 |
|
te й |
|
М > 0 |
te |
|
= 0 |
||||
min: = |
|
|
-dij |
[3] |
|
= |
M * |
|||||||||||
—91 " '
min»» |
t e p ] |
-dij [2]= |
3 - |
1 =» 2 |
te |
[lj=. |
0 < 2 |
min» = |
te[2] |
-dij[lj = |
2 - |
2 = 0 |
te |
[l]= |
0= 0 |
Заключительным циклом присваиваются значения всем выход
ным данным.
/
к |
81 Гк] |
в2 [к] |
* м |
£2 М |
•« М |
« |
/*] |
1 |
О |
о |
2 |
2 |
О |
|
о |
2 |
о |
2 |
1 |
8 |
2 |
|
о |
3 |
0 |
0 |
б |
В |
о |
|
о |
4 |
2 |
3 |
4 |
5 |
1 |
|
3 |
S |
2 |
2 |
8 |
8 |
о |
|
о |
6 |
2 |
в |
7 |
11 |
4 |
|
1 |
7 |
1 |
3 |
S |
Б |
2 |
|
2 |
8 |
1 |
4 |
8 |
11 |
3 |
|
3 |
0 |
5 |
В |
11 |
11 |
о |
|
0 |
10 |
в |
6 |
7 |
8 |
1 |
|
1 |
п |
П |
11 |
ш |
15 |
о, ' |
|
о |
12 |
8 |
9 |
10 |
11 |
1 |
|
о |
13 |
8 |
8 |
16 |
16 |
о |
|
о |
14 |
10 |
11 |
14 |
16 |
1 |
|
1 |
Причем, ввиду простоты соответствующих выкладок, мы их опус тили. Так как критический путь проходит по работам с нулевым полным резервом, то в его состав входят работы с номерами I, 3, 5, 9, II и 13. Просмотр этих работ позволяет установить, что в данном случае имеются два критических пути; первый про ходит по работам с номерами I, 5, 13, а второй - по работам
сномерами 3, 9, II.
Взаключение приводится сетевой график, отвечающий рас сматриваемому примеру
92
Решение задачи линейного программирования симплексным методом
Приводимая ниже процедура основана на использовании ис кусственного базиса. Эта процедура значительно сложнее преды дущих, поэтому сначала приведем ее полностью, потом сделаем ряд пояснений, относящихся как ко всей процедуре в целом, так и к отдельным ее частям, и в заключение приведем решение од ной задачи линейного программирования, даваемое описываемой процедурой. Эта процедура взята из лекций цроф. И.В. Романов ского.
ргооеДцге simplex ( m,n,M,a,Ъ,о) * |
|
|
|
|||
integer т,П{ real М; array |
а,Ъ,о; |
|
|
|||
'begin integer ite r, |
jO; array A £ 0»a, |
Of**n| * |
|
|
||
|
integer |
array |
base [ 1 |
* |
1 |
|
propfdere Ы? (start, new.work,fin.unbohlabel unboj |
||||||
begin Boolean |
opt; |
start |
; |
|
|
|
е ц new (opt); |
i f opt |
then go to |
e2; work; |
go |
to ei; |
|
|
|
|
|
|
93 - |
|
|
|
e2 i fin end |
ЕР ; |
|
|
|
|
|
||
procedure |
start i |
| |
|
|
|
|
||
begin |
integer |
i , j |
f |
A J"o.G~j s a |
Oj iteri |
з |
0 ; |
|
for |
jj = 1: |
atep |
\ |
until n do |
А j Ofjl |
«= |
c [ j j » |
|
|
for |
is |
* |
1 |
etep' .1 |
|
until |
|
m |
do |
|
|
|
|
|
|
|||||||
begin |
A ^ i , |
cl |
i |
з Ъ [ i ] |
; |
|
|
|
|
|
|
|
|
|
|
||||||||
|
for |
J t з |
1 |
step 4 |
|
until |
|
n |
|
do |
|
|
|
|
|
|
|||||||
|
begin |
A |
[ i, |
jj |
|
t * |
|
a [ t » ® |
|
t |
H |
* |
|
|
г »Гт |
|
|||||||
|
|
|
|
A [0, |
j |
|
t |
=» |
A |
[0 , 1 ] |
|
♦ |
4 |
|
1! |
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
do |
|||
|
for |
J; = |
n T |
l |
etep j |
until |
n ■» |
m |
|
|
|||||||||||||
|
A fi,j| t* |
0» |
A^i,nflJ |
|з |
15 |
base [ljt |
з |
irf-i l |
|||||||||||||||
|
A [G,oj «» |
|
|
0j * |
И * A |
£l,(^ |
! 5 § |
|
1 |
? |
|
|
|||||||||||
for |
it |
n |
u + 1 |
ste£ |
t |
until |
|
n + |
m |
do |
|
|
|
|
|||||||||
|
A |
jo,j| |
5 = |
0 |
end |
start |
t |
|
|
|
|
|
|
|
|||||||||
p ro o e d u r e |
new |
1 |
( c p t ) f |
|
|
B o o le a n |
opt |
j |
|
|
|
|
|
|
|||||||||
b e g i n i n t e g e r |
j |
t |
, r e a l |
|
tpax |
; |
|
|
|
|
3 |
0 |
; |
|
|
|
|
|
|||||
f o r ] t » 1 b te p i |
u n t i l |
n |
|
do |
|
|
|
|
|
|
|
||||||||||||
. |
i f |
A |
f o . j/ |
> |
|
« a x |
|
than. |
|
|
|
|
|
|
|
|
|
|
|||||
j |
begin max .» =« |
A [o ,jJ |
* |
|
i |
0 |
* |
* |
J |
|
5 ЙЙ * |
|
|||||||||||
|
opts |
з |
шах з |
0 |
end |
new |
; |
|
|
|
|
|
|
|
|
||||||||
p ro o e d u re |
w ork |
1 |
; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
begin integer |
|
i .jJ O , |
|
real |
min, |
a lt |
Boolean |
un , |
|||||||||||||||
|
ite r: |
з |
iter |
♦ |
1; |
|
unt |
з |
|
true; |
mint |
з |
И ; |
|
|||||||||
|
for 1; |
= |
i |
step 1 |
|
until, |
|
-.m |
|
do |
|
|
^ |
|
|
||||||||
|
|
i f |
A |
(l,jq J > |
0 |
|
then |
|
|
|
|
|
|
|
|
|
|
||||||
begin |
|
el t |
з |
a |
|
£i*oj |
/ |
A |
|
|^i,j0j |
l |
|
|
|
|
||||||||
|
|
i f |
un |
V |
®in > |
|
al |
|
then |
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
94 |
|
|
|
|
|
begin |
ain |
: = at |
5 |
iOi = |
1 » |
uni =« false end |
||||
end |
|
|
|
|
|
|
|
|
|
|
|
If |
un |
|
then go |
to |
unbo; |
base |
[to] i = jO ; |
||||
ai i |
= i |
/ |
A |TlO, |
joj |
( |
|
|
|
|||
for |
3 t |
=» |
1 |
step |
1 |
until |
a + |
n |
do |
||
|
A [lO .jj |
t = |
A |
[ i O j ] |
* |
a1 |
; |
||||
|
for |
1: = |
0 step |
1 |
until |
10 - 1 ,1 0 + |
1 . step 1 until |
||||||||||
|
begin |
a1 : a A |
r |
|
7 |
» |
|
|
|
|
m |
do |
; |
||||
|
£l,;JOf |
|
|
|
|
|
|
|
|||||||||
|
|
for |
ji |
a |
0 |
step |
i until |
m |
t-n |
do |
|
|
|||||
|
|
A [i.jj |
:= |
A ji,j] |
- ai |
* A |iO,jJ |
ends |
endwork* |
|||||||||
procedure |
fin |
i |
j |
|
|
|
|
|
|
|
|
|
|
|
|
||
begin |
Integer |
|
1, |
j ; real ai ; |
|
|
|
|
|
|
|
||||||
|
for |
1 i |
a |
|
1 |
step |
1 |
until |
m |
do |
|
|
|
||||
|
begin |
|
at |
i * |
0 |
; |
|
|
|
|
|
|
|
|
|||
|
|
for |
j |
i |
=» |
1 |
step t |
until m |
do |
|
|
|
|||||
|
|
|
afi |
= |
e{ |
* a £ 1, |
base |
|
[ j ]J |
x A |
pj,oJ ; |
||||||
.ВЫВОД |
( base |
j i j |
, |
A |
£ l,o ],0 t,b |
[lj, A [o,n+l| |
+M) |
end |
|||||||||
end ' fin |
* • |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ЬР ( start 1 , new |
t , work t , |
fin |
1 , |
unbo ) |
; |
|
|
||||||||||
ко |
to |
e3; |
unboj |
вывод |
|
(jO, |
A [ 0,jO j); |
fin |
t ; |
||||||||
e3i end simplex
95
Итцк, входными параметрами к процедуре staple* яв ляется:
- матрица коэффициентов системы ограничений задачи ли нейного программирования, представленных в виде равенств, раз мерами m * п ;
-вектор-столбец правых частей упомннутой системы ог раничений;
-вектор-строка коэффициентов линейной формы задачи ли
нейного |
программирования, причем рассматриваемая линейная фор |
||
ма должна не содержать свободного члена; |
|
|
|
- |
некоторая очень большая величина М |
(например, 10^)'. |
|
В эту процедуру входит процедура |
ь р |
с формальными |
|
параметрами эta r t,new,work, fin и unbo |
|
, из которых |
|
первые четыре, в свою очередь, являются процедурами, а послед
ний - |
это метка. Суть этой процедуры заключается в том, |
что |
|
||||||||||||
с помощью булевской величины |
|
0pt |
, процедуры |
start- |
и двух |
|
|||||||||
меток |
е% |
и |
е2 |
она делает следующее. Если |
opt |
|
имеет |
|
|||||||
значение |
true |
s то переход к метке |
е г |
|
обеспечивает |
|
|||||||||
выполнение процедуры |
fin |
и |
этим заканчивается процедура IP |
|
|||||||||||
В противном случае, т.е. если |
opt |
|
имеет |
значение |
false |
, |
|||||||||
выполняется процедура |
work |
|
, а затем осуществляется пере |
|
|||||||||||
ход к метке' е1 |
. Теперь поясним процедуры |
start |
, |
new |
, |
||||||||||
work |
и |
±in |
* которые входят в процедуру |
|
цр |
и |
заменя |
|
|||||||
ются в дальнейшем фактическими параметрами start |
1 , |
new 1 |
, |
||||||||||||
work 1 |
и |
fin 1 |
• Процедура |
start |
1 |
заключается в построе |
|||||||||
ний расширенной и дополненной матрицы системы ограничений |
|
||||||||||||||
(расширенной - за счет добавления строки, отвечающей линейной |
|
||||||||||||||
формеди дополненной - за счет столбца свободных членов), при |
|
||||||||||||||
чем из строки, отвечающей линейной форме, исключены искусст |
|
||||||||||||||
венные переменные. Кроме того, |
процедура start |
1 |
фиксирует |
|
|||||||||||
номера базисных неизвестных. |
|
|
|
|
|
|
|
|
|
|
|||||
|
Процедура |
new 1 |
(opt) |
|
находит наибольший положи |
|
|||||||||
тельный элемент нулевой строки (не принимая во внимание эле |
|
||||||||||||||
мента этой строки, стоящего в столбце |
свободных членов), |
но |
|
||||||||||||
мерстолбца |
( 3 0 ) |
, в котором он находится и приписывает |
|
||||||||||||
величине |
opt |
значение |
true |
t если величина находимого |
|
||||||||||