Файл: Арутюнян А.Г. Применение математических методов и ЭВМ в народном хозяйстве.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 17.07.2024

Просмотров: 167

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

и определяются

®i, если j = j £ I ,

(21.13)

О, если /£/.

Очевидно, что вектор А' = (х 1, х,,..., jc„), компоненты которого определены из отношения (21.13), удовлетворяет условиям (21.3), (21.4) и минимизирует целевую функцию

( 21. 2 ).

Если для имеющегося базиса условие (21.11)

не вы­

полняются,

то

по формуле

(21.9')

определяются

коэффи­

циенты х ijo

представления вектора

Aj по векторам

базиса,

где Aj — вектор, отстоящий

от В на расстоянии р (т. е. р

определяется

при помощи pj

= m in p i). По формуле (21.10)

определяется

 

Jel

 

 

величина р* и сравнивается с р. Если ps^p",

то из дальнейшего рассмотрения

исключается точка Aj

(путем замены величины pj достаточно большой величи­ ной „Л1“ ) и для остальных внебазисных векторов вычис­ ляется величина р. Если же р<Ср",' то вместо вектора Л)ь

определяющего величину р", в базис вводится вектор Aj При этом элементы обратной матрицы Б преобразуются по формулам преобразования второго алгоритма метода последовательного улучшения плана. Затем повторяется цикл вычислений величин Pj(y’= l , 2,..., л), р, р' и анализа выполнения условия (2 1 .11 ).

Для доказательства сходимости описанного процесса предположим, что план А (0)= (л:,(0), х 20),..., Хп0))т являет­ ся оптимальным опорным планом задачи (21.2)—(21.4). Если в результате применения приведенного алгоритма получен оптимальный опорный план X ' = (х \ , х '2,..., х'„У , то макси­ мальное расстояние векторов базиса от вектора В при этом опорном плане не может быть больше максимального рас­ стояния векторов базиса от того же вектора при опорном

плане А'101. Действительно,

пусть плану _А(0)

соответствует

базис (Б {0,>у '= (^ j» , Aft.....

Л;»ш), а плану А '— базис ( Б ') '1—

— (Лг ,

Лj ',. .

Л;;п).

Предположим,

для

ясности,

что

p(S,

J j- ) > p ( S ,

Aj*),

где р(£, Л,;)

и р(В,

Л)») — макси­

мальные

расстояния, причем х(0)*ф О

и х'у

0.

Это озна­

чает,

что вне

базиса

(Б' ) ~ 1 существует вектор

(в

част-

301

ности, вектор Aj°), расстояние которого от вектора В меньше, чем максимальное расстояние базисных векторов. А последнее эквивалентно тому, что признак оптимальности (21.11) не выполняется. Но если признак оптимальности не выполняется, то, согласно алгоритму, можно еще улуч­ шить план, т. е. перейти к соседнему опорному плану, при котором количество максимально отстоящих от вектора В базисных векторов уменьшается на единицу. Однако пред­ положение оптимальности плана X противоречит возмож­ ности перехода. Следовательно, через конечное число ша­ гов по описанному выше алгоритму обязательно будет найден оптимальный опорный план рассматриваемой зада­ чи. При изложении алгоритма предполагалось наличие не­ которого базиса и обратной матрицы, соответствующей

этому

базису.

 

 

 

 

 

 

 

Для нахождения исходного базиса решается вспомо­

гательная задача,

заключающаяся в минимизации функции

(2 1 .2 )

при

условиях

 

 

 

 

 

 

 

v а '„ JC, =

 

i = l ,

2,..., я ,

(21.3')

где

 

j-I

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Oij,

при у — 1 , 2 ,...,

п, i — l, 2 ,...,

т,

 

а'

1 ,

при j

=

n-\-i\

 

 

 

 

 

v

J

 

 

W = l, 2 ..... m.

 

 

 

О,

при j

ф n -\-i I

 

 

Для вспомогательной задачи искусственные (единич­

ные) векторы An+i( i = l ,

2 ,..., т) образуют базис; следова-’

тельно,

/ 0 =

{/i-f-l,

пф- 2 .....

п-\-т\, и обратная матрица

является единичной.

Для у£ / 0

принимается рS=

M (М — до­

статочно большая величина). Хотя это не соответствует действительности, однако не противоречит общей идее алгоритма и существенно для реализации алгоритма, так как в первую очередь из базиса должны исключаться ис­ кусственные векторы. Ясно, что в предположении сущест­ вования хотя бы одного базиса среди исходных векторов Aj (_/= 1, 2 ,.,., п) через конечное число шагов применения того же алгоритма относительно вспомогательной задачи будет получен некоторый базис исходной задачи.

302

Блок-схема изложенного алгоритма решения задачи (21.2)—(21.4) (при наличии исходного базиса и обратной матрицы) приведена на стр. 304.

§ 2. Задача со специальной структурой матрицы условий

Рассмотрим теперь_другую нелинейную задачу, в кото­ рой требуется вектор B £ R m представить в виде выпуклой комбинации ближайших ( т + 1) линейно независимых век­ торов из заданного множества, при дополнительном пред­ положении, что компоненты векторов Л], j = 2 , 3,..., п выражаются с помощью соответствующих компонентов век­

тора

по следующей формуле:

 

 

a,j =

Ai, г = 1 , 2..... т\ j = 2, 3,..., Ти

(22.1)

где Л;— заданные величины, а 1ц— принимают определенные целые значения и удовлетворяют условиям

* — 1,

2..... m\ j =

2, 3..... Т,.

(22.2)

Предположим, что

компоненты

вектора В удовлетво­

ряют условиям1

 

 

 

 

 

ап ^ Ь ,^ а ^ ,

i — 1 ,2 ,...,

m;

n = \ \ T l.

(22.3)

Поставленная задача матеметически формулируется сле­

дующим образом.

 

_

 

 

 

Найти я-мерный

вектор Х ~ { х 1, х 2,..., х п)т,

минимизи­

рующий величину

 

 

 

 

 

r(B ) =

m axp(B,

Xj),

 

(22.4)

при условиях

Х)ф0

 

 

 

 

 

 

 

 

£ a^Xj^sbii i= l,

2,...,

m,

(22.5а)

j-i

 

 

 

 

 

1 Заметим, что в противном случае вектор В нельзя представить в виде выпуклой комбинации векторов Ау

303

Блок-схема алгоритма решения нелинейной задачи с общей структурой матрицы условий

Начало

304

V

Xj = 1,

 

(22.56)

x ^ O ,

j =

1, 2..... n,

 

(22.6)

^ .аД Л /, 1 )= 0 только

