Сборник задач по линейному программированию (стр. 2 )

В этом случае за базисными переменными необходимо принять а за свободные и тогда:

Такие системы уравнений (6) и(6/) определяют общее решение исходной СЛУ, а решения получаемых при произвольных значениях свободных переменных называют частными решениями. Частное решение системы, получаемое при свободных переменных, равных нулю, называют базисным решением или решением, приведенным к единичному базису. В этом случае частные значения базисных переменных получаются равными свободным членами соответствующих уравнений (строчек).

В нашем случае для матрицы (4):

 

для матрицы (4/):

 

       Как получить матрицы (4), (4/), (5), (5/)?

               Процедура Жордана-Гаусса.

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

               

       Поэтому процедура Жордана-Гаусса излагается с учетом требования неотрицательности переменных.

Пусть имеется СЛУ типа (1), расширенная матрица которой имеет вид (2). Пусть в этой системе все свободные члены – неотрицательные величины. В противном случае умножением обеих частей строки на  -1 можно сделать свободный член положительным. Выберем столбец, в котором имеется хоть бы один положительный элемент. Назовем его разрешающим. Если в разрешающем столбце несколько положительных элементов, то за разрешающий элемент следует взять тот из них, для которого отношение соответствующего свободного члена к этому элементу столбца наименьшее, т. е. находим для всех положительных столбца   .

Соответствующая строка называется разрешающей.

Переходим от исходной матрицы к другой, равносильной. При этом:

а)        элементы разрешающей строки исходной матрицы делятся на разрешающий элемент и записываются строкой в новой матрице;

б)  элементы разрешающего столбца исходной матрицы заменяются в новой матрице нулями, за исключением разрешающего элемента, который заменяется на единицу;

в) все остальные элементы пересчитываются по правилу прямоугольника:

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

 

         

Тогда в новой матрице:

Аналогично, чтобы пересчитать свободный член ( - разрешающий элемент), необходимо воспользоваться формулой.

 

         

При этом, если все свободные члены исходной СЛУ неотрицательны, то после преобразования Жордана-Гаусса они останутся неотрицательными.

Проведя несколько подобных преобразований можно привести матрицу исходной СЛУ к треугольному или трапецеидальному виду и найти базисное решение.

Если найдено хоть одно неотрицательное базисное решение, то с помощью преобразования Жордана-Гаусса можно найти другое неотрицательное решение, если таковое имеется.

Пример. Найти неотрицательное базисное решение СЛУ.

Умножим 1-е и 5-е уравнения на  -1. Получим:

Запишем матрицу СЛУ:

В любом столбце есть положительные элементы, поэтому любой столбец может быть разрешающим. Например, столбец . Для положительных элементов этого столбца составляем симплексное отношение:

Это первая строка. Следовательно, первая строка – разрешающая.

Элемент - разрешающий. Строим новую таблицу.