- •1)Решение системы лау методом Жордана-Гаусса
- •2)Математическая модель задачи об использовании сырья
- •3)Математическая модель задачи составления рациона
- •4)Свойство решений задачи лп(теорема о max(min) целевой ф-ции)
- •Алгоритм симплекс метода
- •10 Метод искусственного базиса
- •17.Целочисленное программирование.
- •18.Метод Гомари
- •19.Транспортная задача(мат.Модель,определения)
- •20.Транспортная задача(постр.Первонач.Опорн.Плана)
- •21. Транспортная задача (метод потенциалов).
- •22. Транспортная задача (открытая модель).
- •23. Математическая модель об оптимальном назначении.
- •24. Алгоритм решения задачи об оптимальном назначении.
- •33.Математ.Модель задачи о кратчайшем пути в сети.
- •34.Алгоритм нах.Кратчайшего пути из источника во все вершины сети.
- •35.Нижняя и верхняя цена игры.
- •36.Игры с седловой точкой.
1)Решение системы лау методом Жордана-Гаусса
О1. Система векторов v1,v2..vk линейного пространства V наз. линейно зависимой, если сущ. такие числа α1,α2..αK не все равные 0, что α1v1+α2v2+..α k v=0. Если равенство вып. только при нулевых значениях α1,α2..αK ,то векторы наз. линейно независимые. Максимальные линейно независимые системы наз. базисом.
Пример1. v1=(1,0,0,..0)
v2=(0,1,0,..0)
v3=(0,0,1,..0) - стандартный базис в n-мерном пространстве Vn
…
vn =(0,0,0,..1)
Алгоритм метода Жордана Гаусса
Рассм. систему линейных уравнений a11x1+a12x2+..+a1n xn = b1
a21x1 +a22x2+.. a2n xn = b2
…
am1 x1 + am2 x2 +..+ amn xn = bm
1)Выписываем расширенную матрицу к системы и в первой строке матрицы находим ненулевой элемент a1k ≠0. Делим первую строку на элемент a1k ,и проводя элементарные преобразования строк, обнуляем все остальные элементы k-столбца.
2) во второй строке полученной матрицы находим ненулевой элемент a2l. Делим вторую строку матрицы на эл-т a2L и с помощью элементарных преобразований строк обнуляем все остальные элементы L–столбца матрицы.
и т.д.
В результате преобразований матрица сведется к виду А ~
Тогда если хотя бы одно из чисел b k+1 ,..bm ≠0,то система не имеет решения. Впротивном случае сист. имеет решение. При этом неизвестные хk+1,..хm объявляем свободными, и неизвестные х1,..хk выражаем через свободные. Если все свободные неизвестные взять равными 0, то получим частные(базисные) решения. X = (b1,b2,..bk,0,0)
Пример 2. Найти несколько базисных решений уравнения
Решение:
базис |
х1 |
х2 |
х3 |
х4 |
b |
х4 |
1 3 1 |
1 -1 -3 |
5 -3 -13 |
1 1 -1 |
24 0 -48 |
х4 |
1 2 2 |
1 -2 -2 |
5 -8 -8 |
1 0 0 |
24 -24 -24 |
х4 |
1 2 0 |
1 -1 0 |
5 -8 0 |
1 0 0 |
24 -24 0 |
х4 х1 |
0 1 |
2 -1 |
9 -4 |
1 0 |
36 -12 |
х4 х2 |
2 -1 |
0 1 |
1 4 |
1 0 |
12 12 |
х3 х2 |
2 -9 |
0 1 |
1 0 |
1 -4 |
12 -36 |
3я строка убирается
Х1*=(-12,0,0,36)
Х2* =(0,12,0,12) Х3*=(0,-36,12,0)