Линейное программирование. Задача линейного программирования (ЗЛП), страница 6

Пусть ищем max z. И пусть не все числа индексной строки неотрицательны. Например, отрицателен индекс с номером j (< 0). Тогда значение целевой функции z не максимально и его можно увеличить, увеличив x_j. При этом x_j перестанет быть равным нулю. Но число равных нулю переменных x_i должно остаться прежним и равным n-m. Значит, вместо x_j должна обратиться в ноль одна из базисных переменных, иначе такой набор х не будет опорным планом. А х_j станет базисной переменной вместо x_i. Выполним такое преобразование.

Одно из уравнений (6.6) преобразуем так, чтобы у x_iкоэффициент стал равен 1. Пусть это будет, например, i-ое уравнение (i-ая строка симплекс-таблицы). Это уравнение имеет вид:

x_i + a_i,m+1 x_m+1 + … + a_i,j x_j +… + a_inj x_n = b_i.                                              (6.8)

Сделаем х_i свободной переменной, а х_j - базисной. Для этого надо, чтобы коэффициент при х_j  стал равен 1, для чего разделим все уравнение на а_ij. Для наглядности переменную х_j поменяем ее местами с х_i. Получаем уравнение

                                                (6.9)

Строка симплекс-таблицы, в которой элементы преобразуются по формуле (6.9), называется ключевой строкой.

Установим, какую из строк симплекс-таблицы можно избрать в качестве ключевой.

Учитывая, что свободные переменные x_m+1= x_m+2 =…= x_n = 0, имеем x_j = b_i ¤a_ij. Для того, чтобы выполнялось условие x_j > 0, должно быть a_ij > 0. При выборе ключевой строки это требование надо учитывать.

Чтобы системе ограничений придать предпочтительный вид, в остальных уравнениях (и строках симплекс-таблицы), кроме i-ой, переменная x_j должна исчезнуть. Рассмотрим одну из таких строк, например, m-ю:

                           (6.10)

Исключим х_j, для чего подставим на место х_j в уравнение (6.10) вытекающее из  (6.9) выражение:

                                              (6.11)

Получим

         (6.12)

Теперь, чтобы при x_m+1= x_m+2 =…= x_n = 0 обеспечить положительное значение x_m , надо, чтобы дробь  была возможно меньше. Следовательно, в качестве i-ой строки надо выбирать такую, в которой  минимальное.

В связи с заменой базисной переменной в целевой функции в результате подстановки (6.11) в (6.7) вместо х_j возникает х_i:

                (6.13)

Поскольку  - свободные переменные, которые в опорном плане равны нулю, получаем

.

6.6. Правила преобразования симплекс-таблицы при переходе от опорного плана к нехудшему

Если исходный опорный план оказался неоптимальным (см. раздел 6.3), необходимо перейти к другому, нехудшему плану, выполнив преобразования в симплекс-таблице.

Порядок перехода от исходного опорного плана к нехудшему.

1. При поиске максимума целевой функции в индексной строке найти наибольшее отрицательное число. При поиске минимума - в индексной строке найти наибольшее положительное число. Этим определяется ключевой столбец.
2. В ключевом столбце найти положительное число, дающее меньшее частное от деления на него соответствующего b_i из столбца А₀. Этим определяется ключевая строка.
3. В ключевой строке все числа разделить на ключевое число.
4. Остальные числа преобразовать, руководствуясь формулой

, где a_ij - ключевое число.

5. В столбик БП симплекс-таблицы ввести новую переменную в ту строку, которая была ключевой, а в столбик с_Б - ее коэффициент из целевой функции.

Расположение элементов формулы в симплекс-таблице показано в следующей схеме, изображающей фрагмент таблицы

Ключевая строка	aij	…	ain
	…		…
Строка m	amj	…	amn
	Ключевой столбец		Столбец  m

Напишем еще мнемоническую формулу преобразования чисел симплекс-таблицы.

6.7. Особые случаи.

Альтернативный оптимум.

Если в индексной строке симплекс-таблицы, содержащей оптимальный план, имеется лишний ноль (в столбике свободной переменной), то ЗЛП имеет бесконечно много равноценных оптимальных планов.

Докажем это утверждение.

Пусть ∆_k = 0, где k - номер свободной переменной x_k. Введем x_k в базис, то есть сделаем ее базисной переменной. Новое значение целевой функции найдем по формуле (6.13). Получим

.