Вспомним некоторые вопросы из алгебры.
Рассмотрим неравенство а´х £ b. Если от неравенства мы хотим перейти к уравнению, то введём дополнительную переменную у и запишем а´х +у = b, т.е. получим одно уравнение с двумя неизвестными.
В общую постановку задачи оптимизации входят неравенства вида (i =1...т), где п – число неизвестных; т – число неравенств. Если в каждое неравенство добавить неотрицательное неизвестное yi ³ 0 (i = 1...m), то от системы неравенств можно перейти к системе уравнений (i = 1...m).
В этой системе общее число неизвестных N = n+m, где п – число основных неизвестных xj; т – число дополнительных неизвестных yi, которое равно числу уравнений.
Возможны три варианта соотношения величин N и т.
1. Число неизвестных меньше, чем число уравнений: N < m.
Например, , т.е. N =1, т =2. Очевидно, эта система решения не имеет, т.е. нет таких значений х1, которые удовлетворяли бы обоим уравнениям. В этом случае говорят, что система условий несовместна. Значит, если число неизвестных N меньше числа уравнений т, то система решения не имеет и является несовместной.
2. Число неизвестных равно числу уравнений: N = m.
Например, . Нетрудно найти, что решением этой системы будут значения х1 =2, х2=1. Таким образом, линейная система, в которой число неизвестных N равно числу уравнений т, имеет одно решение.
Наличие (2) или отсутствие решений (1) при различных соотношениях числа переменных N и числа уравнений т справедливо только для линейно–независимых уравнений, которые не могут быть получены умножением, делением, сложением, вычитанием исходных уравнений.
Например, пусть есть уравнение 2х = 10, из которого можно получить несколько: х=5; 4х=20; 6х=30 и т.д. Все эти уравнения будут линейно зависимыми, и новых сведений о зависимостях для переменной не содержат. Поэтому в этом примере т=1 (а не 4).
Аналогично в системе
есть только два линейно независимых уравнения, так уравнение (в) есть результат суммирования (а) и (б), а уравнение (г) есть результат деления (в) на 5.
3. Число неизвестных больше числа уравнений: N > m. Например, 2х1 + +х2 = 2. Очевидно, что все значения х1 и х2, лежащие на прямой (рис.2.1) этого уравнения, являются его решением. Значит это уравнение имеет бесчисленное множество решений. Итак, если в системе число неизвестных N больше числа уравнений т, то такая система имеет бесчисленное множество решений.
В случае, когда система имеет более одного возможного решения, может быть поставлена задача оптимизации. При этом суть такой задачи, как мы уже знаем, заключается в том, чтобы из всех допустимых решений, удовлетворяющих ограничениям и граничным условиям, выбрать такое, которое придаёт ЦФ оптимальное, т.е. максимальное или минимальное значение.
Если все ограничения и ЦФ линейны, задача оптимизации, как нам известно, является задачей ЛП.