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

При переходе к новому базису параметры А/, и А/, преобразуются по формулам

а; , = Д / . - ^ а*.

Вектор Аг принадлежит базису, поэтому

Для всех значений /, удовлетворяющих неравенству (5.2.7), в част­

ничена на множестве (5.2.2), (5.2.3) для всех t~>t\

б) если некоторые из чисел xik положительны, то, введя в имею­ щийся базис вектор A k по обычным правилам метода последователь­ ного улучшения плана, приходим к новому базису, левый конец f

множества оптимальности которого 1.

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

102

то дальнейшие исследования проводятся в соответствии с рекоменда­ циями случая 1°, приведенными выше. Если же этот процесс снова оканчивается выявлением условий неразрешимости задачи:

д ; (h)= а ', + ^ д ;, < о, xu^ о, о = тгм), (5 .2 . 13)

то дальнейший анализ зависит от знака Д^. В случае Д(2 < 0 усло­

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

исследование проводится по тем же правилам, которые описаны выше, с той разницей, что tx заменяется на t2. Через конечное число шагов будут либо обнаружены условия неразрешимости задачи (5.2.1) — (5.2.3) на всей прямой /, либо получен базис, оптимальный для некоторого значения параметра t (условия случая 1°).

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

2-я частная задача линейного параметрического программирова­ ния. Для каждого (, принадлежащего некоторому множеству дей­ ствительной оси, требуется вычислить вектор X, на котором дости­

Решение задачи (5.2.14) — (5.2.16) основывается на методе уточнения оценок (метод будет рассмотрен ниже): вычислительный процесс состоит в движении по базисам псевдопланов задачи (5.2.14) — (5.2.16). Базисом псевдоплана или псевдобазисом назы­ вается система М линейно независимых векторов условий, относи­ тельно которой все векторы условий задачи имеют неотрицательные оценки. Если при некотором значении параметра / коэффициенты разложения вектора ограничений задачи (5.2.14) — (5.2.16) по век-

104

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

Исследуем задачу (5.2.14) — (5.2.16) в соответствии с методом уточнения оценок для t = t0. В результате будет построен оптималь­ ный базис для t = t0(случай 1°) или выявится несовместность условий (5.2.15) — (5.2.16) при t = t0 (случай 2°). Случай неразрешимости задачи из-за неограниченности её линейной формы не представляет интереса. В этом случае задача окажется неразрешимой при всех t, так как условия двойственной задачи не зависят от t и, следова­ тельно, несовместны для всех /.

совместна.

Оценки Aj векторов А, не зависят от t. Поэтому необходимое и достаточное условие оптимальности псевдобазиса — выполнение - неравенств (5.2.18). Исследуем систему (5.2.18). Соотношение с но­ мером s выполняется, если

Обозначим:

(5.2.19)

10 5

Из того, что системы неравенств (5.2.19) разрешимы, следует, что t t. Рассматриваемый псевдобазис является оптимальным

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

Числа t и /, вычисляемые по формулам (5.2.19), полностью опре­

деляют множество оптимальности Е (/, Т) данного базиса, если выпол­ няются условия, описанные выше.

Исследуем теперь задачу (5.2.14) — (5.2.16) правее точки t — 1 (рассмотрение задачидля/< / проводится аналогично). Естественно,

что это имеет смысл только в том случае, если / <С °о, т. е. если среди

X (/) могут стать отрицательными. Пусть xr0(t) — первая из компо­

симо от величины параметра t) продолжает оставаться псевдопланом задачи.

Преобразуем псевдоплан X (/). В соответствии с методом уточне­ ния оценок исключим из базиса вектор А1г и введем вместо него век­

Причем предположим, что существует по крайней мере один вектор

ДО