- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Система m линейных уравнений с n неизвестными презентация
Содержание
- 1. Система m линейных уравнений с n неизвестными
- 2. Система m линейных уравнений с n переменными имеет вид
- 3. В задачах линейного программирования представляют интерес
- 4. Любые m переменных системы m линейных уравнений с n переменными (m
- 5. Базисным решением системы m линейных уравнений с
- 6. Основными могут быть разные группы из n переменных. Максимальное число групп основных переменных
- 7. Пример. Найти все возможные группы основных переменных в системе
- 8. Решение системы называется допустимым, если оно
- 9. Базисным решением системы m линейных уравнений
- 10. Пример. Найти все базисные решения системы
- 11. Симплексный метод решения задач линейного программирования
- 12. Решение любой задачи линейного программирования можно
- 13. Оптимальный план - совокупность значений переменных,
- 14. Для реализации симплексного метода необходимо освоить
- 15. Пусть требуется найти максимальное (минимальное) значение функции
- 16. при условиях
- 18. Алгоритм решения задачи симплексным методом: привести
- 19. если выполняется критерий оптимальности решения, то
- 20. Для нахождения первоначального базисного плана все
- 21. Критерий оптимальности решения при отыскании максимума(минимума)
- 22. Если система ограничений непротиворечива, то выполнение
- 23. Алгоритм решения задачи линейного программирования построением симплексной таблицы
- 24. Алгоритм: 1. Систему линейных неравенств записываем
- 25. После введения добавочных переменных систему уравнений и линейную функцию записываем в виде:
- 27. 2. Исходную расширенную систему заносим в первую симплексную таблицу.
- 29. 3. Проверяем выполнение критерия оптимальности
- 30. 4 Если критерий оптимальности не выполнен,
- 31. Составляем оценочные отношения каждой строки по
- 32. Определяем
- 33. Если конечного минимума нет, то задача
- 34. 5. Переходим к следующей таблице по
- 35. новую строку с номером q получаем
- 36. Пример. Решим задачу об использовании ресурсов
- 39. 1. Шаг
- 40. Заполняем первую симплексную таблицу, в которой переменные х3,х4,х5,х6 - основные
Система m линейных уравнений с n переменными имеет вид
Слайд 3
В задачах линейного программирования представляют интерес системы, в которых ранг матрицы
r системы A=(aij), i=1,2…m, j=1,2…n, или, что то же самое, максимальное число независимых уравнений меньше числа переменных
Слайд 4
Любые m переменных системы m линейных уравнений с n переменными (m
называются основными (или базисными), если определитель матрицы коэффициентов при них отличен от нуля.
Тогда остальные n - m переменных называются неосновными ( или свободными)
Тогда остальные n - m переменных называются неосновными ( или свободными)
Слайд 5Базисным решением системы m линейных уравнений с n переменными называется решение,
в котором все n-m неосновных переменных равны нулю.
В задачах линейного программирования особый интерес представляют допустимые базисные решения (опорные планы).
Число базисных решений является конечным.
Базисное решение, в котором хотя бы одна из основных переменных равна нулю, называется вырожденным.
В задачах линейного программирования особый интерес представляют допустимые базисные решения (опорные планы).
Число базисных решений является конечным.
Базисное решение, в котором хотя бы одна из основных переменных равна нулю, называется вырожденным.
Слайд 6Основными могут быть разные группы из n переменных. Максимальное число групп
основных переменных
Слайд 8
Решение системы называется допустимым, если оно содержит только неотрицательные компоненты, в
противном случае – решение допустимое.
Слайд 9
Базисным решением системы m линейных уравнений с n переменными называется решение,
в котором все n-m неосновных переменных равны нулю
Слайд 12
Решение любой задачи линейного программирования можно найти симплексным методом.
Симплексный метод
решения задачи линейного программирования основан на переходе от одного опорного плана к другому, при котором значение целевой функции возрастает ( убывает) (при условии, что данная задача имеет оптимальный план).
Слайд 13
Оптимальный план - совокупность значений переменных, при которых достигается наибольшее или
наименьшее значение целевой функции, любая другая совокупность значений, удовлетворяющая ограничениям, определяет опорный (базисный) план.
Слайд 14
Для реализации симплексного метода необходимо освоить три основных элемента:
Способ определения какого-либо
первоначального допустимого базисного решения задачи (опорного плана)
Правило перехода к лучшему (не худшему) решению
Критерий проверки оптимальности найденного решения.
Правило перехода к лучшему (не худшему) решению
Критерий проверки оптимальности найденного решения.
Слайд 18
Алгоритм решения задачи симплексным методом:
привести задачу линейного программирования к стандартному виду.
найти
начальное базисное решение (опорный план). Если базисное решение отсутствует, задача не имеет решения в виду несовместности системы ограничений
проверить полученное базисное решение на оптимальность с помощью критерия оптимальности
проверить полученное базисное решение на оптимальность с помощью критерия оптимальности
Слайд 19
если выполняется критерий оптимальности решения, то решение задачи заканчивается
если выполняется условие
существования множества оптимальных решений, то путем простого перебора найти все оптимальные решения
если имеют место условия неограниченности целевой функции, то задача не имеет решения
если пункты 4 - 6 алгоритма не выполняются, найти новое опорное решение и перейти к пункту 3
если имеют место условия неограниченности целевой функции, то задача не имеет решения
если пункты 4 - 6 алгоритма не выполняются, найти новое опорное решение и перейти к пункту 3
Слайд 20
Для нахождения первоначального базисного плана все переменные разбиваются на две группы:
основные(базисные) и неосновные.
Положив неосновные переменные равными нулю, получаем базисное решение.
Положив неосновные переменные равными нулю, получаем базисное решение.
Слайд 21
Критерий оптимальности решения при отыскании максимума(минимума) линейной функции:
Если в выражении линейной
функции через неосновные переменные отсутствуют положительные (отрицательные) коэффициенты при неосновных переменных, то решение оптимально.
Слайд 22
Если система ограничений непротиворечива, то выполнение конечного числа последовательных шагов симплексного
метода приводит к нахождению оптимального решения задачи.
Слайд 24
Алгоритм:
1. Систему линейных неравенств записываем в каноническом виде. Для этого в
каждое неравенство добавляем дополнительную переменную со знаком «+», если неравенство имеет знак меньше или равно и со знаком «-» в противном случае
Слайд 25
После введения добавочных переменных систему уравнений и линейную функцию записываем
в виде:
Слайд 29
3. Проверяем выполнение критерия оптимальности при решении задач на максимум-
наличие в последней строке отрицательных коэффициентов.
Если таковых нет, то полученное решение оптимально.
Если таковых нет, то полученное решение оптимально.
Слайд 30
4 Если критерий оптимальности не выполнен, то наибольший по модулю отрицательный
элемент в последней строке определяет разрешающий столбец s
Слайд 31
Составляем оценочные отношения каждой строки по правилам:
∞, если bi и ais
имеют разные знаки;
∞, если bi=0 и ais <0
∞, если ais =0
, если bi и ais имеют одинаковые
знаки
∞, если bi=0 и ais <0
∞, если ais =0
, если bi и ais имеют одинаковые
знаки
Слайд 33
Если конечного минимума нет, то задача не имеет конечного оптимума (Fmax=∞)
Если
минимум конечен, то выбираем строку, в которой он достигается и называем ее разрешающей строкой q.
На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент аqs
На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент аqs
Слайд 34
5. Переходим к следующей таблице по правилам:
в левом столбце записываем новый
базис: вместо основной переменной хq- переменную xs
в столбцах, соответствующим основным переменным проставляем нули и единицы: 1 – против «своей» основной переменной 0- против «чужой» основной переменной. 0 в последней строке для всех основных переменных.
в столбцах, соответствующим основным переменным проставляем нули и единицы: 1 – против «своей» основной переменной 0- против «чужой» основной переменной. 0 в последней строке для всех основных переменных.
Слайд 35
новую строку с номером q получаем из старой строки делением на
разрешающий элемент aqs
все остальные элементы получаем по правилу прямоугольника:
все остальные элементы получаем по правилу прямоугольника:
