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

Исходя из специфики задачи (17.5)—(17.8) легко убедиться,

водит к ее разрешимости на рассматриваемом параллелепи­ педе (в работе [811 рассматривается и случай неразреши­ мости задачи в указанной точке).

Алгоритм решения задачи (17.1)—(17.4) основан на принципе сведения многопараметрической задачи к одно­ параметрической, выбором каждый раз определенного на­ правления, обеспечивающего возрастание функции F (A ).

Г Л А В А 2

ЗАДАЧИ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

Опыт показывает, что разработка алгоритмов и их теоретическое обоснование являются, с одной стороны, достижениями теории математического программирования, с другой образуют только аппарат, средство для решения практических задач. Анализ результатов решения практи-

296

ческой задачи, определение целесообразности их внедре­ ния и непосредственное внедрение проводится только спе­ циалистами по словесной постановке задачи. Это обстоя­ тельство, конечно, не снижает роли разработки алгорит­ мов. Формализация различных явлений, постановка задач на оптимум является одним из важнейших с т и м у л о в разви­ тия теории математического программирования. Но без со ­ ответствующей математической подготовки вряд ли удастся разработать практически пригодный алгоритм.

В настоящей главе будут рассмотрены два вида нели­ нейных задач, которые возникли в процессе исследований химических процессов. Однако практическая применяемость этих задач уже выходит за пределы управления химиче­ скими процессами. В рассматриваемых задачах ограничения выражаются линейными соотношениями, и нелинейны толь­ ко целевые функции. Хотя целевая функция не является выпуклой, но всякий локальный ‘ минимум задачи одно­ временно является глобальным минимумом, и множество минимизирующих целевую функцию точек является вы­ пуклым.

Иными словами, задача обладает свойством одноэкстремальности, которое дает возможность разработать сх о ­ дящийся алгоритм ее решения.

5 1. Задача с общей структурой матрицы условий

Пусть имеется определенное конечное множество век­ торов Aj и вектор_£ из пространства Rm, причем во мно­ жестве векторов Aj имеется хотя бы один базис. Ставится задача: из этого множества выделить такую линейно неза­ висимую систему векторов, чтобы:

а) можно было вектор В представить в виде линей­ ной комбинации векторов этой системы;

б) расстояние между В и максимально отстоящим от него вектором из выделенной системы было мини­ мальным.

Геометрически это означает: построить шар с центром, лежащим в точке В, с минимальным радиусом, содержа­ щий такую линейно независимую систему точек, что точку

297

В можно было представить в виде линейной комбинации этих точек.

Необходимость требования линейной независимости векторов Aj вызывается только из-за однозначности пред­

(т. e. векторы Aj при y £ / ' линейно независимы), где мно­ жество У' определяется следующим образом:

/ , = U i x i =f=0 ).

Очевидно, задача (21.2) — (21.4) является нелинейной; кроме того, целевая функция (2 1 .2 ) не является вогнутой функцией. Следовательно, эта задача не входит в класс задач выпуклого программирования. Однако специфика це­ левой функции позволяет решать поставленную задачу без особых затруднений. Опираясь на основные принципы ме­ тода последовательного улучшения плана, можно построить

на условие (21.4), так как, исходя из специфики алгоритма, оно автоматически будет выполняться. По аналогии общей задачи линейного программирования можно для задачи (21.2)— (21.4) определить такие понятия, как базис, опор­ ный план и вырожденность.

298

Вектор X , удовлетворяющий условиям (21.3), будем называть планом задачи; опорным будем называть план, удовлетворяющий условию (21.4).

Опорный план будем называть невырожденным, если множество Г содержит ровно т индексов J. В противном случае (т. е. если количество этих индексов меньше, чем т) опорный план назовем вырожденным.

Из теории линейного программирования известно (см., например, [92|, стр. 760), что всякая разрешимая задача линейного программирования обладает опорным планом, и оптимум линейной функции достигается на опорном плане. Легко показать, что если вместо задачи (21.2)—(21.4), ре­ шать задачу (21.2)—(21.3), то среди планов, оптимизирую­ щих целевую функцию (2 1 .2 ), найдется и опорный план. Действительно, если оптимум целевой функции достигается на некотором плане, ненулевые компоненты которого соот­ ветствуют векторам А} , Ai Ajk, то из этой системы всегда можно выделить линейно независимую систему. Ясно, что при имеющемся оптимальном плане справедливо соот­ ношение

В. (21.5)

Не меняя общности рассуждений, предположим, что первые kt из этих векторов линейно независимы. Предста­ вим каждый из остальных векторов (однозначно) в виде

и тех же векторах, получаем компоненты опорного плана, оптимизирующего функцию (2 1 ,2 ).

З а м е ч а н и е . Векторы, лежащие в построенном шаре, могут образовать линейно зависимую систему только в тех случаях, когда некоторые векторы из этой системы будут равноудаленными от вектора В, или же в шаре имеются векторы, образующие линейно зависимую систему в подпространстве, размерность которого хотя бы на еди­ ницу меньше размерности вектора В.

Приведем описание алгоритма решения задачи (21.2)— (21.4). Предположим, для ясности, что имеется некоторый

299

обратная относительно матрицы, составленной из базисных векторов-столбцов. Множество индексов базисных векто­ ров обозначим через /. Нетрудно заметить, что если за­ дача невырождена, то для любого опорного плана задачи

(21.2)— (21.4) имеет место / ' = /.

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

где 1х= и ^ 1 х - 1О= Б ;В -^ 0 }.

Процедура нахождения оптимального опорного плана достаточно близка к процедуре метода последовательного улучшения плана. Она позволяет перейти от текущего опорого плана к тому из соседних планов, который ближе к оптимальному. Вычислительный алгоритм включает не­ которые идеи второго алгоритма метода последовательного улучшения плана, а именно, при переходах используется обратная матрица Б. Легко заметить что соотношение

является достаточным условием оптимальности данного базиса.

Это условие не является необходимым, однако искусст­ венными приемами можно проверку оптимальности имею­ щегося базиса привести к анализу выполнения этого усло­ вия. Таким образом, для проверки оптимальности базиса в первую очередь проверяется условие (21.11). При вы­ полнении условия (21.11) с помощью обратной матрицы Б

300