- •Киевский университет имени Тараса Шевченко
- •Общие рекомендации к использованию программного обеспечения
- •Элементарные преобразования матриц. Метод гаусса
- •Задача линейного программирования. Симплекс-метод Постановка задачи линейного программирования в стандартной форме (сзлп).
- •Задача линейного программирования. Модифицирован симплекс-метод.
- •Задача линейного программирования. Двойственный симплекс-метод
- •Транспортная задача. Метод потенциалов
- •Транспортная задача с ограниченными пропускными
- •Способностями. Метод потенциалов
- •Постановка транспортной задачи с ограниченными
- •Пропускными способностями (тзо).
- •Задача о кратчайшем пути на сети. Метод минти
- •Задача о максимальном потоке на сети. Метод форда-фалкерсона
- •Задача целочисленного линейного программирования. Метод гомори-1
- •Задача частично целочисленного линейного программирования. Метод гомори-2 Постановка частично целочисленной задачи линейного программирования (чцзлп).
- •Задача целочисленного линейного програмування. Метод гомори-3
- •Задача частично дискретного линейного программирования. Метод дальтона-ллевелина Постановка частично дискретной задачи линейного программирования (чдзлп).
- •Задача целочисленного линейного программирования. Метод ветвей и границ.
- •Лабораторная работа 14. Задача о назначении. Венгерский метод
- •Лабораторная работа 15. Задача о назначении. Метод мака Постановка задачи такая же самая, как и в предыдущем разделе (14.1–14.4).
- •6. Если каждый столбец матрицы расходов имеет элемент с отметкой *, тогда задача об оптимальных назначениях решена. Иначе переходим к следующему пункту.
- •Матричные игры. Связь с задачей линейного программирования. Метод брауна-робiнсон
- •Лабораторная работа 17. Методы одномерной оптимiзации
- •Лабораторная работа 18. Задача выпуклого квадратичного программирования. Квадратичный симплекс-метод
- •Задача безусловной оптимизации. Метод самого быстрого спуску
- •Лiтература
Элементарные преобразования матриц. Метод гаусса
Постановка задачи.
Решить систему линейных алгебраических уравнений
a11x1 + . . . + a1n xn = a10
. . . . . . . . . . . . . . . . . . . . . . (1.1)
am1x1 + . . . + amnxn = am0
что означает:
определить, совместимая данная система ли (то есть, имеет ли она хотя бы одно решение);
если система совместимая, то, имеет ли она единственное решение, или таких решений множество;
найти решение, если он единственный, и найти общее решение в случае существования множества решений.
Вопрос совместимости системы (1.1) решает теорема Кронекера-Капелли, формулировка которой такая:
Система линейных алгебраических уравнений (1.1) совместимая в том и только в том случае, когда совпадают ранги основной и расширенной матриц
-
a11
. . .
a1n
a11
. . .
a1n
a10
А =
. . .
. . .
. . .
,
A=
. . .
. . .
. . .
. . .
.
am1
. . .
amn
am1
. . .
amn
am0
При этом решение единственное тогда и только затем, когда rang(A)=n. Если же rang(A)=r<n, то обязательно найдутся такие r переменных , что исходная система (1.1) будет эквивалентной системе вида:
(1.2)
где суммирование ведется по j=1...,n, отличных от i1...,ir.
О системе (1.2) говорят, что она решена относительно переменных и имеет каноничный вид.
Общее решение системы (1.2) определяется тривиально:
(1.3)
В уравнениях (1.3) переменные xj (j отличное от i1...,ir) — свободные переменные, они могут получать произвольные значения. Каждая совокупность их значений однозначно определяет значение переменных — базисных переменных.
Метод Гаусса является основным законченным методом решить систем линейных алгебраических уравнений (1.1) и заключается в исполнении однотипных превращений исключения.
На 1-м шаге метода находят переменную в 1-м уравнении, коэффициент возле которой не равняется нулю, и исключают эту переменную из всех других уравнений. Если, например, a11 не равняется нулю, то превращения 1-го шага такие: до і-го уравнения прибавить 1-е уравнение, умноженное на число –ai1a11, i=2...,m.
В результате превращений 1-го шага система (1.1) приобретает вид:
a11x1 + a12x2 + . . . + a1n xn = a10
а22х2 + . . . + а2nxn = а20
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . (1.4)
аm2x2 + . . . + аmnxn = аm0.
На следующем шаге эта же последовательность действий применяется к части системы, что состоит из системы (1.4) без 1-го уравнения и т.д. Упомянутый процесс продолжается до тех пор, пока не будет получена система трапециевидного (в частности, треугольного) вида, или не будет подтвержден признак несовместимости системы.
Описанные превращения составляют прямой ход метода Гаусcа. При прямом ходу превращения выполняются «сверху вниз» — от первого уравнения к последнему. Обратный ход метода Гаусса составляют превращения исключения отделенных при прямом ходу базисных переменных, при этом превращения выполняются в обратном порядке: от последнего уравнения к первому — «снизу вверх».
Прямой и обратный ход метода Гаусса достал название метода полного исключения Жордана-Гаусса.
Кроме основного назначения (как метода решить систем линейных алгебраических уравнений) метод Гаусcа имеет и другие важные применения.
С помощью прямого хода метода Гаусcа можно вычислять численные определители (путем сводки определителя к треугольному виду).
Метод Жордана-Гаусcа позволяет находить обратные матрицы.
Пусть имеем некоторую невырожденную квадратную матрицу:
-
a11
. . .
a1n
A=
. . .
. . .
. . .
.
an1
. . .
ann
Построим расширенную матрицу вида:
-
a11
. . .
a1n
1
. . .
0
. . .
. . .
. . .
. . .
. . .
. . .
an1
. . .
ann
0
. . .
1
и применим к ней метод Жордана-Гауcса. Если в результате получим матрицу вида:
-
1
. . .
0
b11
. . .
b1n
. . .
. . .
. . .
. . .
. . .
. . .
,
0
. . .
1
bn1
. . .
bnn
то
-
b11
. . .
b1n
. . .
. . .
. . .
—
bn1
. . .
bnn
обратная матрица к исходной матрице А.
Программное обеспечение.
Модуль, который выполняет элементарные превращения матриц, которые лежат в основе метода Гауcса, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПО–МО.
Задание.
методом Гауcса системы линейных алгебраических уравнений, расширенные матрицы которых задаются модулем с помощью команды «Данные» главного меню (задачи №1–№9), а также следующие задачи.
методом Гаусса системы линейных алгебраических уравнений, что заданы расширенными матрицами:
1) |
2 |
-2 |
0 |
1 |
-3 |
2) |
1 |
1 |
-6 |
-4 |
6 |
3) |
2 |
-1 |
3 |
4 |
5 |
|
2 |
3 |
1 |
-3 |
-6 |
|
3 |
-1 |
-6 |
-4 |
2 |
|
4 |
-2 |
5 |
6 |
7 |
|
3 |
4 |
-1 |
2 |
0 |
|
2 |
3 |
9 |
2 |
6 |
|
6 |
-3 |
7 |
8 |
9 |
|
1 |
3 |
1 |
-1 |
2 |
|
3 |
2 |
3 |
8 |
-7 |
|
8 |
-4 |
9 |
10 |
11 |
Вычислить следующие определители:
4) |
0 |
1 |
1 |
1 |
|
5) |
1 |
1 |
6 |
4 |
|
6) |
3 |
6 |
5 |
6 |
4 |
|
1 |
0 |
1 |
1 |
|
|
3 |
1 |
6 |
4 |
|
|
5 |
9 |
7 |
8 |
6 |
|
1 |
1 |
0 |
1 |
|
|
2 |
3 |
9 |
2 |
|
|
6 |
12 |
13 |
9 |
7 |
|
1 |
1 |
1 |
0 |
|
|
3 |
2 |
3 |
8 |
|
|
2 |
5 |
4 |
5 |
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
6 |
6 |
5 |
4 |
Найти обратные к таким матрицам:
7) |
1 |
1 |
1 |
1 |
|
8) |
1 |
2 |
3 |
4 |
|
9) |
3 |
6 |
5 |
6 |
|
1 |
1 |
-1 |
-1 |
|
|
2 |
3 |
1 |
2 |
|
|
5 |
9 |
7 |
8 |
|
1 |
-1 |
1 |
-1 |
|
|
1 |
1 |
1 |
1 |
|
|
6 |
12 |
13 |
9 |
|
1 |
-1 |
-1 |
1 |
|
|
1 |
0 |
2 |
6 |
|
|
2 |
5 |
4 |
5 |
Лабораторная работа 2.