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

(для всех планов Z-задачи) вытекает, что

для всех планов X-задачи.

Итак, решение Х-задачи сводится к вычислению оптимального плана Z-задачи. Размеры Х-задачи равны М X N. Z-задача содер­ жит меньше ограничений Д4Х+ 1, но во много раз больше перемен­ ных N2. Количество N2 вершин многогранника согласно формулам (5.2.52), (5.2.53) при немалых размерах второго блока — астроно­ мическое число.

2. Рассмотрим общую схему решения Z-задачи. Будем решать Z-задачу при помощи второго алгоритма метода улучшения плана. Предположим известными векторы базиса некоторого опорного плана Z-задачи. В соответствии с правилами метода улучшения плана поря­ док вычислений определяется величинами Av оценок векторов усло­ вий относительно текущего базиса. При использовании второго алго­ ритма оценки Av вычисляются по формуле

где индекс / пробегает номера векторов базиса. Опорный план, отве­ чающий рассматриваемому базису, оптимален, если все Av неотри­ цательны. Однако подобная форма признака оптимальности плана неэффективна для Z-задачи, так как она предполагает известными все векторы ри, число которых, как правило, чрезвычайно велико. Данциг и Вульф указали (и в этом основное содержание метода раз­ ложения) практически приемлемый путь проверки оптимальности опорного плана Z-задачи и выбора вектора, подлежащего включению в базис, если исследуемый план неоптимален. Рассмотрим этот способ.

Выделим последнюю (М + 1)-ю компоненту вектора Л, отвечаю­ щую условию (5.2.61) Z-задачи, и обозначим ее через к. Таким обра­ зом, вектор А можно записать в виде:

189

Учитывая обозначения (5.2.64) и (5.2.68), перепишем формулы (5.2.67) и (5.2.66) для относительных оценок условий задачи и векто­ ров условий в следующем виде:

Каждому опорному плану Z-задачи можно привести в соответ­ ствии Хд-задачу, в которой требуется вычислить максимум линей­ ной формы

при условиях (5.2.52) — (5.2.53). Оптимальное значение линейной формы (5.2.73) может может быть использовано для проверки опти­ мальности опорного плана Z-задачи, обусловившего соответствую­ щую Хд-задачу.

Действительно, значение линейной формы на опорных планах

Хл-задачи (их обозначили через xv, v = 1, У2) связано простыми соотношениями с оценками Ду векторов условий Z-задачи:

La (■^л?) ==(Сд , Ху) = {С — ЛА1, Ху) = Сху (АА1, xv).

Используя обозначения (5.2.57) и (5.2.58) и формулу (5.2.70), имеем

Аналогичное соотношение имеет место и для оптимального опор­ ного плана Хд-задачи:

Условие оптимальности опорного плана х% записывается в виде

или в силу соотношений (5.2.74) и (5.2.75)

121

