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

вычисления исходного опорного плана задачи линейного программирования.

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

Пусть (^(р = 1, q) — план Х2-задачи (вообще говоря, неопор­ ный). Введем обозначения

эквивалента Z-задаче. Поэтому в качестве исходного опорного плана Z-задачи можно принять любую линейно независимую си­ стему из Му + 1-векторов условий задачи (5.2.88) — (5.2.90), обла­ дающую тем свойством, что компоненты разложения вектора огра­

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

5.3. Алгоритмы и программа

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

Первая частная задача, учитывающая наличие параметра в коэф­ фициентах линейной формы, реализуется с помощью первого или второго алгоритма метода последовательного улучшения плана. Причем вместо одной строки оценок векторов условий — (М + 1)-й

строки в таблицах первого алгоритма или строки А вспомогательной

д, таблицы второго.алгоритма — вводятся три строки А/,, А/, и — ~

Ii

Для случая 1° и две строки А/, + /5Д/2 и Д/2 для случая 2°. (Допол­ нительные строки отсутствуют только при вычислении исходного опорного базиса).

Процесс решения параметрической задачи начинается с ее ана­ лиза (по общим правилам метода последовательного улучшения

12:

плана) для некоторого значения ( = t0. Анализ завершается слу­ чаем 1° или 2°.

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

ДL \

=— д-Ч и А/2. Выбор вектора, подлежащего включению в базис,

определяется одним из отрицательных элементов первой строки. При необходимости исследовать задачу слева от точки t0 в алго-

Д ,

ритм следует внести изменения: в случае 1° в строке — дДзапол-

I2

няются только позиции, отвечающие Д/2> 0 , а вектор, подлежащий введению в базис, определяется максимальным элементом этой строки; в случае 2° решение продолжается лишь при А*2 < 0 (усло­ вие Д*2 0 указывает на неразрешимость задачи слева от точки t0).

Если предварительный анализ задачи привел к случаю 2°, то через конечное число шагов выявляем условия неразрешимости задачи (слева или справа от t0) или переходим к случаю 1°. Исследо­ вание задачи в соответствии с правилами случая 1° через конечное число итераций завершается либо построением базиса, множество оптимальности которого — луч, либо выявлением луча, внутри которого задача не имеет решения (направление луча соответствует направлению изменения параметра при анализе задачи). В процессе решения параметрической задачи выгоднее двигаться в одном фик­ сированном направлении. Поэтому, если заданный диапазон изме­ нения параметра t представляет собой луч или отрезок, то целесооб­ разно начать вычисления с одного из его концов. Если же необхо­ димо исследовать задачу на всей оси t, то в качестве начала можно выбрать t — °о или t — —оо (в первом случае предварительный анализ требует максимизации линейной формы

N

Е 4 '* /’

/= 1

во втором случае он сводится к минимизации этой формы).

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

128

Рассмотрим теперь алгоритм задачи параметрического програм­ мирования для случая, когда от параметра линейно зависит вектор ограничений. Решение задачи начинается с вычисления её оптималь­ ного для одной (любой) из точек t0 заданного диапазона изменения параметра t. Если этот диапазон представляет собой луч или отре­ зок, удобно начинать вычисления с крайней точки, чтобы двигаться в процессе решения задачи в одном направлении.

Для начальной точки t0 задача реализуется методом последова­ тельного улучшения плана или методом уточнения оценок в зависи­ мости от того, что проще вычислить — исходный опорный план или псевдоплан задачи.

Если в результате анализа задачи для t — t0 выяснится неогра­ ниченность её линейной формы, то делается вывод о неразрешимости параметрической задачи при всех значениях /. Если же исследова­ ние этой задачи завершается либо построением оптимального плана (случай 1°), либо выявлением несовместимости её условий (случай 2°), то необходимо использовать метод параметрического програм­ мирования, изложенный выше. Алгоритм составляется путем моди­ фикации одного из алгоритмов метода уточнения оценок (первого или второго). В случае 1° в таблицы метода уточнения оценок вместо одного столбца Л0 целесообразно ввести три столбца: в первый стол­ бец Ло записываются компоненты X'th', во второй столбец Л,' — со­

ставляющие вектора *г20', третий столбец заполняется отношениями —

( 1>

---- jjj- . Если параметр t в процессе анализа возрастает (убывает), то

хю

заполняются лишь те позиции третьего столбца, которым отвечают

*й‘ < 0 (хй’ > 0).

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

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

Во втором случае очередной псевдобазис является оптимальным для луча [/*,оо), если t возрастает, и для луча (—оо, (*j, если / убывает.

Если представительный анализ задачи для случая 2° завершился выявлением несовместимости ее условий при / = /0

условий задачи для всех t. В противном случае вычисляем tx = — хгО*гО

и вместо одного столбца А 0 вводим в таблицы два столбца: в первый столбец А ’) записываются компоненты xfi, во второй столбец Л0 (t)—

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

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

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

Исследование следует начать с решения задачи для некоторого значения t = /0.

Пусть для определенности при t = t0 на некоторой итерации процесса решения получен оптимальный план общей задачи, кото­

130

векторам этой системы (для тех t, при которых она является основой):

Оценки Дj (t) векторов условий .4/(0 относительно выбранной

Полученная система векторов (основа) является базисом решения задачи в диапазоне изменения параметра (, для которого удовлетво­ ряется система неравенств

части этих неравенств в общем случае представляют собой отношения некоторых многочленов относительно t. Поэтому построение мно­ жества оптимальности сводится к решению ряда алгебраических уравнений. Очевидно, в общем случае множество оптимальности состоит из нескольких компонент. Для дальнейшего анализа сле­ дует выбрать одну из граничных точек (точку /х) множества опти­ мальности и приступить к исследованию задачи в том из достаточно малых интервалов, примыкающих к tx, который содержится в ещё не рассмотренной части оси (. Пусть этим интервалом для опреде­ ленности является (tx, tx -+- е). Решим общую задачу при t = tx + е, где и — достаточно малое положительное число. В качестве исход­

при рассмотрении частных случаев. В соответствии с ними через несколько итераций методов улучшения плана и (или) уточнения

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

малыюсти или неразрешимости).