при aj==0

для всех у'£/, (22.7)

Jel

 

 

 

 

т. e. (т+ 1)-м ерн ы е векторы (Л;Т,1)

для

образуют ли­

нейно независимую систему, где

 

 

 

/ =

! / / ^ > 0|.

 

 

Задача (22.4)—(22.7), вообще говоря, сложнеезадачи (21.2)— (21.4), однако сделанные допущения относительно структуры матрицы условий позволяют ее решать более простой вычислительной схемой. Нетрудно заметить, что каждому вектору Aj (1 < у '< я ) можно поставить во взаимно­ однозначное соответствие целочисленный вектор Lt. Дейст­ вительно, из (22.1) видно, что вектор Li с компонентами

' » = ”

(22.8)

будет целочисленным.

Таким образом, реализуется некоторое отображение пространства Rm на себя, причем точка Ах переходит в начало координат, а остальные точки А; переходят в цело­ численные вершины /л-мерных параллелепипедов (вернее—

кубов, но с разными

масштабами по координатным осям),

которые в дальнейшем

будем

называть элементарными.

Легко заметить, что

при таком

отображении образ точки

В попадает в некоторый

элементарный параллелепипед с

целочисленными вершинами и, следовательно, во внутрь

некоторого

симплекса, образованного ближайшими (/ге-|-1)

вершинами

параллелепипеда.

 

 

 

Координаты

образа В будут выражаться формулами

 

»,•= А = Д з_,

2

т.

(22.9)

 

 

h\

 

 

 

_ Очевидно,

что координаты

 

самой близкой

к точке

В* = { b * , 6j*.....

Ьт*) вершины элементарного параллелепи-

 

 

305

 

 

 

20— 644

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

 

 

*1, = [*1Т + М Ю . *'“

1.

2 .-.- гп,

 

(22.10)

где

p ( t ) — булевая

функция,

определенная

на

отрезке

[0,1],

т. е.

 

 

 

 

 

 

 

 

 

! 0,

если t — [/]

 

(2 2 .11)

 

 

 

 

 

 

,

 

 

 

 

1,

если

 

 

 

 

Координаты же остальных т ближайших вершин Z)

определяются формулой:

 

 

 

 

V —

f

In , если кФ 1,

/= 1 , 2.....

т,

 

(22.12)

 

0

 

если k = i ,

i = l , 2..... m.

 

[ /и -j—(1—2p(b*)\,

 

Непосредственной проверкой можно убедиться, что

самая удаленная точка

из выбранных будет

отстоять от

В не дальше, чем

любая другая

точка. Такой результат

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

абсолютных

величин раз­

ностей соответствующих координат. А последнее

влечет

за собой

обеспечение

минимума

величины г {В)

при вы­

полнении условий (22.5а), (22.56), (22.6) и (22.7). Дейст­

вительно, вектор В

(образ вектора В) по выбранным век­

торам

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

в виде

 

 

 

B‘ =

Lu +

t (1 -2 р (» ,* ))(* Г -/| ,к)(Г|ь -

г

1.).

(22.13)

 

 

к=1

 

 

 

 

Вектор

В представится по векторам

А}

и A)

(fe = l,

2..... т) этими же коэффициентами. В правой части выражения_(22.13) записана выпуклая комбинация векторов Lio, Zj , Zja,..., Z jm. Доказательство линейной независимости

указанных векторов

при превращении их в (/п+1)-мерные

векторы добавлением

„1“ в качестве (т + 1 ) - о й компоненты

не представляет собой трудности.

Следовательно, вектор

Х = { х г, -*2,..., х п)т,

компоненты

которого определяются

соотношениями1

означает целую часть величины 61*.

1 Здесь символ [6j*]

306

Смотрите также файлы