Читайте также:
|
Каждый набор переменных (
), удовлетворяющий системе ограничений (2.2) и требованию неотрицательности 
(
)называется допустимым решением рассматриваемой задачи ЛП, а множество всех таких наборов называется множеством или областью допустимых решений (ОДР). Для осуществления решения задачи ЛП необходимо (хотя и не достаточно), чтобы ОДР не была пустым множеством, а для этого нужно прежде всего, чтобы система уравнений (2.2) была совместна. Для этого (в соответствии с теоремой Кронекера - Капелли) необходимо и достаточно, чтобы ранг матрицы системы А был равен рангу расширенной матрицы этой системы 
, где
Ранг матрицы – это наибольший порядок отличных от нуля миноров этой матрицы. Будем считать, что указанное выше условие совместности системы (2.2) выполнено и ранг матрицы 
обозначать 
.
Для совместной системы возможны два случая.
1.Ранг системы равен числу неизвестных, т.е. = m. Тогда система (2.2) имеет единственное решение 
. Если все компоненты 
этого решения неотрицательны, то ОДР состоит из одной точки 
. Она и является решением рассматриваемой КЗЛП.
2.В случае, когда 
, система (2.2) имеет бесконечное множество решений. Его образуют наборы значений переменных (
), в которых (n-r)-переменных, называемых свободными, принимают любые значения, а остальные r переменных, называемых базисными, определяются в виде линейной комбинации соответствующих значений свободных переменных.
\В указанном бесконечном множестве решений системы (2.2) нужно выделить образующее ОДР подмножество тех решений, в которых все переменные неотрицательны. Если оно не окажется пустым, то в нем и следует искать решение 
, при котором целевая функция (2.1) принимает наименьшее значение.
Дата добавления: 2015-04-11; просмотров: 39 | Поможем написать вашу работу | Нарушение авторских прав |