Методы оптимизации. Рейзлин В.И. - 34 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

Составители: 

Рубрика: 

3.2 Поиск разрешающего элемента симплексной таблицы
После составления табл.1 анализируется
1m
-я строка. Если для всех
n
,
,
2
,
1
j
значения оценок
jj
CZ
меньше нуля, то опорный план
0
X
оптимальный и минимальное значение линейной функции равно
0
Z X . В
противном случае можно, включив в базис вектор, соответствующий
положительной оценке, построить другой опорный план, которому соответствует
меньшее значение линейной функции.
Если положительных оценок несколько, то в базис должен быть включен
вектор, которому соответствует
jjj0
CZmax
, так как уменьшение значения
целевой функции происходит именно на величину
jjj0
CZ
. Максимум
берется по тем
j
, для которых оценка положительна и
j0
определяется для
каждого
j
. Это дает возможность на данном шаге перейти к вершине
многогранника решений, связанной с наибольшим уменьшением линейной
функции.
Пусть в базис включается
k
-й вектор, тогда исключается из базиса тот
вектор, которому соответствует
ikik0
xxmin
0x
ik
. Пусть это условие
выполняется для вектора базиса
l
A . Элемент
lk
x называется разрешающим, а
столбец и строка, на пересечении которых он находится, – направляющими.
Новому опорному плану соответствует базис, состоящий из векторов
m1lk1l1
,,,,,, AAAAA
.
3.3 Переход к новому опорному плану
Чтобы вычислить новый опорный план и проверить его на оптимальность,
необходимо все векторы разложить по векторам нового базиса. Новый опорный
план и разложения векторов в новом базисе при
n
,
,
2
,
1
j
определяется по
формулам:
ji
x
x
x
li
x
x
xx
lk
ij
ij
lk
ij
ijij
, (3.3)
которые являются формулами полных исключений Жордана-Гаусса.
Таким образом, чтобы получить коэффициенты разложения векторов
0
A ,
j
A
n,,2,1j
по векторам нового базиса, значения оценок нового опорного
плана и значения линейной функции, нужно разделить все элементы
направляющей строки на разрешающий элемент и, производя одно полное
преобразование по методу Жордана-Гаусса, с помощью этой преобразованной
строки составить новую симплексную таблицу.

Страницы