Сравнивая равенства (2.9) и (2.10) с равенством (2.8), заключаем, что при любом 1Л системе ограничений (2.8) удовлетворяет решение
=(xiО,...0)
Х =(xi - ар..х - а,0,...0).
Учитывая, что >0 (у = !,...,«) можно подобрать настолько малым, что все компоненты решений X, и Х будут неотрицательными. В
результате Х и Х будут допустимыми решениями задачи, при этом точка X - + 2) будет лежать на отрезке, соединяющем точки Х, ,
, и следовательно, X не является угловой. Следовательно, векторы i, линейно независимы, и теорема доказана.
Используя утверждения теорем (2.13) и (2.14), можно сделать следующий вывод: если задача линейного программирования имеет решение, то оно совпадает с одним из допустимых базисных решений.
Глава 3 СИМПЛЕКСНЫЙ МЕТОД
3.1. Метод исключения Жордана-Гаусса
Большинство из существующих численных методов решения задач линейного программирования используют идею приведения системы линейных уравнений
а.х. + алХл +... + ах„ = А ,
mi I mz Iтп п m
записываемой в матричном виде как Ах = Ь ,к более приемлемому виду с помощью преобразований Жордана-Гаусса. Суть этих преобразований состоит в следующем [47].
В первом уравнении системы отыскивается коэффициент ац , отличный от нуля. С помощью этого коэффициента обращаются в нуль коэффициенты при переменной x,2 в остальных уравнениях системы. Для этого первое уравнение умножается на число а / а,, и прибавляется к
уравнению с номером г (г = 2,3, w). Затем первое уравнение делится на число а,- . Это преобразование называется элементарным преобразованием, которое не меняет множества решений системы. Полученная эквивалентная система обладает тем свойством, что переменная х, присутствует только в первом уравнении и притом с коэффициентом 1. Переменная хц называется базисной переменной. Аналогичная операция совершается поочередно; при этом каждый раз преобразуются все уравнения и пополняется список базисных переменных. В результате применения метода Жордана-Гаусса либо устанавливается, что система уравнений несовместна (все коэффициенты очередного рассматриваемого уравнения нулевые, а свободный член отличен от нуля), либо выявляются и отбрасываются все уравнения, у которых все коэффициенты и свободный член равны нулю. 50
При этом итоговая система уравнений имеет вид
где or = { 2,...,/} - список номеров базисных переменных,
{hh-h} - множество номеров небазисных переменных. Здесь к- ранг матрицы А. Полученную систему уравнений будем называть приведенной системой, соответствующей множеству а номеров базисных переменных. В качестве базисных переменных х,,, х,2, хц может служить лишь такой набор, для которого соответствующая система а\ а, а столбцов матрицы А линейно независима.
Приведенная система уравнений удобнее первоначальной, поскольку дает явное описание множества всех решений. Давая небазисным переменным Xj,j € СО произвольные значения, вычисляем значение остальных (базисных) переменных по формулам:
Xi =а,о - Z ajXjJea,
jeo)
таким образом, получаем любое решение системы. В частности, одно из решений задается вектором
x=(xX2...,x,),гдe ( О, если i G со.
Пусть ранг матрицы А равен т. Если обозначить через А =(aa...,a"") матрицу, составленную из столбцов матрицы А, соответствующих базисным переменным, то А квадратная невырожденная матрица размера тхт, В этом случае преобразование Жорда-на-Гаусса состоит в умножении исходной матрицы на матрицу А~, и приведенная система имеет вид:
А-АхА-Ъ.
Докажем справедливость приведенного равенства. Для этого обозначим элементы шуп матрицы АА через J3,j,i=\, ..., w;7 = 1,2, ..., п. По