Применение методов теории графов и линейного программирования для решения производственных и технологических задач. Веткасов Н.И - 28 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

25
Решение системы уравнений (13), в которой число переменных п
больше числа уравнений т, можно найти, если n-m каких-либо переменных
положить равными нулю. Тогда полученную при этом систему m уравнений с
п неизвестными можно решить обычными методами алгебры. Найденное при
этом решение называют базисным. Базисом называют любой набор пе-
ременных т, таких, что определитель, составленный из коэффициентов при
этих переменных, не равен нулю.
Эти m переменных называют базисными переменными. Остальные n-m
переменных называют свободными переменными. Если принять все свободные
переменные равными нулю и решить полученную систему m уравнений с п
неизвестными, то получим базисное решение. Однако среди базисных
решений будут такие, которые дадут отрицательные значения некоторых ба-
зисных переменных, что противоречит условию задачи, поэтому такие решения
недопустимы. При нахождении минимального значения целевой функции (11)
необходимо из допустимых базисных решений выбрать такое которое обращает
в минимум функцию (11).
В настоящее время разработаны рациональные способы перебора ба-
зисных решений, которые позволяют рассматривать не все допустимые ба-
зисные решения, а их минимальное число. Наиболее распространенными ме-
тодами такого перебора являются так называемый симплекс-метод и табличный
метод.
\
2.2. СИМПЛЕКС-МЕТОД РЕШЕНИЯ ЗАДАЧИ
ЛИНЕЙНОГО ПРОГРАММИРОВ АНИЯ
Суть симплекс-метода состоит в следующем:
1. Находят какое-либо допустимое базисное решение. Его можно найти,
приняв какие-либо m-n переменные за свободные, приравняв их к нулю и
решив получившуюся систему уравнений. Если при этом некоторые из ба-
зисных переменных окажутся отрицательными, то нужно выбрать другие
свободные переменные, т.е. перейти к новому базису.
2. Проверяют, не достигнут ли уже максимум целевой функции при
найденном допустимом базисном решении.
3. Если оптимальное решение не найдено, то ищут новое допустимое
базисное решение, но не любое, а такое, которое увеличивает значение целевой
функции.
Проверку того, достигнут ли при найденном допустимом решении мак-
симум целевой функции, можно сделать путем поиска нового базисного ре-
шения. Для перехода к новому базисному решению одну из свободных пере-
менных следует сделать базисной, при этом она будет отличаться от нуля,

Страницы