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

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

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

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

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

Добавлен: 23.10.2024

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

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

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

Таким образом, множество оптимальности данной основы пред­ ставляет собой либо прямую (/ = — оо, t — оо), либо луч (одна из границ {, t бесконечна, а другая — конечна), либо, наконец, отре­ зок (( > — оо, t <; оо), который может выродиться в точку (/ =

— t — t0). Как видим, множества оптимальности задачи (5.2.29) — (5.2.31) обладают свойством связности, что является следствием линейной зависимости величин xi0(t) и А_,-(/) от параметра t. Это обстоятельство, а также линейность функций х,0(/) и Aj (() значитель­ но упрощают анализ задачи.

Предположим, что правая граница t данного множества опти­ мальности конечна, и продолжим анализ задачи для t > t. Сделаем

достаточно малый сдвиг вправо от t. Если t = t' <. t", то при этом снова At , Ai , ..., At перестанет быть базисом, однако все еще

останется псевдобазисом, так как неравенства (5.2.33) продолжают выполняться. Естественно, что в данной ситуации следует, как и при исследовании 2-й частной задачи, использовать метод уточне­

ния оценок. Если при переходе через t нарушается одно или несколь­ ко неравенств системы (5.2.33), а система (5.2.32) продолжает соблю­

даться, т. е. t = Г < 7', то для

анализа задачи используется метод

улучшения плана подобно тому,

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

1-й частной задачи. Возможен,

наконец, предельный случай, когда

t — t' = t". В этом случае основа At , А^, ..., AtM при любом t > /

не является ни базисом, ни псевдобазисом.

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

дачи (5.2.29) — (5.2.31) на вектор В (t) и назовем полученную задачу вспомогательной. Очевидно, основа Ai , At2, ..., AtM является бази­

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

могательной задачи при t > 1 или строим новую основу, множество оптимальности которой имеет в качестве левого конца точку t.

Первый исход указывает на неразрешимость параметрической

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

чи (5.2.29) — (5.2.31)

на некотором отрезке с левым концом в точ­

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

последующий анализ может проводиться мето­

дом уточнения оценок, начиная с вновь построенного псевдобазиса. Итак, анализ параметрической задачи (5.2.29) — (5.2.31) сво­ дится к серии последовательно проводимых итераций методов

улучшения плана и уточнения оценок.

Сформулируем правила, которым подчиняется течение процесса. Эти правила являются следствием приведенных выше рассуждений.

Ml

Ограничимся случаем, когда параметр t изменяется слева направо. По имеющейся основе вычисляем величины 1' и t", пользуясь фор­

мулами (5.2.34) и (5.2.35). Если t — min (?, t") = оо, то анализ закончен.

Если же t <; оо, то необходимо перейти к следующей итерации,

вид которой определяется соотношением между числами ( и I". Возможны два случая:

1)2)

Впервом случае проводится итерация метода уточнения оценок для задачи (5.2.29) — (5.2.31) при t = t. Вектор At , подлежащий исключению из базиса, определяется соотношением

лго

 

ХгО 0.

(5.2.37)

~ 7 7 Г =

т ш

">

x'i0 <®

 

 

Во втором случае проводится итерация метода улучшения плана

для задачи (5.2.29) — (5.2.31) при t = t. Вектор А к, подлежащий включению в базис, определяется из соотношения

—

=

min ( —^гА — i, ДА>< 0 .

(5.2.38)

д*г

 

д/а<о V

А/>/

 

Если оказывается, что

 

 

 

хГ] SzO,

(/ =

1,

JV) в 1-м случае

 

или

0,

(/ =

1,

М) во 2-м случае,

 

Xik

 

то фиксируется неразрешимость задачи справа от t: в первом случае несовместны условия задачи, двойственной по отношению к (5.2.29)— (5.2.31) , во втором — несовместны условия самой задачи (5.2.29) — (5.2.31) .

Используя приведенные выше соображения, нетрудно убедиться, что предполагаемый процесс позволяет за конечное число шагов полностью исследовать параметрическую задачу (5.2.29) — (5.2.31). Рассмотренный здесь метод дает возможность последовательно вычис­ лить все значения функции

f(i) = max \ ^ ( C j + tC J ) x X

х L/=1

где максимум берется по значениям X, удовлетворяющим условиям

(5.2.30) — (5.2.31).

Итак, пусть задача (5.2.29) — (5.2.31) имеет решение более чем при одном значении t. В таком случае;

\П

а) область определения Е функции f (/) представляет собой либо прямую, либо луч, либо отрезок; / (t) непрерывна на Е\

б) множество Е конечным числом точек /,• (критические точки) разбивается на множества (отрезки или лучи, если имеется хотя бы одна критическая точка), на каждом из которых f (t) = d i j 2 +

+

di2t -f dis. Рассмотрим еще один частный случай задачи (5.2.26) —

(5.2.28), когда параметр t

входит только в составляющие одного из

ее

векторов условий, т.

е. параметрическую

задачу,

состоящую

в максимизации линейной формы

 

 

 

 

N

 

 

 

 

 

1,с,х1

 

(5.2.39)

при условиях:

 

 

 

 

 

М \ + tA [) +

2 X-jA-j —B\

 

(5.2.40)

 

 

 

/= 2

 

 

 

X j ^ O ,

(j = T7N).

 

(5.2.41)

 

Как обычно, исследование параметрической

задачи

начинается

сее анализа для некоторого значения параметра t = t0. Предвари­ тельный анализ завершается одним из трех исходов:

1)построением оптимального базиса, составленного из векторов

