Обозначим через Bi матрицу, составленную из этих векторов, тогда Вс\ - квадратная (т + \)х(т + 1) матрица, имеющая обратную.
Назовем матрицей перехода к новому базису матрицу, столбцами которой являются координаты векторов нового базиса в их разложении по векторам старого.
Если У"- единичный орт пространства В\ г = 0, 1, 2, т, то матрица перехода от базиса (3.11) к базису (3.20) имеет вид:
/а л
0 1/-1
e = (F,F,...,F ,
/+1т
V ,...,К).
При этом = аб- При указанной смене базиса любой вектор у е 1, координаты которого в базисе (3.11) выражались вектором z, то есть у = В, в новом базисе будет иметь координаты, описываемые
вектором Z, который легко находится подстановкой Bq = Bq\Q\ У = 5ai(6~). то есть Z = e"z.
Следовательно, новые координаты столбцов матрицы U выражаются формулами:
а>
7 = 0,1,2, ...,и.
через и ,
Обозначим матрицу, состоящую из столбцов
т.е.и =Q~U или QU =и. Чтобы явно вычислить элементы матрицы, поступим следующим образом.
Для строк матриц С/ и С/ можно написать соотношение
ao=Ul,ai=UV,i ст, / =(3.21)
Щ = и V, at= UV,aQ = U Л / е ст, / < / Ф s.(3.22)
Тогда а, - ai={U-U )V или
а/ -щ = и (Q - I)V, I = О, / е а, / = /„ / * s.
где /- единичная {т + 1)х(?и + 1) матрица. Из явного вида Q следует, что
{Gl-Dy = (<ySS\>-yi)
для любого У = (У0,У\, ...,yt, Ут) 3*
(3.23)
(3.24)
в частности
(Q-I)r=a,,Vjir,rt(3.25)
(Q-I)V=(ask-\)l(3.26)
(Q-PlVaokV.(3.27)
Используя (3.23) и (3.26), получим
as-ai, =(ask-l)UV={ask-\)a,,
откуда
OLs,(3.28)
из (3.23), (3.25) и (3.28) получим
а,- а, = a,kU V= а,,а,= а.(3.29)
В частности из(3.27) получим
. ccQ=ao-as(3.30)
Очевидно, что ask О, так как в противном случае матрица Q - вырожденная, т.е. (3.19) не базис.
Смысл преобразований (3.28)-(3.30) ясен: к i-й строке матрицы U прибавляется строка с таким коэффициентом I ask, чтобы элемент dj
стал равен нулю, после чего строку as делим на ask, добиваясь равенства
ajj = 1. В результате столбец
В матрице U оказывается ортом V
пространствакак и должно быть в симплексной таблице, так как
вектор теперь уже входит в базис и занимает в нем место с номером t.
На основании рассмотренной симплекс-таблицы, дадим описание вычислительной схемы симплекс-метода.
Пусть имеется начальная симплексная таблица С/.
Этап 1. Проверяем выполнение неравенств А, > О,у = 1,2, ..., п. Если эти неравенства справедливы, то план х, вычисляемый по формуле (3.9), - оптимален. В противном случае ищем индекс к,\<к<п, для которого Ajk< 0.
Этап 2. Проверяем выполнение неравенства < 0. Если все координаты atk вектора неположительны, то вычисления прекращаются, так 68
как исходная задача maxАх = Ь, х>0 вида не имеет решения. В
противном случае ищем такой индекс S, что аА: > О и aso I oisk cl,o I a,k для всех /, для которых aik> 0.
Этап 3. По формулам(3.28)-(3.30) строим новую симплексную таблицу и, которую принимаем за начальную и возвращаемся к этапу 1.
Последовательность выполнения этапов 1-3 называется итерацией симплекс-метода.
Подчеркнем основные свойства симплекс-метода:
1.Конечность итераций в симплекс-методе и каждая из итераций заключается в нахождении очередной крайней точки, на которой значение целевой функции не хуже, чем на предыдущей.
2.Все вычисления симплекс-метода совершаются либо сравнением элементов симплексной таблицы с нулем, либо вычисление по формулам этапа
3.В этом состоит достоинство симплекс-метода, так как при решении практических задач число необходимых итераций велико, и поэтому время выполнения компьютером одной итерации играет важную роль.
3.4. Выроненные задачи линейного программирования
Рассмотрим ситуацию, когда зада-
max с,х,.
Ах = Ь;
х>0(3.31)
обладает вырожденными опорными планами, что приводит к определенным трудностям. Напомним, что
Базисное решение, в котором хотя бы одна из основных переменных равна нулю, называется вырожденным.
Если в процессе работы симплекс-метода появляется вырожденное базисное решение (вырожденный опорный план), то возможна ситуация зацикливания, т.е. на очередной итерации симплекс-метода при переходе к новому базисному решению не происходит улучшение значения целевой функции.
опорный план является вырожденным, если равна нулю хотя бы одна основная переменная. Имея начальную симплексную таблицу С/, соответствующую данному базису планах, можно осуществить все три этапа симплекс-метода, как они описаны в предыдущем разделе.
При этом выбор индекса S может оказаться таким, что xs = 0. Тогда новый опорный план х\ определяемый по формулам (3.28), (3.29), совпа-