Файл: Математическое программирование и производственные задачи..pdf

ответствующее

подозрительной строке. Численное значение

X в выражении

(4.6) выбираем так, чтобы коэффициент при

ся единице.

Это требование выполняется,

если

а и\,-

(4.7)

Приращение

целевой функции

х }

о 2

ajkx J>n

(4.9)

еде

О,

если

jk=hj,

- 1 ,

если

j k= j .

Если в базис входит вектор, добавленный на некотором

шаге, то соответствующая строка исключается из

системы

мым от остальных.

Если А=а,7 0

= 1,

то добавленная

переменная sk+\ = 0.

В этом

случае в

качестве условия

(4.6)

выбирается г'-ая

строка.

Основная

симплексная таблица

имеет размеры

при этом генеральный элемент равен

единице,

вследстбйе

чего полученная

после преобразований

симплексная

табли­

ца тоже будет целочисленной.

Введем следующие обозначения:

а+ У (я+3)+/

номер ячейки

памяти

ЭВМ,

хранящей

элемент а,, симплексной таблицы;

-► —знак засылки содержимого

одной ячейки

в дру­

гую;

< Д >

-содержимое ячейки Д;

t,

k,

k!—счетчики;

j 0,

t0—ячейки запоминания номеров генерального столб­

ца и подозрительной строки;

<*-}-_/, P-И , с~И, Д -рабочие ячейки.

Приведем

вычислительную

схему

решения

задачи

(4.1,) -(4 .4 ') .

1°. Нахождение mln<^a -1-У(« Ч-З)—1>->-Д;

соответствующий

j -У/о-

2<j<n

2°. Сравнение <]Д^> с 0:

а) если <Х><С0. переход к 7°;

б) если < Д > > 0 ,

переход к 3°.

3°. Сравнение <C?-f-«-r2> с 0:

а)

если < у * + « + 2 > = 0 ,>переход

к 4°;

б)

если

<a-r«+2>=/L0,

останов

1;

задача

(4.1)

(4.4)

неразрешима.

4°.

Нахождение

min

+

У (я + 3 ) -2 >

> 4 ;

соответствую-

—1>« О

щнй y'-v/o-

5°. Сравнение

< Д >

с 0:

а) если. < А > > 0 ,

переход

к 6°;

б)

если

< Л > < 0 ,

переход

к 7°.

6’ . Выдача < а + / >

(1

7

п)

останов 2,

задача

(4.1)

(4.4)

решена.

7°,

Нахождение

< а + (< у 0>

- 1)(я + 3 )+ / > > 0

(с запомина­

нием номеров

соответствующих

строк

в

ячейках

с -f t\.

8°, Сравнение /г с 0:

а) если £ = 0 ,

останов 3;

целевая

функция

не

ограничена

(задача

неразрешима);

б) если

к > 0,

переход k

9°.

9°., Формирование холостого хода в 16°.

10°.

1 -> t.

11°.

Составление

отношения

<Са + <Сс +

с >

________

< « + ( < У > - 1 ) ( я - + - 3 ) - г < с + / > >

►3 = с

12°. Сравнение < £ >

с к-

а)

если < Г > < д £ ,

переход

к

13°,

б)

если < 7 > = £ ,

переход к

14°.

13°.

переход к 1Г.

14°.

Нахождение

m

i n 0 + Г >

(с

запоминанием номеров

равных минимумов в ячейках c + t ,

!< £ < £ '< £ ).

15°.

Сравнение k'

с

1:

а)

если k'= \ ,

переход к 32°;

‘

б) если &'>1, переход к 16°.

16°. Холостой ход (переход к 22°).

17°. <A+/>-voc+y(ffl+3),

j = l ,

2, . .

т .

18°. Расстановка <yx-f-y(«-j-3)> по возрастанию (у=1, 2

19°.

\->j.

20°.

1 -> t.

21°.

Сравнение < Х >

с

т\

а)

если < 7

> <у?г, переход к 22°;

б)

если < у > —"С переход

к 24°.

22°. Сравнение <У+У’(я+3)>с<у?+ Г>:

а)

если

<Ca+y(rt+ 3 ) > « C

r ^ ,

переход

к 26°;

б)

если < я + / (л + 3 )> > < с --М > ,

переход к 23°.

23°. Сравнение < С >

с k'\

а)

