- •Элементы линейной алгебры с приложением
- •Введение
- •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
- •Экзаменационные вопросы
23. Геометрическая интерпретация задач линейного программирования
Если в задаче количество неизвестных n больше числа независимых уравнений m на 2, т.е. n – m = 2, то такой задаче можно дать геометрическую интерпретацию.
Для этого выбираем свободные переменные, например х1 и х2. Остальные переменные будут являться базисными. Их можно выразить через свободные переменные следующим образом:
Значения свободных переменных х1 и х2 откладываются по осям Ох1 и Ох2. Эти переменные не могут быть отрицательными, поэтому допустимые значения этих свободных переменных могут лежать только выше оси Ох1 и правее оси Ох2 (см. рис.1).
Рис. 1. Графическое представление свободных переменных в задачах линейного программирования
Базисные переменные также должны быть неотрицательными, т.е.
Пусть х3 = 0, т.е.
.
Это уравнение прямой, которую можно построить в системе координат х1Ох2.
Прямая х3 = 0 проходит таким образом, что по одну сторону от этой прямой лежат точки, соответствующие х3 > 0, а по другую – соответствующие х3 > 0. Поэтому х3 = 0 делит всю область переменных х3 на две полуплоскости – допустимых и запрещенных значений (см. рис.1).
Таким же образом строятся и все остальные ограничивающие прямые: х4 = 0, х5 = 0, … хn = 0. Штриховкой отмечается допустимая область.
Каждая прямая соответствует обращению в 0 одной из переменных. В точках пересечения в 0 будут обращаться две переменные. Число (n - m) определяет число свободных переменных. Их обращение в 0 соответствует базисному решению. Все переменные в совокупности ограничивают область допустимых решений (ОДР), которая представляет собой выпуклый многоугольник (рис.2).
Рис. 2. Выделение области допустимых решений
Цель задачи заключается в нахождении оптимального решения, которое обращает линейную функцию цели при n – m = вmin (max). Этой задаче можно дать геометрическую интерпретацию. Для этого подставим в уравнение целевой функции значения базисных переменных. Получим
,
где - свободный член (его в первоначальном виде не было, но он может появиться при переходе к переменным х1 и х2).
Допустим, что
.
Тогда получаем уравнение прямой на плоскости х1Ох2. Угловой коэффициент этой прямой равен . На оси ординат эта прямая отсекает отрезок, равный.
При изменении величины Q угловой коэффициент прямой не изменится. Изменяется только начальная ордината, т.е. прямая перемещается параллельно самой себе, образуя линии равного уровня целевой функции.
Если, то поученная прямая проходит через начало координат (рис. 3).
Рис. 3. Образование линий равного уровня целевой функции
Направление, в котором должна двигаться основная прямая, чтобы величинаQ убывала, зависит от знаков коэффициентов . Если оба коэффициента положительны, то прямая будет двигаться вниз и влево (рис. 4а) и т. д. Направление движения прямой при различных коэффициентахпоказаны на рис. 4.
Рис. 4. Направления убывания Q линий равного уровня целевой функции при различных коэффициентах:
а - ; б -; в -; г -.
Функция цели L достигает максимального значения, когда прямая будет проходить через крайнюю точку области допустимых решений, наиболее удаленную от начала координат. Координата этой точки (х1, х2) определяет оптимальное решение задачи линейного программирования.
Для примера найдем максимальное значение функции цели
F= 4x1 + 3x2
при ограничениях
Решим эту задачу графически. Сначала построим область допустимых значений для двух ограничений: х1>5 и x2>15 (рис. 5).
Рис. 5. Область допустимых значений для х1>5 и х2>15
Область допустимых значений для х1 будет располагаться справа от прямой х1=5, а для х2 – сверху от прямой х2 = 15.
Аналогичным образом поступим с тремя оставшимися ограничениями. Запишем их сначала как равенства. Каждое из этих равенств является уравнением прямой, которое можно изобразить графически.
Найдем оптимальное решение задачи. Пусть
F= 4x1 + 3x2 = Q.
ЕслиQ=0, то прямая F проходят через начало координат. С увеличением значения Q прямая будет перемещаться в направления, указанном на рис. 6.
Рис. 6. Направление движения прямой F при увеличения значений Q
Максимальное значение целевой функции приходится на одно из крайних положений прямой F в пределах области допустимых значений. Оптимальное решение считается найденным, если точка пересечения прямой F с наиболее удаленной (по ходу F) вершиной выпуклого многогранника ABCDE. В нашем примере такой точкой будет точка D(30, 20) (рис. 7).
Рис. 7. Оптимальное решение задачи
Подставляя координаты этой точки в уравнение целевой функции, получим решение данной задачи:
F= 4x1 + 3x2 = 4∙30+3∙20=180.
Если увеличить число переменных таким образом, что n – m = 3, то для геометрической интерпретации необходимо пространственное построение объемной области допустимых решений. Область допустимых решений (если она существует) представляет собой выпуклый многоугольник (рис. 8).
Рис. 8. Графическое представление задачи линейного программирования
в случае n – m=3.
Вместо прямой постоянного уровня целевой функции для n – m = 2, в случае n – m = 3 возникает поверхность постоянного уровня целевой функции. Ее уравнение
.
Если количество свободных переменных х1, х2, х3 больше 3, то решение задачи линейного программирования можно осуществлять геометрическим построением выпуклого многогранника допустимых решений в неотрицательном октанте n-мерного функционального пространства.
Проверьте себя.
Найдите геометрическим способом оптимальное решение задачи
F=20x1+35x2 min
при ограничениях