Следовательно, если Л* ^э= 0, то и все Av ^ 0. Это значит, что для проверки оптимальности опорного плана Z-задачи достаточно решить Хд-задачу и сравнить оптимальное значение ЕЛ(Х) с оцен­ кой X. (Заметим, что неравенство А* > 0 невозможно, так как под­ ставляя в выражение (5.2.76) вместо v номер любого из базисных

Исследуемый опорный план Z-задачи оптимален, если

L a (4) =^

Если же La(4 ) > следует перейти к соседнему опорному плану Z-задачи с большим значением линейной формы (5.2.59). Из неравен­ ства (5.2.76) видно, что вектор (обозначим его рк), отвечающий опти­ мальному опорному плану х%, имеет наименьшую относительную оценку

А* = Х —ЬА (4) < 0 .

Таким образом, в базис Z-задачи вводится вектор' рк, для которого

Соответствующий коэффициент линейной формы (5.2.59) равен

Все последующие расчеты, связанные с решением Z-задачи (про­ верка задачи на неразрешимость; вычисление элементов матрицы, обратной матрице очередного базиса и т. д.), ведутся в соответствии с правилами второго алгоритма метода последовательного улучше­ ния плана [80].

Обратим еще раз внимание на то, что для решения Z-задачи (и, следовательно, для получения оптимального плана X-задачи) нет необходимости знать заранее ее матрицу условий. Необходима лишь информация о векторах условий, входящих в начальный базис Z- задачи. Компоненты векторов условий, подлежащих включению в ба­ зис для улучшения плана, и соответствующие коэффициенты линей­ ной формы вычисляются по формулам (5.2.77) и (5.2.78) по мере необ­ ходимости в процессе решения задачи. Для решения исходной задачи приходится, как правило, вычислять лишь очень небольшую часть опорных планов Х2-задачи и, следовательно, весьма небольшую часть векторов условий Z-задачи.

Раньше условия Х-задачи были разбиты на два блока с матри­

Х-задачи (5.2.50) — (5.2.53), можно повторить относительно Х2-за- дачи (5.2.50), (5.2.52), (5.2.53). Блок с матрицей А2 может быть раз­ бит на две части с М2 и (М — Мх) — М2 условиями соответственно. Метод разложения может быть применен и к решению Х2-задачи (вернее, к решению каждой из Хд-задач). Продолжая далее анало­ гичные рассуждения, .приходим к следующему выводу. Решение

122

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

3. В процессе построения Z-задачи считалось что область, опре­ деляемая условиями (5.2.52), (5.2.53), ограничена. В противном случае формула (5.2.54) теряла смысл. Незначительная модификация позволяет отказаться от принятого допущения.

Вобщем случае система ограничений (5.2.52), (5.2. 53) выделяет

впространстве переменных X выпуклое многогранное множество G. Система ограничений вида (5.2.52), (5.2.53) имеет ранг, равный числу компонент вектора X. Следовательно, по теореме 2.7 [80, с. 115—116]

любая точка множества G может быть представлена в виде

Здесь xv — вершины многогранного множества G при v = 1, N3 и направляющие векторы неограниченных ребер этого множества

при v = А73 11 N2. В рассматриваемом случае каждая точка множества G уже не является выпуклой комбинацией векторов xv.

Чтобы сохранить эквивалентность X- и Z-задач, следует заменить

Таким образом, в общем случае Z-задача сводится к максими­ зации линейной формы

N ,

У nvZv

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

У< Рv%v— В 1;

V = 1

zv^ 0 , (v = l, О ,

где

Pv = (.. )i Pv = AlX'v, Oy— (C, xv).

123

Оценка Av вектора условий pv относительно базиса Z-задачи вычис­ ляется из соотношения

обоснование которого ничем не отличается от приведенного выше вывода формулы (5.2.74).

Поскольку многогранное множество G условий Х2-задачи, вооб­ ще говоря, не ограничено, решение очередной ХА-задачи может закончиться случаем 1° или 2°. Случай 1° соответствует либо реше­ нию Z-задачи, либо требует включения в очередной базис вектора pv с номером v sg Na (т. е. вектора, отвечающего вершине множе­ ства G). Случай 2° требует продолжения решения Z-задачи, причем

в очередной базис должен быть включен вектор pv с номером v > Na (т. е. вектор, отвечающий неограниченному ребру многогранного множества G).

Приведем соответствующие рассуждения. В случае 1° опреде­

Действительно, пусть неограниченное ребро, соответствующее xv, исходит из вершины xVo. Если LA (xv) > 0, то значение линейной формы LA(xVo + pxv„) = L \ (xv0) + pEA(*v) на плане xVo + pxv

неограниченно растет с увеличением коэффициента р.

Таким образом, нарушение хотя бы одного из неравенств (5.2.84) противоречит разрешимости Хл-задачи (рассматривается случай 1°).

Это значит, что в случае 1° векторы условий pv, отвечающие

неограниченным ребрам многогранного множества G (v = Na+ 1, N2), имеют неотрицательные оценки. Следовательно, в случае 1°

векторы ру (v = Nз + 1 , N2) не следует вводить в базис. Равенство Ау = 0 означает, что Z-задача решена. Если Ду < 0,

то в очередной базис вводится вектор р*, соответствующий вершине Ху многогранного множества G.

Случай 2°, который может встретиться при решении ХА-задачи, означает, что на какой-то итерации оценка Д<л>некоторого вектора

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

124