если <С ><Ж . переход к 25°;

б)

если < Х > = & ', переход к 24°.

24°. < t+ C >

переход

к 32°.

25°. <Х >+1->-С

переход к 22°

26°. 1 - y l .

27°. Сравнение < а + у '(« + 3 )> с

</г ~С>:

а)

если < а+/(и -(-3)>=< У г+ С >,

переход

к 29°;

б)

если <а+у(/г+3)>=У=<А-Ь/>, переход

к 28°.

28°. < / > + 1

>-/,

переход

к 27°.

29°. Замена адреса 0 + < с + Г > >

на <а+/(/г f 3 ) + < с + < » .

30°. < у > + 1 >У.

З Г . Формирование перехода

к 22°

от

16°, переход к

11°.,

32°. Сравнение < а + « У 0>

П (/г+3)+<г0»

с

1:

а) если < я +

« /

0> — 1 ) ( я - г З ) + < г ' 0»

= = 1 , переход х 3 4 р ;

б)

если

< а

К < у 0>

-1)(/1+3)+< г'0» ¥ = 1 ,

переход к

33°.

33°. (/Н-3) >/z+<y0> , переход

к 36°.

34е. <г'р> ^ h + < j 0> .

yy.-+-j(n-*-3) (у = 1,

35°. <у*4~(У - 1)(/г+3)+<У'(С>У>

2, .

■,т)

переход

к 37°.

36°.

<а-!-(у

1 )(/г+ 3 )+ < /0»

|

>'■> /'(/г-гЗ)

< а Ь(<Уо> - 1 ) ( л + 3 ) + < / о » |

(У‘= 1 , 2, . .

от).

37°. Реализация

симплекс-преобразования:

- 1)(/г~ЬЗ)-|-С>

<a+y(/7.+3)>X <a j-

Н~(<Уо> —■1 )(п+ 3 ) + t>

уу--г (/—1)(п+ 3 ) - {-i ;

О—< яФ « У о > —1)(/г+ 3 )ф 7 >

уу-~Г(<Уо> -1)(Л +-3)+С

г —1, 2,

. .

/г+2,

у—1,

2, . .

у'0— 1, у'0+ 1 , . .

m-f-1,

переход к 1°.

Замечание 4.1. В машинах, имеющих индексные регистры,

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

блоки

12° и

от блоков 17°—31°,

но это осложняет вычислительную схему..

Замечание 4.3.

В ячейках

2, . . ., т) с самого-

приписывается

один и тот

же номер— (я + З).

Замечание 4.5. Для полноты программы необходимо пе­

ред блоком Г

иметь блок

вычисления элементов (я + 2 )-ой

строки:

О—V

а,7 - ►?.+ (/—l)(«-f-3)— 1, j - 1, 2, . . ., m4 1,

<■-

i

Л',—х ,

2х3— 2л'4 — 6х5 = 2,

х\-12х2—х 3-\-7х\ 4- Зх, = 5,

—х;+л-2+ х 3—х 4' = 4,

х\~5?0,

Л'2>0, Xj>-0, х ’> 0 . A'-Si-O,

при условиях

х 4— 2

(х4

xs-|-2xg

2х7

6х 8),

Хд—-5

(х4—{—2х-

х 6-• 7х 7+ З х 8),

х3= 4 —(—х 4+ х 5+ х в—х,4-0 ■х 8),

ху—целые неотрицательные (у'=1, 2, . .

8).

Добавим ограничения

вида

(4.9):

х 4= -0 —(—х4+ 0

•х 5-|-0 •хв+ 0

•x 7-fO •х8),

х 5

0

(0 •х4

х 5-(-0 •Xg-f-0 •х 7+ 0 •х 8),

хв= 0 —(0 •х4+ 0

•х5—х 8+ 0 ■х 7-|-0 •х 8),

х 7= 0 — (0 •х 4+ 0

•х 5+ 0

•х в—х 74-0 •х 8),

х 8= 0 —(0 •х 4+ 0

•Xg-j-0 •хе+ 0

•х 7—х 8).

Элементы матрицы условий и компоненты вектора огра­

ничений заполняются

в

первых

восьми

строках

исходной

симплексной

таблицы.

Коэффициенты

целевой функции с

столбце А1 единственный положительный

элемент

(7) стоит

бо 2-й строке. Следовательно, 2-я строка

является

подозри­