Мы можем увидеть пространство решений графического метода, имеющее бесконечное число точек решений, но как можно сделать подобное заключение на основе алгебраического представления пространства решений?
Ответ заключается в том, что в алгебраическом представлении количество уравнений m всегда меньше или равно количеству переменных n. Если m = n и система уравнений совместна, то
она имеет только одно решение; если же m < n и система уравнений совместна, то она имеет бесконечное множество решений.
11
Рассмотрим ЗЛП: Z(х1;x2) = 2х1 + 3x2 → max;
2x1 + x2 4, х1 + 2х2 5, x1, x2 0.
12
После преобразования к стандартной форме имеем следующую ЗЛП.
Z(х1;x2) = 2х1 + 3x2 → max;
2x1 + x2 + s1 4, х1 + 2х2 5,
x1, x2,s1,s20.
13
Имеем систему из m=2 уравнений для
n=4 переменных. Согласно сформули- рованному выше правилу угловые точки можно определить алгебраически, присвоив n–m=4–2=2 переменным нулевые значения и решив затем систему уравнений
относительно оставшихся m=2 переменных. Если, например, положить x1=0 и х2=0,
тогда решением системы будет s1=4, s2=5. Это решение соответствует точке А.
14
Другую угловую точку можно определить, если положить s1=0 и s2=0.
В этом случае надо найти решение системы:
2x1+ x2 = 4, x1 + 2x2= 5.
15
Решением в будет x1=1 и x2=2, что
соответствует точке С. Без графического представления пространства решений нельзя сказать, какие n–m нулевые переменные соответствуют той или иной угловой точке. Однако это не мешает перечислить все угловые точки пространства решений. Для этого надо просто рассмотреть все комбинации n-m переменных, приравнять их к нулю и затем найти решение полученной системы уравнений. Оптимальное решение, которое доставляет наилучшее значение целевой функции, будет
среди допустимых угловых точек. |
16 |
В нашем примере имеем угловых точек. Но, глядя на рисунок
можно насчитать только 4 угловые точки — А, В, С и D.
Где "спрятались" еще две точки?
17
В действительности точки Е и F также являются угловыми точками, но это недопустимые угловые точки, поскольку они не удовлетворяют всем ограничениям задачи.
Такие недопустимые угловые точки не рассматриваются как кандидаты на оптимальное решение.
18
Для полного перехода к алгебраическому методу решения задач ЛП необходимо как-то назвать угловые точки разного типа на "алгебраическом" языке. На этом языке n – m переменные, которые полагаются равными нулю, называются небазисными переменными.
Если оставшиеся m переменные имеют единственное решение, то в этом случае они называются базисными переменными, а совокупность значений, которые они получают в результате решения системы уравнений, составляют базисное решение.
Если при этом все переменные принимают неотрицательные значения, то такое базисное решение является допустимым. В противном случае — недопустимым.
19
В таблице перечислены все базисные и небазисные решения текущего примера.
20