- •Элементы линейной алгебры с приложением
- •Введение
- •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
- •Экзаменационные вопросы
20. Постановка транспортной задачи
Предположим, имеется несколько предприятий-производителей. Они вывозят готовую продукцию на заводы-потребители. Перевозимая продукция должна быть однотонной и взаимозаменяемой.
Поставщики находятся от потребителей на различном расстоянии.
Количество продукции в цехах-изготовителях будем именовать мощностью.
Потребность цехов-потребителей в заданной продукции будем называть спросом.
20.1 Математическая формулировка транспортной задачи.
Пусть заданы векторы Si,Djиcij, где
Si– мощностьi-го цеха-изготовителя (i=1,…,m);
Dj– спросj-го цеха-потребителя (j=1,…,n);
cij– расстояние между каждымi-м поставщиком иj-м потребителем;
m– количество поставщиков;
n– количество потребителей.
Необходимо найти неизвестные показатели хij – количество продукции, перевозимой от поставщиков к потребителю (обратите внимание, что многие показатели хijмогут принимать нулевые значения).
Запомните:
Элементы матрицы cijназываютсякритериями оптимальности.
Совокупность всех элементов матрицы хijназываютсяпланом перевозки.
Проверьте себя:
Правильны ли следующие утверждения?
Векторы SиDназывают критериями оптимальности.
Элементы cij называют планом перевозки.
Элементы хij называют планом перевозки.
Элементы cij называют критериями оптимальности.
Показатели хij> 0.
Показатели хij< 0.
Показатели хij> 0.
Неизвестными являются показатели хij.
Неизвестными являются показатели сij.
Неизвестными являются показатели SiиDj.
Рассмотрим условия задачи с помощью таблицы.
Поставщики и их мощность |
Потребители и их спрос | |||||
D1 |
… |
Dj |
… |
Dn | ||
d1 |
… |
dj |
… |
dn | ||
S1 |
s1 |
с11 х11 |
… |
с1j х1j |
… |
с1n х1n |
… |
… |
… |
… |
… |
… |
… |
Si |
si |
ci1 xi1 |
… |
cij хij |
… |
cin хin |
… |
… |
… |
… |
… |
… |
… |
Sm |
sm |
cm1 хm1 |
… |
|
… |
cmn хmn |
Каждый поставщик должен отдать потребителям столько продукции, сколько у него есть. Это значит, что сумма поставок по строке должна быть равна мощности этой строки, т.е.
Таких соотношений столько, сколько строк в таблице.
Каждый потребитель должен получить столько продукции, сколько ему требуется. Это значит, что сумма поставок по столбцу должна быть равна спросу этого столбца, т.е.
Таких соотношений столько, сколько столбцов в таблице.
Поскольку полная сумма не зависит от того, как производилось суммирование (по строкам или по столбцам), то сумма мощностей производителя должна быть равна суммарному спросу всех потребителей, т.е.
Требуется составить такой план перевозок, при котором грузооборот будет минимальным
Этот план называется оптимальным.
Показатели мощностей и спросов должны принимать неотрицательные значения, т.е.
Si > 0 иdj> 0.
Отрицательных поставок быть не должно, т.е.
хij> 0.
К показателям cij с математической точки зрения не предъявляется требование неотрицательности. Это вытекает из здравого смысла, т.е.
cij> 0.
Проверьте себя:
Какие утверждения являются неправильными?
Потребитель получает всю продукцию первого же поставщика.
Соотношений должно быть столько, сколько столбцов в матрице задачи.
Соотношений должно быть столько, сколько столбцов в матрице задачи.
Функция цели формулируется следующим образом:
Показатели Siиdjдолжны быть неотрицательными.
Поставки хijдолжны быть неотрицательными.
Запомните:
Количество неизвестных в задаче равно m×n.
Количество уравнений равно m+ n.
Одно (любое) уравнение линейно зависимо от остальных.
Количество линейно независимых уравнений равно m+ n- 1.