Файл: Соловейчик, Р. Э. Программирование на АЛГОЛ-60 учеб. пособие.pdf

96

шах

равна нулю,

и

значение lalae

, если эта величина

больше нуля.

Процедура work

1

выполняет симплексное преобразование

матрицы, т.е. выводит из

базиса переменную с номером iO

и

на ее место вводит

переменную с номером

jO

. Кроме того,

отсутствия в

столбце JO

положительного элемента

(не в ну­

левой строке)

происходит выход из процедуры на метку

ш л о

.

что соответствует неограниченности линейной формы снизу.

Процедура f i m обеспечивает вывод номеров базисных переменны!»

Найти минимум линейной формы

0= -х 2 *■ 2x5

при системе

ограничений

х1

-

х2 +

2*3 '

2х4 *

б15 * 2 '

х1 * 2хр -Х3 * 7X4 +

3x5

» 5 i

—x-j +

+ x^ —

^ A t

~

0

( i = 1 . 2 , 3 >4 , 5 )»

Входными параметра!® процедуры

Simplex

будут:.

a[l:3,

1:5]

,

*

[i:^

' c [i-.d ]

(

I

-I 2 - 2 -

6 \

I

2 -1 7

3

(2 5 4)

(О - I 0 .0 2)

\-I

1 1 - 1 0 /

С этими дашшми

переходим к выполнению процедуры.start 1 _ ,

причем рекомендуем читателю непрерывно

сопоставлять

приводи­

мые ниже

вычисления с написанием этой процедуры на АЛГОЛ-60

А [0,о]:= 0,

iter ' :

= 0 „

AfO.Ij

:=0 ,

A

[0 ,2l :=-1 ,

л[о,3] :=0 ,

а [о ,4] :=0

А[0 ,^

А

[1,0]":=2,

А|2,0] :=5,

А [3,<j : =4,

A[2,l]:=I, A[2,2j:=2f

A[2,3]

:=-I, A[2,4j :=7, A[2,5]:=3

A p,lj :=—I , A [3,2]

:=I,

A [3,3] :=I,

A [3,4] :=-I, A [ 3 ,s] :=0

A

[D,lj :=0

+ M. I + M. I +'M(-I) = M

A

p,2] :=-I

+ M

(-1)

+ M2 + MI = -I

+ 2 M

A

p,3]

:=0 + М2

+ M (-1) + MI =

2M '

A

: = 0 + M (-2) + M7 + M (-1) = 4 M

A

[0,| : =

2 + M(-6 ) + М3

+ MO = 2 - 3M

A

p J

: =

0,

A

[1,77 : =0,

A

[ l , 8 ]

:

= 0

A

[I,d : =

I,

• *

base

[ij: = 6

A

[2,|

: =

0,

A

[2,7] :

=

О,

A [2 ,8 ]

: =

0

_

A ]2,f : = I

.

Ъаае

/2J : = 7

А

[З,б] : =0,

A

[3,7f

: =

0,

A [3,8/

: =

0

A [3,8J

: =

I, Ь а а в [ з ] : =8

A

[o,0]

: =

0 + М2 + M5 + M4 = II M

Таким образом, в результате выполнения процедуры

atart 1

мы имеем построенную матрицу

А [О

3,0

: в]

И М

М

2M-I

2М

4М

-ЗМ+2

0

0

0

2

I

-I

2

- 2

-6

I

0

0

5

I

2

-I

7

3

-0

I

•0

4

-I

I

I

-I -

0

0

0

I

и указание на номера базисных переменных

Ъаве jYj

: =

6 , basej2j : =

7, Ьазв[з|

: = 8 .

Процедура

new 1 (opt) использует

эту матрицу и находит

наибольший положительнйй элемент в нулевой ее строке, но не в

нулевом столбце и отмечает номер того столбца, где расположен

этот элемент, и приписывает величине

opt

значение

true

,

если шах =

0

, и

значение

fa lse

, если

пах >

0

,

max

:

=

4 М,

jO

i =

4,

opt

i

= fslae

98

--

Так как величина

opt приняла значение . false -t то

следующей выполняется

процедура

work \ , причем мы опять ре­

Iter

= 0

+ 1 =

1, un5

=

true,

mini =»

M

»

5

mins

5

iOt

=

2,

un: =. falae

a n

=~Т~,

=~1~,

_ 1 _

Ъаае

[ г ]

t =• 4

a i: =«

7

L J

Затем элементы

"ключевой" строки умножаются на

ai

т.е. на

-4—

и

получается матрица

1 Ш

М

2М—I

2М

4М

-ЗМ+2

0

0

0

а I : = 4М

2

I

-I

2

-2

-6

I

0

0

a i : =-2

5

I

2

-I

I

3

0

I

0

7

7

7

7

7

7

4

-I

I

I

-I

0

0

0

I

а ! : = -I

теперь остальные строки матрицы преобразуются'по формуле

a [ i , j ]

at

А

52м

2м

£м- 1

Д м

0

- Д м +2

0

- 4 М ■ 0

7

7

7

7

7

7

24

9

_ 3

12

0

_ 36

I

_

2

0

7

7

7

7

7

_

7

5

I

2

_ I

I

3

0

I

0

7

7

7

7

7

7

33

_ 6

9

6

0

3

’ 0

Г

I

7

7

7

7

7

7

После

этого мы

снова выполняем процедуру

new

л

(o p t)

и если в результате

ее выполнения величина o p t: = _£al_se

то переходим к выполнению процедуры

work i