Материал: 3376

соответствующих переменных в функции (1.1);

3)перпендикулярно вектору c строим прямую (линию уровня) с уравнением c1x1 c2 x2 m , где m – какое-либо число (удобно брать m 0 );

4)перемещаем линию уровня параллельно еѐ начальному положению (в направлении вектора c для задачи "на максимум", в противоположном направлении – для задачи "на минимум") до такого положения, при котором она будет иметь общую точку с ОДР и ОДР целиком будет находиться в одной из полуплоскостей, на которые она разбивает всю плоскость; на прямой, имеющей такое положение (опорной прямой), и будет находиться точка (точки), в которой (которых) функция (7.1) достигает максимума или минимума.

2. МЕТОД ГАУССА-ЖОРДАНА РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ

Рассмотрим систему линейных уравнений

числа.

Опишем кратко метод Гаусса-Жордана решения этой системы уравнений. Выбираем любой отличный от нуля коэффициент при неизвестной. Этот коэффициент назовем ключевым элементом, эту неизвестную – главной неизвестной. Совершаем преобразование Гаусса-Жордана: соответствующее уравнение делим на ключевой элемент (в том случае, если он отличен от единицы); главную неизвестную исключаем из всех остальных уравнений системы. В полученной системе уравнений выбираем отличный от нуля коэффициент (новый ключевой элемент) при неизвестной (новой главной

8

неизвестной) в любом из уравнений, не совпадающих с тем уравнением, в котором главная неизвестная имеет коэффициент 1, затем повторяем преобразование Гаусса-Жордана, и так далее (см. пример 8.1). При выборе очередного ключевого элемента нужно, чтобы он находился в уравнении, не совпадающем с одним из тех уравнений системы, в которых главные неизвестные имеют коэффициент 1. Процесс преобразований останавливаем тогда, когда такой выбор окажется невозможным. В результате получаем систему уравнений, эквивалентную исходной и дающую ее решение.

Этот метод удобно применять в матричной форме, записав расширенную матрицу

системы уравнений (2.1) и проводя соответствующие преобразования ее строк. Метод Гаусса-Жордана можно применять также к системам линейных уравнений, в которых количество неизвестных не совпадает с количеством уравнений. При этом строку и столбец, в которых расположен ключевой элемент, будет называть соответственно ключевой строкой и ключевым столбцом.

3. БАЗИСНЫЕ РЕШЕНИЯ СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ

Рассмотрим систему линейных уравнений

в которой число неизвестных больше числа уравнений ( n m). Предположим, что эта система уравнений может быть разрешена относительно каких-то m

разрешенной относительно неизвестных x1, x2 ,..., xm .

Неизвестные, относительно которых разрешена система уравнений, называются базисными. Совокупность базисных неизвестных образует

базисную систему неизвестных или, короче, базис. Если выбрана базисная система неизвестных, то остальные неизвестные называются свободными. Свободным неизвестным можно давать произвольные значения и находить соответствующие значения базисных неизвестных. Таким образом, система уравнений (3.1) имеет бесчисленное множество решений. Решение системы (3.1), которое получается при нулевых значениях свободных неизвестных, называется базисным. В нашем случае x1, x2 ,..., xm – базис для системы уравнений (3.1). Придав свободным неизвестным (в системе (9.2)) нулевые значения, получаем базисное решение: x1 f1 , x2 f2 ,…, xm fm ,

xm 1 0 ,…, xn 0 .

Базисное решение называется невырожденным, если значения всех базисных неизвестных в нѐм отличны от нуля. В противном случае базисное решение называется вырожденным.

Система уравнений (3.1) имеет лишь конечное число базисных решений,

не превосходящее Cnm .

Для нахождения всех базисных решений системы (3.1) можно воспользоваться методом последовательного замещения. Опишем кратко этот метод.

Применив к системе (3.1) метод Гаусса-Жордана, мы получаем первый базис (как совокупность главных неизвестных) и соответствующее базисное решение. Для перехода к другому базису и соответствующему ему базисному решению применяем преобразование Гаусса-Жордана к системе уравнений,

10

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

4. ДОПУСТИМЫЕ БАЗИСНЫЕ РЕШЕНИЯ СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ

Рассмотрим систему линейных уравнений (9.1), для которой выполнены предположения, сделанные в теоретической части предыдущей лабораторной работы.

Решение системы уравнений (3.1) называется допустимым, если значения всех неизвестных в нѐм неотрицательны.

Пусть нам известно невырожденное допустимое базисное решение

Приведем правило перехода методом последовательного замещения от данного невырожденного допустимого базисного решения к другому допустимому базисному решению.

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

11

свободной неизвестной, в котором есть хотя бы один положительный элемент. После этого для положительных элементов his этого столбца следует вычислить отношения к ним правых частей fi . Тот номер, для которого

отношение fi является наименьшим, и будет номером ключевой строки. Тогда

his

преобразование Гаусса-Жордана приведет к новому допустимому базисному решению.

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

5. СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО

ПРОГРАММИРОВАНИЯ

Каноническая задача линейного программирования (КЗЛП) состоит в нахождении максимума (или минимума) линейной функции

Здесь X обозначает набор переменных x1 , x2 , …, xn , функцию (5.1) можно

называть целевой функцией.

Любое решение системы уравнений (3.1), удовлетворяющее условиям неотрицательности (5.2), называется планом канонической задачи линейного программирования. Любое допустимое базисное решение системы уравнений (3.1) называется опорным планом данной задачи. План КЗЛП, при котором линейная функция (5.1) принимает максимальное (или минимальное для задачи на минимум) значение, называется оптимальным.

12