Составители:
Рубрика:
22
Следующим важным понятием является каноническая форма систе-
мы (26). Каноническая форма системы равенств для одного базиса не
может быть канонической для другого базиса. Это следует из ее опреде-
ления. Форма системы (26) – каноническая, если в целевом уравнении
системы (26) кроме x
0
имеются только базисные переменные, а в ос-
тальных равенствах кроме базисных – только по одной небазисной пе-
ременной. Из определения следует, что система (26) – каноническая
для базиса (x
1
, x
2
). Каноническая форма нужна для определения того,
являются ли текущий базис и соответствующая ему вершина симплекса
оптимальной или нет, а также для определения ребра, по которому нуж-
но перейти к следующей вершине в случае неоптимальности текущей
вершины.
Вершина оптимальна (при поиске максимума целевой функции), если
в целевом уравнении канонической системы перед коэффициентами
всех базисных переменных стоит знак плюс. Это означает, что в опти-
мальной вершине по какому бы исходящему из нее ребру мы ни сдела-
ли пробный шаг, значение целевой функции будет уменьшаться, что
говорит о ее максимальном значении в оптимальной вершине. Если
вершина неоптимальна, то ребру с максимальным увеличением целе-
вой функции при переходе по нему в следующую вершину соответ-
ствует базисная переменная с максимальным абсолютным значением ее
отрицательного коэффициента в целевом уравнении. Сам переход точ-
ки по ребру в следующую вершину соответствует удалению этой ба-
зисной переменной из базиса и включению в него другой переменной,
значение которой в новой вершине становится равным нулю.
Для определения такой переменной для каждого равенства опреде-
ляется отношение его правой части к коэффициенту удаляемой из бази-
са переменной в левой части равенства. Равенство с минимальным зна-
чением этого отношения называется опорным, а его дополнительная
переменная принимает нулевое значение в новой вершине и входит в
состав базисных переменных. Опорное равенство переходит в канони-
ческую форму системы (26) для новой вершины без изменения, а целе-
вая функция и остальные равенства должны быть умножены на такой
коэффициент, что при сложении с опорным равенством в них исчезла
прежняя базисная переменная, которая в новой вершине была удалена
из базиса.
Таким образом получают каноническую форму системы (26) для но-
вой вершины и по ее виду делают вывод об оптимальности или неопти-
Страницы
- « первая
- ‹ предыдущая
- …
- 20
- 21
- 22
- 23
- 24
- …
- следующая ›
- последняя »