сномерами t1( t2, ..., /ль

2)выявлением несовместимости условий задачи;

3)выявлением неограниченности линейной формы задачи на множестве ее планов.

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

Итак, допустим, что имеет место первый случай. Вычислим коэф­ фициенты разложения Xij(i) векторов условий задачи и вектора Л0 =

=

В относительно имеющегося

базиса и оценим Дj(t) =

Xm+i,/(0-

Условимся считать is ^

2

при s

= 2,

3, ..., М. Вид функций Xij(f)

(i

= 1, М + 1; j = 1, N)

различен в зависимости от того, входит

или не входит вектор А^

(t) = А[

+ A'[t в данный базис.

 

 

Если /j

= 1 и система векторов А", Л,-г,

..., A iM линейно неза­

висима, то

 

 

 

 

 

 

 

 

 

 

Xi/jITP'

(l = 2,

M + 1;

/ = 0, N);

(5.2.42)

 

 

Хц (t)

 

 

 

 

 

 

 

 

*=7*,

0 = 1 ,

/ = OTW).

 

 

Если (t

= 1 и вектор

 

 

является линейной комбинацией векто­

ров Лг2, Аез....... AiM, то

 

 

 

 

 

 

 

 

 

X i/W ^ x iy + tx'if,

(;= 1 ,

М + 1; j = 07N).

(5.2.43)

119

Если

z\ >

1,

то

 

 

 

 

 

хи , (t'= 1,

M;

/ = 0 , M);

 

 

 

Xij (t) =

(z =

(5.2.44)

 

 

 

x'A'-\-tx'a\

I7M; / = 'l).

Здесь

Xij,

tij,

t*, x\\\, x'i\' — некоторые

константы.

Соотношения (5.2.42) и (5.2.43) являются простыми следствиями известных формул Крамера.

Как видим, в данном случае элементы задач линейного парамет­ рического программирования могут зависеть от параметра t нелиней­ но. Однако специфика этой нелинейной зависимости (%(/) — дроб­ но-линейные функции с одинаковыми знаменателями) позволяет все же разработать достаточно экономный алгоритм анализа задачи

(5.2.39) — (5.2.41).

Определим область оптимальности имеющейся основы. Пусть

вначале г\ =

1 и система векторов А", Л/г, ...,

A'iM линейно незави­

сима. Условия оптимальности xl0(t) О,

Дj(t)

^ 0 в соответствии

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

(5.2.42) переписываются в

виде

 

 

 

х^т Е т * ^0’

(г‘ = 2 Г м );

(5.2.45)

 

хм +и г ~т~т*'' 1 ^ ° >

(/= T lV ).

(5.2.46)

Если х10

Ф 0,

то учитывая постоянство

знака

знаменателя

t — t* (он должен совпадать со знаком х10), приходим к выводу, что множество оптимальности основы связно.

Обозначим через I и t нижнюю и верхнюю границы множества оптимальности (вычислить эти границы нетрудно). При /*, отличном

от / и t, множество оптимальности замкнуто, т. е. совпадает либо с прямой, либо с лучом, либо с отрезком, который может выродиться

в точку. При i*, совпадающем с одним из чисел 1 ,1, множество опти­ мальности основы — либо открытый луч, либо отрезок без одного из СВОИХ концов.

Если д'10 = 0, то вектор В — линейная комбинация векторов Ai , At3, ..., AiM. Вероятнее всего, среди векторов условий задачи,

не входящих в основу, найдется хотя бы один вектор Aj, для которого Xijito) Ф 0. В этом случае, заменив в базисе вектор A^t) на А), не изменим компонент имеющегося опорного плана и в то же время придем к ситуации, отвечающей формуле (5.2.44). Однако может

случиться, что любой вектор условий Aj (/ ^

2) является линейной

комбинацией векторов Л;2, ..., А 1м. Тогда,

очевидно, левые части

неравенств (5.2.45), (5.2.46) не зависят от t и множество оптималь­ ности данного базиса — прямая. Случай, отвечающий соотношениям (5.2.42), полностью разобран.

Возможности, соответствующие формулам (5.2.43) (5.2.44), более просты, так как зависимость от параметра t в данном случае линейна.

1Н

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

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

деленности будем вести речь о правой границе /, которую естественно считать в данном случае конечной. Рассмотрим параметрическую

задачу (5.2.39) — (5.2.41) в достаточно малом

интервале (t, ~t + е)

изменения параметра. Возможны три

случая:

 

/ +

е);

а)

имеющаяся основа 5 (t) является базисом при / е ( / ,

б)

основа

S (/) — псевдобазис для

t е

(/,

1 +

е);

 

 

в)

при t е

(/, ~t + е) как среди величин

*,-„(/),

(1 С i

sg

М),

так и среди величин Aj(t) = xM^j{t),

(1

/ c N )

имеются отри­

цательные.

 

 

 

 

 

 

 

В случае а (б) применяем метод улучшения плана (уточнения оце­

нок),

начиная от имеющейся основы S (/). Через конечное число ша­

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

няем, что на некотором множестве (связном) с левой границей t задача неразрешима.

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

рой линейной комбинации векторов основы, причем в случае t — t* результат следует умножить на (—1). Затем после нескольких ите­ раций метода улучшения плана выясняется несовместность условий задачи, двойственной по отношению к задаче (5.2.39) — (5.2.41), или строится псевдобазис задачи (5.2.39) — (5.2.41). В обоих слу­ чаях отмеченные условия выполняются в некотором интервале изме­

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

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

с левым концом t.

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

115

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