Файл: Пивоваров, С. Э. Моделирование процессов прогнозирования в приборостроении.pdf

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

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

Отметим, что особые значения параметра характеризуются следующим свойством: системы векторов условий, порождающие

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

ного свойства аналитических функций: точка, в которой отличная от тождественного нуля функция аналитична, не может быть пре­ дельной для нулей данной функции.

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

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

Рассмотрим более подробно алгоритм решения задачи опреде­ ления оптимального варианта прогноза развития отрасли методом разложения. Система условий задачи разбивается на блоки 1 и 2, размеры которых определяются емкостью оперативной памяти ЭВМ. При разделении матрицы А = ||а^|| условий задачи на матрицы А1 и А2 естественно включать во второй блок условия, приводящие к возможно более «редкой» матрице А2. Таким образом обычно удается упростить вычисление оптимальных планов Х А-задачи на различных итерациях решения Z-задачи.

132

Z-задача решается по правилам второго алгоритма метода по­ следовательного улучшения плана [80]. Однако особенности метода разложения заставляют внести некоторые изменения в вычисли­ тельную схему второго алгоритма.

При решении Z-задачи заполняются только элементы матрицы Е1 (рис. 10, а), при этом необходимость во вспомогательной матрице

отпадает. Вместо последней целесообразно ввести матрицу А1 (рис. 10, б), в которой фиксируются строки матрицы условия А1 и коэффициенты Cj линейной формы исходной X-задачи.

Пусть /-я итерация решения Z-задачи закончена. В результате заполнена /-я основная таблица Е1 Z-задачи (кроме двух столбцов рк и 0). Пользуясь величинами Яг, полученными в/-й итерации, форми­ руем линейнуюформу Хлзадачи. Решение Хл-задачи целесообразно также проводить по правилам метода последовательного улучшения плана. При этом можно использовать оптимальный план ХЛ-задачи, отвечающий /-й итерации, в качестве начального опорного плана Хл-задачи, полученной на (/ + 1)-й итерации.

133

Такой порядок вычислений обычно сокращает количество ите­ раций, необходимых для решения ряда Л Л-задач. Выбор первого или второго алгоритма метода улучшения плана для решения ХЛ-за- дач определяется структурными особенностями матрицы А2.

При решении X д-задачи по второму алгоритму метода последо­ вательного улучшения плана, так же как и при решении Z-задачи,

формируются основная матрица Е2 (рис. 11, а) и вспомогательная матрица А2 (рис. 11,6).

В столбец рк основной матрицы Е1 Z-задачи записываются ком­ поненты разложения вектора рк по векторам текущего базиса. Столбец 0 основных матриц Е1 и Е2 заполняется в соответствии с об­ щими правилами второго алгоритма метода последовательного улуч­ шения плана. Далее, как обычно, определяется вектор, подлежащий исключению из базиса Z-задачи, и по известным рекуррентным фор­ мулам заполняется главная часть основной матрицы Е1, отвечающей очередной итерации. Через конечное число шагов приходим к ре­ шению Z-задачи или устанавливаем ее неразрешимость (неограни-

134

ценность линейной формы на множестве возможных планов). Ли­ нейная форма Z-задачи может быть не ограничена в области своего определения только в случае неразрешимости Х-задачи.

Рис. 12. Блок-схема алгоритма метода разложения (оптимизации)

Оптимальный план Х-задачи определяется через компоненты г% решения Z-задачи и оптимальные планы xv последовательных Хдзадач [22].

Блок-схема алгоритма метода разложения (оптимизации) на /-й итерации представлена на рис. 12. Рассмотрим пошаговый алгоритм

135

Рис. 13. Шаг 1 алгоритма оптимизации

136

Р а с п р е д ел е н и е п а м я т и д л я м а с с и в а E l [ M i + 2 , M i + 7 ]

±

r-=j+1

t:=2

~F =

pW

i - = U 1

i - = 2

Рис. 14. Шаг 2 алгоритма опти­ мизации

137