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

Оценки Д/ векторов условий вычисляются по аналогичным фор­ мулам:

Докажем, что новый псевдобазис оптимален при t = t, может быть оптимальным при t > 1, но не может быть оптимальным при

планом задачи только при условии:

xrk

Но x'rd < 0, Xrk < 0. Следовательно, X'(t) может быть планом задачи только при

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

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

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

107

няются для всех значений t\ задача (5.2.14) — (5.2.16) неразрешима

задачу (5.2.14) — (5.2.16) на луче (tlt оо). Применим к исследованию параметрической задачи при t = tx метод уточнения оценок, начиная этот процесс с имеющегося псевдобазиса. Через конечное число ите­

Следовательно, неположительность Х^ означает неразрешимость задачи (5.2.14) — (5.2.16) на всей оси t, а положительность этого параметра указывает на неразрешимость задачи слева отточки t2> tv В последнем случае исследование параметрической задачи про­ должается в соответствии с уже изложенными правилами, но с той лишь разницей, что tx заменяется на t2. Через конечное число шагов приходим к случаю 1° или обнаруживаем несовместность условий (5.2.14) — (5.2.16) для всех значений параметра t.

Общая задача линейного параметрического программирования.

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

108

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

задач, также сводится к покрытию оси t конечным набором множеств (множеств оптимальности или множеств неразрешимости для фикси­ рованных систем векторов условий). Однако в данном случае мно­ жества, покрывающие ось t, необязательно будут связанными, что препятствует монотонному движению вдоль оси t и усложняет ана­ лиз. Кроме того, система векторов условий задачи, составляющая ее оптимальный базис в окрестности (t0 — е, t0), необязательно должна быть базисом или псевдобазисом задачи правее t0. Поэтому непосред­ ственное использование метода улучшения плана или уточнения оценок здесь затруднено. Наконец, величины Лу и xtj в большинстве случаев представляют собой нелинейные функции параметра t. Отмеченные обстоятельства (особенно первое и третье) делают анализ общей задачи (5.2.26) — (5.2.28) чрезвычайно громоздким. В этой связи практический интерес представляет рассмотрение ряда частных случаев задачи (5.2.26) — (5.2.28), специфика которых приводит к относительно простым вычислительным схемам. Ниже рассмот­ рим два таких случая.

Предположим, что а'у = 0 для всех i и /, т. е. параметр t входит лишь в коэффициенты линейной формы задачи (5.2.26) — (5.2.28)

естественное обобщение двух частных задач, исследованных выше. Будем называть особой любую линейно независимую систему, содержащую М векторов условий задачи (5.2.29) — (5.2.31). Сово­ купность значений параметра (, при которых данная основа является базисом решения задачи (5.2.29) — (5.2.31), называется множеством

оптимальности основы.

Подчеркнем, что в отличие от этих частных задач в рассматри­ ваемой фиксированная основа для некоторых значений t может

109