Файл: Арутюнян А.Г. Применение математических методов и ЭВМ в народном хозяйстве.pdf

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

N не имеет ни одной точки.

Возможно, что указанный выше случай встретится при наличии в базисе хотя бы одного искусственного вектора. Очевидно, в этом случае N = '0 .

Таким образом, применением метода последовательного улучшения плана, а затем (при движении в сторону умень­ шения параметра) — метода последовательного уточнения оценок, а также пользуясь формулами определения границ отрезков Nx (см. [18]), за конечное число шагов указанной процедуры строится функция на всей области ее опре­ деления.

Блок-схема решения задачи (15.1)— (15.3) приведена на стр. 278.

§ 6. Решение задачи параметрического программирования с вектором условий, линейно зависящим от параметра

Предположим, для ясности, что урезанная задача (11.1Г )—(11.13') разрешима. Применяя к ней метод после­ довательного улучшения плана, через конечное число ша­ гов получим оптимальный опорный план. Добавлением к этому плану переменной х , с нулевым значением получим опорный план задачи (11.11)—(11.13). Последний будет оптимальным опорным планом для некоторого множества изменения параметра Л. Для определения границ такого множества вектор

P ,(A ) = Q »,+ V k^l

(где Qk,= ( a ku, ak21,..., akmi), £ = 1, 2 ..... К) представляется

277

Блок-схема решения простейшей параметрической задачи

Начало

278

по векторам имеющегося базиса. Пусть лг0и -|- £

_ к=1

коэффициент при базисном векторе Р . (занимающем /-ую

позицию в базисе) в представлении вектора РДЛ) по век­ торам базиса. Оценка

лупространство. Так как на этом полупространстве значе­ ние целевой функции не зависит от Л, то оно постоянно.

ни одной точки области N.

Если же в полупространстве, определяемом условием (16.1) , хотя бы одно из выражений (16.2) остается поло­ жительным (а это означает, что пересечение двух полу­ пространств

является непустым множеством), то фиксируется некото­ рая точка на граничной гиперплоскости полупространства (16.1) , выбирается определенное направление и на этом направлении многопараметрическая задача приводится к однопараметрической. В качестве такого направления мож-

279

-р (» ) — ^ ( А “).

В результате решения однопараметрической задачи строится последовательность отрезков, на каждом из ко­ торых функция <р(я) порождается одним и тем же базисом (вернее, одной и той же группой базисов). Получив гра­ ничную точку nm„ , выбирается новое направление и по этому направлению снова решается однопараметрическая задача, не рассматривая отрезки, соответствующие базисы которых уже были определены. Так как каждый раз вы­ бором направления обращаемся к однопараметрической за­ даче, то следует детально изучить однопараметрическую задачу. На указанной полуоси вектор Р ,(Л ) будет пред­ ставлен в виде

280

В зависимости от значений величин х 'и и х "н рассмат­

определена, так как целевая функция задачи неограничена сверху на множестве планов задачи. А если jc'ix — 0 для 1 = 1, 2 ,..., т, но хотя бы для одного индекса г, то имеется возможность исключить из базиса -некоторый век­ тор, вводя вместо него в базис вектор Р1 (Л), и получить таким образом основу, являющуюся базисом на некотором отрезке (0 , а'|.

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

■*11(<0

но тем строкам, для которых -*ц(*)1>0. Сравнивая эти отношения, отрезок [0 , а'] можно разделить на несколько кусков, на каждом из которых одно из них принимает ми­ нимальное значение. Из полученных отрезков выбирается тот, левой границей которого является точка а = 0. На этом отрезке осуществляется преобразование симплексной таблицы. Полученные на последующих шагах симплексные таблицы уже целиком будут зависеть от параметра я. Каж­ дый элемент таблицы выражается в виде дробно-линейной функции от я:

ау + г

где величина « у + 2 представляет собой значение опре­ делителя матрицы, состоящей из базисных векторов — столбцов.

Так как

х 1о(0 ) = дг>‘° 5=0, i = l , 2 ,..., т,

то область базисности данной основы определяется при помощи знаков величин у и х'-10. В связи с этим в отдель­ ности рассматриваются следующие случаи:

я) у = 0 ; б) у ф 0.

251

В случае а) выполняется неравенство

где отношения в правой части неравенства берутся по всем

Если zy^>0, то правая граница области базисности дан­ ной основы определяется системой неравенств (16.6). Если

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

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

На последующих областях изложенный анализ коэф­ фициентов выражения (16.5) повторяется со следующим

вая граница изучаемой области (т. е. верхняя граница предыдущей области).

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

282