ВУЗ:
Составители:
20
Решение системы уравнений, в которой число переменных n больше
числа уравнений m, можно найти, если n – m каких-либо переменных положить
равными нулю. Тогда полученную при этом систему m уравнений с n
неизвестными можно решить обычными методами алгебры. Найденное при
этом решение называют базисным. Базисом называют любой набор
переменных m, таких, что определитель, составленный из коэффициентов при
этих
переменных, не равен нулю.
Эти m переменных называют базисными переменными. Остальные n – m
переменных называют свободными переменными. Если принять все свободные
переменные равными нулю и решить полученную систему m уравнений с n
неизвестными, то получим базисное решение. Однако среди базисных решений
будут такие, которые дадут отрицательные значения некоторых базисных
переменных, что противоречит условию задачи, поэтому
так ие решения
недопус тимы. Кроме того, при нахождении минимального (максимального)
значения целевой функции необходимо из допустимых базисных решений
выбрать такое, которое обращает функцию в минимум (максимум).
В настоящее время разработаны рациональные способы перебора
базисных решений, которые позволяют рассматривать не все допустимые
базисные решения, а их минимальное число. Наиболее распространенными
методами такого перебора
являются так называемый симплекс-метод и
табл ичный метод.
Суть симплекс-метода состоит в следующем:
1. Находят какое-либо допустимое базисное решение. Его можно найти,
приняв какие-либо m – n переменные за свободные, приравняв их к нулю и
решив получившуюся систему уравнений. Если при этом некоторые из
базисных переменных окажутся отрицательными, то нужно выбрать
другие
свободные переменные, т. е. перейти к новому базису.
2. Проверяют, не дос тигнут ли уже максимум целевой функции при
найденном допустимом базисном решении.
3. Если оптимальное решение не найдено, то ищут новое допустимое
базисное решение, но не любое, а такое, которое увеличивает значение целевой
функции.
Проверку того, достигнут ли при найденном
допустимом решении
максимум целевой функции, можно сделать путем поиска нового базисного
решения. Для перехода к новому базисному решению одну из свободных
переменных следует сделать базисной, при этом она станет отличной от нуля,
т. е. возрастет. Следовательно, если какая-либо из свободных переменных
входит в выражение для целевой функции со знаком «+» и
при ее увеличении
целевая функция увеличивается, то максимум целевой функции не достигнут, и
данную переменную следует превратить в базисную, сделав ее отличной от
Страницы
- « первая
- ‹ предыдущая
- …
- 19
- 20
- 21
- 22
- 23
- …
- следующая ›
- последняя »
