Допустим, дана система т линейно независимых уравнений с n неизвестными x1,…, хп, называемая системой ограничений задачи линейного программирования:
Характерной особенностью данной задачи является то, что число уравнений меньше числа неизвестных, т. е. m<n. Требуется найти неотрицательные значения переменных , которые удовлетворяют уравнениям ограничения и обращают в минимум целевую функцию
Иногда в задаче линейного программирования все или некоторые из уравнений имеют вид неравенств. Так, вместо уравнения
в систему может входить неравенства вида
или
От таких неравенств легко перейти к уравнениям, вводя добавочную переменную хn+j³0 так, чтобы в зависимости от знака неравенства имело место одно из двух выражений
Поскольку число переменных п в этой системе больше числа уравнений т, то одно из возможных решений можно найти, если п — т каких-либо переменных положить равными нулю. Полученную при этом систему т уравнений с т неизвестными можно решать обычными методами линейной алгебры. Правда, для того чтобы система т уравнений с т неизвестными имела решение, необходимо, чтобы определитель, составленный из коэффициентов при неизвестных, не обращался в нуль. Если это условие не выполняется, то можно приравнять нулю другие п — т переменных. Полученное при этом решение называется базисным решением.
|
|
Базисом называется любой набор т переменных, таких, что определитель, составленный из коэффициентов, при этих переменных не равен нулю. Эти т переменных называются базисными переменными (по отношению к данному базису). Остальные п — т переменных называются небазисными или свободными переменными В каждой конкретной системе уравнений может существовать несколько различных базисов с различными базисными переменными.
Если положить все свободные переменные равными нулю и решить полученную систему т уравнений с т неизвестными, то получим базисное решение. Однако среди различных базисных решений будут такие, которые дают отрицательные значения некоторых переменных. Эти базисные решения противоречат условию задачи и являются недопустимыми.