- •Элементы линейной алгебры с приложением
- •Введение
- •1. Определители
- •Определителем матрицы Вназывается число
- •2. Системы линейных уравнений
- •Рассмотрим снова систему (2). Определитель
- •3. Векторы и ленейные операции над ними
- •4. Векторы в декартовой прямоугольной системе координат. Скаряное произведение
- •Доказательство.Используя свойства 3, 4, получим
- •5. Векторное и смешанное произведения
- •Легко проверить исходя из определения векторного произведения, что
- •6. Уравнение плоскости и прямой
- •Решение. Уравнение плоскости, проходящей через точку м1имеет вид
- •7. Матрицы
- •Пусть дана квадратная матрица
- •Покажем, что
- •8. Ранг матрицы. Исследование системы линейных уравнений
- •Рассмотрим матрицу
- •Матрицы
- •Пример 2. Решить систему
- •По формулам Крамера
- •9. Линейные преобразования. Собственные векторы
- •Матрица
- •Так как 0, то1,2,3– ненулевое решение однородной системы
- •В силу следствия из раздела 8
- •В двумерном случае система (3) имеет вид
- •Замечание.Если матрица Аφлинейного преобразованияв базе диагональная:
- •10. Симметрические и ортогональные матрицы Квадратная матрица вида
- •Оказывается, что векторы 1и2перпендикулярны. В самом деле, применяя лемму, получаем
- •Матрица
- •Матрица преобразования в базе1,2диагональная
- •11. Квадратичные формы. Кривые второго парядка
- •12. Положительные матрицы
- •13. Балансовая модель
- •14. Продуктивные матрицы
- •15. Норма матрицы
- •16. Итерационный метод
- •17. Возмущение решений
- •18. Демографический рост
- •19. Регрессионные модели
- •20. Постановка транспортной задачи
- •20.1 Математическая формулировка транспортной задачи.
- •20.2 Базисное распределение в транспортной задаче
- •Вариант 5
- •Вариант 6
- •Вариант 7
- •Вариант 8
- •Вариант 11
- •21. Техника решения транспортной задачи вручную (метод потенциалов)
- •Вариант 13
- •22. Формализация производственных задач линейного программирования
- •23. Геометрическая интерпретация задач линейного программирования
- •24. Симплексный метод решения задач линейного программирования
- •24.1 Общая формулировка задачи линейного программирования
- •24.2 Заполнение симплексной таблицы по строкам
- •Симплексная таблица
- •24.3 Заполнение симплексной таблицы по столцам
- •24.4 Двойственные задачи, оценки, проблемы.
- •Ответы к вариантам:
- •25. Метод последовательных приближений (метод итерации)
- •26. Условия сходимости итерационного процесса
- •27. Оценка погрешности приближенного процесса метода итерации
- •28. Метод зейделя. Условия сходимости процесса зейделя
- •29. Оценка погрешности процесса зейделя
- •30. Привеление системы линейных уравнений к виду, удобному для итерации
- •31. Исправление элементов приближенной обратной матрицы
- •Задания для самостоятельной работы.
- •Вариант 1
- •Вариант 9
- •Экзаменационные вопросы
Вариант 11
-
D1
D2
D3
D4
Мощность
S1
7
4
1
3
60
S2
8
13
5
2
50
S3
5
9
7
5
60
S4
6
10
14
7
20
Спрос
30
70
50
40
190
Вариант 12
-
D1
D2
D3
D4
Мощность
S1
3
1
15
19
60
S2
2
5
7
14
70
S3
4
6
9
10
20
S4
7
8
13
16
50
Спрос
40
50
40
70
200
Запомните:
При составлении первого спорного плана возможен случай вырождения. Он возникает, когда все условия выполнены, а число элементов xtj будет меньше числа m+n-1.
Чтобы избежать вырождения, необходимо внести фиктивную (нулевую) поставку.
В качестве примера рассмотрим опорный план, составленный методом Северо-Западного угла.
Количество заполненных клеток должно быть равно
m+n-1=4+4-1=7
-
D1
D2
D3
D4
Мощность
S1
30
30
S2
10
10
20
S3
20
10
30
S4
20
20
Спрос
30
10
30
30
100
В нашем примере его число равно 6, т.е. мы имеем дело со случаем вырождения. Чтобы устранить его, вводим фиктивную (нулевую) поставку в любую из свободных клеток, например в клетку S2 – D4. Тогда наш опорный план будет иметь вид
-
D1
D2
D3
D4
Мощность
S1
30
30
S2
10
10
0
20
S3
20
10
30
S4
20
20
Спрос
30
10
30
30
100
Примечание
Если опорный план составлен методом «наименьшего элемента в строке (столбце)» или «наименьшего элемента в матрице», то фиктивную поставку следует вводить, в пустую клетку, которая содержит очередное минимальное значение критерия. С помощью такой простой процедуры мы избавимся от случая вырождения.
Но это лишь одна проблема. Другая же заключается в том, что на практике условие транспортной задачи, по которому сумма мощностей должна равняться суммарному спросу всех потребителей, не выполняется, т.е.
В этом случае задача называется открытой транспортной задачей.
Чтобы перейти к закрытой транспортной задаче, достаточно ввести в условия задачи фиктивного поставщика или фиктивного потребителя.
Рассмотрим задачу по таблице.
-
D1
D2
D3
D4
Мощность
S1
1
5
3
1
20
S2
4
6
2
3
10
S3
3
5
2
1
40
S4
2
4
5
2
50
Спрос
30
50
20
60
160\120
Из условия задачи видно, что суммарная мощность меньше суммарного спроса на 40 (160-120=40),т.е. мы имеем дело с открытой транспортной задачей.
Чтобы ее закрыть, введем в условия задачи фиктивного поставщика S5. Его мощность будет равна 40 т.к. в действительности такого поставщика не существует, то мы в праве считать, что расстояние до него от каждого потребителя будет равно 0.
После такого преобразования условия задачи будут выглядеть следующим образом:
-
D1
D2
D3
D4
Мощность
S1
1
5
3
1
20
S2
4
6
2
3
10
S3
3
5
2
1
40
S4
2
4
5
2
50
S5
0
0
0
0
40
Спрос
30
50
20
60
160
Проверь себя.
1. Можно ли избежать вырождения?
2. Количество заполненных клеток должно быть равно m+n?
3. Количество заполненных клеток должно быть равно m+n-1?
4. Что делать, если суммарный спрос превышает суммарные запасы?
Итак, мы получили первый опорный план. Теперь мы должны проверить, является ли он оптимальным, т.е. можно ли его улучшить, уменьшая целевую функцию
Для этой цели воспользуемся методом потенциалов.